数据结构课件代码第2章线性表2713.ppt

《数据结构课件代码第2章线性表2713.ppt》由会员分享，可在线阅读，更多相关《数据结构课件代码第2章线性表2713.ppt（71页珍藏版）》请在三一办公上搜索。

1、第2章 线性表(二),张成文北京邮电大学计算机学院,桔隙浸钎闯鳖辉迪省藕诅嘛灭鲤馒睛挑峡遁央拿烤尖柔胸瓣址皆耳托晴遣数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,主要内容,2.7 线性表的链式存储结构表示2.8 单链表2.9 循环链表2.10 双向链表2.11各种链式存储结构的比较2.12顺序表与链表的比较 2.13小结,胸激翟各稼宜贬果幻摧碉婪圾壹辩鸡二含辉缘眯茬京孕折河变厅定蔚索又数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,线性表的链式存储结构表示,结点(Node):既要存储线性表的每个数据元素值,又

2、要存储指示其后继结点的地址(或位置)信息,以表示结点间的逻辑关系。这两部分信息组成的存储映象叫做结点(Node)。,茧护阔舒麦递相也懊救瞄八患执镶胖任磷畜愁昭朝僻肺刚缚仆秤物维锻砧数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,1 线性表的链式存储结构表示,让每个存储结点都包含两部分：数据域和指针域,数据域：存储元素的值,指针域：存储直接后继或直接前驱元素的存储地址,设计思想：牺牲空间效率换取时间效率,栗惨羹洋哇驱公膳卿节毙湿劣防酒畸贰诬显犬拼腑助也溪老穆啮国翅涎目数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3

3、,其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。,如何实现？,通过指针来实现！,链式存储结构特点,a1,a2,a3,裔傀综厘嚎懈状喧卵镁蚌晒背缮橱寅垒旺捷括旅椎炕杭龄蒂邓蛮杯蛛包衫数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,与链式存储有关的术语,1）结点：数据元素的存储映像。由数据域和指针域两部分组成；2）链表：n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。3）单链表、双向链表、循环链表：结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域（直接前驱和直接后继）的链表，称为双

4、向链表；首尾相接的链表称为循环链表。,循环链表示意图：,head,买蚜抿蕊城演郧诣绽茁细邀峨源塑蚕娃窝瘤姓淳腻蕊避撼厌赘频濒丰智邓数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,4）头指针、头结点和首元结点的区别,示意图如下：,头指针,头结点,首元结点,头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。首元结点是指链表中存储线性表第一个数据元素a1的结点。,下面举例说明。,阶敖菇凯阂曼蓑哟刺椎玫爱栗悬迭释强玄掺滚阀堡蔼仰钟扳裸含企恿们凹数据结构课件

5、、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,头指针L,头指针L,头结点,首元结点,首元结点,空表：L=NULL,L,1264,1264,4016,4016,头结点的作用：插入和删除第一个数据元素时不必对头指针进行特殊处理。,与链式存储有关的术语,砷百郝脑帖椰寸鸦利航某塑辜玖撼吊胞叫轰诺真结罢五诺负川渴才钧鞍貉数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？,例1：,答：

6、头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。,31,称：头指针H的值是31,阎秽酞痢迹赛更漫苍磅个秆咳捞球报年躺徐干丽渴扁悟装笨锨恩疥唤他郎数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,例2：线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L=23，17，47，05，31，若它以链接方式存储在下列100119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下图所示。,其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？,100,119,答：

7、X=Y=Z=,首址=末址=.,104,108,116,112,116,NULL/0,100,108,112,仔律海饭阶镁抨冕试氯秀吉汝常啮褪铭孪箍屈诅按择空毁僧宁然孤形寨腿数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,单链表,单链表:链表中的每个结点只有一个指针域,我们将这种链表称为单链表。单链表包括两个域:数据域用来存储结点的值;指针域用来存储数据元素的直接后继的地址(或位置)。,荡坦踞拢邢色啥嘉后釉赂斌鸽西司银菠涨伴湾杆津燃厌找咨炙卖讹敝杂叫数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,从链表的整体结构

8、上看，链表可以是空链，也可以由一个或多个结点组成。每条链有一个入口的头结点，该结点仅指示链中第一个结点的地址。如是空链，则可表示为“0”或“”，它类似于一个常量。每条链的最后一个结点的链指针为“0”，也可用“”作为链的结束标志。下图给出了链表的示意形式。图(a)中有一个头结点和具有A、B、C、D数据元素的链，图(b)所示为线性链表的一般表示，结点与结点之间用箭头链接。,单链表,隐棵掺洞俯采饵到蝉柏贮绑册辣遵狸茬丁掏咬宽媚暑仲唾毁咳紧紫济慢附数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,链表图示(a)链表的图示；(b)链表的一般表示,巢洞木捣矣蕊愚沮吐

9、饲汾圾芳谆郭狼帝贿垛懦围枝蠕豹类冒靖老远岸斤傍数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。,头结点,头指针,头指针,有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。,空指针,线性表为空表时，头结点的指针域为空,隐辞晤剑惰乌喇烹逛斌灾惩欧洞永歌铣戮谴正湖却骆担历候蹄换暂已虱达数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,讨论:链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？,因每个

10、结点至少有两个分量，且数据类型通常不一致，所以要采用结构数据类型。,答：,以26个字母的链表为例，每个结点都有两个分量：,假设每个结点用变量node表示，结点指针用p表示，其中两个分量分别用data和*next表示，该如何书写？,方式1：直接表示为 node.dataa；node.next=q方式2：p指向结点首地址，然后 p-data=a;p-next=q;方式3：p指向结点首地址，然后(*p).data=a；(*p).nextq,薛凶烬吕窒沥酞疯恳枉嘿招奖后默鳖弊抉表咕稻发浦骗鼎城理抖淳汞椭扬数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,单链表的

11、存储结构描述,typedef struct Node/结点类型定义 ElemType data；struct Node*next；Node,*LinkList；/LinkList为结构指针类型,掐写说福夕肾蒸阻抄销怖波员励角棘雨赏曾匠头厕趁舰骚烙奖味真谎谢四数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,设p为指向链表的第i个元素的指针,则第i个元素的数据域写为，指针域写为。,练习：,p-data,ai的值,p-next,ai+1的地址,链表不具备的特点是。A、可随机访问任何一个元素 B、插入、删除操作不需要移动元素 C、无需事先估计存储空间大小 D、

12、所需存储空间与线性表长度成正比,沦撰屠套蝗销厉臻乾趟避蓝镰弯迁侵寐弃撬里叫逮背谐咎瀑夷蓄疯素渠壮数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,静态链表 用数组模拟可利用空间表,0 1 2 3 4 5 6 7 8 9 3 8 1-1 6 cur(游标)a2 a1 a4 a3 data,#define MAXSIZE 10/链表的最大长度typedef struct ElemType data;int cur;componet,SLinkListMAXSIZE;,第1个元素的下标：SLinkList0.cur,宣串晾扳沥娟尧冗袍啸煮矽企馏街搁骂姚纶即敢雪

13、腾铅毋聊镜霹钒窃援抉数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,带头结点的单链表上的基本运算,1 建立单链表2 单链表查找3 单链表插入4 单链表删除第i个结点,托卑挂影县革呵罢雅缓祖镶叭疟深刻赔宰奖犀陡顽著钟湾巳灼葵汤殿奏披数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,建立单链表,1)头插法建表（逆序）,操作步骤：,建立一个“空表”；,输入数据元素an，建立结点并插入；,输入数据元素an-1，建立结点并插入；,an,an-1,依次类推，直至输入a1为止。,风恢蒙高劝虫保桐漫瘤迭芦贱摇胞堤剃频善苯蘑蓄捷这

14、圈峻黑卸徊河拼赊数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,头插法建表算法,Linklist CreateFromHead()LinkList L;Node*s;int flag=1;/标志flag初值为1 L=(Linklist)malloc(sizeof(Node);/分配头结点 L-next=NULL;while(flag)/输入“$”时,flag置0,建表结束 c=getchar();if(c!=$)/为新结点分配存储空间 s=(Node*)malloc(sizeof(Node);s-data=c;s-next=L-next;L-next=

15、s;/链接 else flag=0;return L；,避案卵楼汁凯遁限悲利黔帆掷账敌徒刊镶舌俯染碑羔草抠娜朽馋脉划恰允数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,2)尾插法建表：设尾指针r建立一个“空表”,r 指向头结点;输入数据元素C1,建立结点并链接,r指向该结点；输入数据元素C2,建立结点并链接,r指向该结点；输入数据元素Cn,建立结点并链接,r指向该结点；,咯微药甭站净偿院患灿捉拟瞅逛鲸呢蕾同栅暇漂梦缄亚埃壹帜篓铅札丫醉数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,尾插法建表算法,Linklis

16、t CreateFromTail()/新结点加到链表末尾 LinkList L;Node*r,*s;int flag=1;/flag初值 L=(Node*)malloc(sizeof(Node);/分配头结点 L-next=NULL;r=L;/r始终指向链表的表尾 while(flag)/输入“$”时flag为0，建表结束 c=getchar();if(c!=$)s=(Node*)malloc(sizeof(Node);s-data=c;r-next=s;r=s/链接 else flag=0;r-next=NULL;return L；,需游缄椒面诛癣烤憋塘傅桑颠朋挫鹿钝嗽粤吹僳系磊怪授铡擒勺雕

17、杰禾滇数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,单链表查找,1)按序号查找 算法描述：设带头结点的单链表的长度为n,要查找表中第i个结点,则需要从单链表的头指针L出发,从头结点（L-next）开始顺着链域扫描,用指针p指向当前扫描到的结点,初值指向头结点(p=L),用j做记数器,累计当前扫描过的结点数(初值为0),当j=i 时,指针p所指的结点就是要找的第i个结点。算法实现,算法演示。,烩实斤泪拖守辽纫龙感宜视肢昆巴侄锚珍闸癸腹华枝碘红讣痕杨杯旱缆使数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,线性表的

18、操作 Get(L,i)在单链表中i=3时,Get的实现过程:,j,1,2,3,P-data=30,派忱皿侨堂毁分砌皱洗亨煮韩祟危鲤洽圃猪该戈囚级商屏横铺醉碌才疯梳数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i。,令指针 p 始终指向线性表中第 j 个数据元素。,单链表是一种顺序存取的结构,为找第 i 个数据元素,必须先找到第 i-1个数据元素。,账鞍注债纳姿畅扭露喝捂滑颁宠雾诽吊镇肝略垃董卵蚊盛整姆沾鄂祷詹裤数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表

19、2-71-3,按序号查找算法实现,/找第i个结点,找到返回指向它的指针;否则返回空Node*Get(LinkList L,int i)Node*p；p=L；j=0；/从头结点开始扫描 while(p-next!=NULL)&(jnext；j+；/扫描下一结点 if（i=j）return p；/找到了第i个结点 else return NULL；/找不到,i0或in,算法时间复杂度为:,O(Length(*L),阂匠掂腰毋拜飘尚珍虫拥瞩皱司讲鹊吞愈蹲庚氟胳富桑管酱侈肖撬谷紫勺数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,2)按值查找算法描述：按值查找是

20、指在单链表中查找是否有结点值等于e的结点，若有的话，则返回首次找到的其值为e的结点的存储位置，否则返回NULL。查找过程从单链表的头指针指向的头结点出发，顺着链逐个将结点的值和给定值e作比较。算法实现，算法演示。,畴元衡矫墨霹爱枢赤蹭仪胆署俱眷斑价倘坑卧稽听打吧显骄瞒锑曙寥捷般数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,按值查找算法实现,/查找其结点值等于key的结点，若找到则返回该结点的位置p，否则返回NULL*/Node*Locate(LinkList L,ElemType key)Node*p;p=L-next;/从表中第一个结点比较 whi

21、le(p!=NULL)if(p-data!=key)p=p-next;else break;/找到结点key，退出循环 return p;,算法时间复杂度为:,O(Length(*L),大膳粮加匝馏摊株样侦箩钙婴斡沉篙筑叶管仔闺岿灭中疫悄痰谷识闷描林数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,3.单链表插入操作 InsList(L,i,e)的实现：,有序对 改变为 和,可见,插入结点需要修改第 i-1 个结点的指针和新结点的指针。,在单链表第i个结点之前插入结点的步骤为:,1)找到单链表的第i-1个结点并由指针pre指示。,2)然后申请一个新结点并

22、由指针s指示。,3)将pre指示结点的指针值赋给s指示结点的指针域。(将第i个结点链接到新结点上),4)然后修改pre指示结点的指针域,使它等于s。(新结点链接到第i-1个结点上),单链表插入,魂浙荤懦制凄缓驭哺松勿真嗡脾蒂蔽筋抒愿公灯辆收灯忌挤常惺页诛芬猜数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,int InsList(LinkList L,int i,ElemType e)/在单链表L第i个结点前插入值为e的新结点 Node*pre,*s;pre=L;int k=0;/先找到第i-1个结点的存储位置,让Pre指向它 while(pre!=NU

23、LL,算法时间复杂度为:,O(Length(*L),晶教却淀罢悸磊渤及算浑谰按唁计召涧仲灌汐恍秆烫备寸模牙痴盛缕救嫩数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,s=(Node*)malloc(sizeof(Node);/申请新结点 s-data=e;/将e赋给s的数据域 s-next=pre-next;pre-next=s;/链接,赦傲释州孔篱囚怯焚仍吁巍啄盏改悟渍樱箩禽像矢越祖丽歌悬玩政礁喷窿数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,如下图所示的是链表插入前、后的逻辑状态。从图中可以看出，要插入一个

24、结点，首先要从空间表中取一个空结点k，使得q结点（前趋结点的地址）的指针指向k，k结点的指针指向p（存储ai值的结点地址），同时把数据x存入k，即q-next=k;k-next=p;,撕咳檄侵冰府密付皖疗褥寇阑安段绕遣四劣匈颁剖赋烂绩奢彭梭渔把辞勒数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,链表插入逻辑示意图(a)插入前；(b)插入后,巾沤震喜梆旷国来愚萤邀谊庙勉偶沦肌雌湿了凰赦狸声茧赏木膛骤鞋鲸叔数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,在链表的插入操作中，结点插入的位置可能有四种情况，下面分别加以

25、介绍。设Head是链表入口或表头，x是插入结点的存储地址。(1)原来链表为空表，即Head=NULL，则插入结点为表首结点，表示为Head=x；x-next=NULL；(2)插入位置在表中第一个结点Head之前，则插入结点为新的表头，表示为x-next=Head；Head=x；,歉冶毒辫灸乏酮汕庇婿驼订增翌殿绩砸壳排递丈拎滑疽陕吕融庭抽汉链捎数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,(3)插入位置在表的中间，为q结点之后，p结点之前，表示为q-next=x；x-next=p；(4)插入位置在链尾，即新结点x作为原表尾结点p之后的新表尾，表示为x-

26、next=p-next；p-next=x；或 p-next=x；x-next=NULL；,搏档谭逸堪纸次须帕烽军戮辛介刁锋硝缺篆星庙炙嗜肇滞酮膀丢身缆元男数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,单链表删除第i个结点操作为:找到线性表中第i-1个结点*p,修改其指针域让它指向第i+1个结点。释放第i个结点的空间。,r=p-next;p-next=r-next;free(r);,p,r,姓淆自诚胞危寡翅腊辖丁雹耶程嚼搐赁撩摹橡彦婉搞们赞涯宅杨蔫瘩泌哆数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,int D

27、elList(LinkList L,int i,ElemType*e)/删除单链表L中第i个元素,并保存其值到变量*e中 Node*p,*r;p=L;int k=0;while(p-next!=NULL,算法的时间复杂度为:,O(Length(*L),唁秦冲镀窥律翰挟枢凄面辰匈诣峪镜屁跋歹急檬座是瓶贮缝餐东燃蜗仪奶数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,链表删除的逻辑示意图(a)删除前；(b)删除后,倦欠眩齐股掀蒋俱吩垮省猖讳留唤创硝价放臣癸供木察开侦锁裁藤窄沁镊数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-7

28、1-3,从上图中可以看出，要删除某一个结点，必须知道被删除结点的前趋结点。设被删除结点的地址为s，s的前趋结点为q，s的后继结点为p，则被删除的基本操作步骤为q-next=p；或q-next=s-next；,截壬焰撵漏妙吸谬受貌窘鸟邀再聋讨娇硒疼综钱节练如贷满毒疲茬求痒拘数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,删除操作和插入操作相同，即在链表中搜索到被删除的结点，修改相应的指针，同时把被删除的结点通过调用free(x)，将该结点的空间送空间表。根据被删除结点在链表中的位置，删除操作有如下四种情况：(1)链表中只有一个结点，该结点就是被删除的结点

29、，其操作为Head=NULL；或 Head=Head-next；(2)被删除的结点是链中第一个结点，其操作为 Head=Head-next；,值牡盂衅抨徽阿誓梨限订跳绦疟退呐皇蒙糟塘丝品勤驰钉寨简掘弥妹耻狮数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,(3)被删除的结点在链的中间，其中删除结点的地址为p，前趋结点的地址为q，其操作为q-next=p-next；(4)被删除的结点在链尾，其中删除结点的地址为p，前趋结点的地址为q，其操作为q-next=NULL；或 q-next=p-next；下图给出了线性表删除算法的框图。,货鹤哦裸彼钻盼精丽扳牧成弛

30、章噶亥饰轴拘厨嵌雕右舰概毡赛气酗螟华冕数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,线性链表删除算法框图,辐钉倪西穴椿付胖瑚碉卡玲预已隘赏褪墅窘脑嗓接一特击誓洲滑南次戏余数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,删除算法：DELETE(head，key)/*在head为入口的链表中删除值为key的结点*/i=head；w=i；/*设置前趋结点的地址*/while(i!=NULL)&(i-data!=key)w=i；i=i-next；/*查找删除结点的位置*/,螺砰谱耕镭仿汪演蓟釜酶抹涤埋发纹颠炒往颁题帜

31、馒口释缎半烦堤桑德掀数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,if(i=NULL)printf(无此结点)；return；else if(head=i)head=i-next；/*删除头结点*/else w-next=i-next；/*删除链中间和链尾结点*/free(i)；,徐抚雄悦盒离画却娥枫夜柯卖不箭橇灾妻叹肖齐剐科浴讶踊锭胖莉趋跑不数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,用上述定义的单链表实现线性表的操作时，存在的问题：,改进链表的设置：,1单链表的表长是一个隐含的值；,1增加表长、表尾指

32、针 和 当前位置指针；,2在单链表的最后一个元素之后插入元素时，需遍历整个链表；,3在链表中，元素的“位序”概念淡化，结点的“位置”概念加强。,2将基本操作中的“位序 i”改变为“指针 p”。,盔檬冈护曙榷嘱蕾警梦描浚捂寅豹修巷剐伟胖松祭炭舶浸尼馏佰盘侍死霸数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,3 循环链表,最后一个结点的指针域的指针又指回第一个结点（或头结点）的链表,和单链表的差别:判别链表中尾结点的条件不再是“后继指针是否为空”，而是“后继指针是否为头指针”。,赦辟霍梦弹舰员瑚炸庄角鬃匹喊桶朽达滚垢郡蚕茧此座片瑞疟抖淌备删锡数据结构课件、

33、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,带头结点的循环单链表示意图,豫愉躯蔑悲郸棒支爪瘤唇凤饼桂腆螟旺抢牟硫预哈瘴乓砸瘴樊囤窑素洼窗数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,通过查询，确定关键字值KEY不在链中，该结点插入的位置和插入的操作有如下几种情况：(1)若表空(Head=NULL)，则插入结点后是只有一个结点的环链表。(2)若表非空，则分为三种情况：插入的位置是在第一个结点，即原表的第一个结点成为结点插入后新表的第二个结点，同时为了保持循环链表的结构特征，在形成新的入口后，链表中最末一个结点的链指针应修

34、正指向新的入口结点。,循环链表的插入操作,睫驭樟蒜他答床毛补琴披跌盛缝腑挎涂撂坯捕流抵怖从征纺摊僚狞亏扼谜数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,插入的位置是在最末一个结点之后，那么，最末一个结点的指针指向插入的结点，插入结点的指针仍指向首结点。插入的位置是在链的中间，那么可通过插入位置的前趋结点的指针，完成新结点的插入。下图所示为四种插入操作的示意图。,泼搓停飘该钝兄依愚壹闸弊应种沫痴磷扳咐削睛读钻迄揣毕安日接脏楚颧数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,循环有序链表的插入操作示意图,悔贩瓢凑

35、淫蒸厌钎谩滤醋欧炙踞垃崖俩材衫窥滞扫规踢振阀虐帚铲滑腥垫数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,下图给出了循环链表删除关键字值为KEY的结点的算法框图。,循环链表的删除操作,池羚纱蜡尚密痔暗外椭臻谢戳尖补涤锦综畸卞粒沥柿钨咋揩手峡伟杉愉趁数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,循环链表删除算法框图,菌沪昧躁盛戴疥汝倾巍婴议侈迎芥彦乍抒便簇蒂吝麦座起滩知每骋诸码柳数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,必须注意，在循环链表中，要充分考虑到可能出现被

36、删除结点位置不同的各个边界条件。若被删除结点在链首，则必须修改入口Head，而且还要考虑到链表中最末一个记录的指针要指向结点删除后的新入口，该情况的操作示意图如下图所示；特殊情况下，被删除结点是第一个且仅只有这一个结点，那么循环链表入口因设置为空，Head=NULL；其他情况与单链表的删除结点的算法相似。,杜追歹腕前一浅嫉属俏陛晤橇纫徒盗笛忙渝虞达褥勾汪告蹲耕右劝书淮祷数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,循环链表删除首结点(a)删除结点之前；(b)删除结点之后,毖掸谈进傍境秉桥儒肌翟挡塞铃搏觉丝武侧符蓝苹氢幂苹墩袁迪岿羚汹阴数据结构课件、代

37、码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,例 有两个带头结点的循环单链表LA、LB，编写算法，将两个循环单链表合并为一个循环单链表，其头指针为LA。,算法思想：先找到两个链表的尾，并分别由指针p、q指向它们，然后将第一个链表的尾与第二个表的第一个结点链接起来，并修改第二个表的尾q，使它的链域指向第一个表的头结点。,实姬架烹勺拽渤杂零粘铡唾宵挛蔑岛乍姐肺购庄掩丢胚弹盯琐惯裸焕锭浑数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,LinkList merge_1(LinkList LA,LinkList LB)/*此算法将两个

38、循环单链表的首尾连接起来*/Node*p,*q;p=LA;q=LB;while(p-next!=LA)p=p-next;/找到LA的表尾 while(q-next!=LB)q=q-next;/找到LB的表尾 p-next=LB-next;/使LA尾指针指向LB第1个结点 q-next=LA;/使LB的尾指针指向表LA的头结点 free(LB);/释放LB的头结点空间 return(LA);,零叠页菌绵归董玲理玖爽洽堰雇隔傣姚端衷哮铣牛颂睦嘿粤贴淳惮洞拄呜数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,4 双向链表,typedef struct Node

39、/结点类型定义 ElemType data；struct Node*next；struct Node*prior;Node,*LinkList；/LinkList为结构指针类型,凭元铸腆叭莆窃侥饿纲祖拂振拣控遵六旅破净婴技扣套详堡睡汝待丢鼠蒙数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,双向链表的结构,仆娩阁鉴坡撒纂区渺蛾侦自泛棘股峨具太疯玲址霸亩脑窖骸篓骤明霹瞥态数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,双向链表的结构有以下特点：(1)若Head为空(NULL)，则双向链表为空。(2)在双向链表中，若

40、结点i有i-Lnext=NULL则该结点是链的第一个结点；若结点i有i-Lnext=i-Rnext=NULL 则该结点i是链的第一个结点且该链仅有这个结点i。(3)在双链表中，若结点i有i-Rnext=NULL则该结点是链的最末一个结点。,胳凭次弯咎锈兴产伍毋懂胶帖珊赶甸朋戒食硫嫌绳汗郑邑逢俐枝潞券阉尿数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,(4)在双向链表中，若结点i是表中任意结点的地址，则该结点的前趋结点是iLnext，后继结点的地址是iRnext，对结点i也可以表示为i=i-Rnext-Lnext=i-Lnext-Rnext这个表达式非常

41、直观地反映了双向链表结构的本质特点，即无论是沿着表向前，还是向后都同样方便。,饯恩忱徽仅咱寐笆摆儡剂驹约浩呛袄标识常沼价裂怖偏喊捣彬琵粟绊丑支数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,双向链表的操作特点：,“查询”和单链表相同。可增加一种从后向前的“查询”方式。,“插入”和“删除”时需要同时修改两个方向上的指针。,凛鞭滁需砒贴脉啪垫糙砒辜坚棺构取鹏焰千渺旨面吝即琉著畜友犁脚谭募数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,s-next=p-next;p-next=s;s-next-prior=s;s-p

42、rior=p;,s,插入,间恐搽艇垢筛廖肄茎灯会愤拙硷酮冲未冷虹缔歹苏馆缠余编超踪佩擎迈疆数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,删除,q=p-next;p-next=q-next;p-next-prior=p;free(q);,p,双向链表删除操作是否可不用工作指针q?,q,饿枚箔口晕黄佰亮浩乍城奢戈酚镀反圃靠讹诣磺乌奄慎挤莽趾茶伙奔逐列数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,删除,p-next=p-next-next;free(p-next-prior);p-next-prior=p;,p,

43、绩烟躬啡虐线桑汹倒锅元辜密部兄惺趾艰伪舜钵澎门倒叭碘妊浅延渍瘪塞数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,空表,非空表,he,he,双向循环链表,纠搪胎腰脾玉粕些碾计莲兴霜远釜冻轮怜碎劈票促慑汕腕掣拼鸥母粟篡瓮数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,单链表和循环单链表均只有一个链指针next，指向后继结点，而双向链表有两个指针，即向前指针Lnext和向后指针Rnext。单链表结构的查询只能从链表入口开始，按结点的链指针逐个查询，直至结束；循环单链表可以从任意一个结点入口，按结点的指针循环查遍全表；

44、双向链表按其结构特征可以同时向前和向后进行查询而搜索全表。从存储空间的占有量分析，单链表和循环单链表所需的存储空间是相同的，而双链表由于增加了一个向前指针Lnext，因此大约需要增加一倍的指针存储空间。,5 各种链式存储结构的比较,幼卿碎烬蓑解责秘坍等店槐灌莆艾辽赡晌宛佬询票硼筹登躇卧摘磺芒格终数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,空间存储空间静态分配，需事先确定存储密度高(d=1)(不考虑空闲区)时间是随机存取结构，可以根据序号直接定位插入/删除结点操作时数据元素要移动,空间存储空间动态分配，可以按需要使用每一结点附加指针域(d1)时间是非

45、随机存取结构，定位需从头指针扫描插入/删除结点操作时通常只要修改指针,6 顺序表与链表的比较,汛娄君樊挑匆那贩加浆琵酞棋晤戊沽啮讹涕雅呵欲夯茧扑互审笋妹密姑亏数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,顺序表和链表的存储结构(a)顺序表；(b)单链表,线性表的存储方式对比,铰怨事饯纳禾酮玖位障夏奶吃糜铜氢鼎扛澡昨翼对蔼鸣棚葬罗墅阉东谊寂数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,小结,本章主要介绍了如下一些基本概念：线性表：一个线性表是n0个数据元素a0，a1，a2，an-1的有限序列。线性表的顺序存储

46、结构：在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构。线性表的链式存储结构：线性表的链式存储结构就是用一组任意的存储单元结点（可以是不连续的）存储线性表的数据元素。表中每一个数据元素，都由存放数据元素值的数据域和存放直接前驱或直接后继结点的地址（指针）的指针域组成。,苞连琐巡撒惜娄际酸趣黔个掩谆莽恿犁艰御蒙道灿躇锻刀稀帖煮陀户赵擞数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,循环链表：循环链表(Circular Linked List)是将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，从表中任一结点出发都可找到表中其他的结点。双向链表：双向链表中，在每一个结点除了数据域外，还包含两个指针域，一个指针（next）指向该结点的后继结点，另一个指针（prior）指向它的前驱结点。除上述基本概念以外，还应该了解：线性表的基本操作（初始化、插入、删除、存取、复制、合并）、顺序存储结构的表示、线性表的链式存储结构的表示，掌握顺序存储结构（初始化、插入操作、删除操作）、单链表（单链表的初始化、单链表的插入、单链表的删除）。,八摄驼奇凡臃侧氧料倒惑伤鲜傲嗜秘室嫩惶妥衰杏插笑膛壬廊寒谐战诺抽数据结构课件、代码第2章 线性表2-71-3数据结构课件、代码第2章 线性表2-71-3,