基本数据结构及其运算

第二章基本数据构造及其运算2.1数据构造的基本概念2.2线性表及次序存储构造2.3线性表链表及其运算2.4数组2.5树与二叉树2.6图本章重要介绍:数据构造、数据逻辑构造、数据存储构造的基本概念；几个惯用的数据构造(线性表、栈、队列、数组、树与二叉树、图），阐明这些数据构造内在的逻辑关系，讨论它们在计算机中存储的惯用方式：次序存储和链式存储，以及在这些数据构造上进行多个运算的算法。重点：理解数据构造、数据逻辑构造和存储构造的概念，掌握惯用的数据构造中各数据内在的逻辑关系，在计算机中的存储方式，以及在其上进行多个运算的算法。难点：对的分辨数据逻辑构造和存储构造，掌握惯用数据构造在计算机中的存储方式，及在其上进行多个运算的算法。1、数据元素之间的固有逻辑关系，称为数据的逻辑构造数据构造重要研究和讨论三方面问题：2、数据元素及其关系在计算机中的存储方式，称为数据的物理构造或存储构造3、施加在数据构造上的操作，称为数据构造的运算。数据解决的本质就是对数据构造施加多个运算，常见的运算有：查找、排序、插入、删除等。2.1数据构造的基本概念例1、无序表的次序查找与有序表的对分查找。2.1.1两个例子2、尽量节省数据解决过程中所占用的存储空间1、提高数据解决的速度重要目的是提高数据解决的效率：1234567891012345678910data[0]data[1]data[2]data[3]data[4]data[5]data[6]data[7]data[8]132442772830121321242830427725(a)无序表

data[0]data[1]data[2]data[3]data[4]data[5]data[6]data[7]data[8]211225(b)有序表

图2.1数据元素寄存次序不同的两个表表(a)只能采用次序查找，将x与表中每一种元素进行比较，查找效率较低。因表(b)中的元素是有序排列，可找到其中间元素data[4]，将x与它进行比较，有三种可能：x=data[4]x>data[4]

x<data[4]找到抛弃表的前半部分，在表的后半部分用相似的办法继续查找抛弃表的后半部分，在表的前半部分用相似的办法继续查找用这种办法查找，每次比较都可抛弃子表二分之一的元素，查找效率较高从该例可看出，数据元素在表中的排列次序对查找效率有很大的影响例2、学生状况记录表信息查询学号姓名性别年龄成绩970156张小明男2086970157李小青女1983970158赵凯男1970970159李启明男2191970160刘华女1878970161曾小波女1990970162张军男1880970163王伟男2065970164胡涛男1995……………9519男胡涛9701649019女曾小波9701619317女梅玲9701689121男李启明970159成绩年龄性别姓名学号成绩在90分及以上的学生情况登记表成绩在80~89分之间的学生情况登记表8018男张军970162……………8319女李小青9701578620男张小明970156成绩年龄性别姓名学号从该例可看出，在对数据进行解决时，可根据所做的运算不同，将数据组织成不同的形式，也可提高数据解决的效率成绩在70~79分之间的学生情况登记表7818女刘华9701607520男刘健9701697019男赵凯970158成绩年龄性别姓名学号成绩在60~69分之间的学生情况登记表6520男王伟9701636118男吕永华970167成绩年龄性别姓名学号2.1.2什么是数据构造数据构造：互相有关联的数据元素的集合。例：向量和矩阵就是数据构造，在这两个数据构造中，数据元素之间有位置上的关系数据：反映客观事物信息集合，在现实生活中称信息在计算机中称数据；即数据是符号化的信息。它由数据元素构成数据元素(元素)：数据集合中的一种元素，是数据的基本单位。数据元素含有广泛的含义，现实世界中的一切个体能够是数据元素例：描述四季的季节名{春、夏、秋、冬}能够作为季节(数据)的数据元素描述学生特性的信息:(970158、赵凯、男、1970、70)，(970159、李启明、男、21、91)，(970162、张军、男、18、80)…能够作为学生状况记录表(数据)的数据元素甚至每一种客观存在的事件：如一次借书、一次比赛等也可作为数据元素 总之，在数据解决领域，每一种需要解决的对象都可抽象成数据元素要表达一种数据构造，需表达出：1、数据元素的集合，记为D2、在D中各数据元素之间的关系，记为R则：数据构造B=(D,R)在数据解决领域，数据元素之间的任何关系都能够用前后件关系描述例1：春、夏、秋、冬四季，春是夏的前件，夏是春的后件为反映春、夏、秋、冬这四个元素之间的前后件关系，普通采用二元组表达，也称二元关系(春,夏)、(夏,秋)、(秋,冬)故：一年四季的数据构造可表达为D={春,夏,秋,冬}R={(春,夏),(夏,秋),(秋,冬)}B=(D,R)例2、n维向量X=(x1,x2,……xn)是一种数据构造，它可表达为：D={x1,x2,……,xn}R={(x1,x2),(x2,x3),…,(xn-1,xn)}B=(D,R)对于复杂的数据构造，它的数据元素能够是另一种数据构造。它的每一行Ai=(ai1,ai2,…,ain)i=1,2,…,m能够当作是它的一种数据元素,D={A1,A2,…,Am}D上的关系为:R={(A1,A2),(A2,A3),…(Am-1,Am)}例：m×n的矩阵是一种数据构造显然,数据构造A中的每一种元素Ai (i=1,2,…,m)又是另一种数据构造,其数据元素,Di={ai1,ai2,…,aim}Di上的关系为:Ri={(ai1,ai2),(ai2,ai3),…(aim-1,aim)}可看出：②、数据的逻辑构造在计算机存储器中的存储方式称为数据的物理构造（存储构造）。③、要将一种数据存储在计算机中应存储：数据元素的集合D数据元素之间的关系R①、一种数据构造中的关系R，事实上是D上各数据元素之间的联系，并不表达数据在计算机中的存储位置，称为数据的逻辑构造。综上，数据的逻辑构造是数据本身所固有的，而存储构造则可根据运算需要进行设计或构造（即一种逻辑构造可表达成多个存储构造）。在进行数据解决时，应根据需要解决的不同，采用不同的存储构造，以提高解决效率。D中的数据元素用中间标有元素值的方框表达，称为数据结点（结点）；R中的关系用一条有向线段从前件结点指向后件结点。

§2.1.3数据构造的图形表达例：设数据元素的集合为D={di|1≤i≤7的整数}，画出对应于下列关系所构成的数据构造的图形①、R1={(d1,d3),(d1,d7),(d4,d5),(d3,d6),(d2,d4)}②、R2={(di,dj)|i+j=5}③、R3={(d2,d3)(d3,d1),(d1,d4),(d4,d6),d6,d5),(d5,d7)}d2

d3

d1

d4

d6

d5

d7

(D,R3)(D,R1)d1

d3

d7

d6

d2

d4

d5

(D,R2)d1

d4d2

d3

d5

d7

d6

没有前件的结点称为根结点，没有后件的结点称为终端结点（叶子结点），其它的结点称为内部结点线性构造：一种非空数据构造满足下列三个条件，则称该数据构造为线性构造：①、有且仅有一种根结点②、每个结点最多只有一种前件，也最多有一种后件③、插入和删除结点后仍满足①、②线性构造：从根结点到终止点之间只有一条由有向线段连起的途径§2.1.4线性数据构造与非线性数据构造数据的逻辑构造可分为两大类线性构造非线性构造不是线性构造非线性构造：不满足线性构造特点的数据构造，即该构造中结点可能有多个前件和多个后件。典型的非线性构造为图构造，树是一种特殊的非线性构造。树构造图构造§2.2线性表及其次序构造§2.2.1线性表及其运算

1、什么是线性表线性表是由n(n0)个含有相似类型的数据元素a1,a2,,ai,…,an构成的一种有限序列。表中的每一种数据元素，除了第一种外，有且只有一种前件；除了最后一种外，有且只有一种后件。其中n为表长(n=0时为空表），ai为线性表中的第i个元素，ai能够是一种数，符号或其它更复杂的信息。其数据构造表达为：D={a1,a2,,an} R={(a1,a2),(a2,a3),,(an-1,an)}a1

a2

a3

an

……图形表达为：线性表是一种线性构造。逻辑构造例1：一种n维向量：X=(x1,x2,……xn)为一种线性表英语小写字母表(a,b,c,…,z)也是一种线性表例2：某班学生状况记录表，是比较复杂的线性表学号姓名性别年龄成绩970156张小明男2086970157李小青女1983970158赵凯男1970970159李启明男2191970160刘华女1878970161曾小波女1990970162张军男1880970163王伟男2065970164胡涛男1995……………2、线性表的次序存储构造数据的逻辑构造在计算机存储器中的存储方式称为数据的存储构造，数据的存储构造是指：根据存储关系R的方式不同，存储构造分为两种：①、次序存储构造②、链式存储构造①、如何为数据元素分派存储单元②、如何实现数据元素之间的关系 次序存储构造是将（D,R）中逻辑上相邻的数据元素存储在物理上相邻的存储单元中，而数据元素之间关系由存储单元的邻接关系唯一拟定例：D={a,b,c,d,e,f},R=((b,c),(c,d),(d,a),(a,f),(f,e)}逻辑构造存储构造efadcb100510061007100810091010(D,R)可看出：①、次序存储构造重要用于存储线性构造，而存储非线性构造较困难②、次序存储构造必须要有一片持续空间存储数据元素，构造中各元素按它们之间的关系次序寄存将线性表的次序存储构造称为次序表。注意：线性表与次序表的区别数据逻辑构造数据存储构造编程时，可用一维数组或用一组地址持续的存储单元来依次存储线性表中的数据元素。①、用数组v(1:m),构成可存储m个数据元素的线性表v(1)=b,v(2)=c,v(3)=d,v(4)=a,v(5)=f,v(6)=e,表长n=6②、用C动态分派内存地址函数malloc构成可存储m个数据元素的线性表#include“stdlib.h”voidinitsl(ET*v,intm,int*n){ v=(ET*)malloc(m*sizeof(ET)); v[0]=b；v[1]=c；v[2]=d； v[3]=a；v[4]=f；v[5]=e； *n=6；}其中：ET表达线性表中元素的数据类型，n表长在次序表中，设线性表中每一种数据元素占用k个存储单元，线性表中任一元素ai的存储地址可用下式来表达：存储地址ADR(a1)ADR(a1)+k

ADR(a1)+(i-1)*k

ADR(a1)+(n-1)*k

序号内存a1a2

ai

an

12

i

n

mADR(ai)=ADR(a1)+(i-1)*k在次序表中读取任何一种元素所用时间相似，读取元素方便，也称为随机存储构造线性表可进行重要运算：①、在线性表指定位置加入一种新元素（线性表插入）②、在线性表中删除指定元素（线性表删除）③、在线性表中查找某个特定的元素（线性表查找）④、对线性表中元素进行排序（线性表排序）⑤、将一种线性表分解成多个线性表（线性表分解）⑥、将多个线性表合并成一种线性表（线性表合并）⑦、复制一种线性表（线性表复制）⑧、逆转一种线性表（线性表逆转）注意：运算定义在逻辑构造上，在不同存储构造下有不同的实现办法（算法）3、线性表在次序存储下的插入运算设长度为n的线性表为（a1,a2,

,ai-1,ai,,an),现在第i-1与第i个元素间插入一个新元素b，插入后得到长度为n+1的新表为

(a1,a2,…,ai-1,b,ai,…,an)顺序表插入示意图：12

i-1ii+1nn+112i-1ina1a2…ai-1ai…anba1a2…ai-1ai…an-1anbV[1]V[2]V[i-1]V[i]V[n]V[1]V[2]V[i-1]V[i]V[i+1]V[n]V[n+1]该算法涉及到的输入、输出数据：线性表插入异常状况分析，重要分析：①、现在所拥有的条件能否让算法顺利执行完毕②、根据算法特性第四条，规定对的的输入信息对本算法，其异常状况为：①、表满时，不能插入②、插入点不在表中n=mi>ni<1设插在表尾，即i=n+1设插在表头，即i=1要判断异常状况，需用到数据m，必须输入m故：该算法应输入、输出的数据为：线性表插入v,b,i,n,mv,nPROCEDUREINSL(v,m,n,b,i)IF(n=m)THEN{overflow;RETURN}IF(i>n)THENi=n+1IF(i<1)THENi=1FORj=nTOiBY–1DOV(j+1)=V(j)V(i)=b 或 V(j+1)=bn=n+1RETURN其算法为：设长度为n的线性表为(a1,a2,,ai-1,ai,ai+1,,an),删除第i个元素,删除后的线性表为(a1,a2,

,ai-1,ai+1,,an)。3、线性表在次序存储下的删除运算12i-1ii+1na1a2…ai-1aiai+1…anV[1]V[2]V[i-1]V[i]V[i+1]V[n]12

i-1ii+1n-1na1a2…ai-1V[1]V[2]V[i-1]V[i]V[i+1]V[n-1]V[n]ai+1ai+1

…an

该算法涉及到的输入、输出数据：线性表删除异常状况为：①、表空时，不能删除②、删除点超出表范畴n=0i>n或i<1不能进行删除其算法为：PROCEDUREDESL(V,n,i)IF(n=0)THEN{UNDERFLOW;RETURN}IF(i<1)or(i>n)THEN{printf(“Notthiselementinthelist”;RETURN}FORj=iTOn-1DOV(j)=V(j+1)n=n-1RETURN例：C++语言编写次序表基本操作：表初始化、输出、插入与删除（C++幻灯20）次序表操作的特点：1次序表中数据元素的个数需要预先拟定；2由于次序表的随机存取特性，访问每个元素很方便；3插入和删除操作需移动大量的元素，平均为个4、需一片持续空间，线性表容量不易扩充§2.2.2栈及其应用例：下列给出了含有嵌套调用的五个程序1、什么是栈MAIN:…CALLSUB1A:…SUB1…CALLSUB2B:…SUB2…CALLSUB3C:…SUB3…CALLSUB4D:…SUB3……RETURN返回地址：A、B、C、DA、B、C、D构成一种线性表，计算机系统在解决时可用一种线性表来动态记忆调用过程中的途径，即建立一种空线性表，调用函数时将返回地址插入线性表，返回主程序时将返回地址从表中删除；但如何解决插入与删除的元素，才干让调用过程不出差错。要让调用过程不出差错，这四个元素的插入次序必须为A、B、C、D，而删除次序刚好与这相反，为D、C、B、A，如规定只能在一端进行插入与删除操作，可满足上述规定。这种只能在一端进行插入与删除操作的线性表称为栈。允许插入和删除的一端称为栈顶，而不允许插入与删除的一端称为栈底。入栈次序：a1,a2,a3,…,an出栈次序：an,an-1,…a2,a1栈的操作原则：先进后出栈底

栈顶

插入(入栈)删除(出栈)topbottom随着入栈与出栈操作的进行，栈顶的位置浮动变化，为反映这种变化，设立一种栈顶指针top，指向现在栈顶元素的存储位置，设一种栈底指针bottom，指向栈底元素的存储位置。2、栈的基本运算（1）入栈：在栈顶端插入一种新元素（2）出栈(退栈)：从栈顶删除一种元素（3）取栈顶元素：在栈中读栈顶元素3、栈的次序存储构造及其运算栈是一种特殊的线性表，与普通次序存储构造的线性表同样，也可运用一片持续的存储单元依次寄存自栈底到栈顶的数据元素，可用一维数组S(1:m)模拟栈，m为栈的容量普通取：bottom=1入栈：top=top+1S(top)=x出栈：top=top-1y=S(top)栈空：top=0栈满：top=m初始状态：top=0入栈出栈topbottoma0a1an。。。算法2.3在容量为m的栈s中插入一种元素xPROCEDUREPUSH(S,m,top,x)IF(top=m)THEN{stack-OVERFLOW;RETURN}top=top+1S(top)=xRETURN入栈运算异常状况为：栈满时，不能插入top=m该算法涉及到的输入、输出数据：算法2.4在容量为m的栈s中删除一种元素PROCEDUREPOP(S,top,y)IF(top=0)THEN{stack-UNDERFLOW;RETURN}y=S(top)top=top-1RETURN出(退)栈运算异常状况为：栈空时，不能删除top=0该算法涉及到的输入、输出数据：算法2.5读栈顶元素PROCEDURETOP(S,top,y)IF(top=0)THEN{stack-UNDERFLOW;RETURN}y=S(top)RETURN读栈顶元素异常状况为：栈空时，无元素可读top=0该算法涉及到的输入、输出数据：栈是最广泛使用的数据构造之一，子程序的调用，递归过程的实现，体现式的计算都是栈应用的典型例子。自学P38体现式的计算 2.2.3队列及其应用1、什么是队列队列也是一种特殊的线性表，它只允许在一端进行插入，而在另一端进行删除，允许插入的一端称为队尾，用一种尾指针rear批示，允许删除的一端称为队（排）头，用一种排头指针(front)批示。FEDCBA入队(插入)出队(删除)front(头)rear(尾)入队次序：A,B,C,D,E,F出队次序：A,B,C,D,E,F队列的操作原则：先进后出同栈类似，在次序存储构造下，可用一维数组Q(1:m)模拟队列，m为队列的容量入队：rear=rear+1Q(rear)=x出队：y=Q(front)队空：front=rear队满：rear=m初始状态：front=rear=0front=front+1FEDCBA入队出队front(头)rear(尾)由于队列只能在一端插入，在另一端删除，随着入队与出队运算不停进行，队列中元素不停向队尾方向移动，而在排头产生一片不能用的空间，最后可能造成尾指针指向队列最后一种位置，而排头却有一片无法运用的空闲区，这种现象称为“假溢出”frontrear如何避免“假溢出”现象的发生：最简朴的方法，在进行入队与出队运算时，调节队列中元素在存储空间中的位置，即出队时将队列中全部元素依次向排头方向移动一种位置。但这种方法需移动大量的元素，在实际中普通不用，而是采用另一种方法。入队出队KJHm12、循环队列将队列存储空间的最后一种位置饶到第一种位置，形成逻辑上的环状空间，供队列循环使用frontrear循环队列示意图HJKm1m1frontrearKJH队列存储空间入队：rear=rear+1Q(rear)=x出队：y=Q(front)队空：front=rear队满：rear=front初始状态：front=rear=mfront=front+1循环队列的运算Ifrear=m+1Then rear=1Iffront=m+1Then front=1由此可见，循环队列构造即使避免了“假溢出”现象，但却带来一种新问题，无法区别满足条件front=rear的队列是处在队空还是队满的状态，为解决这个问题，可采用两种办法：（1）、另设一种标志以区别队空和队满s=01队空队非空队满条件：s=1andrear=front队列初始状态：s=0且front=rear=m队空条件：s=0入队操作：If(rear=front)and(s=1)Then{“队满”；Return}rear=rear+1Ifrear=m+1Then rear=1Q(rear)=xs=1出队操作：If(s=0)Then{“队空”；Return}front=front+1Iffront=m+1Then front=1y=Q(front)Ifrear=frontThens=0完整的算法见P43~44（2）、用队尾指针追上排头指针这一特性作为队满的条件frontrearKJHfrontKJHrearABC入队时，将rear+1=front作为队满的条件即：rear=rear+1Ifrear=m+1Thenrear=1Ifrear=frontThen“队满”队空：rear=front算法2.6a在容量为m的循环队列Q中插入一种元素xPROCEDUREADDCQ(Q,m,rear,front,x)t=rear+1IF(t=m+1)THENt=1IF(t=front)THEN{“OVERFLOW”;RETURN}rear=tQ(rear)=xRETURN入队运算异常状况为：队满时，不能插入(rear+1)modm=front该算法涉及到的输入、输出数据：算法2.7a在容量为m的循环队列Q中删除一种元素PROCEDUREDELCQ(Q

,m,rear,front,y)IF(rear=front)THEN{“UNDERFLOW”;RETURN}front=front+1IF(front=m+1)THENfront=1y=Q(front)RETURN出(退)队运算异常状况为：队空时，不能删除rear=front该算法涉及到的输入、输出数据：队列在计算机中也有广泛的应用，凡可抽象为线性表并符合先到先服务的解决过程，均可用队列模拟。例VB中的事件队列；计算机中CPU与外设传递数据时，在内存中设立的缓冲区队列。P48介绍了队列在日常生活中应用，自学线性表次序存储构造含有构造简朴，读取元素方便等优点，适合小线性表或长度固定的线性表，但它存在下列几方面的缺点：需一片持续空间，不能运用存储器中的碎片，且线性表容量不易扩充不能对存储空间进行动态分派；

插入和删除操作需移动大量的元素，平均为个对于大的线性表或元素变化频繁的线性表不适宜采用次序构造，而是采用链式存储构造1、线性链表线性链表是线性表的链式存储构造，在链式存储构造中，数据元素可存储在不持续的空间中，各数据元素之间的关系不是由存储单元的邻接关系拟定，而是由指针域拟定。§2.3线性链表及其运算

§2.3.1线性链表的基本概念在链式存储构造中，每一种数据元素的表达由两部分信息构成：一是数据元素的值；二是各数据元素的前后件关系存储数据元素值存储与该结点逻辑上相邻的结点地址即：线性链表中每一种元素的存储单元都由数据域和指针域两部分构成，称为存储结点（结点）只有一种指针域时，其存储内容为该结点后件的地址，无后件结点，指针域为“0”、“NULL”或“”例：已知数据构造B=(D,R)，D={a,b,c,d,e,f}，R={(b,c),(c,d),(d,a),(a,f),(f,e)}，其链式存储构造为：注意：头指针Head是整个链表的唯一标记，通过它可找到链表中任意元素数据元素间的逻辑关系是通过指针来反映的链式构造既可存储线性构造，也可存储非线性构造（多个后件用多个指针域指向，前件也可用指针域指出线性链表的物理状态用链式构造存储线性表时，每个结点的存储空间可任意分派，它们能够不持续，它们之间的关系由指针域拟定在程序设计时，惯用两个一维数组V(1:m)，Next(1:m)存储线性表，用V表达数据，Next表达指针域则第i个结点为数据元素值数据元素地址上例用数组存储：R={(b,c),(c,d),(d,a),(a,f),(f,e)}V(1)=a、V(2)=b、V(3)=c、V(4)=d、V(5)=e、V(6)=fNext(1)=6Next(2)=3Next(3)=4Next(4)=1Next(5)=0Next(6)=5Head=2通过Head可找到链表中任意元素，例： V(Head)=V(2)=bp=Next(Head)=Next(2)=3,V(p)=V(3)=cNext(i)V(i)普通而言，线性链表（a1,a2,a3,ai,an）可用以下逻辑状态图来表达：上例可用下图表达线性链表的逻辑状态：V(1)=a、V(2)=b、V(3)=c、V(4)=d、V(5)=e、V(6)=fR={(b,c),(c,d),(d,a),(a,f),(f,e)}bcadfe0Head234165线性链表中的各结点在计算机中的存储位置分布是杂乱的，但只要抓住了链表的头指针Head，事实上就抓住了表中全部结点。当Head=0时为空表算法2.9依次输出头指针为Head的线性表中各结点值输出链表中各元素异常状况：该算法涉及到的输入、输出数据：空表时无输出PROCEDUREPRTLL(V,Next,Head)j=HeadWhile(j0)Do{outputV(j)j=Next(j)}RETURNP55~56介绍了如何在C++语言中用动态分派内存的办法实现链表，并用一段程序介绍在C++语言中如何创立链表，如何输出链表中各元素，自学前面讨论的链表每个结点只有一种指针域，指向其后件地址，由该指针能方便找到其后件，但不能找到前件，这种链表称为线性单链表(单链表)，在单链表中，只能顺指针向链尾方向扫描，当要寻找某个结点的前件时，只能从头指针开始重新寻找。为弥补单链表的局限性，在应用中可设立两个指针域，一种指向前件，称为左指针；一种指向后件，称为右指针。这样的线性表称为双向链表Llink(i)Data(I)Rlink(i)第i个结点：逻辑状态图：a10a2a30an……Head…2、带链的栈栈和队列是线性表，故栈和队列都可采用链式存储构造Top…an-2an-1ana1栈顶指针相称于链表头指针0Top0…在实际应用中，带栈的链能够用来收集计算机存储空间中含有相似构造的空闲存储空间，这种带链的栈称为可运用栈。由于可运用栈链接了计算机存储空间中含有相似构造的空闲结点，因此，当计算机系统或顾客程序需要存储结点时，可从中取出栈顶结点，当计算机系统或顾客程序释放一种存储结点时，则将该结点放回到可运用栈的栈顶。p从可运用栈中获得一种结点pp将结点p送回可运用栈Top0…用链式存储构造解决实际问题时，首先分派一定的存储空间形成可运用栈，再构造与可运用栈中结点含有相似构造的链表(可能有多个)，这些链表中元素的插入结点取至可运用栈，删除的结点送回可运用栈。因此全部含有相似构造的链表可共用同一种可运用栈算法2.10从栈顶为Top的可运用栈获得一种p输入：

输出：异常状况：栈为空，获得结点失败返回值P=0可运用栈无空间分派失败0可运用栈有空间分派成功PROCEDUREnew(p)p=TopIfp=0ThenReturnTop=Next(Top)Return算法2.11将结点p送回栈顶为Top的可运用栈输入：输出：异常状况：无PROCEDUREdispose(p)Next(p)=TopTop=pReturn可运用栈是一种空表，是为其它链表服务的。下列算法是带链的栈的入栈与出栈运算算法2.12在栈顶为Top1的带链栈中插入一种元素x输入：输出：异常状况：可运用栈为空分派新结点失败pTop10…ana3a2a1xnew(p);ifp=0then“无空间”PROCEDUREPushLL(Top1,x)new(p)Ifp=0Then{“无空间”；Return}V(p)=xNext(p)=Top1Top1=pReturn算法2.13在栈顶为Top1的带链栈中删除栈顶元素p输入：输出：异常状况：栈空，不能删除Top1=0Top10…ana1a2a3PROCEDUREPOPLL(Top1,y)IfTop1=0Then{“栈空”；Return}y=V(Top1)p=Top1Top1=Next(Top1)dispose(p)Return在C语言中用函数malloc()分派空间，用free()释放空间在C++语言中用new分派空间，用delete释放空间3、带链的队列排头指针(front)相称于链表头指针，尾指针(rear)指向链表最后一种元素front0…a3a2a1anrear队空(front=rear=0)，变化头指针和尾指针的值算法2.14在带链队列中插入一种元素x输入：输出：异常状况：可运用栈为空，分派新结点失败p0…ana3a2a1xnew(p);ifp=0then“无空间”rearfront0front=prear=pPROCEDUREADDLL(rear,front,x) new(p) Ifp=0Then{“无空间”；Return} V(p)=x Next(p)=0 Iffront0Then {Next(rear)=p rear=p } Else rear=front=p Return算法2.15在带链队列中删除一种元素输入：输出：队中只有一种结点，删除该结点后，必须变化尾指针(rear)的值frontp0…a2a1a3anrear异常状况：队空，不能删除front=0rear=0PROCEDUREDELLL(front,rear,y) Iffront=0Then{“队空”；Return} y=V(front) p=front front=Next(front) Iffront=0Thenrear=0 dispose(p) Return线性链表可进行的基本运算即为线性表的基本运算，重要介绍前两种运算，在线性链表中，结点之间的关系是由指针的链接关系关系来表达，在对线性链表进行插入与删除时，只需变化指针即可线性表插入、线性表删除、线性表查找、线性表排序、线性表分解、线性表合并、线性表复制、线性表逆转2.3.2线性链表的基本运算一、在线性链表中包含x元素的结点之前插入一种新元素bpb1、为插入的新元素分派一种新结点p，V(p)=b2、在线性表中寻找包含元素x的前一种结点q3、将结点p插入到结点q之后…xa2…a2x…………bp单向链表双向链表单向链表Next(p)=Next(q)Next(q)=p双向链表Llink(p)=qRlink(p)=Rlink(q)Llink(Rlink(q)=pRlink(q)=pqqa2x……………xa2…二、在线性链表中删除包含元素x的结点p1、在线性表中寻找包含元素x的前一种结点q2、删除结点q的后一种结点3、释放被删除的结点p单向链表双向链表单向链表Next(q)=Next(Next(q))双向链表Rlink(q)=Rlink(Rlink(q))Llink(Rlink(Rlink(q)))=qqq从上面分析可看出，线性表的插入与删除不涉及数据元素的移动，但也存在两个问题：１、插入时，从何处得到空闲的结点作为新元素结点；删除时，被删除结点应释放到何处才干被后来使用，即如何管理空闲结点(用可运用栈)2、在非空链表中寻找包含指定元素的前一种结点算法2.16在头指针为Head的非空链表中寻找包含元素x的前一种结点q输入：输出：2、x在表中第一种元素异常状况：1、空表3、x不在表中放入插入与删除算法中考虑qPROCEDURELookST(Head,x,q)q=HeadWhile(Next(q)≠0)and(V(next(q))≠x)Doq=Next(q)Return如链表中未包含元素x，q指向链表最后一种元素即返回值Next(q)=0 x不在链表中Next(q)≠0q为x前件地址Head…a2a1xan0三、线性表的插入与删除算法算法2.1７在头指针为Head的线性链表中包含元素x的结点前插入结点b，如链表中无元素x，则将b插入到链表的末尾。②、x在表中第一种元素，插在表头异常状况：①、空表，插入结点为表中第一种结点③、x不在表中，插在表尾输入：输出：Head=0V(Head)=xLookST(Head,x,q)Next(q)=0④、无空间，不能插入pb…xa2…qPROCEDUREInsLst(Head,x,b)new(p)Ifp=0Then{“无空间”；Return}V(p)=bIfHead=0Then{Head=p;Next(p)=0;Return}IfV(Head)=xThen{Next(p)=Head;Head=p;Return}LookST(Head,x,q)Next(p)=Next(q)Next(q)=pReturn…xa2…算法2.1８在头指针为Head的线性链表中删除包含元素x的结点②、删除元素为表中第一种结点异常状况：①、空表，不能删除③、x不在表中，不能删除Head=0V(Head)=xLookST(Head,x,q)Next(q)=0PROCEDUREDelSt(Head,x)IfHead=0Then{“空表”;Return}IfV(Head)=xThen{p=Next(Head);dispose(Head);Head=p;Return}LookST(Head,x,q)IfNext(q)=0Then{“无此结点”;Return}p=Next(q)Next(q)=Next(p)Dispose(p)Returnpq线性链表插入与删除示意图见书P68图2.26P70图2.27输入：输出：四、循环链表增加一种表头结点，数据域任意或根据需要设立，指针域指向线性链表的第一种结点，Head指向表头结点最后一种结点指针域不为空，而是指向表头结点空循环链表注意：①循环链表能够从任何一种结点出发去访问其它结点②循环链表和单链表鉴定表的结束标志的办法不同：循环单链表的结束标志：Next(P)=Head单链表的结束标志：Next(P)=0④循环链表的插入和删除算法和单链表类似。自学③循环链表和单链表鉴定空表的办法不同：循环单链表为空表标志：Head=Next(Head)单链表为空表标志：Head=01.次序表占用的存储空间最少，而双链表占用的存储空间最多2.次序表是一种随机存储构造，访问表中的某一种元素方便；单链表元素的访问则必须从头指针开始按次序依次去寻找待访问的元素。3.一种次序表一旦拟定则其大小就不能够随意变化，因此操作中需要进行“判满”的工作，而链表的大小却可方便的变化，但链表占用的存储空间较多。4.次序表的操作重要消耗在元素的移动上，效率较低，单链表的操作消耗在指针的移动上，双链表的操作极为方便，但却是建立在存储空间的消耗上的。总结:五、线性表的应用一元多项式相加任何一种一元多项式Pn(x)都可按升幂表达为：Pn(x)=p0+p1x+p2x2+…+pixi+…+pnxn可见Pn(x)由n+1个系数（p0，p1，…，pi，…，pn）唯一拟定，可用一种线性表P来表达系数的集合，其中Pi(x)项的指数隐含在系数pi中。该线性表可表达为：P=（p0，p1，…，pi，…，pn）表长为n+1。同理，再设一种一元多项式Qm(x)，此多项式也可由一种线性表Q=（q0，q1，…，qi，…，qm）(表长为m+1)来表达。若要计算：Rn(x)=Pn(x)+Qm(x)，这里不失普通性，假定m<n。Rn(x)也可用线性表R=(p0+q0，p1+q1，…，pm+qm，pm+1,…，pn）来表达，显然能够对P、Q、R采用次序构造存储，采用次序表形式解决这种多项式的相加。但是，若已知多项式为S(x）=1+3x10000+5x30000，此时再用将指数项隐含在系数中的方式，用系数次序表来表达S（x），则其表长为30001，而表中只有3个非零元素，浪费了大量的存储空间。因此，普通状况下的一元n次多项式可写成：Pn(x)=P1xe1+P2xe2+…+Pixei+…+Pmxem，其中Pi是指数为ei的非零系数项，且满足0≤e1<e2<…<em，可用每个元素有两个数据项的线性表R=((P1,e1),(P2,e2),…，(Pm,em))来表达。此线性表可用次序和链式构造存储。+=p0p1p2…pmpn…q0q1q2…qmp0+q0p1+q1p2+q2…pm+qm…pntypedefstructpoly{intcoef;intexp;}elemtype;typedefstructpolynty{elemtypedata[Max];intnum;}polynty;用次序表的形式表达的一元多项式，仅用于只对多项式进行求值等不变化多项式系数和指数项（即不进行插入、删除等变化元素间的逻辑关系的操作）的运算。若要进行其它运算，则要采用链式存储构造。如：要实现一元多项式的加法运算，须涉及到插入、删除等变化元素逻辑关系的操作。用C描述此线性表的次序存储构造以下：p1+e1p2+e2pm+emdata[0]data[1]data[m]data[Max-1]…num单链表元素数据类型和结点的C语言描述为：typedefstructnode{floatcoef;intexp;structnode*next;}node;数据域

指针域

一元多项式相加的运算规则：对两个一元多项式中全部指数相似的项，对应指数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一元多项式中全部指数不相似的项，则插入到“和多项式”中。例、已知：A4(X)=7+3X+9X8+5X17B3(X)=8X+22X7-9X8

求：C(X)=A4(X)+B3(X)

pqp实现办法和环节：在其中一种链表的基础上构造“和多项式”将p,q指针分别指向A，B链表的第一种结点。

依次比较p,q指针所指向结点的数据域中的指数项。pqqif(pexp<qexp){p指针指向的结点是和多项式的结点(以A表为基础，便不必插入）；p指针后移指向A表的下一种结点；}ppfree(*hb)elseif(p

exp==qexp){系数相加；(x=p

coef+qcoef)if(x!=0){以x做为该结点的系数项；释放q结点；p,q指针同时后移；}else{删除p,q结点；释放p,q结点；p,q指针后移；}elseif(p

exp>qexp){q结点为和多项式的结点，将其插入到p结点之前；q指针后移；}始终比较到两表中有一张表已到结束结点为止：if(A表到头：pnext==NULL){将B表中剩余的结点插入到A表之后；}

释放B表的头结点。2.4数组数组是大家都已经很熟悉的一种数据类型，几乎全部高级语言程序设计中都设定了数组类型。但数组是什么数据构造：一维数组(a1,a2,……an)能够当作是一种长度为n的线性表二维数组

线性构造逻辑构造采用次序存储构造存储物理构造能够当作一种长度为m的线性表，表内元素(ai1,ai2,……ain)又可当作一种长度为n的线性表；或当作一种长度为n的线性表，表内元素(a1i,a2i,……ami)当作一种长度为m的线性表2.4.1数组的次序存储构造1、按行依次寄存数组中各元素(以行为主分派方式)VB、C中用2、按列依次寄存数组中各元素(以列为主分派方式)FORTRAN中用二维数组的次序存储有以下两种形式：amnam2am1a2na22a21a1na12a11…………amna2na1nam2a22a12am1a21a11…………以行为主存储形式以列为主存储形式数组中普通运算是，给定一种下标，拟定与之对应的数据元素存储地址，设每个元素占用L个字节以行为主：ADR(aij)=ADR(a11)+[n*(i-1)+j-1]*LADR(a11)ADR(a11)以列为主：ADR(aij)=ADR(a11)+[m*(j-1)+i-1]*L2.4.2规则矩阵的压缩存储矩阵是一种二维数组，它是诸多科学与工程计算问题中研究的数学对象。矩阵能够用行优先或列优先办法次序寄存到内存中，但是，当矩阵的阶数很大时将会占较多存储单元。而当里面的元素分布呈现某种规律时，这时，从节省存储单元出发，可考虑若干元素共用一种存储单元，即进行压缩存储。所谓压缩存储是指：为多个值相似的元素只分派一种存储空间，值为零的元素不分派空间。压缩存储时，节省了存储单元，但如何在压缩后找到某元素呢？因此还必须给出压缩前的下标和压缩后下标之间变换公式，才干使压缩存储变得故意义。规则矩阵：非零元素的分布有规则的矩阵上三角矩阵

下三角矩阵

1．三角矩阵

上三角矩阵和下三角矩阵

22211211..................nnnnacccaacaaaaij≠ci≥j=ci<jaij≠ci≤j=ci>jc为某一常量或为“０”222111..................1nacaacca2nanna...aij=B[i(i-1)/2+j](j≤i)C(j>i)

下三角矩阵压缩存储时，元素值为常数C或0的元素不必存，只需存下三角部分元素，n阶下三角矩阵有n2元素，只需存下三角的元素,共:1+2+3+…+n=n(n+1)/2个可选用一维数组B依次寄存，只需存储n(n+1)/2个元素，可节省大概二分之一的空间,存储形式为:压缩复原(解压缩)a11a21a22a31a32a33…an1an2…ann以行为主a11a21an1a22a32…a33a34…an4…an2…ann以列为主或则，对于下三角矩阵中元素aij(j≤i)在一维数组中为第k个元素，即aij＝B[k]在以行为主的压缩形式下：k=(1+2+3+…+i-1)+j=i*(i-1)/2+j下三角矩阵以列为主及上三角矩阵压缩存储见P85，自学k=1Fori=1TonForj=1Toi{B[k]=a[i,j]k=k+1}Fori=1TonForj=1Ton{Ifj≤ia[i,j]=B[i*(i-1)/2+j]Elsea[i,j]=0}222111..................1nacaacca2nanna...2．对称矩阵aij=B[i(i-1)/2+j](j≤i)B[j(j-1)/2+i](j>i)只需存储下三角元素即可,用B[1:n(n+1)/2]以行为主存储,访问时：j≤iaij=B[i(i-1)/2+j]j>iaij=aji=B[j(j-1)/2+i]即：3．对角矩阵若矩阵中全部非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。例如，7×7的三对角矩阵有三条对角线上元素非0。一个7×7的三对角矩阵222111..................1naa2naaa1na12a2naann...aij=B[2(i-1)+j](i-1≤j≤i+1)0(j<i-1或j>i+1)三对角矩阵压缩存储时，只需存三对角元素，共3(n-2)+4=3n-2个，用B[1:3n-2]以行为主存储，访问时，i-1≤j≤i+1时aij=B[k]；其它aij=0aij=B[2(j-1)+i](i-1≤j≤i+1)0(j<i-1或j>i+1)同理，以列优先依次寄存，要访问i行j列元素aij的公式为：k=[3(i-1)-1]+(j-i+2)=2(i-1)+j2.4.3普通稀疏矩阵的表达在特殊矩阵中，元素的分布呈现某种规律，故一定能找到一种适宜的办法，将它们进行压缩寄存。但是，在实际应用中，我们还经常会碰到一类矩阵：其矩阵阶数很大，非零元素个数较少，零元素诸多，但非零元素的排列没有一定规律，我们称这一类矩阵为稀疏矩阵。00300001000000009000000000007000000000600002030000500000例：以下7×8矩阵，56个元素中只有8个非零元素，其它均为零元素，而非零元素分布是无规则的。这类矩阵也可采用压缩存储，只存储非零元素，但由于非零元素分布无规律，压缩时，除寄存非零元素的值外，还必须存储适宜的辅助信息，才干快速拟定一种非零元素是矩阵中的哪一种位置上的元素。1、稀疏矩阵的次序存储为了使稀疏矩阵通过压缩后，能方便地访问其中每一种非零元素(访问不到的为零元素)，普通需给出三个信息：①非零元素所在行号②非零元素所在列号③非零元素值即一种非零元素可用一种三元组(i,j,v)表达。上例三元组可表达为：IJV78813318131945757664266373500300001000000009000000000007000000000600002030000500000123456712345678所对应的三元组为：(1,3,3)(1,8,1)(3,1,9)(4,5,7)(5,7,6)(6,4,2)(6,6,3)(7,3,5)为表达唯一性，添加一种三元组:（总行数，总列数，非零元素个数），即(7,8,8)，表达稀疏矩阵的总体信息。因此，一种含有t个非零元素的稀疏矩阵可用t+1个三元组表达，其中第一种三元组用于表达稀疏矩阵的总体信息，其后各三元组依次表达各非零元素，且按以行为主的次序存储。惯用三列二维的表格或数组形式表达(三列二维数组)，如图。2、稀疏矩阵的链式存储构造当稀疏矩阵中非零元素的位置或个数经常变动时，三元组的次序存储构造就不适合，此时，采用链表作为存储构造更为恰当。稀疏矩阵的链式存储构造办法有几个，如带行指针的单链表表达法和十字链表表达办法。⑴．带行指针的链表把含有相似行号的非零元素用一种单链表连接起来，稀疏矩阵中的若干行构成若干个单链表，合起来称为带行指针的链表。例如，上例稀疏矩阵的带行指针的链表描述形式：73

5

^

4

57

^

5

218

^0030000100000000900000000000700001800006000020300005000001234567123456783

1

9

^1

3

31

8

1

^6

6

3

^6

4

2

1行指针2^45637这种办法能方便找到同一行的全部非零元素，但不便寻找同一列的全部元素⑵．十字链表十字链表是稀疏矩阵的的一种较好的存储办法，在该办法中，每一种非零元素用一种结点表达，结点中除了表达非零元素所在的行、列和值的三元组（i,j,v）外，还需增加两个链域：行指针域(rptr)，用来指向本行中下一种非零元素；列指针域(cptr)，用来指向本列中下一种非零元素。稀疏矩阵中同一行的非零元素通过向右的rptr指针链接成一种链表。同一列的非零元素也通过cptr指针链接成一种链表。因此，每个非零元素既是第i行链表中的一种结点，又是第j列链表中的一种结点，相称于处在一种十字交叉路口，故称这种链表为十字链表。十字链表结点向右域向下域值域列域行域rowcolvaldownright指向本行下一种元素指向本列下一种元素另外，为了运算方便，我们规定行、列循环链表的表头结点和表达非零元素的结点同样，也定为五个域，且规定行、列、域值为0，并且将全部的行、列链表和头结点一起链成一种循环链表。在行（列）表头结点中，行、列域的值都为0，故两组表头结点能够共用，即第i行链表和第i列链表共用一种表头结点，这些表头结点本身又能够通过V域（非零元素值域，但在表头结点中为next，指向下一种表头结点）相链接。另外，再增加一种附加结点（由指针H批示，行、列域分别为稀疏矩阵的行、列数目），附加结点指向第一种表头结点，则整个十字链表可由H指针惟一拟定。

5430070010200400000009123451234例：如图稀疏矩阵的十字链表描述形式：147113344000000231549312000000H00000000在表头结点中，行、列域的值都为0，故两组表头结点能够共用，即第i行链表和第i列链表共用一种表头结点，这些表头结点本身又能够通过V域相链接。再增加一种表头结点H，则整个十字链表可由H指针惟一拟定2.5树与二叉树

树是一种简朴的非线性构造，在树这种数据构造中，全部数据元素之间的关系含有明显的层次特性。如图，可用于描述含有层次关系的数据。如学校行政关系构造(P114图2.40)ABCDEFGIHJ2.5.1树的基本概念1、定义：树是由n个（n>0）含有相似类型的结点元素构成的有限集合，且满足下列的条件：1)其中有一种结点无直接前驱，称为根（Root）；2)其它的结点元素可分为m个互不相交的子集T1,T2…Tm，这m个子集本身又构成树，称为Root的子树。上右图所示为一棵树，其中A为根，它有三棵子树：T1={B,E,F};T2={C,G,H,I,J};T3={D}在子树T2中，C是该子树的根，它有三棵子树：T21={G}；T22={H}；T23={I，J}；T22和T21仅有一种根结点，没有子树。注意：（1）树的定义中n>0，即没有空树的概念；（2）树的定义中采用了递归定义的办法，显示了树构造本身的这种递归的性质。2、树的有关术语ABCDEFGIHJ根结点、父结点、子结点、叶子结点、内部结点或分支结点(度不为0的结点)兄弟结点(含有同一父结点的子结点称为兄弟结点)结点的度、树的度，树的深度、子树森林：是m(m>0)棵树的集合有序树树中结点在同层中按从左到右有序排列，不能交换的树称有序树，反之称无序树例:((a+(b+c/d))+(e*h-g*f(s,t,x+y))的体现式树3、可用树型构造描述一种体现式：用操作数代表树叶，运算符代表非叶子结点，所构成的树称体现式树。编译系统中惯用的体现式表达办法。体现式树是有序树,结点次序不可更改。+b+a-cd/+*eh+xy*gfts树在计算机中可用多重链表表达，即每个结点有多个指针域，每个指针域指向它的一种子结点，每个结点的指针域数由该结点的度拟定4、树的存储值度Link1Link2…LinknABCDEFG例：ABCDEFG3210000BT1、定义：二叉树是由n个（n0）含有相似类型的结点元素构成的有限集合，且满足下列的条件：（1）由一种根结点和它的两棵左右子树构成；（2）其左右子树分别又构成一棵二叉树。注意：①二叉树的定义中n0，即表达有空二叉树的概念；②二叉树的定义中也采用了递归定义的办法，显示了二叉树构造本身的这种递归的性质。③二叉树的子树有左右之分，次序不能颠倒。由定义知二叉树有五种基本形态，以下图所示：2.5.2二叉树及其基本性质空性质1在二叉树的第K层上，最多有2k-1(1≤k)个结点。性质2深度为m的二叉树最多有2m-1个结点。2、二叉树的基本性质性质3在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一种。性质4含有n个结点