数据结构：链队列的基本操作及应用

╰半夏微凉° 2022-12-19 06:18 152阅读 0赞

## 链队列的基本操作及应用 ##

**实验目的**  
通过该实验，使学生理解链队列的构造特点并灵活应用，掌握链队基本操作的编程实现，认识栈是在一端进行插入，在另一端进行删除集中操作的线性结构，掌握队列的“先入先出”操作特点，知道判断队列空和满的条件，进一步熟悉C语言中指针操作。  
**实验内容**  
用链式存储结构，实现教材定义的队列的基本操作。  
**参考界面**  
菜单中包括以下功能：  
1.初始化队列，  
2.销毁队列，  
3.清空队列，  
4队列判空，  
5.求队列长度，  
6.获取队头元素，  
7.插入一个 元素，  
8.删除一个元素，  
9输出所有元素。  
要求：  
自定义的函数中不允许出现提示语和输出语句。  
**验收/测试用例**  
通过菜单调用各个操作，测试点：

*  没有初始化前进行其他操作，程序是否能控制住；
 *  初始化一个队列；
 *  判队列空，屏幕显示队列为空；
 *  3个数入队， 3、5、7；
 *  队头长度，屏幕输出3；
 *  取队头元素，再判队列是否空，然后再判队列长度，（让学生知道取队头元素不改变队列中的内容，队头指针不发生改变）；
 *  出队，再判队列长度和显示队列中剩余的元素；（多次出队，队列为空之后再执行出队操作，是否提示队列为空）；
 *  入队一个元素2，再出队，再判断队列是否为空，（主要测试出队操作中特殊情况下的那两行代码是否写了）；
 *  销毁队，再做其他操作，判断程序是否能控制。  
    **主要代码**

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    //--------------队列的链式存储表示------------------- 
    typedef int status;     //status是函数的类型，其值是函数结果状态代码。
    typedef int QElem;     //自定义
    
    /* 该结构体为一个节点所含内容 data：数据域 *next：指针域 */
    typedef struct QNode{ 
    	QElem data;
    	struct QNode *next;
    }QNode,*Queue;
    /* 队列很显然需要两个指针，一个队头指针，一个队尾指针 front：队头指针，初始为NULL rear：队尾指针 */
    typedef struct { 
    	Queue front;
    	Queue rear;
    }LQueue;
    
    //---------------基本操作的函数原型说明------------ 
    status InitQueue(LQueue &Q);
           //构造一个空队列Q
    status DestroyQueue(LQueue &Q);
           //销毁队列Q 
    status ClearQueue(LQueue &Q);
           //清空队列Q 
    status QueueEmpty(LQueue Q);
           //判空 
    int QueueLength(LQueue Q);
           //求长度 
    status GetHead(LQueue Q,QElem &e);
           //获取队头元素，并用e返回其值 
    status EnQueue(LQueue &Q,QElem e);
           //插入元素e为Q的新的队尾元素 
    status DeQueue(LQueue &Q,QElem &e);
           //删除Q的队头元素，并用e返回其值 
    
    //---------------主函数---------------------------- 
    int main(){ 
    	int i;
    	LQueue Q = { NULL,NULL};
    	QElem e = 0;
    	
    	int choice;
    	while (1){ 
    		//菜单
    		printf("\t\t\t 1---初始化一个队列\n");
    		printf("\t\t\t 2---销毁队列\n");
    		printf("\t\t\t 3---清空队列\n");
    		printf("\t\t\t 4---判断队列是否为空\n");
    		printf("\t\t\t 5---求队列长度\n");
    		printf("\t\t\t 6---获取队头元素\n");
    		printf("\t\t\t 7---插入一个元素\n");
    		printf("\t\t\t 8---删除一个元素\n");
    		printf("\t\t\t 9---输出所有元素\n");	
    		printf("\t\t\t 退出，输入一个负数！");
    		printf("\n");
    		printf("\t\t----------------------------------------------\n");
    		printf("\n");
    		printf("请输入你需要的操作：\n");
    		//退出
    		scanf("%d",&choice);
    		if(choice<=0){ 
    			printf("已退出\n");
    			return 0;
    		} 
    		switch (choice){ 
    			case 1:
    				if(Q.front){ 
    					printf("队列已存在，不可重复初始化！\n");
    				}else{ 
    					//初始化 
    					i = InitQueue(Q);
    					if(i==1){ 
    						printf("初始化栈成功\n");
    					}else if(i==-2){ 
    						printf("分配空间失败\n");
    					} 
    				}
    				break;
    			case 2:
    				if(!Q.front){ 
    					printf("队列未完成初始化，请先进行初始化！\n");
    				}else{ 
    					//销毁
    					i = DestroyQueue(Q); 
    					if(i==1){ 
    						printf("销毁队列成功\n");
    					}
    				}
    				break;
    			case 3:
    				if(!Q.front){ 
    					printf("队列未完成初始化，请先进行初始化！\n");
    				}else{ 
    					//清空
    					i = ClearQueue(Q);
    					if(i == 1){ 
    						printf("清空队列成功\n");
    					} 
    				}
    				break;
    			case 4:
    				if(!Q.front){ 
    					printf("队列未完成初始化，请先进行初始化！\n");
    				}else{ 
    					//判空
    					i = QueueEmpty(Q);
    					if(i == 1){ 
    						printf("该队列为空队列\n");
    					} else{ 
    						printf("该队列非空\n");
    					}
    				}
    				break;
    			case 5:
    				if(!Q.front){ 
    					printf("队列未完成初始化，请先进行初始化！\n");
    				}else{ 
    					//求长度
    					i = QueueLength(Q);
    					printf("当前队列的长度为%d\n",i);
    				}
    				break;
    			case 6:
    				if(!Q.front){ 
    					printf("队列未完成初始化，请先进行初始化！\n");
    				}else{ 
    					//获取队头元素
    					i = GetHead(Q,e);
    					if(i == 1){ 
    						printf("该队列的队头元素为%d \n",e);	
    					}else{ 
    						printf("该队列为空队列\n");
    					}
    				}
    				break;
    			case 7:
    				if(!Q.front){ 
    					printf("队列未完成初始化，请先进行初始化！\n");
    				}else{ 
    					//插入
    					printf("请输入你想插入的元素:");
    					scanf("%d",&e);
    					i = EnQueue(Q,e);
    // printf("%d\n",e);
    					if(i == 1){ 
    						printf("插入成功\n");
    					}else { 
    						printf("分配空间失败\n");
    					}
    				}
    				break;
    			case 8:
    				if(!Q.front){ 
    					printf("队列未完成初始化，请先进行初始化！\n");
    				}else{ 
    					//删除 
    					i = DeQueue(Q,e); 
    					if(i == 1){ 
    						printf("队头元素%d删除成功\n",e);
    					}else { 
    						printf("该队列为空队列\n");
    					}
    				}
    				break;
    			case 9:
    				if(!Q.front){ 
    					printf("队列未完成初始化，请先进行初始化！\n");
    				}else{ 
    					//打印 
    					if(Q.front == Q.rear){ 
    						printf("空队列！！！\n");	
    					}else{ 
    						Queue q;
    						q = Q.front->next;
    						printf("队列内元素如下:【队头】->");
    						while(q){ 
    							printf("【%d】-> ",q->data);
    							q = q->next; 
    						}
    						printf("【队尾】\n");
    					}
    				}
    				break;
    			default:
    				printf("选择失败！请重新选择！\n");
    				break; 	 	 	 			
    		}
    		system("pause");   //请按任意键结束 
    		system("cls");     //清屏 
    	}
    	return 0;
    } 
    
    //---------------基本操作的算法描述----------------
    status InitQueue(LQueue &Q){ 
    	/*构造一个空的队列Q &Q:可以影响到 函数以外的队列 */
    	Q.front = Q.rear = (Queue)malloc(sizeof(QNode));
    	if(!Q.front){      //存储失败 
    		return OVERFLOW;
    	} 
    	Q.front ->next = NULL;
    	return OK;
    } 
    
    status DestroyQueue(LQueue &Q){ 
    	/*销毁 &Q */
    	while(Q.front){ 
    		Q.rear = Q.front->next;
    		free (Q.front);
    		Q.front = Q.rear;
    	}
    	return OK;
    } 
    
    status ClearQueue(LQueue &Q){ 
    	/*清空队列 &Q 即将队尾指针退回至队头指针处 清空后这个队列还能用 */
    	Q.rear = Q.front;
    	return OK;
    } 
    
    status QueueEmpty(LQueue Q){ 
    	//判空
    	 if(Q.rear == Q.front){ 
    	 	return OK;
    	 }else{ 
    	 	return ERROR;
    	 }
    }
    
    int QueueLength(LQueue Q){ 
    	//求长度
    	int i = 0;
    	while (Q.front !=Q.rear){ 
    		i++;
    		Q.front = Q.front->next;
    	} 
    	return i;
    } 
    
    status GetHead(LQueue Q,QElem &e){ 
    	/*获取队头元素 插入时用得是尾插，保留了头指针， 故队头元素为front的下一个指针中的数据 不为空用e返回队头元素 */
    	if(Q.front == Q.rear){ 
    		return ERROR;
    	}else{ 
    		Queue p;
    		p = Q.front->next;   
    		e = p->data;
    // printf("%d\n",e);
    		return OK;
    	} 
    }
    
    status EnQueue(LQueue &Q,QElem e){ 
    	//插入元素e为新的队尾元素 
    	Queue p;
    	p = (Queue)malloc(sizeof(QNode));
    	if(!p){ 
    		return OVERFLOW;
    	}
    // printf("%d\n",e);
    	p->data = e;
    	p->next = NULL;
    	Q.rear->next = p;
    	Q.rear = p;
    	return OK;
    }
    
    status DeQueue(LQueue &Q,QElem &e){ 
    	//删除队头元素，并用e返回队头元素
    	if(Q.front == Q.rear){ 
    		return ERROR;
    	}
    	Queue p;
    	p = Q.front->next;
    	e = p->data;
    	//将 Q.front的下一个指针指向下下一个指针，即front向前移动 
    	Q.front->next = p->next;
    	if(Q.rear == p){ 
    		/*当队列中只有一个元素的时候，删除后为空， 但由于插入时使用的是尾插，就会存在队头和队尾指针不一致的后果， 故需要将其移至一致。 */
    		Q.rear = Q.front;
    	} 
    	free(p);
    	return OK;
    }