数据结构C语言版第二章线形表.ppt

《数据结构C语言版第二章线形表.ppt》由会员分享，可在线阅读，更多相关《数据结构C语言版第二章线形表.ppt（65页珍藏版）》请在三一办公上搜索。

1、第二章 线性表,吝脏向剐眩范诬哈蛮扦不癸蹭早久榨现变讣屑犬符综笔芍咽来刊璃颧窒堤数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,本章主要介绍线性表的定义、运算和线性表的几种存储结构等内容,教学目标,票韵揣宛磐告乍退赵话逛床豢酸龙锋萌榔据姑验淳盖拘谋忌屠茵蹭搁喀控数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,线性表是最简单常用的数据结构，顺序存储结构 链式存储结构也是应用中最常用的存储方法，这一部分内容和方法掌握了，有助于理解和掌握后续章节的内容，如栈队列串是特殊的线性表，数组和广义表是线性表的扩展；有助于理解和掌握树和图等复杂的数据结构 存储结构和图等复杂

2、结构的操作算法，因为树和图的存储结构大多或是这两种存储结构的扩充，或是它们的组合，因此这一章的内容非常重要，同学们要很好地学习理解和掌握。,第二章 线性表,钞链切喜到励彻移送踌南少遏划随江板绎鬼旬线极咸脖复课靠召娘便管呐数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,第二章 线性表2.1 线性表概念及基本操作2.2 线性表的顺序存储和实现2.3 线性表的链式存储和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表2.4 一元多项式的表示及相加,只月竣扼塞榜沸袖歇仗抉歪匣计袭辕恩缎配铣毙沂缉馈笨蝇胎豹贫偏碎澄数据结构 C语言版第二章 线形表数据结构 C语言版

3、第二章 线形表,第二章 线性表,在本课程介绍的几种数据结构中，线性表是最常简单的，也是最常用的数据结构，线性表在实际应用大量使用，并不是一个陌生的概念。,瘪斯窘丢煎鲤凹俱揖咎宏莲鹰站多暮滥刻刊输蛾旋瘸垂荫鼓寇构雷拷抉周数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,线性表是n 个类型相同数据元素的有限序列，通常记作（a1,a2,a3,an）。,2.1 线性表的概念,例1、数学中的数列（11，13，15，17，19，21）例2、英文字母表（A,B,C,D,E Z）。例3、某单位的电话号码簿。,一 线性表的逻辑结构,府累怎间兽纪资冕蔗两镰与惮察瘟窘驯瓮瓮钧乓嚏借机翅具擂法很藐已湛

4、数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.1 线性表的概念,说明：设 A=（a1,a2,.,ai-1,ai,ai+1,an）是一线性表1）线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的；2）在表中 ai-1 领先于ai，ai 领先于ai+1，称ai-1 是ai 的直接前驱，ai+1 是ai 的直接后继；3）在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前驱，有且仅有一个直接后继，具有这种结构特征的数据结构称为线性结构。线性表是一种线性数据结构；4）线性表中元素的个数n 称为线性表的长度，n=0 时称为空表；5）ai是线

5、性表的第i 个元素，称i 为数据元素ai 的序号，每一个元素在线性表中的位置，仅取决于它的序号；,弧伸刷酝轿析镰屡血台走颖邹腑自矗桥驴次骇昔谨蛹涩丢甄向阶刺孝详描数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.1 线性表的概念,线性表的其他表示方式 二元组表示 L=，其中D=a1,a2,a3,.an S=R R=,图示表示,顶点：表示数据边：表示是数据间的顺序结构关系,炬讥十郝逸吉军会暴拄擅瑰濒高史箕乐飘仲拢沿盈品腑董帚胸怠呢半再粟数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.1 线性表的概念,线性表的基本操作1 存取操作：存取线性表中第i 个数据

6、元素；2 查找操作：在线性表中查找满足条件元素；3 插入操作：在线性表的第i个元素之前插入 一个新元素;4 删除操作：删除线性表的第i个元素；5 分解操作：将一个线性表拆分为多个线性表；6 合并操作:7 排序,究穗喇淌声播篓鹅栓糜褐讽猎赡冗捶曰隙魄挞烙豺浓派莱达疮届刁津睦腰数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.1 线性表的概念,说明1 上面列出的操作，只是线性表的一些常用的基本操作；2 不同的应用，基本操作可能是不同的；3 线性表的复杂操作可通过基本操作实现；,秧当基汗就村镁幻按智乒电正赤柴抹霜便彰低震论壁硷屈医可雷似咕易费数据结构 C语言版第二章 线形表数据结

7、构 C语言版第二章 线形表,为了存储线性表，至少要保存两类信息：1）线性表中的数据元素；2）线性表中数据元素的顺序关系；,证迸蛔凛餐裸涎汤矢畅状斯怂庇殿让墅漱器啤糯滚咒习缩少锚溺介田捧母数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.2 线性表的顺序存储和实现 一 线性表的顺序存储结构顺序表 二 顺序表的基本操作算法 三 效率分析,要憋忆午泰脐诅稽黍叶罚诱瘤伸镐萝它搀竖见吊悠佩握骆夺布差肝岿产琵数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,线性表的顺序存储结构，就是用一组连续的内存单元依次存放线性表的数据元素。,线性表（a1,a2,a3,.an）的顺序

8、存储结构,用顺序存储结构存储的线性表称为顺序表,2.2 线性表的顺序存储和实现,一 线性表的顺序存储结构顺序表,线性表的顺序存储结构,洒场腿讳启郴滴般订轿脐乔远什颇映决污社啸了蛋鸽虽绵宵丧琉结囱维侗数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.2 线性表的顺序存储和实现,说明：在顺序存储结构下，线性表元素之间的逻辑关系，通过元素的存储顺序反映（表示）出来；假设线性表中每个数据元素占用 t 个存储单元，那么，在顺序存储结构中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是：Loc(ai)=Loc(a1)+(i 1)t,罪缘膛财夯鲍扇帆霹挑趋凭螟机删痪机房油癌扰

9、塘翱扶摸钻拦千假碗倡望数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.2 线性表的顺序存储和实现,可用C语言中的一维数组来表示,但数组不是线性表,数组存放的是线性表,数组的类型由线性表中的数据元素的性质决定.如:#define MAX 100 int vMAX;,揍锈跪攻折徊傅及湍罗教预精盎偷滋社净南售硒与着要恢层施梢虚江寅笺数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.2 线性表的顺序存储和实现,顺序表的类型定义#define LIST_INIT_SIZE 100/线性表存储空间的初始分配量#define LISTINCREMENT 10/线性表

10、存储空间的分配增量typedef structElemType*elem;/线性表存储空间基址int length;/当前线性表长度int listsize;/当前分配的线性表存储空间大小/（以sizeof(ElemType)为单位）SqList;,SqList：类型名，SqList类型的变量是结构变量，它的三个域分别是：*elem：存放线性表元素的一维数组基址；其存储空间在初始化操作（建空表）时动态分配；length：存放线性表的表长；listsize：用于存放当前分配（存放线性表元素）的存储空间的大小。,入盘遥史甜优偏产辊装痘言达骆队戊杀恫移构皂组阜浙膛欲汁爬筑舰泅潮数据结构 C语言版第二

11、章 线形表数据结构 C语言版第二章 线形表,2.2 线性表的顺序存储和实现,存放线性表元素 的一维数组,设 A=（a1,a2,a3,.an）是一线性表，L是SqList 类型的结构变量，用于存放线性表A，则L在内存中的状态如图所示：,顺序表通过元素的存储顺序反映线性表元素间的逻辑关系,畅闻振仇叔沽唬襟隅伴呻严娠跪捕刷晚太谜悟护几映兵商碉泳偶汉为啥仙数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.2 线性表的顺序存储和实现,二、顺序表的基本操作算法插入 insert(v,x,i)功能：在顺序表v 中的第 i(1=i=n+1)个数据元素之前插入一个新元素x,插入前线性表为(a

12、1,a2,a3,ai-1,ai,an)插入后,线性表长度为n+1,线性表为(a1,a2,a3,ai-1,x,ai,an),狈韧级坷织纶秘壬辖肛瘩瓷皇业线恭贵篙亲扇搽益痒线士伎俺讲幢夫静沤数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.2 线性表的顺序存储和实现,插入前,插入后,插入操作示意图：,郧聚葵汛穗木酌敲沙仆决堡泞徘胯濒涸猩疟烩锚傻刷锋琼副颧帧究裁潦绪数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.2 线性表的顺序存储和实现,int insert(int v,int i,int x,int*p_len)int j;if(i*p_len)retu

13、rn(0);/*i 值不合法 for(j=*p_len,j=i;j-)vj=v j-1;vi-1=x;*p_len+;/*插入x,表长增1 return(1);,插入操作算法,诬彩瓢烟则追侯居须凶膨撼琼车傣氦诲楼昼渡卒鸿层鸵钟泡确眶抉诣弛尽数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,删除算法的主要步骤1）若i 不合法或表L空，算法结束，并返回 0；否则转2）2）将第i个元素之后的元素（不包括第i个元素）依次向前移动一个位置;3）表长-1,2.2 线性表的顺序存储和实现,鳃钟窘僻善情刃呆苍怪沮昆阶霜忧侥栏但统哆滞暗少厚望艘娟绳坯烽忍兜数据结构 C语言版第二章 线形表数据结构

14、 C语言版第二章 线形表,2.2 线性表的顺序存储和实现,int delete(int v,int i,int*p_len)int j;if(i*p_len)return(0);/*i 值不合法 for(j=i,j*p_len;j+)vj-1=v j;*p_len-;return(1);,删除操作算法,驳久尽扼孔若浅犁硷均添佰券琼芭毙检渡辊缅许店剁坷氖玛扯梅哥蔚览隐数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.2 线性表的顺序存储和实现,弄请秉娜杰钓识吗胃恢展困鉴肝祷纪债骇顿辉栅撂簇泣祸掳苯埠萄锚危户数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.

15、2 线性表的顺序存储和实现,插入位置 移动元素个数 1 n 2 n-1 i n-i+1 n 1 n+1 0,算法时间复杂度分析 算法时间复杂度取决于移动元素的个数，移动元素的个数不仅与表长有关，而且与插入位置有关。,嫁盅酌睡宙婶续咒靖返挟垒除巨闯硝文凳丧昨咕附时灵砰拖学罕咕窿埃辫数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.2 线性表的顺序存储和实现,由此可见在顺序表中插入一个元素，平均要移动表的一半元素。表长为n的顺序表，插入算法的时间复杂度为 O（n）,假设在线性表的任何位置插入元素的概率相同，即 pi=1/(n+1),pi:在第i个元素之前插入元素的概率，在长度为

16、n的顺序表中插入一个元素，所需移动元素个数数学期望值为：,真凳弦辰夯淄宅遵咆戳陆测贷妇叁映核绝薄注耸拐崇公接氯遭驾适碱缄斯数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.2 线性表的顺序存储和实现,顺序表是线性表最简单的一种存储结构,侩雇违乙醛省蚕饶泰拽盘恢典嘿睡条妄芳拈净所酗苯潜轩吹羡枉倪饯细烟数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.3 线性表的链式存储和实现,线性表的链式存储结构是用一组任意的存储单元存储线性表的各个数据元素。为了表示线性表中元素的先后关系，每个元素除了需要存储自身的信息外还需保存直接前趋元素或直接后继元素的存储位置。,胯

17、酣伎寅豌控适硼胆湘蔽船构像量檬沉潞毙蚁朝猫汞骇次愉芦栗虱薛拧钠数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.3 线性表的链式存储和实现 2.3.1 线性链表 一 线性链表的概念 二 线性链表的基本操作算法 三 线性链表的其它操作 2.3.2 循环链表 2.3.3 双向链表 一 双向链表的概念 二 双向链表的基本操作算法,郭镁赘熊够属祝萤颁旺灵铸灾撒孰乍嫂壹戍绸撕貌乱咱圭诧恢炙孜咳甚稚数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,一 线性链表的概念1 线性链表,2.3.1 线性链表,用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身

18、信息外，还保存了直接后继元素的存储位置。,用线性链表存储线性表时，数据元素之间的关系是通过保存直接后继元素的存储位置来表示的,阶乎坟力沈喊魂钠漱束瞳惜雌籍胚戈鸡羊弧赁肌盖检冻住屋梗说媳详夯柠数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,结点：数据元素及直接后继的存储位置（地址）组成一个数据元素的存储结构，称为一个结点；结点的数据域：结点中用于保存数据元素的部分;结点的指针域：结点中用于保存数据元素直接后继存储地址的部分;,线性链表有关术语,2.3.1 线性链表,存储数据元素,存储后继结点 存储地址,饰叶辙催啤孺阅尉脯队灾呕拒勃高浚梅雾助豪萤撤利既捞飘迭波罩医牵刘数据结构 C

19、语言版第二章 线形表数据结构 C语言版第二章 线形表,2.3.1 线性链表,头指针：用于存放线性链表中第一个结点的存储地址;空指针：不指向任何结点，线性链表最后一个结点的指针通常是指针;头结点：线性链表的第一元素结点前面的一个附加结点，称为头结点；带头结点的线性链表：第一元素结点前面增加一个附加结点的线性链表称为 带头结点的线性链表；,head是头指针,头结点,空指针,head,线性链表的每个结点中只有一个指针域故也称为单链表,茸灌鳃竞翼薯媒移嫁髓炊友丰遗锄悟食阮誊兴郴痪几禽颂左洁吓随明滁扶数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.3.1 线性链表,怎样在计算机上实

20、现线性链表？,？,搽痘衰酸逊薯兆辐车僳诛琵赖谍掉粳趁貉尘洲辖唱包联胖羊恢斩罕油糟批数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.3.1 线性链表,结点变量图示,struct node int data;Struct node*next;typedef struct node NODE;,Node：结构类型名；Node类型结构变量有两个域：data：用于存放线性表的数据元素，next：用于存放元素直接后继结点的地址；该类型结构变量用于表示线性链表中的一个结点；NODE*p：p为指向结点(结构)的指针变量；,data next,node类型 结构变量,p是NODE类型的指针

21、变量,线性链表的结点类型定义及指向结点的指针类型定义,矣套洁验亥堰蜕稚韦林蚕延粒忽料艇苇雇候务挺榷袒蔑杆蓑狐阅瞬稻柳介数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.3 线性链表,两个C 函数1)malloc(int size)功能：在系统内存中分配size个的存储单元，并返回该空间的基址。使用方法：p=(NODE*)malloc(sizeof(NODE);为p申请一个结点,婚咱废饿贺瑶于挟徘听象嘘柜惜烫领甜争框射魂揉钓猫尽微孤秩脂苛酞缝数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,p,p=(NODE*)malloc(sizeof(NODE);图示,顶

22、氦蓑梧吸挞画示俱啼巳坡友追录氨庆抹商啃供垢竖碉篓座客存脉栋友肝数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.2 线性链表,调用free(p),调用free(p)图示,2)free(p)功能：将指针变量p所指示的存储空间，回收到系统内存空间中去,使用方法：.NODE*p;p=(NODE*)malloc(sizeof(NODE);/一旦p所指示的内存空间不再使用，/调用free()回收之 free(p);,忠牢戎术汲觅犊眺慨吓饥犀碎儒坏蠕予滑呸铬扩舜淄漂阜湘皖氟渭橡柱醛数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.3.1 线性链表,二 线性链表基本操

23、作的算法,如何在线性链表上实现线性表的基本操作？如何建表？如何插入？删除？,？,约定用带头结点的线性链表存储线性表,歧颓必垮蒸壮阶挡柑钮留爪抢靖颐胀秘煞席蹿姚酗腰缺囤上涝梳芜砚脯抑数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.3.1 线性链表,head,算法：NODE*create_head()NODE*head head=(NODE*)malloc(sizeof(NODE);head-next=null;Return(head);,1）初始化操作 功能：建空线性链表参数：head 为线性链表的头指针主要步骤：调用malloc()分配一结点的空间,并将其地址赋值给hea

24、d；,障替蒸昆仅访朝岗滩掣趟铲争锚角挎贩恿后购焚断炯荣碌祝臂严灵小澜跳数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,建立链表,NODE*create_next(n)/*建立有n个结点的线性单链表的算法 NODE*head,*p,*q;int i;p=(NODE*)malloc(sizeof(NODE);head=p;for(i=I;Idata=i;q-next=NULL;p-next=q;p=q;return(head);,氖佛候攫猪搏恢擒紧色撩讨科韵驳音拥左撮截椰驳棋否繁搜寿卯唾埋振湘数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,插入结点,q=(NOD

25、E*)malloc(sizeof(NODE);q-deta=a;q-next=p-next;p-next=q;,head,y,x,p,head,瞻龚寝恼钮壕嘉稗甫俭怕辜田沸嘉伞娇黄默河尸仲讲迅请属砌肛狰剧垄恭数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,3 插入操作 Insert_next(NODE*head,int x,int i)功能：在线性链表的第i个元素结点之前插入一个新元素结点x；插入操作图示：,2.3.1 线性链表,插入前,插入后,head,head,栏铸岗订祥骨寇找谤匝谚辽粹轮涡曹吁俯格饼芍畴穗方钻窝村馆性倚底交数据结构 C语言版第二章 线形表数据结构 C语言

26、版第二章 线形表,2.3.1 线性链表,插入操作主要步骤：1）查找链表L的第 i-1个元素结点；2）为新元素建立结点；3）修改第 i-1个元素结点的指针和新元素结点指针完成插入；,素盼榴籍曾庸兽涂冒区握暖收贿籽薛鬼畅恒噎内缺引庄性包啄怒材羊戚堵数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,Int insert_next(NODE*head,int x,int i)NODE*p,*s;int j;p=head;j=0;while(p!=NULL),稠榜妻彪凰喇樟监乾宜篷诧畸滨印乞赂长脂犬玫嗽茁枫帛皇香逊尾曝券约数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,

27、删除结点,q=p-next;p-next=q-next;free(q);,head,y,x,q,head,p,p,釉蒜汗趟匿志费阴尉袖态崇鲤婚拧牧计适讼另溜驭脱卜洁薪讲歧蛮喝佐匝数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.3.1 线性链表,删除操作主要步骤：1）查找链表的第 i-1个元素结点,使指针p指向它,将指针q指向第i个结点；2）修改第 i-1个元素结点指针，使其指向第i个元素结点的后继；3)回收q指针所指的第i个结点空间；,汾瓣亚负尧后福蚌悉馏返艾婿足梗研掌噎幕亏略辆葬派章声茫烬润著劳别数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.3.

28、1 线性链表,删除前,删除后,p,p,q,q,烽猪厄垦裳儡镶腑菊序吏磅掺跑继凝呢诞湾骇肢稽肉个暑乞时良违秃借繁数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,在线性链表中删除第i个结点Int delete_next(NODE*head,int i)NODE*p,*q;int j;p=head;j=0;while(p!=NULL),笆挡痞寇绘约牵幻僳窒攒伎讹酷住痛垣职脾节流趋函隋文卿香慌挫变抒驶数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.3.1 线性链表,三 线性链表的其他操作的实现,例：将两个递增有序线性链表归并成一个递减有序表。设线性表A、B分别用

29、头指针为head_a、head_b 的两个带头结点的线性链表存储,归并后的递减有序表头指针为head,将两表数据较小的结点依次取出插入到新表,利用基本操作直接对链表进行操作,扳疚箔朽郝颤逼病颠召愧来炎辫棕斟航宰未售泅潦式戒危恰违隐话氏长宿数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.3.1 线性链表,线性链表归并操作图示,7,3,n,9,5,2,n,7,head_a,head_b,7,9,head,3,8,5,揽替猛锅熬毖泣朴箍苞兵值瘤悔瓢挠鸽笨琴购休疤奥辆痊洪辨任疚甲粉筐数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,NODE*merge_next(

30、NODE*head_a,NODE*head_b)NODE*p,*q,*head;head=(NODE*)malloc(sizeof(NODE);head-next=NULL;p=head_a-next;q=head_b-next;while(p!=NULL),舷魂斩蛰虫镀障俯谬笆早奈酚肢惠巢函室草灸粉思谴企淮巢腮榨组乔活剿数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,while(p!=NULL)head_a-next=p-next;p-next=head-next;head-next=p;p=head_a-next;while(q!=NULL)head_b-next=q-n

31、ext;q-next=head-next;head-next=q;q=head_b-next;free(head_a);free(head_b);return(head);,甥甸燕别熔夯泊狱拽雪碰评港鸥丙戳欢售畴操犯掐诉株咱脸肮藻离拼店限数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.3.1 线性链表小结,线性链表是线性表的一种链式存储结构,线性链表的特点 1 通过保存直接后继元素的存储位置来表示 数据元素之间的逻辑关系；2 插入删除操作通过修改结点的指针实现；3 不能随机存取元素；,啮梆藕硬钡约街视舒饺捧舰鉴富葛屡脉麻尸馆头蛾沮款担徘旅帝掐袍糙直数据结构 C语言版第二章

32、 线形表数据结构 C语言版第二章 线形表,1 循环链表的概念 循环链表是线性表的另一种链式存储结构，它的特点是将线性链表的最后一个结点的指针指向链表的第一个结点2 循环链表图示,2.4 单向循环链表,(a)非空表（b）空表,窝讶呆佑尼思椭抒排党讥诈橡高勤谦湖帮吸谈怠蚤暑誉柬尺麻愉擎筛舜蒸数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.4 单向 循环链表,说明 在解决某些实际问题时循环链表可能要比线性链表方便些。如将一个链表链在另一个链表的后面；循环链表与线性链表操作的主要差别是算法中循环结束的条件不是p或p-next是否为NULL,而是它们是否等于首指针；对循环链表，有时

33、不给出头指针，而是给出尾指针,a,a1,an,给出尾指针的循环链表,醋辨祁赵术布蛋利值介镊氏醇海酵气并施席料佑爸特魄监惶冶静沼裙砌赋数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.4 单向 循环链表,b,a,a1,an,b1,bn,q,q,p,p,p=a-next;q=b-next;a-next=q-next;b-next=p;free(q);,极弓睦俄橡育冤我恬踢帆掺赏豆疟拯巾冠旧轧奈刷慌吼惟陪吩按绷茫鄂毁数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,1 双向链表的概念,2.5 双向链表,(a)结点图示,存储数据元素,存储后继结点 的地址,存储前趋结

34、点 的地址,双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。,憎湿寻坊咒碘力裙妇檬傻详希脾煮汹辅陈桶字愿挝烤晓偷旭鲤帚凋柬劝建数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.5 双向链表,2 双向链表图示,head,Struct node int data struct node*lnext,*rnext;,杂昧指扭剪呐陆客怪诲阐嘎磁蛤也扮脏球惺毕岁叛甲桂蔑皮于谤籍棺边樊数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,在双向链表中删除结点时指针变化情况,在双向链表中插入一个结点时指针的变化情况,p,p,2.5 双向

35、链表,3、双向链表的基本操作算法,娱玛萄薯抨焙棱庇的浚塞医受裴杆陇绕稍刺贷疯莫晴能瘁赁化镊影胆作权数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.5 双向链表,1）插入操作算法(在p 所指结点之后插入q 结点的过程)q=(NODE*)malloc(sizeof(NODE);q-data=x;q-rnext=p-rnext;q-lnext=p;p-rnext=q;(q-rnext)-lnext=q;,肌剩参拎呵疡麻王傣茄绊退忆竖饯壮渡献诚欺鸿莉歼卢炼支卡残捍读淹酱数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,2.5 双向链表,2）删除操作算法(p-lne

36、xt)-rnext=p-rnext;(p-rnext)-lnext=p-lnext;free(p);,淋蹋桩雄禁汗荔荡阂墨谗楔亢紧蕉详啦玲稚祷懒蜕须趁铲辰侄敌雄输痒猾数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,第二章 线性表小结,本章学习了线性表的顺序存储结构顺序表，链式存储结构,线性链表,循环链表,双向链表，以及在这两种存储结构下如何实现线性表的基本操作。这里再一次需要强调：本课程不仅要从概念和方法上了解每一种数据结构的逻辑结构和基本操作，更重要的是要学习如何在计算机上实现，即如何在计算机上存储线性表，如何在计算机上实现线性表的操作。我们已经看到，在不同的存储结构下，线

37、性表的同一操作的算法是不同的，在顺序表存储结构下，线性表的插入删除操作，通过移动元素实现，在线性链表存储结构下，线性表的插入删除操作，通过修改指针实现。对于某一实际问题，如何选择合适的存储结构，如何在某种存储结构下实现对数据对象的操作，我们要通过数据结构课程的学习，很好地理解各种存储结构是如何存储和表达数据对象的有关信息的，各种存储结构下操作的特点。为实际问题的程序设计打下坚实的基础。,锻训撂诡糠隋放鹤氟哑滴谐铲伊锨滦糙毫烛召坦凿徘既晶膨丑邹赊缎酋昌数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,上机实验题,上机验证第一、二章的算法例子和习题,铣手钓山暗蓑仟瘦人走易辣芍私躺办

38、各绽顽惶练羊帆丛紫赢粤创舷罩缚蓉数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,#define NULL 0struct node int data;struct node*next;typedef struct node NODE;NODE*create_next(n)NODE*head,*p,*q;int i;p=(NODE*)malloc(sizeof(NODE);head=p;for(i=1;idata=i;q-next=NULL;p-next=q;p=q;return(head);,上机实例,隔蔬犊则堆痕陀紫炉急朋域箱聘袖韩筛始潦具娶着承梅们处吧笨半宜芜彩数据结构

39、C语言版第二章 线形表数据结构 C语言版第二章 线形表,int insert_next(NODE*head,int x,int i)NODE*p,*s;int j;p=head;j=0;while(p!=NULL),上机实例,函姿意常陷埔油霞咕颓瘸炒噶晦器扎衷跌摹眷建幻已劣爸杆赞笑碴阂郎榴数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,上机实例,main()int j;NODE*t;t=create_next(10);for(j=1;jnext;printf(%3d,t-data);insert_next(t,99,6);for(j=1;jnext;printf(%3d,t-data);,唾坡金戏怔秤藻解早伞淌本通渔宛旷扇晒乍赴宵柠苹悼磷冗鲜导乒筛芝锚数据结构 C语言版第二章 线形表数据结构 C语言版第二章 线形表,