数据结构线性表链式表示和实现.ppt

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第2章 线性表,数据结构讲义,-链式表示和实现,2.3.1 链表的表示,特点：,用一组,任意,的存储单元存储线性表的数据元素,利用,指针,实现了用不相邻的存储单元存放逻辑上相邻的元素,每个数据元素ai，,除存储本身信息外，还需存储其直接后继的信息,结点,数据域：元素本身信息,指针域：指示直接后继的存储位置,2.3,线性表的链式表示和实现,ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG,H,例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG),43,13,1,NULL,37,7,19,25,数据域,指针域,LI,QIAN,SUN,WANG,WU,ZHAO,ZHENG,ZHOU,存储地址,1,7,13,19,25,31,37,43,31,H,头指针,与链式存储有关的术语：,1、结点：,数据元素的存储映像。由数据域和指针域两部分组成；,2、链表：,n 个结点由,指针链,组成一个链表。它是线性表的链式存储映像,，,称为线性表的链式存储结构,。,3、单链表、双链表、多链表、循环链表,：,结点只有一个指针域的链表，称为,单链表,或,线性链表,；,有两个指针域的链表，称为,双链表,；,有多个指针域的链表，称为,多链表,；,首尾相接的链表称为,循环链表,。,a,1,head,a,2,a,n,head,循环链表示意图：,何谓,头指针、头结点和首元结点,？,头指针,是指向链表中第一个结点（或为,头结点,或,为首元结点,）的指针。,单链表可由一个头指针唯一确定。,头结点,是在链表的,首元结点,之前,附设,的一个结点；数据域内只放空表标志和表长等信息;,首元结点,是指链表中存储线性表第一个数据元素,a,1,的结点。,头指针,头结点,首元结点,a,1,一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，,请问其,头指针,的,值,是多少？,存储地址,数据域,指针域,1,LI,43,7,QIAN,13,13,SUN,1,19,WANG,NULL,25,WU,37,31,ZHAO,7,37,ZHENG,19,43,ZHOU,25,例,：,答：,头指针,是指向链表中第一个结点的指针，因此关键是要寻找,第一个结点,的,地址,。,7,ZHAO,H,31,头指针的值是,31,return OK;,插入步骤（即核心语句）：,q=p-next;/保存b的指针，靠它才能指向c,搜索：需要两个指针搜索两个链表；,单链表-p=NULL 或 p-next=NULL,设线性表 C 由单链表 LC 存储。,用一组任意的存储单元存储线性表的数据元素,return OK;,两个链表的归并（教材P31）,有两个指针域的链表，称为双链表；,P-next=q-next;,if(pa-datadata),这种有两个指针的链表称为双向链表。,Step 2：p-next=s；,设线性表 C 由单链表 LC 存储。,pa=La-next;pb=Lb-next;Lc=pc=La；,Void MergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc),2、操作仅有 一 点与单链表不同：循环条件,上例链表的逻辑结构示意图有以下,两种形式,：,ZHAO,QIAN,LI,SUN,ZHOU,WU,ZHENG,/,WANG,H,ZHAO,QIAN,LI,SUN,ZHOU,WU,ZHENG,/,WANG,H,区别：,无头结点,有头结点,答：,讨论1,.在链表中设置,头结点,有什么好处？,讨论2,.如何表示,空表,？,头结点,即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对,空表、非空表,的情况以及对,首元结点,进行统一处理，编程更方便。,答：,无头结点时，,当头指针的值为空,时表示空表；,有头结点时，,当头结点的指针域为空,时表示空表。,头指针,头指针,头结点,无头结点,有头结点,在链表中设置头结点有什么好处？,Void MergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc),while(pa&pb)/将pa、pb结点按大小依次插入C中,查找 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。,S-next=p-next,假设：A=（3，5，8，11），B=（2，6，8，9，11）,利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素,while(p,每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息,free(Lb);/释放Lb的头结点,3 线性表的链式表示和实现,无头结点时，当头指针的值为空时表示空表；,Lnode,*LinkList;/*LinkList为Lnode类型的指针,插入和删除 因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。,删除步骤（即核心语句）：,typedef struct Lnode,ElemType data;,/数据域,struct Lnode *next;,/指针域,Lnode,*LinkList;,/*LinkList为Lnode类型的指针,教材P28对于单链表的,抽象,描述:,结构类型的C语言表示法,介绍三个有用的库函数（都在 中）：,sizeof(,x,)计算变量,x,的长度；,malloc(,m,)开辟,m,字节长度的地址空间，并返回这段空间的首地址；,free(,p,)释放指针,p,所指变量的存储空间，即彻底删除一个变量。,链表的实现,1.单链表的插入,2.单链表的删除,3.链表的合并,实例,1,（和顺序表一样）：一条记录有学号和成绩两个数据项，先不考虑有序的情况编写程序记录数据。,1.单链表的插入,在链表中插入一个元素的示意图如下：,x,s,b,a,p,a,b,p,插入步骤（即核心语句）：,Step 1：,s-next=p-next;,Step 2：,p-next=s；,p-next,s-next,元素x结点应预先生成：,S=(LinkList)malloc(m);,S-data=x;,S-next=p-next,Status,ListInsert(LinkList&L,int i,ElemType e),p=L-next;j=1;,while,(p,&,jnext;+j;,if(!p|ji-1),return,ERROR;,S=(LinkList)malloc(sizeof(Lnode);,S-data=x;,S-next=p-next;,P-next=s;,return,OK;,单链表结点插入的演示,2.单链表的删除,在链表中删除某元素的示意图如下：,c,a,b,p,删除步骤（即核心语句）：,q=p-next;,/,保存,b,的指针，靠它才能指向c,p-next=q-next;,/a、c两结点相连,free(q)；,/删除b结点，彻底释放,p-next,思考：省略,free(q)语句,行不行？,(p-next)-next,Status,ListDelete(LinkList&L,int i,ElemType&e),p=L-next;j=1;,while,(p,&,jnext;+j;,if(!p|ji-1),return,ERROR;,Q=p-next;,P-next=q-next;,E=q-data;,Free(q);,return,OK;,单链表结点的删除演示,3.两个链表的归并（教材P31）,算法要求：,已知：,线性表 A、B，分别由,单链表 LA,LB,存储，其中数据元素按值,非递减有序,排列，,要求：,将 A，B,归并,为一个新的线性表C,C 的数据元素仍按值非递减排列 。设线性表 C 由,单链表 LC,存储。,假设：,A=（3，5，8，11），B=（2，6，8，9，11）,预测：,合并后 C=（2,3,5,6,8,8,9,11，11）,用链表可表示为：,3,5,11,/,8,La,2,6,11,/,8,Lb,9,2,3,6,5,Lc,8,头结点,算法分析：,算法主要包括：,搜索、比较、插入,三个操作：,搜索：,需要,两个指针,搜索两个链表；,比较：,比较结点数据域中数据的大小；,插入：,将两个结点中数据,小的结点插入新链表,。,La,3,5,8,11,Lb,2,6,8,11,9,Pa,Pb,Pa,Pb,Pa、Pb用于搜索La和Lb，,Pc,指向新链表当前结点,Lc,Pa,3,Pc,Pa,5,Pc,11,Pc,2,Pb,Pc,Pa,算法实现：,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),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,；,/初始化,其它链表形式,答：能。只要将表中最后一个结点的指针域指向头结点即可(,P-next=head;,)。这种形成环路的链表称为,循环链表,。,特别：带头结点的,空,循环链表样式,H,参见教材P35,特点：,1、从任一结点出发均可找到表中其他结点。,2、操作仅有 一 点与单链表不同：,循环条件,单链表-p=NULL 或 p-next=NULL,循环链表-p=head 或 p-next=head,讨论1：链表能不能首尾相连？怎样实现？,讨论2：单链表只能查找结点的直接后继，能不能查找直接前驱？如何实现？,答：能。只要把单链表再多开一个指针域即可(例如用,*next和*prior,;,)。,双向链表在非线性结构（如树结构）中将大量使用。,prior,data,next,这种有两个指针的链表称为,双向链表,。其特点是可以双向查找表中结点。参见教材P3539。,特别：带头结点的,空,双向链表样式：,链表的运算效率分析,1.查找,因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为,O,(n),。,时间效率分析,2.插入和删除,因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为,O,(1),。,但是，如果要在单链表中进行,前插,或,删除,操作，由于要从头查找前驱结点，所耗时间复杂度为,O,(n)。,空间效率分析,链表中每个结点都要增加一个指针空间，相当于总共增加了,n,个整型变量，空间复杂度为,O,(n),。,作业,用链表编写完整程序实现以下内容：,一条记录有学号和成绩两个数据项，建立两个有序表（按成绩由大到小），并合并成一个有序表。第一个表输入的数据如下（学号，成绩）：(1,70),(2,85),(3,75),(4,90)；第二个表输入的数据如下：(5,60),(6,80),(7,76),(8,50)。,