线性表的链式表示和实现44284.ppt
第2章 线性表2.1 线性表的逻辑结构 2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现2.4 一元多项式的表示和相加12.3 线性表的链式表示和实现2.3.1 链表的表示2.3.2 链表的实现2.3.3 一个带头结点的单链表类型2.3.4 其它形式的链表2(1)链式存储结构特点：其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。如何实现？通过指针指针来实现！让每个存储结点都包含两部分：数据域和指针域指针 数据 指针 数据 数据 指针 或样式：数据域：存储元素数值数据指针域：存储直接后继或者直接前驱的存储位置设计思想：牺牲空间效率换取时间效率设计思想：牺牲空间效率换取时间效率2.3.1 链表的表示3链表存放示意图如下：a1heada2/an 讨论1：每个存储结点都包含两部分：数据域和讨论2：在单链表中，除了首元结点外，任一结点的存储位置由 指示。其直接前驱结点的链域的值(2)与链式存储有关的术语：1）结点：数据元素的存储映像。由数据域和指针域两部分组成；2）链表：n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。只包含一个指针域的称为单链表或线性链表指针域43）头指针、头结点和首元结点的区别头指针头结点 首元结点a1heada2 infoan首元结点是指链表中存储线性表第一个数据元素a1的结点。头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。头指针是指向链表中第一个结点（或为头结点、或为首元结点）的指针；示意图如下：5讨论2：在链表中设置头结点有什么好处？讨论1：如何表示空表？因为任何元素结点都有前驱结点，而在做插入和删除操作时，都需修改其前驱结点的指针域，因此对首元结点可以统一处理。即简化插入和删除操作；表头指针是指向头结点的非空指针，因此空表和非空表的处理一样。无头结点时，当头指针的值为空时表示空表；头指针无头结点头指针 头结点有头结点有头结点时，当头结点的指针域为空时表示空表。头结点不计入头结点不计入链表长度！链表长度！6一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址 数据域 指针域1 LI 437 QIAN 1313 SUN 119 WANG NULL25 WU 3731 ZHAO 737 ZHENG 1943 ZHOU 25答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。7 ZHAOH31称：头指针H的值是31（3）举例例1：7 现有一个具有五个元素的线性表L=23，17，47，05，31，若它以链接方式存储在下列100119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下图所示。其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？Z Z47 47 Y Y 31 31 V V23 23 X X 17 17 U U 05 05100 100119 119104 104108 108 116 116 112 112116116NULL(0)NULL(0)100100108108112112答：X=Y=Z=,首址=末址=。例2：8讨论:链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？因每个结点至少有两个分量，且数据类型通常不一致，所以要采用结构数据类型。答：设每个结点用变量nodenode表示，其指针用pp表示，两个分量分别用datadata和*nextnext表示，这两个分量如何赋值？p*next*next data datanode node方式1：直接表示为 node.dataaa；node.next=q;q;方式2：p指向结点首地址 p-data=aa;p-next=qq;方式3：p指向结点首地址(*p).data=aa；(*p).nextq;q;9单链表的抽象数据类型描述如下（参见教材P28）：typedef struct LNode ElemType data;/数据域 struct LNode*next;/指针域LNode,*LinkList;/*LinkList为Lnode类型的指针Q1：第一行的LNode 与最后一行的LNode是不是一回事？A1：不是。前者LNode是结构名，后者LNode是对整个struct类型的一种“缩写”，是一种“新定义名”，它只是对现有类型名的补充，而不是取代。请注意：typedef不可能创造任何新的数据类型，而仅仅是在原有的数据类型中命名一个新名字，其目的是使你的程序更易阅读和移植。10Q2：那为何两处要同名(LNode和LNode）？太不严谨了吧？A2：同名是为了表述起来方便。因为描述的对象相同，方便阅读和理解。Q3：结构体中间的那个struct LNode是何意？A3：在“缩写”LNode还没出现之前，只能用原始的struct LNode来进行变量说明。此处说明了指针分量的数据类型是struct LNode。返 回1 12.3.2 链表的实现（1）单链表的存取（2）单链表的插入（3）单链表的删除（4）单链表的建立12（1）单链表的存取思路：要存取第i个数据元素，必须从头指针起一直找到该结点的指针p，然后才能执行 p-data=new_value。修改第i个数据元素的操作函数可写为：Status GetElem_L(LinkList L,int i,ElemType e)p=L-next;j=1;/带头结点的链表while(p&jnext;+j;if(!p|ji)return ERROR;/i不合法 p-data=e;/若是读取则为：e=p-data;return OK;/GetElem_L缺点：想寻找单链表中第i个元素，只能从头指针开始逐一查询（顺藤摸瓜），无法随机存取。13在链表中第i个位置前插入一个元素x 的示意图如下：Xsai-1aip链表插入的核心语句：Step 1Step 1：s-next=p-next;s-next=p-next;p-nexts-next思考：思考：Step1Step1和和22能互换么？能互换么？X 结点的生成方式：s=(Lnode*)malloc(m);s-data=x;s-next=?aiai-1p插 插 入 入 X（2）单链表的插入Step2:p-next=s;Step2:p-next=s;14 Status ListInsert_L(LinkList L,int i,ElemType e)/LinstInsert_L算法的时间复杂度为:O(ListLength(L)p=L;j=0;while(p&j next;+j;/寻找第 i-1 个结点if(!p|j i-1)return ERROR;/i不合法 s=(LinkList)malloc(sizeof(LNode)s-data=e;s-next=p-next;p-next=s;/插入return OK;15在链表中删除某元素ai的示意图如下：ai+1 ai-1 aip删除动作的核心语句（要借助辅助指针变量q）：q=p-next;/首先保存ai的指针，靠它才能找到ai+1 p-next(p-next)-nextq（3）单链表的删除P-next=q-next；/将ai-1与ai+1两结点相连,淘汰ai结点free(q);16 Status ListDelete_L(LinkList L,int i,ElemType&e)/删除以 L 为头指针(带头结点)的单链表中第 i 个结点/ListDelete_L算法的时间复杂度为:O(ListLength(L)p=L;j=0;while(p-next&j next;+j;/寻找第 i 个结点，并令 p 指向其前趋if(!(p-next)|j i-1)return ERROR;/删除位置不合理q=p-next;p-next=q-next;/删除并释放结点 e=q-data;free(q);return OK;17空间效率分析链表中每个结点都要增加一个指针空间，相当于总共增加了n 个整型变量，空间复杂度为 O(n)。在n个结点的单链表中要删除已知结点*P，需找到它的，其时间复杂度。前驱结点的地址前驱结点的地址/指针指针 O(n)练习：18操作步骤：一、建立一个“空表”；二、输入数据元素an，建立结点并插入；三、输入数据元素an-1，建立结点并插入表头；ananan-1四、依次类推，直至输入a1为止。（4）单链表的建立例如：逆位序输入 n 个数据元素的值，建立带头结点的单链表。链表是一个动态的结构，它不需要预先分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。19void CreateList_L(LinkList&L,int n)/逆序输入 n 个数据元素，建立带头结点的单链表/CreateList_L算法的时间复杂度为:O(Listlength(L)L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/先建立一个带头结点的单链表for(i=n;i 0;-i)p=(LinkList)malloc(sizeof(LNode);scanf(&p-data);/输入元素值 p-next=L-next;L-next=p;/插入20算法要求：已知：线性表 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）例：两个链表的归并（教材P31例）算法设计：算法主要包括搜索、比较、插入三个操作：搜索：需要设立三个指针来指向La、Lb和Lc链表；21La3 5 8 11 Lb2 6 8 11 9 PaPbPaPbPa、Pb用于搜索La和Lb，Pc指向新链表当前结点。归并过程示意如下：Lc=LaPbPa PaPb比较：比较La和Lb表中结点数据的大小；插入：将La和Lb表中数据较小的结点插入新链表Lc。请注意链表的特点，仅改变指针便可实现数据的移动,即“数据不动，指针动”22 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结点按大小依次插入Lc中 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；/有头结点注：注：LcLc用的是用的是LaLa的头指针的头指针思考：重复的数据元素不需要插入，怎么修改？23用上述定义的单链表实现线性表的操作时，存在的问题：改进链表的设置：1单链表的表长是一个隐含的值；1.增加“表长”、“表尾指针”和“当前位置的指针”三个数据域；2.将基本操作中的“位序 i”改变为“指针 p”。2在单链表的最后一个元素之后插入元素时，需遍历整个链表；3在链表中，元素的“位序”概念淡化，结点的“位置”概念加强。返 回24typedef struct LNode/结点类型 Elemtype data;struct LNode*next;*Link,*Positiontypedef struct/链表类型 Link head,tail;/分别指向链表头尾结点 int len;/链表中元素个数（长度）Linklist;2.3.3 一个带头结点的线性链表类型定义如下：（用类C语言，见P37）：结点的结构表结构基本操作（略）返 回25单链表中查找只能从前往后，而不能从后往前查。为了查找方便，提高查找速度，可以在结点上增加一个指针域，用来存结点的直接前驱，这样的链表称为双向链表。其结点的结构为：prior data nexttypedef struct DuLNode ElemType data;/数据域 struct DuLNode*prior;/前驱指针域 struct DuLNode*next;/后继指针域 DuLNode,*DuLinkList;双向链表类型的定义如下：2.3.4 其它形式的链表 1.双向链表26 最后一个结点的指针域的指针又指回第一个结点的链表。从表中任一结点出发均可找到表中其它结点 a1 a2.an 2.循环链表 和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”即p-next?=headhead273.双向循环链表空表非空表 a1 a2.anhead-prior=head-next=headhead28插入操作：设p已指向第 i 元素，请在第 i 元素前插入元素x ai-1的后继从 ai(指针是p)变为 x（指针是s):s-next=p;p-prior-next=s;ai 的前驱从 ai-1(指针是p-prior)变为 x(指针是s);s-prior=p-prior;p-prior=s;注意：要修改双向指针！x sai-1 ai p指针域的变化：29指针域的变化：ai-1的后继由 ai 变为 ai+1(指针 p-next);p-prior-next=p-next;ai+1 的前驱由 ai 变为ai-1(指针 p-prior);p-next-prior=p-prior;ai-1 ai+1 ai p删除操作：设p指向第i个元素,删除第i个元素注意：要修改双向指针！30动态链表样式：静态链表样式：指针 数据指针 数据指针 数据指示 数据指示 数据指示 数据指示 数据指示 数据数组中每个元素都至少有两个分量，属于结构型数组。常用于无指针类型的高级语言中。用一片连续空间（一维数组）实现链式存储，这种方式称为静态链表。具体实现方法：定义一个结构型数组（每个元素都含有数据域和指示域），就可以完全描述链表，指示域就相当于动态链表中的指针,指示结点在数组中的相对位置。4.静态链表31 静态单链表的类型定义如下：#define MAXSIZE 1000/预分配链表的最大长度 typedef struct ElemType data;/数据域 int cur;/指示域 component,SLinkListMAXSIZE;/这是一维结构型数组前例1：一线性表 S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)，用静态链表如何表示？说明1：假设S为SLinkList型变量，则SMAXSIZE 为一个静态链表；S0.cur则表示第1个结点在数组中的位置。32说明2：如果数组的第i个分量表示链表的第k个结点，则：Si.data表示第k个结点的数据；Si.cur 表示第k+1个结点(即k的直接后继)的位置。data1ZHAO3LI5QIAN6WU0ZHOU4SUN2 0 01 12 23 34 45 56 6 1000 1000curi头结点 头结点说明3：静态链表的插入与删除操作与普通链表一样，不需要移动元素，只需修改指示器就可以了。例如：在线性表 S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)的QIAN,SUN之间插入新元素插入新元素LIU，可以这样实现：33Step1:将QIAN的指示器原内容备份到临时变量temp：temp=S3.cur；Step2:将QIAN的指示器换为新元素LIU的位置：S3.cur=S3.cur=77；Step3:将LIU的指示器变为后继SUN的位置：SS77.cur=temp.cur=temp；data 2SUN4ZHOU0WU6QIAN5LI3ZHAO10 01 12 23 34 45 56 61000 1000cur i头结点 头结点LIU LIU 6 67 77 734本节小结1.线性结构(包括表、栈、队、数组）的定义和特点：仅一个首、尾结点，其余元素仅一个直接前驱和一个 直接后继。2.线性表逻辑结构：“一对一”存储结构：顺序、链式运 算：修改、插入、删除3.顺序存储特征：逻辑上相邻，物理上也相邻；优点：随机查找修改快 O(1)缺点：插入、删除慢 O(n)改进方案：链表存储结构 链表存储结构35循环链表的特点：从任一结点出发均可找到表中其他结点双向链表的特点：可方便找到任一结点的前驱静态链表的特点：不用指针也能实现链式存储和运算4.链式存储特征：逻辑上相邻，物理上未必相邻；优点：插入、删除快 O(1)缺点：随机查找修改慢 O(n)5.几种特殊链表的特点：36讨论：顺序存储和链式存储的区别和优缺点？顺序存储时，逻辑上相邻的数据元素，其物理存放地址也相邻。顺序存储的优点是存储密度大，存储空间利用率高且能随机存取；缺点是插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小，存储空间利用率低，且只能顺序存取。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。37
