数据结构实例精讲：队列
数据结构实例精讲：队列
栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，故又称它们为运算受限的线性表。
3.3 队列的定义和基本运算实现
对于队列我们并不陌生，商场、银行的柜台前需要排队，餐厅的收款机旁也需要排队。队列也是一种特殊的线性表，是一种只允许在表的一端进行插入操作而在另一端进行删除操作的线性表。表中允许进行插入操作的一端称为队尾，允许进行删除操作的一端称为队头。队头和队尾分别由队头指示器（或称队头指针）和队尾指示器（或称队尾指针）指示。当队列中没有数据元素时，称之为空队列。队列的插入操作通常称为进队列或入队列，队列的删除操作通常称为退队列或出队列。
根据队列的定义，每次进队列的数据元素都放在原当前队尾之后而成为新的队尾元素，每次出队列的数据元素都是原队头元素。这样，最先入队列的数据元素总是最先出队列，因此，队列具有“先进先出”（FIFO：First In First Out）的特性。图3-4是队列及其操作的示意图。
图3-4 队列及其操作的示意图
队列的基本操作有：
（1）InitQueue（Q）：队列初始化。构造一个空队列。
（2）QueueEmpty（Q）：判队空。若队列Q为空，则返回True，否则返回False。
（3）EnQueue（Q，x）：入队。若队列Q非满，则将元素X插入Q的队尾。
（4）DeQueue（Q）：出队。若队列Q非空，则删去的队头元素。
（5）GetHead（Q）：读取队头元素。若队列Q非空，则返回队头元素，但不改变队列Q的状态。
队列可以用顺序存储结构存储，也可以用链式存储结构存储。
1．循环队列
和顺序栈相类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的数据元素之外，尚需附设两个指针front和rear分别指示队头元素和队尾元素的位置。可以定义顺序队列结构如下：
#define MAXNUM ** ; // 队列能存放的最大元素数
typedef struct {
QElemType data[MAXNUM];
int front;
int rear；
} SqQueue ;
其中，QElemType为队列的数据元素类型，data[MAXNUM]为一维数组，用于存放队列的结点元素。为了操作方便，我们约定初始化建空队列时，队头指针front和队尾指针rear 都置为0，即front = rear = 0。当新元素插入队列时，尾指针随之增1；当删除队头元素时，头指针随之增1。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。
图3-5是一个顺序存储结构队列的动态示意图，假设为队列分配的最大空间为5，（a）表示一个空队列；（b）表示插入一个数据元素A、B、C以后的状态；（c）表示删除数据元素A以后的状态；（d）表示插入数据元素D、E以后的状态；（e）表示删除数据元素B、C以后的状态。
图3-5 顺序队列的动态示意图
顺序队列在进行入队操作时，会产生假溢出现象，如图3-5（d）和（e）所示。由于当前为队列分配的最大空间MAXNUM为5，此时rear == MAXNUM，表示队列已满，若再有元素进队列就会溢出。这种溢出就是假溢出，因为实际上队列中还有可用空间。一个很自然的想法是让队列首尾相连，即data[0]和data[MAXNUM-1]连接起来，构成一个循环队列，这样，当队列的最后一个单元已占用时（rear = MAXNUM），只要第一个单元是空的就可以加入欲入队的元素。
在循环队列中需要解决两个问题：①队头指针和队尾指针的后移；②如何判断队列的空和满。
【实例3-8】循环队列的基本操作实现。
定义一个循环队列，并实现其5个基本操作：初始化队列、判队列空、入队、出队、取队头元素。
（1）问题分析。
循环队列的初始化状态（队列为空）是front = rear = 0，一维数组data下标值范围在0与MAXNUM –1之间。往队列中加入一个元素时，rear按顺时针方向前进一个位置（rear=rear+1）；删除一个元素时，front按顺时针方向前进一个位置（front=front+1）。当front或rear大于队列的最大长度MAXNUM-1时，相应的值置为0。
即对于队头指针front，它的后移操作是
if (front+1>=MAXNUM) front=0;
else front=front+1;
等价的语句形式为front=(front+1)%MAXNUM；
同样，对于队尾指针rear，它的后移操作的等价语句形式为rear=(rear+1)%MAXNUM；
当队列空和满时都有front = rear。为了区别循环队列空和满两种状态，习惯上采用保留一个空闲位置来区别，即约定：若front == rear，队列为空，不能进行出队操作；若rear+1==front（更精确表示为(Q.rear+1)%MAXNUM == Q.front），表示如果再向队列中插入一个元素队列将满，此时就认为队列已满，不能进行入队操作。
（2）源程序。
#include
using namespace std;
typedef int QElemType;
#define MAXQSize 100 // 最大队列长度
typedef struct{
QElemType *base;
int front, rear;
} SqQueue;
void InitQueue(SqQueue &Q) // 队列初始化
{
Q.base=new QElemType [MAXQSize];
if(!Q.base)
{
cout<<"存储分配失败！"< exit(1); } Q.front=Q.rear=0; } void DestroyQueue(SqQueue &Q) // 销毁队列，释放空间 { Q.front=Q.rear=0; delete [] Q.base; } bool QueueEmpty(SqQueue Q) // 判队列空 { return Q.front==Q.rear; } void EnQueue(SqQueue &Q, QElemType e) // 入队 { if((Q.rear+1)%MAXQSize == Q.front) { cout<<"队列已满，不能入队！"< exit(1); } Q.base[Q.rear] = e; Q.rear = (Q.rear+1) % MAXQSize; } void DeQueue(SqQueue &Q) // 出队 { if(Q.front==Q.rear) { cout<<"队列为空!"< exit(1); } Q.front=(Q.front+1)% MAXQSize; } QElemType GetHead(SqQueue Q) // 取队头元素 { if (Q.front==Q.rear) { cout<<"队列为空!"< exit(1); } return Q.base[Q.front]; } int main() { SqQueue q; InitQueue(q); for(int i=1; i <=10; i++ ) EnQueue(q,i); while( !QueueEmpty(q)) { cout << GetHead(q) << " "; // 10 9 8 7 6 5 4 3 2 1 DeQueue(q); } cout< DestroyQueue(q); return 0; } 2．链队列 单链表可以作为队列的链式存储结构。由于一个队列需要两个分别指向队头和队尾的指针才能唯一确定。在链队列中，将队头指针指向单链表的第一个结点或头结点，而将队尾指针指向单链表的最后一个结点。为方便处理，通常在单链表中设置一个头结点。这样，一个空队列如图3-6（a）所示，队列中有一个元素的情况如图3-6（b）所示。 （a ） （b ） 图3-6 链队列示意图 【实例3-9】链队列的基本操作实现。 定义一个链队列，并实现其5个基本操作：初始化队列、判队列空、入队、出队、取队头元素。 #include void InitQueue(LinkQueue &Q) // 队列初始化 { Q.front=Q.rear=new QNode; if (! Q.front) { cout<<"存储分配失败！"< exit(1); } Q.front->next=NULL; } void DestroyQueue(LinkQueue &Q) // 销毁队列，释放空间 { while (Q.front) { Q.rear = Q.front->next; Q.Front Q.rear delete Q.front ; Q.front = Q.rear; } Q.front=Q.rear=NULL; } bool QueueEmpty(LinkQueue Q) // 判队列空 { return Q.front==Q.rear; } void EnQueue(LinkQueue &Q, QElemType e) // 入队 { QueuePtr p; p=new QNode; if(!p) { cout<<"存储分配失败！"< exit(1); } p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; } void DeQueue(LinkQueue &Q) // 出队 { QueuePtr p; if(Q.front==Q.rear) { cout<<"队列为空!"< exit(1); } p=Q.front->next; Q.front->next= p->next; // 将队头结点从链上摘下 if(Q.rear==p) // 原队中只有一个结点，删去后队列变空，需修改队尾指针Q.rear=Q.front; delete p; } QElemType GetHead(LinkQueue Q) // 取队头元素 { if (Q.front==Q.rear) { cout<<"队列为空!"< exit(1); } return Q.front->next->data; } int main() { LinkQueue q; InitQueue(q); for(int i=1; i <=10; i++ ) EnQueue(q,i); while( !QueueEmpty(q)) { cout << GetHead(q) << " "; // 10 9 8 7 6 5 4 3 2 1 DeQueue(q); } cout< DestroyQueue(q); return 0; } 3.4 队列的应用 队列的应用也很广泛，它可以用于各种应用系统中的事件规划、事件模拟，例如银行和商场的顾客队列；计算机操作系统中的各种资源请求排队和各种数据缓冲区的先进先出管理也用队列来实现，如操作系统用队列来处理打印作业的调度。 下面我们主要介绍队列在搜索问题中的应用实例。 1．广度优先搜索 在使用计算机求解的问题中，有许多问题是无法用数学公式进行计算推导且找出答案的。这样的问题往往需要程序员根据问题所给定的一些条件，在问题的所有可能解中用某种方式找出问题的解来，这就是所谓的搜索法或搜索技术。 根据搜索问题所给定的条件，从一个结点出发，可以生成一个或多个新的结点，这个过程通常称为扩展。结点之间的关系一般可以表示成一棵树，它被称为解答树。搜索算法的搜索过程实际上就是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的结点的过程。 广度优先搜索（BFS，Breadth First Search）也称为宽度优先搜索，它是一种先生成的结点先扩展的策略。 在广度优先搜索算法中，解答树上结点的扩展是按它们在树中的层次进行的。首先生成第一层结点，同时检查目标结点是否在所生成的结点中，如果不在，则将所有的第一层结点逐一扩展，得到第二层结点，并检查第二层结点是否包含目标结点，……，对层次为n+1的任一结点进行扩展之前，必须先考虑层次完层次为n的结点的每种可能的状态。因此，对于同一层结点来说，求解问题的价值是相同的，可以按任意顺序来扩展它们。通常采用的原则是先生成的结点先扩展。 为了便于进行搜索，要设置一个表存储所有的结点。由于在广度优先搜索算法中，要满足先生成的结点先扩展的原则，所以存储结点的表一般采用队列这种数据结构。 广度优先搜索算法的搜索步骤一般是： （1）从队列头取出一个结点，检查它按照扩展规则是否能够扩展，如果能则产生一个新结点。 （2）检查新生成的结点，看它是否已在队列中存在，如果新结点已经在队列中出现过，就放弃这个结点，然后回到第（1）步。否则，如果新结点未曾在队列中出现过，则将它加入到队列尾。 （3）检查新结点是否目标结点。如果新结点是目标结点，则搜索成功，程序结束；若新结点不是目标结点，则回到第（1）步，再从队列头取出结点进行扩展。 最终可能产生两种结果：找到目标结点，或扩展完所有结点而没有找到目标结点。 2．广度优先搜索实例 【实例3-10】用队列解决迷宫问题。 采用队列作为数据结构进行广度优先搜索，解决迷宫问题。 （1）问题分析。 首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则，将初始位置放入队列中，按上面介绍的广度优先搜索算法进行搜索。具体步骤描述为： ①从队列头取出一个结点，查看当前位置是否为出口，若是，已找到迷宫出口，搜索成功，退出。 ②对当前位置的东、南、西和北四个方向进行下一个位置的探索，如果下个位置无障碍且以前未被搜索过，则将该位置加入到队列中。为防止搜索重复出现，将加入到搜索队列中的位置标记为“2”，同时保留搜索痕迹。 ③重复执行①、②歩，直到队列为空。 搜索结束后，若队列为空，则说明所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，表明不存在从入口到出口的路径。若找到了路径，则一定是最短路径。 （2）函数程序代码。 void MazePath(int maze[M+2][N+2],PosType start, PosType end,int m,int n) // 若迷宫maze[m][n]中存在从入口start到出口end的通道，则输出解信息 { int nextto[4][2]={{0,1},{1,0},{0,-1},{-1,0}},i; PosType curpos,nextpos; int parent[M*N+1]; // 保存每个位置在访问过程中的上一个位置的情况 SqQueue Q; InitQueue(Q); curpos.row =start.row ; curpos.col =start.col ; if(maze[curpos.row][curpos.col]==1) { cout<<"此迷宫无解\n\n"; return ; } maze[curpos.row][curpos.col]=2; // 记下当前位置被访问过 parent[(curpos.row-1)*n+curpos.col]=-1; EnQueue(Q,curpos); // 初始位置入队 while (!QueueEmpty(Q)) { curpos=GetHead(Q); DeQueue(Q); // 从队头取一个位置作为当前位置 if((curpos.row==end.row )&&(curpos.col==end.col)) break; for (i=0;i<4;i++) // 从4个方向探索下一个位置 { nextpos.row =curpos.row +nextto[i][0]; nextpos.col =curpos.col +nextto[i][1]; if (maze[nextpos.row][nextpos.col]==0) // 下个位置可通过且未被访问 { maze[nextpos.row][nextpos.col]=2; // 记下下个位置已被搜索到 parent[(nextpos.row-1)*n+nextpos.col]=(curpos.row-1)*n+curpos.col; EnQueue(Q,nextpos); // 将下个位置加入到队列，等待访问} } } if(curpos.row==end.row && curpos.col==end.col) { cout<<"迷宫路径为："; cout<<"("< maze[curpos.row][curpos.col]=3; while(parent[(curpos.row-1)*n+curpos.col]!=-1) { i=parent[(curpos.row-1)*n+curpos.col]; if (i%n!=0) { curpos.row =i/n+1; curpos.col =i%n; } else { curpos.row =i/n; curpos.col =n; } cout<<"("< maze[curpos.row][curpos.col]=3; } cout< cout<<"迷宫通路(用☆表示)如下所示："< OutputMaze(maze,m,n); } else { cout<<"此迷宫无解！"< } } （3）源程序。 #include #include using namespace std; // 数据类型定义 #define M 15 // 迷宫的最大行数 #define N 15 // 迷宫的最大列数 typedef struct { int row; // row表示“行”号 int col; // col表示“列”号 }PosType; // 位置的元素类型 #define MAXQSize 512 // 最大队列长度 typedef PosType QElemType; typedef struct{ QElemType *base; int front, rear; } SqQueue; // 函数原型说明 void InitQueue(SqQueue &Q); // 队列初始化 void DestroyQueue(SqQueue &Q) ; // 销毁队列，释放空间bool QueueEmpty(SqQueue Q) ; // 判队列空 void EnQueue(SqQueue &Q, QElemType e); // 入队 void DeQueue(SqQueue &Q); // 出队 QElemType GetHead(SqQueue Q) ; // 取队头元素 void MazePath(int maze[M+2][N+2],PosType start, PosType end,int m,int n) ; void OutputMaze(int maze[M+2][N+2],int x,int y); // 显示迷宫 int main() { PosType start,end; int x,y; char sele; int maze[M+2][N+2]; do{ cout<<"迷宫设置："< do { cout<<"请输入行数X(x<="< cout<<"请输入列数Y(y<="< if(x<1 || x>M||y<1 || y>N) cout<<"输入行数或列数错误!"< } while(x<1 || x>M || y<1 || y>N); for(int i=1;i<=x;i++) // 采用随机数初始化迷宫 { maze[i][0]=maze[i][y+1]=1; maze[0][i]=maze[y+1][i]=1; for(int j=1;j<=y;j++) maze[i][j]=rand()%2; } maze[0][0]=maze[0][y+1]=maze[y+1][0]=maze[y+1][y+1]=1; cout<<"所建的迷宫(■表示墙)如下:"< OutputMaze(maze,x,y); // 显示所创建的迷宫 do { cout<<"请输入入口的行坐标（1～"< cin>>start.row>>start.col; if(start.row>x || start.col>y) cout<<"输入错误!"< } while(start.row>x || start.col>y); do { cout<<"请输入出口的行坐标（1～"< cin>>end.row>>end.col; if(end.row>x || end.col>y) cout<<"输入错误!"< } while(end.row>x || end.col>y); MazePath(maze,start,end,x,y); cout<<"继续吗？Y/N "; cin>>sele; if ((sele=='N'||sele=='n')) break; } while(1); return 0; } void MazePath(int maze[M+2][N+2],PosType start, PosType end,int m,int n) { int nextto[4][2]={{0,1},{1,0},{0,-1},{-1,0}},i; PosType curpos,nextpos; int parent[M*N+1]; // 保存每个位置在访问过程中的上一个位置的情况 SqQueue Q; InitQueue(Q); curpos.row =start.row ; curpos.col =start.col ; if(maze[curpos.row][curpos.col]==1) { cout<<"此迷宫无解\n\n"; return ; } maze[curpos.row][curpos.col]=2; // 记下当前位置被访问过 parent[(curpos.row-1)*n+curpos.col]=-1; EnQueue(Q,curpos); // 初始位置入队 while (!QueueEmpty(Q)) { curpos=GetHead(Q); DeQueue(Q); // 从队头取一个位置作为当前位置 if((curpos.row==end.row )&&(curpos.col==end.col)) break; for (i=0;i<4;i++) // 从4个方向探索下一个位置 { nextpos.row =curpos.row +nextto[i][0]; nextpos.col =curpos.col +nextto[i][1]; if (maze[nextpos.row][nextpos.col]==0) // 下个位置可以通过且未被访问过 { maze[nextpos.row][nextpos.col]=2; // 记下下个位置已被搜索到 parent[(nextpos.row-1)*n+nextpos.col]=(curpos.row-1)*n+curpos.col; EnQueue(Q,nextpos); // 将下个位置加入到队列，等待访问 } } } if(curpos.row==end.row && curpos.col==end.col) { cout<<"迷宫路径为："; cout<<"("< maze[curpos.row][curpos.col]=3; while(parent[(curpos.row-1)*n+curpos.col]!=-1) { i=parent[(curpos.row-1)*n+curpos.col]; if (i%n!=0) { curpos.row =i/n+1; curpos.col =i%n; } else { curpos.row =i/n; curpos.col =n; } cout<<"("< maze[curpos.row][curpos.col]=3; } cout< cout<<"迷宫通路(用☆表示)如下所示："< OutputMaze(maze,m,n); } else { cout<<"此迷宫无解！"< } } void OutputMaze(int maze[M+2][N+2],int x,int y) { int i,j; cout<<" Y "; for(j=1;j cout< cout< for(i=0;i<=x+1;i++) { if (i==0) cout<<" X"; else if (i==x+1) cout<<" "; else cout< for(j=0;j<=y+1;j++) { if (maze[i][j]==0 || maze[i][j]==2) cout<<"□"; else if (maze[i][j]==1) cout<<"■"; else if (maze[i][j]==3) cout<<"☆"; } cout< } } void InitQueue(SqQueue &Q) // 队列初始化 { Q.base=new QElemType [MAXQSize]; if(!Q.base) { cout<<"存储分配失败！"< exit(1); } Q.front=Q.rear=0; } void DestroyQueue(SqQueue &Q) // 销毁队列，释放空间{ Q.front=Q.rear=0; delete [] Q.base; } bool QueueEmpty(SqQueue Q) // 判队列空 { return Q.front==Q.rear; } void EnQueue(SqQueue &Q, QElemType e) // 入队 { if((Q.rear+1)%MAXQSize == Q.front) { cout<<"队列已满，不能入队！"< exit(1); } Q.base[Q.rear] = e; Q.rear = (Q.rear+1) % MAXQSize; } void DeQueue(SqQueue &Q) // 出队 { if(Q.front==Q.rear) { cout<<"队列为空!"< exit(1); } Q.front=(Q.front+1)% MAXQSize; } QElemType GetHead(SqQueue Q) // 取队头元素 { if (Q.front==Q.rear) { cout<<"队列为空!"< exit(1); } return Q.base[Q.front]; } 【实例3-11】细胞个数。 一个矩形阵列由数字0到9组成，数字1到9代表细胞，细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞。求给定矩形阵列的细胞个数。 例如，阵列 0 2 3 4 5 0 0 0 6 7 1 0 3 4 5 6 0 5 0 0 2 0 4 5 6 0 0 6 7 1 0 0 0 0 0 0 0 0 8 9 有4个细胞。 （1）问题分析。 用一个二维数组a来保存矩形阵列，用num记录找到的细胞数。寻找细胞数的步骤为： ①沿矩阵从上到下，从左到右的顺序，找到遇到的第一个细胞（a[i][j]!=0）。 ②将当前细胞的位置（i，j）入队q。 ③将q队列的队头出队，得到一个当前位置（i，j），将该位置处的数组元素a[i][j]置为0，表示该处的细胞已被处理，以后不再重复搜索。并沿其上、下、左、右四个方向上搜索细胞，将找到的细胞的位置入队。 ④重复执行③，直至q队列为空，则此时找出了一个大细胞，num++。 ⑤重复①，直至矩阵中找不到a[i][j]!=0的元素。 ⑥返回找到的细胞数num。 （2）函数程序代码。 struct PosType { int x; int y; }; int SearchCell(int **a,int m,int n) // 在数阵a[m][n]中搜索细胞个数 { int offset[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int i, j, x,y,num; PosType curpos,nextpos; SqQueue q; InitQueue(q); num=0; for(i = 0; i < m; ++i) for(j = 0; j < n; ++j) if(a[i][j] > 0) { curpos.x =i; curpos.y =j; EnQueue(q,curpos); // 遇到的第一个细胞入队 while(!QueueEmpty(q)) { curpos = GetHead(q); DeQueue(q); a[curpos.x][curpos.y] = 0; for(int k = 0; k < 4; ++k) // 沿细胞的上下左右四个方向搜索细胞 { x = curpos.x + offset[k][0]; y = curpos.y + offset[k][1]; if(x >= 0 && x < m && y >= 0 && y < n && a[x][y] > 0) { nextpos.x =x; nextpos.y =y; EnQueue(q,nextpos); } } } ++num; } return num; } （3）源程序。 #include using namespace std; struct PosType { int x; int y; }; #define MAXQSize 100 // 最大队列长度 typedef PosType QElemType; typedef struct{ QElemType *base; int front, rear; } SqQueue; void InitQueue(SqQueue &Q) // 队列初始化 { Q.base=new QElemType [MAXQSize]; if(!Q.base) { cout<<"存储分配失败！"< exit(1); } Q.front=Q.rear=0; } void DestroyQueue(SqQueue &Q) // 销毁队列，释放空间{ Q.front=Q.rear=0; delete [] Q.base; } bool QueueEmpty(SqQueue Q) // 判队列空 { return Q.front==Q.rear; } void EnQueue(SqQueue &Q, QElemType e) // 入队 { if((Q.rear+1)%MAXQSize == Q.front) { cout<<"队列已满，不能入队！"< exit(1); } Q.base[Q.rear] = e; Q.rear = (Q.rear+1) % MAXQSize; } void DeQueue(SqQueue &Q) // 出队 { if(Q.front==Q.rear) { cout<<"队列为空!"< exit(1); } Q.front=(Q.front+1)% MAXQSize; } QElemType GetHead(SqQueue Q) // 取队头元素 { if (Q.front==Q.rear) { cout<<"队列为空!"< exit(1); } return Q.base[Q.front]; } int SearchCell(int **a,int m,int n) // 在数阵a[m][n]中搜索细胞个数 { int offset[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int i, j, x,y,num; PosType curpos,nextpos; SqQueue q; InitQueue(q); num=0; for(i = 0; i < m; ++i) for(j = 0; j < n; ++j) if(a[i][j] > 0) { curpos.x =i; curpos.y =j; EnQueue(q,curpos); // 遇到的第一个细胞入队 while(!QueueEmpty(q)) { curpos = GetHead(q); DeQueue(q); a[curpos.x][curpos.y] = 0; for(int k = 0; k < 4; ++k) // 沿细胞的上下左右四个方向搜索细胞 { x = curpos.x + offset[k][0]; y = curpos.y + offset[k][1]; if(x >= 0 && x < m && y >= 0 && y < n && a[x][y] > 0) { nextpos.x =x; nextpos.y =y; EnQueue(q,nextpos); } } } ++num; } return num; } int main() { int m, n,i,j; cin >> m >> n; int **a = new int*[m]; for(i = 0; i < m; ++i) { a[i] = new int[n]; for(j = 0; j < n; ++j) { cin >> a[i][j]; } } cout < return 0; } 【实例3-12】奇怪的电梯。 在理工大学有一部很奇怪的电梯。大楼的每一层楼都可以停电梯，每层楼上均有一个数字。电梯只有2个按钮：上和下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：一楼上的数字为3，则按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。 编写一个程序，输入大楼的层数N（1≤N≤200）、每层上的数字Ki（1≤Ki≤N）以及X和Y（1≤X，Y≤N），输出从X层楼到Y层楼至少要按几次按钮，若无法到达，则输出-1。 （1）问题分析。 采用广度优先搜索算法来解决。例如，设电梯共5层，每层上的数字分别为3、3、1、2、5。从第1层到第5层至少按几次按钮？初始时，将“1”层加入搜索队列中，其按键次数为0。将队列中的“1”取出，由于第“1”层按上可以到第“4”层，按下按钮无效，因此将“4”层加入队列中，其按键次数为1（即从第1层到第4层按一次按钮）；再将队列中的“4”取出，由于第“4”层按上无效，按下可以到第“2”层，因此将“2”层加入队列中，其按键次数为2（即从第1层到第2层按2次按钮）；再将队列中的“2”取出，由于第“2”层按上可以到第“5”层，按下无效，因此将“5”层加入队列中，其按键次数为3（即从第1层到第5层按3次按钮）；…，此时得到了解。 程序中定义3个数组int a[201],c[201]={0},d[201]={0}; 其中： 数组a保存电梯各层的数字，数组c用于保存是否可以到达某层，如c[i]==1，表示可以到达第i层，c[i]==0，表示不能到达第i层，数组d用于保存到达某层所需的最少按键次数，如d[i]=x表示到达第i层至少按x次按钮。 初始时，将起始层x加入队列q。处理过程中，每次取出队头元素x，判断其按上和下按钮可以到达的层是否处理过（例如，向上的判断为if (c[x+a[x]]==0 && x+a[x]<=n)，没有处理过，则将其加入队列中，并置相应的层可达（c[x+a[x]]=1）、记录到达该层的按键次数（d[x+a[x]]=d[x]+1）；重复这一过程，直到搜索队列为空，结束处理。 处理结束后，若c[y]非零，则从x层到y层可到达，最少按键次数为d[y]。 （2）源程序。 #include using namespace std; typedef int QElemType; #define MAXQSize 1000 // 最大队列长度 typedef struct{ QElemType *base; int front, rear; } SqQueue; void InitQueue(SqQueue &Q) // 队列初始化 { Q.base=new QElemType [MAXQSize]; if(!Q.base) { cout<<"存储分配失败！"< exit(1); } Q.front=Q.rear=0; } void DestroyQueue(SqQueue &Q) // 销毁队列，释放空间{ Q.front=Q.rear=0; delete [] Q.base; } bool QueueEmpty(SqQueue Q) // 判队列空 { return Q.front==Q.rear; } void EnQueue(SqQueue &Q, QElemType e) // 入队 { if((Q.rear+1)%MAXQSize == Q.front) { cout<<"队列已满，不能入队！"< exit(1); } Q.base[Q.rear] = e; Q.rear = (Q.rear+1) % MAXQSize; } void DeQueue(SqQueue &Q) // 出队 { if(Q.front==Q.rear) { cout<<"队列为空!"< exit(1); } Q.front=(Q.front+1)% MAXQSize; } QElemType GetHead(SqQueue Q) // 取队头元素 { if (Q.front==Q.rear) { cout<<"队列为空!"< exit(1); } return Q.base[Q.front]; } int main() { int i,n,x,y; SqQueue q; int a[201],c[201]={0},d[201]={0}; cout<<"请输入楼层数："; cin>>n; cout<<"请依次输入每层电梯上的数字："< for (i=1;i<=n;i++) cin>>a[i]; cout<<"请输入从第X层到第Y层的数字X 和Y："; cin>>x>>y; InitQueue(q); // 搜索队列初始化 EnQueue(q,x); // 起始楼层号入队 c[x]=1; d[x]=0; while (!QueueEmpty(q)) // 搜索队列非空 { x=GetHead(q); DeQueue(q); // 队头元素出队 if (c[x+a[x]]==0 && x+a[x]<=n) // 按上按钮 { c[x+a[x]]=1; d[x+a[x]]=d[x]+1; EnQueue(q, x+a[x]); // 向上可达的楼层号入队} if (c[x-a[x]]==0 && x-a[x]>0) // 按下按钮 { c[x-a[x]]=1; d[x-a[x]]=d[x]+1; EnQueue(q, x-a[x]); // 向下可达的楼层号入队} } if (c[y]==0) cout<<-1< else cout< DestroyQueue(q); return 0; 实验二堆栈和队列 实验目的： 1.熟悉栈这种特殊线性结构的特性； 2.熟练并掌握栈在顺序存储结构和链表存储结构下的基本运算； 3.熟悉队列这种特殊线性结构的特性； 3.熟练掌握队列在链表存储结构下的基本运算。 实验原理： 堆栈顺序存储结构下的基本算法； 堆栈链式存储结构下的基本算法； 队列顺序存储结构下的基本算法；队列链式存储结构下的基本算法；实验内容： 3-18链式堆栈设计。要求 （1）用链式堆栈设计实现堆栈，堆栈的操作集合要求包括：初始化Stacklnitiate （S）, 非空否StackNotEmpty（S），入栈StackiPush（S,x）, 出栈StackPop （S,d）,取栈顶数据元素StackTop（S,d）; （2）设计一个主函数对链式堆栈进行测试。测试方法为：依次把数据元素1，2，3, 4，5 入栈，然后出栈并在屏幕上显示出栈的数据元素； （3）定义数据元素的数据类型为如下形式的结构体， Typedef struct { char taskName[10]; int taskNo; }DataType; 首先设计一个包含5个数据元素的测试数据，然后设计一个主函数对链式堆栈进行测试，测试方法为：依次吧5个数据元素入栈，然后出栈并在屏幕上显示出栈的数据元素。 3-19对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当 前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求： （1）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空； （2）编写一个主函数进行测试。 实验结果： 3-18 typedef struct snode { DataType data; struct snode *n ext; } LSNode; /* 初始化操作：*/ 贵州大学实验报告 学院：计信学院专业：网络工程班级：091班姓名XXX 学号XXXXXXXXX 实验组 5 实验时间2011.12.02 指导教师XXXXX 成绩 实验项目名称 队列的实现 实 验目的1．掌握队列的思想及其存储实现。2．掌握队列的常见算法的程序实现。 实验原理1.根据实验内容编程，上机调试、得出正确的运行程序。 2. 编译运行程序，观察运行情况和输出结果。 3. 写出实验报告（包括源程序和运行结果）。 实验内容 1．采用链式存储实现队列的初始化、入队、出队操作。 2．采用顺序存储实现循环队列的初始化、入队、出队操作。 3．在主函数中设计一个简单的菜单，分别测试上述算法。 实验数据及其步骤链式存储队列： #include 第3章栈和队列 一、选择题 1.栈结构通常采用的两种存储结构是（A ）。 A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2.设栈ST 用顺序存储结构表示，则栈ST 为空的条件是（ B ） A、ST.top-ST.base<>0 B、ST.top-ST.base==0 C、ST.top-ST.base<>n D、ST.top-ST.base==n 3.向一个栈顶指针为HS 的链栈中插入一个s 结点时，则执行（ C ） A、HS->next=s; B、s->next=HS->next；HS->next=s; C、s->next=HS；HS=s; D、s->next=HS；HS=HS->next; 4.从一个栈顶指针为HS 的链栈中删除一个结点，用x 保存被删除结点的值，则执行（ C） A 、x=HS；HS=HS->next; B 、HS=HS->next；x=HS->data; C 、x=HS->data；HS=HS->next; D 、s->next=Hs；Hs=HS->next; 5.表达式a*(b+c)-d 的后缀表达式为（ B ） A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6.中缀表达式A-（B+C/D）*E 的后缀形式是（ D ） A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*- 7.一个队列的入列序列是1，2，3，4，则队列的输出序列是（ B ） A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 8.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为空的条件是（） A、Q.rear-Q.front==n B、Q.rear-Q.front-1==n C、Q.front==Q.rear D、Q.front==Q.rear+1 9.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为满的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 10.若在一个大小为6 的数组上实现循环队列，且当前rear 和front 的值分别为0 和3，当从 队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为（） A、1，5 B、2, 4 C、4，2 D、5，1 11.用单链表表示的链式队列的队头在链表的（）位置 A、链头 B、链尾 C、链中 12.判定一个链队列Q（最多元素为n 个）为空的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 13.在链队列Q 中，插入s 所指结点需顺序执行的指令是（） A 、Q.front->next=s；f=s; B 、Q.rear->next=s；Q.rear=s; 实验编号：3四川师大《数据结构》实验报告2016年10月29日 实验三栈和队列及其应用_ 一．实验目的及要求 （1）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们； （2）本实验训练的要点是“栈”的观点及其典型用法； （3）掌握问题求解的状态表示及其递归算法，以及由递归程序到非递归程序的转化方法。 二．实验内容 （1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； （2）应用栈的基本操作，实现数制转换（任意进制）； （3）编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）； （4）利用栈实现任一个表达式中的语法检查（括号的匹配）。 （5）利用栈实现表达式的求值。 注：（1）～（3）必做，（4）～（5）选做。 三．主要仪器设备及软件 （1）PC机 （2）Dev C++ ,Visual C++, VS2010等 四．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； A.顺序储存： 代码部分： 栈" << endl; cout << " 2.出栈" << endl; cout << " 3.判栈空" << endl; cout << " 4.返回栈顶部数据" << endl; cout << " 5.栈长" << endl; cout << " 0.退出系统" << endl; cout << "你的选择是：" ; } 链式储存： 代码部分： 栈"< 实验名称：实验四队列的基本操作 实验目的 掌握队列这种抽象数据类型的特点及实现方法。 实验内容 从键盘读入若干个整数，建一个顺序队列或链式队列，并完成下列操作： （1）初始化队列； （2）队列是否为空； （3）出队； （4）入队。 算法设计分析 （一）数据结构的定义 单链表存储结构定义为： struct Node; //链表单链表 typedef struct Node *PNode; int dui; dui =1; struct Node { int info; PNode link; }; struct LinkQueue { PNode f; PNode r; }; typedef struct LinkQueue *PLinkQueue; （二）总体设计 程序由主函数、创建队列函数、判断是否为空队列函数、入队函数、出队函数、取数函数、显示队列函数、菜单函数组成。其功能描述如下： （1）主函数：调用各个函数以实现相应功能 main() { PLinkQueue a; //定义链表a int b,c,e; //b 菜单选择c选择继续输入e输入元素 do { //菜单选择 mune(); scanf("%d",&b); switch(b) { case 1://初始化 a=create(); //初始化队列 case 2: //入队 do { printf("\n请输入需要入队的数："); if(e!=NULL) { scanf("%d",&e); enQueue(a,e); } printf("是否继续入队？(是:1 否：0)\n"); scanf("%d",&c); } while(c==1); break; case 3: //出队 c=frontQueue(a); deQueue(a); if(dui!=0) { printf("\n出队为:%d\n",c); } dui=1; break; case 4: //显示队中元素 showQueue(a); break; case 5: return; default: printf("输入错误，程序结束!\n"); return; } } while(a!=5); { return 0; } } （三）各函数的详细设计： Function1: PLinkQueue create(void)//创队 一．实验项目名称 循环队列和链式队列的创建 二、实验目的 1、掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等， 2、队列顺序存储结构、链式存储结构和循环队列的实现，以便在 实际问题背景下灵活应用。 三、实验内容 1．链式队列的实现和运算 2．循环队列的实现和运算 四、主要仪器设备及耗材 VC++6.0运行环境实现其操作 五．程序算法 (1) 循环队列操作的算法 1>进队列 V oid enqueue (seqqueue &q, elemtype x) { if ((q.rear+1)%maxsize = = q.front) cout<<”overflow”; else { q.rear=(q.rear+1)%maxsize; //编号加1或循环回第一个单元 q.queue[q.rear]=x; } } 2>出队列 V oid dlqueue(seqqueue &q ) { if (q.rear= =q.front) cout<<”underflow”; else q.front =(q.front+1)%maxsize; } 3>取对头元素 elemtype gethead(seqqueue q ) { if (q.rear= =q.front) { cout<<”underflow”； return NULL;} else return q.queue[(q.front+1)%maxsize]; //front指向队头前一个位置 } 4>判队列空否 int empty(seqqueue q ) { if (q.rear= =q.front) reurn 1; else return 0; } （2）.链队列操作的算法 1>.链队列上的初始化 void INIQUEUE( linkqueue &s) { link *p; p=new link; p->next=NULL; //p是结构体指针类型，用-> s.front=p; //s是结构体变量，用. s.rear=p; //头尾指针都指向头结点 } 2>.入队列 void push(linkqueue &s, elemtype x) { link *p; //p是结构体指针类型，用-> p=new link; p->data=x; p->next=s.rear->next; //s是结构体变量，用. s.rear->next=p; s.rear=p; //插入最后 } 3>判队空 int empty( linkqueue s ) { if (s.front= =s.rear) return 1; else return 0; } 4>.取队头元素 elemtype gethead( linkqueue s ) { if (s.front= =s.rear) return NULL; else retuen s.front->next->data; } 第三章栈和队列试题 一、单项选择题 1.栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 2.当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时， 首先应执行（）语句修改top指针。 A. top++; B. top--; C. top = 0; D. top; 3.若让元素1,2,3依次进栈，则出栈次序不可能出现（）种情况。 A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 4.在一个顺序存储的循环队列中，队头指针指向队头元素的（）位置。 A. 前一个 B. 后一个 C. 当前 D. 后面 5.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 6.从一个顺序存储的循环队列中删除一个元素时，需要（）。 A. 队头指针加一 B. 队头指针减一 C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素 7.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front+1 == rear B. rear+1 == front C. front == 0 D. front == rear 8.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL 9.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一 个由指针s所指的结点，则应执行操作（）。 A. top->link = s; B.s->link = top->link; top->link = s; C. s->link = top; top = s; D. s->link = top; top = top->link; 10.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点， 并将被摘除结点的值保存到x中，则应执行操作（）。 A. x = top->data; top = top->link; B. top = top->link; x = top->data; C. x = top; top = top->link; D. x = top->data; 11.设循环队列的结构是 #define MaxSize 100 typedef int ElemType; 《数据结构》课程实验报告 一、实验目的和要求 （1）熟悉C语言的上机环境，进一步掌握C语言的结构特点。 （2）掌握队列的顺序表示和实现。 二、实验环境 Windows7 ,VC 三、实验内容及实施 实验三：队列 【实验要求】 构建一个循环队列, 实现下列操作 1、初始化队列(清空)； 2、入队； 3、出队; 4、求队列长度； 5、判断队列是否为空； 【源程序】 #include Q.base=new int[MAXSIZE]; Q.front=Q.rear=0; return OK; }//队列的初始化 int EnQueue(SqQueue &Q,int e) { if((Q.rear+1)%MAXSIZE==Q.front) return ERROR; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXSIZE; return OK; }//队列的入队 int DeQueue(SqQueue &Q,int &e) { if(Q.front==Q.rear) return ERROR; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXSIZE; return OK; }//队列的出队 int QueueLength(SqQueue &Q) { int i; i=(Q.rear-Q.front+MAXSIZE)%MAXSIZE; return i; }//求队列长度 void JuQueue(SqQueue &Q) { if(Q.rear==Q.front) printf("队列为空"); else printf("队列不为空"); }//判断队列是否为空 void QueueTraverse(SqQueue &Q) 数据结构练习第三章栈和队列 一、选择题 1．栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2．向顺序栈中压入新元素时，应当（）。 A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针C．先后次序无关紧要 D．同时进行 3．允许对队列进行的操作有( )。 A. 对队列中的元素排序 B. 取出最近进队的元素 C. 在队头元素之前插入元素 D. 删除队头元素 4．用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 5．设用链表作为栈的存储结构则退栈操作（）。 A. 必须判别栈是否为满 B. 必须判别栈是否为空 C. 判别栈元素的类型 D.对栈不作任何判别 6．设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。 A.front->next=s；front=s； B. s->next=rear；rear=s； C. rear->next=s；rear=s； D. s->next=front；front=s； 7．设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。 A.top=top+1; B. top=top-1; C. top->next=top; D. top=top->next; 8．队列是一种（）的线性表。 A. 先进先出 B. 先进后出 C. 只能插入 D. 只能删除 9．设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。 A. n-i B. n-1-i C. n+l -i D.不能确定 10．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。 A. 5，3，4，6，1，2 B. 3，2，5，6，4，1 C. 3，1，2，5，4，6 D. 1，5，4，6，2，3 11．队列的删除操作是在（）进行。 A．队首 B．队尾 C．队前 D．队后 12．当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（）语句修改top指针。 A．top++; B．top=0; C．top--; D．top=N; 13．队列的插入操作是在（）进行。 2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨 实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。 三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 南京信息工程大学实验（实习）报告 实验（实习）名称栈和队列日期2017.11.8 得分指导老师崔萌萌 系计算机系专业软件工程年级2016 班次(1) 姓名学号 一、实验目的 1、学习栈的顺序存储和实现，会进行栈的基本操作 2、掌握递归 3、学习队列的顺序存储、链式存储，会进行队列的基本操作 4、掌握循环队列的表示和基本操作 二、实验内容 1、用栈解决以下问题： （1）对于输入的任意一个非负十进制数，显示输出与其等值的八进制数，写出程序。（2）表达式求值，写出程序。 2、用递归写出以下程序： （1）求n！。 （2）汉诺塔程序，并截图显示3、4、5个盘子的移动步骤,写出移动6个盘子的移动次数。 3、编程实现：（1）创建队列，将asdfghjkl依次入队。（2）将队列asdfghjkl依次出队。 4、编程实现创建一个最多6个元素的循环队列、将ABCDEF依次入队，判断循环队列是否队满。 三、实验步骤 1.栈的使用 1.1 用栈实现进制的转换： 代码如下： #include printf("转换为%d进制： ",radix); while(n) { s.push(n%radix); n /= radix; } while(!s.empty()) { //非空 printf("%d",s.top()); s.pop(); } printf("\n"); return 0; } 运行结果如下： 2.2 求表达式的值 代码如下： #include ?、实验目的 1. 了解队列的特性。 2. 掌握队列的顺序表示和实现。 3. 掌握队列的链式表示和实现。 1、实验内容 实验3. 3队列的顺序表示和实现 编写一个程序实现顺序队列的各种基本运算（采用循环队列）， 主程序，完成如下功能： ⑴ 初始化队列。 ⑵ 建立顺序队列。 ⑶ 入队。 ⑷ 岀队。 (5) 判断队列是否为空。 ⑹ 取队头元素。 (7) 遍历队列。 实验3.4队列的链式表示和实现 编写一个程序实现链队列的各种基本运算，并在此基础上设计 能： (1) 初始化并建立链队列 ⑵ 入链队列。 ⑶ 岀链队列。 ⑷ 遍历链队列。 #i nclude int Ini tQueue(SqQueue &Q) { Q.base=(i nt*)malloc(MAXQSIZE*sizeof(i nt)); if(!Q.base)exit(O); Q.fro nt=Q.rear=0; return 0; }//初始化顺序队列 int QueueLe ngth(SqQueue Q) { int i; i=(Q.rear-Q.fro nt+MAXQSIZE)%MAXQSIZE; printf(“队列长度％5d\n",i); if(i)printf(" 队列非空“)； else printf(" 队列为空"); return 0; }//判断队列是否为空 int En Queue(SqQueue &Q,i nt e) { if((Q.rea 叶1)%MAXQSIZE==Q.fro nt)return 0; Q.base[Q.rear]=e; Q.rear=(Q.rea r+1)%MAXQSIZE; return 0; }//将元素e入队 int DeQueue(SqQueue & Q,i nt e) { if(Q.fro nt==Q.rear)return 0; e=Q.base[Q.fro nt]; prin tf("%5d\n",e); Q.fron t=(Q.fr on t+1)%MAXQSIZE; return 0; }// 删除元素e并返回其值 软件学院 上机实验报告 课程名称：数据结构 实验项目：队列的应用 实验室：耘慧420 姓名：学号 专业班级：实验时间： 2016.11.17 一、实验目的及要求 (一) 目的 1．掌握栈队列特点及顺序存储结构(循环队列)下基本操作的实现。 2．掌握队列的应用，能根据问题特点选择队列结构。 （二）.要求 1．定义循环队列的存储结构 2．完成入队、出队、取队头等基本操作的实现。 3．利用队列的基本操作实现n行杨辉三角的输出。 4．主函数调用杨辉三角输出函数，实现n行杨辉三角输出。 二、性质 设计性 三、实验学时 2学时 四、实验环境 C与C++程序设计学习与实验系统 五、实验内容及步骤 (一).内容 1．定义循环队列的存储结构，完成入队、出队、取队头等基本操作的实现。 2. 利用循环队列实现杨辉三角的输出 (二).步骤 1.//---------循环队列—队列的顺序存储结构 ----- #define MAXSIZE 100 typedef struct { QElemType *base; //初始化的动态分配存储空间 int front; //头指针，队列不空指向队列头元素 int rear; //尾指针，队列不空指向队列尾元素下一位置 } SqQueue; 2.杨辉三角: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 …………………… 这是一个初等数学中讨论的问题。系数表中的第 k行有 k个数，除了第一个和最后一个数为1之外，其余的数则为上一行中位其左、右的两数之和。 如果要求计算并输出杨辉三角前n行的值，则队列的最大空间应为 n+2。假设队列中已存有第 k 行的计算结果，并为了计算方便，在两行之间添加一个"0"作为行界值，则在计算第 k+1 行之前，头指针正指向第 k 行的"0"，而尾元素为第 k+1 行的"0"。由此从左到右依次输出第 k 行的值，并将计算所得的第 k+1 行的值插入队列的基本操作为： void YangHui(int n) { printf("1\n"); EnQueue(&q,0); /*开始*/ EnQueue(&q,1); /*第1行*/ EnQueue(&q,1); for(j=2;j<=n;j++) { EnQueue(&q,0); do{ 习题三栈和队列 一单项选择题 1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 2．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 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 4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（） A.2 B. 3 C. 5 D.6 5. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 6. 执行完下列语句段后，i值为：（） int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1)); A．2 B. 4 C. 8 D. 无限递归 7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。 A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(- 8. 用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 10．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队尾指针，则执行出队操作的语句为（） A.front=front+1 B. front=（front+1）% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( ) A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front 数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include >验目的 掌握顺序栈的基本操作：初始化栈、判栈空否、入栈、出栈、取栈顶数据元素等运算以及程序实现方法。 2.实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）分析问题的要求，编写和调试完成程序。 （3）保存和打印出程序的运行结果，并分析程序的运行结果。 3.实验内容 利用栈的基本操作实现一个判断算术表达式中包含圆括号、方括号是否正确配对的程序。具体完成如下： （1）定义栈的顺序存取结构。 （2）分别定义顺序栈的基本操作（初始化栈、判栈空否、入栈、出栈等）。 （3）定义一个函数用来判断算术表达式中包含圆括号、方括号是否正确配对。其中，括号配对共有四种情况：左右括号配对次序不正确；右括号多于左括号；左括号多于右括号；左右括号匹配正确。 （4）设计一个测试主函数进行测试。 （5）对程序的运行结果进行分析。 实验代码： #include < > #define MaxSize 100 typedef struct { int data[MaxSize]; int top; }SqStack; 实验二栈和队列 一、实验目的 1. 掌握栈的顺序表示和实现 2. 掌握队列的链式表示和实现 二、实验内容 1. 编写一个程序实现顺序栈的各种基本运算。 2. 实现队列的链式表示和实现。 三、实验步骤 1. 初始化顺序栈 2. 插入元素 3. 删除栈顶元素 4. 取栈顶元素 5. 遍历顺序栈 6. 置空顺序栈 7. 初始化并建立链队列 8. 入链队列 9. 出链队列 10. 遍历链队列 四、实现提示 1. /*定义顺序栈的存储结构*/ typedef struct { ElemType stack[MAXNUM]; int top; }SqStack; /*初始化顺序栈函数*/ void InitStack(SqStack *p) {q=(SqStack*)malloc(sizeof(SqStack) /*申请空间*/) /*入栈函数*/ void Push(SqStack *p,ElemType x) {if(p->top 《数据结构》课程实验报告 实验名称栈和队列实验序号实验日期 姓名院系班级学号 专业指导教师成绩 教师评语 一、实验目的和要求 (1)理解栈和队列的特征以及它们之间的差异，知道在何时使用那种数据结构。 (2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。 (3)重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队队列满和队空的条件。 (4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。 二、实验项目摘要 编写一个程序algo3-1.cpp，实现顺序栈的各种基本运算，并在此基础上设计一个主程序并完成如下功能：（1）初始化栈s； （2）判断栈s是否非空； （3）依次进栈元素a,b,c,d,e； （4）判断栈s是否非空； （5）输出栈长度； （6）输出从栈顶到栈底元素； （7）输出出栈序列； （8）判断栈s是否非空； （9）释放栈。 编写一个程序algo3-3.cpp，实现顺序环形队列的各种基本运算，并在此基础上设计一个主程序并完成如下功能： （1）初始化队列q； （2）判断队列q是否非空； （3）依次进队列a,b,c； （4）出队一个元素，输出该元素； （5）输出队列q的元素个数； （6）依次进队列元素d,e,f； （7）输出队列q的元素个数； （8）输出出队序列； （9）释放队列。 三、实验预习内容 栈的顺序存储结构及其基本运算实现（初始化栈，销毁栈，求栈的长度，判断栈是否为空，进栈，取栈顶元素，显示栈中元素） 队列的顺序存储结构及其基本运算实现（初始化队列，销毁队列，判断队列是否为空，入队列，出队列） 三、实验结果与分析 3-1 #define maxsize 100 #include 栈和队列 1 简述栈和线性表的区别。 2 简述栈和队列这两种数据结构的相同点和不同点。 3 如果进栈的元素序列为A，B，C，D，则可能得到的出栈序列有多少种？写出全部的可能序列。 4 如果进栈的元素序列为1，2，3，4，5，6，能否得到4，3，5，6，1，2和1，3，5，4，2，6的出栈序列？并说明为什么不能得到或如何得到。 5 写出下列程序段的运行结果（栈中的元素类型是char）： main( ) { SEQSTACK s,*p; char x, y; p = &s; initstack(p); x = ′c′; y = ′k′; push(p,x); push(p,′a′); push(p,y); x = pop(p); push(p,′t′); push(p,x); x = pop(p); push(p,′s′); while(!empty(p)) { y = pop(p); printf(″%c″,y);} printf(″%c＼n″,x); } 6 将一个非负十进制整数转换成二进制数，用非递归算法和递归算法来实现。 7 写一算法将一顺序栈中的元素依次取出，并打印元素值。 8 设单链表中存放着n个字符，试编一算法，判断该字符串是否有中心对称关系，例如xyzzyx，xyzyx都算是中心对称的字符串。 9 写出下列程序段的运行结果（队列中的元素类型是char）： main( ) { SEQQUEUE a, *q; char x, y; q = &a; x=′e′; y=′c′; initqueue(q); enqueue(q,′h′); enqueue(q,′r′); enqueue(q,y); x = dequeue(q);数据结构-堆栈和队列实验报告
数据结构-实验队列的实现
完整版数据结构习题集第3章栈和队列
数据结构_实验三_栈和队列及其应用
数据结构(C语言)队列的基本操作
队列实验报告
数据结构第三章栈和队列3习题
数据结构-队列实验报告
数据结构练习 第三章 栈和队列
数据结构实验报告及心得体会
数据结构栈和队列实验报告.doc
数据结构实验——队列(附程序)
数据结构——队列的应用
数据结构栈和队列习题及答案
数据结构实验报告全集
数据结构栈和队列
数据结构栈和队列实验报告
《数据结构练习题》栈和队列
- 数据结构栈和队列实验报告.doc
- 数据结构栈和队列实验报告
- 数据结构实验二题目一栈和队列实验报告
- 简易计算器栈与队列实验报告
- 数据结构--栈和队列的应用实验报告
- 数据结构实验-栈和队列基本操作
- 数据结构实验三栈和队列的应用
- 数据结构栈和队列实验报告
- 东软数据结构实验报告——通过栈和队列来实现进制转换
- 数据结构栈和队列实验报告
- 数据结构实验二题目一栈和队列实验报告
- 数据结构_实验三_栈和队列及其应用
- 数据结构栈和队列的应用表达式的求值
- 《数据结构》实验二 栈和队列
- 2数据结构-实验报告二(栈和队列及其应用)
- 数据结构--栈和队列的应用实验报告
- 数据结构实验报告栈和队列迷宫图最短路径
- 数据结构-堆栈和队列实验报告
- 数据结构堆栈实验报告
- 数据结构栈和队列实验报告