严蔚敏版数据结构第三章

1、严蔚敏版数据结构第三章.3.1 栈Stack 第三章 栈和队列3.2 队列Queue1. 定义2. 逻辑构造3. 存储构造4. 运算规那么5. 实现方式1. 定义2. 逻辑构造3. 存储构造4. 运算规那么5. 实现方式21. 定义3.1 栈与同线性表一样，仍为一对一关系。用顺序栈或链栈存储均可，但以顺序栈更常见只能在栈顶运算，且访问结点时按照后进先出LIFO或先进后出FILO的原那么。关键是编写入栈和出栈函数，详细实现依顺序栈或链栈的不同而不同。根本操作有入栈、出栈、读栈顶元素值、建栈、或判断栈满、栈空等。3. 存储结构4. 运算规则5. 实现方式 2. 逻辑结构限定只能在表的一端进展插入和

2、删除运算的线性表只能在栈顶操作3问：堆栈是什么？它与一般线性表有什么不同？3.1 栈答：堆栈是一种特殊的线性表，它只能在表的一端即栈顶进展插入和删除运算。 与一般线性表的区别：仅在于运算规那么不同。一般线性表 堆栈逻辑构造：一对一 逻辑构造：一对一存储构造：顺序表、链表 存储构造：顺序栈、链栈运算规那么：随机存取 运算规那么：后进先出(LIFO)“进 压入=PUSHx)“出 弹出=POP ( y )4栈 是仅在表尾进展插入、删除操作的线性表。表尾(即 an 端)称为栈顶 top ; 表头(即 a1 端)称为栈底base例如： 栈 s= (a1 , a2 , a3 , .,an-1 , an )

3、 a1 称为 栈底元素 an 称为 栈顶元素插入元素到栈顶即表尾的操作，称为入栈。从栈顶即表尾删除最后一个元素的操作，称为出栈。教材P44对栈有更详细定义：强调：插入和删除都只能在表的一端栈顶进展！5栈的表示和实现顺序栈：栈的顺序存储构造，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，指针top指向栈顶元素在顺序栈中的下一个位置，base为栈底指针，指向栈底的位置。base空栈a 进栈b 进栈aabtopbasetopbasetop6顺序栈示意图s a1 a2 a3data(栈底)(栈顶)99.3210top顺序栈的类型表示:#define STACK_INIT_SIZE 100；

4、#define STACKINCREMENT 10；typedef char StackData;typedef struct /顺序栈定义 StackData *base; /栈底指针 StackData *top; /栈顶指针int stacksize；/当前已分配的存储空间 SeqStack；8判栈空int StackEmpty (SeqStack *S) if( S-top = S-base ) return 1 /空那么返回1 else return 0; /否那么返回0判栈满int StackFull (SeqStack *S) if( S-top- S-base = S- Sta

5、ckSize ) return 1 /判栈满,满那么返回1else return 0; /否那么返回0顺序栈的根本运算:9初始化void InitStack ( SeqStack *S) /置空栈S-base =( StackData *)malloc(STACK_INIT_SIZE * sizeof(StackData);if (!S-base) exit(OVERFLOW);S-top = S-base ; S-stacksize= STACK_INIT_SIZE ;Return ok; 10 a1 a2 an顺序栈S ai表和栈的操作区别对线性表 s= (a1 , a2 , . , an

6、-1 , an )表头表尾栈底base栈顶top低地址高地址写入：vi= ai读出： x= vi压入：PUSH (an+1)弹出： POP (x)前提：一定要预设栈顶指针top！低地址高地址vi a1 a2 ai an 顺序表Vn an+111入栈操作例如用堆栈存放A，B，C，D 注意要遵循“后进先出 原那么AACBABAtop核心语句：top=L; 顺序栈中的PUSH函数status Push(ElemType x) if(topM)上溢 else vtop+=x;Push (B);Push (C);Push (D);toptoptoptop低地址LPush (A);高地址MBCD12入栈i

7、nt Push (SeqStack *S, StackData x) /插入元素x为新的栈顶元素 if ( StackFull (S) ) S-base =( StackData *)malloc(S-base ,(S-stacksize+ STACKINCREMENT) * sizeof(StackData);if(! S-base)exit(overflow); S-top= S-base + S-stacksize;S-stacksize+= STACKINCREMENT; /追加存储空间 *(S-top)=x; S-top+;Return ok13 出栈操作例如从栈中取出B 注意要遵循

8、“后进先出 原那么DCBAtoptopDCABDCBAtopDCBAtop低地址L高地址MD核心语句：Pop ( );Pop ( );Printf( Pop () );顺序栈中的POP函数status Pop( ) if(top=L) 下溢 else y=v-top; return(y); 14出栈int pop (SeqStack *S, StackData &x) /假设栈空返回0, 否那么栈顶元素退出到x并返回1 if ( StackEmpty(S) ) return 0; -(S-top);x = *(S-top); return 1;15例1：一个栈的输入序列是12345，假设在入栈

9、的过程中允许出栈，那么栈的输出序列43512可能实现吗？12345的输出呢？ 43512不可能实现，主要是其中的12顺序不能实现； 12345的输出可以实现，只需压入一个立即弹出一个即可。 435612中到了12顺序不能实现； 135426可以实现。例2：假设一个栈的输入序列为123456，能否得到435612和135426的出栈序列？答：答：16例3严题集一个栈的输入序列为123，假设在入栈的过程中允许出栈，那么可能得到的出栈序列是什么？答：可以通过穷举所有可能性来求解： 1入1出， 2入2出，3入3出， 即123； 1入1出， 2、3入3、2出， 即132； 1、2入，2出， 3入3出，

10、即231； 1、2入，2、1出，3入3出， 即213； 1、2、3入，3、2、1出， 即321；合计有5种可能性。17例4：计算机系2001年考研题程序设计根底设依次进入一个栈的元素序列为c，a，b，d，那么可得到出栈的元素序列是： a，b，c，d c，d，a，b b，c，d，a a，c，d，bA、D可以 B、C不行。讨论：有无通用的判别原那么？有。在可能的输出序列中，不存在这样的输入序列i，j，k，能同时满足 ijk 和 PjPkdata=x; p-link=st; st=p; Status pop( ) if(st=NULL)下溢elsey=st-data;p=st;st=st-link;

11、 free(p); return(y); 链栈入栈函数链栈出栈函数插入表头从表头删除22说 明链式栈无栈满问题，空间可扩大插入与删除仅在栈顶处执行链式栈的栈顶在链头适宜于多栈操作23 数制转换十转N P48 设计思路：用栈暂存低位值例2：括号匹配的检验P49 设计思路：用栈暂存左括号例3 ：表达式求值 -P52 设计思路：用栈暂存运算符例1：栈的应用举例241.数制转换N = (N div d)d + N mod d 例如：1348)10 = (2504)8 ，其运算过程如下：N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2输出顺序计算顺序25

12、void conversion () InitStack(S); scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion26在用户输入一行的过程中，允许用户输入出过失，并在发现有误时可以及时更正。设立一个输入缓冲区，用以承受用户输入的一行字符，然后逐行存入用户数据区; 并假设“#为退格符，“为退行符。假设从终端承受两行字符： whli#ilr#es#*s) outchaputchar(*s=#+);实际有效行为： while (

13、*s) putchar(*s+);27Void LineEdit()InitStack(s);ch=getchar();while (ch != EOF) /EOF为全文完毕符while (ch != EOF & ch != n) switch (ch) case # : Pop(S, c); break; case : ClearStack(S); break;/ 重置S为空栈 default : Push(S, ch); break; ch = getchar(); / 从终端接收下一个字符 28将从栈底到栈顶的字符传送至调用过程的数据区；ClearStack(S); / 重置S为空栈if

14、 (ch != EOF) ch = getchar(); DestroyStack(s);29例3 表达式求值( 这是栈应用的典型例子 ) 这里，表达式求值的算法是“算符优先法。例如：3*7 2 1要正确求值，首先理解算术四那么运算的规那么： a. 从左算到右 b. 先乘除，后加减 c. 先括号内，后括号外例：4+2*3-10/5=4+6-10/5=10-10/5=10-2=8 由此，此表达式的计算顺序为： 3*7 2 = 3 * 5 = 15302根据上述三条运算规那么，在运算的每一步中，对任意相继出现的算符1和2 ，都要比较优先权关系。算符优先法所根据的算符间的优先关系见教材P53表 是提

15、供给计算机用的表！由表可看出，右括号 ) 和井号 # 作为2时级别最低； 由c 规那么得出： * ，/， + ，-为1时的优先权低于，高于 由a规那么得出：= 说明括号内运算，已算完。 # = # 说明表达式求值完毕。栈的应用表达式求值313算法思想：设定两栈：操作符栈 OPTR ，操作数栈 OPND栈初始化：设操作数栈 OPND 为空；操作符栈 OPTR 的栈底元素为表达式起始符 #；依次读入字符：是操作数那么入OPND栈，是操作符那么要判断： if 操作符 栈顶元素，压入OPTR栈。栈的应用表达式求值32栈的应用表达式求值OPTROPNDINPUTOPERATE3*(7-2)#Push(o

16、pnd,3) #*(7-2)#3#Push(optr,*)#,*3(7-2)#Push(optr,()#,*,(37-2)#Push(opnd,7)#,*,(3,7-2)#Push(optr,-)#,*,(,3,72)#Push(opnd,2)#,*,(,3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)33Status EvaluateExpression( OperandType &result) InitStack(OPND); InitStack(OPTR);Push(OPTR ,#);c=

17、getchar(); while(c!=#)/(GetTop(OPTR)!=#) if (!In(c,OP) Push(OPND,c); c=getchar(); else switch(compare(c,GetTop(OPTR) case : Push(OPTR , c); c=getchar();break; case =: Pop(OPTR);c=getchar();break; case next=S; rear=S;出队头部删除：front-next=p-next; 队列会满吗？front=rear一般不会，因为删除时有free动作。除非内存缺乏！37frontrearx元素x入队

18、frontrearxy元素y入队frontrearxy元素x出队frontrear空队列38链式队列的定义typedef int QueueData;typedef struct node QueueData data; /队列结点数据 struct node *link; /结点链指针 QueueNode;typedef struct QueueNode *rear, *front; LinkQueue;39根本操作Status InitQueue(LinkQueue &Q) / 构造一个空队列Qif(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNod

19、e) exit(OVERFLOW); Q.front-next=NULL; return OK; 40Status QueueEmpty(LinkQueue Q) / 假设Q为空队列,那么返回TRUE,否那么返回FALSE if(Q.front=Q.rear) return TRUE; else return FALSE; 41int QueueLength(LinkQueue Q) / 求队列的长度 int i=0; QueuePtr p; p=Q.front; while(Q.rear!=p) i+; p=p-next; return i; 42Status EnQueue(LinkQue

20、ue &Q,QElemType e) / 插入元素e为Q的新的队尾元素 QueuePtr p; if(!(p=(QueuePtr)malloc(sizeof(QNode) / 存储分配失败 exit(OVERFLOW); p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK; 43 Status DeQueue(LinkQueue &Q,QElemType &e) / 假设队列不空,删除Q的队头元素,用e返回其值,并返回OK,否那么返回ERROR QueuePtr p; if(Q.front=Q.rear) return ERROR

21、; p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; free(p); return OK; 44顺序队示意图Q(队尾)(队首)front a1 a2 a3data a40.99rear 队列会满吗？很可能会，因为数组前端空间无法释放。因此数组应当有长度限制。 空队列的特征？ 约定：front=rear队尾后地址入队(尾部插入)：vrear=e; rear+;出队(头部删除)：x=vfront; front+;讨论：假溢出 有缺陷 怎样实现入队和出队操作？3.2 队列45问：什么叫“假溢出 ？

22、如何解决？答：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出。3.2 队列解决假溢出的途径采用循环队列46a3a2a10123N-1rearfront循环队列臆造顺序队列a3a2a1frontrear 0 1 2 3 . .N-1新问题：在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！解决方案有三： 加设标志位，让删除动作使其为1,插入动作使其为0,那么可识别当前 front=rear 使用一个计数器记录队列中元素个数即队列长度； 人为浪费一个单元，令队满特征为front=(rear+1)%

23、N；47队空条件 : front = rear (初始化时：front = rear )队满条件： front = (rear+1) % N (N=maxsize)队列长度：L=Nrearfront% N J2 J3J1 J4 J5frontrear 选用空闲单元法：即front和rear之一指向实元素，另一指向空闲元素。 问2： 在具有n个单元的循环队列中，队满时共有多少个元素？ n-1个5 问1：左图中队列长度L=？48J6 J5J7J8 J9例1： 一循环队列如以以下图所示，假设先删除4个元素，接着再插入4个元素，请问队头和队尾指针分别指向哪个位置? J2 J3J1 J4 J5front

24、rear解：由图可知，队头和队尾指针的初态分别为front=1和rear=6。frontrear删除4个元素后front=5；再插入4个元素后，r=(6+4)%6=4 frontfrontfrontfrontfront49例2 ：数组n用来表示一个循环队列，f 为当前队列头元素的前一位置，r 为队尾元素的位置。假定队列中元素的个数小于n，计算队列中元素的公式为: rf nfr% n nrf nrf% n4种公式哪种合理？当 r f 时A合理；当 r f 时C合理；分析 ：综合2种情况，以D的表达最为合理例3：在一个循环队列中，假设约定队首指针指向队首元素的前一个位置。那么，从循环队列中删除一个

25、元素时，其操作是 先 ，后 。 挪动队首指针取出元素50问：为什么要设计队列？它有什么独特用处？离散事件的模拟模拟事件发生的先后顺序；操作系统中多道作业的处理一个CPU执行多个作业；3. 简化程序设计。答：循环队列的操作实现见教材P6451循环队列的操作实现1初始化一空队列算法要求：生成一空队列算法操作：为队列分配根本容量空间 设置队列为空队列，即 front=rear=0也可为任意单元，如 2，或 4;52算法：Status InitQueue ( SqQueue &q )/初始化空循环队列 q q . base=(QElemType *)malloc(sizeof(QElemType* Q

26、UEUE_MAXSIZE); /分配空间 if () exit(OVERFLOW);/失败，退出程序 q.front =q.rear=0;/置空队列 return OK; /InitQueue;新开单元的地址为0那么表示内存缺乏53算法说明：向循环队列的队尾插入一个元素分 析：(1) 插入前应领先判断队列是否满 if ( q . rear + 1 ) % QUEUE_MAXSIZE )=q.front) return ERROR;(2插入动作 q.base q.rear = e; q.rear = ( q . rear + 1 ) % QUEUE_MAXSIZE; 2 入队操作54Status

27、 EnQueue(SqQueue &q, QElemType e)/向循环队列 q 的队尾参加一个元素 e if ( (q.rear+1) % QUEUE_MAXSIZE = = q.front ) return ERROR ; q.base q.rear = e; /存储 q.rear = ( q . rear + 1 ) % QUEUE_MAXSIZE;/指针后移 return OK; / EnQueue;2 入队操作完好函数553出队操作算法说明：删除队头元素，返回其值 e 分 析： 1 在删除前应当判断队列是否空； if (q.front = q.rear ) return ERROR

28、; 2插入动作分析； 因为队头指针front指向队头元素的位置，所以： e = q.base q.front ; q.front = ( q . front + 1 ) % QUEUE_MAXSIZE; 56Status DeQueue ( SqQueue &q, QElemType &e) /假设队列不空，删除循环队列 q 的队头元素， /由 e 返回其值，并返回OK if ( q.front = = q.rear ) return ERROR;/队列空 e = q.base q.front ; q.front=(q.front+1) % QUEUE_MAXSIZE ; return OK;

29、 / DeQueue算法：57讨论代本章小结线性表、栈与队的异同点一样点：逻辑构造一样，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表只是对插入、删除运算加以限制。不同点： 运算规那么不同，线性表为随机存取，而栈是只允许在一端进展插入和删除运算，因此是后进先出表LIFO；队列是只允许在一端进展插入、另一端进展删除运算，因此是先进先出表FIFO。 用处不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。58一 选择题1. 对于栈操作数据的原那么是 。先进先出 B. 后进先出 C. 后进后出 D. 不分顺序

30、2. 一个栈的输入序列为123n，假设输出序列的第一个元素是n，输出第i1=i=n个元素是 。A. 不确定 B. n-i+1 C. i D. n-i3. 假设一个栈的输入序列为1,2,3,n，输出序列的第一个元素是i，那么第j个输出元素是 。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的4. 栈在 中应用。【中山大学 1998 二、32分】递归调用 B. 子程序调用 C. 表达式求值 D. A， 5. 有六个元素6，5，4，3，2，1 的顺序进栈，问以下哪一个不是合法的出栈序列？ 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 596. 在作进栈运算时,应先判别栈是否( ),在作退栈