软件复习指导第2章基本数据结构2.2new

1、软件技术基础授课教师 刘艳民 22第二章 基本数据结构及其运算2.1 数据结构的基本概念2.2 线性表及其顺序存储结构2.3 线性链表及其运算2.4 树与二叉树2.1.1 什么是数据结构 2.1.2 学习数据结构的意义 2.1.3 数据结构主要涵盖内容基本概念和术语数据的逻辑结构数据的物理结构数据的运算 上次课主要内容2.1 数据结构的基本概念本次课主要内容2.2 线性表及其顺序存储结构2.2.1 线性表及其运算2.2.2 栈及其应用2.2.3 队列及其应用1.什么是线性表(Linear List)线性表是是数据元素的有限序列。在日常生活中有很多例子，例如：英文小写字母表(a，b，c，z)是一

2、个长度为26的线性表一年中的四个季节(春，夏，秋，冬)是一个长度为4的线性表n维向量(x1，x2，xn)是一个长度为n的线性表，其中的每一个分量就是一个数据元素。2.2.1 线性表及其运算学生情况登记表是一个复杂的线性表,每个数据元素由若干数据项组成，称为记录(record)。现实中客观存在的实体经过数学抽象后都可以用线性表的一般形式来表示。 线性表是由n(n0)个数据元素a1，a2，an组成的一个有限序列。线性表中结点的个数n称为线性表的长度。当n=0，即线性表或是一个空表当n0，可以表示为(a1，a2，an)，其中数据对象的元素，通常也称其为线性表中的一个结点。2.线性表的逻辑结构 非空线

3、性表结构特征： (1)有且只有一个根结点a1，它无前件； (2)有且只有一个终端结点an，它无后件； (3)除根结点与终端结点外，其它所有结点有且只有一个前件，也有且只有一个后件。第2章 基本数据结构及其运算83. 线性表的顺序存储结构线性表的顺序存储结构基本特点：(1)线性表中所有元素所占的存储空间是连续的；(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。线性表(a1，a2，ai，an)中，每个元素占用k个存储单元，第i个元素ai在计算机存储空间中的存储地址为？第2章 基本数据结构及其运算9长度为n的线性表(a1，a2，ai，an)顺序存储结构举例：用一维数组存放长度为8的线性表

4、(29,18,56,63,35,24,31,47)第2章 基本数据结构及其运算11建立空线性表的顺序存储空间（即初始化线性表的顺序存储空间） #include stdlib.h void init_ls(ET *v，int m，int *n) vmalloc(m*sizeof(ET)； *n0； return； 释放线性表的顺序存储空间 free(v)；数据元素类型总的数据元素数量已经存入的数据元素数量申请所需的总的存储空间4.线性表顺序存储结构下的主要运算：插入：(1)在线性表的指定位置处加入一个新的元素；删除：(2)在线性表中删除指定的元素；查找：(3)在线性表中查找某个（或某些）特定的元

5、素；排序：(4)对线性表中的元素进行整序；不常用运算：(5)按要求将一个线性表分解成多个线性表（即线性表的分解）；(6)按要求将多个线性表合并成一个线性表（即线性表的合并）；(7)复制一个线性表（即线性表的复制）；(8)逆转一个线性表（即线性表的逆转）等。4-1.线性表在顺序存储下的插入运算第2章 基本数据结构及其运算14第2章 基本数据结构及其运算15线性表在顺序存储下的插入算法输入：线性表的存储空间V(1：m)；线性表的长度n（nm）；插入的位置i（i表示在第i个元素之前插入）；插入的新元素b。输出：插入后的线性表存储空间V(1：m)及线性表的长度n。第2章 基本数据结构及其运算16线性表

6、在顺序存储下的插入算法PROCEDURE Ins_ls(v，m，n，i，b) IF (nm) Then OVERFLOW；RETURN IF (in) Then in1 IF (i1) Then i1 FOR jn TO i BY 1 DOv(j)v(j-1) v(i)b nn1 RETURN第2章 基本数据结构及其运算17判断线性表是否存满判断插入位置是否合理把要插入位置之后的元素全部后移，为新元素腾出空间在腾出的位置上，写入要插入的元素4-2. 线性表在顺序存储下的删除运算第2章 基本数据结构及其运算18第2章 基本数据结构及其运算19线性表在顺序存储下的删除算法输入：线性表的存储空间V(

7、1：m)；线性表的长度n（nm）；删除的位置i（表示删除第i个元素）。输出：删除后的线性表存储空间V(1：m)及线性表的长度n。 第2章 基本数据结构及其运算20顺序存储结构方式下的线性表的删除算法PROCEDURE Dells(v，m，n，i) IF (n0) THEN UNDERFLOW；RETURN IF (i1)or(in) THEN “Not this element in the list”；RETURN FOR ji TO n1 DO v(j)v(j1) nn1 RETURN判断线性表是否为空判断要删除元素的位置是否合理把要删除元素后面的元素依次前移1.什么是栈栈（stack）是

8、一种特殊的线性表。对它的操作只能是“后进先出”（LIFO），也是使用最为广泛的数据结构之一。因为它的运算次序受到严格的规定，故又称为限定性数据结构。第2章 基本数据结构及其运算222.2.2 栈及其应用第2章 基本数据结构及其运算23 由这个例子可以看出，在这种特殊的线性表中，其插入与删除运算都只能在线性表的一端进行。即在这种线性表的结构中，一端是封闭的，不允许插入和删除元素；另一端是开口的，允许插入与删除元素。在顺序存储结构下，对这种类型线性表的插入与删除运算是不需要移动表中其它数据元素的。这种线性表成为栈。第2章 基本数据结构及其运算24栈(stack)是限定在一端进行插入与删除的线性表。

9、栈顶:允许插入与删除的一端.栈底:不允许插入与删除的另一端。栈是按照“先进后出” (FILOFirst In Last Out)或“后进先出” (LIFOLast In First Out)的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。栈具有记忆作用。用指针top来指示栈顶的位置，用指针bottom指向栈底。往栈中插入一个元素称为入栈运算，从栈中删除一个元素(即删除栈顶元素)称为退栈运算。关于栈的几个基本概念2. 栈的顺序存储及其运算top0表示栈空；topm表示栈满。建立空栈的顺序存储空间（即初始化栈的顺序存储空间） #include stdlib.h void init

10、_stack(ET *s，int m，int *top) smalloc(m*sizeof(ET)； *top0； return； 释放栈的顺序存储空间时 free(s)； (1)入栈运算 PROCEDURE PUSH(S，m，top，x) IF (topm) THEN StackOVERFLOW；RETURN toptop1 S(top)x RETURN 第2章 基本数据结构及其运算28(2) 退栈运算第2章 基本数据结构及其运算29PROCEDURE POP(S，m，top，y) IF (top0) THEN StackUNDERFLOW；RETURN yS(top) toptop1 RE

11、TURN(3) 读栈顶元素第2章 基本数据结构及其运算30PROCEDURE TOP(S，m，top，y) IF (top0) THEN “Stack empty”；RETURN yS(top) RETURN3.栈的应用表达式计算运算符栈，用于在表达式处理过程中存放运算符。开始时，运算符栈先压入一个表达式结束符“；”。操作数栈，用于在表达式处理过程中存放操作数。从左到右依次读出表达式中的各个符号：若是操作数，则压入操作数栈，依次读下一个符号。若是运算符，则作进一步判断：第2章 基本数据结构及其运算31AB*CD/E；AB*CD/E；第2章 基本数据结构及其运算33AB*CD/E；第2章 基本数

12、据结构及其运算34AB*CD/E；第2章 基本数据结构及其运算35若读出运算符的优先级大于运算符栈栈顶运算符的优先级，则将读出的运算符压入运算符栈，并依次读下一个符号。若读出的是表达式结束符“；”，且运算符栈栈顶的运算符也是表达式结束符“；”，则表达式处理结束，最后的计算结果在操作数栈的栈顶位置。若读出运算符的优先级不大于运算符栈栈顶运算符的优先级，则从操作数栈连续退出两个操作数，并从运算符栈退出一个运算符，然后作相应的运算（运算符为刚从运算符栈退出的运算符，运算对象为刚从操作数栈退出的两个操作数），并将运算结果压入操作数栈。第2章 基本数据结构及其运算364. 栈的应用递归依次打印输出自然数

13、1到n的非递归算法 PROCEDURE WRT(n) FOR k1 TO n DO OUTPUT k RETURN依次打印输出自然数1到n的递归算法 PROCEDURE WRT(n) IF (n0) THEN WRT(n)； OUTPUT n RETURN第2章 基本数据结构及其运算37主程序与子程序之间的调用关系 MAIN SUB1 SUB2 SUB3 SUB4 CALL SUB1 CALL SUB2 CALL SUB3 CALL SUB4 A： B： C： D： END RETURN RETURN RETURN RETURN第2章 基本数据结构及其运算381.什么是队列队列(equeue)

14、是指允许在一端进行插入、而在另一端进行删除的线性表。数据结构中的队列与生活中的“排队”极为相似，也是按“先来先解决”的原则行事的，并且既不允许“加塞”，也不允许“中途离队”。2.2.3 队列及其应用允许插入的一端称为队尾，用尾指针(rear)指向队尾元素。允许删除的一端称为排头(也称队头)，用排头指针(front)指向排头元素的前一个位置。队列又称为“先进先出” (FIFOFirst In First Out)或“后进后出” (LILOLast In Last Out)的线性表，体现了“先来先服务”的原则。往队列的队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。第2章 基本

15、数据结构及其运算40关于队列的几个基本概念第2章 基本数据结构及其运算41队列空的条件为 s0队列满的条件为 (s1)且frontrear第2章 基本数据结构及其运算42为什么不仅仅用front=rear来表示栈空？反而用来表示栈满？为什么叫加入条件S？2.循环队列及其运算第2章 基本数据结构及其运算43第2章 基本数据结构及其运算44建立循环队列顺序存储空间（即初始化循环队列顺序存储空间）#include stdlib.hvoid init_queue(q，m，front，rear，s)ET *q； int m， *front， *rear， *s； qmalloc(m*sizeof(ET)

16、； *frontm；*rearm；*s0； return；释放循环队列的顺序存储空间 free(q)；第2章 基本数据结构及其运算45(1) 入队运算PROCEDURE ADDCQ(Q，m，rear，front，s，x) IF (s1)and(rearfront) THEN QueueOVERFLOW；RETURN rearrear1 IF (rearm1) THEN rear1 Q(rear)x s1 RETURN第2章 基本数据结构及其运算46(2) 退队运算PROCEDURE DELCQ(Q，m，rear，front，s，y) IF (s0) THEN QueueUNDERFLOW；RETURN frontfront1 IF (frontm1) THEN front1 yQ(front) IF (frontrear) THEN s0 RETURN第2章 基本数据结构及其运算473.队列的应用(1) 给工人分配工作的模拟开辟一个队列结构的线性表。设置一个排头指针和一个队尾指针。初始时队列为空。每当有一个工人到调度员处报到时（包括新来的与完成任务后返回的），都将他加入到队尾；当需要一名工人去做某项工作时，就排头的工人去做该项