计算机软件技术基础课件(第三版)

1、1,第二章 数据结构,2.1 基本概念 2.2 线性表 2.3 栈、队列和数组 2.4 树和二叉树 2.5 排序和查找,2,上节课（线性表）要点回顾,线性结构(表、栈、队、数组）的定义和特点： 仅一个首、尾结点，其余元素仅一个直接前驱和一个直接后继。,2. 线性表,逻辑结构：“一对一” 或 “1:1” 存储结构：顺序、链式 运 算 ：修改、插入、删除查找排序后述,3.顺序存储,特征：逻辑上相邻，物理上也相邻； 优点：随机查找修改快 O(1) 缺点：插入、删除慢 O(n),改进方案：链表存储结构,3,链表存储结构特点：,链表的表示(介绍了若干术语和结构数据类型） 链表的实现（创建、输出、修改、插

2、入、删除）,例：建立26字母单链表的生成和输出, p=head; while (p-next!=NULL) printf(%c,p-data); p=p-next; printf(“%cn”,p-data); , int i; head=(Node*)malloc(m); p=head; for( i=1; idata=i+a-1; p-next=(Node*)malloc(m); p=p-next； p-data=i+a-1; p-next=NULL ;,逻辑上相邻的元素，物理上未必相邻。,输出链表,创建链表,4,一、栈（Stack）,2.3 栈、队列和数组,二、队列（Queue）,1. 定

3、义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式,1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式,三、数组（Arrays）,1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式,5,1. 定义,一、 栈,与线性表相同，仍为一对一( 1:1)关系。,用顺序栈或链栈存储均可，但以顺序栈更常见,只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。,关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的存储结构有别而不同。,限定只能在表的一端进行插入和删除运算的线性表。,即表尾(或称栈顶),基本操作有：建栈、

4、判断栈满或栈空、入栈、出栈、读栈顶元素值等。,6,栈 是仅在表尾进行插入、删除操作的线性表。 表尾(即 an 端)称为栈顶 /top ; 表头(即 a1 端)称为栈底/base,例如： 栈 S= (a1 , a2 , a3 , .,an-1 , an ),插入元素到栈顶的操作，称为入栈 从栈顶删除最后一个元素的操作，称为出栈,an称为栈顶元素,a1称为栈底元素,想一想：要从栈中取出a1，应当如何操作？,强调：插入和删除都只能在表的一端（栈顶）进行！,7,一般用 s 代表栈. 栈的体积m表示它能容纳m个元素(S1:m). top 代表栈顶指针，直接指向栈顶元素. 当 top=m时，栈满。栈满后再

5、进行进栈运算，则发生上溢。 当top=0时，栈空。栈空后再进行退栈运算，则发生下溢。,顺序栈,8,4. 顺序栈的类型定义 #define N 100 struct stack datatype dataN; int top; s;,9,讨论1：堆栈是什么？它与一般线性表有什么不同？,答：堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。 与一般线性表的区别：仅在于运算规则不同。,一般线性表 堆栈 逻辑结构：1:1 逻辑结构： 1:1 存储结构：顺序表、链表 存储结构：顺序栈、链栈 运算规则：随机存取 运算规则：后进先出(LIFO),“进”插入=入栈=PUSH（an+1),“

6、出”删除=出栈=POP(an),10,顺序表和顺序栈的操作区别:,写入：Si= ai 读出： e= Si,入栈(PUSH): S+top=an+1,an+1,以线性表 S= (a1 , a2 , . , an-1 , an )为例：,栈底base,前提：预设栈顶指示变量top,出栈( POP) : e=Stop- -,11,顺序栈的入栈操作例如用堆栈存放（A，B，C，D）,A,A,C B A,B A,B,C,D,核心语句： top=0;,Push (A);,Push (B);,Push (C);,Push (D);,顺序栈入栈函数PUSH（） status Push(ElemType e) i

7、f(top= =m)上溢 else s+top=e; ,12,顺序栈出栈操作例如从栈中取出B,D C B A,D C B A,核心语句： Pop ( );,Pop ( );,printf( Pop () );,顺序栈出栈函数POP() status Pop( ) if(top=0) 下溢 else e=stop -; return(e); ,顺序栈的实现（演示1）,13,补充3： 上溢：对一个满栈作入栈操作 下溢：对一个空栈作出栈操作,若入栈动作使地址向高端增长，称为“向上生成”的栈； 若入栈动作使地址向低端增长，称为“向下生成”的栈；,补充1：,补充2： 判断： 栈 为 空 的 条件 ： t

8、op =0; 栈 满 的 条 件 ： top=stacksize;,14,例1：一个栈的输入序列为1, 2, 3，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？,答：,可以通过穷举所有可能性来求解： 1入1出， 2入2出，3入3出， 即123； 1入1出， 2、3入，3、2出， 即132； 1、2入，2出， 3入3出， 即231； 1、2入，2、1出，3入3出， 即213； 1、2、3入，3、2、1出， 即321； 合计有5种可能性。,15,例2：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？,43512不可能实现，主要

9、是其中的12顺序不能实现； 12345的输出可以实现，每压入一数便立即弹出即可。,答：,例3：设依次进入一个栈的元素序列为c，a，b，d，则可能得到出栈的元素序列是： ）a，b，c，d ）c，d，a，b ）b，c，d，a ）a，c，d，b,16,链栈的入栈操作和出栈操作,链栈的构造方式以头指针为栈顶，在头指针处插入或删除,Node *st=Null, *p; int m=sizeof(Node);,栈顶top,栈底 base,栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈,链栈中每个结点由两个域构成： data域和next域，其定义为：,typedef struct node Data

10、Type data; struct node * next; Node;,17,Push (ElemType e) p=(Node*)malloc(m); p-data=e; p-next=st; st=p; ,Status Pop( ) if(st=NULL)下溢 elsee=st-data;p=st;st=st-next; free(p); return(e); ,链栈 入栈函数,链栈 出栈函数,插入表头,从表头删除,由此可以看出：一个链栈由其栈顶指针唯一指定 设st指向栈顶元素，则 st = NULL 表示栈空,18,链栈不必设头结点，因为栈顶（表尾）操作频繁； 链栈一般不会出现栈满情况

11、，除非没有空间导致malloc分配失败。 链栈的入栈、出栈操作就是栈顶的插入与删除操作，修改栈顶指针即可完成。,几点说明:,链栈的实现（演示2）,19,讨论2：为什么要设计堆栈,它有什么独特用途？,调用函数或子程序； 递归运算的有力工具； 表达式求值； 用于保护现场和恢复现场。,举例：,答：,举例：,递归（实例1） 表达式求值（举例2）,20,举例：表达式计算需要栈,例: 已知 x=9+4*6/8-5 试写出表达式求值时栈的变化过程。,解：表达式 9 + 4 * 6 / 8 - 5 ；,1.从左向右逐个扫描表达式的各个成分;2.建立两个栈s1和s2，遇运算对象进s1栈，遇运算符作如下判断：(在

12、求值的 过程中要考虑运算符的优先级）. 若运算符优先级大于s2栈顶元素优先级，则进s2栈； 若运算符优先级小于/等于s2栈顶元素优先级，则不进s2栈，而进行运算.,第一步：,9,4,6,s1,+,*,s2,运算 4*6=24,计算过程为：,21,9,24,8,s1,+,/,s2,第二步：,运算 24/8=3,9,3,s1,+,s2,第三步：,运算 9+3=12,12,5,s1,-,s2,第四步：,运算 12-5=7,7,s1,；,s2,第五步：,计算结束：表达式结果入s1栈，故x=7.,22,定 义,二、 队列,与线性表相同，仍为一对一关系。,顺序队或链队，以循环顺序队更常见。,只能在队首和队

13、尾运算，且访问结点时依照先进先出（FIFO）的原则。,关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。,只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。,基本操作：入队或出队，建空队列，判断队空或队满等操作。,尾部插入,首部删除,23,队列 （Queue）是仅在表尾进行插入操作，在表头进行删除 操作的线性表。它是一种先进先出（FIFO）的线性表。,例如：队列 Q= (a1 , a2 , a3 , .,an-1 , an ),在队尾插入元素称为入队；在队首删除元素称为出队。,队首,队尾,问：为什么要设计队列？它有什么独特用途？,操作系统中的作业调度（一个CPU执行多个

14、作业）； 离散事件的模拟（模拟事件发生的先后顺序）； 3. 简化程序设计。,答：,24,先简介链队列,讨论： 空链队的特征？, 怎样实现链队的入队和出队操作？, 链队会满吗？,front=Null,一般不会，因为删除时有free动作。除非内存不足！,入队（尾部插入）：rear-next=S; rear=S; 出队（头部删除）：p = front;front=front-next; free(p);,链队列的实现（演示3）,25,思考：,题：某线性表最常用的运算是插入和删除，插入运算是指在表尾插入一个新元素，删除运算是指删除第一个元素，那么采用存储方式最节省运算时间。,（）仅有尾指针的单向循环链

15、表 （）单向链表 （）仅有头指针的单向循环链表 （）双向链表,26,再介绍顺序队,(队尾),(队首), 队列会满吗？ 极易装满！因为数组通常有长度限制，而其前端空间无法释放。, 空队列的特征？ 约定：front=rear,队尾后一地址,入队(尾部插入)：rear+;Qrear=e; 出队(头部删除)：front+; e=Qfront;,讨论：,假溢出,有缺陷, 怎样实现入队和出队操作？核心语句如下；,e,27,问：什么叫“假溢出” ？如何解决？,答：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。,解决假溢出的途径,采用循环队列,28,1,顺

16、序队列,新问题：在循环队列中，空队特征是front=rear；队满时也会有 front=rear；判决条件将出现二义性！ 解决方案： 人为浪费一个单元，则队满特征可改为front=(rear+1)%N； 即front和rear之一指向空闲元素，另一指向实元素。,29,队空条件 : front = rear (初始化时：front = rear ) 队满条件： front = (rear+1) % N (N=maxsize) 队列长度（即数据元素个数）：L=（Nrearfront）% N,问3： 在具有n个单元的循环队列中，队满时共有多少个元素？,n-1个,6,问1：左图中队列maxsize N

17、=？,问2：左图中队列长度L=？,5,30,例1 ：数组n用来表示一个循环队列，f 为当前队列头元素的前一位置，r 为队尾元素的位置。假定队列中元素的个数小于n，计算队列中元素个数的公式为:,（） rf （）（nfr）% n （）nrf （） （nrf）% n,要分析4种公式哪种最合理？ 当 r f 时（A）合理； 当 r f 时（C）合理；,答：,综合2种情况，以（D）的表达最为合理,例2：在一个循环队列中，若约定队首指针指向队首元素的前一个位置。那么，从循环队列中删除一个元素时，其操作是 先,移动队首指针,取出元素,，后,。,31,几点说明：,1)循环队列的出、入队运算和顺序队列的运算完全

18、一样，只不过是队满的判断条件为：front=(rear+1)%m,头、尾指针加1的运算要加上“%”运算； 2)“%”运算主要用在边界上(由m-1加1变成0时用)； 3)循环队列也是顺序队列，用于解决顺序队列的假溢出； 4)循环队列满时，元素个数为m-1; 5)若已知循环队列的长度m,头指针front和尾指针rear,则循环队列中元素的个数为:(rear-front+m)%m.,32,对这4个数据元素进行的队操作是进队2次，出队1次，再进队2次，出队1次；这时，第1次出队得到的元素是 ？ ，第2次出队得到的元素是 ？ 。经操作后，最后在队中的元素还有 ？ 个，队尾指针指向 ？ 。,例：对4个数据

19、元素进行队操作。在进队操作时，按a1、a2、a3、a4次序每次进入一个元素（假设队的初态为空）。, 进队2次, 出队1次, 再进队2次, 出队1次,a1、a2 f=r=0 ; r+ ; r+ (f=0, r=2),a3、a4 r+ ; r+ (f=1, r=0),v0,a1 f+; (f=1, r=2),a2 f+ (f=2, r=0),a1,a2,2,解：此题用V4大小数组即可（V0V3 4个单元有效） 。,33, 数据元素并非原子类型，可以再分解; 所有数据元素仍属同一数据类型。,1 数组的定义 2 数组的顺序表示和实现 3 矩阵的压缩存储,数组的特点：一种特殊的线性表,三、数组,34,1

20、 数组的定义,数组： 由一组名字相同、下标不同的变量构成,注意： 一个二维数组Amn 含有mn个元素，每个元素都受行和列两个关系的约束，即二维数组中的每一行是一个线性表，同一行中元素间的关系满足线性表的关系，同样，每一列也是一个线性表，列内元素也满足线性表的关系。因此，若把每一行看作一个数据元素，则数组可看成长度为m的线性表。,答：对的。因为： 数组中各元素具有统一的类型； 数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。 数组的基本操作比较简单，通常是在给定一组下标的情况下存取或修改相应的数组元素，一般不对数组作插入或删除运算。,讨论：“数组的处理比其它复

21、杂的结构要简单”，对吗？,35,二维数组的特点：,一维数组的特点：,1个下标，ai 是ai+1的直接前驱,2个下标，每个元素ai,j受到两个关系（行关系和列关系）的约束：,一个mn的二维数组可以看成是m行的一维数组，或者n列的一维数组。,N维数组的特点：,n个下标，每个元素受到n个关系约束,一个n维数组可以看成是由若干个n1维数组组成的线性表。,36,2 数组的顺序存储表示和实现,问题：计算机的存储结构是一维结构，而数组一般是多维结构，怎样存放？ 解决办法：存放次序的约定 事先约定按某种次序将数组元素排列成一序列，然后将这个线性序列存入存储器中。 例如：在二维数组中，既可以规定按行存储(按行优

22、先次序存放)，也可以规定按列存储(按列优先次序存放)。,注意： 若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式； 约定的次序不同，则计算元素地址的公式也有所不同； C和BASIC中一般采用行优先顺序；FORTRAN采用列优先。,37,补充：计算二维数组元素地址的通式设一般的二维数组是Ac1.d1, c2.d2，这里c1,c2不一定是0。,无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址（这样数组中的任一元素便可以随机存取）,二维数组列优先存储的通式为： LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1*L,

23、单个元素长度,aij之前的行数,数组基址,总列数，即第2维长度,aij本行前面的元素个数,开始结点的存放地址（即基地址） 维数和每维的上、下界； 每个数组元素所占用的单元数,则行优先存储时的地址公式为：LOC(aij)=LOC(ac1，c2)+(i-c1)*(d2-c2+1)+j-c2)*L,38,难点是：多维数组与一维数组的地址映射关系,例1：已知二维数组Am,m按行存储的元素地址公式是： Loc(aij)= Loc(a11)+(i-1)*m+(j-1)*K , 请问按列存储的公式相同吗？,答：尽管是方阵，但公式仍不同，要作修改： Loc(aij)=Loc(a11)+(j-1)*m+(i-1

24、)*K,例2：设数组a160, 170的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a32,58的首字节存储地址为 。,根据列优先公式 Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K 得：LOC(a32,58)=2048+(58-1)*60+(32-1)*28950,答：请注意审题！,想一想：若数组是a059, 069，结果是否仍为8950？,8950,39,例3 已知二维数组A910,试问：元素A85按行存储时的地址与哪个元素按列存储时的地址相同。 解：设所求的元素为Aij, 每个元素占d个字节，则 1）按行存放时：Loc（A8，5）= Loc

25、（A0，0）+（8*10+5）*d 2）按列存放时： Loc（Ai，j ） = Loc（A0，0）+（j*9+i） *d 两式相等，得8*10+5 = j*9+i,即 i+9j=85. j= (0i 8, 0j 9) 可得：i=4，j=9. 因此，元素A85按行存放的起始地址和A49按列存放的起始地址相同。,总结：求元素 Ai，j 的地址的一般形式为： 数组首地址 +( Ai，j元素前已存入元素的个数 各元素的字节数 ),40,例4：假设有三维数组A798，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，末尾元素A687的第一个字节地址为多少？若按高地址优先存储时，元素A476的第一个字节地址为多少？, 末元素A687的首字节地址 1000 +(798)66 = 4018 按高地址优先存储时，元素A476的第1个字节地址=? 提示：将第3维看作“页码”，前面两维就是每页上的二维数组。 A476=1000+(7 9 6) 6+(7 7+4 ) 6=,3586,只要计算出任一数组元素的地址，就能对其轻