作者：JSHGDF5649 | 来源：互联网 | 2023-01-31 16:59
介绍队列的相关知识:
(3)队列ADT:
像栈一样，队列也是表。然而，使用队列时插入在一端进行而删除在另一端进行。
3.1队列模型
队列的基本操作是Enqueue(入队)，它是在表的末端插入一个元素；还有Dequeue(出队)，它是删除（或同时）返回在表的开头的元素。
3.2队列的数组实现
如同栈的情形一样，对于队列而言任何表的实现都是合法的。队列的链表实现是直接的，现在我们只讨论队列的数组实现。
1)队列数组实现的ADT:
#define MinQueueSize (5)
typedef int ElementType;
struct QueueRecord{
int Capacity;//队列包含元素的最大值
int Front;
int Rear;
int Size;//现有队列的大小
ElementType *Array;
};
typedef struct QueueRecord Queue;
int IsEmpty(Queue Q);
int IsFull(Queue Q);
Queue CreateQueue(int MaxElements);
void DisposeQueue(Queue Q);
void MakeEmpty(Queue Q);
void EnQueue(ElementType X,Queue Q);
ElementType Front(Queue Q);
void Dequeue(Queue Q);
ElementType FrontAndDequeue(Queue Q);
int IsEmpty(Queue Q){
return Q->Size==0;
}
void MakeEmpty(){
Q->Size=0;
Q->FrOnt=1;
Q->Rear=0;
}
//对下标进行处理，防止跃出数组边界
static int Succ(int Value,Queue Q){
if(++Value==Q->Capacity){
value=0;
}
return Value;
}
void Enqueue(ElementType X,Queue Q){
if(IsFull(Q)){
printf("队列已经满了！);
}else{
Q->Size++;
Q->Rear=Succ(Q->Rear,Q);
Q->Array[Q->Rear]==X;
}
}
2)队列的数组实现的实例:
将一个随机无序数组中的每个元素依次插入队列，再执行出队操作和入队操作。
1 //队列的应用实例
2 #include
3 #include
4 #include
5 #define MinQueueSize (5)
6
7 struct QueueRecord;
8 typedef int ElementType;
9 typedef struct QueueRecord *Queue;
10
11 int IsEmpty(Queue Q);
12 int IsFull(Queue Q);
13 Queue CreateQueue(int MaxElements);
14 void DisposeQueue(Queue Q);
15 void MakeEmpty(Queue Q);
16 void Enqueue(ElementType X,Queue Q);
17 ElementType Front(Queue Q);
18 void Dequeue(Queue Q);
19 ElementType FrontAndDequeue(Queue Q);
20 struct QueueRecord{
21 int Capacity;//队列包含元素的最大值
22 int Front;
23 int Rear;
24 int Size;//现有队列的大小
25 ElementType *Array;
26 };
27
28 int *RandInt4(int total,int i,int j,int order){
29 int *numberGroup=malloc(total*sizeof(int));//用于返回一个指定大小的数组
30 int tempory[j-i+1];//辅助产生随机数的数组。
31 int k;//用于循环遍历
32 int x;//接收产生的随机变量
33 srand(time(NULL));
34 //初始化辅助数组
35 for(k=0;k<=j-i;k++){
36 tempory[k]=0;
37 }
38 for(k=0;k){
39 L: x=rand()%(j-i+1)+i;//产生从i到j，包括i和j的随机数
40 if(tempory[x-i]==0){
41 tempory[x-i]=1;
42 //当需要产生的数组是无序的则执行：
43 if(order==0){
44 numberGroup[k]=x;
45 }
46 }else{
47 goto L;
48 }
49 }
50 //当需要产生有序的随机数组时执行:
51 int w=0;
52 if(order!=0){
53 for(k=0;k1;k++){
54 if(tempory[k]==1){
55 numberGroup[w++]=k+i;
56 if(w>=total){
57 break;
58 }
59 }
60 }
61 }
62
63 return numberGroup;
64 }
65 Queue CreateQueue(int MaxElements){
66 if(MaxElements<MinQueueSize){
67 printf("定义的队列的大小小于5");
68 MaxElements=MinQueueSize;
69 }
70 Queue Q=malloc(sizeof(struct QueueRecord));
71 Q->Capacity=MaxElements;
72 Q->Array=malloc(sizeof(int)*MaxElements);
73 MakeEmpty(Q);
74 return Q;
75 }
76 void MakeEmpty(Queue Q){
77 Q->FrOnt=0;//在数组的末尾，下标为MaxElements-1
78 Q->Rear=Q->Capacity-1;//在数组的开头，下标为0
79 Q->Size=0;//
80 }
81 //判断是否Front和Rear是否挨着，只有挨着队列才有可能为空或者满，当挨着时也有可能是两个元素。但此时size=2;
82 int IsFRClosed(Queue Q){
83 int size=(Q->Rear-Q->Front+1)%Q->Capacity;
84 if(size<0){
85 size+=Q->Capacity;
86 }
87 if(size>Q->Capacity){
88 size-=Q->Capacity;
89 }
90 //当size==0时两种情况，一种是队列为空，一种是队列满了。
91 return size==0;
92 }
93 int IsEmpty(Queue Q){
94 if(IsFRClosed(Q))//这里这样做，只是更加不容易出错！
95 return Q->Size==0;
96 else
97 return 0;
98 }
99 int IsFull(Queue Q){
100 if(IsFRClosed(Q)){
101 return Q->Size==Q->Capacity;
102 }else
103 return 0;
104 }
105 void Enqueue(int element,Queue Q){
106 if(!IsFull(Q)){
107 Q->Size++;
108 Q->Rear+=1;
109 if(Q->Rear==Q->Capacity){
110 Q->Rear=0;
111 }
112 Q->Array[Q->Rear]=element;
113 }else{
114 printf(" :无法将%2d插入队列，队列已满!\n",element);
115 }
116 }
117 void Dequeue(Queue Q){
118 if(!IsEmpty(Q)){
119 Q->Size--;
120 Q->Front++;
121 if(Q->FrOnt==Q->Capacity ){
122 Q->FrOnt=0;
123 }
124 }
125 }
126 int FrontAndDequeue(Queue Q){
127 int tempFrOnt=Q->Front;
128 //printf("FrOnt=%4d\n",Q->Front);
129 Dequeue(Q);
130 return Q->Array[tempFront];
131 }
132 int Front(Queue Q){
133 return Q->Array[Q->Front];
134 }
135 int main(){
136 int *tempGroup=RandInt4(40,0,100,0);
137 int *tempGroup2=RandInt4(30,0,100,0);
138 int i;
139 Queue Q=CreateQueue(50);
140 printf("1.入队40个元素！\n");
141 for(i=0;i<40;i++){
142 printf("%4d",tempGroup[i]);
143 Enqueue(tempGroup[i],Q);
144 if((i+1)%20==0){
145 printf("\n");
146 }
147 }
148 printf("2.出队10个元素！\n");
149 for(i=0;i<10;i++){
150 printf("%4d",Front(Q));
151 Dequeue(Q);
152 if((i+1)%10==0){
153 printf("\n");
154 }
155 }
156 printf("3.再入队30个元素!\n");
157 for(i=0;i<30;i++){
158 printf("%4d",tempGroup[i]);
159 Enqueue(tempGroup2[i],Q);
160 if((i+1)%20==0){
161 printf("\n");
162 }
163 }
164 printf("4.显示此队列中的所有出队结果！\n");
165 int size=Q->Size;
166 for(i=0;i){
167 printf("%4d",FrontAndDequeue(Q));
168 if((i+1)%20==0){
169 printf("\n");
170 }
171 }
172 printf("\n5.Front和Rear的位置是:\n");
173 printf("FrOnt=%d,Rear=%d",Q->Front,Q->Rear);
174 }
3.3队列的应用:
有几种使用队列给出提高运行效率的算法，我们将在第九章的图论算法中讨论他们。现在先给出某些应用队列的例子：
1)当作业送交给一台打印机，他们就按照到达的顺序被排列起来。因此被送往行式打印机的作业基本是被放到一个队列中。
2)实际生活中的每次排队都应该是一个队列。
3)在计算机网络中，有许多种PC机的网络设置，其中磁盘是放在一台叫做文件服务器上的。使用其他计算机的用户是按照先到先使用的原则来访问文件的。因此其数据结构是一个队列。
3.4排队论
处理用概率的方法计算用户排队等待时间、等待服务器的队列能够排多长，以及其他诸如此类的问题将用到被称为排队论（queueing theory）的整个数学分支。问题的答案依赖于用户加入队列的频率以及一旦用户得到服务处理时处理服务所花费的时间。这两个参数作为概率分布函数给出。
3.5队列的应用实例:
迷宫问题:迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次试验终于得到它学习走迷宫的路线。
设计一个计算机程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
1)第一种方法:用栈实现:
解题思路:从起始结点开始，寻找当前结点的下一个有效的结点（找下一个结点的顺序依照“右下左上”），如果下一个结点是可通过的'-'，则压入栈中，并标志其为*，代表已经走过，将此结点作为当前结点再次重复操作。如果下一个结点不能通过，则按照找结点的顺序（右下左上）找下一个。如果四个方向的都不行。则将当前结点从栈中弹出。执行上一次压入栈中的那个结点的找结点过程。直到遍历所有能到达的结点或者找到出口为止。
1 //迷宫问题的栈的解法
2 #include
3 #include
4 #include
5 //在栈中存地图上区块的位置信息
6 #define mapSize (10)
7 struct BlockNode{
8 int row;
9 int column;
10 int direction;//用于指示下一个区块相对于当前区块的位置，依序右下左上，值为1234.
11 struct BlockNode *Next;
12 };//用来构成栈的元素结点
13 struct PositionNode{
14 int x;
15 int y;
16 };
17 struct MazNode{
18 char mapStatus[mapSize][mapSize];//存迷宫指定位置的状态
19 struct PositionNode start;//起始位置
20 struct PositionNode end;//结束位置
21 };
22 typedef struct MazNode *Map;
23 typedef struct BlockNode *BlockStack;
24 typedef struct BlockNode *Block;
25 typedef struct PositionNode *Position;
26 void initMap(Map map){
27 srand(time(NULL));
28 int i,j;int x,y;
29 for(i=0;i<10;i++){
30 for(j=0;j<10;j++){
31 map->mapStatus[i][j]='#';
32 }
33 }//建立围墙
34 for(i=0;i<50;i++){
35 x=rand()%8+1;
36 y=rand()%8+1;
37 map->mapStatus[x][y]='-';
38 }
39 map->start.x=1;map->start.y=1;
40 map->end.x=8;map->end.y=8;
41 map->mapStatus[1][1]='m';//mouse代表入口
42 map->mapStatus[8][8]='c';//cat代表出口
43 }
44 void printMap(Map map){
45 int i,j;
46 for(i=0;i<10;i++){
47 for(j=0;j<10;j++){
48 printf("%c",map->mapStatus[i][j]);
49 }
50 printf("\n");
51 }
52 }
53 BlockStack createStack(){
54 BlockStack L=malloc(sizeof(struct BlockNode));
55 L->Next=NULL;
56 return L;
57 }
58 Block Top(BlockStack stack){
59 return stack->Next;
60 }
61 void Pop(BlockStack stack){
62 stack->Next=stack->Next->Next;
63 }
64 void Push(Block temp,BlockStack stack){
65 temp->Next=stack->Next;
66 stack->Next=temp;
67 }
68 int IsEmpty(BlockStack stack){
69 return stack->Next==NULL;
70 }
71 Position FindNextPosition(Block tempBlock){
72 Position p=malloc(sizeof(struct PositionNode));
73 switch(tempBlock->direction)
74 {
75 case 1://右
76 p->x=tempBlock->row;
77 p->y=tempBlock->column+1;
78 break;
79 case 2://下
80 p->x=tempBlock->row+1;
81 p->y=tempBlock->column;
82 break;
83 case 3://左
84 p->x=tempBlock->row;
85 p->y=tempBlock->column-1;
86 break;
87 case 4://上
88 p->x=tempBlock->row-1;
89 p->y=tempBlock->column;
90 break;
91 default:printf("error!\n");
92 }
93 return p;
94 }
95 int Pass(Position p,Map map){
96 //printf("地图中的是%c\n",map->mapStatus[p->x][p->y]);
97 if(map->mapStatus[p->x][p->y]=='-'||map->mapStatus[p->x][p->y]=='c')
98 return 1;
99 else
100 return 0;
101 }
102 void makeFoot(Position p,Map map){
103 map->mapStatus[p->x][p->y]='*';
104 }
105 void printRoute(BlockStack stack){
106 Block temp;
107 while(stack->Next!=NULL){
108 temp=Top(stack);
109 printf("<%d,%d>",temp->row,temp->column);
110 Pop(stack);
111 }
112 }
113 void printStack(BlockStack stack){
114 BlockStack ptr=stack->Next;
115 while(ptr!=NULL){
116 printf("<%d,%d>",ptr->row,ptr->column);
117 ptr=ptr->Next;
118 }
119 printf("\n");
120 }
121 BlockStack FindRoute(Map map){
122 BlockStack stack=createStack();
123 Block currentBlock;
124 Block temp=malloc(sizeof(struct BlockNode));
125 temp->row=map->start.x;
126 temp->column=map->start.y;
127 temp->direction=1;
128 Push(temp,stack);
129 //printStack(stack);
130 //当栈不为空时，取栈顶元素为当前元素
131 while(!IsEmpty(stack)){
132 currentBlock=Top(stack);
133 //当当前结点的四个方向的结点没有视察完时，逐个视察
134 while(currentBlock->direction<=4){
135 Position nextAvaliable=FindNextPosition(currentBlock);
136 //printf("结点<%d,%d>的下%d个有效的位置是<%d,%d>\n",currentBlock->row,currentBlock->column,currentBlock->direction,nextAvaliable->x,nextAvaliable->y);
137 //printf("%c",map->mapStatus[nextAvaliable->x][nextAvaliable->y]);
138 if(Pass(nextAvaliable,map)){
139 makeFoot(nextAvaliable,map);
140 //printMap(map);printf("\n");
141 temp=malloc(sizeof(struct BlockNode));
142 temp->row=nextAvaliable->x;
143 temp->column=nextAvaliable->y;
144 temp->direction=1;
145 Push(temp,stack);
146 //printStack(stack);
147 currentBlock=temp;
148 //如果当前结点是末尾结点
149 if(currentBlock->row==map->end.x&¤tBlock->column==map->end.y){
150 return stack;
151 }
152 }else{
153 currentBlock->direction++;
154 }
155 }
156 Block ord=Top(stack);
157 map->mapStatus[ord->row][ord->column]='@';//将已经访问过的点并且从栈中弹出的设为“@”。
158 Pop(stack);
159 //printStack(stack);
160 }
161 return NULL;
162 }
163
164 int main(){
165 Map map=malloc(sizeof(struct MazNode));
166 initMap(map);//初始化迷宫地图
167 printMap(map);
168 printf("\n");
169 BlockStack routeStack=FindRoute(map);//start为起始点，end为终点
170 if(routeStack==NULL){
171 printf("没有路径从起始点(%d,%d)通往(%d,%d)",map->start.x,map->start.y,map->end.x,map->end.y);
172 }else{
173 printf("从起始点(%d,%d)通往(%d,%d)的路径为:\n",map->start.x,map->start.y,map->end.x,map->end.y);
174 printMap(map);
175 printRoute(routeStack);//倒序输出
176 }
177 }//这里注释掉的语句都是调试用的。
本题的地图是随机生成的，你可以在initMap里随意更改地图的大小，但相应的printMap函数也要求更改。
如果把注释掉的第140行代码取消掉，你能清晰的看到结点遍历的过程。
2)第二种方法：用队列实现:
解题思路:队列的解决方案与栈的解决方案异曲同工。从入口开始，依序（右下左上）四个方向遍历，如果下个结点是可通过的，则加入队列。当前结点的四个方向的结点在同一层。因此，当从队列的开头顺序查看队列的结点时，只要是到达了出口，此路径肯定是最短的。因为后面的即使还有到达出口的路径但层级数肯定大于第一个出现的路径。因此这种方法求出的是最小短路径。
1 //用队列找到最短路径的问题
2
3 #define MapSize (10+2)
4 #include
5 #include
6 #include
7 struct PositionNode{
8 int x;
9 int y;
10 };
11 struct MapNode{
12 char mapStatus[MapSize][MapSize];//存迷宫指定位置的状态
13 struct PositionNode start;//起始位置
14 struct PositionNode end;//结束位置
15 };
16 struct BoxNode{
17 int row;
18 int column;
19 int pre;//指向前一个元素的下标
20 };//队列中的元素类型
21 struct QueueNode{
22 struct BoxNode *BoxBlock;
23 int Front;
24 int Rear;
25 };
26 typedef struct PositionNode Position;
27 typedef struct MapNode *Map;
28 typedef struct QueueNode *Queue;
29 void initMap(Map map){
30 //srand(time(NULL));
31 int i,j;int x,y;
32 for(i=0;i<12;i++){
33 for(j=0;j<12;j++){
34 map->mapStatus[i][j]='#';
35 }
36 }
37 for(i=0;i<80;i++){
38 x=rand()%10+1;
39 y=rand()%10+1;
40 map->mapStatus[x][y]='-';
41 }
42 map->mapStatus[1][1]='M';
43 map->mapStatus[10][10]='C';
44 map->start.x=1;map->start.y=1;
45 map->end.x=10;map->end.y=10;
46 }
47 void printMap(Map map){
48 int i;int j;
49 for(i=0;i<12;i++){
50 for(j=0;j<12;j++){
51 if(map->mapStatus[i][j]=='#'){
52 printf("%c%c",161,246);//白的当作墙
53 }else if(map->mapStatus[i][j]=='-'){
54 printf("%c%c",161,245);//黑的当作有效的通道
55 }else if(map->mapStatus[i][j]=='*'){
56 printf("%c%c",161,242);//圆的代表路径
57 }else{
58 printf(" %c",map->mapStatus[i][j]);//其余的代表进出口
59 }
60 }
61 printf("\n");
62 }
63 }
64 void initQueue(Queue queue){
65 queue->FrOnt=-1;
66 queue->Rear=-1;
67 queue->BoxBlock=malloc(sizeof(struct BoxNode)*100);
68 }
69 Queue FindRoute(Map map){
70 int Find=0;//表示没有找到最短路径
71 int row,column;//从队列的开头开始处理的结点的坐标
72 int direction;//表示当前结点的方向（四个值）
73 Queue queue=malloc(sizeof(struct QueueNode));
74 initQueue(queue);
75 queue->Rear++;
76 queue->BoxBlock[queue->Rear].row=map->start.x;
77 queue->BoxBlock[queue->Rear].column=map->start.y;
78 queue->BoxBlock[queue->Rear].pre=-1;
79 while(queue->Front<=queue->Rear&&!Find){
80 queue->Front++;
81 row=queue->BoxBlock[queue->Front].row;
82 column=queue->BoxBlock[queue->Front].column;
83 //printf("当前处理的结点是:<%d,%d>\n",row,column);
84 if(row==map->end.x&&column==map->end.y){
85 Find=1;//表示此结点是出口。路径已经找到
86 return queue;
87 }
88 for(direction=1;direction<5;direction++){
89 switch(direction){
90 case 1:
91 row=queue->BoxBlock[queue->Front].row;
92 column=queue->BoxBlock[queue->Front].column+1;
93 break;
94 case 2:
95 row=queue->BoxBlock[queue->Front].row+1;
96 column=queue->BoxBlock[queue->Front].column;
97 break;
98 case 3:
99 row=queue->BoxBlock[queue->Front].row;
100 column=queue->BoxBlock[queue->Front].column-1;
101 break;
102 case 4:
103 row=queue->BoxBlock[queue->Front].row-1;
104 column=queue->BoxBlock[queue->Front].column;
105 break;
106 default:printf("error!\n");
107 }
108 if(map->mapStatus[row][column]=='-'||map->mapStatus[row][column]=='C'){
109 queue->Rear++;
110 //printf("结点<%d,%d>加入队列！\n",row,column);
111 //printMap(map);
112 queue->BoxBlock[queue->Rear].row=row;
113 queue->BoxBlock[queue->Rear].column=column;
114 queue->BoxBlock[queue->Rear].pre=queue->Front;
115 if(map->mapStatus[row][column]!='C'){
116 map->mapStatus[row][column]='@';//表明此结点已经访问过。
117 }
118 }
119 }
120 }
121 return NULL;
122 }
123 void printRoute(Queue queue,Map map){
124 int k=queue->Front;
125 int row,column;
126 k=queue->BoxBlock[k].pre;
127 while(k>0){
128 row=queue->BoxBlock[k].row;
129 column=queue->BoxBlock[k].column;
130 map->mapStatus[row][column]='*';//从Front开始，将结点的途径之地的map对应值设为'*'。
131 k=queue->BoxBlock[k].pre;//指向Front位置元素的前一个
132 }
133 }
134 int main(){
135 Map map=malloc(sizeof(struct MapNode));
136 initMap(map);
137 printf("原始地图为:\n");
138 printMap(map);
139 Queue queue=FindRoute(map);
140 if(queue!=NULL){
141 printRoute(queue,map);
142 printf("最短路径为:\n");
143 printMap(map);
144 }else{
145 printf("没有路径从起点<%d,%d>通向<%d,%d>,队列遍历的结点有:\n",map->start.x,map->start.y,map->end.x,map->end.y);
146 printMap(map);
147 }
148 }
//这里注释掉的语句都是调试用的。
将第30行代码取消注释，将随机产生地图。将110行和111行取消注释，你将看到详细的结点遍历过程。
其实，队列也可以求解所有路径，还可以用四叉树求解所有路径，在此先不做探讨。
后续会专门写一篇解决迷宫问题的文档，包括迷宫生成算法，和找出迷宫的所有路径和最短路径问题，结合openGL动态绘制结点的遍历过程。类似下面的链接那种:
http://www.2cto.com/kf/201411/349889.html（结点的动态遍历）
http://bbs.9ria.com/thread-156150-1-1.html（三种迷宫生成算法）
http://wenku.baidu.com/link?url=AgRCE5ddoGdA-rW1nyyYD2Qhny5xPEjAlH_DkFgIB2wBFvyu0HijO7774gp-eP_bRa2OlrENBlZbE7zaFCjS_Ami2L7JGF8BUE5jXjr0pu3（迷宫问题链表实现的详解）
京公网安备 11010802041100号