武汉理工大学-信息工程学院-数据结构-ppt-课件ch02-2-线性表2-链式表示和实现

第2章线性表数据结构讲义-链式表示和实现信息工程学院魏洪涛Email:[e-mail]2.3.1链表的表示特点：用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点–数据域：元素本身信息–指针域：指示直接后继的存储位置2.3线性表的链式表示和实现ZHAOQIANSUNLIZHOUWUZHENGWANG^H例线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针与链式存储有关的术语：1、结点：数据元素的存储映像。由数据域和指针域两部分组成；2、链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。3、单链表、双链表、多链表、循环链表：•结点只有一个指针域的链表，称为单链表或线性链表；•有两个指针域的链表，称为双链表；•有多个指针域的链表，称为多链表；•首尾相接的链表称为循环链表。a1heada2an……head循环链表示意图：何谓头指针、头结点和首元结点？头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。单链表可由一个头指针唯一确定。头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息;首元结点是指链表中存储线性表第一个数据元素a1的结点。头指针头结点首元结点a1一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例：答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。7ZHAOH31∴头指针的值是31上例链表的逻辑结构示意图有以下两种形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH区别：①无头结点②有头结点答：讨论1.在链表中设置头结点有什么好处？讨论2.如何表示空表？头结点即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。答：无头结点时，当头指针的值为空时表示空表；有头结点时，当头结点的指针域为空时表示空表。^头指针^头指针头结点无头结点有头结点typedefstructLnode{ElemTypedata;//数据域structLnode*next;//指针域}Lnode,*LinkList;//*LinkList为Lnode类型的指针教材P28对于单链表的抽象描述:结构类型的C语言表示法介绍三个有用的库函数（都在stdlib.h中）：sizeof(x)——计算变量x的长度；malloc(m)—开辟m字节长度的地址空间，并返回这段空间的首地址；free(p)——释放指针p所指变量的存储空间，即彻底删除一个变量。链表的实现1.单链表的插入2.单链表的删除3.链表的合并实例1（和顺序表一样）：一条记录有学号和成绩两个数据项，先不考虑有序的情况编写程序记录数据。ch2_ltable1.c1.单链表的插入在链表中插入一个元素的示意图如下：xsbapabp插入步骤（即核心语句）：Step1：s-next=p-next;Step2：p-next=s；p-nexts-next元素x结点应预先生成：S=(LinkList)malloc(m);S-data=x;S-next=p-nextStatusListInsert(LinkList&L,inti,ElemTypee){p=L-next;j=1;while(p&&ji-1){p=p-next;++j;}if(!p||ji-1)returnERROR;S=(LinkList)malloc(sizeof(Lnode));S-data=x;S-next=p-next;P-next=s;returnOK;}单链表结点插入的演示注意：i的范围，循环执行完后i的值是多少？2.单链表的删除在链表中删除某元素的示意图如下：cabp删除步骤（即核心语句）：q=p-next;//保存b的指针，靠它才能指向cp-next=q-next;//a、c两结点相连free(q)；//删除b结点，彻底释放p-next思考：省略free(q)语句行不行？(p-next)-next××注意：j的范围，循环执行完后j的值是多少？StatusListDelete(LinkList&L,inti,ElemType&e){p=L-next;j=1;while(p&&ji-1){p=p-next;++j;}if(!p||ji-1)returnERROR;Q=p-next;P-next=q-next;E=q-data;Free(q);returnOK;}单链表结点的删除演示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）用链表可表示为：3511/\8La2611/\8Lb92365Lc8811/\911头结点算法分析：算法主要包括：搜索、比较、插入三个操作：搜索：需要两个指针搜索两个链表；比较：比较结点数据域中数据的大小；插入：将两个结点中数据小的结点插入新链表。La35811^Lb26811^9PaPbPaPbPa、Pb用于搜索La和Lb，Pc指向新链表当前结点Lc…Pa3PcPa5Pc11^Pc2PbPcPa算法实现：VoidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){//按值排序的单链表LA,LB，归并为LC后也按值排序free(Lb);//释放Lb的头结点}//MergeList_Lpc-next=pa?pa:pb;//插入剩余段while(pa&&pb)//将pa、pb结点按大小依次插入C中{if(pa-data=pb-data){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;)。双向链表在非线性结构（如树结构）中将大量使用。priordatanext这种有两个指针的链表称为双向链表。其特点是可以双向查找表中结点。参见教材P35—39。特别：带头结点的空双向链表样式：/\链表的运算效率分析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)。