《706-⒈教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现.ppt》由会员分享，可在线阅读，更多相关《706-⒈教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现.ppt（46页珍藏版）》请在三一文库上搜索。
1、2019年12月29日,数据结构讲义,1,教学内容：2.1 线性表逻辑结构； 2.2 线性表的顺序存储及运算实现； 2.3 线性表的链式存储和实现。 教学目的：理解线性表的定义及其运算； 理解顺序表和链表的定义、组织形式、结构特征和类型说明； 掌握在这两种表上实现的插入、删除和按值查找的算法； 了解循环链表、双(循环)链表的结构特点和在其上施加的插入、删除等操作。 教学重点：线性表的定义及逻辑上的特点； 顺序表上插入、删除和定位运算的实现； 单链表的结构特点及类型说明； 头指针和头结点的作用及区别； 定位、删除、插入运算在单链表上的实现； 循环链表、双链表的结构特点，循环链表、双链表上删除与插
2、入运算的实现。 教学难点：线性表与线性结构的联系与区别； 头结点在链表中的作用；指针操作； 删除、插入运算中的指针操作顺序； 双链表上指针的操作顺序。 教学时数： 8学时（含习题课2学时）,第二章 线性表,贴制巡釜愈便顽九曰沟匣贿饥运杖持才瘪趴窖猛叫铰秃旋字助郎式筹婚诽706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,2,2.1 线性表的逻辑结构,线性表的定义 线性表的基本操作,宜擅绦屹斟途株贱卉声镣全字阜剐广或婶堂萍蹬识供买篆妻捣逼蜒揩慧臼706-教学
3、内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,3,2.1.1 线性表的定义,线性表是一种线性结构。线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。在一个线性表中数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构。 线性表是具有相同数据类型的n(n=0)个数据元素的有限序列，通常记为： (a1，a2， ai-1，ai，ai+1，an) 其中n为表长， n0 时称为空表。 表中相邻元素之间存在着顺序关系。将 ai-1
4、称为 ai 的直接前趋，ai+1 称为 ai 的直接后继。就是说：对于ai，当 i=2，.，n 时，有且仅有一个直接前趋 ai-1.，当i=1，2，.，n-1 时，有且仅有一个直接后继 ai+1，而 a1 是表中第一个元素，它没有前趋，an 是最后一个元素无后继。 需要说明的是：ai为序号为 i 的数据元素（i=1,2,n），通常我们将它的数据类型抽象为datatype，datatype根据具体问题而定，如在学生情况信息表中，它是用户自定义的学生类型； 在字符串中，它是字符型； 等等。,芒癌瞪滚擦肖信郁盗憨肿铅逊贝兹靶暗痛材逃暂顷俐扑尚柞净闽聋乎浚折706-教学内容：2.1 线性表逻辑结构；2
5、.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,4,2.1.2 线性表的基本操作,线性表初始化：Init_List(L) 初始条件：表L不存在 操作结果：构造一个空的线性表 求线性表的长度：Length_List(L) 初始条件：表L存在 操作结果：返回线性表中的所含元素的个数 取表元：Get_List(L,i) 初始条件：表L存在且1=i=Length_List(L) 操作结果：返回线性表L中的第个元素的值或地址 按值查找：Locate_List(L,x)，是给定的一个数据元素。 初始条件：线
6、性表L存在 操作结果：返回在L中首次出现的值为的那个元素的序号或地址，称为查找成功; 否则，在L中未找到值为的数据元素，返回一特殊值表示查找失败。 插入操作：Insert_List(L,i,x) 初始条件：线性表L存在，插入位置正确 (1=i=n+1,为插入前的表长)。 操作结果：在线性表L的第 i 个位置上插入一个值为 x 的新元素，这样使原序号为 i , i+1, . , n 的数据元素的序号变为 i+1,i+2, . , n+1，插入后表长=原表长+1。 删除操作：Delete_List(L,i) 初始条件：线性表L存在，1=i=n。 操作结果：在线性表L中删除序号为i的数据元素，删除后
7、使序号为 i+1, i+2,., n 的元素变为序号为 i, i+1,.,n-1，新表长原表长。,需要说明的是： 某数据结构上的基本运算，不是它的全部运算，而是一些常用的基本的运算，而每一个基本运算在实现时也可能根据不同的存储结构派生出一系列相关的运算来。 在上面各操作中定义的线性表仅仅是一个抽象在逻辑结构层次的线性表，尚未涉及到它的存储结构。,浇百枢戌蠕方半深守仆楼垫晚为搭遏铁连作销硕睫巢暂绞轨滤都逗语凿呻706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲
8、义,5,2.2 线性表的顺序存储及运算实现,线性表的顺序存储 顺序表上基本运算的实现 顺序表应用举例,萍钎狙砚馅戏滔捎原芜锹梁袭帚雏颤怯踌闰豁怯帮树沁衫臻拯复揖沟飘穷706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,6,2.2.1 线性表的顺序顺序存储,线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。 设 a的存储地址为Loc(a)，每个数据元素占d个存储地址，则第i个数据元素的地址为：
9、 Loc(ai)=Loc(a)+(i-1)*d 1In 从结构性上考虑，通常将 data 和 last 封装成一个结构作为顺序表的类型： typedef struct datatype dataMAXSIZE; int last; SeqList;,祈时鲤栅邀偿劫润萍宠被壁紧栈颧核毡火呵宏眶拯影夜堂屎诧匣悉蜒赞狸706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,7,2.2.2 顺序表上基本运算的实现 顺序表的初始化,顺序表的初始化即构造一个空表，对表是一
10、个加工型的运算，因此，将 L设为指针参数，首先动态分配存储空间，然后，将表中 last 指针置为1，表示表中没有数据元素。,疼幢肩券敖井睛瘫编聘例开傀卜歧溢庐汉册整蜗鸿罗珍监枚潮惧埂峡嗣呛706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,8,插入运算,线性表的插入是指在表的第i个位置上插入一个值为 x 的新元素：,邻蚀鲜戳挖闽哇慑擦怎很式嫌饱于黄札今奏阵飘猛怂佰晶豪骡半彰粮困连706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现7
11、06-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,9,插入算法的时间性能分析,顺序表上的插入运算，时间主要消耗在了数据的移动上，在第i个位置上插入 x ，从 ai 到 an 都要向下移动一个位置，共需要移动 ni1个元素，而 i 的取值范围为 ：1 i n+1，即有 n1个位置可以插入。设在第i个位置上作插入的概率为Pi，则平均移动数据元素的次数： 设：Pi=1/ (n+1) ，即为等概率情况，则： 这说明：在顺序表上做插入操作需移动表中一半的数据元素。显然时间复杂度为(n)。,僵版魂吐坤将党瓤牌祟均盏仔在秽挛棠蒂鹿截锦匀紧淑为挞
12、扣闻店午噎叉706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,10,删除运算,线性表的删除运算是指将表中第 i 个元素从线性表中去掉。,球黎病液波盟把药野驯质敞如逻米坛巡盐迈髓顾志唇拒脏鱼霍檄侠毒糯衔706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,11,删除算法的时间性能分析,与插入运算相同，其时间主要消耗在了移
13、动表中元素上，删除第i个元素时，其后面的元素 ai+1an 都要向上移动一个位置，共移动了 n-i 个元素，所以平均移动数据元素的次数： 在等概率情况下，pi =1/ n，则： 这说明顺序表上作删除运算时大约需要移动表中一半的元素，显然该算法的时间复杂度为(n)。,喻癣挟沈臃戊襄赚层熙料卿粟窿除阎尸饥鳞贩甫汛伏七司渣屠逝江汲誊硝706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,12,按值查找,线性表中的按值查找是指在线性表中查找与给定值x相等的数据元素。
14、,本算法的主要运算是比较。显然比较的次数与x在表中的位置有关，也与表长有关。平均比较次数为（n+1）/2，时间性能为O(n)。,看颠傈淌难伺拭佩查奸丑牙瞒式箭抛葫悬阳广人链屎妄秦爹舰醒卷感计涤706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,13,2.2.3 顺序表应用举例,例2.1 将顺序表 (a1，a2，. ，an) 重新排列为以 a1 为界的两部分：a1 前面的值均比 a1 小，a1 后面的值都比 a1 大。 划分的方法有多种，下面介绍的划分算法其
15、思路简单，性能较差。 基本思路： 从第二个元素开始到最后一个元素，逐一向后扫描： 当前数据元素 aI 比 a1 大时，表明它已经在 a1 的后面，不必改变它与 a1 之间的位置，继续比较下一个。 当前结点若比 a1 小，说明它应该在 a1 的前面，此时将它上面的元素都依次向下移动一个位置，然后将它置入最上方。,窘绅伺三茅招瞄纸匡晤挞赠楞汰兔福释猪搜忠滨共蘸伞筐凿龙卫酷聋宋公706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,14,总的移动次数为 ： 即最坏
16、情况下移动数据时间性能为()。,转淬耪园咆钝儡瞬封蹄沿垢到娶随来荐冈担沥它犁也虫耽稼松伺殷欠煮秒706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,15,例2.2 有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大的升序排列。 算法思路：依次扫描通过A和B的元素，比较当前的元素的值，将较小值的元素赋给C，如此直到一个线性表扫描完毕，然后将未完的那个顺序表中余下部分赋给C即可。C的容量要能够容纳A、B
17、两个线性表相加的长度。,符佳拉卑亨绑沸岿蛤余离聂革撕链察蜜启易健织荆理嘎密蔼阻九律恢灵胎706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,16,算法的时间性能是O(m+n)，其中m是A的表长，n是B的表长。,鹊空招曹鹏毯镣们壤享伏锈罕潦昏瞥辆敛赁例婆偏唱铸煮知昨役棱荤曹介706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构
18、讲义,17,例2.3 比较两个线性表的大小。两个线性表的比较依据下列方法：设A、B是两个线性表，均用向量表示，表长分别为m和n。 A和B分别为 A 和 B 中除去最大共同前缀后的子表。 例如A=(x,y,y,z,x,z)， B=(x,y,y,z,y,x,x,z)，两表最大共同前缀为 (x,y,y,z) 。则A=（x,z），B=（y,x,x,z），若A= B= 空表，则A=B；若A=空表且B空表，或两者均不空且A首元素小于B首元素，则AB。 算法思路：首先找出A、B的最大共同前缀；然后求出A和B，之后在按比较规则进行比较，AB 函数返回1；A=B返回0；AB返回-1。,夹熏被做皂闺楞前顾们刑秆领
19、湘具曾彪献侯者札繁失糕抄内跌竹痪矢姆雀706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,18,算法的时间性能是O( m+n )。,涌污寓悠蓬念互遗迁傻稻汐绪机夺多盔焕钾熄宫晨廉欠录嗜桥醋泡晓铁桂706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,19,2.3 线性表的链式存储和运算实现,单链表 循环链表 双向链表 静
20、态链表 单链表应用举例,谢慰伦牡圃崔抿鸵衬填伪腕谆鉴瑟专懊视凶茄煎畜硷状二俱侦避鹏奖贺铺706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,20,2.3.1 单链表,链表是通过一组任意的存储单元来存储线性表中的数据元素的，对每个数据元素ai，除了存放数据元素的自身的信息 ai 之外，还需要和ai一起存放其后继 ai+1 所在的存贮单元的地址，这两部分信息组成一个“结点”。存放数据元素信息的称为数据域，存放其后继地址的称为指针域。 链表是由一个个结点构成的，
21、 结点定义如下： typedef struct node datatype data; struct node *next; LNode，*LinkList； 定义头指针变量： LinkList H；,曙亮窝猖贾注固酸渐抿版除砚线详净曳寿硕鸣高储括鲸肢枢履绪退魔糖敢706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,21,2.3.2 单链表上基本运算的实现 建立单链表,在链表的头部插入结点建立单链表,糕谍熄撰圃陕搔擎戒锑滇严犁逊糖疙仑秀彰霍涤傣吞会议汀桃恳
22、肄匹圭腊706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,22,在单链表的尾部插入结点建立单链表,斤樱后悬另瀑趋晰掳均说殆富鸦戏誓爹启乒窿昼启蛛怔盂千刻矛旺腰币凡706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,23,求表长,设L是带头结点的单链表(线性表的长度不包括头结点)。,侗螺津砍兔著傻智紧勘首总滤囤撂炙婆天
23、浇娶古舰迷卵灼莎怠抛峨肤涕魏706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,24,设L是不带头结点的单链表。,酪竟冒长荒蘸过恩宗伞秧贾耶捎翠继颧赛返绊截溢补讲雀驭佃临鸽缆庞哉706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,25,查找操作,按序号查找 Get_Linklist(L,i) 算法思路：从链表的第一个元
24、素结点起，判断当前结点是否是第i个，若是，则返回该结点的指针，否则继续后一个，表结束为止。没有第个结点时返回空指针。,参拾境烷身史罩呢猩则懈捡散纹羞红士俗劝猩沫晾炒受豁奴搔晚鹅怕亮蛀706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,26,按值查找即定位 Locate_LinkList(L,x) 算法思路：从链表的第一个元素结点起，判断当前结点值是否等于x，若是，返回该结点的指针，否则继续后一个，表结束为止。找不到时返回空指针。,算法2-12、算法2-13
25、的时间复杂度均为O(n)。,膨期峪踪任踞旋稳经逮窗囤求漓伤氨短隙丧温绪卯苔装爆凹裹夷塌薄牟鞍706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,27,插入操作,后插结点：设p指向单链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的后面。 操作如下： s-next=p-next; p-next=s; 注意：两个指针的操作顺序不能交换。,帽穆芬辖捐冻耍砸痈托零沾热裴拌衍钥室跑紫姐蕴陷诉毙垂料剃咕丸砖悔706-教学内容：2.1 线性表逻辑结构；2.2
26、 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,28,前插结点：设指向链表中某结点，指向待插入的值为x的新结点，将*s插入到*p的前面。与后插不同的是：首先要找到*p的前驱*q，然后再完成在*q之后插入*s，设单链表头指针为L，操作如下： q=L; while (q-next!=p) q=q-next; /*找*p的直接前驱*/ s-next=q-next; q-next=s;,杂宦灸追憾舵衔利万尚勺啡润欢佣欧澜殴纠贿捏暗箭足躁爆玛卓襟蜗宠荆706-教学内容：2.1 线性表逻辑结构；2.2 线性表的
27、顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,29,插入运算 Insert_LinkList(L,i,x) 算法思路：1.找到第i-1个结点；若存在继续2，否则结束。 2.申请、填装新结点。 3.将新结点插入，结束。,算法2-14的时间复杂度为O(n)。,蓝嘿骡啄驼栽铱熏琳趟袱椒档葫涧纽殃仓织渊冻向炯另婴贿懒颇印路沥策706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,
28、30,删除操作,设p指向单链表中某结点，删除*p。要实现对结点*p的 删除，首先要找到*p的前驱结点*q，然后完成指针的操作即可。指针的操作由下列语句实现： q-next=p-next; free(p); 显然找*p前驱的时间复杂性为O(n)。 若要删除*p的后继结点(假设存 在)，则可以直接完成： s=p-next; p-next=s-next; free(s); 该操作的时间复杂性为O(1) 。,锁轿债扰讫族屈驰釉姜非羡酱晕庆畦狞呐上虚份盘洗蚊檄怯凉鸭点舵脯虚706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表
29、的顺序存储及运算实现,2019年12月29日,数据结构讲义,31,删除运算：Del_LinkList(L,i) 算法思路：1.找到第i-1个结点；若存在继续2，否则结束。 2.若存在第i个结点则继续3，否则结束。 3.删除第i个结点，结束。,算法2-15的时间复杂度为O(n)。,榜台汗痘售肌固羽鲜步象上羔戍宿涩董蚁锹炮摇办闭瞪篡隆昼迎傅易堑渠706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,32,2.3.3 循环链表,对于单链表而言，最后一个结点的指针域
30、是空指针，如果将该链表头指针置入该指针域，则使得链表头尾结点相连，就构成了单循环链表。,在单循环链表上的操作基本上与非循环链表相同，只是将原来判断指针是否为NULL变为是否是头指针而已，没有其它较大的变化。 对于单循环链表则可以从表中任意结点开始遍历整个链表；另外，有时对链表常做的操作是在表尾、表头进行，此时可以改变一下链表的标识方法，不用头指针而用一个指向尾结点的指针R来标识，可以使得操作效率提高。,妆要绕喝铀陵茵赁欧学奋肚轰幻名稗溃序踏唁茎囱吉好蔚甭恳辛彼阳歹赠706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性
31、表的顺序存储及运算实现,2019年12月29日,数据结构讲义,33,例：对两个单循环链表H1 、H2的连接操作，是将H2的第一个数据结点接到H1的尾结点，如用头指针标识，则需要找到第一个链表的尾结点，其时间复杂性为O(n)，而链表若用尾指针R、R2来标识，则时间性能为O(1)。操作如下： P= Rnext; /*保存第一个表的头结点指针*/ R-next=R2-next-next; /*头尾连接*/ free(R2-next); /*释放第二个表的头结点*/ R2-next=P; /*组成循环链表*/,陵攫必昭廓坍泡朝瞒腔赞呼柑迅幅忍蛋惨蜕讲阂旨修信锯脸惠半奈戎吴酵706-教学内容：2.1 线
32、性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,34,2.3.4 双向链表,单链表的结点中只有一个指向其后继结点的指针域next，找后继的时间性能是O(1)，找前驱的时间性能是O(n)；可以付出空间的代价使得找前驱的时间性达到O(1)：每个结点再加一个指向前驱的指针域。用这种结点组成的链表称为双向链表。 双向链表结点的定义如下： typedef struct dlnode datatype data; struct dlnode *prior,*next; DLNode,*DLi
33、nkList;,梅澳浦溃侨捌厅仓墒韵娜段祷案虚林肺献墒须呵润熔吃昆跃巷吱惨够票胳706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,35,和单链表类似，双向链表通常也是用头指针标识，也可以带头结点和做成循环结构。通过某结点的指针p即可以直接得到它的后继结点的指针p-next，也可以直接得到它的前驱结点的的指针p-prior。这样在有些操作中需要找前驱时，则勿需再用循环。 p-prior-next = p= p-next-prior,兹傅废粘全俯屑已匪宴耀下
34、匿墨赣供讽颖莉诀翠酸闰洪输唱教烛署烫钻专706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,36,在双向链表中插入一个结点： 设p指向双向链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的前面。操作如下： s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; 上面指针操作的顺 序不是唯一的，但也 不是任意的，操作必须要放到操作的前面完成，否 则*p的前驱结点的指针就丢掉了。,蝇轧泪纯橱森廓洼
35、铃料连五尧闹饿战挖邢只君辱吧杨林处肮肯设景蹬队栋706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,37,在双向链表中删除指定结点： 设p指向双向链表中某结点，删除*p。 操作如下： p-prior-next=p-next; p-next-prior=p-prior; free(p);,拙宽桓吮咎俞晨婴弃芦赃苑芝挫谍楔邱列儡厚筐憎鳃圣邯械拨壕蜡迅刁泵706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表
36、逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,38,2.3.5 静态链表,首先看一个例子：规模较大的结构数组 sdMAXSIZE 中有两个链表：其中链表SL是一个带头结点的单链表，表示了线性表(a1, a2, a3, a4, a5)，而另一个单链表AV是将当前 sd 中的空结点组成的链表。 数组sd的定义如下： #define MAXSIZE /*足够大的数*/ typedef struct datatype data; int next; SNode; /*结点类型*/ SNode sdMAXSIZE; int SL,AV; /*两个头指针变量*/,伸撤
37、悠腮速挺牺散卡钮坟霸乾彻息托杏浑仪扼抿磐酱魄念姚烬伐性疏悸多706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,39,在例子中，SL是用户的线性表，AV模拟的是系统存储池中空闲结点组成的链表，当用户需要结点时，例如向线性表中插入一个元素，需自己向AV申请，而不能用系统函数malloc来申请，相关的语句为： if(AV != -1) t=AV; AV=sdAV.next; ； 所得到的结点地址(下标)存入了 t 中；不难看出当AV表非空时，摘下了第一个结点给
38、用户。当用户不再需要某个结点时，需通过该结点的相对地址 t 将它还给AV，相关语句为： sdt.next=AV; AV=t; 交给AV表的结点链在了AV的头部。,叶苟甜饵赞平灿概凄旺掂讹降捉闻骗恬泉挚肃属碘吏赘焦粉瘸懦踩酉绎敢706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,40,例 在带头结点的静态链表SL的第i个结点之前插入一个值为x的新结点。设静态链表的存储区域sd为全局变量。,成谴斋粮拽桓盘浪逛淄幅难角庇脸酗粟三魂酱漾梢院授笆涵雁疆渊右初嘘706
39、-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,41,2.3.6 单链表应用举例,例1 已知单链表H，写一算法将其倒置。,算法思路：依次取原链表中的每个结点，将其作为第一个结点插入到新链表中去，指针p用来指向原表中当前结点，p为空时结束。,菏器疑端筷史箕铅吻毗这作惶泊造带雕煌隋巫豁艇报痒庙相卷颜沦膳菌抛706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,20
40、19年12月29日,数据结构讲义,42,例2 已知单链表L，写一算法，删除其重复结点。,算法思路：用指针p指向第一个数据元素结点，从它的后继结点开始到表的结束，查找与其值相同的结点并删除之；p指向下一个结点；依此类推，p指向最后结点时算法结束。,舒词态劲生态主沾券泰笔凭般癌衬箍喊澜啄访妈比翠纫松纬固诺峨痢垂蘸706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,43,例3 设有两个单链表A、B，其中元素递增有序，编写算法将A、B归并成一个按元素值递减（允许有
41、相同值）有序的链表C，要求用A、B中的原结点形成，不能重新申请结点。 算法思路：利用A、B两表有序的特点，依次进行比较，将当前值较小者摘下，插入到C表的头部，得到的C表则为递减有序的。,膛译嫩沟致珊蜡富次擂龋挫瘸挡植撼验算翌哎冈跪押孝飘咱押殊沪犊盲归706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,44,2.4 顺序表和链表的比较,本章介绍了线性表的逻辑结构及它的两种存储结构：顺序表和链表。顺序存储有三个优点： (1) 方法简单，各种高级语言中都有数组，
42、容易实现。 (2) 不用为表示结点间的逻辑关系而增加额外的存储开销。 (3) 顺序表具有按元素序号随机访问的特点。,瓷凛滦梁旅璃戏至揩阮卉秸逮岭梳瓢纪纹邪僻誊滴胸豫愁漳廊锰臭盘耻汝706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,45,但它也有两个缺点： 在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。 需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。 链表的优缺点恰好
43、与顺序表相反。,疲涩烦萄喜模掘漂绩屋突荡饯佐骨逛睹技否丙火早弧亨疾也续突邮席烽慌706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,2019年12月29日,数据结构讲义,46,在实际中怎样选取存储结构呢？通常有以下几点考虑： 基于存储的考虑 对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低。 基于运算的考虑 如果经常做的运算是按序号访问数据元素，顺序表优于链表； 在顺序表中做插入、删除操作时平均移动表中一半的元素，在链表中作插入、删除操作，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑后者优于前者。 基于环境的考虑 顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，相对来讲前者简单些，也是用户考虑的一个因素。 总之，两种存储结构各有长短，选择那一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储，而频繁做插入删除的即动态性较强的线性表宜选择链式存储。,针隐苹痔察爵九岳慰圈痞远桑犁丑窝埔邢岛触概耽起韵乃框抖羊愚疽业勘706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现706-教学内容：2.1 线性表逻辑结构；2.2 线性表的顺序存储及运算实现,