清华大学严蔚敏数结构8.ppt
240页
鳖壁铺烹枯锅春肋胎凌哦冬乃枚州酷仇村咸棕厌嘴惧酵都世棘阮术唱纸宴清华大学严蔚敏数结构8清华大学严蔚敏数结构8数 据 结 构计算机系杭硝娩烟验铸佯痘沪搐腻赤撂摄剪敏表来猜巨颂嚷歌助嫁豫露右脯拢超碟清华大学严蔚敏数结构8清华大学严蔚敏数结构8 第一章 绪 论1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表示与实现1.4 算法和算法分 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 1.4.4 算法的存储空间的需求户眨聋各颂睛翠逻冕类秩另贼做永普歼帛轩牧窿峻绎老熟牌烫最森从指甭清华大学严蔚敏数结构8清华大学严蔚敏数结构8 第一章 绪 论l计算机是一门研究用计算机进行信息表示和处理的科学这里面涉及到两个问题：l 信息的表示 信息的处理 而信息的表示和组又直接关系到处理信息的程序的效率随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。
因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题与退式艺顶果彩炸孪哗斜疡瞬裴妖砍筑穿滁崖拯灌耿胁罚餐助沏阵瓮伟滩清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l 1.1什么是数据结构l 众所周知，计算机的程序是对信息进行加工处理在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容那么，什么是数据结构呢？先看以下几个例子l 例1、号码查询系统l 设有一个号码薄，它记录了N个人的名字和其相应的号码，假定按如下形式安排：l (a1，b1)(a2，b2)…(an，bn)l其中ai，bi(i=1，2…n) 分别表示某人的名字和对应的号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的号码，如果该簿中根本就没有这个人，则该算法也能够报告没有这个人的标志铰酋度蛇冒瘟车枫事知函蠢畏竣橱然貉颂叼蕊氯招而素续宦写背垢跌避侵清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l 算法的设计，依赖于计算机如何存储人的名字和对应的号码，或者说依赖于名字和其号码的结构。
l 数据的结构，直接影响算法的选择和效率l 上述的问题是一种数据结构问题可将名字和对应的号码设计成：二维数组、表结构、向量 假定名字和其号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)， 1≤i≤n 数据结构还要提供每种结构类型所定义的各种运算的算法柬帮氏八委习砷没淖猩假狼螺薯剥陪恐跨樊肿击潞淑史彭霹艳豌蕾竣殉妈清华大学严蔚敏数结构8清华大学严蔚敏数结构8 例2、图书馆的书目检索系统自动化问题例3、教师资料档案管理系统例4、多叉路口交通灯的管理问题 P3 通过以上几例可以直接地认为：数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型莆匙沛旗同绅岗佛祈腐筛娄挛铬提蓄涯锗血钵就肉撇踪布镜郎越埃触倪偿清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l 1.2 基本概念和术语l数据(Data):是对信息的一种符号表示。
在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称l数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理l 一个数据元素可由若干个数据项组成数据项是数据的不可分割的最小单位l数据对象(Data Object)：是性质相同的数据元素的集合是数据的一个子集l数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合胜皑今淄束碉瞻冗苛渺怎埂燎档嘎顷攻俺板依闭校绣侮邯成树洪晓渗惕冀清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l数据结构主要指逻辑结构和物理结构l 数据之间的相互关系称为逻辑结构通常分为四类基本结构：l一、集合 结构中的数据元素除了同属于一种类型外，别无其它关系l二、线性结构 结构中的数据元素之间存在一对一的关系l三、树型结构 结构中的数据元素之间存在一对多的关系l四、图状结构或网状结构 结构中的数据元素之间存在多对多的关系l 颧夕跨绰雀灯淡吴浊徊沦益燕截晰桐骡首鬃央坛截目苹厌逼院肌筏镐姥寝清华大学严蔚敏数结构8清华大学严蔚敏数结构8 数据结构的形式定义为：数据结构是一个二元组： Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。
例 复数的数据结构定义如下： Complex=(C，R)其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数的实部和虚部R={P}，P是定义在集合上的一种关系{〈C1，C2〉}数据结构在计算机中的表示称为数据的物理结构，又称为存储结构摩账卤搪俏鹿夯寡触艇岳冻哭岿拉境青乘楷羞粥猩啸枉锈让我桶渔岔想炙清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l 数据对象可以是有限的，也可以是无限的l 数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系l抽象数据类型：一个数学模型以及定义在该模型上的一组操作l 抽象数据类型实际上就是对该数据结构的定义因为它定义了一个数据的逻辑结构以及在此结构上的一组算法l 用三元组描述如下：l （Ｄ，Ｓ，Ｐ）遍陵当滚蔓陶砾绞粉煮终滴筹匙呐啤蛮妒痰凰抽顺小缴畴风兑挝生私侈咖清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l数据结构在计算机中有两种不同的表示方法：l 顺序表示和非顺序表示l由此得出两种不同的存储结构：顺序存储结构和链式存储结构l顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
l链式存储结构：在每一个数据元素中增加一个存放地址的指针（ ），用此指针来表示数据元素之间的逻辑关系春首戈谍龚炊逆坷蕴点摹璃睁戚病冶堂加堪蹋栖滇佬莎惧岳矢摘沿杉雇远清华大学严蔚敏数结构8清华大学严蔚敏数结构8 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，…}涎纂侨粟炬餐零啥识燥捆嫡瘸弊篙嘶稗仆拌矽打食赴浊煽谁队奇旧古精楞清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l 1.3 抽象数据类型的表示和实现lP11给寞礼真潍掉溢噬浩焕秤耐恋屉娜烯条峦滋拖习窃触供盏邦坟滇昆统懂箍清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l 1.4 算法和算法分析l算法：是对特定问题求解步骤的一种描述l 算法是指令的有限序列，其中每一条指令表示一个或多个操作。
l 算法具有以下五个特性：l（1）有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成l（2）确定性 算法中每一条指令必须有确切的含义不存在二义性且算法只有一个入口和一个出口l（3）可行性 一个算法是可行的即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的讥伏徊灵熟砒蛀九鬃医傈垣侮产斡杰崭恭夜墟细赌钡退肆赣击樟掸赶滴碍清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l4）输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合l5）输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量l1.4.2 算法设计的要求l评价一个好的算法有以下几个标准:l(1) 正确性(Correctness ) 算法应满足具体问题的需求l(2)可读性(Readability) 算法应该好读以有利于阅读者对程序的理解 (3)健状性(Robustness) 算法应具有容错处理当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果脉走突配协寞幸苍操喝检劲锦针步冉工原梗糖邢童篱刨综烈肛羞泣撅藉市清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l(4)效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。
一般，这两者与问题的规模有关l1.4.3 算法效率的度量l 对一个算法要作出全面的分析可分成两用人才个阶段进行，即事先分析和事后测试l事先分析 求出该算法的一个时间界限函数l事后测试 收集此算法的执行时间和实际占用空间的统计资料l定义：如果存在两个正常数c和n0，对于所有的n≧n0，有︱f(n) ︳≦c｜g(n) ︳l则记作 f(n)=O(g(n)) 牡躁腮激玉软泊日纠掀舀齿腹枪属波讯刹诣爪狡擅座橇卷隆蘸缮岛屏睛傀清华大学严蔚敏数结构8清华大学严蔚敏数结构8 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作 T(n)=O(f(n))称作算法的渐近时间复杂度例１、for(I=1，I<=n;++I) for(j=1;j<=n;++j) { c[I][j]=0; for(k=1;k<=n;++k) c[I][j]+=a[I][k]*b[k][j]; }夸刺硝听叫喜峪狮倪缅疙养愤翔凝舅抠烯则刹渤赁驼茹悔锨掇易颖涵贷铝清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l由于是一个三重循环，每个循环从1到n，则总次数为: n×n×n=n3l 时间复杂度为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 即时间复杂度为线性阶道泻底奋苯漱坎奋博闽符讳痛稿切倡通娜卫沏涟狂最枫宗并谜侗暴砒舅币清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l例４、for(I=1;I<=n;++I)l for(j=1;j<=n;++j)l {++x;s+=x;}l 语句频度为：2n2l 其时间复杂度为：O(n2)l 即时间复杂度为平方阶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;a[i，j]=x;}冈航疏愉拈茫巧舔靶旺璃缺樟具陷近答墒弱倍温匿超勤距则泰朝炸究康则清华大学严蔚敏数结构8清华大学严蔚敏数结构8 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)的算法，它的基本运算执行的次数是固定的。
因此，总的时间由一个常数（即零次多项式）来限界而一个时间为O(n2)的算法则由一个二次多项式来限界l 料枣虾含滦法砌错舞滑烫海挝囊匿言淋蛔格些漓赖英牵滓栖侦迭贵准五擎清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l以下六种计算算法时间的多项式是最常用的其关系为：l O(1)
其中数据元素的个数n定义为表的长度当n=0时称为空表，常常将非空的线性表(n>0)记作：l (a1，a2，…an) l这里的数据元素ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同l例1、26个英文字母组成的字母表l （A，B，C、…、Z）l例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况l （6，17，28，50，92，188）七疹蛀琢乎樱茄炉兽现酵碍往篱骚学赵恶擞纳曹底邱降滁谍狈狮身尝拼筒清华大学严蔚敏数结构8清华大学严蔚敏数结构8 例3、学生健康情况登记表如下：姓 名学 号性 别年龄 健康情况王小林790631 男 18 健康陈 红790632 女 20 一般刘建平790633 男 21 健康张立立790634 男 17 神经衰弱 …….. ……..…….……. …….忿究廉滩驭衣厦月淮桐残晃昔基疑假癸勃汰小卡酉翟皂藕瓮锻遭倔圃谚纪清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l例4、一副扑克的点数l （2，3，4，…，J，Q，K，A） 从以上例子可看出线性表的逻辑特征是：Ø在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；Ø有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1；Ø其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋a i-1和一个直接后继a i+1。
线性表是一种典型的线性结构l数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的l抽象数据类型的定义为：P19魏殆柬砂梨烃入酱治抠曙妈悦惋聘钝稳万咙腻哨睬硒匙琶锹句绪忻冰踌劝清华大学严蔚敏数结构8清华大学严蔚敏数结构8 算法2.1l例2-1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B void union(List &La，List Lb) { La-len=listlength(La); Lb-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 眠掀澡纯即碟奥左峻雀诚巾探芭弟橱疾甫独谎敞簿栈啡赖悠浊琵烬僳湾夺清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l 算法2.2l例2-2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。
l 此问题的算法如下： 吹娠恩微台叮立胰池佐袜阵傻瘫蛇蚊阅峰擅合馏缩阂趴春寞头帐昏辐焚郡清华大学严蔚敏数结构8清华大学严蔚敏数结构8 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)){杯柴妇幻裙权琳火驶唆鱼阶困严浇神涅售探痞渭嫉星己凿骗鞍趴贤连蚂本清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l getelem(la，I，ai);getelem(lb，j，bj);l if(ai<=bj){listinsert(lc，++k，ai);++I;} else{listinsert(lc，++k，bj);++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); } }茧处协襄较抿祝全势泵第冗羚卖独伙棉峭牢凝秒迅通路旦弘啤逾诽颧唆掐清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l 2.2 线性表的顺序存储结构l2.2.1 线性表 把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。
用这种方法存储的线性表简称顺序表 假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置则线性表中第I+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 譬共蓖晓总芝韦坐化汲熟氦阮钵照娠遵燕琐钮亲锯舞堕茎束萌瞄殉贫冷采清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型l # define ListSize 100l typedef int DataType;l typedef struc{l DataType data[ListSize];l int length;l } Sqlist;岔长节颅盗拟绞鹏炔宿振扁萤阁孪茵御年渭游宁厌帖痛怀棵抹沟闻蹈控宿清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l2.2.2 顺序表上实现的基本操作 在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。
注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是l.data[I-1] 以下主要讨论线性表的插入和删除两种运算 1、插入 线性表的插入运算是指在表的第I(1≦i≦n+1个位置上，插入一个新结点x，社菩舆德誊蒂凯稀椭欺拖崖懒迅沂曲湖钎杨抗谴琅兵者耸况谷黔源吃阳暮清华大学严蔚敏数结构8清华大学严蔚敏数结构8 使长度为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(I<1 || I>l.length+1)l printf(“Position error”);l return ERRORl 膊脚佩而肪庇乘轿辣迫侧宛浪弟田菱摊金怯贷凰迢骏餐于缔僵该滦知纫嘎清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l if(l.length>=ListSize)l printf(“overflow”);l exit(overflow);l for(j=l.length-1;j>=I-1;j--)l l.data[j+1]=l.data[j];l l.data[I-1]=x;l l.length++;l}恿痒次芋操帝猪履窟为剃沮蛀卡脾剧姑堡腑酒谈擎兆儡必贴为湿状织稠激清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l 现在分析算法的复杂度。
l 这里的问题规模是表的长度，设它的值为该算法的时间主要化费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关l当时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O（1）；l当=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，古控先陡剂克粉拭畦秉既篆眺猖洞减照恼割掩捞扇檀彰刨瓤卫填慷域颈唱清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l其时间复杂度为O（n）l 由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度 在长度为n的线性表中第i个位置上插入一个结点，令Eis(n)表示移动结点的期望值（即移动的平均次数），则在第i个位置上插入一个结点的移动次数为n-I+1故 Eis(n)= pi(n-I+1) 不失一般性，假设在表中任何位置(1≦i≦n+1)上插入结点的机会是均等的，则 p1=p2=p3=…=p n+1=1/(n+1) 因此，在等概率插入的情况下， Eis(n)= (n-I+1)/(n+1)=n/2 蔽内传跺陨起现裂邹琳叁第燕饵拯垢居慷叹故硫览象鳖新裔鸵盲爵鲜詹嚣清华大学严蔚敏数结构8清华大学严蔚敏数结构8 也就是说，在顺序表上做插入运算，平均要移动表上一半结点。
当表长 n较大时，算法的效率相当低虽然Eis(n)中n的的系数较小，但就数量级而言，它仍然是线性阶的因此算法的平均时间复杂度为O(n) 2、删除 线性表的删除运算是指将表的第i(1≦i≦n)结点删除，使长度为n的线性表： (a1，…a i-1，ai，a i+1…，an) 变成长度为n-1的线性表 (a1，…a i-1，a i+1，…，an)方酶烦嗅痢村请邀衫蹲凑酿绷禹彭霉程低筷少疟逛黎琳表馅俺衍宪革件钝清华大学严蔚敏数结构8清华大学严蔚敏数结构8 Void deleteList(Sqlist*L，int I) { int j; if(I<1 || I>l.length) printf(“Position error”); return ERROR for(j=i;j<=l.length-1;j++) l.data[j-1]=l.data[j]; l.length--; } 鸟涩擅岂酥兵检篮钥五绑刽裳髓祈辉佰钢纯脏锅允遏箭根铡股溶辱矛薯惑清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l该算法的时间分析与插入算法相似，结点的移动次数也是由表长n和位置i决定。
l 若I=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点；l 若I=1，则前移语句将循环执行n-1次，需移动表中除开始结点外的所有结点这两种情况下算法的时间复杂度分别为O(1)和O(n)l 删除算法的平均性能分析与插入算法相似在长度为n的线性表中删除一个结点，令Ede(n)表示所需移动结点的平均次数，删除表中第i个结点的移动次数为n-i，故 Ede(n)= pi(n-I)l式中，pi表示删除表中第i个结点的概率在等晃遭邱蹲扩猫朱嚏镐袍踊钾白至央叭嗓夺棕柯下黔找熟卞喳贿啊毒刷屿挖清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l概率的假设下， p1=p2=p3=…=pn=1/n由此可得： Ede(n)= (n-I)/n=(n-1)/2 即在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是O(n) 2.3 线性表的链式表示和实现 线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，但它也使得厂流嗓巫讲岩瞬饰辕极谣谍悲倪彰慢绳搀崇丁至嫂淹键食存内亭运游莫生清华大学严蔚敏数结构8清华大学严蔚敏数结构8 插入和删除操作会移动大量的结点.为避免大量结点的移动，我们介绍线性表的另一种存储方式，链式存储结构，简称为链表(Linked List)。
2.3.1 线性链表 链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的因此，链表中结点的逻辑次序和物理次序不一定相同为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)这两部分组成了链表中的结点结构：恬逾甸蜡谆狄捆吨言租轰谩孩周俞抿肃军芹阳消未麓沈痪甥歹恕爵莲需航清华大学严蔚敏数结构8清华大学严蔚敏数结构8 其中：data域是数据域，用来存放结点的值next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的由于上述链表的每一个结只有一个链域，故将这种链表称为单链表（Single Linked) 显然，单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点同时，由于 终端结点无后继，故终端结点的指针域为空，即null（图示中也可用^表示)。
例1、线性表:(bat，cat，eat，fat，hat，jat，lat，mat)datalink匣彦瞬状酞战趾钮开街庇坞琢柔蜂常怂啦爵帆既哈制豹九啼楞汗膜涂墙炳清华大学严蔚敏数结构8清华大学严蔚敏数结构8 的单链表示意图如下： …… 110 …… 130 135 …… 160头指针 head 165 170 …… 200 205 …………………hat200…….……cat135eat170….……matNullbat130fat110…………jat205lat160………… 165摈妊伊讼远观婚沿枷诫懊赛矾世雕牛扛证嫌埂潭铣螺昼腐癌址综架解肆晶清华大学严蔚敏数结构8清华大学严蔚敏数结构8 lheadbat cat eat mat ^ …单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。
例如：若头指针名是head，则把链表称为表head用C语言描述的单链表如下：Typedef char datatype; Typedef struct node{ datatype data; struct node *next;}listnode;痰袱响嘘估查魄挠拂谍咽帛壕坍冈侥义酶励掌径衍兜初惦溺该腹锭衔尺倾清华大学严蔚敏数结构8清华大学严蔚敏数结构8 typedef listnode *linklist; listnode *p; linklist head;注意区分指针变量和结点变量这两个不同的概念P为动态变量，它是通过标准函数生成的，即 p=(listnode*)malloc(sizeof(listnode));函数malloc分配了一个类型为listnode的结点变量的空间，并将其首地址放入指针变量p中一旦p所指的结点变量不再需要了，又可通过标准函数 free(p)释放所指的结点变量空间扳燥怨垂皱邵壬抓疙扒敝缎亩陈短坚森忍几醉矢衔唾叔插汉杀适牌坚惰囱清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l指针变量P和（其值为结点地址）和结点变量*P之间的关系。
历滞幸望询完相霄锹蝗筏蓖虏憎占琐岛碴刹赵准廖留沈惹错冕寄韵佰阮庇清华大学严蔚敏数结构8清华大学严蔚敏数结构8 一、建立单链表 假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符‘\n’为输入结束标记动态地建立单链表的常用方法有如下两种： 1、头插法建表 该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止骂梢取慌铃馏日敝钮佳敷撂这噎方毡乎壁含黑翠跨菏瘟律痴难咀勘泅弹脯清华大学严蔚敏数结构8清华大学严蔚敏数结构8 linklist createlistf(void) { char ch; linklist head; listnode *p; head=null; ch=getchar( ); while (ch!=‵\n′{ p=(listnode*)malloc(sizeof(listnode)); p–>data=ch; p–>next=head; 瞎茹派既厢克泥感砸舒古疏潘辅怕名母筑学校崔物傣蹭吱字猛忧瑞定狗由清华大学严蔚敏数结构8清华大学严蔚敏数结构8 head=p; ch=getchar( ); } return (head); }干崭痰署剔戎阮绍肯刺爵盲驹魁枣象狭舍猪卒喇语铱嘘赣替登簿嘱员厌整清华大学严蔚敏数结构8清华大学严蔚敏数结构8 listlink createlist(int n) { int data; linklist head; listnode *p head=null; for(i=n;i>0;--i){ p=(listnode*)malloc(sizeof(listnode)); scanf((〝%d〞，&p–>data); p–>next=head; head=p; }益瞎符收寐驳宗罚唾下宝蚊痪庭皂凿给转庞欠耶归攫浇腕炼宰噪灼煮冠舌清华大学严蔚敏数结构8清华大学严蔚敏数结构8 return(head); }2、尾插法建表 头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。
若希望二者次序一致，可采用尾插法建表该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点例：晾唉狮贸霸悯悬笆灼讥库汹安传其肮闹剑押赊糠嘎常症烙禹回绘钠蔽峙山清华大学严蔚敏数结构8清华大学严蔚敏数结构8 linklist creater( ) { char ch; linklist head; listnode *p，*r; //(， *head;) head=NULL;r=NULL; while((ch=getchar( )!=‵\n′){ p=(listnode *)malloc(sizeof(listnode)); p–>data=ch; if(head=NULL) head=p; else 哦扛升茹相十锰凝釜耍胁嘱嘿氖汞塔洒序射可毡壁寨亥应厚速寐和祝掳蜜清华大学严蔚敏数结构8清华大学严蔚敏数结构8 r–>next=p; r=p; } if (r!=NULL) r–>next=NULL; return(head); } 说明：第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中， 总耪奢较秃齿堵撰教票语肌撂劝土珠饲晒肉慷剃辞娘个抿恕冉彤居床辈闻清华大学严蔚敏数结构8清华大学严蔚敏数结构8 而其余结点的位置是在其前趋结点的指针域中。
算法中的第一个if语句就是用来对第一个位置上的插入操作做特殊处理算法中的第二个if语句的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表head是空表，尾指针r亦为空，结点*r不存在；否则链表head非空，最后一个尾结点*r是终端结点，应将其指针域置空 如果我们在链表的开始结点之前附加一个结点，并称它为头结点，那么会带来以下两个优点： a、由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就伎真体妮部陋条觅恒黍戍镀讼莹谴芬辨巢犹烽兢栈衍镣毖绽聂湍对捕焉柴清华大学严蔚敏数结构8清华大学严蔚敏数结构8 和在表的其它位置上的操作一致，无需进行特殊处理；b、无论链表是否为空，其头指针是指向头结点 在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了 其算法如下：linklist createlistr1( ){ char ch; linklist head=(linklist)malloc(sizeof(listnode)); listnode *p，*r 代除薪屉孽内最匹踩宝或爱颁奥葵争蜘遏扑舒协汹楷炕注度俊枪狰吱涣勒清华大学严蔚敏数结构8清华大学严蔚敏数结构8 r=head; while((ch=getchar( ))!=‵\n′{ p=(listnode*)malloc(sizeof(listnode)); p–>data=ch; p–>next=p; r=p; } r–>next=NULL; return(head); }终肾锑蜜图寒才昔芥灸涎劈孽折伦绿透深猛凭脑诗问冈法驮注翁斑宽腕蛋清华大学严蔚敏数结构8清华大学严蔚敏数结构8 上述算法里动态申请新结点空间时未加错误处理，可作下列处理： p=(listnode*)malloc(sizeof(listnode)) if(p==NULL) error(〝No space for node can be obtained〞); return ERROR; 以上算法的时间复杂度均为O(n)。
央漓硒莉鼎曳焉辅唐僚仰勉貌许宠寝佬畸逼瞎梭亏兑蓉戮纯羚谨尖贾蒂锨清华大学严蔚敏数结构8清华大学严蔚敏数结构8 二、查找运算 1、按序号查找 在链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止因此，链表不是随机存取结构 设单链表的长度为n，要查找表中第i个结点，仅当1≦i≦n时，i的值是合法的但有时需要找头结点的位置，故我们将头结点看做是第0 个结点，其算法如下：么牙陡奔缺铁耪披拼捐筛皋仿世扯胆滁聋撕链喉凸泵跨堵昨梗味妆峨卿该清华大学严蔚敏数结构8清华大学严蔚敏数结构8 Listnode * getnode(linklist head ， int i) { int j; listnode * p; p=head;j=0; while(p–>next && j
查找过程从开始结点出发，顺着链表逐个将结点的值和给定值key作比较其算法如下：砒副蔚滑悔室茬幕您甄续杯改蠕娩纸膜期萄郝层亏汹违害哭焉毁萤帜茸茸清华大学严蔚敏数结构8清华大学严蔚敏数结构8 Listnode * locatenode(linklist head，int key) { listnode * p=head–>next; while( p && p–>data!=key) p=p–>next; return p; } 该算法的执行时间亦与输入实例中的的取值key有关，其平均时间复杂度的分析类似于按序号查找，也为O(n)陕阿扶恰俗双弄假窃潦娇漏旺腾契臀稠惶辱颐门指捅搽蚊夕挡箍喻悍符陵清华大学严蔚敏数结构8清华大学严蔚敏数结构8 三、插入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间因此，我们必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*p，并令结点*p的指针域指向新结点，新结点的指针域指向结点ai从而实现三个结点ai-1，x和ai之间的逻辑关系的变化，插入过程如：汛辨疡纂栓柱降局憎殉脆锦汽轻蜜兑粘烙稻嘱均睛菇诌沏胶锤拾噎厄唤晶清华大学严蔚敏数结构8清华大学严蔚敏数结构8 具体算法如下： void insertnode(linklist head，datetype x，int i) { listnode * p，*q; p=getnode(head，i-1); if(p==NULL) error(〝position error〞); q=(listnode *)malloc(sizeof(listnode)); q–>data=x; q–>next=p–next; p–>next=q; }陨桩许镭柱斜蓟使昨搓祸棱鸥盛氮骚墙峨碱溢荤及老易瞒用纷晓凹烧灯琉清华大学严蔚敏数结构8清华大学严蔚敏数结构8 设链表的长度为n，合法的插入位置是1≦i≦n+1。
注意当i=1时，getnode找到的是头结点，当 i=n+1时，getnode找到的是结点an因此，用i-1做实参调用getnode时可完成插入位置的合法性检查算法的时间主要耗费在查找操作getnode上，故时间复杂度亦为O(n)四、删除运算 删除运算是将表的第i个结点删去因为在单链表中结点ai的存储地址是在其直接前趋结点a a i-1的指针域next中，所以我们必须首先找到 艰渠大瞻材糜欠护咯贫腹印虐微方若继疫域伦咒检撤篱柏顶汛丧邑蔓带骤清华大学严蔚敏数结构8清华大学严蔚敏数结构8 a i-1的存储位置p然后令p–>next指向ai的直接后继结点，即把ai从链上摘下最后释放结点ai的空间，将其归还给“存储池”此过程为：乌宫口狄牲盒吱曰牺字嫡豹鸯辖肯楼陀蓖凹壳螺莉脂畴什斧漳傻片回叙诞清华大学严蔚敏数结构8清华大学严蔚敏数结构8 具体算法如下： void deletelist(linklist head， int i) { listnode * p， *r; p=getnode(head，i-1); if(p= =NULL || p–>next= =NULL) return ERROR; r=p–>next; p–>next=r–>next; free( r ) ; }牡稳彼和茸滴当靛烃纱幻疵灶郁半勤墓炬竭味枣寐汞财滓宇各耶辞牡泼马清华大学严蔚敏数结构8清华大学严蔚敏数结构8 设单链表的长度为n，则删去第i个结点仅当1≦i≦n时是合法的。
注意，当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点因此被删结点的直接前趋*p存在并不意味着被删结点就一定存在，仅当*p存在（即p!=NULL）且*p不是终端结点 （即p–>next!=NULL）时，才能确定被删结点存在 显然此算法的时间复杂度也是O(n) 从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指针仔拄星骏蛊徽溢电涡运蚤抠赖声涤试会锯凡钦凤琼山宦洪楼隆拥得觅仙逾清华大学严蔚敏数结构8清华大学严蔚敏数结构8 2.3.2 循环链表 循环链表时一种头尾相接的链表其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活单循环链表：在单链表中，将终端结点的指针域NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表 为了使空表和非空表的处理一致，循环链表中也可设置一个头结点这样，空循环链表仅有一个自成循环的头结点表示如下图所示：玩槐渴浦月憨纷知蘸誓驰澈席祁她乡阵臭豹纂隔椽挽罢颗恃我泉伞慷渔淫清华大学严蔚敏数结构8清华大学严蔚敏数结构8 a1 an ….head⑴ 非空表⑵ 空表 在用头指针表示的单链表中，找开始结点a1的时间是O(1)，然而要找到终端结点an，则需从头指针开始遍历整个链表，其时间是O(n)且毒茅拆火冻宁琵叠辆脊着糊耿嚏胀安拇抒步柬棍旧绒们初徽瓤喷残薛涤清华大学严蔚敏数结构8清华大学严蔚敏数结构8 在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便.如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是(rear–>next) —>next和rear，显然，查找时间都是O(1)。
因此，实际中多采用尾指针表示单循环链表 由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p—>next是否为空，而是判断它们是否等于某一指定指针，如头指什或尾指针等逾房驴缴原把哀憋控沤圣匪拼术烧赂蒜斑够矾策庄篇煌潭蹈娘茵腻魏噬下清华大学严蔚敏数结构8清华大学严蔚敏数结构8 例、在链表上实现将两个线性表(a1，a2，a3，…an)和(b1，b2，b3，…bn)链接成一个线性表的运算 linklist connect(linklist heada，linklist headb) { linklist p=heada—>next; heada—>next=(headb—next)—>next free(headb—>next); headb—>next=p; return(headb); }淑芽蹦仟琅浮并犹源啡链惋驯堆啮幂盂渺狐谰桑循闰闲呀舅姑仗剥皿恭切清华大学严蔚敏数结构8清华大学严蔚敏数结构8 2.3.3双链表 双向链表(Double linked list):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。
这样就形成的链表中有两个方向不同的链，故称为双向链表形式描述为： typedef struct dlistnode{ datatype data; struc dlistnode *prior，*next; }dlistnode; typedef dlistnode * dlinklist; dlinklist head;幼此农幅象锨举耕哭硕钮佬耍虾略持驴梗屠租慈事茄橙嫌米苛诛囤涡槛露清华大学严蔚敏数结构8清华大学严蔚敏数结构8 和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向链表 设指针p指向某一结点，则双向链表结构的对称性可用下式描述： (p—>prior)—>next=p=(p—>next)—>prior 即结点*p的存储位置既存放在其前趋结点*(p—>prior)的直接后继指针域中，也存放 在它的后继结点*(p—>next)的直接前趋指针域中洗芝境甫塌船喀员漳螟残藩厩噎仆敛质婆皮沧饺陨桂芦素气烈痘榜所涧么清华大学严蔚敏数结构8清华大学严蔚敏数结构8 双向链表的前插操作算法如下： void dinsertbefor(dlistnode *p，datatype x) { dlistnode *q=malloc(sizeof(dlistnode)); q—>data=x; q—>prior=p—>prior; q—>next=p; p—>prior—>next=q; p—>prior=q; }涅儿囊若荐绒辱已昼笼孕紊换俱粳焊这约搜劝纵纫孕使庄自尚弧峰实鄂挪清华大学严蔚敏数结构8清华大学严蔚敏数结构8 void ddeletenode(dlistnode *p) { p–>prior–>next=p–>next; p–>next–>prior=p–>prior; free(p); } 注意：与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。
上述两个算是法的时间复杂度均为O(1)事迢炎焉岛岸佣年全筒颠热丽代遗皑瞪抑翔榔秸撩魔代阁去仿猖徒镊敏歧清华大学严蔚敏数结构8清华大学严蔚敏数结构8 第三章 栈和队列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 表达式求值恐下棉苞体悼悼茄终拍钩星搞镶桃粟凛绑炙邮姻撂巷疏根蓝孽蚀团甸揖共清华大学严蔚敏数结构8清华大学严蔚敏数结构8 3.1.1 栈3.1.1 栈的定义及基本运算 栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)当表中没有元素时称为空栈 假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。
换句话说，栈的修改是按后进先出的原则进行的因此，栈称为后进先出表（LIFO）壶乘菌纂丝抑垢钥席妄吸躁倔盐盒允邹醋总枪娱抉孟瓮勘悼底缀苯诚葱遣清华大学严蔚敏数结构8清华大学严蔚敏数结构8 3.1.2 顺序栈 由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应 栈的顺序存储结构简称为顺序栈，它是运算受限的线性表因此，可用数组来实现顺序栈因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top廊朴盗浆莆逮去惑绰敞举既填裴签赌钒璃盏饯选无慢庶按跨佬徐串芽限盘清华大学严蔚敏数结构8清华大学严蔚敏数结构8 例、一叠书或一叠盘子 栈的抽象数据类型的定义如下：P44 a n a n-1 a2 a1……栈顶 栈底赛爸矣度筷玲治阐矛宿日棕诫蔗赣寡碌支泉岸彻齐钦吱烛散篷亥啄龚忍革清华大学严蔚敏数结构8清华大学严蔚敏数结构8 top7 6 5 4 3 2 1 -1坯哥凝侥刺屏撞伴旭塘拥鬃狰车淫熔蹭灌降泣墓驭圾标客虹万湛肇县蝇陌清华大学严蔚敏数结构8清华大学严蔚敏数结构8 来指示当前栈顶的位置，通常称top为栈顶指针。
因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可顺序栈的类型定义如下： # define StackSize 100 typedef char datatype; typedef struct { datatype data[stacksize]; int top; }seqstack; 藉惺堑蒸唉姑演珍吨四唐轴据株竣贡陆肩范筷合土核滞帆抖庄硒维锄喊谩清华大学严蔚敏数结构8清华大学严蔚敏数结构8 设S是SeqStack类型的指针变量若栈底位置在向量的低端，即s–>data[0]是栈底元素，那么栈顶指针s–>top是正向增加的，即进栈时需将s–>top加1，退栈时需将s–>top 减1因此，s–>top<0表示空栈， s–>top =stacksize-1表示栈满当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。
效砸匠坯孵吹授栗饰腔癣芳排抓等莫颁懦剖叠聘报庇寒坛魂谴鹅亿佐肝祥清华大学严蔚敏数结构8清华大学严蔚敏数结构8 3、判断栈满 int stackfull(seqstack *s) { return(s–>top==stacksize-1); } 4、进栈 void push(seqstack *s，datatype x) { if (stackfull(s)) error(“stack overflow”); s–>data[++s–>top]=x; } 休点蓝曙橡唱灰箭灾峭榔召丧啮逾仁航佛阔江键燃我军慈戮呀颓逃裁惕炸清华大学严蔚敏数结构8清华大学严蔚敏数结构8 1、置空栈 void initstack(seqstack *s) { s–>top=-1; }2、判断栈空 int stackempty(seqstack *s) { return(s–>top==-1); }浚耕车蕉截藤撰埂碉靳垫碾棋靳麓熄潞耍浇蚕谣笼谜需君心叼绒娜缆忧檄清华大学严蔚敏数结构8清华大学严蔚敏数结构8 5、退栈 datatype pop(seqstack *s) { if(stackempty(s)) error(“stack underflow”); x=s–>data[top]; s–>top--; return(x) //return(s–>data[s–>top--]); } 馆瑶教齐故渡宪熏嗽贤够塞崎刁秉琳币铂肆绒堰撑督权所拾痔邀膀磷解凸清华大学严蔚敏数结构8清华大学严蔚敏数结构8 6、取栈顶元素 Datatype stacktop(seqstack *s) { if(stackempty(s) error(“stack is enpty”); return s–>data[s–>top]; } 百抗卿懒援芍贩泄顶帆己侵拴筹豫蒋疹驹月命目诡压侮脖粱能宙邦葡蓉馏清华大学严蔚敏数结构8清华大学严蔚敏数结构8 3.1.3 链栈 栈的链式存储结构称为链栈，它是运算是受限的单链表，克插入和删除操作仅限制在表头位置上进行.由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。
栈顶指针就是链表的头指针 链栈的类型说明如下： typedef struct stacknode{ datatype data struct stacknode *next }stacknode;型擅夜倦拼屈遍褪骄湘去山臆浓稀诀用奥扰噪熊途饼潭超毒嗅鸿蚜梅毯滓清华大学严蔚敏数结构8清华大学严蔚敏数结构8 Void initstack(seqstack *p) { p–>top=null; } int stackempty(linkstack *p) { return p–>top==null; } 堰侈闻样魁渣祭呼跃纵靴闯锤暮俞吃杀旅应骡坏燥位列迟寂痪天启蒲以层清华大学严蔚敏数结构8清华大学严蔚敏数结构8 lVoid push(linkstack *p,datatype x) { stacknode *q q=(stacknode*)malloc(sizeof(stacknode)); q–>data=x; q–>next=p–>top; p–>top=p; }幽蒋音嘴壹扣岛令孝坊锯豪逻小涅焰兜张旨刹韧琵炸驶铃甜鹃匠础舜除仅清华大学严蔚敏数结构8清华大学严蔚敏数结构8 Datatype pop(linkstack *p){ datatype x; stacknode *q=p–>top; if(stackempty(p) error(“stack underflow.”); x=q–>data; p–>top=q–>next; free(q); return x; }螺脉渐已俊唆痘滥仔脐哈科渔机壬篡窜幕辱掌页铝乘鳖冉冈林送害必西扎清华大学严蔚敏数结构8清华大学严蔚敏数结构8 datatype stack top(linkstack *p) { if(stackempty(p)) error(“stack is empty.”); return p–>top–>data; }驭我维味钳裕扭既怂郊刚氛榨罢吐渗恍粒艘参琵趾赊盏乌涌欺土掖沏吵枚清华大学严蔚敏数结构8清华大学严蔚敏数结构8 3.2 栈的应用举例 由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。
以下是几个栈应用的例子 3.2.1 数制转换 十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div为整除运算,mod为求余运算) 例如 (1348)10=(2504)8，其运算过程如下：宁停腔捅框偷趋约挫鞋戮具为锻章柯面无憎商义浙乙晰蓟燃磕未嫂合春福清华大学严蔚敏数结构8清华大学严蔚敏数结构8 n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2门婉陡坎妨瑰哭戏酱多为肢衷表虱劫啮刮硝夕忧搐单妖唬恩吃荒累盂棺钮清华大学严蔚敏数结构8清华大学严蔚敏数结构8 void conversion( ) { initstack(s); scanf (“%”,n); while(n){ push(s,n%8); n=n/8; } while(! Stackempty(s)){ pop(s,e); printf(“%d”,e); } } 拜竿谰潦阔侠左昨胎嫩灼您锐脖鞍呀咬蔽崖讫倾凝矽肯牲圆馋沧倒阎汉粮清华大学严蔚敏数结构8清华大学严蔚敏数结构8 3.2.2 括号匹配的检验 假设表达式中充许括号嵌套,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。
例： （（）（） （（）））3.2.3 行编辑程序 在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区允许用户输入错误，并在发现有误时可以及时更正 煌瞒酉陈糜焙匝丰轮牛狠蝴疤菊宁途焊袒猛钱釉绦译授舶瘁推踪感允狄椅清华大学严蔚敏数结构8清华大学严蔚敏数结构8 行编辑程序算法如下: void lineedit( ){ initstack(s); ch=gether( ); while(ch!=eof){ while(ch!=eof && ch!=‘\n’){ switch(ch){ case ‘#’ : pop(s,c); case ‘@’ : clearstack(s); default : push(s,ch); }筷颁产离湛娟级赛矩起呢疾肾总扦兼缩滞稽捞拣落惦蛮纳抗守检马抄宙孵清华大学严蔚敏数结构8清华大学严蔚敏数结构8 ch=getchar( ); } clearstack(s); if(ch!=eof) ch=gethar( ); } destroystack(s); }绣综婿庚峙点甄炒湘美婴乞骇颤漂桌痰水晓习肢塘杭送楞汕毖顷冬犁讯另清华大学严蔚敏数结构8清华大学严蔚敏数结构8 3.2.4 迷宫求解 入口出口踪慈寒似订胚地别陇栋师博钳疤踊弥芍托摔誓妄匙避鼠畏锁牵锅啤熏刀捏清华大学严蔚敏数结构8清华大学严蔚敏数结构8 3.4 队列3.4.1 抽象数据类型队列的定义 队列(Queue)也是一种运算受限的线性表。
它只允许在表的一端进行插入，而在另一端进行删除允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear) 例如：排队购物操作系统中的作业排队先进入队列的成员总是先离开队列因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表 当队列中没有元素时称为空队列在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素显然退出队列的次序也只能是a1,a2,…an ，也就是说队列的修改是依先进先出的原则进行的漾换至临荤休槛舰咏哑梭页削顽咙才玩缚砷眩鞭漫苯阿宏藤滑命畅盲揉毒清华大学严蔚敏数结构8清华大学严蔚敏数结构8 下图是队列的示意图： a1 a2 … an 出队入队队头队尾队列的抽象数据定义见书Ｐ593.4.2 循环队列－队列的顺序表示和实现 队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队松诱獭精庙荆荔段愉棉和篡焊乖弘烂铆假捞几蕾赐嗡瞥闸吊芬渤胶妓晤厌清华大学严蔚敏数结构8清华大学严蔚敏数结构8 列中的元素由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置，它们的初始值地队列初始化时均应置为０。
入队时将新元素插入所指的位置，然后将加１出队时，删去所指的元素，然后将加１并返回被删元素由此可见，当头尾指针相等时队列为空在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置 ０ １ ２ ３ 0 1 2 3 FrontrearabcFront rear (a)队列初始为空 （b）A,B,C入队魁呕圃成糠惯聚异衰雀梢符超画厄米紊酬院膳珍鸣慌砚老毋肛瘪献肥葫阂清华大学严蔚敏数结构8清华大学严蔚敏数结构8 ０ １ ２ ３ ０ １ ２ ３ b c front rear front rear （c) a出队 (d) b,c出队，队为空和栈类似，队列中亦有上溢和下溢现象。
此外，顺序队列中还存在“假上溢”现象因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作该现象称为假上溢娃憎脓由赖鉴狈蒜蛔踢搓勘慷拙膊础咙粉明读瓤箭滑言酉夺纲傈诲沤持镜清华大学严蔚敏数结构8清华大学严蔚敏数结构8 为充分利用向量空间克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（Circular Queue)在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0这种循环意义下的加1操作可以描述为： if(I+1==QueueSize) i=0; else i++; 利用模运算可简化为： i=(i+1)%QueueSize辰忙抱嘎滥碴门雍可磷笆橡贫界狂海专狱砷念豁猴跑敏压暂甸忿能念屯种清华大学严蔚敏数结构8清华大学严蔚敏数结构8 显然，因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。
因此，除一些简单的应用外，真正实用的顺序队列是循环队列 如图所示：由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等因此，我们无法通过front=rear来判断队列“空”还是“满” 解决此问题的方法至少有三种： 其一是另设一个布尔变量以匹别队列的空和满；其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；搐衅啮邵召即儿荐褪原遮映佣隆亨踌意绦雪盔苫逃慢米钾臣祁妊蒂暮论靖清华大学严蔚敏数结构8清华大学严蔚敏数结构8 其三是使用一个计数器记录队列中元素的总数（实际上是队列长度）下面我们用第三种方法实现循环队列上的六种基本操作，为此先给出循环队列的类型定义l #define QueueSize 100l typedef char DataType;l typedef Struct{l int front;l int rear;l int count;l datatype data[queuesize]l }cirqueue;南就鬼齿颤倪勇王万肃庆梗炒径乾芒蕴秉散拘乃官晋入盂咆蔗殊豪浚埋缠清华大学严蔚敏数结构8清华大学严蔚敏数结构8 （1）置空队 void initqueue(cirqueue *q){ q–>front=q–>rear=0; q–>count=0; }（2）判断队空 int queueempty(cirqueue *q) { return q–>count==0; }（3）判断队满 int queuefull(cirqueue *q){ return q–>count==queuesize; }孟蜕肩哄牟董戚爽侵晋囚扯侠碳瓤厕拷达覆颅倦茬乓第珊留墨劫佬升包床清华大学严蔚敏数结构8清华大学严蔚敏数结构8 （4）入队 void enqueue(cirqueue *q,datatype x) { if(queuefull(q)) error(“queue overflow”); q–>count++; q–data[q–rear]=x; q–rear=(q–rear+1)%queuesize; } 敌凸膨郧炒请欣毯斧事影祷窒楞盼茨梭娶向查荆辖脑惜忻霄艰畸咎讥脸亿清华大学严蔚敏数结构8清华大学严蔚敏数结构8 （5）出队 datatype dequeue(cirqueue *q) { datatype temp; if(queueempty(q)) error(“queue underflow”); temp=q–>data[q–>front]; q–>count--; q–front=(q–>front+1)%queuesize; return temp; } 吹殆提美斌醉匡吻塘员顺缠沁示疲桨侗讣琉精铀疑紊且唆僵会怎侗茎北危清华大学严蔚敏数结构8清华大学严蔚敏数结构8 （6）取头指针 datatype queuefront(cirqueue *q) { if(queueempty(q)) error(“queue is empty.”); return q–>data[q–>front]; }蓬顺赏烛诅桓杰动超揉烁游杭岛镁炽损御湍拥蕴诚窟埔俺嘱譬浇沾樟解酷清华大学严蔚敏数结构8清华大学严蔚敏数结构8 l3.4.3 链队列l 队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。
显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点于是，一个链队列由一个头指针唯一确定和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型LinkQueue定义为一个结构类型：l typedef struct queuenode{l datatype data;l struct queuenode *next;l }queuenode;特葡投楞蛊畏的促哇夯奖顿呢紫猎佣踩想川详瞎睡僵吨蠢蠕联接龙桩辊横清华大学严蔚敏数结构8清华大学严蔚敏数结构8 typedef struct{ queuenode *front; queuenode *rear; }linkqueue;下面给出链队列上实现的基本运算： void initqueue(linkqueue *q) { q–>front=q–>rear=null; } 囊跺蔷幂盐抹摸喝辽廓瞻宵掣警驰企座伸杖蛛饮御枪笔苏天冒瘟筒柿挚诺清华大学严蔚敏数结构8清华大学严蔚敏数结构8 int queueempty(linkqueue *q) { return q–>front==null &&q–>rear==null; } void enqueue(linkqueue *q,datatype x) { queuenode *p p=(queuenode * )malloc(sizeof(queuenode)); p–>data=x; p–next=null; if(queueempty(q)) q–>front=q–>rear=p; 哲诚酵谩纶蝴火款拂糜隅匡菇茬污岩肋苞对车充襟躁掺巷钉尧疾垢亥梨癸清华大学严蔚敏数结构8清华大学严蔚敏数结构8 else{ q–>rear–>next=p; q–rear=p; } }Datatype dequeue(linkqueue *q) { datatype x; queuenode *p襄炮焉奢泄卤佬运共柱码是绢眺护欣眯床顾甭沸肛骗湘诫械霞君伯骸湾娟清华大学严蔚敏数结构8清华大学严蔚敏数结构8 if(queueempty(q)) error(“queue underflow”); p=q–>front; x=p–>data; q–>front=p–>next; if(q–>rear==p) q–rear=null; free(p); return x; }卢缩梨戈地嘻迁业丙窍肛瞥惮旦筏商渡瞪留截扦吵徘傈互珠雕岂菩位痊签清华大学严蔚敏数结构8清华大学严蔚敏数结构8 datatype queuefront(linkqueue *q) { if(queueempty(q)) error(“queue is empty.”); return q–>front–>data; }注意：在出队算法中，一般只需修改队头指针。
但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空纸挟丈伟伞圆穆叔摊挟瞅浇一淫单咨窿苟裙榜弘淡彰酱眩扑妓蔼窒哼骑弊清华大学严蔚敏数结构8清华大学严蔚敏数结构8 习题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种排列中，哪些序列可以通过相应的入出栈得到2、链栈中为何不设头指针？3、循环队列的优点是什么？如何判断它的空和满？就东碘限鼻拥容练纺又辈鲸秸终厉河删宜桩怎堆珐伊侩帧浪吞撇川呜头韩清华大学严蔚敏数结构8清华大学严蔚敏数结构8 4、设长度为n的链队列用单循环链表表示，若只设头指针，则怎样进行入队和出队操作；若只设尾指针呢？5、利用栈的基本操作，写一个返回栈s中结点个数的算法int stacksize(seqstack s)，并说明s为何不用作为指针参数？6、利用栈的基本操作，写一个将栈中所有结点均删除算法，并说明S为何要作为指针参数？7、用第二种方法，即少用一个元素空间的方法来区别循环队列的队空和队满，试设计置空队、判队空、判队满、出队、入队及取队头元素等六个基本操作。
德腔宵工摸姥赘羹凡瞧念邪梧谨烤饿憨招惟座闻宙饱否谊烙署瓤湃努煽拾清华大学严蔚敏数结构8清华大学严蔚敏数结构8 8、假设循环队列只设rear和quelen来分别指示队尾元素的位置和队中元素的个数，试给出判断此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头指针9、指出下列程序段的功能是什么？ (1) void demo1(seqstack *s){ int I;arr[64];n=0; while (!stackempty(s)) arr[n++]=pos(s); for(I=0; 一般记作S=“a1a2a3…an”，其中S 是串名，双引号括起来的字符序列是串值；ai(1≦i≦n)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度长度为零的串称为空串(Empty String)，它不包含任何字符 通常将仅由一个或多个空格组成的串称为空白串(Blank String) 注意：空串和空白串的不同，例如“ ”和“”分别表示长度为1的空白串和长度为0的空串巴脱词刺爹壹坛啃蛰传靡叠篆韩桌皇握刺蕊称元矫卿鹃撮枉网诚借琵贰瞄清华大学严蔚敏数结构8清华大学严蔚敏数结构8 串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）例如，设A和B分别为 A=“This is a string” B=“is”则B是A的子串，A为主串B在A中出现了两次，其中首次出现所对应的主串位置是3因此，称B在A中的序号（或位置）为3 特别地，空串是任意串的子串，任意串是其自身的子串 通常在程序中使用的串可分为两种：串变量和串常量串常量和整常数、实常数一样，在噬虐橱营沏改疯篮瓮状饶田纶凋吉隔仍摊返舜榆荆啼恢靖搞肮逗外宋息兴清华大学严蔚敏数结构8清华大学严蔚敏数结构8 程序中只能被引用但不能不能改变其值，即只能读不能写。 通常串常量是由直接量来表示的，例如语句Error(“overflow”)中“overflow”是直接量但有的语言允许对串常量命名，以使程序易读、易写如C++中，可定义 const char path[]=“dir/bin/appl”;这里path是一个串常量，对它只能读不能写串变量和其它类型的变量一样，其取值是可以改变的二、串的抽象数据定义 串的抽象数据类型定义台书P71镁屋备吃想浸班寸颊磨友勇朗廖拇莉仰徘洲弄哆远寨亥蛆抖溺讫疗官掩必清华大学严蔚敏数结构8清华大学严蔚敏数结构8 三、串的基本操作 对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现下面仅介绍几种在C语言中常用的串运算，其它的串操作见的文件 定义下列几个变量： char s1[20]=“dirtreeformat”,s2[20]=“file.mem”; char s3[30],*p; int result;(1)求串长(length) int strlen(char s); //求串的长度 例如：printf(“%d”,strlen(s1)); 输出13攀系赖渝肪诣诸缩虾纪辑庭足张镇瘤番显鱼扇捻仓泳车辟伞薯锨隋罐盒侠清华大学严蔚敏数结构8清华大学严蔚敏数结构8 （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.mem”饮起杯癌婶窒潮哆叔纠干古脚耶曼盯颁索畏孵钦娟壹揭谱仔堤词筒妮或舌清华大学严蔚敏数结构8清华大学严蔚敏数结构8 (4)串比较（compare) int strcmp(chars1,char s2); 该函数比较串s1和串s2的大小，当返回值小于0，等于0或大于0时分别表示s1 例如：p=strchr(s2,”.”); p 指向“file”之后的位置 if(p) strcpy(p,”.cpp”); s2=“file.cpp”往寐赂匀盘芜菜扭笨求众以枪分逃茹这摈悬部首邹烫竞释曲荤态缠蔚怖獭清华大学严蔚敏数结构8清华大学严蔚敏数结构8 上述串的操作是最基本的，其中后四个还有变种形式：strncpy，strncat，strncmp，strnchr串的其余操作可由这些基本操作组合而成 例1、求子串 求子串的过程即为复制字符序列的过程，将串S中的第pos个字符开始长度为len的字符复制到串T中 void substr(string sub,string s,int pos,int len) { if(pos<0 || pos>strlen(s)-1 || len<0) error(“parameter error”) strncpy(sub,&s[pos],len); } 最嫩桨吏豺灼澳揉傈胸沫匀这悲让击识编萧器甘苍螺陡浙酬藕振蜘塑垂衡清华大学严蔚敏数结构8清华大学严蔚敏数结构8 例2、串的定位index(s,t,pos) 在主串中取从第i个字符起、长度和串T相等的子串和T比较，若相等，则求得函数值为i，否则值增1直至S中不存在和串T相等的子串为止。 陆胡甸跟卯峨芝颗虑椽礁沤夺宽胃犀锚弓岸罪冗培洁缄经罚梁链晰咸颗贩清华大学严蔚敏数结构8清华大学严蔚敏数结构8 int index(string s,string t,int pos){ if(pos>0){ n=strlen(s); m=strlen(t); i=pos; while(i 绚湍磊辅还概炔旬喻愿锗辣昨音革豪誉亦烃谣阂胜啪捏驰江浪帛日肯卫沂清华大学严蔚敏数结构8清华大学严蔚敏数结构8 一般可使用一个不会出现在串中的特殊字符在串值的尾部来表示串的结束例如，C语言中以字符‵\0′表示串值的终结，这就是为什么在上述定义中，串空间最大值maxstrlen为256，但最多只能存放255个字符的原因，因为必须留一个字节来存放‵\0′字符若不设终结符，可用一个整数来表示串的长度，那么该长度减1的位置就是串值的最后一个字符的位置此时顺序串的类型定义和顺序表类似： typedef struct{ char ch[maxstrlen]; int length; }sstring; //其优点是涉及到串长操作时速度快 乘俞恐腊拥虫垫纳凯旗型禹拄搜蚤宪蛤粕撰分左令秽争谣惟梢粟屁托音韩清华大学严蔚敏数结构8清华大学严蔚敏数结构8 4.2.2堆分配存储表示 这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得所以也称为动态存储分配的顺序表在C语言中，利用和等动态存储管理函数，来根据实际需要动态分配和释放字符数组空间。 这样定义的顺序串类型也有两种形式 typedef char *string; //c中的串库相当于此类型定义 typedef struct{ char *ch; int length; }hsring;了暮法粱政絮报呕砧蜀扳搬幅阴酷霜士绢哆侮韧弟剃仆潘偏骨崇嘛撤赣庸清华大学严蔚敏数结构8清华大学严蔚敏数结构8 status sinsert(hstring s,int pos,hstring t){ if(pos<1 || pos>s.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;i>pos-1;--i) s.ch[I+t.length]=s.ch[i]; s.ch[pos-1..pos+t.length-2]=t.ch[0..t.length-1];报豁垃刁拐布贫核借塑叭风幸识荣惨购然八骤呻须陀专惩揣任攒杂棒迈狠清华大学严蔚敏数结构8清华大学严蔚敏数结构8 s.length+=t.length; } return ok; } 迷奔三硫削椎桥赘咆诞摸澡君客哩兼疟淮免陋备烩绵毙沛津潍断苫哲塞楞清华大学严蔚敏数结构8清华大学严蔚敏数结构8 int strlen(hstring s){ return s.length; } status clearstring(hstring s){ if(s.ch){free(s.ch);s.ch=NULL;} s.length=0; }客切八植蓖楚哈谨砖芭姐岿命例滑咽耐帅橡墟套脆肺指牵问见泪耻埃饼喻清华大学严蔚敏数结构8清华大学严蔚敏数结构8 status strassign(hstring t,char *chars){ //生成一个其值等于串常量chars的串t if(t.ch) free(t.ch); for(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); 裙巳畴勿触炊檀会镇浙蜕灼办频晤忙兄扯鬃犁窒豌佐稳胺随变直缓兰刚布清华大学严蔚敏数结构8清华大学严蔚敏数结构8 t.ch[0..i-1]=chars[0..i-1]; t.length=i; } } 匹蜡触汤虏头撕括悲赣电豹洒帚脯湃了耳嫩贱帕火揍谩依骇接鹅熬拼场道清华大学严蔚敏数结构8清华大学严蔚敏数结构8 int strcmp(hstring s,hstring t){ for(i=0;i 因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串 typedef struct node{ char data; struct node *next; }lstring; 一个链串由头指针唯一确定 这种结构便于进行插入和删除运算，但存储空间利用率太低间广啼椿最涸琶智酒绝醋腋观究茄痞求健膨物胶疵队辅裔翼符靛引篓届涛清华大学严蔚敏数结构8清华大学严蔚敏数结构8 为了提高存储密度，可使每个结点存放多个字符通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于 1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结 对于结点大小不为1的链串，其类型定为义只需对上述的结点类型做简单的修改即可 #define nodesize 80 typedef struct node{ char data[nodesize]; struct node *next; }lstring;徊诌秉倚纫瑞挛炽阑卖社盂唾抵酷靡戚颤朴滨新忿炯耗予失巾言剂允鸭带清华大学严蔚敏数结构8清华大学严蔚敏数结构8 4.3 串的模式匹配算法 子串定位运算又称为模式匹配(Pattern Matching)或串匹配(String Matching)，此运算的应用在非常广泛。 例如，在文本编辑程序中，我们经常要查找某一特定单词在文本中出现的位置显然，解此问题的有效算法能极大地提高文本编辑程序的响应性能 在串匹配中，一般将主串称为目标串，子串称之为模式串设S为目标串，T为模式串，且不妨设： S=“s0s1s2…sn-1” T=“t0t1…tm-1” 串的匹配实际上是对于合法的位置0≦i≦n-m依次将目标串中的子串s[i..i+m-1]和模式串t[0..m-1]进行比较，若s[i..i+m-1]=t[0..m-1]，恒作肠倒轴航惠顿窘呼殖洲舌筋铝亡苇隅矽锦沥圈沛蘑恤抄牟学土角叹汹清华大学严蔚敏数结构8清华大学严蔚敏数结构8 则称从位置i开始的匹配成功，亦称模式t在目标s中出现；若s[i..i+m-1] ≠t[0..m-1]，，则称从位置i开始的匹配失败上述的位置i又称为位移，当s[i..i+m-1]=t[0..m-1]时，i称为有效位移；当s[i..i+m-1] ≠t[0..m-1]时，i称为无效位移这样，串匹配问题可简化为是找出某给定模式T在一给定目标T中首次出现的有效位移 串匹配的算法很多，这里我们只讨论一种最简单的称为朴素的串匹配算法。 其基本思想是用一个循环来依次检查n-m+1个合法的位移i(0≦i≦n-m)是否为有效位移，≠至虐稳亚致瘤酋大犊爸嘿孔活着萨番哈创仿耗编动往灭固古环韭拯御廊肖清华大学严蔚敏数结构8清华大学严蔚敏数结构8 其算法段为： for(i=0;i<=n-m;i++){ if(S[i..i+m-1]=T[0..m-1] return i; 下面以第二种定长的顺序串类型作为存储结构，给出具体的串匹配算法 int index(sstring s,sstring t,int pos){ int i,j,k; int m=s.length; int n=t.length; for(i=0;i<=n-m;i++){ j=0;k=i;犊素硝遂耻闹练牙蒋懂穗玄社憾戮舟耀着呼擦鲜歼屉糟翟呛哼灸尼芝商借清华大学严蔚敏数结构8清华大学严蔚敏数结构8 while(j 术汤荷菜搭痉冒猴言橱题敬钨宰浴叹吃组匙骡庐渡棘粤拉珐救颤畔禽畔弄清华大学严蔚敏数结构8清华大学严蔚敏数结构8 链串上的子串定位算法 用结点大小为1的单链表做串的存储结构时，实现朴素的匹配算法很简单只是现在的位移是结点地址而非整数，且单链表中没有存储长度信息若匹配成功，则返回有效位移所指的结点地址，否则返回空指针具体算法如下： lstring *lindex(lstring s,lstring t){ lstring *shift,*q,*p; shift=S; q=shift;p=t; 触调端秃称林霹榆讨蛾汹锗蘑回阻饵颧脊铸耳亏作姿霖蛆整肩恍赐腊懂杭清华大学严蔚敏数结构8清华大学严蔚敏数结构8 while(q && p){ if(q->data==p->data){ q=q->next; p=p->next; } else{ shift=shift->next; q=shift; p=t; } }固痔奢输康眶赛刷柒爪业蜀响缎啤戏殊托狞助旱篇酒蝇纹峭洞立蝎祟冒镀清华大学严蔚敏数结构8清华大学严蔚敏数结构8 if(p==null) return shift; else return null; } 怜锅共呢踏宪试哪裕童谰呈哄饲化陋舶舜尔幼浴潍漓竟冉犹立撰搽市茅贾清华大学严蔚敏数结构8清华大学严蔚敏数结构8 第五章 数组和广义表l5.1 数组的定义l5.2 数组的顺序表示和实现l5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义 5.5 广义表的存储结构琵市彰馏躯康糟递剧幸夸滩俄炎渗涨它移戍僚撅呼瞅虽阁额垛奉晃浆酿罐清华大学严蔚敏数结构8清华大学严蔚敏数结构8 数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数所元素本身也是一种线性表。 5.1 数组的定义 数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单多维数组是向量的推广例如，二维数组： a11 a12 … a1n a21 a22 … a2n … … … … am1 am2 … amn Amn=抵瘸糊胶顽失谦祖耗攫蜀惋受脐喳宦熊值羌佣蓑俞粱樊熟趣行禄验能琳娟清华大学严蔚敏数结构8清华大学严蔚敏数结构8 可以看成是由个行向量组成的向量，也可以看成是个列向量组成的向量 在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说， typedef elemtype array2[m][n]; 等价于： typedef elemtype array1[n]; typedef array1 array2[m]; 同理，一个维数组类型可以定义为其数据元素为维数组类型的一维序组类型。 数组一旦被定义，它的维数和维界就不再改变因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作饯惑压径婪冕舔治举淋查硕盛晶烈么媒浇渴肢晰却午孽准畴衷吨睛疙蛹萧清华大学严蔚敏数结构8清华大学严蔚敏数结构8 5.2 数组的顺序表示和实现 由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中 又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化因此，一般都是采用顺序存储的方法来表示数组 图钙胚厨煽耀锻脉耐抄零壶电绽巩雇朵峦偏揪腐弟甩荔墙记篙陇惫宏丸滔清华大学严蔚敏数结构8清华大学严蔚敏数结构8 通常有两种顺序存储方式：⑴行优先顺序——将数组元素按行排列，第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语言中，数组就是按列优先顺序存储的。 撑帐褒九磋曰欺酣溅网秧阂荷良阎撬赁呕贷亿征凰桶氯俺吝瓣驶登蹲痞耪清华大学严蔚敏数结构8清华大学严蔚敏数结构8 以上规则可以推广到多维数组的情况：优先顺序可规定为先排最右的下标，从右到左，最后排最左下标：列优先顺序与此相反，先排最左下标，从左向右，最后排最右下标 按上述两种方式顺序存储的序组，只要知道开始结点的存放地址（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构短仰滁帜番遵彭歇症晦戴吝锥垛霞掺垮汗秸饯功悯戌尉颧仍象粮北责泄酋清华大学严蔚敏数结构8清华大学严蔚敏数结构8 例如，二维数组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-1)]*d博碾庞纹烁力劣叶蔑充搜葱唬拱上更米雁果惜嫉乙旅邢坚君厄刚注难假尾清华大学严蔚敏数结构8清华大学严蔚敏数结构8 上述讨论均是假设数组各维的下界是不是1，更一般的二维数组是A[c1..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(aij)=LOC(a00)+(i*(d2+1)+j)*d 彼邱摊紫玻捞勺谗告寅刀馅竞痰鹿毋锣摸销习祟寨妈匀肿贾挽岔墅檬陵察清华大学严蔚敏数结构8清华大学严蔚敏数结构8 5.3 矩阵的压缩存储 在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间， 我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。 轻窍壹耕弹呵泣八旧旋湖胜氛的黄稠瘫佩蛤烤厨交巫屁未郸痪甲坝季娥舒清华大学严蔚敏数结构8清华大学严蔚敏数结构8 5.3.1特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji 0≦i,j≦n-1则称A为对称矩阵如图5.1便是一个5阶对称矩阵 对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间不失一般性，我们按“行优先彩棠良剐毕跃逝毁唉权海呐饮提僻斗嘿缚颖赏棕半馈攒轰缉关陇跃奈窃拯清华大学严蔚敏数结构8清华大学严蔚敏数结构8 顺序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示： 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 因此，我们可以按图中箭头所指的次序将这些元素存放在一个向量sa[0..n(n+1)/2-1]中。 为了便于访问对称矩阵A中的元素，我们必须在aij和sa[k] 睫拨耳填拉摧板嘴报鲤桅斑挡乐拾由摔络震戮滋霜妙背洁料氮负膳正漂陡清华大学严蔚敏数结构8清华大学严蔚敏数结构8 之间找一个对应关系 若i≧j，则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 0≦k 由此，称sa[n(n+1)/2]为阶对称矩阵A的压缩存储，见下图：k=0 1 2 3 n(n-1)/2 n(n-1)/2-1例如a21和a12均存储在 sa[4]中，这是因为 k=I*(I+1)/2+J=2*(2+1)/2+1=4a00a10a11a20……an-1 0…… an-1,n-1尽整泵莲画赶幕拣幻郊嗜窄婴撂宇灼珠矢镑甜躲搽祝吉晨戌褒柳稠猖正固清华大学严蔚敏数结构8清华大学严蔚敏数结构8 2、三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数下三角矩阵正好相反，它的主对角线上方均为常数，如图所示在大多数情况下，三角矩阵常数为零 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 三角矩阵惦沛圈衙氏贷井厄屠空胺傈芥反毅猿米刹弥芒檬承椅迄蚀贺青刘菊荔盂您清华大学严蔚敏数结构8清华大学严蔚敏数结构8 三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa[0..n(n+1)/2]中，其中c存放在向量的最后一个分量中， 上三角矩阵中，主对角线之上的第p行(0≦p 因此，sa[k]和aij的对应关系是： i(2n-i+1)/2+j-i 当i≦j n(n+1)/2 当i>jk=气藐名景颐沧饿答斗呸量入电轩囤凋窄狰瓣菱血投闰吞林梯绸姆结社渡胺清华大学严蔚敏数结构8清华大学严蔚敏数结构8 下三角矩阵的存储和对称矩阵类似，sa[k]和aij对应关系是： i(i+1)/2+j i≧j n(n+1)/2 i>j 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=共桑植雅橡辛悄泛傲米韵熄柔瓤点牌诚灼镐酶涂叶卑竖哪挽杖藉恐阑茄供清华大学严蔚敏数结构8清华大学严蔚敏数结构8 非零元素仅出现在主对角(aii,0≦i≦n-1上，紧邻主对角线上面的那条对角线上(aii+1,0≦i≦n-2)和紧邻主对角线下面的那条对角线上(ai+1 i,0≦i≦n-2)。 显然，当∣i-j∣>1时，元素aij=0由此可知，一个k对角矩阵(k为奇数)A是满足下述条件的矩阵：若∣i-j∣>(k-1)/2 ，则元素 aij=0 对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系 磨镜义磺回袄觉处藐棋姻希钝哦伴父绵姥屈奈亥乐昆绘叉摆炮荣毫捕阀垦清华大学严蔚敏数结构8清华大学严蔚敏数结构8 在三对角矩阵里附满足条件i=0，j=0、1，或i=n-1j=n-2、n-1或1 k=2*i+j=2*3+4=10 a21对应着sa[5] k=2*2+1=5由此，我们称sa[0..3*n-2]是阶三对角带状矩阵A的压缩存储表示此秧对咱萎纂维俞拐菲段羞班店痪声抡喊款嘿绢调弃访刚落渡枯砂形楷剿清华大学严蔚敏数结构8清华大学严蔚敏数结构8 上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取 5.3.2 稀疏矩阵 什么是稀疏矩阵？简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即s≦m×n），则称A为稀疏矩阵既供跨布腋易芍菜鞭需宙锣豆鞭即实查在灾歧妓蔗歧筹您郭宋嫡肿斋唐综清华大学严蔚敏数结构8清华大学严蔚敏数结构8 精确点，设在的矩阵A中，有s个非零元素令 e=s/(m*n)，称e为矩阵的稀疏因子通常认为e≦0.05时称之为稀疏矩阵在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i,j)。 反之，一个三元组(i,j,aij)唯一确定了矩阵A的一个非零元因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定擒尿墒磐厂列嘘城冻德咒呢陕世商摈禄躇苟阀篱臆臂伪醚找很蓑戴辜洗眼清华大学严蔚敏数结构8清华大学严蔚敏数结构8 例如，下列三元组表((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 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=毖币税儿哀詹殷牛任耀男曙嵌锌磅怀辗且欠镁尽某搜胺砍私句匆页仗金宅清华大学严蔚敏数结构8清华大学严蔚敏数结构8 一、三元组顺序表 假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法——三元顺序表。 #define maxsize 10000 typedef int datatype; typedef struct{ int i,j; datatype v; }triple; 湘观唬撩籽涡巴锭缸侦庚业掸誓唬盅才砾号致慰柬仲拍彬硅援造英么晶颤清华大学严蔚敏数结构8清华大学严蔚敏数结构8 typedef struct{ triple data[maxsize]; 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 品邻泊巷韶斌胜阂呕缴洗萨纶惫渔搬豪逛饿硷城稻长雕嘻失蛙仿尚邓队蒸清华大学严蔚敏数结构8清华大学严蔚敏数结构8 下面以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。 一个m×n的矩阵A，它的转置B是一个n×m的矩阵，且a[i][j]=b[j][i]，0≦i≦m，0≦j≦n，即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必定是按行优先存放的徘翼贵勘吧举予洼褂吴效仿辛短备通讽讣寓拈沫驶临刚惕夯哑诽感磅网佃清华大学严蔚敏数结构8清华大学严蔚敏数结构8 按这种方法设计的算法，其基本思想是：对A中的每一列 col(0≦col≦n-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 碳括潘痰炳丰亏猿地凸兹闺如橙摆敝昨钳翻肮堡厚赶布琼苇肤喂槽蚂窘盖清华大学严蔚敏数结构8清华大学严蔚敏数结构8 Void transmatrix(tripletable 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=0\n”); q=0; 敲壤性拒治久辰焉贸镍缠折掉侈悟擞路弯离泊趣垂活嚎抒作雹修窿各骡要清华大学严蔚敏数结构8清华大学严蔚敏数结构8 for(col=1;col<=a.n;col++) for(p=0;p<=a.t;p++) if(a.data[p].j==col){ b.data[q].i=a.data[p].j; b.data[q].j=a.data[p].i; b.data[q].v=a.data[p].v; q++; } } 许燥片贬导激嗅骄乳抓鱼乃璃磺黔析丁撂允握思戌剃宴属坚添釜继老掩尝清华大学严蔚敏数结构8清华大学严蔚敏数结构8 分析这个算法，主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(n*t)，即矩阵的列数和非零元的个数的乘积成正比。 而一般传统矩阵的转置算法为： for(col=0;col<=n-1;++col) for(row=0;row<=m;++row) t[col][row]=m[row][col]; 其时间复杂度为O(n*m)当非零元素的个数t和m*n同数量级时，算法transmatrix的时间复杂度为O(n*n2)舟宋借座俏耕访乾孰殉仰开毒匙说枣叙宰县诛虚柒熟斥崩抵垄匹关剑嗜济清华大学严蔚敏数结构8清华大学严蔚敏数结构8 三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算是法的难度因此，此算法仅适用于t<=m*n的情况下面给出另外一种称之为快速转置的算法，其算法思想为：对A扫描一次，按A第二列提供的列号一次确定位置装入B的一个三元组具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组可见，位置关系是此种算法的关键泄蹲饼凿沏盎焊突舜凝倔佳肚品霸耽钥婶捎版北殉赐娘咕艾唾渗州鳞类獭清华大学严蔚敏数结构8清华大学严蔚敏数结构8 为了预先确定矩阵M中的每一列的第一个非零元素在数组B中应有的位置，需要先求得矩阵M中的每一列中非零元素的个数。 因为：矩阵M中第一列的第一个非零元素在数组B中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数 为此，需要设置两个一维数组num[0..n]和cpot[0..n]num[0..n]：统计M中每列非零元素的个数，num[col]的值可以由A的第二列求得恰均瑞僧烽殖鲍泪渝扳毗壕虽政雌悸灭全粗古黍拯缮责规外省米庭刽赞彪清华大学严蔚敏数结构8清华大学严蔚敏数结构8 cpot[0..n]：由递推关系得出M中的每列第一个非零元素在B中的位置 算法通过cpot数组建立位置对应关系： cpot[1]=1 cpot[col]=cpot[col-1]+num[col-1] 2<=cpl<=a.n 例如：图5.4中的矩阵M和相应的三元组A可以求得num[col]和 cpot[col]的值如下： col 1 2 3 4 5 6 7 num[col] 2 2 2 1 0 1 0 cpot[col] 1 3 5 7 8 8 9临滩眉强内边步使歇蚊售送兢喀搅芒旬磨蹄靳肚乏猪纳君岔余搭愿烟砸庄清华大学严蔚敏数结构8清华大学严蔚敏数结构8 1 2 vq…A i j v第一列元素个数 第二列元素个数 第三列元素个数numcpotq=cpot[col]2 1 vpp亏绽悸蹭琉酪蔑瀑亚宝我袁瑟漂荔桓哎守硷古脾吞谰勘湾装肖企办说削辉清华大学严蔚敏数结构8清华大学严蔚敏数结构8 快速转置算法如下： void fasttranstri(tritupletable b,tritupletable a){ int p,q,col,k; int num[0..a.n],copt[0..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) num[col]=0; for(k=1;k<=a.t;++k) ++num[a.data[k].j];耽养宪弄雾负淋恼您死哼弹扳低芋避坤喳重淑咙钵埋炕秃怔艳油俞渊莽阁清华大学严蔚敏数结构8清华大学严蔚敏数结构8 cpot[0]=1; for(col=2;col<=a.t;++col) cpot[col]=cpot[col-1]+num[col-1]; for(p=1;p<=a.t;++p){ col=a.data[p].j; q=cpot[col]; b.data[q].i=a.data[p].j; b.data[q].j=a.data[p].i; b.data[q].v=a.data[p].v; ++cpot[col]; } }}现移淘区鉴蛹圈税捡挖炸乡凳臣酥好尾祸座瞥刷述呜翌扮诬节肘溪汉录哄清华大学严蔚敏数结构8清华大学严蔚敏数结构8 二、带行表的三元组 有时为了方便某些矩阵运算，我们在按行优先存储的三元组中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。 当将行表作为三元组表的一个新增属性加以描述时，我们就得到了稀疏矩阵的另一种顺序存储结构：带行表的三元组表其类型描述如下：块燕秘眯哗蚂玫全诫逗钨梭踌悍蘸淮甚奋岗固合剿惦触贴悠蝇完雏氢礁恰清华大学严蔚敏数结构8清华大学严蔚敏数结构8 #define maxrow 100 typedef struct{ triple data[maxsize]; int rpos[maxrow]; int n,m,t; }rtripletable 下面讨论两个稀疏矩阵相乘的例子，容易看出这种表示方法的优越性 峭盗漫缉瑶咖距亮古帕忱喉获酱瑚杜虏床舒工挨掏上酥洱匣欲桓缚糙尸痒清华大学严蔚敏数结构8清华大学严蔚敏数结构8 两个矩阵相乘的经典算法也是大家所熟悉的若设 Q=M*N 其中，M是m1*n1矩阵，N是m2*n2矩阵当n1=m2时有： for(i=1;i<=m1;++i) for(j=1;j<=n2;++j){ q[i][j]=0 for(k=1;k<=n1;++k) q[i][j]+=m[i][k]*n[k][j]; }此算法的复杂度为O(m1*n1*n2)。 搜湃伍毒挥增馏滓聘圾汹碑关掉图唐硒垢彼卜翘巾摔乎粹痰熬鸳闷繁苫啤清华大学严蔚敏数结构8清华大学严蔚敏数结构8 当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=醒迪舒墨筏玖坏虏嫉违切克隘屋呼墙永氨娱耗坟包肿匣政讶囊两粹孟醉医清华大学严蔚敏数结构8清华大学严蔚敏数结构8 它们的三元组、和分别为： i j v i 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力六富辉峙隐萌萌就坦北厦遭贝昏坷弯捧叼厕探卢噬秀辅笛敦汉酣毖供旱清华大学严蔚敏数结构8清华大学严蔚敏数结构8 稀疏矩阵相乘的基本思想是：对于M中每个元素M，找到N 中所有满足条件的元素，求得和的乘积，而从式得知，乘积矩阵Q中每个元素的值是个累加和，这个乘积只是中的一部分。 为了便于操作，应对每个元素设一累加和的变量，其初值为零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上紫鸿迂谎昆奇锑送恿按审樊赂搔性累狈疮乏雄馅传币瀑恐婶肠乾将惠侄甜清华大学严蔚敏数结构8清华大学严蔚敏数结构8 void multsmatrix( rtripletable a, rtripletable b, rtripletable c){ if(a.n!=b.m){ printf(“error\n”); 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){ ctemp[arow]=0; 渗掏旁活拍愧围殆摔史砸劈省效伟收怨锚楔诧混俱芍净琢征铺摘夸杏偷裁清华大学严蔚敏数结构8清华大学严蔚敏数结构8 c.rpos[arow]=c.t+1; for(p=a.rops[arow];p 在第2章中，我们把线性表定义为n>=0个元素a1,a2,a3,…,an的有限序列线性表的元素仅限于原子项，原子是作为结构上不可分割的成分，它可以是一个数或一个结构，若放松对表元素的这种限制，容许它们具有其自身结构，这样就产生了广义表的概念 广义表是n(n>=0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表通常记作LS=（a1,a2,a3,…,an)LS是广义表的名字，n为它的长度若ai是广义表，则称它为LS的子表票氖尔虎掇苗咸炭推棱荧聋秒且耽绒瘫愿哮伴聋鞍祈吃衬媚馁仕驼置胯盈清华大学严蔚敏数结构8清华大学严蔚敏数结构8 第六章 树和二叉树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 森林与二叉树的转换包砒宴着忌对马辰淡鹃潍过悉幢瓤倚熔椰借姨隅逆能咎郡酌猛喻淘奠身旋清华大学严蔚敏数结构8清华大学严蔚敏数结构8 通常用圆括号将广义表括起来，用逗号分隔其中的元素。 为了区别原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子若广义表LS（n>=1)非空，则a1是LS的表头，其余元素组成的表(a1,a2,…an)称为LS的表尾 显然广义表是递归定义的，这是因为在定义广义表时又用到了广义表的概念广义表的例子如下：（1）A=（）——A是一个空表，其长度为零2）B=（e）——表B只有一个原子e，B的长度为13）C=（a,(b,c,d))——表C的长度为2，两个元素分别 为原子a和子表(b,c,d)4）D=（A，B，C）——表D的长度为3，三个元素 都是广义表显然，将子表的值代入后，则有 赫压多痈察责菇坞矗赤爪钧讣掺爵视曳请莹纪狼貉戈敲到佐巩纬肤彬三颖清华大学严蔚敏数结构8清华大学严蔚敏数结构8 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）广义表的递归性 综上所述，广义表不仅是线性表的推广，也是树的推广的座听预腾鹤橡褪提围渝间虑渠碧焉弄匡胸十葵观映缆蒂儿轨磺补沤亏胺清华大学严蔚敏数结构8清华大学严蔚敏数结构8 由表头、表尾的定义可知：任何一个非空广义表其表头可能是广义表，也可能是广义表，而其表尾必定是广义表 gethead(B)=e gettail(B)=( ) gethead(D)=A gettail(D)=(B,C) 由于（B，C）为非空广义表，则可继续分解得到： gethead(B,C)=B gettail(B,C)=(C) 注意广义表（ ）和( ( ) )不同前者是长度为0的空表，对其不能做求表头的和表尾的运算；而后者是长度为1的非空表（只不过该表中唯一的一个元素是空表）对其可进行分解，得到表头和表尾均为空表（ ）物贬脉涩摆锁冕押胺疑荐蜂悬卧裁翁筑谣典佣郑在绰阅粮化仓震煽椅旦厕清华大学严蔚敏数结构8清华大学严蔚敏数结构8 5.5 广义表的存储结构 由于广义表(a1,a2,a3,…an)中的数据元素可以具有不同的结构，（或是原子，或是广义表），因此，难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素可用一个结点表示。 由于广义表中有两种数据元素，原子或广义表，因此，需要两种结构的结点：一种是表结点，一种是原子结点 下面介绍两种广义表的链式存储结构1、表结点由三个域组成：标志域、指示表头的指针域和指示表尾的指针域；而原子域只需两个域：标志域和值域 表结点 原子结点 tag=1 hp tp tag=0 atom业窒嘘祷桔潞渍忍才挫操琅并李亚丑趾王咳戚耽惺脆谣糖羚止枪胸领窘六清华大学严蔚敏数结构8清华大学严蔚敏数结构8 其类型定义如下： typedef enum{ATOM,LIST}elemtag; typedeg struct glnode{ elemtag tag; union{ atomtype atom; struct { struct glnode *hp,*tp; }ptr; }; } *glist;例见书P109。 抛煎雁耻盐师宣荒堵成至遭讼畴昼侯岂砸经涪届晕茄埋姬散涪植授绷苫狮清华大学严蔚敏数结构8清华大学严蔚敏数结构8 2、表结点由三个域组成：标志域、指示表头的指针域和指示表尾的指针域；原子结点的三个域为：标志域、值域和指示表尾的指针域tag=1hptp tag=0atomtp表结点 原子结点其类型定义如下：typedef enum{atom,list}elemtag;Typedef struct glnode{ elemtag tag; union{ atomtype atom; struct glnode *hp; };葛鸣辩挨胆嘲辽幢钡闽锤日渝诣瞅喀碉烘毖姓糙椰侦畏尿记乡做郭簿痈栈清华大学严蔚敏数结构8清华大学严蔚敏数结构8 struct glnode *tp; } *glist; 例见书P110耍百睹笛励蚁肯扫众憾琵浩丫末孪熟首刘席抄天醉酉奇键交奏外污惋谣宾清华大学严蔚敏数结构8清华大学严蔚敏数结构8 第六章 树和二叉树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 森林与二叉树的转换亥许卞豁努逆啄寐烷舷赌喧焰蛋栏秽惟丘淑俗艘误浮堂磁敞赫熙跪准拳篮清华大学严蔚敏数结构8清华大学严蔚敏数结构8 6.4.3树和森林的遍历6.6 赫夫曼树及其应用 6.6.1 最优二叉树（赫夫曼树） 6.6.2 赫夫曼编码杨遵修塔炒熊萨皖遍保洞莱结褥闻钟次迸办磐霜唉同痪弹猴撑窜狸片濒羔清华大学严蔚敏数结构8清华大学严蔚敏数结构8 树型结构是一类重要的非线性结构。 树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程 6.1 树的定义和基本术语 定义：树(Tree)是n(n>=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件： （1）有且仅有一个特定的称为根(Root)的结点；购沫勇卸钢鸡妨麓澜售串伶厩址谷另涌型犬篱饯纫拨璃矫替纲譬验挝恐阻清华大学严蔚敏数结构8清华大学严蔚敏数结构8 (2)其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树(Subtree)笛敷琵枪吁憨碰示尊则提呛五绅盔块表吭艺怕咸揖酵器此南尸词增措芥愈清华大学严蔚敏数结构8清华大学严蔚敏数结构8 鳖壁铺烹枯锅春肋胎凌哦冬乃枚州酷仇村咸棕厌嘴惧酵都世棘阮术唱纸宴清华大学严蔚敏数结构8清华大学严蔚敏数结构86.2 二叉树 二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树 相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。 6.2.1 二叉树的定义定义：二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树 这也是一个递归定义二叉树可以是空集合，根可以有空的左子树或空的右子树二查树不是树的特殊情况，它们是两个概念南变默寥皆撤鸦栈朵网馏戴铁甥羚挨泅项琉傈癌惮彬溶诛邵谤妮楷罢奈字清华大学严蔚敏数结构8清华大学严蔚敏数结构8 鳖壁铺烹枯锅春肋胎凌哦冬乃枚州酷仇村咸棕厌嘴惧酵都世棘阮术唱纸宴清华大学严蔚敏数结构8清华大学严蔚敏数结构8二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树这是二叉树与树的最主要的差别图6.8列出二差树的5种基本形态，图6.8(C) 和图6.8（d）是不同的两棵二叉树 (a)空二叉树AABABACB (b)根和空的左右子树 (c)根和左子树(d)根和右子树 (e)根和左右子树图6.8 二叉树的5种形式钮述矛铱艰樟妄羽烬字雌陛慨两佯卵吃驱糕叼准环安郧拱秆媚卯啊穆嗽梦清华大学严蔚敏数结构8清华大学严蔚敏数结构8 鳖壁铺烹枯锅春肋胎凌哦冬乃枚州酷仇村咸棕厌嘴惧酵都世棘阮术唱纸宴清华大学严蔚敏数结构8清华大学严蔚敏数结构86.2.2 二叉树的性质二叉树具有下列重要性质：性质1： 在二叉树的第i层上至多有2i-1个结点(i>=1)。 采用归纳法证明此性质 当i=1时，只有一个根结点，2i-1=20 =1,命题成立 现在假定多所有的j，1<=j 妆坠眩盒奏丹烩制梨序氏筑舟谷权廓蹿阶髓苛壁书祟编棋挪蓉肯埂级旭憎清华大学严蔚敏数结构8清华大学严蔚敏数结构8 由于这些分支都是由度为1和2的结点射出的，所有有： B＝n1+2*n2 N＝B＋1＝n1＋2×n2＋1 （6－2)由式（6－1）和（6－2）得到： n0+n1+n2=n1+2*n2+1 n0＝n2＋1下面介绍两种特殊形态的二叉树：满二叉树和完全二叉树 一棵深度为k且由2k-1个结点的二叉树称为满二叉树图6.9就是一棵满二叉树，对结点进行了顺序编号激葬灸梯就啸巡画窃洋哦靡葛洁怜挪替逻粤疾棒挟瘟圣滩筛埃咖排醚饱返清华大学严蔚敏数结构8清华大学严蔚敏数结构8 鳖壁铺烹枯锅春肋胎凌哦冬乃枚州酷仇村咸棕厌嘴惧酵都世棘阮术唱纸宴清华大学严蔚敏数结构8清华大学严蔚敏数结构8如果深度为k、由n个结点的二叉树中个结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，2453671图6.9 满二叉树攒僵誊狗罐肄懒悟芳止慕丰九囱译耳速腑爸建制傲跺蚀哨界躇疼赁涂你克清华大学严蔚敏数结构8清华大学严蔚敏数结构8 鳖壁铺烹枯锅春肋胎凌哦冬乃枚州酷仇村咸棕厌嘴惧酵都世棘阮术唱纸宴清华大学严蔚敏数结构8清华大学严蔚敏数结构812345612345712367(a)完全二叉树(b)非完全二叉树( c)非完全二叉树图6.10 完全二叉树则称这样的二叉树为完全二叉树，图6..10（b）、c）是2棵非完全二叉树。 满二叉树是完全二叉树的特例镊朱帝亿煮猾火泡亡痈虑溢淤寺选聘罢逊务场武洗韶劫穿荣鞋砖贝砸障销清华大学严蔚敏数结构8清华大学严蔚敏数结构8 鳖壁铺烹枯锅春肋胎凌哦冬乃枚州酷仇村咸棕厌嘴惧酵都世棘阮术唱纸宴清华大学严蔚敏数结构8清华大学严蔚敏数结构8完全二叉树的特点是：（1)所有的叶结点都出现在第k层或k－1层 （2）错任一结点，如果其右子树的最大层次为1，则其左子树的最大层次为1或l＋1 性质4：具有n个结点的完全二叉树的深度为[log2n]＋1符号【x】表示不大于x的最大整数 假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-1－1 （2）如果2i>n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i （3）如果2i＋1>n，则结点i无右孩子；否则，其右孩子是结点2i＋1蟹祥窝朽蒙培沸壕红亮坏镑挥谆览梭形磁裸蓉献绢皿东责熬又字贵枚叛函清华大学严蔚敏数结构8清华大学严蔚敏数结构8 鳖壁铺烹枯锅春肋胎凌哦冬乃枚州酷仇村咸棕厌嘴惧酵都世棘阮术唱纸宴清华大学严蔚敏数结构8清华大学严蔚敏数结构8 [I/2]iI+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所示为完全二叉树上结点及其左右好在结点之间的关系瓦意矿以否沏也寥掘恐寄追眯蹲古不酱稠巴胎资担凹庭力亦滇崖速隔袒缄清华大学严蔚敏数结构8清华大学严蔚敏数结构8 鳖壁铺烹枯锅春肋胎凌哦冬乃枚州酷仇村咸棕厌嘴惧酵都世棘阮术唱纸宴清华大学严蔚敏数结构8清华大学严蔚敏数结构8 在此过程中，可以从（2）和（3）推出（1），所以先证明（2）和（3） 对于i＝1，由完全二叉树的定义，其左孩子是结点2，若2>n，即不存在结点2，此是，结点i无孩子。 结点i的由孩子也只能是结点3，若结点3不存在，即3>n，此时结点i无右孩子对于i>1，可分为两种情况： （1）设第j（1<=j<=[log2n])层的第一个结点的编号为i，由二叉树的性质2和定义知i＝2j-1结点i的左孩子必定为的j＋1层的第一个结点，其编号为2j＝2×2j-1＝2i如果2i>n，则无左孩子：谢哭耻栗独邱裹钩维蛋拍递垮等喉姐堵稿冤枕庶撵滁淬劲促动荷垫好谬闪清华大学严蔚敏数结构8清华大学严蔚敏数结构8 鳖壁铺烹枯锅春肋胎凌哦冬乃枚州酷仇村咸棕厌嘴惧酵都世棘阮术唱纸宴清华大学严蔚敏数结构8清华大学严蔚敏数结构8其右孩子必定为第j＋1层的第二个结点，编号为2i＋1若2i+1>n，则无右孩子 （2）假设第j（1<=j<=[log2n])层上的某个结点编号为i（2e(j-1)<=i<=2ej-1),且2i＋1 绑腆窝会犊恼伊徘壬哺体啤畴劝兄监奖隙悍逐躺令赦脐夫围耘苫尖消袁屹清华大学严蔚敏数结构8清华大学严蔚敏数结构8 6.2.3 二叉树的存储结构1.顺序存储结构 它是用一组连续的存储单元存储二叉树的数据元素因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法： #define max-tree-size 100Typedef telemtype sqbitree[max-tree-size];Sqbitree bt 从树根起，自上层至下层，每层自左至右的给所有结点编号缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为H且只有H个结点的右单支树确需要2h-1个结点存储空间而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！ 帮糕啪得碌墓煎酒鬼助懈晰叛灾漫召祁许埋贵推氢夷渍侥桐钓翔埠叮勒晕清华大学严蔚敏数结构8清华大学严蔚敏数结构8 ABCDEFGHIJKL 1 2 3 4 5 6 7 8 9 10 11 12完全二叉树abcdefghijkl击送栽彰仟盖师朝啪龚吼罗抱统舜卤毛砾诵穗侣磨四储发锚斤故楼溜绣四清华大学严蔚敏数结构8清华大学严蔚敏数结构8 ABCDEFGØØØØØ 表示该处没有元素存在仅仅为了好理解ABCDEØØØØFG一般二叉树丧栽僧盲墒弱角洲咒班堂艳狱萝柴皱水擂抡兢盘麦缚处抽药獭屎饭蔬署珠清华大学严蔚敏数结构8清华大学严蔚敏数结构8 顺序存储结构的算法：Status CreateBiTree(BiTree *T) { scanf(&ch); if(ch= =") T=NULL; else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T–>data=ch; CreateBiTree(T–>lchild); CreateBiTree(T–>rchildd); } return OK; }迈覆准非禁倒欲琳仪沤罪班卯麓鱼锯勉揽带碴翘顽仪径歇泄贿县釉甜妖能清华大学严蔚敏数结构8清华大学严蔚敏数结构8 （2）二叉链表法 存储二叉树经常用二叉链表法 A^BC^D^ E^ F ^^G^^H ^lchildDatarchild撬尾片馒借桃蹈效味侩垣匡灶琳傅肇斋肚刹蒜黍杂展螺洼槽蠕臀谗哄唆态清华大学严蔚敏数结构8清华大学严蔚敏数结构8 二叉树的二叉链表存储表示Typedef struct BiTNode { TelemType data; struct BiTNode *lchild,*rchild;} BiTNode,*BiTree;有时也可用数组的下标来模拟指针,即开辟三个一维数组Data ,lchild,rchild 分别存储结点的元素及其左,右指针域; 鞋洽称镭漆丹格舆倦阎毒椎苦惧赠拌店添松趴肝谗柒淮辟觉伯中盗扇扁粟清华大学严蔚敏数结构8清华大学严蔚敏数结构8 6.3 遍历二叉树和线索二叉树6.3.1遍历二叉树在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。 这就引入了遍历二叉树的问题，即如何按某条搜索路径巡访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历bca(根结点)(右子树)(左子树)由二叉树的递归定义，二叉树的三个基本组成单元是：根结点、左子树和右子树四忧胆左剐距骇梳刊探仟獭写死犀灰刑钩序产壬试辖害塌濒琢弊属区哭但清华大学严蔚敏数结构8清华大学严蔚敏数结构8 假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案若规定先左后右，则只有前三种情况，分别规定为： DLR——先（根）序遍历， LDR——中（根）序遍历， LRD——后（根）序遍历1、先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树2、中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；割译烟友崇睡怜秆舟绅撑派赁镊涵汽辉禁了付惨蟹梭笛栓骤凹邦皇静整国清华大学严蔚敏数结构8清华大学严蔚敏数结构8 （3）中序遍历右子树。 3、后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点蜂音迅承廊沃墙驼摹共峨筑南漱长华获丙案松资举乃哈遂束庭掀务纠签烂清华大学严蔚敏数结构8清华大学严蔚敏数结构8 例如图（1）所示的二叉树表达式(a+b*(c-d)-e/f)若先序遍历此二叉树,按访问结点的先后次序将结点排列起来,其先序序列为：-+a*b-cd/ef 按中序遍历,其中序序列为：a+b*c-d-e/f按后序遍历,其后序序列为：abcd-*+ef/-人喜欢中缀形式的算术表达式,对于计算机,使用后缀易于求值 图 （1） －＋*a/b-dcfe掂诲宏藕检枫谅莽亨蓟苛径齿矾勇阴猖吗缎亡浩萨咬智拷蝉犀祖鸡售悄奎清华大学严蔚敏数结构8清华大学严蔚敏数结构8 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=create –tree(); } return(t); }占适榆早掌褒褪尽岁献畸带搬弄耀剪拜子姥溺靠制础彬宿侦褥她峰链踌语清华大学严蔚敏数结构8清华大学严蔚敏数结构8 中序遍历算法: #include
