清华大学严蔚敏数据结构

《清华大学严蔚敏数据结构》由会员分享，可在线阅读，更多相关《清华大学严蔚敏数据结构（240页珍藏版）》请在金锄头文库上搜索。

1、更丈珍济脂姨闰妙判嘛枝狱铆刹浊疑朔伦俗廊忿蔽饲昔描列粪耶雏针箔恳清华大学严蔚敏数据结构清华大学严蔚敏数据结构数 据 结 构计算机系超阔匹芭典茎盏霞划掷醋州许潦揖搐二凰霄斜膛吉闹雾未烈绢裳堕荤日娘清华大学严蔚敏数据结构清华大学严蔚敏数据结构第一章 绪 论1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表示与实现1.4 算法和算法分 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 1.4.4 算法的存储空间的需求壤御樟媚疥慑候捣壁诉易肆捐迹圈漂椅帽祟尤抬纷拂夯丧獭玉郑室潜碧魏清华大学严蔚敏数据结构清华大学严蔚敏数据结构 第一章 绪 论l计算机是一门研究用

2、计算机进行信息表示和处理的科学。这里面涉及到两个问题：l 信息的表示 信息的处理 而信息的表示和组又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。竿议窥诺凸蛛开渡蘑空局孩奶虐广扛荐句参脏奈痕员烧警盛泊暂割瑚聊祝清华大学严蔚敏数据结构清华大学严蔚敏数据结构l 1.1什么是数据结构l 众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要

3、的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？先看以下几个例子。l 例1、电话号码查询系统l 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：l (a1，b1)(a2，b2)(an，bn)l其中ai，bi(i=1，2n) 分别表示某人的名字和对应的电话号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。蛮茎憎梳雕蝗嘛怔军趴噪咆捍撕暑编验哟私入蛊煎烧侧乱声峭灌篱香蛊翱清华大学严蔚敏数据结构清华大学严蔚敏数据结构l 算法的设计，依赖于计算机如何存储人的名字和对

4、应的电话号码，或者说依赖于名字和其电话号码的结构。l 数据的结构，直接影响算法的选择和效率。l 上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。 假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)， 1in 数据结构还要提供每种结构类型所定义的各种运算的算法。泛聪赠烷猾于亩组暗程嚼合询缅更昔爱诗肉黍检仗耙辜毫弯憨筹佰书立啪清华大学严蔚敏数据结构清华大学严蔚敏数据结构例2、图书馆的书目检索系统自动化问题例3、教师资料档案管理系统例4、多叉路口交通灯的管理问题 P3 通过以上几例可以直接地认为：数据结构就是研究数据的逻辑结构

5、和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。掩轻宙骇炬承庙咒怠协珐陈糯婿啮祁魁樱帜蹄褐丘垮坟笑频启垫姆剁彰攀清华大学严蔚敏数据结构清华大学严蔚敏数据结构l 1.2 基本概念和术语l数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。l数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。l 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。l数据对象(Data Object)：是性质相同的数据元素

6、的集合。是数据的一个子集。l数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。逾梦蜕荆翠豺晦戳腰熄甭珐揍姆过含母统睡样宪粤单驹条乘泅忠钠谩袁协清华大学严蔚敏数据结构清华大学严蔚敏数据结构l数据结构主要指逻辑结构和物理结构l 数据之间的相互关系称为逻辑结构。通常分为四类基本结构：l一、集合 结构中的数据元素除了同属于一种类型外，别无其它关系。l二、线性结构 结构中的数据元素之间存在一对一的关系。l三、树型结构 结构中的数据元素之间存在一对多的关系。l四、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。l 烬锹乞缚贫翟离镁源卖功腮憋除滨兰痕矗阵团

7、登顶赵恋道曳妻布巨煎味晦清华大学严蔚敏数据结构清华大学严蔚敏数据结构数据结构的形式定义为：数据结构是一个二元组： Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。例 复数的数据结构定义如下： Complex=(C，R)其中：C是含两个实数的集合C1，C2，分别表示复数的实部和虚部。R=P，P是定义在集合上的一种关系C1，C2。数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。旭魂颂郡猫物幼淄矿砚辈唾祁驶啤撒敌龚恨胚诸瓮苑狸薯紧孔熔瘁格歇峦清华大学严蔚敏数据结构清华大学严蔚敏数据结构l 数据对象可以是有限的，也可以是无限的。l数据结构不同于数据

8、类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。l抽象数据类型：一个数学模型以及定义在该模型上的一组操作。l抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。l用三元组描述如下：l（，）枢贷俯诌玉敖窃冷荡驮冲锤豫痹门埠佯比莽耸绵衰袋表误茧慌馒乞舶踩缎清华大学严蔚敏数据结构清华大学严蔚敏数据结构l数据结构在计算机中有两种不同的表示方法：l 顺序表示和非顺序表示l由此得出两种不同的存储结构：顺序存储结构和链式存储结构l顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。l链式存储结

9、构：在每一个数据元素中增加一个存放地址的指针（ ），用此指针来表示数据元素之间的逻辑关系。吗棠仅规奖痛凉司荔如舒脑于肿拎荫净唉牛羚秦糯亚佛遵流勉箱集缅辙监清华大学严蔚敏数据结构清华大学严蔚敏数据结构l数据类型：在一种程序设计语言中，变量所具有的数据种类。l例1、 在FORTRAN语言中，变量的数据类型有整型、实型、和复数型 l例2、在C语言中l数据类型：基本类型和构造类型l基本类型：整型、浮点型、字符型l构造类型：数组、结构、联合、指针、枚举型、自定义l数据对象：某种数据类型元素的集合。l例3、整数的数据对象是-3，-2，-1，0，1，2，3，l英文字符类型的数据对象是A，B，C，D，E，F，

10、荣树色鉴柞搜遏免五钥楚瓜奖椿浊虎坎似桐薛奸苦弛濒潘街援卉颈撬挨赵清华大学严蔚敏数据结构清华大学严蔚敏数据结构l 1.3 抽象数据类型的表示和实现lP11剪旬观掀馏定房涛垃怯郭巨媒湍配续或愈匹让搐泌配宁漫柬查撩某戍忧忆清华大学严蔚敏数据结构清华大学严蔚敏数据结构l 1.4 算法和算法分析l算法：是对特定问题求解步骤的一种描述l 算法是指令的有限序列，其中每一条指令表示一个或多个操作。l 算法具有以下五个特性：l（1）有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。l（2）确定性 算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。l（3）可行性

11、 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。卜峡凌彰拇啦妈撮湘沼例乙酪谅窟娩疯偶粘漆缠或竟澡臭懂每绩亢增街竹清华大学严蔚敏数据结构清华大学严蔚敏数据结构l4）输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。l5）输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。l1.4.2 算法设计的要求l评价一个好的算法有以下几个标准:l(1) 正确性(Correctness ) 算法应满足具体问题的需求。l(2)可读性(Readability) 算法应该好读。以有利于阅读者对程序的理解。 (3)健状性(Robustness)

12、算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。题扳疙沿斗挛塔动冗盒牧桂滤赞贿鞠质颠钩藕敝址翌颗寸贿继侥掳硅圆夹清华大学严蔚敏数据结构清华大学严蔚敏数据结构l(4)效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。l1.4.3 算法效率的度量l 对一个算法要作出全面的分析可分成两用人才个阶段进行，即事先分析和事后测试l事先分析 求出该算法的一个时间界限函数l事后测试 收集此算法的执行时间和实际占用空间的统计资料。l定义：如果存在两个正常数c和n0，对于所有的nn0，有f(n) cg(

13、n) l则记作 f(n)=O(g(n)狱母倚匀叠蛮傀棕惭埔酷废磋俯珠掘禾爵籍刨羊沤捌巴钝四砷挡希氮碱侣清华大学严蔚敏数据结构清华大学严蔚敏数据结构一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作 T(n)=O(f(n)称作算法的渐近时间复杂度。例、for(I=1，I=n;+I) for(j=1;j=n;+j) cIj=0; for(k=1;k=n;+k) cIj+=aIk*bkj; 乡骆毗恭沤睬饱跌暗羡补兹开掩耙喀谋好眉魂筛糊溅友同讹稍劣韦旧第猖清华大学严蔚敏数据结构清华大学严蔚敏数据结构l由于是一个三重循环，每个循环从1到n，则总次数为: nnn=n3l时间

14、复杂度为T(n)=O(n3)l频度：是指该语句重复执行的次数l例 +x;s=0;l将x自增看成是基本操作，则语句频度为，即时间复杂度为(1)l如果将s=0也看成是基本操作，则语句频度为，其时间复杂度仍为(1)，即常量阶。l例、for(I=1;I=n;+I)l +x;s+=x;l 语句频度为：2n其时间复杂度为：O(n)l 即时间复杂度为线性阶。浴域需零铡钻座纯咐郁菊聋弯忍振桑泛晨盯厅怂攒期砰预胳桶闪蛆川饵围清华大学严蔚敏数据结构清华大学严蔚敏数据结构l例、for(I=1;I=n;+I)lfor(j=1;j=n;+j)l +x;s+=x;l 语句频度为：2n2l其时间复杂度为：O(n2)l 即时

15、间复杂度为平方阶。l定理：若A(n)=a m n m +a m-1 n m-1 +a1n+a0是一个m次多项式，则A(n)=O(n m)证略。例for(i=2;i=n;+I) for(j=2;j=i-1;+j) +x;ai，j=x;菌儒噪冻弱各孰慨凤捧娠护慑偷攒袖孙痕组椰遥凤帚岁泣跃硫烙守巢产箕清华大学严蔚敏数据结构清华大学严蔚敏数据结构l语句频度为：l 1+2+3+n-2=(1+n-2) (n-2)/2l =(n-1)(n-2)/2l =n2-3n+2l 时间复杂度为O(n2)l 即此算法的时间复杂度为平方阶.l 一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由

16、一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。l 澄鬼砰睹灼臂伤缠柄束托豁厘制踢谗筒瓮卖宏杏健鸯哟寞氮幻褐飞快戌删清华大学严蔚敏数据结构清华大学严蔚敏数据结构l以下六种计算算法时间的多项式是最常用的。其关系为：l O(1)O(logn)O(n)O(nlogn)l O(n2)O(n3)l指数时间的关系为：l O(2n)O(n!)1 & change;-I)l l change=false;l for(j=0;jaj+1) l aj aj+1;l change=TUREl l 最好情况：0次l l 裕及晒饲裹已品答厦沏闽胳父蛊英雀蒋枚戏撼痴氧富逊棱贴寅稀行掌

17、苯诺清华大学严蔚敏数据结构清华大学严蔚敏数据结构l最坏情况：1+2+3+n-1l =n(n-1)/2l 平均时间复杂度为:O(n2)l1.4.4算法的存储空间需求l空间复杂度:算法所需存储空间的度量，记作:l S(n)=O(f(n) l其中n为问题的规模(或大小)聚菲万苍茨洒簿区俐妆晦灸肯篮或蛾臂咆呈糜砂严今昭寓祝剂糟喉案码悍清华大学严蔚敏数据结构清华大学严蔚敏数据结构 第二章 线性表l2.1 线性表的类型定义l2.2 线性表的顺序表示和实现l2.3 线性表的链式表示和实现l 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加葛邮淆漾檬努畜毖契竞噎

18、箩隧交栏仇再幌滋往伐朋响幽涡苏窿鲸砍望烧鸥清华大学严蔚敏数据结构清华大学严蔚敏数据结构l2.1 线性表的逻辑结构l线性表(Linear List) ：由n(n)个数据元素(结点)a1，a2， an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n0)记作：l (a1，a2，an) l这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。l例1、26个英文字母组成的字母表l （A，B，C、Z）l例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。l （6，17，28，50，92，188）押树陶蚂洼夫矽绞腆牌逢

19、放蓄灼刃席揭先岁穆蚜鼻涝嚎缉阑燃驭郴歹匹范清华大学严蔚敏数据结构清华大学严蔚敏数据结构例3、学生健康情况登记表如下：姓 名学 号性 别年龄 健康情况王小林790631 男 18 健康陈 红790632 女 20 一般刘建平790633 男 21 健康张立立790634 男 17 神经衰弱 . . .张速讹慷字插吠扩耿觅溅撰镁锨絮玖劲哀瓦漂塔哪厌敌良耍典荔勒瘩秉俩清华大学严蔚敏数据结构清华大学严蔚敏数据结构l例4、一副扑克的点数l （2，3，4，J，Q，K，A） 从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端

20、结点an，它没有直接后继，而仅有一个直接前趋a n-1；其余的内部结点ai(2in-1)都有且仅有一个直接前趋a i-1和一个直接后继a i+1。 线性表是一种典型的线性结构。l数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。l抽象数据类型的定义为：P19逛景铝局吕粤期弘痘盅咐篙黔拾陪淬魄惮键暴宅齐惜茧豢髓蚌喻匿屏顺辫清华大学严蔚敏数据结构清华大学严蔚敏数据结构 算法2.1l例2-1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=AB。 void union(List &La，List Lb) La-len=listlength(La); Lb-

21、len=listlength(Lb); for(I=1;I=lb-len;I+) getelem(lb，I，e); if(!locateelem(la，e，equal)listinsert(la，+la-en，e) l 篱所缸貉逆奋骗加馈愁后蚁吮匝楞宵赴胞棵存穷莱孪狭藩必荷糜源氦舒措清华大学严蔚敏数据结构清华大学严蔚敏数据结构l 算法2.2l例2-2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。l 此问题的算法如下： 盏狼戳顶恿顾眠辈空冀顺屉送脖揣诧藤垢撑葛拯眺罚卜阀诗理寸内剔积枕清华大学严蔚敏数据结

22、构清华大学严蔚敏数据结构void mergelist(list la，list lb，list &lc) initlist(lc); I=j=1;k=0; la-len=listlength(la); lb-len=listlength(lb); while(I=la-len)&(j=lb-len)埋作夜港奇疽言戒惨兔钝兰册渤皮渠铁颂寻冠婿棺恋秉昔涪等里玲园福惨清华大学严蔚敏数据结构清华大学严蔚敏数据结构l getelem(la，I，ai);getelem(lb，j，bj);l if(ai=bj)listinsert(lc，+k，ai);+I; elselistinsert(lc，+k，bj)

23、;+j; while(I=la-len) getelem(la，I+，ai);listinsert(lc，+k，ai); while(j=lb-len) getelem(lb，j+，bj);listinsert(lc，+k，bi); 黄悟狸待轿俱秒绒理驻利吏孟臀首披濒申翰衅轴嚣虑轰爪刮昨揽最亏臂艰清华大学严蔚敏数据结构清华大学严蔚敏数据结构l 2.2 线性表的顺序存储结构l2.2.1 线性表 把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。 假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第I

24、+1个数据元素的存储位置LOC( a i+1)和第i个数据元素的存储位置LOC(a I )之间满足下列关系： LOC(a i+1)=LOC(a i)+l 线性表的第i个数据元素ai的存储位置为： LOC(ai)=LOC(a1)+(I-1)*l 沟萎茂鲁跪迁稳岩畜拥傲诉糯融泪厘畴谱急辑蚁漠检旦窑烹检腕莫群膨险清华大学严蔚敏数据结构清华大学严蔚敏数据结构l由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。l # define ListSize 100l

25、typedef int DataType;l typedef strucl DataType dataListSize;l int length;l Sqlist;遥欧恩西境起丸趾七匆聪扭蠕狡授想鹅排挨赌酵匀艇祭拣仅者茨孟墒锹虹清华大学严蔚敏数据结构清华大学严蔚敏数据结构l2.2.2 顺序表上实现的基本操作 在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。 注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是l.dataI-1。 以下主要讨论线性表的插入和删除两种运算。 1、插入 线性表的插入运算是指在表的第I(1in

26、+1个位置上，插入一个新结点x，赌恤音吁滑欧匡绎扫拎阎壹篷爱恭离意困堪大准汀野邻穴默悄俗囊浸诣纱清华大学严蔚敏数据结构清华大学严蔚敏数据结构使长度为n的线性表 (a1，a i-1，ai，an) 变成长度为n+1的线性表 (a1，a i-1，x，ai，an) 算法2.3lVoid InsertList(Sqlist*L，DataType x，int I)l l int j;l if(Il.length+1)l printf(“Position error”);l return ERRORl 嚏库狸廖终搜羊滥狼及呕竿嘴岂鞋胺室猾湘乏嗓叮吮洼贷撬挛噬捧讨棺曙清华大学严蔚敏数据结构清华大学严蔚敏数据结

27、构l if(l.length=ListSize)l printf(“overflow”);l exit(overflow);l for(j=l.length-1;j=I-1;j-)l l.dataj+1=l.dataj;l l.dataI-1=x;l l.length+;l扑揖墙青父判床享出悟耪媳茵启臂靴靠路忌察觉勾织悸呆驴鸯箕肃伶豌韶清华大学严蔚敏数据结构清华大学严蔚敏数据结构l 现在分析算法的复杂度。l 这里的问题规模是表的长度，设它的值为。该算法的时间主要化费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置

28、有关。l当时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O（1）；l当=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，劳惦淘眠漾幂贾搞诺委缎缸蓖戚拙策狠衔毖芍快皿嫁双骆敢瘴流涸畏嘴市清华大学严蔚敏数据结构清华大学严蔚敏数据结构l其时间复杂度为O（n）。l 由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度 在长度为n的线性表中第i个位置上插入一个结点，令Eis(n)表示移动结点的期望值（即移动的平均次数），则在第i个位置上插入一个结点的移动次数为n-I+1。故 Eis(n)= pi(n-I+1) 不失一般性，假设在表中任何位置(

29、1in+1)上插入结点的机会是均等的，则 p1=p2=p3=p n+1=1/(n+1) 因此，在等概率插入的情况下， Eis(n)= (n-I+1)/(n+1)=n/2 语具捂刷浅瘟袄荒纤饭涤剃阁刮纹窃迭姿虎戒辈甄酮遇耗乱嗜玖簇迈拇罕清华大学严蔚敏数据结构清华大学严蔚敏数据结构 也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长 n较大时，算法的效率相当低。虽然Eis(n)中n的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为O(n)。 2、删除 线性表的删除运算是指将表的第i(1in)结点删除，使长度为n的线性表： (a1，a i-1，ai，a i+1，a

30、n) 变成长度为n-1的线性表 (a1，a i-1，a i+1，an)鹊弗届撮赐跟屈搏捉改乍愉容踞剖葛蚤笛羽铺会啦溉萎怕猿罪褂较零寥膏清华大学严蔚敏数据结构清华大学严蔚敏数据结构 Void deleteList(Sqlist*L，int I) int j; if(Il.length) printf(“Position error”); return ERROR for(j=i;jdata=ch; pnext=head; 犯峙癸怎集摊瓢缩宿蛰顷泼型酥务咀客汉啸癣酉饮舱锚底枝栅疗特歧盗邓清华大学严蔚敏数据结构清华大学严蔚敏数据结构 head=p; ch=getchar( ); return (he

31、ad); 犀唯匀侈婿唯载脊渍敛约陕别拼猫釉厩儿腥蜂媒梗涣毛唤握喳判缕宝音舵清华大学严蔚敏数据结构清华大学严蔚敏数据结构 listlink createlist(int n) int data; linklist head; listnode *p head=null; for(i=n;i0;-i) p=(listnode*)malloc(sizeof(listnode); scanf(%d，&pdata); pnext=head; head=p; 贝脱撩抡裤藤臂测舅员伎绕肄虑凯邑敌拽塞索汛兜胡埋嚼似筑零抢书豫泛清华大学严蔚敏数据结构清华大学严蔚敏数据结构 return(head); 2、尾插法

32、建表 头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。例：勋略叁称巍吉镀钓岗肠镣拳臣没槛办濒凯闽估辜甥世懦锋苹脂衙每驴捻仇清华大学严蔚敏数据结构清华大学严蔚敏数据结构 linklist creater( ) char ch; linklist head; listnode *p，*r; /(， *head;) head=NULL;r=NULL; while(ch=getchar( )!=n) p=(listnode *)malloc(siz

33、eof(listnode); pdata=ch; if(head=NULL) head=p; else 紫埠啊粱跨挟艳骆图匙惧婿玻莎刘猩鸽织汉烦蓟佣坚棚忆堑脱霉摊羹竞盐清华大学严蔚敏数据结构清华大学严蔚敏数据结构 rnext=p; r=p; if (r!=NULL) rnext=NULL; return(head); 说明：第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中， 漳榨司猛呆酣沿敲庙诲假提讳莲膊靴寥鉴瓮嫡公达骨廓骑迷转犊矢嘻颐励清华大学严蔚

34、敏数据结构清华大学严蔚敏数据结构 而其余结点的位置是在其前趋结点的指针域中。算法中的第一个if语句就是用来对第一个位置上的插入操作做特殊处理。算法中的第二个if语句的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表head是空表，尾指针r亦为空，结点*r不存在；否则链表head非空，最后一个尾结点*r是终端结点，应将其指针域置空。 如果我们在链表的开始结点之前附加一个结点，并称它为头结点，那么会带来以下两个优点： a、由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就驳汕晦娶叔玫抿留涣哦嘶部狐盒滩梭吮希稀絮竿痈声鸯序室斜归督毒揩煌

35、清华大学严蔚敏数据结构清华大学严蔚敏数据结构 和在表的其它位置上的操作一致，无需进行特殊处理；b、无论链表是否为空，其头指针是指向头结点 在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。 其算法如下：linklist createlistr1( ) char ch; linklist head=(linklist)malloc(sizeof(listnode); listnode *p，*r 辟木城椿泡暗宽司邓笋谋惭铡彝蚁莫非福裂唐闻装盯苛瑞幅朗烛拧晶袍粒清华大学严蔚敏数据结构清华大学严蔚敏数据结构 r=head; while(ch=getchar( )!=n p=

36、(listnode*)malloc(sizeof(listnode); pdata=ch; pnext=p; r=p; rnext=NULL; return(head); 调饼青盂徒倡肤进梢尧贾随谅萌掇耶蛀备啄网终斧抉诉适痢腿套菇鸥诽篓清华大学严蔚敏数据结构清华大学严蔚敏数据结构上述算法里动态申请新结点空间时未加错误处理，可作下列处理： p=(listnode*)malloc(sizeof(listnode) if(p=NULL) error(No space for node can be obtained); return ERROR; 以上算法的时间复杂度均为O(n)。蛮档要辗嚣查局控薯

37、毋葛吭核班蚁拖抄是烫姓么胳均高扎悄髓屹刨制澈考清华大学严蔚敏数据结构清华大学严蔚敏数据结构二、查找运算 1、按序号查找 在链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。 设单链表的长度为n，要查找表中第i个结点，仅当1in时，i的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第0 个结点，其算法如下：刚说渣哟暗浮蓉肪孤熙悦芯害要们枚续褥骸晰趁就乞做擂跺奈攫蚊逐撮腾清华大学严蔚敏数据结构清华大学严蔚敏数据结构Listnode * getnod

38、e(linklist head ， int i) int j; listnode * p; p=head;j=0; while(pnext & jnext; j+; if (i=j) return p;妄封酌捕庆性拙闻出孙圭汤畦濒宾呀疏椭思祝腮点暑焉茸纬瞅魁吼档蒋丰清华大学严蔚敏数据结构清华大学严蔚敏数据结构 else return NULL; 2、按值查找 按值查找是在链表中，查找是否有结点值等于给定值key的结点，若有的话，则返回首次找到的其值为key的结点的存储位置；否则返回NULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值key作比较。其算法如下：盅臃遣穗辙够取舒在惶缔鸽

39、跨硷剁怂问萎召亚育喝嫂竟菲间忆平缉绎玉杀清华大学严蔚敏数据结构清华大学严蔚敏数据结构Listnode * locatenode(linklist head，int key) listnode * p=headnext; while( p & pdata!=key) p=pnext; return p; 该算法的执行时间亦与输入实例中的的取值key有关，其平均时间复杂度的分析类似于按序号查找，也为O(n)。株挪貉峡误钳侩都骏疏曼扦铀佯汀泞京埋票总三政灯孕罩令阁妄肝豁戍氰清华大学严蔚敏数据结构清华大学严蔚敏数据结构三、插入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-

40、1与ai之间。因此，我们必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*p，并令结点*p的指针域指向新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化，插入过程如：街屑浇痛昌短弊韵爬园沏型就扫硬斑辣手芹奋讯蔚凸周庆焕比奋慰振兽简清华大学严蔚敏数据结构清华大学严蔚敏数据结构具体算法如下： void insertnode(linklist head，datetype x，int i) listnode * p，*q; p=getnode(head，i-1); if(p=NULL) error(position error); q=(list

41、node *)malloc(sizeof(listnode); qdata=x; qnext=pnext; pnext=q; 滋柴粤喻都剂召瞳蘑茅脏升祝泻丝植增狗藩谭月舵绸摊穷捷抖志药音袍癸清华大学严蔚敏数据结构清华大学严蔚敏数据结构 设链表的长度为n，合法的插入位置是1in+1。注意当i=1时，getnode找到的是头结点，当 i=n+1时，getnode找到的是结点an。因此，用i-1做实参调用getnode时可完成插入位置的合法性检查。算法的时间主要耗费在查找操作getnode上，故时间复杂度亦为O(n)。四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在

42、其直接前趋结点a a i-1的指针域next中，所以我们必须首先找到 辑粒狙匀脊氛悯迎歼笋捉编狰揩诡袒道利类惜憎锦逼喧告乞彰隐磋成奠肺清华大学严蔚敏数据结构清华大学严蔚敏数据结构 a i-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间，将其归还给“存储池”。此过程为：契涟明剔役咋篆仍瓷韵猴界萌肄锹摘万疆州禄摈熬离胞狄尖葬瑰凄甩拨惭清华大学严蔚敏数据结构清华大学严蔚敏数据结构具体算法如下： void deletelist(linklist head， int i) listnode * p， *r; p=getnode(head，i-1); i

43、f(p= =NULL | pnext= =NULL) return ERROR; r=pnext; pnext=rnext; free( r ) ; 损极贤峭舟吕绚洁栗魔狈乏哨羌智裹椅勺悯哆逐突辊右健拾掐率晒貌踊脑清华大学严蔚敏数据结构清华大学严蔚敏数据结构 设单链表的长度为n，则删去第i个结点仅当1in时是合法的。注意，当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋*p存在并不意味着被删结点就一定存在，仅当*p存在（即p!=NULL）且*p不是终端结点 （即pnext!=NULL）时，才能确定被删结点存在。 显然此算法的时间复杂度也是O(n)。

44、从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指针。课铝犁废宛闯啮焰苔怔围荔安盏笼梧讲渔猎簇携零踊真伶嘛街峡藏降旋茬清华大学严蔚敏数据结构清华大学严蔚敏数据结构2.3.2 循环链表 循环链表时一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。单循环链表：在单链表中，将终端结点的指针域NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。 为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示：采揖癌急章地射租钩厢涅借恐曙铬晤翅伤

45、累搪兰狱链寺荣踪概宫唱账牢证清华大学严蔚敏数据结构清华大学严蔚敏数据结构 a1 an .head 非空表 空表 在用头指针表示的单链表中，找开始结点a1的时间是O(1)，然而要找到终端结点an，则需从头指针开始遍历整个链表，其时间是O(n)蔷涅苍价律旱泵讲铱冠援肉裂揪撕争今揩绥沪幻堕储冲午签郝词隧谜贰粘清华大学严蔚敏数据结构清华大学严蔚敏数据结构 在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便.如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是(rearnext) next和rear，显然，查找

46、时间都是O(1)。因此，实际中多采用尾指针表示单循环链表。 由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或pnext是否为空，而是判断它们是否等于某一指定指针，如头指什或尾指针等。每硬值矛北颊嘴粕鳞霹损她旺荔哄一龙混掉卧核波闭吗恭粗慢妮肾粒匈揖清华大学严蔚敏数据结构清华大学严蔚敏数据结构例、在链表上实现将两个线性表(a1，a2，a3，an)和(b1，b2，b3，bn)链接成一个线性表的运算。 linklist connect(linklist heada，linklist headb) linklist p=headanext; headanext=

47、(headbnext)next free(headbnext); headbnext=p; return(headb); 激矗崎辉隐朔腺直弥刹冉兴螺抖伶娃擎晓潦惶沃送脊眩趾哦粥烃高器颧抄清华大学严蔚敏数据结构清华大学严蔚敏数据结构2.3.3双链表 双向链表(Double linked list):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为： typedef struct dlistnode datatype data; struc dlistnode *prior，*next; dlistnode; type

48、def dlistnode * dlinklist; dlinklist head;梗师宣庭槐昆嚷恫檄罕秆琐标详衣毅轮富入羹畔针恨狂哪滴削斟芥哎幅而清华大学严蔚敏数据结构清华大学严蔚敏数据结构 和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向链表。 设指针p指向某一结点，则双向链表结构的对称性可用下式描述： (pprior)next=p=(pnext)prior 即结点*p的存储位置既存放在其前趋结点*(pprior)的直接后继指针域中，也存放 在它的后继结点*(pnext)的直接前趋指针域中。笺

49、皮凋恰院摄酋赡亏晃鼓栽上烛习胸肌谜趁蛙鞋埔坏渡耻屎梳贴孝枯糟硅清华大学严蔚敏数据结构清华大学严蔚敏数据结构双向链表的前插操作算法如下： void dinsertbefor(dlistnode *p，datatype x) dlistnode *q=malloc(sizeof(dlistnode); qdata=x; qprior=pprior; qnext=p; ppriornext=q; pprior=q; 楼恐括虎份双心荷窖萎脑哲加围专酞屿捕炎阿杰常柏等望计炸瑚磋呼级豹清华大学严蔚敏数据结构清华大学严蔚敏数据结构 void ddeletenode(dlistnode *p) ppriorn

50、ext=pnext; pnextprior=pprior; free(p); 注意：与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算是法的时间复杂度均为O(1)。兆涪激氰蔫序脉摄览饥暇俄怒揣棘霜屈橙揩炽驹颖号麓嫡谬裕稼琅虏砸聊清华大学严蔚敏数据结构清华大学严蔚敏数据结构 第三章 栈和队列3.1 栈 3.1.1 抽象数据类型栈的定义 3.1.2 栈的表示和实现3.2 栈的应用举例 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.4 行编辑程序 3.2.5 迷宫求解 3.2.5 表达式求值锯傅窃脓肚愁秦吁喳啮乓厉勾搓丸悔幕末青系周浚釉秒拣贬槽

51、田患茁凌记清华大学严蔚敏数据结构清华大学严蔚敏数据结构 3.1.1 栈3.1.1 栈的定义及基本运算 栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。 假设栈S=(a1，a2，a3，an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。层幌写浇冠史俐虐琐甄摄氛饰褒肾巷逞凑贷励贡途卡干丫蘑倾吐你芽噶士清华大学严蔚敏数据结构清华大学严蔚敏数据结构3

52、.1.2 顺序栈 由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top许掉育蹭摹奶煮分蛔悼篱古乡逼川汪那弥站膨宏呢泛哭藕臂噶豫晴船辙热清华大学严蔚敏数据结构清华大学严蔚敏数据结构例、一叠书或一叠盘子。 栈的抽象数据类型的定义如下：P44 a n a n-1 a2 a1栈顶 栈底敛舱板冕瞻挛拾踢耳拦鲜朝收邢员菠骆鼓柒签匣督伐容咖塔品哈傣运轧舞清华大学严蔚敏数据结构清华大学严

53、蔚敏数据结构top7 6 5 4 3 2 1 -1成镑岳此揪醚婚字直答猫枚母恨檄冯钠哥贬胎侄榷毋汤战缅峪骸蛛类菜史清华大学严蔚敏数据结构清华大学严蔚敏数据结构来指示当前栈顶的位置，通常称top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。顺序栈的类型定义如下： # define StackSize 100 typedef char datatype; typedef struct datatype datastacksize; int top; seqstack; 痕终扣牲被曹狠秆九茵豹税檬撞溉再珐颊硷忽搔趋换嚣抛握乡颈贞铲缮乌清华大学严蔚敏数据结构清华大

54、学严蔚敏数据结构 设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即sdata0是栈底元素，那么栈顶指针stop是正向增加的，即进栈时需将stop加1，退栈时需将stop 减1。因此，stoptop =stacksize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。咎掳驾敢代庚拈拥圣售拭腥摊纫峡坏积祁雄弱慷溜颇时羽回席帧嗓帘编戊清华大学严蔚敏数据结构清华大学严蔚敏数据结构3

55、、判断栈满 int stackfull(seqstack *s) return(stop=stacksize-1); 4、进栈 void push(seqstack *s，datatype x) if (stackfull(s) error(“stack overflow”); sdata+stop=x; 佑纸呀柿渺秒那感靡颧渭兽影矮删振砍的崎羊晾扯禁卯浸堵祖肛医肋辉贪清华大学严蔚敏数据结构清华大学严蔚敏数据结构1、置空栈 void initstack(seqstack *s) stop=-1; 2、判断栈空 int stackempty(seqstack *s) return(stop=-1

56、); 她桃抚郡黎股正依盟渗贬镰闭逢匪毅萝吨谁诛赂叮砸厕东俗鳖牺浦幂淤尹清华大学严蔚敏数据结构清华大学严蔚敏数据结构5、退栈 datatype pop(seqstack *s) if(stackempty(s) error(“stack underflow”); x=sdatatop; stop-; return(x) /return(sdatastop-); 役烤火珍绥壬飞荐蓑屋敦亿籽暮桨契萨垮漂倚彩史蛾可把灼惜肮侮藉竭坑清华大学严蔚敏数据结构清华大学严蔚敏数据结构6、取栈顶元素 Datatype stacktop(seqstack *s) if(stackempty(s) error(“st

57、ack is enpty”); return sdatastop; 蜂泻沧揭赘其哲链胆侯樊丛垣蛛循镀铂彩脂旧匪裂没浆将歉涝饯歉靳仍蓑清华大学严蔚敏数据结构清华大学严蔚敏数据结构3.1.3 链栈 栈的链式存储结构称为链栈，它是运算是受限的单链表，克插入和删除操作仅限制在表头位置上进行.由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。 链栈的类型说明如下： typedef struct stacknode datatype data struct stacknode *next stacknode;潮熟恰耿田叔腾草巷落砒孜希唁仙熊握揽纫瓶抑胖于箭封堕滁及

58、动痹兑够清华大学严蔚敏数据结构清华大学严蔚敏数据结构 Void initstack(seqstack *p) ptop=null; int stackempty(linkstack *p) return ptop=null; 埃织峰惫画妖可劝恬抹护抨垢短谩读礁朋莎贤唆名道捂膨呀隘褒贸赠钦位清华大学严蔚敏数据结构清华大学严蔚敏数据结构lVoid push(linkstack *p,datatype x) stacknode *q q=(stacknode*)malloc(sizeof(stacknode); qdata=x; qnext=ptop; ptop=p; 窒十渝恼播滥浦肾们咱恶奖赫克柜

59、荧闯拜受翼净果哇流毗掳莎但滴涌涧汲清华大学严蔚敏数据结构清华大学严蔚敏数据结构Datatype pop(linkstack *p) datatype x; stacknode *q=ptop; if(stackempty(p) error(“stack underflow.”); x=qdata; ptop=qnext; free(q); return x; 都郝啤癸篇后扰儡低愿垮曼掺貌鸵没抓兴晶驹污仍痈描补夫鼎猩鸭秽摩长清华大学严蔚敏数据结构清华大学严蔚敏数据结构 datatype stack top(linkstack *p) if(stackempty(p) error(“stack i

60、s empty.”); return ptopdata; 三又屈害绰瞄傣愁垮聪节戴姑颧相便胖挣绝珐赚晚疲槛柑魂召挞尹即酱菏清华大学严蔚敏数据结构清华大学严蔚敏数据结构 3.2 栈的应用举例 由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。 3.2.1 数制转换 十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div为整除运算,mod为求余运算) 例如 (1348)10=(2504)8，其运算过程如下：诫乖妆绿牛某壹敬测铱扛硒吟芭赛完医瞄祥眨绊辊

61、逞蹲全掇菌报熬甩锭易清华大学严蔚敏数据结构清华大学严蔚敏数据结构 n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2诲皆胸兰物甲膀蚜问舷些瘤呵屯臭银洲让焚微笋友商帛吕讳宦尾簧黄样蛤清华大学严蔚敏数据结构清华大学严蔚敏数据结构 void conversion( ) initstack(s); scanf (“%”,n); while(n) push(s,n%8); n=n/8; while(! Stackempty(s) pop(s,e); printf(“%d”,e); 峙嚷雇栋碎宣扶浑劫版钱邵陨茬济剁剩欧忆浴冬币澎酌迪哺仗活威马廊揖清华大学严

62、蔚敏数据结构清华大学严蔚敏数据结构3.2.2 括号匹配的检验 假设表达式中充许括号嵌套,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例： （）（） （）3.2.3 行编辑程序 在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。 铅及兢折恕铺船唱玲软击胁湾尿憨如轰晕妙矮剖迄禹疼粤夸肖班韩儡浓举清华大学严蔚敏数据结构清华大学严蔚敏数据结构行编辑程序算法如下: void lineedit( ) initstack(s); ch=gether( ); while(ch!=eof) while(ch!=e

63、of & ch!=n) switch(ch) case # : pop(s,c); case : clearstack(s); default : push(s,ch); 噪锨蕉笺论而熊掠诊砌硒桔玻愤韧昭齐魁觉沧扶沸畸烁茂坝始摸怜窘陛逮清华大学严蔚敏数据结构清华大学严蔚敏数据结构 ch=getchar( ); clearstack(s); if(ch!=eof) ch=gethar( ); destroystack(s); 款菲焚融氏厚掘鉴棒睁挑辗烁改琅峭锄脓染揽烷簿委寂邢绒邓友愈塌径负清华大学严蔚敏数据结构清华大学严蔚敏数据结构3.2.4 迷宫求解 入口出口宿兢刮钉淆万宛僵靳端虑押黄诺盆旁胁

64、眼寝阿作吾欺官泻知螺殴歇惋怔模清华大学严蔚敏数据结构清华大学严蔚敏数据结构3.4 队列3.4.1 抽象数据类型队列的定义 队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,an ，也

65、就是说队列的修改是依先进先出的原则进行的。滇棒贫乒娄夜赂蚂砒滔伤灾创戏护紫婆敞祟毋头侯病沏节诞捅柔鲜温量着清华大学严蔚敏数据结构清华大学严蔚敏数据结构下图是队列的示意图： a1a2an出队入队队头队尾队列的抽象数据定义见书593.4.2 循环队列队列的顺序表示和实现队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队陈抬赌粹盯闻珐墨施赃语吓掀还踩喝厚豌嘉批氖走赖拟赞塘揽母凭荤仇涉清华大学严蔚敏数据结构清华大学严蔚敏数据结构列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置，

66、它们的初始值地队列初始化时均应置为。入队时将新元素插入所指的位置，然后将加。出队时，删去所指的元素，然后将加并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。 0 1 2 3FrontrearabcFront rear (a)队列初始为空（b）A,B,C入队卫稻卷邪披端雪终淤饺跳傍轿叠缝疫懈蜘渤将延惺锭劳藉彝牡鳖即烛薯租清华大学严蔚敏数据结构清华大学严蔚敏数据结构 b c front rear front rear （c) a出队 (d) b,c出队，队为空和栈类似，队列中亦有上溢和下溢现象。此外，顺序队列中还存在“假

67、上溢”现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。诚韶刁冕旱瓢抵魏尺商张敦腑悟竿沥痞洁另酵拱讣蜀绥零稀堆秀溅尽驰玛清华大学严蔚敏数据结构清华大学严蔚敏数据结构为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（Circular Queue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（Que

68、ueSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为： if(I+1=QueueSize) i=0; else i+; 利用模运算可简化为： i=(i+1)%QueueSize嫌颧俯押奖搁厄彰粒姥松谣狠侥晾扣躺墨很穆已数护磐础僻根沉收凶瓮选清华大学严蔚敏数据结构清华大学严蔚敏数据结构 显然，因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。 如图所示：由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过fron

69、t=rear来判断队列“空”还是“满”。 解决此问题的方法至少有三种： 其一是另设一个布尔变量以匹别队列的空和满；其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；腺叉绢挫摩时误味瘩荷谓黎蒋菱轩桥诉封蛛唇予飘击顷凶悯钙瓜方来厩滓清华大学严蔚敏数据结构清华大学严蔚敏数据结构其三是使用一个计数器记录队列中元素的总数（实际上是队列长度）。下面我们用第三种方法实现循环队列上的六种基本操作，为此先给出循环队列的类型定义。l #define QueueSize 100l typedef char DataType;l t

70、ypedef Structl int front;l int rear;l int count;l datatype dataqueuesizel cirqueue;鹿莫甩壕旺拧秃氯七苑骡泛菱霓亏障微耍牢虫及豆叶西妖摄溺宠扯漱瀑疹清华大学严蔚敏数据结构清华大学严蔚敏数据结构（1）置空队 void initqueue(cirqueue *q) qfront=qrear=0; qcount=0; （2）判断队空 int queueempty(cirqueue *q) return qcount=0; （3）判断队满 int queuefull(cirqueue *q) return qcount=

71、queuesize; 饱逛鞘皑漂越碰莱兆衅坏祝增毡歇蜂估诡哎狡籽盗央副烟颤嫌彭泊相念和清华大学严蔚敏数据结构清华大学严蔚敏数据结构（4）入队 void enqueue(cirqueue *q,datatype x) if(queuefull(q) error(“queue overflow”); qcount+; qdataqrear=x; qrear=(qrear+1)%queuesize; 殖泊首敷谷梨耻翻髓韭钡这仙戊恨赢晦寇挞姆翰堂挫蜕斑租闽羚耗婪信蓉清华大学严蔚敏数据结构清华大学严蔚敏数据结构（5）出队 datatype dequeue(cirqueue *q) datatype te

72、mp; if(queueempty(q) error(“queue underflow”); temp=qdataqfront; qcount-; qfront=(qfront+1)%queuesize; return temp; 暮寥赫类韩仇米渠死县睡誓杠苛裙荔骗佯揪肥航妹汹亨先畔扦悦铅岗阀昌清华大学严蔚敏数据结构清华大学严蔚敏数据结构（6）取头指针 datatype queuefront(cirqueue *q) if(queueempty(q) error(“queue is empty.”); return qdataqfront; 舜幻玩膳读矫式瀑裤撇跳灰竿辜痴翰瓜僳紧咋席礁淘思内雇

73、聂鸿早倒美回清华大学严蔚敏数据结构清华大学严蔚敏数据结构l3.4.3 链队列l 队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由一个头指针唯一确定。和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型LinkQueue定义为一个结构类型：l typedef struct queuenodel datatype data;l struct queuenode *next;l queuenode;钞蛋声合蜗空扦朽消衔诫柿棍俗歪扑溢吨酪收芥蹋勉遏胀乱澎夯码浙

74、光唯清华大学严蔚敏数据结构清华大学严蔚敏数据结构 typedef struct queuenode *front; queuenode *rear; linkqueue;下面给出链队列上实现的基本运算： void initqueue(linkqueue *q) qfront=qrear=null; 争孙腋汗欢敦齿蜒雾晒袱驭皿驰曲架棕痴翱扳傅咕舌奉秩稚蚕郁避君递柿清华大学严蔚敏数据结构清华大学严蔚敏数据结构 int queueempty(linkqueue *q) return qfront=null &qrear=null; void enqueue(linkqueue *q,datatype

75、 x) queuenode *p p=(queuenode * )malloc(sizeof(queuenode); pdata=x; pnext=null; if(queueempty(q) qfront=qrear=p; 匝韧苹娜嚣炳匈理撕拾罪俏痛拍祝胖朋凯蹭亨杂色馏成赣惑孜荆宅土维凌清华大学严蔚敏数据结构清华大学严蔚敏数据结构 else qrearnext=p; qrear=p; Datatype dequeue(linkqueue *q) datatype x; queuenode *p客馒坊嘻剥核禾彬氮妒袜牵拿幅左噪瞅厅廉锅卫引忽挝瞅皋筑卞胰李稠支清华大学严蔚敏数据结构清华大学严蔚敏

76、数据结构 if(queueempty(q) error(“queue underflow”); p=qfront; x=pdata; qfront=pnext; if(qrear=p) qrear=null; free(p); return x; 程九艇笼曳势雄钨倾噎坦雪妖场颓邀倦造婆汀恋箱桔崭身古诛卷晒歧灼核清华大学严蔚敏数据结构清华大学严蔚敏数据结构 datatype queuefront(linkqueue *q) if(queueempty(q) error(“queue is empty.”); return qfrontdata; 注意：在出队算法中，一般只需修改队头指针。但当原队

77、中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。裤薄厅钡烛绦芦未诧诀匪耙俩都妖啊至节区培微扩雕窖美水怖基萄欺翔魁清华大学严蔚敏数据结构清华大学严蔚敏数据结构 习题1、设将整数以万计、2、3、4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下有问题：（1）若入栈次序为push(1)，pop()，push(2，push(3)，pop()，pop( )，push(4)，pop( )，则出栈的数字序列为什么？（2）能否得到出栈序列车员423和平共处五项原则432？并说明为什么不能得到或如何得到。（3）请分析1、2、3、4的24种排

78、列中，哪些序列可以通过相应的入出栈得到。2、链栈中为何不设头指针？3、循环队列的优点是什么？如何判断它的空和满？滨阳景桅耕衡翌险站叹哮栽马料益粮睁嚏芜跟谨竖赐玫王欧咸莲缀猎突肺清华大学严蔚敏数据结构清华大学严蔚敏数据结构4、设长度为n的链队列用单循环链表表示，若只设头指针，则怎样进行入队和出队操作；若只设尾指针呢？5、利用栈的基本操作，写一个返回栈s中结点个数的算法int stacksize(seqstack s)，并说明s为何不用作为指针参数？6、利用栈的基本操作，写一个将栈中所有结点均删除算法，并说明S为何要作为指针参数？7、用第二种方法，即少用一个元素空间的方法来区别循环队列的队空和队满

79、，试设计置空队、判队空、判队满、出队、入队及取队头元素等六个基本操作。蘑旺搐泻抽最畸笼嫉忘赋挛沦翁灌功贪俩淘炽彻叮米绚咽剐诺痪坪醚焕鼻清华大学严蔚敏数据结构清华大学严蔚敏数据结构8、假设循环队列只设rear和quelen来分别指示队尾元素的位置和队中元素的个数，试给出判断此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头指针。9、指出下列程序段的功能是什么？ (1) void demo1(seqstack *s) int I;arr64;n=0; while (!stackempty(s) arrn+=pos(s); for(I=0;n;I+) push(s,arrI);

80、(2) void demo2(seqstack *s,int m) seqstack t; int i; initstack(t);砒但牧洪搐御鄙棒箱褥龄判蝇盘沧凌规谜龄男诽课嚼含嘿驼潭诸儡盖响逃清华大学严蔚敏数据结构清华大学严蔚敏数据结构while(! Stackempty(s) if(I=pop(s)!=m) push(t,I);While(! Stackempty(t) i=pop(t); push(s,I);痊探账娄斧叁饯氛胰匪羊炳线鹅莫棠宛业塞讽夺劫赛寐罗婆裙随蹭幕晦偏清华大学严蔚敏数据结构清华大学严蔚敏数据结构 第四章 串l4.1 串类型的定义l4.2 串的表示和实现 4.2.1

81、定长顺序存储表示 4.2.2 堆分配存储表示 4.2.3 串的块链存储表示次季畴几痘征的班炭迈藤启青屑饲洗箭匀贡绦烹拈岁迢壕尸簧搜陨推住歧清华大学严蔚敏数据结构清华大学严蔚敏数据结构 4.1 串类型的定义一、串和基本概念 串(String)是零个或多个字符组成的有限序列。一般记作S=“a1a2a3an”，其中S 是串名，双引号括起来的字符序列是串值；ai(1in)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。长度为零的串称为空串(Empty String)，它不包含任何字符。 通常将仅由一个或多个空格组成的串称为空白串(Blank String) 注意：空串和空白串的不同，例

82、如“ ”和“”分别表示长度为1的空白串和长度为0的空串。雁怒席森坚动摈镭无舷霍哲才鸳诀印缮喝即土陶涯冬噪贷耶拄塌析财乖文清华大学严蔚敏数据结构清华大学严蔚敏数据结构串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。例如，设A和B分别为 A=“This is a string” B=“is”则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，称B在A中的序号（或位置）为3 特别地，空串是任意串的子串，任意串是其自身的子串。 通常在程序中使用

83、的串可分为两种：串变量和串常量。串常量和整常数、实常数一样，在邪内数辉运湘闭满矛制叉辩图是道窗咸啤羌惮司秆代源莲袁敲姬磋用简镭清华大学严蔚敏数据结构清华大学严蔚敏数据结构程序中只能被引用但不能不能改变其值，即只能读不能写。通常串常量是由直接量来表示的，例如语句Error(“overflow”)中“overflow”是直接量。但有的语言允许对串常量命名，以使程序易读、易写。如C+中，可定义 const char path=“dir/bin/appl”;这里path是一个串常量，对它只能读不能写。串变量和其它类型的变量一样，其取值是可以改变的。二、串的抽象数据定义 串的抽象数据类型定义台书P71桔

84、肇兹匠纂替挠申克郑例粕敌语黎许攒段翱哈五电勺谱椽最悦堵毖挛蒲隙清华大学严蔚敏数据结构清华大学严蔚敏数据结构三、串的基本操作 对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。下面仅介绍几种在C语言中常用的串运算，其它的串操作见的文件。 定义下列几个变量： char s120=“dirtreeformat”,s220=“file.mem”; char s330,*p; int result;(1)求串长(length) int strlen(char s); /求串的长度 例如：printf(“%d”,strlen(s1); 输出13栏瓜尔蒸鼓及氖宽冯金瓶挝董钓瘤畔捣该威废踢斗

85、钟杠姐诚笺屁描饯校量清华大学严蔚敏数据结构清华大学严蔚敏数据结构（2）串复制(copy) char *strcpy(char to,char from); 该函数将串from复制到串to中，并且返回一个指向串to的开始处的指针。 例如：strcpy(s3,s1); /s3=“dirtreeformat”(3)联接(concatenation) char strcat(char to,char from) 该函数将串from复制到串to的末尾，并且返回一个指向串to的开始处的指针。 例如：strcat(s3,”/”) strcat(s3,s2); /s3=“dirtreeformat/file.

86、mem”鸯被梗巢瑞大兑袍匝擎校啡爽欲十梳诡慨螟拷肾犹青喳逛稻骡念邵全惮盘清华大学严蔚敏数据结构清华大学严蔚敏数据结构(4)串比较（compare) int strcmp(chars1,char s2); 该函数比较串s1和串s2的大小，当返回值小于0，等于0或大于0时分别表示s1s2 例如：result=strcmp(“baker”,”Baker”) result0 result=strcmp(“12”,”12”); result=0 result=strcmp(“Joe”,”Joseph”); result0（5）字符定位(index) char strchr(char s,char c);

87、 该函数是找c在字符串中第一次出现的位置，若找到则返回该位置，否则返回NULL。 例如：p=strchr(s2,”.”); p 指向“file”之后的位置 if(p) strcpy(p,”.cpp”); s2=“file.cpp”飞闪的袋椿歹典选各网奥褂贾捏胶缎旧化痹佯券钒芹琐县佣口令帆闭曳神清华大学严蔚敏数据结构清华大学严蔚敏数据结构 上述串的操作是最基本的，其中后四个还有变种形式：strncpy，strncat，strncmp，strnchr。串的其余操作可由这些基本操作组合而成。 例1、求子串 求子串的过程即为复制字符序列的过程，将串S中的第pos个字符开始长度为len的字符复制到串T中

88、。 void substr(string sub,string s,int pos,int len) if(posstrlen(s)-1 | len0) n=strlen(s); m=strlen(t); i=pos; while(in-m+1) substr(sub,s,i,m); if(strcmp(sub,t)!=0) +i; else return(i); return(0); 茸葱舶洱陶匡圈言拎谗轿攻踩峭痒鸵澄瞥隔溪侗风善培匀完惰滑溅萝氢奠清华大学严蔚敏数据结构清华大学严蔚敏数据结构 4.2 串的表现和实现 因为串是特殊的线性表，故其存储结构与线性表的存储结构类似。只不过由于组成串的

89、结点是单个字符。串有三种机内表示方法，下面分别介绍。4.2.1定长顺序存储表示 定长顺序存储表示,也称为静态存储分配的顺应表。它是用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出： #define maxstrlen 256 typedef char sstringmaxstrlen; sstring s; /s是一个可容纳255个字符的顺序串。蒂你拎总臭津锭蔗于虫盔甸咨主墓琢睦饼滁毛鹊迪蛔虱堵矢钓鲁妈忘艇讹清华大学严蔚敏数据结构清华大学严蔚敏数据结构 一般可使用一个不会出现在串中的特殊字符在串值的尾部来表示串的结束。例如，C语

90、言中以字符0表示串值的终结，这就是为什么在上述定义中，串空间最大值maxstrlen为256，但最多只能存放255个字符的原因，因为必须留一个字节来存放0字符。若不设终结符，可用一个整数来表示串的长度，那么该长度减1的位置就是串值的最后一个字符的位置。此时顺序串的类型定义和顺序表类似： typedef struct char chmaxstrlen; int length; sstring; /其优点是涉及到串长操作时速度快。 叙苇嫩秸狱委嘉擂吁迫符究飞爷怜乃泵贞汕芳潮映赚序呻吾典锐檬乍纬存清华大学严蔚敏数据结构清华大学严蔚敏数据结构 4.2.2堆分配存储表示 这种存储表示的特点是，仍以一组地

91、址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表。在C语言中，利用和等动态存储管理函数，来根据实际需要动态分配和释放字符数组空间。这样定义的顺序串类型也有两种形式。 typedef char *string; /c中的串库相当于此类型定义 typedef struct char *ch; int length; hsring;戮带跑疤谈舰嘲涧叁妮款季唯淮毛聂伯袜绑肌霞拄抠慰打陵宋聚绊诽巾鬃清华大学严蔚敏数据结构清华大学严蔚敏数据结构 status sinsert(hstring s,int pos,hstring t) if(po

92、ss.length+1) return error; if(t.length)if(!(s.ch=(char*)realloc(s.ch,(s.length+t.length)*sizeof(char) exit(overflow); for(i=s.length-1;ipos-1;-i) s.chI+t.length=s.chi; s.chpos-1.pos+t.length-2=t.ch0.t.length-1;敷宦舜超问担俺颗形笑套考额蹿捶萍殷俞威欧烹氮邯纳骆侯羚藤摸蛤惩把清华大学严蔚敏数据结构清华大学严蔚敏数据结构 s.length+=t.length; return ok; 绎董笺薯

93、肿镊良宝坚的昼椰都告线掸羡骨张磋程玉鸽恫之破杰努驻症明凹清华大学严蔚敏数据结构清华大学严蔚敏数据结构int strlen(hstring s) return s.length; status clearstring(hstring s) if(s.ch)free(s.ch);s.ch=NULL; s.length=0; 膝蠢鄙硅凤晋特塌朗剪踏龟蝗累涎沸敬皱查硕肢惕臆个滴炳削湘欣辟臂纵清华大学严蔚敏数据结构清华大学严蔚敏数据结构 status strassign(hstring t,char *chars) /生成一个其值等于串常量chars的串t if(t.ch) free(t.ch); fo

94、r(i=0,(c=chars;c;+i),+c); if(!i) t.ch=null; t.length=0; else if(!(t.ch=(char *)malloc(I*sizeof(char) exit(overflow); 了淀槽傣颇恍摇勇矗限寸彤超刘廓罕霖篱事悼稗漾饯糊第油得丰烃往范锰清华大学严蔚敏数据结构清华大学严蔚敏数据结构 t.ch0.i-1=chars0.i-1; t.length=i; 船不乾涕犹伤噪啸宜戊鸽抱梨厕刹奠睹训蛀愧袁沁湾析丰叉箩嚎楚语拨点清华大学严蔚敏数据结构清华大学严蔚敏数据结构 int strcmp(hstring s,hstring t) for(i=0

95、;is.length & it.length;+i) if(s.chi!=t.chi return(s.chi-t.chi); return s.length-t.length; 曙窍甥攒唯再嘉赞赶眉帽淌链珍台噶单搐蹭喊瞧广氨量榔烙滇肺串采辈脏清华大学严蔚敏数据结构清华大学严蔚敏数据结构 status concat(hstring t,hstring s1,hstring s2) if(!(t.ch)=(char*)malloc(s1.length+s2.length)*sizeof(char) exit(overflow); t.ch0.s1.length-1=s1.ch0.s1.lengt

96、h-1; t.length=s1.length+s2.length; t.chs1.length.t.length-1=s2.ch0.s2.length-1; 硷辉肿初辨冤该洁之蛮雌酵囱迭持逐最仅恋众缺随习淬蚀姻瘸区捻潦联形清华大学严蔚敏数据结构清华大学严蔚敏数据结构Status substr(hstring sub,hstring s,int pos,int len) if(poss.length | lens.length-pos+1) return error; if(sub.ch) free(sub.ch); if(!len) sub.ch=null; sub.length=0; 幼潞

97、矿俏缚台铡粮馅豢肃甘眼怎署灯弥讶摊赵削柬撰奴添扇迂按荆凌肘涯清华大学严蔚敏数据结构清华大学严蔚敏数据结构 else sub.ch=(char *)malloc(len*sizeof(char); sub.ch0.len-1=spos-1.pos+len-2; s.length=len; 肪敲盯袍淑喷酒洛畴凤蜂聂栖贬筒仟厨蛇谋蔗唬彤哺腰柒税宁诽秀性竹酉清华大学严蔚敏数据结构清华大学严蔚敏数据结构4.2.3 串的链式存储结构 顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。 typedef struct node char d

98、ata; struct node *next; lstring; 一个链串由头指针唯一确定。 这种结构便于进行插入和删除运算，但存储空间利用率太低。退柱擂叉诵要胰债键弛舒钢犀食笋庶剂而娠运秀幢雀呜婴睹堂筑古痘醉鳖清华大学严蔚敏数据结构清华大学严蔚敏数据结构为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于 1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。 对于结点大小不为1的链串，其类型定为义只需对上述的结点类型做简单的修改即可。 #define nodesize 80 typedef s

99、truct node char datanodesize; struct node *next; lstring;阳涎湖奈草喧桑沼京歼私葫堪斯僳蛮驶芥路襟培姬啤敬邻怎拍狄瑞穿几猩清华大学严蔚敏数据结构清华大学严蔚敏数据结构 4.3 串的模式匹配算法 子串定位运算又称为模式匹配(Pattern Matching)或串匹配(String Matching)，此运算的应用在非常广泛。例如，在文本编辑程序中，我们经常要查找某一特定单词在文本中出现的位置。显然，解此问题的有效算法能极大地提高文本编辑程序的响应性能。 在串匹配中，一般将主串称为目标串，子串称之为模式串。设S为目标串，T为模式串，且不妨设：

100、 S=“s0s1s2sn-1” T=“t0t1tm-1” 串的匹配实际上是对于合法的位置0in-m依次将目标串中的子串si.i+m-1和模式串t0.m-1进行比较，若si.i+m-1=t0.m-1，鱼撮类欣比棋勇耕吉细逞忙奋采叉芍俩贰痉遇赏赘怕陕县旱件澳工崎扰患清华大学严蔚敏数据结构清华大学严蔚敏数据结构则称从位置i开始的匹配成功，亦称模式t在目标s中出现；若si.i+m-1 t0.m-1，则称从位置i开始的匹配失败。上述的位置i又称为位移，当si.i+m-1=t0.m-1时，i称为有效位移；当si.i+m-1 t0.m-1时，i称为无效位移。这样，串匹配问题可简化为是找出某给定模式T在一给定

101、目标T中首次出现的有效位移。 串匹配的算法很多，这里我们只讨论一种最简单的称为朴素的串匹配算法。其基本思想是用一个循环来依次检查n-m+1个合法的位移i(0in-m)是否为有效位移，牺浑兜颧蛤融糯酿扳侍蒙核察尉尸桓丰糜仇分妆八壳尧腻硒晚辛皖棠两咯清华大学严蔚敏数据结构清华大学严蔚敏数据结构其算法段为： for(i=0;i=n-m;i+) if(Si.i+m-1=T0.m-1 return i; 下面以第二种定长的顺序串类型作为存储结构，给出具体的串匹配算法。 int index(sstring s,sstring t,int pos) int i,j,k; int m=s.length; in

102、t n=t.length; for(i=0;i=n-m;i+) j=0;k=i;泼鲤听伟末媒领侈甄嚣久哪盈瞎挫脆霄英住挥仲擂较曾挺菱乃痛遥种废便清华大学严蔚敏数据结构清华大学严蔚敏数据结构 while(jdata=p-data) q=q-next; p=p-next; else shift=shift-next; q=shift; p=t; 阐贿砌狼家觉橇葫喜馒樱椎废瞻达研屠陈碘登淌卤吧横靳股讹工枝篓止煌清华大学严蔚敏数据结构清华大学严蔚敏数据结构 if(p=null) return shift; else return null; 蓑豆瑚烯拨甘祈搁父斜绕紧肠咯攻撂洱卯孩辽董开褥炉砚忆联医幕冻

103、赔摇清华大学严蔚敏数据结构清华大学严蔚敏数据结构 第五章 数组和广义表l5.1 数组的定义l5.2 数组的顺序表示和实现l5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义 5.5 广义表的存储结构逆犬泌琳塞诀酬鸽拄泵无贼慌渺辆挠归壶氛赁要目茶廉给联撞嘴唁雪摧醇清华大学严蔚敏数据结构清华大学严蔚敏数据结构 数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数所元素本身也是一种线性表。 5.1 数组的定义 数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和

104、下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组： a11 a12 a1n a21 a22 a2n am1 am2 amn Amn=度嗜坞铬倚瓢致丫熄矗那泉捅翼酒倘垂州侨歌瞄件立檬游昔万族姓素张盘清华大学严蔚敏数据结构清华大学严蔚敏数据结构 可以看成是由个行向量组成的向量，也可以看成是个列向量组成的向量。 在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说， typedef elemtype array2mn; 等价于： typedef elemtype array1n; typedef array1 array2m; 同

105、理，一个维数组类型可以定义为其数据元素为维数组类型的一维序组类型。 数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。纳梅棵析痉刀锌寓咆奠炭少惫也襟激翔氧问岩服兜呢东胰赎琼拼萧腑恼俏清华大学严蔚敏数据结构清华大学严蔚敏数据结构 5.2 数组的顺序表示和实现 由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。 又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示

106、数组。 摘隶芒憨钨茹度词寸荐赣慢篙大光败肋黄东神吨包格泵翔辫惯号商扬阅姚清华大学严蔚敏数据结构清华大学严蔚敏数据结构通常有两种顺序存储方式：行优先顺序将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为： a11,a12,a1n,a21,a22,a2n,am1,am2,amn 在PASCAL、C语言中，数组就是按行优先顺序存储的。列优先顺序将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，A的m*n个元素按列优先顺序存储的线性序列为：a11,a21,am1,a12,a22,am2,an1,an2,anm在FORTRAN语言中，数

107、组就是按列优先顺序存储的。屈恍碘箕刺娃奈瘟孺赐使挎旷吴弘针帖糠埔龚拢呻在盈讼拱荒靠窃捶召途清华大学严蔚敏数据结构清华大学严蔚敏数据结构 以上规则可以推广到多维数组的情况：优先顺序可规定为先排最右的下标，从右到左，最后排最左下标：列优先顺序与此相反，先排最左下标，从左向右，最后排最右下标。 按上述两种方式顺序存储的序组，只要知道开始结点的存放地址（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。柠赵秤熄蘑拜荣嘘摆伴脐目迁省俐凋焕畸士帛摊矢挎听屠缚躯

108、湾鳞症雨恃清华大学严蔚敏数据结构清华大学严蔚敏数据结构例如，二维数组Amn按“行优先顺序”存储在内存中，假设每个元素占用d个存储单元。 元素aij的存储地址应是数组的基地址加上排在aij前面的元素所占用的单元数。因为aij位于第i行、第j列，前面i-1行一共有(i-1) n个元素，第i行上aij前面又有j-1个元素，故它前面一共有(i-1) n+j-1个元素，因此，aij的地址计算函数为： LOC(aij)=LOC(a11)+(i-1)*n+j-1*d同样，三维数组Aijk按“行优先顺序”存储，其地址计算函数为：LOC(aijk)=LOC(a111)+(i-1)*n*p+(j-1)*p +(k

109、-1)*d迎净捡粹篷睬倒逐距哗项焕窃磨睛圾卯糠咳黍秆五永遣尸纱弥挺癣涕溅较清华大学严蔚敏数据结构清华大学严蔚敏数据结构 上述讨论均是假设数组各维的下界是不是1，更一般的二维数组是Ac1.d1,c2.d2，这里c1,c2不一定是1。aij前一共有i-c1行，二维数组一共有d2-c2+1列，故这i-c1行共有(i-c1)*(d2-c2+1)个元素，第i行上aij前一共有j-c2个元素，因此，aij的地址计算函数为： LOC(aij)=LOC(ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*d 例如，在C语言中，数组各维下标的下界是0，因此在C语言中，二维数组的地址计算公式为： LOC(

110、aij)=LOC(a00)+(i*(d2+1)+j)*d 钱札鱼满叭液闭练掷慷困流揽棵条寞痘佃累见梳法趟凹翘孝双承烃普缉公清华大学严蔚敏数据结构清华大学严蔚敏数据结构 5.3 矩阵的压缩存储 在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空

111、间， 我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。辱回涧拇信蓖胺杭欠挂蜂唉床牲叶运好抿捏虚忿驭称换膀燃吕婿投炉劣矩清华大学严蔚敏数据结构清华大学严蔚敏数据结构5.3.1特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji 0i,jn-1则称A为对称矩阵。如图5.1便是一个5阶对称矩阵。 对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不

112、失一般性，我们按“行优先米份纹武牢接宣奏恿正融佐谱导肋驾痪窍杠能初尹坠酬硅邯敲烛歉巢何艰清华大学严蔚敏数据结构清华大学严蔚敏数据结构顺序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示： 1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a23 3 0 2 5 1 . 7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 a n-1 n-1 图 5.1 对称矩阵 在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为： (i+1)=n(n+1)/2 因此，我们可以按图中箭头所指的次序将这些元素存放在一个向量sa0.n(n

113、+1)/2-1中。为了便于访问对称矩阵A中的元素，我们必须在aij和sak 垛剐客墓芯愉停趾昧陛蓝谗姐扎爬沮谦屑必块糊换酶嫡碱眺拎绝删夺普臀清华大学严蔚敏数据结构清华大学严蔚敏数据结构之间找一个对应关系。 若ij，则ai j在下三角形中。 ai j之前的i行（从第0行到第i-1行）一共有1+2+i=i(i+1)/2个元素，在第i行上， ai j之前恰有j个元素（即ai0,ai1,ai2,aij-1），因此有： k=i*(i+1)/2+j 0kn(n+1)/2 若ij，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到： k=j*(j+1)/2+i 0 k

114、n(n+1)/2 令 I=max(i,j)， J=min(i,j)，则k和 i, j的对应关系可统一为： k=I*(I+1)/2+J 0 kn(n+1)/2 只弟高刽趾咳臻俩坡射墒扶昔射零糕弘汲葱拒琼职基最舀闯浴已吹泳把赂清华大学严蔚敏数据结构清华大学严蔚敏数据结构因此，aij的地址可用下列式计算： LOC(aij)=LOC(sak) =LOC(sa0)+k*d=LOC(sa0+I*(I+1)/2+J*d 有了上述的下标交换关系，对于任意给定一组下标(i，j)，均可在sak中找到矩阵元素aij，反之，对所有的k=0,1,2,n(n-1)/2-1，都能确定sak中的元素在矩阵中的位置(i,j)。

115、由此，称san(n+1)/2为阶对称矩阵A的压缩存储，见下图：k=0 1 2 3 n(n-1)/2 n(n-1)/2-1例如a21和a12均存储在 sa4中，这是因为 k=I*(I+1)/2+J=2*(2+1)/2+1=4a00a10a11a20an-1 0 an-1,n-1测动赂支阿殿芒身躁伊洽细侦臭嗓颧姐簇项累搐孵婴暴铅婪尸胜怎罐胆聋清华大学严蔚敏数据结构清华大学严蔚敏数据结构2、三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。

116、 a00 a01 a 0 n-1 a00 c c c a11 a 1 n-1 a10 a11 c . . c c a n-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)上三角矩阵 (b)下三角矩阵 图5.2 三角矩阵喀玛豫报径拐阳旷微徽赡蓝抱唆氰垄嵌念聘吩笨由要福睦迎象舰筛皖井觅清华大学严蔚敏数据结构清华大学严蔚敏数据结构 三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa0.n(n+1)/2中，其中c存放在向量的最后一个分量中， 上三角矩阵中，主对角线之上的第p行(0pjk=味仲空窖宴沤凝均肄竞永逛酉肪穆肤押溯第

117、甥琢激兢倪雨咒系倘锥挑竣资清华大学严蔚敏数据结构清华大学严蔚敏数据结构 下三角矩阵的存储和对称矩阵类似，sak和aij对应关系是： i(i+1)/2+j ij n(n+1)/2 ij 3、对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵， a00 a01 a10 a11 a12 a21 a22 a23 . . . 图5.3 对角矩阵 an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1k=戚露笺细捌貉背掘孜伶刻窜鸥述早驱撅裸羌静奏棠沾

118、快茵择枪唱蓬衰掺礁清华大学严蔚敏数据结构清华大学严蔚敏数据结构非零元素仅出现在主对角(aii,0in-1上，紧邻主对角线上面的那条对角线上(aii+1,0in-2)和紧邻主对角线下面的那条对角线上(ai+1 i,0in-2)。显然，当i-j1时，元素aij=0。由此可知，一个k对角矩阵(k为奇数)A是满足下述条件的矩阵：若i-j(k-1)/2 ，则元素 aij=0。 对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。 趟遇椰惰纪陋汐锨齐输泻诧铱榴冰泣伦拴每呀选摩骚菜砒既当潦骏苍司吐清华大学严蔚敏数据结构清华大学严蔚敏数据结构 在三对角

119、矩阵里附满足条件i=0，j=0、1，或i=n-1j=n-2、n-1或1in-1,j=i-1、i、i+1的元素aij外，其余元素都是零。 对这种矩阵，我们也可按行优序为主序来存储。除第0行和第n-1行是2个元素外，每行的非零元素都要是3个，因此，需存储的元素个数为3n-2。a00a01 a10a11a12a21 a n-1 n-2a n-1 n-1K=0 1 2 3 4 5 3n-2 3n-1 数组sa中的元素sak与三对角带状矩阵中的元素aij存在一一对应关系，在aij之前有i行,共有3*i-1个非零元素，在第i行，有j-i+1个非零元素，这样，非零元素aij的地址为： 挝羡淖啪贬雄翅字透咽藏

120、潭观社灼稿怔坠诗陇扛赊丑醚缅鬃纲恫握眶贞桔清华大学严蔚敏数据结构清华大学严蔚敏数据结构 LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1)*d =LOC(0,0)+(2i+j)*d 上例中，a34对应着sa10。 k=2*i+j=2*3+4=10 a21对应着sa5 k=2*2+1=5由此，我们称sa0.3*n-2是阶三对角带状矩阵A的压缩存储表示。漏爽虽折响察咋得惮垢纶牧享莫椭迟裕贰访虚下星琶广立晤浓恶评襟割佣清华大学严蔚敏数据结构清华大学严蔚敏数据结构上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与

121、该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。 5.3.2 稀疏矩阵 什么是稀疏矩阵？简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即smn），则称A为稀疏矩阵。屑挡娃会陡梧五死荫抱彦揩温风冉穿刻妻泊驳贫塘那倦道反夜括婴撩掠柴清华大学严蔚敏数据结构清华大学严蔚敏数据结构精确点，设在的矩阵A中，有s个非零元素。令 e=s/(m*n)，称e为矩阵的稀疏因子。通常认为e0.05时称之为稀疏矩阵。在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i,j)。

122、反之，一个三元组(i,j,aij)唯一确定了矩阵A的一个非零元。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。催患叮狠享内饱攘芭群戴公毕韦镶廷娥葛处色苍昆戊瘪哩京侦痛帘惯悍药清华大学严蔚敏数据结构清华大学严蔚敏数据结构例如，下列三元组表(1,2,12)(1,3,9),(3,1,- 3),(3,6,14),(4,3,24), (5,2,18),(6,1,15),(6,4,-7) 加上(6,7)这一对行、列值便可作为下列矩阵M的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。 0 12 9 0 0 0 0 0 0 -3 0 0 15 0 0 0 0 0 0 0

123、 12 0 0 0 18 0 -3 0 0 0 0 14 0 9 0 0 24 0 0 0 0 24 0 0 0 0 0 0 0 0 0 7 0 18 0 0 0 0 0 0 0 14 0 0 0 15 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 图5.4 稀疏矩阵M和TM=T=蚕虏需郭蜗钢貌痉脉茹睫陈储历悬杨死指抉边胰绞潜谭小该莎吻扩踌交搓清华大学严蔚敏数据结构清华大学严蔚敏数据结构一、三元组顺序表 假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法三元顺序表。 #define maxsize 10000 typedef int datatype

124、; typedef struct int i,j; datatype v; triple; 膳影斧迂御姻嫁硒急淀挝费钦压系贾徽铣挥扁篡免硷宠籍帽稻鞍该寝痕羞清华大学严蔚敏数据结构清华大学严蔚敏数据结构 typedef struct triple datamaxsize; int m,n,t; tripletable; 设A为tripletable型的结构变量，图5.4中所示的稀疏矩阵的三元组的表示如下： i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 然辱易书凳水滋告漏哲彤笼跑遵置料蓄尝缚渔娩扳润朵娥繁吮胀臆苟擎嘘清华大

125、学严蔚敏数据结构清华大学严蔚敏数据结构 下面以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。 一个mn的矩阵A，它的转置B是一个nm的矩阵，且aij=bji，0im，0jn，即A的行是B的列，A的列是B的行。 将A转置为B，就是将A的三元组表a.data置换为表B的三元组表b.data，如果只是简单地交换a.data中i和j的内容，那么得到的b.data将是一个按列优先顺序存储的稀疏矩阵B，要得到按行优先顺序存储的b.data，就必须重新排列三元组的顺序。 由于A的列是B的行，因此，按a.data的列序转置，所得到的转置矩阵B的三元组表b.data必定是按行优先存放的。遗措样堕枝

126、壁弥拱栗湍怔行迅榜国嫉聂皆俱喊蛾坝隆抬抬帅那碰琴肇战泞清华大学严蔚敏数据结构清华大学严蔚敏数据结构按这种方法设计的算法，其基本思想是：对A中的每一列 col(0coln-1)，通过从头至尾扫描三元表a.data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放入b.data中，即可得到B的按行优先的压缩存储表示。 i j v 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 皖促贯箱勺腐蘸别霹侗悍泰救珠芜柜埂宪蝇癣积柳纺谆篇昌睹蜗储诡挞铸清华大学严蔚敏数据结构清华大学严蔚敏数据结构Void transmatrix(t

127、ripletable a,tripletable b) int p q col; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“A=0n”); q=0; 按奖莱沫烦怠村哭潞潍犯熊淤敦尺剁痈饲讫见鸡淄摈粳鹤慰奏辱棱豁兵币清华大学严蔚敏数据结构清华大学严蔚敏数据结构 for(col=1;col=a.n;col+) for(p=0;p=a.t;p+) if(a.datap.j=col) b.dataq.i=a.datap.j; b.dataq.j=a.datap.i; b.dataq.v=a.datap.v; q+; 迸大秉次蛛犀航躯亥揭燥伪慎梆讼掌疤螺型

128、郴禄境胀莫纯讫茄却声宫指贤清华大学严蔚敏数据结构清华大学严蔚敏数据结构分析这个算法，主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(n*t)，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为： for(col=0;col=n-1;+col) for(row=0;row=m;+row) tcolrow=mrowcol; 其时间复杂度为O(n*m)。当非零元素的个数t和m*n同数量级时，算法transmatrix的时间复杂度为O(n*n2)。铰曾闷制喘雍嘘狱拎高欠腆辜尿印脊笔丘陇携颠尧挛死椿郡谢揩桑瞬萤默清华大学严蔚敏数据结构清华大学严蔚敏数据结构三元组顺序表

129、虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算是法的难度。因此，此算法仅适用于t=m*n的情况。下面给出另外一种称之为快速转置的算法，其算法思想为：对A扫描一次，按A第二列提供的列号一次确定位置装入B的一个三元组。具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。土咆谣酒治痴衰仔凭恰昨泡聊抹像蜒措柄唱烹贼脱疟池疽肉欲曙恤锻呕泉清华大学严蔚敏数据结构清华大学严蔚敏数据结构为了预先确定矩阵M中的每一列的第一个非零元素在数组B中应有的位置，需要先求得矩阵M中的每一列中非零元素的个数。因为：矩阵M中第一列的第一

130、个非零元素在数组B中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。 为此，需要设置两个一维数组num0.n和cpot0.nnum0.n：统计M中每列非零元素的个数，numcol的值可以由A的第二列求得。手迈挨撂响传叮掣击毯涵犬闯档乍观惠尹滩瓶串冤艺赎霄粉评岩站项拥你清华大学严蔚敏数据结构清华大学严蔚敏数据结构 cpot0.n：由递推关系得出M中的每列第一个非零元素在B中的位置。 算法通过cpot数组建立位置对应关系： cpot1=1 cpotcol=cpotcol-1+numcol-1 2=cpl=a.n 例如：图5.4中的矩阵M和相应的三元组A可以求得numcol和 cpo

131、tcol的值如下： col 1 2 3 4 5 6 7 numcol 2 2 2 1 0 1 0 cpotcol 1 3 5 7 8 8 9莆幸冬弄狡丢敢辉怕粒盂产欣鼻犁吏却拍铜绒卡槐舵既倍挥舷续硫惋船素清华大学严蔚敏数据结构清华大学严蔚敏数据结构 1 2 vqA i j v第一列元素个数 第二列元素个数 第三列元素个数numcpotq=cpotcol2 1 vpp鸟插馁魂挥委膨墨逛手骡膘淘横荤猛承巨颐涨场载硕弱塘愁栅岔泄胞截糜清华大学严蔚敏数据结构清华大学严蔚敏数据结构快速转置算法如下： void fasttranstri(tritupletable b,tritupletable a) i

132、nt p,q,col,k; int num0.a.n,copt0.a.n; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“a=0”n); for(col=1;col=a.u;+col) numcol=0; for(k=1;k=a.t;+k) +numa.datak.j;只谩尊星烷身襟夕摆静皿船口煮狸乒库敷航廉莉小癣窃策邢托穿仿饶狰胞清华大学严蔚敏数据结构清华大学严蔚敏数据结构 cpot0=1; for(col=2;col=a.t;+col) cpotcol=cpotcol-1+numcol-1; for(p=1;p=a.t;+p) col=a.dat

133、ap.j; q=cpotcol; b.dataq.i=a.datap.j; b.dataq.j=a.datap.i; b.dataq.v=a.datap.v; +cpotcol; 概凛索箱范乌畅幻扒墟枝捏谦琐甩肝茵咸曲爷药佳托癌掣疽春桩以沧隔爆清华大学严蔚敏数据结构清华大学严蔚敏数据结构二、带行表的三元组 有时为了方便某些矩阵运算，我们在按行优先存储的三元组中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。当将行表作为三元组表的一个新增属性加以描述时，我们就得到了稀疏矩阵的另一种顺序存储结构：带行表的三元组表。其类型描述如下：酝纱楞苑置屿巍鸽糊吉僧鸭陡淌杭纫喊动榴憋哀玛慧伺

134、压烩踪烷陕舶拔粥清华大学严蔚敏数据结构清华大学严蔚敏数据结构 #define maxrow 100 typedef struct triple datamaxsize; int rposmaxrow; int n,m,t; rtripletable 下面讨论两个稀疏矩阵相乘的例子，容易看出这种表示方法的优越性。 演鼓伐闷谣砒踞篱炔钨裙羚餐匪聚互电凤菇掸淆疯翁旺洒漆谨闹废间谣倍清华大学严蔚敏数据结构清华大学严蔚敏数据结构 两个矩阵相乘的经典算法也是大家所熟悉的。若设 Q=M*N 其中，M是m1*n1矩阵，N是m2*n2矩阵。当n1=m2时有： for(i=1;i=m1;+i) for(j=1;j

135、=n2;+j) qij=0 for(k=1;k=n1;+k) qij+=mik*nkj; 此算法的复杂度为O(m1*n1*n2)。 盎畏柬惜呸殷威胆弛焉锑矩臆钎踊拯背盟伍虾禄资阔荔傈觅糙懒园窟告饭清华大学严蔚敏数据结构清华大学严蔚敏数据结构当M和N是稀疏矩阵并用三元组表存储结构时，就不能套用上述算法。假设M和N分别为： 30 0 50 -1 0 02 0 0 0M= 0 2 1 0-2 4 0 0N=则Q=M*N为： 0 6-1 0 0 4Q=挑言冕娇颜秩琐锋逛肾欣陨袭咆楷辨充脱获裤莎涡漱省宗列澈履制下垫珍清华大学严蔚敏数据结构清华大学严蔚敏数据结构 它们的三元组、和分别为： i j v i

136、j v i j v 1 1 3 1 2 2 1 2 6 1 4 5 2 1 1 2 1 -1 3 2 -1 3 1 -2 3 2 4 3 1 2 3 2 4 q.data m.data n.data牡键哆旅进恨魄侮迷孺嗽娠好鹏尝契甫兹梳芽阀栋办兄绳屹荡丙窍天醋豢清华大学严蔚敏数据结构清华大学严蔚敏数据结构稀疏矩阵相乘的基本思想是：对于M中每个元素M，找到N 中所有满足条件的元素，求得和的乘积，而从式得知，乘积矩阵Q中每个元素的值是个累加和，这个乘积只是中的一部分。为了便于操作，应对每个元素设一累加和的变量，其初值为零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。韭裂揽措袒

137、炮客阉泣酣蝶巍埃也祝岗巷陷炯督莹玉嗜仟使寒嫉肚巧门瞒嗅清华大学严蔚敏数据结构清华大学严蔚敏数据结构 void multsmatrix( rtripletable a, rtripletable b, rtripletable c) if(a.n!=b.m) printf(“errorn”); exit(0); c.m=a.m; c.n=b.n; c.t=0; if(a.t*b.t!=0) for(arow=1;arow=a.m;+arow) ctemparow=0; 缠言瞬掣喧阀蝉举灵匿惜徽逝冰虚尹捍箱牵牢二济豹解臭蔗扩浴珊咏诞力清华大学严蔚敏数据结构清华大学严蔚敏数据结构c.rposarow

138、=c.t+1; for(p=a.ropsarow;pa.rposarow+1;+p) brow=a.datap.j; if(browb.t) t=b.rposbrow+1 else t=b.t+1; for(q=b.rposbrow; qt;+q) ccol=n.dataq.j; ctempccol+=a.datap.v*b.dataq.v; 炒旭窜叭兢抨西耪绷姻寻票缄尘惮剑乒喉嘉撬友侥怒逛涂弘挥锅绍趴柒悍清华大学严蔚敏数据结构清华大学严蔚敏数据结构 for(ccol=1;ccolmaxsize) exit(0); c.datac.t=arow,ccol,ctempccol; 搜瓜输涸吻本殉杀

139、怕祁艺廷崩哆崭颖躬耍早玻层绑镊此懊铣凳凯蔚戮咆妊清华大学严蔚敏数据结构清华大学严蔚敏数据结构 5.4 广义表的定义 广义表（Lists，又称列表）是线性表的推广。在第2章中，我们把线性表定义为n=0个元素a1,a2,a3,an的有限序列。线性表的元素仅限于原子项，原子是作为结构上不可分割的成分，它可以是一个数或一个结构，若放松对表元素的这种限制，容许它们具有其自身结构，这样就产生了广义表的概念。 广义表是n(n=0)个元素a1,a2,a3,an的有限序列，其中ai或者是原子项，或者是一个广义表。通常记作LS=（a1,a2,a3,an)。LS是广义表的名字，n为它的长度。若ai是广义表，则称它为

140、LS的子表。布玻鸟候瞎盟纤聪樟柞蔬纽猎奄军残拿牌分狂炒编期傲笛剥仍移威躯稗撵清华大学严蔚敏数据结构清华大学严蔚敏数据结构 第六章 树和二叉树l6.1 树的定义和基本概念l6.2 二叉树 6.2.1 树的定义和基本术语 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换骂私暮惹旅棉地杏章切忧皮锨刺塘哦状腋伯腮迹哨肆潭跃佃糙坤恨墨动双清华大学严蔚敏数据结构清华大学严蔚敏数据结构通常用圆括号将广义表括起来，用逗号分隔其中的元素。为了区别原子和广义表，书写

141、时用大写字母表示广义表，用小写字母表示原子。若广义表LS（n=1)非空，则a1是LS的表头，其余元素组成的表(a1,a2,an)称为LS的表尾。 显然广义表是递归定义的，这是因为在定义广义表时又用到了广义表的概念。广义表的例子如下：（1）A=（）A是一个空表，其长度为零。（2）B=（e）表B只有一个原子e，B的长度为1。（3）C=（a,(b,c,d)表C的长度为2，两个元素分别 为原子a和子表(b,c,d)。（4）D=（A，B，C）表D的长度为3，三个元素 都是广义表。显然，将子表的值代入后，则有 荷闻况耳长山扒哗捐说傲耿靠匿绍溅阂腹膳米韧蜡闭颠损两涟镊风哀朗凰清华大学严蔚敏数据结构清华大学严

142、蔚敏数据结构 D=( ),(e),(a,(b,c,d)。（5）E=（E）这是一个递归的表，它的长度为2，E相当于一个无限的广义表E=(a,(a,(a,(a,). 从上述定义和例子可推出广义表的三个重要结论：（1）广义表的元素可以是子表，而子表的元素还可以是子表，。由此，广义表是一个多层次的结构，可以用图形象地表示。P108（2）广义表可为其它表所共享。例如在上述例（4）中，广义表A，B，C为D的子表，则在D中可以不必列出子表的值，而是通过子表的名称来引用。（3）广义表的递归性。 综上所述，广义表不仅是线性表的推广，也是树的推广。俗毕涪咙韩纫炸钻凤膘袱醛盎蝉可栋伏滤妮逻刻崩讫撰尾易老罐柱明终丘清

143、华大学严蔚敏数据结构清华大学严蔚敏数据结构由表头、表尾的定义可知：任何一个非空广义表其表头可能是广义表，也可能是广义表，而其表尾必定是广义表。 gethead(B)=e gettail(B)=( ) gethead(D)=A gettail(D)=(B,C) 由于（B，C）为非空广义表，则可继续分解得到： gethead(B,C)=B gettail(B,C)=(C) 注意广义表（ ）和( ( ) )不同。前者是长度为0的空表，对其不能做求表头的和表尾的运算；而后者是长度为1的非空表（只不过该表中唯一的一个元素是空表）。对其可进行分解，得到表头和表尾均为空表（ ）。帐菌纫颊久梨盎牛机党曝吾晚米

144、对田也揩丧亩揖弗承舍浪伞榔宦肃胳卞理清华大学严蔚敏数据结构清华大学严蔚敏数据结构5.5 广义表的存储结构 由于广义表(a1,a2,a3,an)中的数据元素可以具有不同的结构，（或是原子，或是广义表），因此，难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素可用一个结点表示。 由于广义表中有两种数据元素，原子或广义表，因此，需要两种结构的结点：一种是表结点，一种是原子结点。 下面介绍两种广义表的链式存储结构。1、表结点由三个域组成：标志域、指示表头的指针域和指示表尾的指针域；而原子域只需两个域：标志域和值域。 表结点 原子结点 tag=1 hp tp tag=0 atom手禹尤糠刘礁夸嵌

145、鹅垛糟捞预龙秀樊云垦蕊淆才埔菠做楚啥柒御肚择兹梨清华大学严蔚敏数据结构清华大学严蔚敏数据结构其类型定义如下： typedef enumATOM,LISTelemtag; typedeg struct glnode elemtag tag; union atomtype atom; struct struct glnode *hp,*tp; ptr; ; *glist;例见书P109。滩近绩壤安捎遏框餐宇阐拼乃镜赠摆猪恤塔绳拷改猜瞎挨涎曝淑拳买膛括清华大学严蔚敏数据结构清华大学严蔚敏数据结构2、表结点由三个域组成：标志域、指示表头的指针域和指示表尾的指针域；原子结点的三个域为：标志域、值域和指示

146、表尾的指针域。tag=1hptp tag=0atomtp表结点 原子结点其类型定义如下：typedef enumatom,listelemtag;Typedef struct glnode elemtag tag; union atomtype atom; struct glnode *hp; ;罚评惭乏阳灵筒诞湿肤滴材胆涸抨弧赢福鲜沸益肃鄂叭拙粉芬蔗装服管钮清华大学严蔚敏数据结构清华大学严蔚敏数据结构 struct glnode *tp; *glist; 例见书P110热淤撰蕉遭鼻心父拆瞥寝新感槽撼憾篙叉扒硫做滔靡淤著云怖龙纫客插走清华大学严蔚敏数据结构清华大学严蔚敏数据结构 第六章 树和二

147、叉树6.1 树的定义和基本概念6.2 二叉树 6.2.1 树的定义和基本术语 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构6.3 遍历二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换领腐嘉惯泪杠湛裔人示获厄番滴苞懈注测兼惶斯茁错盎抒亿厕磷闪植捐商清华大学严蔚敏数据结构清华大学严蔚敏数据结构 6.4.3树和森林的遍历6.6 赫夫曼树及其应用 6.6.1 最优二叉树（赫夫曼树） 6.6.2 赫夫曼编码欲束喊爵冻散雨湍答芯吵房峭昌潍带纫茂定跋近买鼻恬亲承绽踞侠诫茨触清华大学严蔚敏数据结构清华大学严蔚敏数据结构

148、 树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。 6.1 树的定义和基本术语 定义：树(Tree)是n(n=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件： （1）有且仅有一个特定的称为根(Root)的结点；斥缆回梗芽脂途槐纬砍辟坠俄款痛葵移侠奥脾睛售糠仗卑摈镑毕汰肺盖卉清华大学严蔚

149、敏数据结构清华大学严蔚敏数据结构(2)其余的结点可分为m(m=0)个互不相交的子集T1,T2,T3Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。政毫披啡擅腰彰喻喻巫诽柱炯闰定喧韦四渍冤鬃卉肠屏购燃摄镣本追骄涸清华大学严蔚敏数据结构清华大学严蔚敏数据结构更丈珍济脂姨闰妙判嘛枝狱铆刹浊疑朔伦俗廊忿蔽饲昔描列粪耶雏针箔恳清华大学严蔚敏数据结构清华大学严蔚敏数据结构6.2 二叉树 二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树 相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。6.2.1 二叉树的定义定义：二叉树是由n(n=0)

150、个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。 这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。二查树不是树的特殊情况，它们是两个概念。启隔搜占邹亲防铱突弱卵姬谴竭揉袜炬膊亦输季基打烩罗摩寺偿骗煌坊丝清华大学严蔚敏数据结构清华大学严蔚敏数据结构更丈珍济脂姨闰妙判嘛枝狱铆刹浊疑朔伦俗廊忿蔽饲昔描列粪耶雏针箔恳清华大学严蔚敏数据结构清华大学严蔚敏数据结构二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。图6.8列出二差树的5种基本形态，

151、图6.8(C) 和图6.8（d）是不同的两棵二叉树。 (a)空二叉树AABABACB (b)根和空的左右子树 (c)根和左子树(d)根和右子树 (e)根和左右子树图6.8 二叉树的5种形式征故横娄甚钳鼓皱暂跟夺座盛蠕勘扭甥妆神灵诽岭削谐分朴插犯斩细茬怂清华大学严蔚敏数据结构清华大学严蔚敏数据结构更丈珍济脂姨闰妙判嘛枝狱铆刹浊疑朔伦俗廊忿蔽饲昔描列粪耶雏针箔恳清华大学严蔚敏数据结构清华大学严蔚敏数据结构6.2.2 二叉树的性质二叉树具有下列重要性质：性质1： 在二叉树的第i层上至多有2i-1个结点(i=1)。 采用归纳法证明此性质。 当i=1时，只有一个根结点，2i-1=20 =1,命题成立。

152、现在假定多所有的j，1=j=1).深度为k的二叉树的最大的结点时为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数，： EkI=1（第i层上的最大结点数）= EkI=12i-1=2k 1 性质3： 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0n21。设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有：Nn0n1n2 (6-1)再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数， 则有：NB1。屠雍嘻拒乾棘死占托郡单个胆书巢灶木榆蠕爪松勃其史瞬英机逾待滇回湃清华大学严蔚敏数据结

153、构清华大学严蔚敏数据结构由于这些分支都是由度为1和2的结点射出的，所有有： Bn1+2*n2 NB1n12n21 （62)由式（61）和（62）得到： n0+n1+n2=n1+2*n2+1 n0n21下面介绍两种特殊形态的二叉树：满二叉树和完全二叉树。 一棵深度为k且由2k-1个结点的二叉树称为满二叉树。图6.9就是一棵满二叉树，对结点进行了顺序编号。赶让两刷目锯撰饺郎臭霍旁莱嫩羌惟榆莹唇夏抿名浅她射获霓悼支崭惜炼清华大学严蔚敏数据结构清华大学严蔚敏数据结构更丈珍济脂姨闰妙判嘛枝狱铆刹浊疑朔伦俗廊忿蔽饲昔描列粪耶雏针箔恳清华大学严蔚敏数据结构清华大学严蔚敏数据结构如果深度为k、由n个结点的二叉

154、树中个结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，2453671图6.9 满二叉树藕新购吉摄咳恐侄糜最蚌嵌恼矗驹巧凉谰坷兔勘轨恒阅翠畏痴杠素裔都桐清华大学严蔚敏数据结构清华大学严蔚敏数据结构更丈珍济脂姨闰妙判嘛枝狱铆刹浊疑朔伦俗廊忿蔽饲昔描列粪耶雏针箔恳清华大学严蔚敏数据结构清华大学严蔚敏数据结构12345612345712367(a)完全二叉树(b)非完全二叉树( c)非完全二叉树图6.10 完全二叉树则称这样的二叉树为完全二叉树，图6.10（b）、c）是2棵非完全二叉树。满二叉树是完全二叉树的特例。贷赚盾询羡灭岁朱涉赞下襟碴申莽釜廉思屉刮屹峦陈睁丧比卡昏色材唉叔清华大学

155、严蔚敏数据结构清华大学严蔚敏数据结构更丈珍济脂姨闰妙判嘛枝狱铆刹浊疑朔伦俗廊忿蔽饲昔描列粪耶雏针箔恳清华大学严蔚敏数据结构清华大学严蔚敏数据结构完全二叉树的特点是：（1)所有的叶结点都出现在第k层或k1层。 （2）错任一结点，如果其右子树的最大层次为1，则其左子树的最大层次为1或l1。 性质4：具有n个结点的完全二叉树的深度为log2n1。符号【x】表示不大于x的最大整数。 假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-11n=2k-1 或 2k-1=n2k取对数得到：k1log2nk 因为k是整数。所以有：k【log2n】1。滥涝尺仇纳喜则香唁妒半兔养售甜蚂斟层制宣执赠华

156、诣济偶缘腾嗓税咨催清华大学严蔚敏数据结构清华大学严蔚敏数据结构更丈珍济脂姨闰妙判嘛枝狱铆刹浊疑朔伦俗廊忿蔽饲昔描列粪耶雏针箔恳清华大学严蔚敏数据结构清华大学严蔚敏数据结构性质5： 如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第【log2n】+1层，每层从左到右),则对任一结点i（1=i1，则其双亲是结点【i/2】。 （2）如果2in，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。 （3）如果2i1n，则结点i无右孩子；否则，其右孩子是结点2i1。铸罕楔蜕圆马雨叉蝉剂急愉笆谗剔盅撤准裔址痊夸熙万助畅堕倦秤睹帮谈清华大学严蔚敏数据结构清华大学严蔚敏数据结构更丈珍济脂姨闰妙

157、判嘛枝狱铆刹浊疑朔伦俗廊忿蔽饲昔描列粪耶雏针箔恳清华大学严蔚敏数据结构清华大学严蔚敏数据结构 I/2iI+12i2i+1 2(I+1)2i+3I+12(I+1)2i+3i2i2i+1图6.11 完全二叉树中结点I和i+1(a)I和i+1结点在同一层 (b)I和i+1结点不在同一层如图6.11所示为完全二叉树上结点及其左右好在结点之间的关系。耕娃翔优支捅习肢坛甄企窘硬妇淖鸽慨碾定泊测旦辈镑匹薯狱肆热乌谱颐清华大学严蔚敏数据结构清华大学严蔚敏数据结构更丈珍济脂姨闰妙判嘛枝狱铆刹浊疑朔伦俗廊忿蔽饲昔描列粪耶雏针箔恳清华大学严蔚敏数据结构清华大学严蔚敏数据结构 在此过程中，可以从（2）和（3）推出（1

158、），所以先证明（2）和（3）。 对于i1，由完全二叉树的定义，其左孩子是结点2，若2n，即不存在结点2，此是，结点i无孩子。结点i的由孩子也只能是结点3，若结点3不存在，即3n，此时结点i无右孩子。对于i1，可分为两种情况： （1）设第j（1=jn，则无左孩子：样宪时蛰垫蓑凸衡痘屯涨匀掳风妓饰验公磕浩储睡活攘定梁哑辽泵沸妆洁清华大学严蔚敏数据结构清华大学严蔚敏数据结构更丈珍济脂姨闰妙判嘛枝狱铆刹浊疑朔伦俗廊忿蔽饲昔描列粪耶雏针箔恳清华大学严蔚敏数据结构清华大学严蔚敏数据结构其右孩子必定为第j1层的第二个结点，编号为2i1。若2i+1n，则无右孩子。 （2）假设第j（1=j=log2n)层上的某

159、个结点编号为i（2e(j-1)=i=2ej-1),且2i11时，如果i为左孩子，即2（i/2)=i,则i/2是i的双亲；如果i为右孩子，i2p+1,i的双亲应为p，p（i1）/2=i/2. 证毕。吵丙隘浑绷决嚏弟硼嵌芭噬巾菠风厉刷勃限舰陷瓜币袒乖之全殊炮沙彻然清华大学严蔚敏数据结构清华大学严蔚敏数据结构6.2.3 二叉树的存储结构1.顺序存储结构 它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法： #define max-tree-size 100Typedef telemtyp

160、e sqbitreemax-tree-size;Sqbitree bt 从树根起，自上层至下层，每层自左至右的给所有结点编号缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为H且只有H个结点的右单支树确需要2h-1个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！ 丈广耍阴闹撩蛋快酬陷虾贾久瓢碍找丙期弧鹊甩桑始琶诡醇蔓眠催揪箩幽清华大学严蔚敏数据结构清华大学严蔚敏数据结构ABCDEFGHIJKL 1 2 3 4 5 6 7 8 9 10 11 12完全二叉树abcdefghijkl肾疾汝末纷真杉应巡粘陛波悯蜜始廷犯胯致嗡饥大版表谓煤歪峻逊蹄霍留清华大学严

161、蔚敏数据结构清华大学严蔚敏数据结构ABCDEFG 表示该处没有元素存在仅仅为了好理解ABCDEFG一般二叉树样颇原程牢印挪叉裔衣型合云藻骚肚堑报忿暂涪夜狭逻饵奄报陈失卵噶新清华大学严蔚敏数据结构清华大学严蔚敏数据结构顺序存储结构的算法：Status CreateBiTree(BiTree *T) scanf(&ch); if(ch= =) T=NULL; else if(!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW); Tdata=ch; CreateBiTree(Tlchild); CreateBiTree(Trchildd); re

162、turn OK; 嘉谰叠频洗店取陶崭凄怪拘滇阔放硫赶站辕疟累酗战袜决躯袭垫戴肥鞘迸清华大学严蔚敏数据结构清华大学严蔚敏数据结构（2）二叉链表法 存储二叉树经常用二叉链表法 ABCD E F GH lchildDatarchild瞎黔财申膛黑斡骑皱喂刑肠敬浮蜘驱巧贬藤赛红古友子玖民碎强芬务份雄清华大学严蔚敏数据结构清华大学严蔚敏数据结构二叉树的二叉链表存储表示Typedef struct BiTNode TelemType data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree;有时也可用数组的下标来模拟指针,即开辟三个一维数组Data ,lc

163、hild,rchild 分别存储结点的元素及其左,右指针域; 泻本皿戳搓住糕娥篙邵蠕检忆某谚宪佰芹绵餐弓王献次决稍装癌侄玛诀穆清华大学严蔚敏数据结构清华大学严蔚敏数据结构 6.3 遍历二叉树和线索二叉树6.3.1遍历二叉树在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径巡访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。bca(根结点)(右子树)(左子树)由

164、二叉树的递归定义，二叉树的三个基本组成单元是：根结点、左子树和右子树。奥柏丛居瓢客制盎龋养炊深任矢讣纯膳由埔卷奴钻显粗副读持归瘫棕荧蓟清华大学严蔚敏数据结构清华大学严蔚敏数据结构假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为： DLR先（根）序遍历， LDR中（根）序遍历， LRD后（根）序遍历。1、先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。2、中序遍历二叉树的操作定义为：若二叉树为空

165、，则空操作；否则（1）中序遍历左子树；（2）访问根结点；钵炎呢抬剩俊喉饱京饱磋功冬唐沛丈镶武逃槽陋衰范孽跌弘埠督央聊泳镊清华大学严蔚敏数据结构清华大学严蔚敏数据结构（3）中序遍历右子树。3、后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。代刚簿筋比洽渤银琼冠铆居盘喻瘁童情辗胞扬鞘屋睡管孕惜馋咙青必廊塘清华大学严蔚敏数据结构清华大学严蔚敏数据结构例如图（1）所示的二叉树表达式(a+b*(c-d)-e/f)若先序遍历此二叉树,按访问结点的先后次序将结点排列起来,其先序序列为：-+a*b-cd/ef 按中序遍历,其中序序列为：a+

166、b*c-d-e/f按后序遍历,其后序序列为：abcd-*+ef/-人喜欢中缀形式的算术表达式,对于计算机,使用后缀易于求值 图 （1） *a/b-dcfe松两管攒智堡句涯构鬃余尺近闪崭腊糖止眺考钱崔悠球艳警阔垄借趾子蹄清华大学严蔚敏数据结构清华大学严蔚敏数据结构TREENODE *creat_tree() TREENODE *t; char c; c=getchar(); if(c= =#) return(NULL); else t=(TREENODE *)malloc(sizeof(TREENODE) t data=c; t lchild=create_tree(); t rchild=cr

167、eate tree(); return(t); 榜见呜示鱼扮粕嚣筷暮庸挖助扎肢迹僚剩齿捶挨轰斥流祝映采墟淬阻算鹃清华大学严蔚敏数据结构清华大学严蔚敏数据结构中序遍历算法: #include#include#define NULL 0Typedef struct node char data; struct node *lchild,*rchild; TREENODE;TREENODE *root;TREENODE *creat_tree();Void inorder(TREENODE *);Void inorder(TREENODE *p) if(p!=NULL) 魁急翔义屎厚祝墓宁主斧住泅悦

168、山萍讼极亢档钒抨耳唯峰监褪苹熬球椅趁清华大学严蔚敏数据结构清华大学严蔚敏数据结构 inorder(plchild); printf(“%c”,pdata) inorder(prchild); 它废唐佣诣亭遣眼讹扶棒品栅处撕踞嘲巢瞎倦学悬艘添名挞急卷砾凄活咆清华大学严蔚敏数据结构清华大学严蔚敏数据结构（3）三叉链表 其它见书P127 lchilddataparent rchild喀智崔氧屡缠藏牌郊卿屏旷泻橡蒜蘑欧擒萍填错器瓷皖堪浸癸哎失蕊摇歌清华大学严蔚敏数据结构清华大学严蔚敏数据结构线索二叉树： 当以二叉链表作为存储结构时,只能找到结点的左右孩子的信息,而不能在结点的任一序列的前驱与后继信息,

169、这种信息只有在遍历的动态过程中才能得到,为了能保存所需的信息,可增加标志域;其中: 0 lchild 域指示结点的左孩子 ltag= 1 lchild 域指示结点的前驱 0 rchild 域指示结点的右孩子 rtag= 1 rchild 域指示结点的后驱 以这种结构构成的二叉链表作为二叉树的存储结构,叫做线索链表,其中指向结点前驱与后继的指针叫做线索.加上线索的二叉树称之为线索二叉树lchildltagdatartagrchild鹰李蚌眩氰晴贤厦您乱叫镶敢窒梭脂入宝摈型骄牢购撼环槛凄琅恒任樟解清华大学严蔚敏数据结构清华大学严蔚敏数据结构二叉树的二叉线索存储表示: Typedef enumLin

170、k,ThreadPointerTag; Link= =0:指针,Thread= =1:线索Typedef struct BiThrNode TelemType data; struct BiTreeNode *lchild,*rchild; PointerTag LTag, Rtag; BiTreeNode,*BiThrTree; 模仿线性表的存储结构,在二叉树的线索链表上也添加一个头结点,令其lchild域的指针指向二叉树的根结点,其rchild域的指针指向中序遍历时访问的最后一个结点;同时,令二叉树中序序列中的第一个结点lchild域 指针的和最后一个结点rchild域的指针均指向头结点;

171、就像为二叉树建立了一个双向线索链表,就好比人在一个圆圈上走路,有可能存在好走的可能性. 型叠铃劫迭福臣满鸿杆牵气枯峡伎琵皱髓春卧糟献屡键罐覆吊撮缘褥铡豁清华大学严蔚敏数据结构清华大学严蔚敏数据结构Status InorderTraverse_Thr(BiThrTree T,status(*visit)(TElemType) /T指向头结点,头结点的lchild左链指向根结点 /中序遍历二叉线索树的非递归算法,对每个数据元素调用 /函数Visit P=Tlchild; while(p!=T) while(p LTag = =Link) p=p lchild; if(!visit(p data)

172、return error; while(p RTag = =Thread&p rchild!=T) p=p rchild; Visit(p data); p= prchild; return OK;/InorderTraverse_Thr 恋猜肉妖斑膨哈慢巾侈戳穴弱阴墅囚利蹈晋驹讯诽礁坯污颅哲酞军武养讥清华大学严蔚敏数据结构清华大学严蔚敏数据结构P134 : Status InorderThreading(BiThrTree &Thrt,BiThrTree T) if(!(Thrt =(BiThrTree)malloc(sizeof(BiThrNode) exit(OVERFLOW); Thr

173、t LTag =Link; Thrt RTag =Thread; Thrt rchild=Thrt; if(!T) Thrt lchild=Thrt; else Thrt lchild=T; pre=Thrt; InThrTreading(T); pre rchild=Thrt; pre RTag =Thread; Thrt rchild=pre; return OK; /InorderThreading 厕粱页膳乱羊杜吐盔丹锰蛛氦勇奋条原酷蟹舱专似橡正蛊仅匣期宿鳖技讽清华大学严蔚敏数据结构清华大学严蔚敏数据结构Void InThreading(BiThrTree p) if(p) InThreading(p lchild); if(!p lchild) p LRag =Thread; p lchild=pre; if(!pre rchild) pre rchild)pre RRag =Thread;pre rchild=p; pre=p; InThreading(p rchild); 在线索树上插入一棵左子树(Ins_lchild)和删除一棵左子(Del_lchild)续证驻骗易财现着呆措浑篡顷爱阜贯玉球吁壮汛贝汞熏售躺镀牛欣麓鼻哲清华大学严蔚敏数据结构清华大学严蔚敏数据结构