数据结构与算法教程 朱明方 吴及 第3章 链表

《数据结构与算法教程 朱明方 吴及 第3章 链表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章链表3.1线性表的链式存储一、线性链表的概念二、线性链表及其结点的结构定义三、线性链表的运算3.2链式栈与链式队列一、链式栈二、链式队列3.3循环链表一、循环链表的结构二、循环链表的基本运算第三章链表3.4多重链表一、多重链表的结构二、双向链表3.5广义表一、广义表的概念二、广义表的存储表示三、广义表的运算一、线性链表的概念线性链表——线性表的链式存储。1.为什么提出链表结构①存储空间不能满足线性表要求;线性表长n>连续的存储空间大小。②事先不能确定线性表所需要的存储空间的大小如,多项式的表示与运算:A(x)=a0+a1x+a2x+…+anxB(x)=b0+b1x+…+bmx运算前后有

2、哪些项？③线性表长经常发生变化如,空闲单元管理——应用程序经常要取用和释放所占用的存储空间。3.1线性表的链式存储3.1线性表的链式存储2.线性链表的结构形式结构特点:①用一组任意的存储单元存储线性表中的元素②存储数据元素之间的关系好处:灵活利用存储空间,提高插入、删除运算效率数据元素的存储映像——结点结点结点的图形表示：元素指针数据域指针域3.1线性表的链式存储例如,线性表(a1，a2，……ai，……，an),结点链接：pdatapnext空指针二、线性链表及其结构定义结点类型的定义:typedefstructLNode{ElemTypedata；//结点值域structLNode*nex

3、t；//结点指针}LNode;表结构类型:structLinkList{LNode*head；//定义单链表头指针};a1a2an∧头指针H结点P……3.1线性表的链式存储三、线性链表的运算1.线性链表的初始化voidInitList(LinkList*HL){HL.head=NULL；//置线性链表的头指针为空}2.求线性链表长度intListlen(LinkList*HL){LNode*p=HL.head；intlen=0；//len存链表长度while(p){p=p->next；len++；}returnlen；//返回链表长度}3.1线性表的链式存储3.线性链表的插入运算在头指针为h

4、ead的线性链表中，在元素b的结点之前插入一个新元素a,如：b∧e…adfb∧eac…headdfchead插入后:3.1线性表的链式存储运算步骤：•分配一个空闲结点p，令P→data=a；•寻找元素b的前一个结点s；•将结点p插入到s与s→next之间；主要问题：如何寻找元素b的前一个结点s?注意特殊情况：•HL为空表；•b处于第1个结点；•b不在HL中；3.1线性表的链式存储dfc∧eak…head找不到b?head=NULL链表空dfc∧eab…head插入在第1个结点位置3.1线性表的链式存储实现算法：voidInsertList(LinkList*HL,ElemTypeb,Elem

5、Typea)//在线性链表HL中的元素b之前插入元素a{LNode*newp,*p,*q;newp=(LNode*)malloc(sizeof(LNode))；//分配一个新结点if(!newp){printf(〃内存动态空间分配失败！″)；exit(1)；}newp->data=a；//置a到新结点的值域if(HL->head==NULL‖HL->head->data=b)//处理空表或元{newp->next=HL->head；//素b处于第一个结点的情况HL->head=newp；return；}3.1线性表的链式存储q=HL->head;p=q->next；//从第2个结点开始查

6、找元素bwhile(p!=NULL&&p->data!=b){q=p；p=p->next；}newp->next=q->next；//若找到元素b，把元素a插入到b之前q->next=newp；//若b不在表中，则把元素a插入到链尾。}主要操作——查找元素b所在结点平均时间复杂度为:O(n)若不要查找插入位置(指定插入位置)，则时间复杂度为O(1)3.1线性表的链式存储4.线性链表的删除运算在头指针为head的线性链表中删除元素b所在的结点dbf∧ec…head运算步骤：☛寻找元素b的前一个结点；☛删除元素b的结点；☛释放被删除结点；算法考虑：①b在第1个结点中；②空表情况、找不到b；③

7、正常删除，释放空闲结点；实现算法：删除后：dcheadf∧e…3.1线性表的链式存储intDeleteList(LinkList*HL,ElemTypeb)//b为指定删除的元素{LNode*p=HL->head,*q=NULL；//q为p的前件结点while(p!=NULL)//在表中找查元素b{if(p->data==b)break；q=p；p=p->next；}if(p==NULL)return0；//