数据结构第三部分栈和队列.ppt

数据结构课程中国科学技术大学网络学院中国科学技术大学网络学院中国科学技术大学网络学院中国科学技术大学网络学院数据结构第三章第三章栈和队列栈和队列本章内容3.1 栈3.2 栈的应用举例3.3 队列中国科大数据结构3.1 栈3.1.1 3.1.1 栈的定义栈的定义p栈（栈（stackstack）：是限定仅在表尾进行插入和删除操作的线性表又：是限定仅在表尾进行插入和删除操作的线性表又称为称为后进先出后进先出（last in first outlast in first out）的线性表（简称）的线性表（简称LIFOLIFO结构）p栈顶（栈顶（toptop）：栈表尾端栈表尾端p栈底（栈底（bottombottom）：栈表头端栈表头端例：假设栈例：假设栈 S=(a S=(a1 1,a,a2 2,a,an n) ) ，则，则 a a1 1 称称为栈底元素，为栈底元素，a an n 为栈顶元素栈中元素按为栈顶元素栈中元素按a a1 1,a,a2 2,a,an n 的次序进栈，退栈的第一个元的次序进栈，退栈的第一个元素应为栈顶元素如右图所示素应为栈顶元素如右图所示 出出栈栈 进栈进栈 栈顶栈顶 an . . . a2 栈栈底底 a1 栈栈的示意的示意图图中国科大数据结构3.1 栈3.1.2 3.1.2 栈的顺序存储结构栈的顺序存储结构p定义：顺序栈（即栈的顺序存储结构）：是利用一组地址连续的存定义：顺序栈（即栈的顺序存储结构）：是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针储单元依次存放自栈底到栈顶的数据元素，同时附设指针toptop指示指示栈顶元素在顺序栈中的位置。

栈顶元素在顺序栈中的位置pC C语言描述语言描述typedef struct stack_tag typedef struct stack_tag elemtype *elem; elemtype *elem; / /指向存放数据元素的内存块指向存放数据元素的内存块 int top; int top; / /栈顶标识，栈顶标识，elemtopelemtop是栈顶元素是栈顶元素 int size; int size; / /栈的容量栈的容量 SQSTACK; SQSTACK;p图形表示图形表示topbottomtopbottomtopbottomAABCDE栈的顺序存储结构示意图栈的顺序存储结构示意图 中国科大数据结构3.1 栈1.初始化栈初始化栈intint InitSqstack(SQSTACKInitSqstack(SQSTACK *S, *S, intint n) n) / /初始化顺序栈，栈的容量是初始化顺序栈，栈的容量是n n成功则返回成功则返回1 1，否则返回，否则返回0 0 S- S-elemelem=(=(elemtypeelemtype *) *)malloc(nmalloc(n* *sizeof(elemtypesizeof(elemtype); ); / /为数据元素分配内存为数据元素分配内存 if (S-if (S-elemelem=NULL) return 0; =NULL) return 0; / /初始化失败初始化失败 S-size=n; S-size=n; / /设置栈的容量设置栈的容量 S-top=-1; S-top=-1; / /设置栈为空栈设置栈为空栈 return 1;return 1; 2.2.销毁栈销毁栈void void DestroySqstack(SQSTACKDestroySqstack(SQSTACK *S) *S) / /释放栈所占有的内存释放栈所占有的内存 free(Sfree(S-elemelem); ); / /释放内存，并设置为释放内存，并设置为NULLNULL S- S-elemelem=NULL;=NULL; S-top=-1; S-top=-1; / /将其他成员设置成安全值将其他成员设置成安全值 S-size=0;S-size=0; 中国科大数据结构3.1 栈3.入栈入栈int Push(SQSTACK *S,elemtype e) /在栈顶一端插入数据元素在栈顶一端插入数据元素e，操作成功，则返回，操作成功，则返回1，否则返回，否则返回0 if (IsSqstackFull(*S)return 0; /栈满，操作失败栈满，操作失败 S-top+; /top增增1 S-elemS-top=e; /将将e赋值成新的栈顶赋值成新的栈顶 return 1;4.出栈出栈int Pop(SQSTACK *S,elemtype *e) /获取栈顶数据元素，并删除栈顶。

操作成功，则返回获取栈顶数据元素，并删除栈顶操作成功，则返回1，否则返回，否则返回0 if (IsSqstackEmpty(*S) return 0; /如果栈空，操作失败如果栈空，操作失败 *e=S-elemS-top; /获取栈顶元素获取栈顶元素 S-top-; /删除栈顶删除栈顶 return 1;中国科大数据结构3.1 栈5.判断栈空、栈满判断栈空、栈满int IsSqstackEmpty(SQSTACK S) /如果栈空，则返回如果栈空，则返回1，否则返回，否则返回0 return =-1; /top是栈顶标识，是是栈顶标识，是-1时表示空栈时表示空栈int IsSqstackFull(SQSTACK S) /如果栈满，则返回如果栈满，则返回1，否则返回，否则返回0 return =S.size-1; /top作为作为elem的下标，其最大值是的下标，其最大值是size-1 中国科大数据结构3.1 栈3.1.3 栈的链式存储结构栈的链式存储结构 data next S 栈顶栈顶 栈底栈底 链栈示意图链栈示意图 中国科大数据结构3.2 栈的应用举例3.2.1 数制转换数制转换十进制数十进制数N和其他和其他d进制数的转换是计算机实现计算的基本问进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个是辗转相除法：题，其解决方法很多，其中一个是辗转相除法： N = ( N div d ) d + N mod d （其中：（其中：div为整除运算，为整除运算，mod为求余运算）为求余运算）由于计算过程是从低位到高位顺序产生八进制数的各个数由于计算过程是从低位到高位顺序产生八进制数的各个数位，而输出应从高位到低位进行，恰好和计算过程相反。

因此，若位，而输出应从高位到低位进行，恰好和计算过程相反因此，若计算过程中得到八进制数的各位顺序进栈，则按出栈序列打印输出计算过程中得到八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数的即为与输入对应的八进制数 例如：例如：(1348)10(2504)8，其运算过程如下：，其运算过程如下：NN div 8 N mod 8 1348 / 168 余余 4 168 / 21 余余 0 21 / 2 余余 5 2 / 0 余余 2中国科大数据结构3.2 栈的应用举例p算法如下：算法如下： 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); /conversion中国科大数据结构3.2 栈的应用举例3.2.2 迷宫路径求解迷宫路径求解【任【任务务描述】描述】给给定某个迷定某个迷宫宫的布局及其入口和出口的坐的布局及其入口和出口的坐标标（如（如图图3_9所示，注所示，注意横坐意横坐标标是从左向右的，但是是从左向右的，但是纵纵坐坐标标是从上向下的），迷是从上向下的），迷宫宫中空白的地方中空白的地方可以走，阴影的部分表示可以走，阴影的部分表示墙墙壁，走不通。

壁，走不通设计设计算法找出从入口到出口的所算法找出从入口到出口的所有路径需要解决有路径需要解决2个个问题问题：迷宫在计算机中如何表示迷宫在计算机中如何表示 int maze 12= 1,1,1,1,1,1,1,1,1,1,1,1, 1,0,0,0,0,0,1,0,0,1,1,1, 1,0,1,0,1,0,1,0,1,1,1,1, 1,0,1,0,0,0,1,0,1,1,1,1, 1,0,1,1,1,1,1,0,1,1,1,1, 1,0,0,0,0,0,0,0,0,0,0,1, 1,1,1,1,1,1,1,1,1,1,1,1 ;如何探索从入口到达出口的所有路径如何探索从入口到达出口的所有路径 深度优先探索深度优先探索+回溯：从当前位置出发，向四个方向探索，如果发现某方回溯：从当前位置出发，向四个方向探索，如果发现某方向的相邻位置可走，则走过去，将那个位置当作当前位置继续探索这时向的相邻位置可走，则走过去，将那个位置当作当前位置继续探索这时需要将原当前位置保存在栈中如果四个方向都走不通，则退回到出发点需要将原当前位置保存在栈中如果四个方向都走不通，则退回到出发点（栈顶中的位置）走过的地方要打上（栈顶中的位置）。

走过的地方要打上“已走标记已走标记”，回退时要将，回退时要将“已走已走”标记清除标记清除中国科大数据结构3.2 栈的应用举例typedef struct int x,y; /位置坐标位置坐标 int v; /探索方向探索方向 elemtype;int movex5=0,0,1,0,-1;int movey5=0,-1,0,1,0;#define M 27#define N 25#define MAXSIZE 200算法：算法：void go(int mazeMN ,int x0,int y0 ,int xx ,int yy) /找出找出maze中从入口中从入口(x,y)到出口到出口(xx,yy)的所有的所有路径路径 int x,y,x1,y1,v; SQSTACK s; /存放探索路径的栈存放探索路径的栈 elemtype e; InitSqstack(&s,MAXSIZE); /初始化栈初始化栈中国科大数据结构3.2 栈的应用举例 =x0; =y0; =0; Push(&s,e); /将入口入栈，探索方向是将入口入栈，探索方向是0，准备探索，准备探索 mazey0 x0=2;/打上已走标记打上已走标记 while(!IsSqstackEmpty(s) /如果栈未空，探索没有结束如果栈未空，探索没有结束 Pop(&s,&e); x=; y=; /弹出栈顶，作为当前位置弹出栈顶，作为当前位置 v=e.v+1; /探索新的方向探索新的方向 0) /这次出栈是回退操作，清除原探索位置的这次出栈是回退操作，清除原探索位置的已走已走标记标记 =0; while(v=4) /*按照顺时针顺序探索按照顺时针顺序探索4个方向个方向*/ x1=x+movexv; y1=y+moveyv; /获取当前位置获取当前位置(x,y)v方向的相邻位置坐标方向的相邻位置坐标(x1,y1) if (x1=xx&y1=yy) /遇到出口遇到出口 输出存放在输出存放在s中的路径中的路径 /*这条指令不是这条指令不是C语句语句*/ V+; /换一个方向继续探索换一个方向继续探索 while(v0&x10&y1elem=(elemtype *)malloc(n+1)*sizeof(elemtype); if(q-elem=NULL)return 0; /操作失操作失败败 q-front=q-rear=0; /队队首指首指针针、队队尾指尾指针针都都归归零零 q-size=n+1; /设设置容量置容量 return 1; 中国科大数据结构 队列2.销毁队列销毁队列void DestroySueue(SUEUE *q) /销毁队列销毁队列 free(q。