软件技术基础：第一章 数据结构

1、第一章数据结构1.1 数据结构的基本概念数据、数据项、数据元素、数据结构、直接前趋、直接后继、逻辑关系（线性和非线性结构）、存储方法（顺序和链式）、操作方法（遍历，插入，更新，删除，查找，排序）、抽象数据结构1.2 线性结构线性表（顺序表和链表）、栈（顺序栈和链栈）、队列（顺序队列和链队列）、数组（定义和压缩存储方式）1.3 非线性结构树（普通树和二叉树）、图1.4 查找和排序基本概念、方法和算法实现、各方法的效率评估和比较1.1数据结构的基本概念一、什么是数据结构 计算机解一个有关数值计算的具体问题的步骤：建立数学模型设计解模算法编程调试输出结果 建立数学模型的实质是：分析实际问题，寻找包含

2、在问题中的操作对象，以及这些对象之间的关系，并用数学的语言对这些操作对象和其间的关系加以描述，这就是该问题的数学模型。数值计算问题中的数学模型通常可用数学方程来描述，但是更多的非数值计算的问题却无法用数学方程来描述其数学模型。这三张查询表就是学生成绩查询的数学模型，各元素间存在线性关系，因此这种数学模型称为线性数据结构。 例1 学生成绩查询 例2 人机对奕问题（五子棋） 对奕的过程是在一定的对奕规则和取胜策略下进行的，因此为使计算机能够灵活对奕必须事先将对奕的规则、以及对奕过程中可能出现的情况和相应的策略都存入计算机。在人机对奕过程中，计算机操作的对象是对奕过程中可能出现的棋局状态（称为格局）

3、。abcd 联想一下，若将一局棋从开始到结束可能出现的格局都画出来，可以得到下面一张图： 因此，对奕问题中的数学模型就是以各种格局为元素的一种“树”结构。可以看出这种树结构中元素的关系不是简单的线性关系，是另一种典型的数据结构，称为“树结构”。例3、利用交通灯进行多叉路口的交通管理问题。 本题中可以用一个圆圈表示一条通路，两个通路之间的矛盾关系用对应两个圆圈的连线表示（圆圈称为顶点、连线称为边），则设置交通灯的问题可以等价为对圆圈的染色问题。要求： 每个顶点染一种颜色。 相连的顶点不能染相同的颜色。 总色类最少。A BA CA DB AB CB DD AD BD CE AE BE CE D 它

4、是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。 由此我们可以这样来定义数据结构： 用计算机来解决这类问题时，要处理的问题是诸如顶点和边这样的元素，数据结构中称这种为图结构，于是这类问题的数学模型就是图这种数据结构。 由此，至少要四种颜色的交通灯才能满足保证交通秩序的要求。二、数据结构中的有关基本概念 数据(data)：数据是指所有能输入到计算机中并能被计算机程序处理的符号的总称。1234567810101110ABCDEFG 数据元素(data element)：是数据结构的基本单位。 数据项(data Item)：一个数据元素可以由若干个数据项组成，它

5、是数据的不可分割的最小单位。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。 直接前驱、直接后继：在数据结构中的任意一个元素与之相邻且在它之前的元素称为该元素的直接前驱，与之相邻且在它之后的元素称为该元素的直接后继。学生成绩表对奕树交通管理图三、数据结构的三个层次数据元素之间的逻辑关系线性结构和非线性结构数据元素的存储结构线性存储结构、链式存储结构和散列存储结构数据结构的操作集合元素的遍历，插入，更新，删除，查找，排序1、数据元素之间的逻辑关系线性结构：该结构中有且仅有一个开始元素和结束元素，中间所有元素有且仅有一个直接前驱，有且仅有一个直接后继，这样的数据结构称为线性结构。典型

6、的线性结构有线性表，如：学生成绩表。非线性结构：该结构中一个元素可能有多个直接前驱和多个直接后继，这样的数据结构称为非线性结构。典型的非线性结构为图结构，而树是一种特殊的非线性结构。线性结构树结构图结构2、数据结构的存储方式顺序存储结构：该方法是将逻辑关系相邻的数据元素存储在地址相邻的存储单元中。多用于线性结构的存储。各元素之间的逻辑关系是通过存储单元(物理位置)的相邻的关系来反映的。链式存储结构：该方法是用一组离散的存储单元来存放数据结构中的各元素。此方法中，每个元素所占的存储单元分成两部分：一部分为数据域，用于存储数据元素本身；另一部分为指针域，指示其后继或前驱元素的存储地址，从而结构中的

7、各数据元素间形成了一个链。存储单元地址100130160190存储单元地址P4300P1P23、数据结构中常见的操作：遍历：查看数据结构中的所有数据元素。插入：添加新的元素到一个数据结构中。删除：将指定元素从数据结构中去掉。更新：修改数据结构中的某个数据元素。查找：在数据结构中寻找满足条件的数据元素。排序：将数据结构中的数据元素按指定的顺序排列。元素间的逻辑关系是由指针来反映的。数据结构的三个层次之间的关系逻辑关系与存储结构是否一一对应？比如线性结构对应顺序存储方式，非线性结构对应链式存储方式？不是，同一种逻辑关系可采用不同的存储方法，比如线性结构可以采用顺序和链式存储方式。同样的同一种存储方

8、法可以表达不同的逻辑关系，比如链式储存方式可以存储线性和非线性结构。选择何种存储结构来表示相应的逻辑结构，主要是使其运算方便及根据算法的时空要求来具体确定。数据的运算不仅受到逻辑关系存储结构的影响，而且有其自身的特点不同的存储结构的运算是不同的，比如顺序存储结构和链式存储结构的插值算法就是不同。同样的数据的运算有其本身的特点，对线性表上的插入、删除运算限制仅在表的一端进行，则该线性表称之为栈；而插入限制在表的一端进行，删除限制在表的另一端进行的线性表称为队列。数据结构的逻辑关系、存储结构和操作集合要作为一个整体来理解，其中任何一个的改变会导致不同的数据结构。四、抽象数据类型1、数据类型的定义：

9、是指一个值域和定义在这个值域上的一组操作集合的总称。如：整型是定义在（-32768，32767）上的整数以及定义在该值域上的一组操作：+、-、*、/、%。高级语言中定义的这些数据类型，将用户不必了解的细节都封装在数据类型中，从而实现了信息的隐藏，完成了数据抽象。例：8 - 7 = 1 8的二进制代码：00001000 7的二进制代码：00000111 7的补码： 11111001 8 - 7 = 8 + 7的补码 = （00000001）二进制 =（1）十进制2、抽象数据类型（ADT）的定义：是指一个数学模型以及定义在该模型上的一组操作的集合。注意：定义中的数学模型既包含了数据类型概念中值域的

10、含义，还包含了非数值计算领域中的的含义。因此一方面ADT和数据类型的含义相同，另一方面ADT的范畴比数据类型的范畴更广。3、ADT定义的格式：ADT数据类型名 数据对象：（数据对象的定义） 数据关系：（数据关系的定义） 基本操作：（基本操作的定义） ADT抽象数据类型名 高级程序语言中不仅可以使用各种已有的数据类型，还可以根据用户的需求自己定义新的数据类型。struct student int id ; char name20; int classes; float score4; elemtype;右边的结构体是否是一个完整的ADT定义？1.1 思考题1、分析一个具体的数据结构如何入手？2、

11、常见的数据结构有哪些？各有什么特征？3、抽象数据类型的含义？1.2 线性结构线性结构中数据元素的逻辑关系： 存在一个唯一的“开始元素”和一个唯一的 “结束元素”（有限性）。 其间任何一个元素都有且仅有一个直接前驱、 有且仅有一个直接后继（有序性）。1.2.1 线性表一、定义： 线性表是由n(n0)个具有相同类型的元素 a1， a2， ， ai ， ， an , 所构成的一个有限的线性序列。其中 n 为表长，ai 为线性表中的第i个元素， ai 可以是一个数，符号或其它更复杂的信息，但 ai 必须具有相同的数据类型。开始元素：无直接前趋，有且只有一个直接后继结束元素：无直接后继，有且只有一个直接

12、前趋典型线性结构：线性表、堆栈、队列、数组、串等(1,2,3,4,5,6,7)(SUN,MON,TUE,WED,THU,FRI,SAT)二、线性表的ADT定义ADT Linear_List 数据元素： ai具有相同的数据类型，1 i n 。 逻辑结构： a1为“开始元素”无前驱； an为“结束元素” 无后继；中间任何一个元素都存在以下关系： ( i=1,2,n-1 )。 操作集合：INITIATE（L）：初始化线性表。 LENGTH（L）；求表长，返回值为int 型。 GET（L，i )：访问表中的第 i 个元素。 LOCATE（L，X）：定位，查找表中等于X的元 素的位置，返回值为 int

13、型。 INSERT（L，i, X)：在表L的第i个位置上插入X。 DELETE（L，i)：删除表L中的第i个元素。 Linear_List ；LOCATE(L,X): 返回表中等于 X 的元素的序号i。 若表中有m(m1)个元素等于X， 则 返回序号最小的i。 若ai X，则返回（false)。INSERT(L,i,x): if(1i(LENGTH(L)+1) 则在L的第i个位置上插入X； n + + ; return ( true ); else return(flase);DELETE(L,i) : if( 1 i LENGTH(L) 删除L中的第i个元素； n - ; return(删除

14、的元素); else return(NIL);相关操作的具体含义 ADT定义了基本操作，更复杂的操作如将两个线性表合成一个线性表，可由基本操作完成。例：已知存在线性表LA，LB，求LA=LA U LB。设两 线性表中的元素的数据类型同为elemtype。 思路：以A表作为骨架构造和链表，把B表中的每个元素依次取出，比较A表中有无该元素，没有则把该元素插入到A表的最后即第i=n+1个位置上。这里比较A表中有无该元素的过程，可用定位操作来实现，把B表中取出的元素x在A表中做定位操作，若其返回值为1n的整数时说明元素x在A表中有，对求“并集”操作来讲元素x无须插入到A表；若其返回值为false时，说

15、明A表中没有元素x，此时应插入。 1、求A表的长度：n=length(LA)； 2、用一个循环来依次取B表中的各元素：x=get (LB,i)； 3、把x在A表中定位：k=locate(LA,x)； 4、如果k= = false就将插入在A表的最后：insert (LA,n+1,x)； 5、表长加1：n+； #define true 1 #define false 0 void union (LA,LB) Linear_List LA,LB; int i,k,n; elemtype x ; n = LENGTH(LA); /* 取LA表的表长 */ for(i=1;i LENGTH(LB);i

16、+) x = GET(LB,i); /* 取LB表中的第 i 个元素 */ k = LOCATE( LA,x); /* x在LA中定位 */ if(k = false) /* 若LA中的元素 ai x */ INSERT(LA,n+1,x); /* 将x插入LA的后面*/ n + + ; /* 表长加1 */ 作业：假定A、B两表都是递增有序的线性表，设计一个程序利用以上基本操作，实现LA=LA U LB 得到的LA保持递增有序。#define true 1 #define false 0 void union (LA,LB) Linear_List LA,LB; int i,k,n,j; e

17、lemtype x ; n = LENGTH(LA); /* 取LA表的表长 */ for(i=1;i LENGTH(LB);i+) x = GET(LB,i); /* 取LB表中的第 i 个元素 */ k = LOCATE( LA,x); /* x在LA中定位 */ if(k = false) /* 若LA中的元素 ai x */ If (x GET(LA,n) /*若x大于LA中最后一个元素，则在LA中n+1位置插入*/INSERT(LA,n+1,x); for (j=1;j GET(LA,j) & xnext=NULL;s =(node *)malloc(sizeof(node);s-d

18、ata = ai;p-next = s;p=s;p-next = NULL;ha1a2aianhpsa1a2spaianp设置一个前驱指针p：p=h;算法二、单链表的访问算法。 PP P P单链表的访问就是访问单链表中的第 i 个元素。注意：单链表中任意两个元素的存储位置都没有固定 的关系，每个元素的存储位置仅包含在其前 驱结点的指针域中。 设p指针指向ai结点（数据域为ai的结点）， 则： p data=ai； p nextdata=ai+1； 因此，在单链表中访问第i个元素必须从头指针出发，依次寻找，直到找到第i个元素为止。PC语言实现：、未访问到ai结点返回空元素。步骤：、p指向头结点，

19、结点计数器j置0；、若p还未指向ai结点且未到表尾则p后移，j+；、找到结点访问ai结点并返回ai ； p=h；j=0;while(jnext!=NULL) p=p-next; j+; if(j=i&p！=NULL) return(p-data);else return(NIL);寻找ai -1结点，判i是否有效。申请一个新结点t(tdata=x)。重新建立x和ai之间的链：tnext=pnext;重新建立 ai-1 和 x 之间的链：pnext=t;算法三、单链表的插入算法。INSERTSL（node *h,int i,elemtype x)的含义：已知线性表 sl= （a1,a2,a3,a

20、i-1,ai,an）要在ai-1 和 ai 之间插入 x 使 sl=（a1,a2,a3,ai-1,x,ai, an）。 t步骤：C语言实现： P能交换吗？算法四、单链表的删除算法。 单链表的删除deletesl（node *h,int i)的含义：已知线性表 sl=（a1,a2,a3,ai -1,ai,ai +1,an）要去掉元素 ai ， 使：sl=（a1,a2,a3,ai-1,ai+1,an）。 P S(free(s)步骤： 寻找ai-1结点，判i是否有效； 重新建立ai-1和ai+1与x之间的链：Pnext=Snext； 释放 ai 结点。C语言实现：注意：单链表的插入和删除算法中都需要

21、判i是否有效，但判断条件不一样。4、循环单链表定义：将单链表中最后一个结点的指针指向头结点， 从而使整个单链表形成一个环。逻辑示意图：空循环 链表注意： 循环链表可以从任何一个结 点出发去访问其他结点。 循环链表和单链表判定表的结束标志的方法不同： 循环单链表的结束标志：pnext= h；(书中为 *h) 单链表的结束标志：pnext = NULL ； 循环单链表的插入和删除算法和单链表类似。例、将两个链表(a1,a2,ai, an)和(b1,b2,bi, bn)合成一个新链表(a1,a2,ai,an,b1,b2,bi, bn)的算法。 qfree(*hb)步骤：遍历A表，找到A表的尾结点an

22、。将B表的第一个结点b1连接到A表的尾结点an之后。遍历B表，找到B表的尾结点bn。让bn结点的指针指向A表的头结点。释放B表的头结点。 Pq例、用尾指针表示的循环单链表来实现两个链表的合并。步骤： 保留指向A表的头结点的指针：p = ranext； 将A表的尾结点和B表的第一结点相连： ra next = rb next next； 保留指向B表的头结点的指针：q = rbnext； 将B表的尾结点和A表的头结点相连：rbnext = p； 释放B表的头结点：free(q)。 free(q) P5、双链表定义：链表中结点的指针域中不仅包含了指向后继结点的指针也包含了指向前驱结点的指针，这样的

23、链表称为线性双链表。 双链表结点的结构：指向前驱结点的指针域数据域指向后继结点的指针域 逻辑示意图：注意： 从双链表的任一结点出发均可访问链表中所有 结点。 双链表不须头指针来标识，用指向表中的任一 结点的指针均可标识双链表。 双链表结点结构的C 语言描述： typeded struct node_dl elemtype data; struct node *prior , *next ; node; 双链表常见操作的C 语言实现算法一、插入算法已知：dL=（a1,a2,ai-1,ai, an），insertdL(dL,x,i)的含义是在dL中的 ai-1和 ai 元素之间插入x，使插入后的链

24、表dL= （a1,a2,ai-1,x,ai, an）。Pt算法二、删除算法 已知：dL=（a1,a2,ai-1,ai,ai+1 ,an），deletedL(dL,i)的含义是将dL中的第个元素 ai 删除，使删除后的链表dL=（a1,a2,ai-1,ai+1, , an）。P free(P) 以上给大家介绍了顺序表的两种不同的存储结构：顺序表和链表（单链表、循环单链表、双链表）以及不同存储结构下的一些常见操作的实现方法。 顺序表占用的存储空间最少，而双链表占用的存储 空间最多。 顺序表是一种随机存储结构，访问表中的某一个元 素方便；单链表元素的访问则必须按照一定的顺序 依次去寻找待访问的元素。

25、 一个顺序表一旦确定则其大小就不可以随意改变， 因此其操作中不可避免地要进行“判满”的工作， 而链表的大小却可方便的改变，但链表占用的存储 空间较多。 顺序表的操作主要消耗在元素的移动上，效率较低， 单链表的操作消耗在指针的移动上，双链表的操作 极为方便，但却是建立在存储空间的消耗上的。五、线性表的应用 一元多项式相加任何一个一元多项式Pn(x)都可按升幂表示为： Pn(x) = P0 +P1x + P2x2 + + Pixi + + Pnxn 可见Pn(x)由n+1个系数（ P0，P1， ，Pi， ，Pn）唯一确定，可用一个线性表P来表示系数的集合，其中Pi(x)项的指数隐含在系数Pi中。该

26、线性表可表示为： P= （ P0， P1， ， Pi， ， Pn）表长为n+1。 同理，再设一个一元多项式Qm(x)，此多项式也可由一个线性表Q =（Q0，Q1，Qi，Qm）表长为m+1来表示。若要计算： Rn(x) = Pn(x)+ Qm(x)，这里不失一般性，假定mn。 Rn(x) 也可用线性表R=(p0+q0，p1+q1，pm+qm，pm+1，pn）来表示，这时显然可以用顺序表的形式来表示和处理这种一元多项式和一元多项式的相加。 i+= 但是，若已知多项式为 S（x）= 1+3x10000+5x30000 ，此时再用将指数项隐含在系数中的方式，用系数顺序表来表示S（x），则其表长为300

27、01，而表中只有3个非零元素，浪费了大量的存储空间。因此，一般情况下的一元n次多项式 Pn(x) = P1xe1 + P2xe2 + + Pixei+ + Pmxem ， 其中Pi为系数项，为ei指数项这时可用一个线性表R=(P1 ,e1), (P2 ,e2), ， (Pm ,em) )来表示。其中元素数据类型和顺序表的C语言描述为：typedef struct poly float coef ; int exp ; elemtype ;typedef struct polynty elemtype dataMaxnum; int num; polynty;12mMaxnum 以上，用顺序表的

28、形式表示了一元多项式，这种方式表示的一元多项式适用于其运算仅用于求值等不用修改多项式系数或指数项（即不进行插入、删除等改变元素间的逻辑关系的操作）时。而一元多项式的加法运算的实现，须涉及到插入、删除等改变元素逻辑关系的操作，则应采用单链表来表示一元多项式。一元多项式单链表表示结点的C语言描述为：typedef struct node float coef; int exp ; struct node *next ; node ;数据域 指针域 一元多项式相加的实现方法： 指数相同的项系数相加，若其和不为零则构成“和 多项式”中的一项。 所有指数不同的项均插入到“和多项式中”。例已知：A4(X)

29、=7+3X+9X8+5X17 B3(X)=8X+22X7- 9X8 求：C(X) = A4(X) + B3(X) P qP方法和步骤：在其中一个链表的基础上构造“和多项式”将p,q指针分别指向A，B链表的第一个结点。依次比较p,q指针所指向结点的数据域中的指数项。P q qif (p exp q exp ) q结点为和多项式的结点，将其插入到p结点之前； q指针后移； 一直比较到两表中有一张表已到结束结点为止： if( A表到头： pnext=NULL) 将B表中剩余的结点插入到A表之后； 释放B 表的头结点。C语言实现：1.2.1 思考题及作业1、线性数据结构按其存储方式的不同可分 为哪几种

30、线性表？各有哪些区别？2、请画出顺序表插入和删除程序的流程图。4、链表由可分为单链表、双链表、循环链 表等，有哪些区别？各适用于什么地方？3、请画出单链表插入和删除程序的流程图。5、请画出一元多项式相加程序的流程图。 写出源程序。1.2.2栈和队列栈和队列是常用的数据结构它和线性表的关系在于：逻辑结构和存储结构与线性表相同。一、栈(stack)1、栈的基本概念定义：是限定在表尾进行插入和删除的线性表。表尾的一端称为栈顶，表头的一端称为栈底。栈底栈顶pushpop设栈 S=（ a1,a2,a3,ai, an），则a1为栈底元素， an为栈顶元素，栈的修改是按后进先出的原则进行的，因此栈又称为后进

31、先出的线性表（LIFO）。操作集合是线性表的操作集合的子集，即是操作受限。2、栈的ADT定义ADT stack 数据元素： ai具有相同的数据类型， ai S 1 i n 。 逻辑结构： a1为栈底元素； an栈顶元素；中间任何一个元素 都存在一种关系： ( i=1,2, ,n-1 )。 操作集合：SETNULL（S）：初始化栈，把栈设为空栈。 EMPTY（S）；判断是否为空栈。 if (S为空）return (true); else return (false); PUSH（S，x )：进栈操作，即在栈顶插入元素x。 POP（S）：出栈操作，若栈不为空删除栈顶元素。 TOP（S）：访问栈顶元

32、素an ，不改变栈的内容。 stack ；注意：这些操作都限制在表尾（栈顶）的一端进行。判空3、栈的存储结构：栈是操作受限的线性表，顺序栈和链栈 顺序栈：利用一组地址连续的存储单元依次存放从栈底 到栈顶的元素。 typedef struct elmtype dataMaxnum; int top; stacktype; top=0 Atop=-1 栈空top=4 E D C B A top=2 C B A注意：在顺序栈结构的C语言描述中，Maxnum表示顺序栈的最大长度，top 和顺序表中num的含义不一致：num为表中实际元素的个数；top为栈中栈顶元素的数组下标值。假定定义一个数组data

33、5 来表示一个顺序栈。43210顺序栈的C语言描述：top=0 插入A元素top=4 栈满指向指针的指针：int *ppi;ppi是一个特殊的指针变量，它存放着另外一个指针的地址int i,*pi, *ppi; pi=&i; ppi=*pi=i *ppi=pi *ppi=*pi=i 算法一、初始化栈使栈顶指针为一个无效值。C 语言中将此值定义为-1。算法二、进栈操作 设栈 S=（a1,a2,a3,ai,an）， PUSH（S，x）的含义是：通过操作使栈 S=（a1,a2,a3 ,ai,an，x），但是插入之前要检测是否栈满。步骤：若栈满的话，返回“false”，程序结束。栈顶指示器的值加1。（

34、top+ +）将x放入栈顶指示器指示的存储单元。返回“true”，程序结束。算法三、出栈操作 设栈 S=（a1,a2,a3,ai,an-1,an），POP（S）的含义是：通过操作使栈 S=（a1,a2,a3,ai,an-1），但是删除之前要检测是否栈空。步骤：若栈空的话，返回“NIL”，程序结束。栈顶指示器的值减1。（top- -）返回删除的栈顶元素。顺序栈操作的特点：同顺序表的操作相比较简单的多，即操作受限。“上溢”的问题同样不能圆满解决，而当一个程序中使用多个栈时，常常会发生一个栈满，而另外的栈非满甚至为空的情况，使得资源的利用率很低。链栈：是采用一组地址不连续的存储单元来存放栈中各元 素

35、，栈中各元素的逻辑关系用指针来表示。结构示意图：注意： 在单链表中表中第一个结点为a1结点，而在链栈中 第一个结点是an结点。 链栈中没有头结点。 链栈和单链表一样也用头指针(top)来唯一的标识。链栈结点结构的C语言描述：typedef struct node elemtype data; struct node *next; node;算法一、进栈操作toptop步骤： 申请P结点： P data = x; P结点和栈顶结点(an结点)相连： Pnext= top; 重置栈顶指针： top = P;C语言实现：算法二、出栈操作top free(p) P步骤： 让P指针指向栈顶结点： P =

36、 top 修改栈顶指针： top = top next 释放原栈顶结点（ an结点）： free( P ) 链栈的引入解决了栈的上溢问题，由于链栈的结点是动态产生的，因此只有在整个内存空间都被占满，malloc过程无法实现时才会出现上溢的情况，从而实现了多个栈的空间共享。C语言实现： top设依次进入一个栈的元素序列为a,b,c,d,e,不可得到出栈的元素序列有_。( )(A) a,d,c,b,e(B) b,a,d,c,e(C) d,c,e,b,a(D) c,a,b,d,e二、队列(queue)1、队列的基本概念定义：是限定在表尾进行插入，在表头进行删除的线性表。表尾的一端称为队尾，表头的一端

37、称为队头。12n出队列端入队列端（队尾）（队头） 队列和我们日常生活中的排队一样，最早进入队列的元素最先离开，因此称队列为先进先出(FIFO)的线性表。2、队列的ADT定义ADT queue 数据元素： ai具有相同的数据类型，1 i n 。 逻辑结构： a1为队头元素； an队尾元素；中间任何一个元素 都存在一种关系： ( i=1,2,n-1 )。操作集合：SETNULL（Q）：初始化队列。 EMPTY（Q）；判断是否为空队列。 if (Q为空）ruturn (true); else return (false); ENTER（Q，x )：入队列，即在队尾插入元素x。 DELETE（Q）：出

38、队列，即删除队头元素。 GETHEAD（Q）：访问队头元素an 。 queue ；3、队列的存储结构： 顺序队列：利用一组地址连续的存储单元依次存放从队 尾到队头的元素。通常以一个队头指示器 front 和一个队尾指示器 rear 来描述队列。顺序队列结构的C语言描述：判空判空判满？typedef struct elmtype dataMaxnum+1; int front, rear ; queuetype;543210front rear 假定以数组data6来定义一个队列。如右图所示： rear=front=0 ：队空 rear=3; front =0 rear=5=Maxnum; fr

39、ont = 0 ; 队满rear a3 a2 a1front rear a5 a4 a3 a2 a1front 算法一、入队列操作（插入算法） 设栈 Q =（ a1,a2,a3,ai,an）， ENTER（Q，x）的含义为：若Q满则入队列操作无效，否则Q=（a1,a2,a3,ai, an , x）。data0空int enter(queuetype *q,elemtype x) Maxnum n+1 n 2 1 0 an a2 a1 x front=0rear=nrear=n+1实现： 如果队满（rear=Maxnum）则插入无效，返回插入出错的的信息。 否则，队尾指示器加1，并将 x 插入到

40、新的队尾位置。返回插入成功的信息。算法二、出队列操作（删除算法） 设栈 Q=（a1,a2,a3,ai,an），DELETE（Q）的含义为：若Q空则出队列操作无效，否则Q=（a2,a3,ai,an）。 Maxnum n+1 n 2 1 0 an a2 a1front= 0front= 1rear= nelemtype delete(queuetype *q ) 实现： 如果队空则删除无效，返回空元素。 否则，队头指示器加1，并返回删除的元素。Rear a5 a4 a3 a2 a1front rear front顺序队列的假溢出现象： rear=5=Maxnum; front=0 ;队满删除队列中

41、的五个元素，即： rear=5; front=5 ;此时，队列为空，还是为满？为解决顺序队列的假溢出现象，可采用循环队列。rear a7 a6 a5 a4 a3 a2 a1front 76543210循环队列： 在循环队列的结构中，将data0看作是datamaxnum-1的下一个相邻的位置。循环队列的C语言描述：typedef struct elmtype datamaxnum; int front, rear ; queuetype;指示器的移动：一般队列和循环队列的区别：一般队列循环队列front + + ( front + + ) % Maxnumrear + + ( rear + +

42、 ) % Maxnumrear a7 front rear front rear a1front rear front front rear a8rear front 不同操作中的空条件 front = rear front = rear 初始化空 front=rear= 0 front=rear=0 操作中的满条件 rear =Maxnum front=(rear+1)% Maxnum 有关循环队列的操作和一般队列一致，仅仅是判空和判满的条件发生了变化。 链队列：是采用一组地址不连续的存储单元来存放队列中 各元素，队列中各元素的逻辑关系用指针来表示。 设队列 q =（a1,a2,a3 ,ai

43、,an），其结构示意图为：空队列的结构示意图：链队列结点结构的C语言描述：typedef struct node elemtype data; struct node *next; node;typedef struct qtype node *front ; node *rear ; qtype;算法一、入链队列操作（插入算法） 入链队列的操作和链表的操作相似，仅仅是插入操作被限定在队尾进行而已。其含义和入顺序队列一致。p rearrear步骤： 申请待插入的 x 结点，以p指针指向该结点，赋值。 进行 an 结点和 x 结点的连接。 链队列的尾指针指向 x 结点。能否交换？算法二、出链队列

44、操作（删除算法） 出链队列的操作和链表的操作相似，仅仅是删除操作被限定在队头进行而已。其含义和出顺序队列的含义一致。 pfree(p)步骤： 以p指针指向链队列的第一个结点: p=front-next; 进行头结点和a2 结点的连接: front-next=p-next; 释放被删除的a1 结点: free(p);注意：若队列中仅有一个元素，删除后则为空队列。因此删除后还要修改尾指针，使其也指向头结点，表示队列已空。1.2.2 思考题及作业1、栈和队列各有哪些基本特征？2、设一个栈的输入序列是1,2,3,4,写出该 栈的所有可能的输出序列。3、进一步理解循环队列的判空和判满的条件。1.2.3

45、数组一、二维数组的ADT定义：ADT Array 数据元素：D=aij|aijelemtype 1in & 1jm 逻辑关系：R=|(1in-1 & 1jm)& |(1in & 1jm-1) 操作集合：Value(A,i,j)：给定数组元素的下标，求数 组元素的值。 Assign(A,x,i,j)：修改指定下标的元素的值。 ADT Array；二、二维数组中元素的逻辑关系：已知一个二维数组Anm行下标列下标A= 由于，二维数组中任意一个元素aij，都有两个直接前驱和两个直接后继，因此它不是一般意义上的线性表。但它的每一行和每一列都是一个线性表。a1 1 , a1 2 , ,a1 j-1, a1

46、 j, a1 j+1, , a1 ma2 1 , a2 2 , ,a2 j-1, a2 j, a2 j+1, , a2 m ai-1 1 , ai-1 2,ai-1 j-1, ai-1 j, ai-1 j+1, ai-1 mai 1 , ai 2 ,ai j-1, ai j, ai j+1, , ai mai+1 1 , ai+1 2,ai+1 j-1, ai+1 j, ai+1 j+1, ai+1 m an 1 , an 2, , an j-1, an j, an j+1, , an m我们若以行向量或列向量来表示二维数组的话，则有： A= (1,2, ,i, ,p ) 其中 p = m 或

47、 n当i是一个列向量时：i=(a1i,a2i, ,an,i) 0im 当i是一个行向量时：i=(ai1,ai2, ,ai m) 0in 若以行向量或列向量来作为二维数组的元素的话，则可将二维数组视为一个线性表，前者称为列主序的线性表，后者称为行主序的线性表。三、二维数组的存储结构 数组的存储结构一般采用顺序存储结构，这是由于存储单元是一维的，因此在处理二维甚至多维数组的存放时有一个次序的问题。对二维数组而言，可以按行优先方式存储，也可按列优先方式存放。在C语言中二维数组采用行优先方式存放，即按以下次序存放：a11,a12,a1.m,a21,a22,a2.m ,an,1,an,2,an,m 由此

48、不难看出，数组中每个元素的存储地址可以有下式方便地求出：Loc( aij ) = Loc( a11 )+(i-1) * m+(j-1) * s 其中： s 为每个元素所占用的存储单元的 byte 数 同理，也有列优先的存储方式，但无论哪种存储方式，只要给定下标，便可很方便地存取该元素，以上表达式可推广到多维数组。四、矩阵的压缩存储 一般而言矩阵的存储采用和二维数组类似的存储结构，但对于一些结构特殊的矩阵如：对称矩阵、稀疏矩阵等，套用一般数组的存储结构则会带来存储空间的浪费。压缩存储的含义是：值相同的元素仅分配一个存储单元，而零元素不分配存储单元等等一些特殊的存储方式。A=从a1 1到ai j一

49、共（i-1）m+j个数据元素，另外由于从a1 1作为起始位算起，所以公式为Loc( aij ) = Loc( a11 )+(i-1) * m+(j-1) * s相似的，对于列优先的每个元素的存储地址为Loc( aij ) = Loc( a11 )+(j-1) * n+(i-1) * sa1 1 , a1 2 , ,a1 j-1, a1 j, a1 j+1, , a1 ma2 1 , a2 2 , ,a2 j-1, a2 j, a2 j+1, , a2 m ai-1 1 , ai-1 2,ai-1 j-1, ai-1 j, ai-1 j+1, ai-1 mai 1 , ai 2 ,ai j-1,

50、 ai j, ai j+1, , ai mai+1 1 , ai+1 2,ai+1 j-1, ai+1 j, ai+1 j+1, ai+1 m an 1 , an 2, , an j-1, an j, an j+1, , an m(i-1)mj1、特殊矩阵的压缩存储 特殊矩阵是指元素在矩阵中的位置分布存在一定的规律的矩阵如：对称矩阵、三角阵等。例：若一个n 阶矩阵A的元素满足以下条件： aij= aji 1i,jn 则称A为n阶对称矩阵。A=a11,a21,a31,an1a21,a22,a32,an2 a31,a32,a33,an3 an1,an2,an3,ann不失一般性我们以行主序方式来存

51、储其下三角中的元素，这样表长为1/2(n+1)*n)，节省了近一半的存储空间。表长1/2(n+1)*n)可由等差数列公式计算而来。数组元素存储次序为 对称矩阵中任意一个元素在顺序表中的位置（地址），可用下式来得到：a11,a21,a22,ai-1.i-1,ai1,ai2,aij, annLoc(aij)=Loc(a11)+(i-1) * i/2+(j-1) * s(i-1) * i/2ji j=Loc(a11)+(j-1) * j/2+(i-1) * si jaij在上三角矩阵中，而aij=aji ，即Loc(aij)=Loc(aji)2、稀疏矩阵的压缩存储稀疏矩阵是指一个矩阵中非零元素很少且

52、其分布无规律。 这里介绍一种常用的三元组的存储方法，只是存储稀疏矩阵中的非零元素。所谓三元组是一个（x+1）行、3列的矩阵，而三元是指非零元素所在的行和列的值和非零元素本身的值。例、已知一个稀疏矩阵A，求其对应的三元组表示。A56 =1 0 0 0 7 00 0 12 0 0 03 0 0 0 0 00 0 0 0 0 0 0 -3 0 0 0 0 T63 =5 6 51 1 11 5 72 3 123 1 35 2 -3 行的值列的值非零元素的值注意：T矩阵的第一行表示原矩阵的行、列数和非零元素的个数。加了这一行的描述之后，便可使A、T矩阵之间一一对应。 稀疏矩阵的三元组压缩存储是一种基础的

53、数据压缩的方法，而在此基础上发展起来的更先进的压缩方法（JPEG、MPEG）被广泛地应用于图象处理和数据传输中。如雷达图像的压缩传输。640480压缩传送300KB几KB300KB压缩解压缩无损压缩1.2.3 思考题及作业1、数组和线性表的关系，三维数组又如何 用数据结构的方法用线性表来表示呢？2、矩阵压缩存储的基本目的和方法是什么？3、稀疏矩阵的用三元组压缩方法压缩时 可以不给出原矩阵的行、列和非零元 素的个数吗？1.3 非线性结构1.3.1 树结构数据元素：具有相同的数据类型的元素所组成的有限集合。逻辑结构：任何一个元素均可能有多个直接前驱和直接后继。 一、基本概念： 1、定义：树是由n个

54、（n0）具有相同类型的结点元素组成 的有限集合，且满足以下的条件： 其中有一个结点无直接前驱，称为根（Root）； 其余的结点元素可分为m个互不相交的子集： T1,T2 Tm，这m个子集本身又构成树，称为 Root 的子树。主要的非线性结构：树结构和图结构和线性结构一致ABCDEFGHIJ右图所示为一棵树，其中A为根，它有三棵子树：T1=B,E,F; T2=C,G,H,I,J; T3=D 在子树T2中，C是该子树的根，它有三棵子树：T21=G；T22=H；T23=I，J；T22和T21仅有一个根结点，没有子树。注意： 树的定义中n0，即没有空树的概念； 树的定义中采用了递归定义的方法，显示了树

55、 结构本身的这种递归的性质。在客观世界中，树结构广泛存在，如家谱、行政组织机构和计算机磁盘文件管理等。2、有关基本概念：结点的度：该结点所拥有的子树的数目。叶子结点：度为0的结点。分支结点：度不为0的结点。树的度：树中各结点的度的最大值子结点：某结点的子树的根， 称为他的子结点。父结点：该结点称为其子树根的父结点。兄弟结点：具有同一父结点的子结点称为兄弟结点。结点的层次：根结点的层次为1，其他结点的层次等于其父 结点的层次加1。树的深度：树中结点的最大层次。森林： 是m(m0)棵树的集合。 ABCDEFGHIJ二、二叉树1、定义：二叉树是由n个（n 0）具有相同类型的结点元素 组成的有限集合，

56、且 满足以下的条件： 由一个根结点和它的两棵左右子树组成； 其左 右子树 分别又构成一棵二叉树。注意： 二叉树的定义中n0，即表示有空二叉树的概念，而树至少有一个根结点； 二叉树的定义中也采用了递归定义的方法，显示了二叉树结构本身的这种递归的性质，树的定义也采用了递归定义。 二叉树的子树有左右之分，次序不能颠倒，即使只有一个子 树也必须分左右，树中无此区分。 对于每一个结点至多有2个子树。树中对子树的数目没有限制，但必须是有限个。由定义知二叉树有五种基本形态，如下图所示：2、二叉树的基本性质 在二叉树的第 i 层上至多有2 i -1个结点（ i 1 ）。 深度为K的二叉树至多有2 k -1个结

57、点（ k 1）。由性质 可知深度为k的二叉树的最大结点个数为：由以上性质可以引入以下概念：满二叉树：一棵深度为k且有 2 k -1 结点的二叉树称为满二叉树。特点： 满二叉树中所有分支 结点均存在左右子树； 所有叶子结点均在同 一层次上。ABCFGHEDIJKLMNO约定编号顺序：从上到下，从左到右。12345678 9 10 11 12 13 14 15特点： 只有最下面两层的结点的度可以小于2。 最下层上的节点都集中在该层最左边的若干位置。 完全二叉树：一棵深度为k且有n个 结点的二叉树，当且仅当其 每一个结点的编号都与深度为k的满二叉树中编号 为1n的结点的编号完全一致时该二叉树称为完全

58、 二叉树。ABCFGHEDIJKLL12345678 9 10 11 12 13 14 151234567 8 9 10 111213 6 7 8 912M在完全二叉树中：设树有n个结点，对任意序号为i的结点有： 若i1，则i结点的父结点的序号为 int(i/2)。 i=1时 该结点为根结点，无父结点。若 2in 则 i 结点的左子结点的序号为 2i，否则该结 点无左子结点。 若 (2i+1) n 则 i 结点的右子结点的序号为 2i+1， 否则该结点无右子结点。 int(i/2)ii+1 2 i2i+12(i+1)2(i+1)+112345678 9 10 11 12 13 14 152、二

59、叉树的存储结构 二叉树的顺序存储结构：对于下图中所示的完全二叉树，可以用内存空间中一组地址连续的存储单元来存放，并以一个一维数组（BT 12 ）来表示。ABCDEFGHIJKL12345678910111201234567891011数组下标序号可见，在完全二叉树的顺序存储结构中各结点间的的逻辑关系可以由其存储单元的物理地址来反映。ABCFGHEDIJKL1234567 8 9 10 1112 对于一般的二叉树，也可以按照完全二叉树的顺序结构来存储，仅需要添加一些空结点，使它变成为一棵完全二叉树。ABCDEF000001234567891011012345678910ABC0D0000EF这样

60、做可能会带来存储空间的浪费，最坏的情况，一个深度为K，且只有K个结点的单支树，却至少需要2 k -1个存储单元。若 K= 4， 2 k -1 =8 ；K=11， 2 k -1 =1024 。123K1234567891011二叉树的链式存储结构：由二叉树的特性知链式存储结构中的每一个结点可如下图所示：指向左子结点的指针域数据域指向左子结点的指针域 A B C E F DhABCDEF3、二叉树的遍历： 二叉树的遍历是指用一定的规律，按某条搜索路径访问树中的每一个结点，使树中的每个结点都被访问且只被访问一次。根结点 D左子树 L右子树 R如右图所示，任何一棵二叉树都由D、L、R三部分组成，若限定