陈海明 副教授 信息学院 计算机系 http://www.chenhaiming.cn 电子信息类非计算机专业选修课 程序设计实践 陈海明 副教授 信息学院 计算机系 http://www.chenhaiming.cn

数据结构 线性表 顺序表 链 表 栈 线性结构 顺序表 队列 链 表 顺序表 链 表 任意位置 插入和删除 顶部插入 顶部删除 入栈 出栈 链 表 线性结构 顺序表 顶部插入 顶部删除 入栈 出栈 链 表 顺序表 尾部插入 头部删除 入队列 出队列 链 表

队列 问题1：队作为一种限定性线表，其运算限制是什么？ 先进先出（FIFO） 问题2：若进队顺序为1234，能否得到3142的出队顺序？ 队头 队尾 队尾（rear）：进行插入操作的一端。 队头（front)：进行删除操作的一端。 1 2 先进先出（FIFO） 3 问题2：若进队顺序为1234，能否得到3142的出队顺序？

队列 问题3：队列的假溢出指什么？ rear=(rear+1)%MSIZE; front=(front+1)%MSIZE 空队 有3个元素 一般情况

队列 问题4：循环队列会有问题吗？ 一般情况

循环队列

循环队列 1.计算元素个数num 2.少用一个元素空间

循环队列 #define MAXSIZE 100 typedef struct{ ElemType *base; int front; int rear; }cycleQueue; initQueue(cycleQueue *q){ q->base=(ElemType *) malloc(MAXSIZE*sizeof(ElemType)); if (!q->base) exit(0); q->front=q->rear=0; } EnQueue(cycleQueue *q, ElemType e){ if ((q->rear+1) % MAXSIZE == q->front) return -1; q->base[q->rear] =e; q->rear=(q->rear+1) % MAXSIZE; DeQueue(cycleQueue *q, ElemType *e){ if (q->front == q->rear) return -1; *e=q->base[q->front]; q->front=(q->front+1) % MAXSIZE;

案例分析（栈和队列） 迷宫问题：心理学家把一只老鼠从无顶盖的大盒子的入口处赶进迷宫，迷宫中很多墙壁，对前进造成障碍。在唯一的出口处放置了一块奶酪，吸引老鼠寻找通路以到达出口。

案例分析（栈和队列） 1、假设迷宫为m行n列，则设计maze[m+2][n+2]来表示迷宫 2、入口maze[1][1],出口maze[m][n] 3、maze[i][j]=0或1；0表示通路，1表示不通

案例分析（栈和队列） (x,y) (x,y+1) (x-1,y) (x-1,y+1) (x-1,y-1) (x,y-1) (x+1,y-1)

案例分析（栈和队列） typedef struct{ int x,y; }item; item move[8]; 从某点（x, y）按某方向序号d(0<=d<=7)到达新点（i, j）的方式： i=x+move[d].x; j=y+move[d].y;

案例分析（栈） //栈元素定义 typedef struct { int x,y,d; //横纵坐标及行走方向 }datatype; datatype temp; 入栈顺序

案例分析（栈） //算法思路 （1）栈初始化 （2）将入口坐标（1,1）及到达该点的方向（-1）入栈 （3）while(栈非空) {将栈顶三元组赋值给(x,y,d); 出栈； 求出下一个要试探的方向d++； while(还有剩余试探方向时) { 子算法 } }

案例分析（栈） while(还有剩余试探方向时) { if(d方向可走） 则{ (x,y,d)入栈； 求新点坐标（i,j）; 将新点(i,j)切换为当前点(x,y) if(x,y)==(m,n)结束 else 重置d=0 } else d++;

案例分析（栈） temp.x=1;temp.y=1;temp.d=-1; Push(s,temp); //入口点坐标及方向入栈 while(!Empty(s)) { Pop(s,&temp); x=temp.x;y=temp.y;d=temp.d++; //求下一个试探方向 while(d<8) //还有剩余试探方向时 }

案例分析（栈） while(d<8) //还有剩余试探方向时 { i=x+move[d].x; j=y+move[d].y; //求新点坐标 if(maze[i][j]==0) //若路通 { temp.d=d; Push(s,temp); //坐标及方向入栈 x=i;y=j;maze[x][y]=-1; //到达新点 if(x==m&&y==n) return 1; //迷宫有路 else d=0; //重置0 } else d++;

案例分析（队列） 区别：存储搜索路径的方法？ //结构数组sq[num]作为队列的存储空间 typedef struct { int x,y; //到达点的坐标 int pre; //前驱点在sq中的坐标 }SqType; SqType sq[num]; int front,rear;

案例分析（队列） front=rear=0; sq[0].x=1; sq[0].y=1; sq[0].pre=-1; //入口点入队 maze[1,1]=-1; while(front<rear) //队非空 { x=sq[front].x; y=sq[front].y; for(d=0;d<8;d++) { i=x+move[d].x; j=x+move[d].y; if(maze[i][j]==0) {rear++; sq[rear].x=i; sq[rear].y=j;sq[rear].pre=front;maze[i][j]=-1;} if(i==m&&j==n) {printpath(sq,rear); //打印迷宫 restore(maze); //恢复迷宫 return 1; } front++; return 0;