数据结构-基于C++语言（微课版） 课件 2-4 线性结构-链表所有

线性结构—线性表顺序存储结构以及算法实现链式存储结构以及算法实现线性表的两类存储结构链式存储结构及算法实现1、链式存储结构的基本原理2、链式存储结构的实现方法3、链表中结点间关系的基本操作实现

线性结构—线性表4、链式存储结构上线性表算法的实现链式存储结构定义结点的构成链式存储结构及实现链表的组成本节目录：本节内容：链式存储结构的实现原理缺点：在插入、删除某一元素时，需要批量移动元素；链表优点：可以随机存取任一位置的元素（不需要遍历）；存储密度大（结点本身所占存储量）；浪费存储空间；属于静态存储形式，数据元素的个数不能自由扩充；链式存储结构及实现链式存储结构及实现定义：把逻辑上相邻的数据元素存储在物理上不相邻的存储单元中的存储结构。例

三国演义中人物构成的线性表，链式存储结构如下：1刘备2张飞3关羽4曹操5吕布链式存储200600300250张飞200关羽600吕布250曹操300结点：刘备结点地址

500结点由两个域组成：数据指针数据域：存储元素数值数据。指针域：存储直接后继结点的存储位置。链式存储结构及实现链式存储结构结点的构成：200600300张飞200关羽600结点：刘备地址500链式存储结构及实现例a01024a1200…..an-1

链表L线性表L={a0,a1,…ai-1，ai,ai＋1

，…,an-1}^说明结点间逻辑关系的表示，通过指针阈来表示。

结点存储单元离散地分布在内存中的任意位置上的。结点ai中存放ai+1的地址。a0a1a2…an

L^1、头指针：链表中第一个结点的指针。头指针头结点首结点链式存储结构及实现2、头结点：链表中附设的一个结点；数据域内只放空表标志(表长、频率）等信息。3、首结点：链表中存储第一个数据元素a1的结点链表小结：链式存储结构及实现链式存储结构的意义；结点的构成，由两个阈构成，每个阈的作用；链表的组成；本节内容：链式存储结构的实现原理链式存储结构及算法实现1、链式存储结构的基本原理2、链式存储结构的实现方法3、链表中结点间关系的基本操作实现02线性结构—线性表4、链式存储结构上线性表算法的实现链式存储结构及实现本节目录：本节内容：链式存储结构的实现方法结点的类型声明结点的定义结点的访问结点的类型声明typedef

structNode{intdata;

structNode*next;

}

*LinkList；datanext结点结构链式存储结构及实现结点的定义Node*p结点是通过动态分配和释放来实现的，需要时分配，不需要时释放。结点的访问1、结点是动态分配和释放的，即需要时分配，不需要时释放。2、C++提供函数new

和delete实现。链式存储结构及实现Node*p/*定义结点p*/p=new

Node;/*动态申请一个结点的存储空间*/p->data=100;/*结中数据置为100*/p->next=NULL;100^练习线性表L={10,20,30}，分别用三个结点进行存储；链式存储结构及实现typedef

structNode{

intdata;

structNode*next;

}

*LinkList；/*定义三个结点*/Node*p1，*p2，*p3；/*实现三个结点*/p1=newNode;p1->data=10;

p2=newNode;p2->data=20;

p3=newNode;p3->data=30;

存在的问题:1、结点的重复定义2、没有实现线性表存储102030^p1p2p3小练线性表L={10,20,30}，构造三个结点的链表。链式存储结构及实现typedef

structNode{

intdata;

structNode*next;

}

*LinkList；/*定义三个结点存储线性表数据*/Node*p1,*p2,*p3；/*定义一个头结点*/Node*head,head=newNode;

/*实现三个结点*/p1=newNode;

p1->data=10;

p2=newNode;p2->data=20;

p3=newNode;p3->data=30;//将三个结点构成一个链表head->next=p1;

p1->next=p2;p2->next=p3;p3->next=NULL;结果102030head小结：链式存储结构及实现结点的类型说明；结点的定义、存储空间申请；结点数据的访问；本节内容：链式存储结构的实现方法练习如有线性表L={10,20,30}，分别用三个结点进行存储；建立链表并访问链表输出三数的和。102030^L链式存储结构及实现说明：存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。a0200a4300a1700a3400a2300地址：

500400200300700结点：datanextp链式存储结构及实现链式存储结构及算法实现1、链式存储结构的基本原理2、链式存储结构的实现方法3、链表中结点间关系的操作实现02线性结构—线性表4、链式存储结构上线性表算法的实现链式存储结构及实现本节目录：本节内容：链表中结点间关系的操作实现相同结点、后继结点的指向；增加后继结点；删除后继结点；q指向p结点;q指向p的后继结点；链式存储结构及实现a200ab…………pqqp链表中结点间的关系操作：…………代码:q=p;代码:

q=p->next;p指向下一个结点；链式存储结构及实现链表上结点间的关系操作：ab…………p说明：无论指向后继结点、还是同一个结点，都不会改变链表中总的结点个数。代码:

p=p->next；

删除p的后继结点；链式存储结构及实现链表上结点间的关系：ab……spc代码：s=p->next;p->next=s->next;

deletes;……新结点s插入到p结点的尾部；链式存储结构及实现链表上结点间的关系：ab……p代码：s->next=p->next;p->next=s;……Sc交换两句代码，结果如何？小结：链式存储结构及实现结点的指向关系；后继结点的删除和增加；本节内容：链表中结点间关系的操作实现链式存储结构及算法实现1、链式存储结构的基本原理2、链式存储结构的实现方法3、链表中结点间关系的操作实现02线性结构—线性表4、链式存储结构上线性表算法的实现1、线性表初始化：InitList(ListL)；6、删除操作：DeleteList(ListL,inti)5、插入操作：InsertList(ListL,inti,intx)3、取值：intGetList(ListL,inti)；2、求线性表的长度：intLengthList(List);4、查找：LocateList(ListL,intx)；线性表基本操作链式存储结构及实现链式存储结构及实现本节目录：本节内容：链式存储结构上线性表算法的实现建立链表—首部插入结点法建立链表的基本步骤算法实现LinkListInitLinkList(){

LinkListL;

L=newLinkList;

L->next=NULL;/*返回链表*/

returnL;}链表的初始化（构造一个空的链表）L^算法实现创建一个头结点链式存储结构及实现首部插入结点建立链表L^例线性表L={10、20、30、40}，建立链表。首部建立链表过程：L10^L10^2030L10^20L10^203040链式存储结构及实现首部插入结点建立链表建立链表主要操作L10^20304050链表p创建结点p;结点p插入到首部主要代码

p=new

Node;p->data=x;p->next=L->next;L->next=p;^链式存储结构及实现首部插入结点建立链表链式存储结构及实现LinkListCreateLinkListF(LinkListL,intarr[],intlength){

LinkListp,s;

s=L;

for(inti=0;i<length;i++)

{

p=newNode;

p->data=arr[i];

p->next=s->next;

s->next=p;

}

returnL;}时间复杂度o(n)小结：链式存储结构及实现首部插入结点的步骤；方法实现；时间复杂度；本节内容：链式存储结构上线性表算法的实现链式存储结构及实现本节目录：本节内容：链式存储结构上线性表算法的实现建立链表—尾部插入结点法基本步骤算法实现尾部插入结点建立链表例线性表L={10、20、30、40}，建立链表。过程演示L10^rearL20^10rearL30^2010rearL40^302010rearL^rear尾结点：所有操作在尾结点上完成链式存储结构及实现尾部插入结点建立链表建立链表主要操作创建结点p;结点p插入到尾部L1020...40链表50^prear^链式存储结构及实现主要代码p=new

Node;p->data=x;rear->next=p;rear=p;

rear-next=NULLLinkListCreateLinkListR(LinkListL,intarr[],intlength){

LinkListp,s;

rear=L;

for(inti=0;i<length;i++)

{

p=newNode;

p->data=arr[i];

rear->next=p;

rear=p;

}

rear->next=NULL;

returnL;}尾部建立链表算法实现链式存储结构及实现小结：链式存储结构及实现尾部插入结点的原理；方法实现；时间复杂度；本节内容：链式存储结构上线性表算法的实现链式存储结构及实现本节目录：本节内容：链式存储结构上线性表算法的实现求链表的长度基本步骤算法实现主要操作设立一个指针p，用来移动，从头到尾指向各个结点。一个计数器num，每指向一个结点，累加器+1。主要代码p=p->next；num++;求链表的长度L1020...40链表p^链式存储结构及实现链式存储结构及实现intLengthLinkList(LinkListL){

Node*p=L;/*p指向头结点*/

intj=0;

while(p->next)

{

p=p->next;

j++;

}/*p所指的是第j个结点*/

returnj;}求链表的长度的算法实现小结：链式存储结构及实现尾部插入结点的原理；方法实现，循环遍历链表本节内容：链式存储结构上线性表算法的实现L1020...40链表p^链式存储结构及实现本节目录：本节内容：链式存储结构上线性表算法的实现查找链表中指定的结点基本步骤算法实现查找第i个结点主要操作L20...40链表在指定范围内遍历链表，指针p移动，n=i？n=i查找成功，返回结点，否则返回NULL。主要代码p=p->next；n++;p链式存储结构及实现第i个结点…65^说明：在求链表长度的基础上，限制遍历到第i个结点即可。链式存储结构及实现Node*LocateLinkList(LinkListL,inti){/*在单链表L中查找第i个元素结点，找到返回其指针，否则返回空*/

Node*p=L;

intj=0;

while(p->next!=NULL&&j<i){

p=p->next;

j++;

}

if(j==i)

returnp;

else

returnNULL;

returnNULL;}查找第i个结点算法实现小结：链式存储结构及实现遍历链表；方法实现，查找的范围限制。本节内容：链式存储结构上线性表算法的实现L20...40链表p第i个结点…65^链式存储结构及实现本节目录：本节内容：链式存储结构上线性表算法的实现删除链表中指定的结点基本步骤算法实现删除第i个结点主要操作主要代码s=p->next；p->next=s-next;deletes;链式存储结构及实现L40...40链表…20前驱i-1个p说明：在查找的基础上，增加删除操作。查找到第i-1个结点p，如果没有前驱，则结束。删除p的后继结点。第i个intDeleteLinkList(LinkListL,inti){/*在单链表L中首先查找第i个结点，然后删除，返回0或-1*/LinkListp,s;

p=LocateLinkList1(L,i-1);/*查找第i-1个结点*/

if(p==NULL){

cout<<"第i-1个结点不存在";

return-1;

}elseif(p->next==NULL){

cout<<"第i个结点不存在";

return0;

}else{

s=p->next;/*s指向第i个结点*/

p->next=s->next;/*从链表中删除*/

delete(s);/*释放*s*/

return1;

}}删除第i个结点算法实现链式存储结构及实现小结：链式存储结构及实现删除结点的基本步骤；方法实现，首先查找结点，然后删除。本节内容：链式存储结构上线性表算法的实现L20...40链表p第i个结点…65^链式存储结构及实现本节目录：本节内容：链式存储结构上线性表算法的实现链表上指定位置插入结点；基本步骤；算法实现。插入第i个