DS03_栈和队列

1、2022-4-241第第3 3章章 栈和队列栈和队列2022-4-242a a0 0a a1 1a an-1n-1入栈入栈出栈出栈栈顶栈顶 toptop栈底栈底 bottombottom图图3-13-1栈的示意图栈的示意图2022-4-2432022-4-244入栈入栈出栈出栈入栈入栈出栈出栈栈顶栈顶 top图图3-1栈的初始状态栈的初始状态2022-4-2452022-4-246 top-1toptoptop-1AtopBCDAABC01230123012301230123(a)(b)(c)(d)(e)（a a）当栈中没有数据元素时，表示为栈空。栈顶元素所对应的当栈中没有数据元素时，表示为栈

2、空。栈顶元素所对应的下标值下标值top=-1top=-1。（b b）表示在（表示在（a a）基础上执行基础上执行Push(S, A)Push(S, A)后得到这种状态后得到这种状态。（c c）又有三个元素又有三个元素B B、C C、D D先后入栈，此时栈顶元素的下标值先后入栈，此时栈顶元素的下标值top=3top=3。栈已满。栈已满。（d d）表示在（表示在（c c）状态下，执行一次状态下，执行一次Pop(SPop(S，x)x)运算得到。运算得到。（e e）表示在（表示在（d d）状态下，执行三次状态下，执行三次Pop(SPop(S，x)x)运算得到。此时运算得到。此时栈顶下标值栈顶下标值to

3、p=-ltop=-l，又变成栈空状态又变成栈空状态 2022-4-247 SeqStack *InitStack() SeqStack *S; s=(SeqStack*)malloc(sizeof(SeqStack); s-top=-1; return s; int Empty_SeqStack(SeqStack *S) if (S-top=-1) return 1; else return 0; 2022-4-248int Push_SeqStack(SeqStack int Push_SeqStack(SeqStack * *s,DataType x)s,DataType x) if(s-

4、top=MaxSize-1) if(s-top=MaxSize-1) printf(n Stack is full!); printf(n Stack is full!); return 0; return 0; s-top+; s-top+; s-datas-top=x; s-datas-top=x; return 1; return 1; 算法思想：算法思想： 检查栈是否已满，若检查栈是否已满，若满则进行满则进行“上溢出上溢出”处理；处理； 不满则栈顶指针加不满则栈顶指针加1 1，即即top+top+。 将新元素赋给将新元素赋给toptop所所指示的单元；指示的单元；2022-4-249i

5、nt Pop_SeqStack(SeqStackint Pop_SeqStack(SeqStack * *s,DataType s,DataType * *x) x) if(Empty_SeqStack if(Empty_SeqStack (s) (s) printf(n Stack is free!); printf(n Stack is free!); return 0; return 0; * *x=s-datas-top;x=s-datas-top; s-top-; s-top-; return 1; return 1; 算法思想：算法思想： 检查栈是否已检查栈是否已空，若空则进行空，

6、若空则进行“下溢出下溢出”处理；处理； 不空则取出栈不空则取出栈顶元素之值。顶元素之值。 将栈顶指针将栈顶指针toptop下移一位；下移一位；2022-4-2410int Get_SeqStack(SeqStack *S, DataType *x) if(Empty_SeqStack (S) printf(n Stack is free!); retrn 0; *x=S-dataS-top; return 1; 算法思想：算法思想： 检查栈是否已检查栈是否已空，若空则进行空，若空则进行“下下溢出溢出”处理；处理； 不空则取出栈不空则取出栈顶元素之值。顶元素之值。 栈顶指针栈顶指针toptop不

7、变；不变；2022-4-2411栈1栈2top1top22022-4-24122022-4-24132022-4-2414topCBA栈顶栈底data next2022-4-2415(a) top-next=NULL表示空栈(b) A，B两个元素顺序入栈(c) B元素出栈topAtoptopAB2022-4-24162022-4-24172022-4-24182022-4-24192022-4-24202022-4-2421例例3-13-1：数制转换问题（辗转相除法：数制转换问题（辗转相除法, ,十进制数转十进制数转r r进制）进制）算法分析：算法分析：算法的原理：算法的原理：N=N=（N/r

8、N/r）* *r + N%r r + N%r （N N为十进制数，为十进制数，r r为其他进制）为其他进制）算法：算法：设置一个顺序栈设置一个顺序栈 : : 本算法包含本算法包含（InitStack( ), Push_SeqStack( ) , InitStack( ), Push_SeqStack( ) , Pop_SeqStack( ),Eampty_SeqStack( ) , Pop_SeqStack( ),Eampty_SeqStack( ) , （利（利用栈的用栈的“后进先出后进先出”） 2022-4-2422Void conversion (int N, int r)Void co

9、nversion (int N, int r) SeqStack SeqStack * *s; int x;s; int x; s=Initstack (s); s=Initstack (s); While(N!=0) While(N!=0) Push_SeqStack(s, (N%r) Push_SeqStack(s, (N%r) N=N/r; N=N/r; / /* *转换算法核心转换算法核心* */ / While(! Empty_SeqStack(s) While(! Empty_SeqStack(s) Pop_SeqStack(s, &x); Pop_SeqStack(s,

10、&x); printf(“%d”,x); printf(“%d”,x); 2022-4-2423“In”Exit2022-4-2424 求迷宫中从入口到出口的所有路径，所求路径必求迷宫中从入口到出口的所有路径，所求路径必须是简单路径，即某一位置不能重复走两遍。须是简单路径，即某一位置不能重复走两遍。 求解思想：求解思想：使用使用回溯法回溯法，即，即从入口出发，按某一从入口出发，按某一方向向前探索，若能走通（未走过的），则到达新点，方向向前探索，若能走通（未走过的），则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，换

11、下一个方向再继续试探，直到所原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。走又返回到入口点。 在求解过程中，为了保证无路在求解过程中，为了保证无路可行可行时，能沿原路时，能沿原路返回前一点以便继续下一个方向向前试探，则需要用返回前一点以便继续下一个方向向前试探，则需要用一个栈一个栈来来保存所能够到达的每一点的坐标及从该点前保存所能够到达的每一点的坐标及从该点前进的方向。进的方向。 2022-4-2425需要解决的四个问题：需要解决的四个问题：（1 1）表示迷宫的数据结构）表示迷宫的数据

12、结构 设迷宫为设迷宫为m m行行n n列，利用列，利用mazem+2n+2 mazem+2n+2 来表示来表示一个带围墙的迷宫。一个带围墙的迷宫。mazeij=0mazeij=0或或1 1，其中，其中0 0表示表示通道，通道，1 1表示墙（不通）。迷宫四周为围墙，因此值表示墙（不通）。迷宫四周为围墙，因此值全部为全部为1 1。迷宫可定义如下：。迷宫可定义如下：#define M 6 /#define M 6 /迷宫的实际行迷宫的实际行#define N 8 /#define N 8 /迷宫的实际列迷宫的实际列 int maze M+2N+2 ; int maze M+2N+2 ; 2022-4

13、-2426（2 2）试探方向）试探方向对于迷宫的每个点，有对于迷宫的每个点，有8 8个方向可以试探。个方向可以试探。(x，y)(x，y+1)(x，y-1)(x+1，y)(x-1，y)(x-1，y+1)(x-1，y-1)(x+1，y-1)(x+1，y+1)2022-4-2427 从正东开始沿顺时针进行从正东开始沿顺时针进行的这的这8 8个方向的坐标增量，放个方向的坐标增量，放在一个结构体数组在一个结构体数组move 8 move 8 中，在中，在move move 数组中，每个元数组中，每个元素由两个域组成，素由两个域组成，x x：横坐标：横坐标增量，增量，y y：纵坐标增量。：纵坐标增量。mo

14、vemove数组为数组为 ：typedef struct typedef struct int x, y ; int x, y ; item ; item ; item move8 ;item move8 ;xy00111121031-140-15-1-16-107-112022-4-2428（3 3）栈的设计）栈的设计 当到达了某点而无路可走时，需返回前一点，再当到达了某点而无路可走时，需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入从前一点开始向下一个方向继续试探。因此，压入栈栈中的不仅是顺序到达的各点的坐标，而且还要栈栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本

15、点的方向序号。栈中元素是一个有从前一点到达本点的方向序号。栈中元素是一个由行、列、方向组成的三元组，栈中元素的类型定由行、列、方向组成的三元组，栈中元素的类型定义如下：义如下：#define MAXSIZE 100#define MAXSIZE 100typedef struct int x , y , d ; DataType ;typedef struct int x , y , d ; DataType ;typedef struct stack typedef struct stack DataType elemMAXSIZE; /DataType elemMAXSIZE; /存栈顺序

16、表存栈顺序表 int top; int top; /栈顶下标栈顶下标 SQSTACK; SQSTACK;SQSTACK s ; /SQSTACK s ; /栈的定义栈的定义2022-4-2429（4 4）标志已走过的坐标）标志已走过的坐标 为防止重复到达某点，以避免发生死循环，一为防止重复到达某点，以避免发生死循环，一种方法是另外设置一个标志数组种方法是另外设置一个标志数组markmnmarkmn，它的，它的所有元素都初始化为所有元素都初始化为0 0，一旦到达了某一点，一旦到达了某一点 ( i , ( i , j )j )后，使后，使markij markij 置置1 1，下次再试探这个位置，

17、下次再试探这个位置时就不能再走了；另一种方法是当到达某点（时就不能再走了；另一种方法是当到达某点（i , i , j j）后，使）后，使mazeij mazeij 置置 1 1，以便区别未到达过，以便区别未到达过的点，同样也能起到防止走重复点的目的。的点，同样也能起到防止走重复点的目的。 这里使用后一种方法。这里使用后一种方法。 2022-4-2430int mazepath (int mazeM+2N+2, item move8)int mazepath (int mazeM+2N+2, item move8) SeqStack SeqStack * *s; s; DataType temp

18、; DataType temp; int x,y,d,i,j; int x,y,d,i,j; s=InitStack(); s=InitStack(); /栈初始化栈初始化 temp.x=1; temp.y=1; temp.d=-1;temp.x=1; temp.y=1; temp.d=-1; Push(s, temp); Push(s, temp); while (! EmptySeqStack (s) while (! EmptySeqStack (s) PopSeqStack (s, &temp); PopSeqStack (s, &temp); x=temp.x; y=

19、temp.y; d=temp.d+1; x=temp.x; y=temp.y; d=temp.d+1; while (d8) while (d8) i=x+moved.x; i=x+moved.x; j=y+moved.y; j=y+moved.y; 2022-4-2431 if (mazeij=0)if (mazeij=0) temp.x=x;temp.y=y;temp.d=d; / temp.x=x;temp.y=y;temp.d=d; /坐标及方向坐标及方向 PushSeqStack (s,temp); /PushSeqStack (s,temp); /坐标及方向入栈坐标及方向入栈 x=

20、i; y=j;x=i; y=j; mazexy=-1; / mazexy=-1; /到达新点到达新点 if (x=M&y=N) if (x=M&y=N) printpath (s); / printpath (s); /输出路径输出路径 return 1; /return 1; /迷宫有路迷宫有路 else d=0; else d=0; else d+; else d+; return 0; /return 0; /迷宫无路迷宫无路2022-4-2432void printpath (SeqStack void printpath (SeqStack * *s)s) DataT

21、ype temp; DataType temp; printf (%d,%d)-, M, N); printf (%d,%d)-, M, N); while (! EmptySeqStack (s) while (! EmptySeqStack (s) PopSeqStack (s, &temp); PopSeqStack (s, &temp); printf (%d,%d)-, temp.x, temp.y); printf (%d,%d)=0 & c0 例例3-4 栈与递归栈与递归2022-4-2442 #define MAXSIZE 100float nfact(

22、 int n ) int stackMAXSIZE; / /* * 使用顺序栈结构实现使用顺序栈结构实现的阶乘的阶乘* */ / int top=-1; long res; while (n0) stack+top=n; n=n-1; res=1.0; while (top=0) res = res * stacktop-; return ( res );2022-4-24432022-4-24442022-4-24452022-4-2446 -1 0 1 2 3 MAXN-1frontrear dc-1 0 1 2 3 MAXN-1frontrearsr -1 0 1 2 3 MAXN-1f

23、rontrear队列初始指针为：rear=front= -1, 队空：front=rear非空：front MAXN-1或rear=MAXN2022-4-2447（a a）表示空队列，表示空队列， rear=front=-1rear=front=-1。（b b）元素元素A A入队后，入队后， rear=0rear=0，front=-1front=-1。（c c）B B，C C依次入队后，依次入队后， rear=2rear=2，front=-1front=-1。（d d）A A，B B，C C依此出队后依此出队后, , rear=front=2rear=front=2。（e e）D D、E E依

24、次依次入队后入队后, ,rear=4, front=2rear=4, front=2。（f f）D D、E E依次依次出队后，出队后，rear=front=4rear=front=4。432104321043210432104321043210rearfrontrearrearrearrearrearfrontfrontfrontfrontfrontBC(a)(b)(c)(d)(e)(f)AADE2022-4-2448队列的溢出队列的溢出 当队列的当队列的rearrear指针达到最大下标指针达到最大下标MAXSIZE-1MAXSIZE-1时，便出现队满的时，便出现队满的情况（即溢出），这利溢出

25、有真溢出与假溢出之分：情况（即溢出），这利溢出有真溢出与假溢出之分：sr -1 0 1 2 3 MAXSIZE-1frontrearsr da-1 0 1 2 3 MAXSIZE-1frontrearbc真溢出真溢出假溢出假溢出解决溢出的方法：引入循环队列技术解决溢出的方法：引入循环队列技术2022-4-2449循环队列循环队列解决队列假溢出的办法是将存放队列元素的数组首尾相解决队列假溢出的办法是将存放队列元素的数组首尾相接，形成循环队列。接，形成循环队列。 2022-4-2450 为了将队空和对满的条件加以区分，一般不使为了将队空和对满的条件加以区分，一般不使用用frontfront指针所指

26、的位置指针所指的位置( (即浪费一个空闲单元即浪费一个空闲单元) )。队空条件为队空条件为front=rearfront=rear队满条件为队满条件为(rear+1)%M=front(rear+1)%M=front30124567frontrearABCD30124567frontrear30124567frontrearABCDFGE (a)(a)循环队列空循环队列空 (b)(b)非空循环队列非空循环队列 (c)(c)循环队列满循环队列满 循环队列示意图循环队列示意图 2022-4-2451如图所示是具有五个存储单元的循环队列如图所示是具有五个存储单元的循环队列012340123401234

27、0123401234frontrearAfrontrearrearrearrearfrontfrontfrontABCDBCD(a)(b)(c)(d)(e)（a a）表示空队列，表示空队列， rear= front=0rear= front=0。（b b）元素元素A A入队后，入队后， rear=1rear=1， front=0 front=0。（c c）B B，C C，D D依次入队后，依次入队后， rear=4rear=4， front=0 front=0。（d d）A A出队后出队后, , front=1 ,rear=4front=1 ,rear=4。（e）B，C，D出队后出队后, re

28、ar= front=4。 2022-4-2452( ( ) ) ; ; q-front=q-rear=MAXSIZE-1; q-num=0; q-front=q-rear=MAXSIZE-1; q-num=0; return q; return q; 2022-4-2453int In_Queue(Cint In_Queue(C * *q,DataType x)q,DataType x) if(q-num=MaxSize) if(q-num=MaxSize) printf(n Queue is full!); printf(n Queue is full!); return 0; return

29、 0; q-rear=(q-rear+1)%MaxSize; q-rear=(q-rear+1)%MaxSize; q-dataq-rear=x; q-dataq-rear=x; return 1; return 1;if (q-rear+1)%MaxSize=q-front) /浪费一空闲单元判满浪费一空闲单元判满算法思想：算法思想： 检查队列是否已满，若检查队列是否已满，若满则进行满则进行“上溢出上溢出”处理；处理； 不满不满, ,则修改尾指针则修改尾指针rear=(rear+1)%MaxSizerear=(rear+1)%MaxSize。 将新元素赋给将新元素赋给rearrear所指所指

30、示的单元；示的单元；2022-4-2454int Out_SeQueue(Cint Out_SeQueue(C * *q,DataType q,DataType * *x)x) if(Empty_SeQueue(q) if(Empty_SeQueue(q) printf(n Queue is free); printf(n Queue is free); return 0; return 0; q-front=(q-front+1)%MaxSize; q-front=(q-front+1)%MaxSize; * *x=q-dataq-front;x=q-dataq-front; return

31、1; return 1; int Empty_SeQueue(Cint Empty_SeQueue(C * *q)q) return(q-num=0)?1:0; return(q-num=0)?1:0; return(q-rear=q-front)?1:0;/浪费一空闲单元判空浪费一空闲单元判空算法思想：算法思想： 检查队列是否空，若空检查队列是否空，若空则进行则进行“下溢出下溢出”处理；处理； 不空不空, ,则修改队头指针则修改队头指针front=(front+1)%MaxSizefront=(front+1)%MaxSize。 将新元素赋给将新元素赋给frontfront所所指示的单元；指

32、示的单元；2022-4-2455.frontreardatanext2022-4-2456(a) 队空frontrearq(c) 元素B入队后frontrearqAB(b) 元素A入队后frontrearqA(d) 元素A出队ABfrontrearq2022-4-24572022-4-2458(a) 队空frontrearq2022-4-2459int In_LQueue(LQUEUE int In_LQueue(LQUEUE * *q,DataType x)q,DataType x) QNode QNode * *s;s; s=(QNode s=(QNode * *)malloc(sizeo

33、f(QNode); )malloc(sizeof(QNode); s-data=x; s-data=x; s-next=q-rear-next;( s-next=q-rear-next;(或或s-next=NULL;)s-next=NULL;) q-rear-next=s; q-rear=s; q-rear-next=s; q-rear=s; return 1; return 1; int Empty_LQueue(LQueue int Empty_LQueue(LQueue * *q)q) return(q-front=q-rear?1:0); return(q-front=q-rear?1

34、:0);2022-4-24602022-4-2461int Front_LQueue(LQueue int Front_LQueue(LQueue * *q,DataType q,DataType * *x)x) if(Empty_LQueue(q) if(Empty_LQueue(q) printf(n Queue is free!); printf(n Queue is free!); return 0; return 0; * *x=q-front-next-data;x=q-front-next-data; return 1; return 1; 2022-4-24622022-4-2

35、4632022-4-2464/ /* *出队列算法出队列算法* */ /2022-4-24650 1 2 M-3 M-2 M-1 栈0底栈1底top0top12022-4-2466代码：代码： typedef struct dustack typedef struct dustack / /* *共享栈类型定义共享栈类型定义 DataType datam; DataType datam; int top0 ,top1; int top0 ,top1; Dubstack Dubstack void Initstack (Dubstack void Initstack (Dubstack * *s ) s ) / /* *初始化初始化* */ / s-top0=-1; s-top1=m ; s-top0=-1; s-top1=m ; 2022-4-2467void push (Dubstack void push (Dubstack * *s, int i ,D