数据结构课件：第2章 线性表1链式

1、一元多项式的表示及相加第2章 线性表线性表的类型定义线性表的顺序表示和实现线性表的链式表示和实现2.3 线性表的链式表示及实现线性表的链式表示线性表的链式实现链表的运算效率分析线性表的链式表示逻辑上相邻，物理上不一定相邻 2.3 线性表的链式表示及实现 a 201BH b 1087H z NULL a1 a2 an / HeadHeadDataLinkDataLinkDataLinkDataLink链表存放示意图如下：(a，b，c，d，e , z)线性表的链式表示线性表的链式存储结构，也称为链表。数据元素通过指针表示数据元素之间的关系。 2.3 线性表的链式表示及实现 a1 a2 an / H

2、ead特点1：每个存储结点都包含两部分：数据和 。特点2：在单链表中，除了首元结点外，任一结点的存储位置 由 指示。 其直接前驱结点的链域的值指针域(链域)线性链表的有关术语结点: 数据元素的存储映像。由数据域和指针域两部分组成； 链表: n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为链式存储结构2.3 线性表的链式表示及实现信息域 指针域结点的结构 info next a1 a2 an / Head线性链表的有关术语头指针: 是指向链表中第一个结点(或为头结点或为首元结点)的指针。单链表可由一个头指针唯一确定。2.3 线性表的链式表示及实现 a1 a2 an / Head头指针

3、线性链表的有关术语头结点: 是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息;首元结点: 存储第一个数据元素a1的结点2.3 线性表的链式表示及实现 a1 an / Head首元结点头结点线性链表的有关术语链表设置头结点的作用插入或删除表中任何结点，都需修改前一结点的指针域。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除结点时需单独处理，操作较复杂。带头结点的链表，链表指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。2.3 线性表的链式表示及实现一个线性表的逻辑结构为:2.3 线性表的链式表示及实现（ZHAO,QIAN,SUN,LI,ZHOU

4、,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。 ZHAO 7 HeadDataLink31上例链表的逻辑结构示意图有以下两种形式2.3 线性表的链式表示及实现区别： 无头结点 有头结点 ZHAO QIAN SUN LI Head ZHOU WU ZHENG WANG / ZHAO QIAN SUN LI Head ZHOU WU ZHENG WANG

5、 / 线性表的单链表存储结构2.3 线性表的链式表示及实现Typedef struct Lnode ElemType data; /数据域 struct Lnode *next; /指针域Lnode, *LinkList; / *LinkList为Lnode类型的指针线性链表的实现1.单链表的建立2.单链表的查找3.单链表的插入4.单链表的删除5.其它链表形式2.3 线性表的链式表示及实现单链表的建立难点分析：每个数据元素在内存中是“零散”存放的，其首地址怎么找？又怎么一一链接？实现思路：先开辟头指针，然后陆续为每个数据元素开辟存储空间并赋值，并及时将地址送给前面的指针。2.3 线性表的链式表

6、示及实现单链表的建立2.3 线性表的链式表示及实现操作步骤：一、建立一个“空表”；二、输入数据元素an， 建立结点并插入；三、输入数据元素an-1， 建立结点并插入；an四、依次类推，直至输入a1为止。anan-1单链表的建立2.3 线性表的链式表示及实现Void CreateList_L (LinkList &L, int n) /逆位序输入n个元素的值,建立带表头结点的单链线性表L. L = (LinkList) malloc (sizeof(LNode); Lnext = NULL; / 先建立一个带头结点的单链表 for ( i =n; i0; -i) p=(LinkList)mall

7、oc (sizeof(LNode); / 生成新结点 scanf (&p data); / 输入元素值 pnext = Lnext ; Lnext = p; / 插入到表头 / CreateList_L单链表的查找难点：单链表中想取得第i个元素，必须从头指针出发寻找(顺藤摸瓜)，不能随机存取 。思路：要修改第i个数据元素，关键是要先找到该结点的指针p，然后用p-data=new_value 即可。2.3 线性表的链式表示及实现单链表的查找例1：单链表中 GetElem(L,i,&e) 的实现2.3 线性表的链式表示及实现L211830754256pppj123单链表的查找2.3 线性表的链式表

8、示及实现Status GetElem_L(LinkList L, int i, ElemType &e) / L为带头结点的单链表的头指针 / 当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR P = L-next; j=1; / 初始化 ,p指向第一个结点,j为计数器 while(p&jnext; +j; / 顺指针向后查找,直到p指向第i个元素或p为空 if(!p|ji) return ERROR; / 第i个元素不存在 e=p-data; / 取第i个元素 return OK; / GetElem_L单链表的插入单链表中 ListInsert(&L,i,e) 的实现2.3 线

9、性表的链式表示及实现 改变为 和 eai-1ai-1spai单链表的插入2.3 线性表的链式表示及实现s = new LNode; / 生成新结点if ( s = NULL) return ERROR;s-data = e; s-next = p-next; p-next = s; / 插入return OK;(2)(1)(3) eai-1ai-1spai单链表的插入可见，在链表中插入结点只需修改指针。但同时，若要在第 i个结点之前插入元素，修改的是第 i-1个结点的指针。因此，在单链表中第 i个结点之前进行插入的基本操作为：找到线性表中第i-1个结点，然后修改其指向后继的指针。2.3 线性表

10、的链式表示及实现单链表的插入2.3 线性表的链式表示及实现status ListInsert(LinkList &L,int i,ElemType e ) /在带头结点的单链表L中第i个位置之前插入元素e p = L; j = 0; while (p& j next; +j; if (! p | j i-1) return ERROR; s = (LinkList) malloc (sizeof(LNode); s - data=e; s-next= p - next; p - next = s; return OK; / ListInsert_l算法的时间复杂度为：O(ListLength(

11、L)ai-1ai-1单链表的删除单链表中 ListDelete(&L,i,&e) 的实现找到链表中第i-1个结点，修改其指向后继的指针2.3 线性表的链式表示及实现ai+1aiq = p-next; p-next = q-next; e = q-data; free(q);pq单链表的删除2.3 线性表的链式表示及实现Status ListDelete_L(LinkList &L,int i,ElemType &e) / 删除以L为头指针(带头结点)的单链表中第i个结点 p = L; j = 0; while (p-next & j next; +j; / 寻找第 i 个结点，并令 p 指向其

12、前趋 if (!(p-next) | j i-1) return ERROR; / 删除位置不合理 q = p-next; p-next = q-next; / 删除并释放结点 e = q-data; free(q); return OK; / ListDelete_L算法的时间复杂度为:O(ListLength(L)2.3 线性表的链式表示及实现考虑如何将两个有序链表并为一个有序链表？单链表的合并已知：线性表 A、B，分别由单链表 LA , LB 存储，其中数据元素按值非递减有序排列，要求：将 A ，B 归并为一个新的线性表C , C 的数据元素仍按值非递减排列 。设线性表 C 由单链表 L

13、C 存储。假设: A=(3，5，8，11) B=(2，6，8，9，11)预测:合并后 C =(2 , 3 , 5 , 6 , 8 , 8 , 9 , 11 , 11)2.3 线性表的链式表示及实现单链表的合并A、B、C用链表可表示为2.3 线性表的链式表示及实现 3 511 / 8 LA 2 611 / 8 LB 9 2 3 6 5 LC 811 8 911 /单链表的合并算法主要包括：搜索、比较、插入三个操作：搜索：需要两个指针搜索两个链表；比较：比较结点数据域中数据的大小；插入：将两个结点中数据小的结点插入新链表2.3 线性表的链式表示及实现单链表的合并2.3 线性表的链式表示及实现 3

14、511 / 8 LA 2 611 / 8 LB 9 2 3 5 6 LC 8 8 911 11 /PaPbPcPcPaPbPaPbPaPbPbPcPcPcPcPcPcPc单链表的合并2.3 线性表的链式表示及实现 Void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) /按值排序的单链表LA,LB，归并为LC后也按值排序 free(Lb); /释放Lb的头结点 /MergeList_L pc-next = pa?pa:pb ; /插入剩余段 while(pa&pb) /将pa 、pb结点按大小依次插入C中 if(pa-datadata)

15、 pc-next=pa; pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next pa=La-next; pb=Lb-next; Lc=pc=La； /初始化 其它链表形式2.3 线性表的链式表示及实现1）双向链表：有两个指针域的链表，称为双链表。 # Head prior data nextA. 结点结构B. 特点：可以双向查找表中结点 a1 a2 an / # Head空表其它链表形式2.3 线性表的链式表示及实现1）双向链表：插入运算 s-next = p-next; p-next = s;s-next-prior = s; s-pri

16、or = p; ai-1 ai esp其它链表形式2.3 线性表的链式表示及实现1）双向链表：删除运算 p-next = p-next-next;p-next-prior = p; ai-1 aip ai+1其它链表形式2.3 线性表的链式表示及实现2）循环链表：将表中最后一个结点的指针域指向头结 点( p-next=head)，整个链表形成一个环。 # a1 an HeadB.与单链表的区别 (循环条件) 和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。A.特点：从任一结点出发均可找到表中其他结点。时间效率分析查找: 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。插入和删除: 因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。但如果要在单链表中进行前插或删除操作，由于要查找前驱结点，所耗时间复杂度为 O(n)。2.3 线性表的链式表示及实现空间效率分析链表中每个结点都要增加一个指针空间，相当于总共增加了n个整型变量，空间复杂度为 O(n)。2.3 线性表的链式表示及实现(1)顺序表是用数组实现的，而链表是用指针来实现的。(