数据结构第三章教案及作业

1、数据结构Data Structure计算机科学与技术学院掌握栈和队列的特点，并能在相应的应用问题中正确选用熟练掌握栈的两种存储结构的基本操作实现算法，特别应注意栈满和栈空的条件熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的条件理解递归算法执行过程中栈的状态变化过程 教学目标第3章 栈与队列3教学内容3.1 栈3.2 栈的应用3.3 栈与递归的实现3.4 队列栈（Stack）1. 定义2. 逻辑结构3. 存储结构4. 运算规则5. 实现方式队列（Queue）1. 定义2. 逻辑结构3. 存储结构4. 运算规则5. 实现方式53.1 栈（Stack）（1）通常称插入、删除的这一端

2、为栈顶（Top），另一端称为栈底（Bottom）。 （2） 栈的删除称为退栈，插入称为进栈。（3）当表中没有元素时称为空栈图1 栈示意图栈：限制仅在表的一端进行插入和删除的线性表。一、栈的ADT用顺序栈或链栈存储均可，但以顺序栈更常见2. 存储结构与线性表相同，仍为一对一关系1. 逻辑结构只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则3. 运算规则关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同基本操作有入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空等4. 实现方式7栈的基本操作1.初始化栈：InitStack(&S) 将栈S置为一个空栈(不含任何

3、元素)。2.进栈：Push(&S,e) 将元素e插入到栈S中，也称为 “入栈”、“插入”、压入”。3.出栈：Pop(&S,&e) 删除栈S中的栈顶元素,用e返回其值，也称为”退栈”、“删除”、“弹出”。4.取栈顶元素：GetTop(S,&e) 若栈不空，用e返回栈S中栈顶元素。5.判栈空：StackEmpty(S) 判断栈S是否为空，若为空，返回值为true，否则返回值为false。9二、栈的表示与实现1. 顺序栈：栈的顺序存储结构简称为顺序栈。（1）顺序栈中元素用数组存放；（2）栈底位置是固定不变的，通常设一个指针base指示栈底的位置；（3）栈顶位置是随着进栈和退栈操作而变化的，通常设一个

4、指针top来指示当前栈顶位置;10#define STACK_INIT_SIZE 100#define STACKINCREMENT 10顺序栈的类型定义 typedef struct SElemType *base; SElemType *top; int stacksize; SqStack; Status InitStack(SqStack &S) =(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S.base)exit(OVERFLOW); =; =STACK_INIT_SIZE; return OK;/InitSta

5、ck（动画演示）12Status Push(SqStack &S,SElemType e) if (=) =(SElemType *), (S.stacksize+STACKINCREMENT)*sizeof(SElemType); if (!) exit(OVERFLOW); =; +=STACKINCREMENT; *+=e; return OK;13Status Pop(SqStack &S,SElemType &e) if (=) return ERROR; e=*-; return OK;14返回Status GetTop(SqStack S,SElemType &e)=S.base

6、)return ERROR;e=*（）;return OK;/GetTop15顺序栈栈满的条件：=栈空的条件：=栈非空时，指向栈顶元素的下一个位置b0 t0 t1 b10 m-1V双栈共享一个栈空间优点：互相调剂，灵活性强，减少溢出机会 b0 t0 t1 b10 m-1V栈空：topi = boti i表示栈的编号 栈满：top0+1=top1 或top1-1=top02.链栈：栈的链式存储结构。运算是受限的单链表，只能在链表头部进行操作，故没有必要附加头结点。栈顶指针就是链表的头指针 typedef struct StackNode SElemType data; struct StackN

7、ode *next; StackNode, *LinkStack;LinkStack S; data next 栈顶栈底S193.2 栈的应用例1 数制转换 将一个非负的十进制整数N转换为另一个等价的基为r的r进制数的问题，很容易通过“除r取余法”来解决。 例如：(12)10=(1100)2 N N div 2 N % 2 126063031110120算法十进制转八进制void conversion()InitStack(S);scanf(“%d”,N);while (N)Push (S, N%8); N=N/8;while(!StackEmpty(s) Pop(S,e);printf(“%

8、d”,e);/ conversion21例2 行编辑程序接收用户输入的一行文本，并显示出来。字符“#”为删字符，删除左边一个可见字符。字符“”为删行符，删除当前一行。用栈来处理一行，一行结束即用户输入n。例如：用户输入：whli#ilr#e(s#*s) outchaputchar(*s= # +);则实际有效为： while(*s) putchar(*s+);22算法3.2 行编辑程序处理一行 void LineEdit()InitStack(S);ch=getchar();while (ch!=EOF)while(ch!=EOF & ch!=n) Switch(ch) case #: Pop

9、(S,c); case :ClearStack(S);Default:Push(S,ch);ch=getchar();ClearStack(S);If(ch!=EOF) ch=getchar();DestoryStack(S);/LineEdit算法3.3 迷宫求解 （动画演示）算法描述：设定当前位置的初值为入口位置；Do 若当前位置可通， 则将当前位置插入栈顶； 若该位置是出口位置，则结束； 否则切换当前位置的东邻方块为新的当前位置； 否则， 若栈不空且栈顶位置尚有其他方向未经探索， 则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通， 则 删

10、去栈顶位置； 若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；while(栈不空)算法3.4 表达式求值（动画演示）算符间的优先关系OperandType EvaluateExpression()InitStack(OPTR);Push(OPTR,#);initStack(OPND);c=getchar();while(c!=#|GetTop(OPTR)!=#)if(!In(c,OP)Push(OPND,c);c=getchar();else switch(Precede(GetTop(OPTR),c) case : Pop(OPTR,theta); Pop(OPND,

11、b);Pop(OPND,a); Push(OPND,Operate(a,theta,b); break; /switch/whilereturn GetTop(OPND);/EvaluateExpression3.3 栈与递归的实现递归的定义 若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。算法3.5 汉诺塔（动画演示）hanoi(int n,char x,char y,char z)if(n=1)move(x,1,z);elsehanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1

12、,y,x,z)283.4 队列（ Queue ）一、队列的定义 队列：是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。 a1a2a3an.入队列队头队尾出队列29队列只允许在一端进行删除, 这一端称为队头（front）；只允许在一端进行插入, 这一端称为队尾（rear）；当队列中没有元素时称为空队列；队列是先进先出（First In First Out， FIFO ）的线性表。30二、链队列链队列: 特殊的单链表带表头结点：便于处理空队列带指向头结点的指针: 带指向队尾的指针 : 提高插入操作的效益链队列的运算指针变化情况 （P61）链队列的表示与实现typedef struct

13、 QNodeQElemType data;struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front;QueuePtr rear;LinkQueue;链队列的的基本操作Status InitQueue(LinkQueue &Q)=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);-next=NULL;return OK;Status DestroyQueue(LinkQueue &Q) while) =-next; ); =; return OK;Status

14、 EnQueue(LinkQueue &Q,QElemType e) p=(QueuePtr)malloc(sizeof(QNode); if(!p)exit(OVERFLOW); p-data=e; p-next=NULL; -next=p; =p; return OK;Status DeQueue(LinkQueue &Q,QElemType &e) =Q.rear)return ERROR; p=-next; e=p-data; -next=p-next; =; free(p); return OK;36三、循环队列（队列的顺序表示）1、一般数组实现：初始队列: =0; =0非空队列空队

15、列：=37一般数组实现存在的问题假设下述操作序列作用在初始为空的顺序队列上反复执行下列操作： EnQueue，DeQueue，EnQueue，DeQueue，Q.frontQ.rearT由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。可能由于尾指针已超越向量空间的上界而不能做入队操作。38 循环队列实现的思想设想数组Q0.AXQSIZE -1中的单元不是排成一行，而是围成一个圆环，即Q0接在QAXQSIZE -1的后面。将队列中从队头到队尾的元素按顺时针方向存放在循环数组中一段连续的单元中。 2、循环队列（动画演示）39循环队列示意图40入队(1)在队尾指针指示

16、的单元中存入新元素(2)再将队尾指针按顺时针方向移一位（加1?）出队 将队头指针依顺时针方向移一位（加1?） (如果需要，移动之前将所指单元中的元素赋值给一个变量)注意：按顺时针方向移动或时，其值是不断增大的，当增大超过AXQSIZE-1时，其值要置为0。循环队列的操作循环队列需解决的新问题问题1: 如何判断头指针或尾指针增大到AXQSIZE时, 如何重置为0? =(Q.front+1)%AXQSIZE或 Q.rear=(Q.rear+1)%AXQSIZE问题2: 如何区分空队列和满队列?方法1: 另设一个布尔变量来判断方法2: 少用一个元素空间（队列长度为AXQSIZE -1）满队列：在顺时

17、针方向的下1个位置 =(Q.rear+1) % MAXQSIZE空队列：=方法3: 用一个计数器记录队列中元素总数42循环队列类型定义#define MAXQSIZE 100typedef structQElemType *base; /初始化的动态分配存储空间 int front; /头指针，队非空时指向队头元素int rear; /尾指针，队非空时指队尾元素下一位置SqQueue;循环队列的基本操作Status InitQueue(SqQueue &Q)=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType);if(!Q.base)exit(OVERFL

18、OW);=0;return OK;int QueueLength(SqQueue Q)return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;Status EnQueue(SqQueue &Q,QElemType e)if(Q.rear+1)%MAXQSIZE=Q.front)return ERROR;=e;=(Q.rear+1)%MAXQSIZE;return OK;Status DeQueue(SqQueue &Q,QElemType &e)=Q.rear)return ERROR;=(Q.front+1)%MAXQSIZE;return OK;47作业1选择题

19、（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（ ）种情况。 A5，4，3，2，1 B2，1，5，4，3 C4，3，1，2，5 D2，3，5，4，1（2）若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为（ ）。 Ai Bn-i Cn-i+1 D不确定（3）数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素个数的公式为（ ）。 Ar-f B(n+f-r)%n Cn+r-f D（n+r-f)%n（4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，

20、并将删除结点的值保存到x中,则应执行操作（ ）。 Ax=top-data;top=top-link； Btop=top-link;x=top-link； Cx=top;top=top-link； Dx=top-link；（5）设有一个递归算法如下 int fact(int n) /n大于等于0 if(n=0) return 1; else return n*fact(n-1); 则计算fact(n)需要调用该函数的次数为（ ）。An+1 Bn-1 C n D n+248（6）栈在（ ）中有所应用。 A递归调用 B函数调用 C表达式求值 D前三个选项都有（7）为解决计算机主机与打印机间速度不匹配

21、问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。 A队列 B栈 C 线性表 D有序表（8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。 A2 B3 C4 D 6（9）在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top作为栈顶指针，则当作进栈处理时，top的变化为（）。 Atop不变 Btop=0 Ctop- Dtop+（10）设计一个判别表达式中左，

22、右括号是否配对出现的算法，采用（）数据结构最佳。A线性表的顺序存储结构 B队列 C. 线性表的链式存储结构 D. 栈（11）用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改（12）循环队列存储在数组A0.m中，则入队时的操作为（）。 A. rear=rear+1 B. rear=(rear+1)%(m-1) C. rear=(rear+1)%m D. rear=(rear+1)%(m+1) （13）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。 A. (rear+1)%n=front