数据结构实验5_C语言_链队列的基本操作、入队、出队、获取队头元素等

实验5、链队列的基本操作（1）实验目的通过该实验，使学生理解链队列的构造特点并灵活应用，掌握链队基本操作的编程实现，认识栈是在一端进行插入，在另一端进行删除集中操作的线性结构，掌握队列的“先入先出”操作特点，知道判断队列空和满的条件，进一步熟悉C语言中指针操作。（2）实验内容用链式存储结构，实现教材定义的队列的基本操作。（3）参考界面菜单中包括以下功能：初始化队列，销毁队列，清空队列，队列判空，求

scl、

8937人浏览 · 2020-10-30 14:02:26

scl、 · 2020-10-30 14:02:26 发布

实验5、链队列的基本操作

（1）实验目的

通过该实验，使学生理解链队列的构造特点并灵活应用，掌握链队基本操作的编程实现，认识栈是在一端进行插入，在另一端进行删除集中操作的线性结构，掌握队列的“先入先出”操作特点，知道判断队列空和满的条件，进一步熟悉C语言中指针操作。

（2）实验内容

用链式存储结构，实现教材定义的队列的基本操作。

（3）参考界面

菜单中包括以下功能：

初始化队列，
销毁队列，
清空队列，
队列判空，
求队列长度，
获取队头元素，
插入一个元素，
删除一个元素，
输出所有元素。

要求：自定义的函数中不允许出现提示语和输出语句。

（4）验收/测试用例

通过菜单调用各个操作，测试点：

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

环境：Dev C++

一、设计思想

While + switch + 功能函数整体架构，还是功能函数不能有提示和输出语句，要求返回结果到main函数中处理操作，程序尽量规范返回值、变量命名等提高程序健壮性的点
此队列的实现采用采用链队列，一个节点结构体QNode、一个包装front\rear指针的结构体(包装起来方便一些，初始化队列的时候两指针随着初始化指向链表的头结点，注意头结点的数据域data是不作为数据节点使用的)
需要注意的点：

3.1获取队头元素的操作只是获得队头元素的值，区别与1出队，不会对原队列造成影响。另外队列头结点不是数据节点，获取元素的值需要先向前移动指针，在获取data（也就是队列元素开始于 front指针的下一个节点，结束于rear指向的节点）
3.2对于获取队列长度，需要采用移动指针+计数的方法，不像顺序队列那样指针加加
3.3销毁的时候，类似链表的销毁，需要双指针或者嵌套循环来逐个释放每个节点
3.4队列的清空这里采用的是调用初始化函数,（也可以直接front=rear，但是这样有可能会出现存储空间的浪费）
3.5注意打印所有队列的元素功能函数，这里采用的是定义指针（需要注意，定义指针的方式，是指向QNode结构体节点的指针，而不是指向双指针结构体的指针，即p = Q.front，而不是p = Q），从front开始逐个后移，循环打印，直到p=p->next超过rear指针，不在进入循环（也可以采用调用前面获取队头元素的函数，还需要对此函数加以调整）

二、主要源代码


#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

typedef int QElemType;

typedef struct QNode {
	
	QElemType data;
	struct QNode *next;
}*QueuePtr;

//把两个指针封装在一个结构体内 
//front、rear都是指向队列节点的结构体指针 
typedef struct{
	QueuePtr front;
	QueuePtr rear;
	
}LinkQueue;

// 一、功能函数声明

// 1. 初始化队列函数
void InitQueue(LinkQueue &Q) ;

// 2. 销毁队列
void DestoryQueue(LinkQueue &Q); 

// 3. 清空队列
void ClearQueue(LinkQueue &Q) ;

// 4. 队列判空
bool JudgeEmpty(LinkQueue Q); 

// 5. 求队列长度
int GetLength(LinkQueue Q); 

// 6. 获取队头元素
QElemType GetFront(LinkQueue Q);

// 7. 插入一个元素（入队） 
void InsertElem(LinkQueue &Q,QElemType elem) ;

// 8. 删除一个元素（出队） 
QElemType  DeleteElem(LinkQueue &Q) ;

// 9. 输出所有的元素
QElemType PrintElem(QueuePtr p) ;

int main(){
	
	LinkQueue Q;
	Q.front = NULL;
	Q.rear = NULL;
	
	bool flag = true;
	while(flag){
		
		cout<<"☆欢迎使用链队列操作小程序☆"<<endl;
		cout<<"Design by 司超龙-1925050351-软6"<<endl<<endl;
		cout<< "1. 初始化队列"<<endl;
		cout<< "2. 销毁队列"<<endl;
		cout<< "3. 清空队列"<<endl;
		cout<< "4. 队列判空"<<endl;
		cout<< "5. 求队列长度"<<endl;
		cout<< "6. 获取队头元素"<<endl;
		cout<< "7. 插入一个元素"<<endl;
		cout<< "8. 删除一个元素"<<endl;
		cout<< "9. 输出所有元素"<<endl<<endl;
		cout<<"请选择相应的指令执行对应的功能~"<<endl;
		cout<<"输入一个负数退出程序！"<<endl;
	
		int n;
		cin>>n;
		switch(n){
			case 1:
				system("cls");
				InitQueue(Q);
				if(Q.front != NULL){
					cout<<"队列初始化完成！" <<endl<<endl;
				}
				else{
					cout<<"队列初始化失败！请重新初始化~"<<endl<<endl; 
				}
				break;
			case 2:
				system("cls");
				if(Q.front == NULL){
					cout<<"队列还为初始化！请先初始化 ~"<<endl<<endl; 
				}
				else{
					DestoryQueue(Q);
					if(Q.front == NULL){
						cout<<"销毁队列成功!"<<endl<<endl; 
					}
					else{
						cout<<"销毁队列失败！请重新销毁~~"<<endl<<endl; 
					}
				}
				break;
			case 3:
				system("cls");
				if(Q.front == NULL){
					cout<<"队列还为初始化！请先初始化 ~"<<endl<<endl; 
				}
				else if(GetLength(Q) == 0){
					cout<<"队列为空! 不用再清空了"<<endl<<endl;
				}
				else{
					ClearQueue (Q);
					if(Q.front == Q.rear){
						cout<<"队列清空完成!"<<endl<<endl; 
					}
					else{
						cout<<"队列清空失败！请重新清空~"<<endl; 
					}
				}
				break;
			case 4:
				system("cls");
				if(Q.front == NULL){
					cout<<"队列还为初始化！请先初始化 ~"<<endl<<endl; 
				}
				else{
					if(JudgeEmpty(Q)){
						cout<<"队列为空!"<<endl<<endl; 
					}
					else{
						cout<<"队列不为空!"<<endl<<endl; 
					}
				}
				break;
			case 5:
				system("cls");
				
				if(Q.front == NULL){
					cout<<"队列还为初始化！请先初始化 ~"<<endl<<endl; 
				}
				else{
					cout<<"队列的长度为："<<GetLength(Q) <<endl<<endl; 
				}
				break;
			case 6:
				system("cls");
				if(Q.front == NULL){
					cout<<"队列还为初始化！请先初始化 ~"<<endl<<endl; 
				}
				else if(GetLength(Q) == 0){
					cout<<"队列为空! 不存在队首元素"<<endl<<endl; 
				}
				else{
					cout<<"队首元素为: "<<GetFront(Q)<<endl<<endl; 
				}
				break;
			case 7:
				system("cls");
				
				if(Q.front == NULL){
					cout<<"队列还为初始化！请先初始化 ~"<<endl<<endl; 
				}
				else{
					int elem;
					cout<<"请输入你要插入的元素:"<<endl;
					cin>>elem;
					InsertElem(Q,elem); 
					cout<<"元素 "<<elem<<" 入队成功~！"<<endl<<endl;
				}
				break;
			case 8:
				system("cls");
				if(Q.front == NULL){
					cout<<"队列还为初始化！请先初始化 ~"<<endl<<endl; 
				}
				else if(GetLength(Q) == 0){
					cout<<"队列为空! 不存在元素"<<endl<<endl;
				}
				else{
					cout<<DeleteElem(Q)<<" 元素出队成功！"<<endl<<endl; 
				
				}
				
				break;
			case 9:
				system("cls");
				
				if(Q.front == NULL){
					cout<<"队列还为初始化！请先初始化 ~"<<endl<<endl; 
				}
				else if(GetLength(Q) == 0){
					cout<<"队列为空! 不存在元素"<<endl<<endl;
				}
				else{
					
					QueuePtr p = Q.front; 
					
					cout<<"队列中的元素依次为："; 
					while(p != Q.rear){
						p = p->next;
						cout<<PrintElem(p)<<" ";
					}
					cout<<endl<<endl;
					
					
				}
				break;
			default:
				system("cls");
				if(n < 0){
					flag = false;
					cout<<"退出程序成功！欢迎下次使用~~" <<endl;
					break;
				}
				else{
					cout<<"你输入的指令有误！下次吧~下次吧~~"<<endl<<endl; 
				}
			
		}
	} 
	
	return 0; 
	
	
}

// 二、功能函数实现

// 1. 初始化队列函数
void InitQueue(LinkQueue &Q){
	
	Q.front = (QueuePtr )malloc(sizeof(QNode));
	Q.rear = Q.front;
	
	
	
} 

// 2. 销毁队列
void DestoryQueue(LinkQueue &Q){
	//队列元素为空 
	if(Q.front == Q.rear){
		free(Q.front);
		Q.front = NULL;
		Q.rear = NULL;
	}
	//队列不为空，边移动，边释放空间，rear紧邻在front前开路 
	else{
		while(Q.front){
			Q.rear = Q.front->next;
			free(Q.front);
			Q.front = Q.rear;
		}
		Q.front = NULL; 
		
	}
	
	

} 

// 3. 清空队列
void ClearQueue(LinkQueue &Q){
	InitQueue(Q);
	
}

// 4. 队列判空
bool JudgeEmpty(LinkQueue Q){

	if(Q.front == Q.rear){
		return true;
	}
	else{
		return false;
	}
} 

// 5. 求队列长度
int GetLength(LinkQueue Q){
	int length = 0;
	while(Q.front != Q.rear){
		length ++;
		Q.front = Q.front->next;
	}
	return length;
} 

// 6. 获取队头元素
QElemType GetFront(LinkQueue Q){
	
	return Q.front->next->data;
	
}

// 7. 插入一个元素（入队） 
void InsertElem(LinkQueue &Q,QElemType elem){
	
	QueuePtr p = (QueuePtr )malloc(sizeof(QNode));
	p->data = elem;
	
	Q.rear->next = p;
	Q.rear = p;
}

// 8. 删除一个元素（出队） 
QElemType  DeleteElem(LinkQueue &Q){
	
	//注意顺序，Q.front指向的当前节点不做数据节点 
	Q.front = Q.front->next;
	QElemType elem = Q.front->data;
	
	return elem; 
} 

// 9. 输出所有的元素
QElemType PrintElem(QueuePtr p){
	
	return  p->data;

}

三、实验截图

在这里插入图片描述

四、实验结果运用

简单实现了单链队列的基本操作，对比顺序栈、链队列体会到一段增删和两段增删需要根据情况选择合适的存储结构，这样实现起来，效率才会高
某些功能函数的实现，应该尽量避免O(n^2)的时间复杂度即不嵌套循环

魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

全家桶集齐！Qwen3.5四款小模型上线魔乐社区，附昇腾全套实践教程

魔乐社区

Pont - 搭建前后端之桥：高效、灵活的接口管理工具

Pont 是一款强大的数据服务层解决方案，它能够帮助开发者快速搭建前后端之间的桥梁，实现接口的高效管理和代码自动生成。无论是新手还是有经验的开发者，都能通过 Pont 轻松处理接口文档、生成类型安全的 API 代码，从而显著提升开发效率。[![Pont 工具标志](https://raw.gitcode.com/gh_mirrors/po/pont/raw/3f1b7d4bbba3fd2dda

魔乐社区

如何快速上手 hvac：HashiCorp Vault Python 客户端零基础入门指南

**hvac** 是 HashiCorp Vault 的 Python 3.X 客户端库，专为开发者提供简单高效的 Vault 交互方式。无论你是需要管理密钥、配置身份验证，还是实现安全的秘密数据存储，hvac 都能帮助你轻松搞定 Vault 的各项操作。本文将带你零基础快速入门，从安装到基础操作，让你在几分钟内即可上手使用这个强大的工具。[![hvac 客户端 Logo](https://r

魔乐社区

所有评论(0)

查看更多评论

scl、

@qq_24654501

已为社区贡献6条内容