数据结构——实验三·队列
哈喽~~欢迎来到Tubishu的博客🌸如果你也是一名在校大学生，正在寻找各种编程资源，那么你就来对地方啦🌟
Tubishu是一名计算机本科生，会不定期整理和分享学习中的优质资源，希望能为你的编程之路添砖加瓦⭐🔥
当然，如果你也好的资源推荐，欢迎在评论区分享，让我们共同打造一个丰富的编程资源库🔥
本文专栏 ➡️ 数据结构
本实验是基于C语言实现队列的各种操作，包括实验目的、内容，循环队列+链队列的分析、算法设计、代码、运行结果贴图，最后实验总结
实验目的：
- 掌握队列的顺序/链式存储结构
- 掌握队列的操作特性
- 掌握基于顺序队列/链队列的基本操作的实现方法
实验内容:
（1）建立一个空队列
（2）对已建立的队列进行插入、删除、取队头元素等基本操作
循环队列操作
实验产出：
1.问题分析：
队满问题：需要预先定义队列的最大容量，并在入队时进行检查。
队空问题：需要在出队时进行检查，避免队空时弹出元素。
内存管理：循环队列使用数组实现，不需要动态分配内存，但需要注意队列的最大容量。
2.算法设计：
初始化队列：将队头指针front和队尾指针rear都初始化为0。
入队操作：将新元素插入到队尾指针指向的位置，然后将队尾指针向后移动一位，并进行取模运算以实现循环。
出队操作：取出队头指针指向位置的元素，然后将队头指针向后移动一位，并进行取模运算。
判断队列是否为空：当队头指针等于队尾指针时，队列为空。
判断队列是否已满：当队尾指针加 1 并取模后等于队头指针时，队列已满。
3.核心代码：
#include <stdio.h>
#include <stdlib.h>
#define ERROR 0
#define OK 1
#define MAXQSIZE 4
typedef char QElemType;
typedef struct {
QElemType data[MAXQSIZE]; // 数据的存储区
int front, rear; // 队头、队尾指针
int num; // 队中元素的个数
} c_SeqQ;
// 循环队列的初始化
int InitQueue_Sq(c_SeqQ *&Q) {
if (!(Q = new c_SeqQ)) { // 存储分配失败
return ERROR;
}
Q->front = Q->rear = 0;
Q->num = 0;
return OK;
}
// 销毁顺序队列
int DestroyQueue_Sq(c_SeqQ *Q) {
if (Q) {
delete Q;
return OK;
}
return ERROR;
}
// 获取队列大小
int GetSize_Sq(c_SeqQ *Q) {
if (Q == NULL) {
return ERROR; // 如果队列未初始化，返回错误
}
printf("队列元素个数：%d\n", Q->num); // 返回队列中元素的数量
}
// 清空队列
int ClearQueue_Sq(c_SeqQ *Q) {
if (Q == NULL) {
return ERROR; // 如果队列未初始化，返回错误
}
Q->front = Q->rear = 0; // 将队头和队尾指针都重置为0
Q->num = 0; // 元素数量重置为0
return OK;
}
// 判断顺序队列空
int QueueEmpty_Sq(c_SeqQ *Q) {
return (Q->num == 0);
}
// 判断顺序队列满
int QueueFull_Sq(c_SeqQ *Q) {
return (Q->num == MAXQSIZE);
}
// 入队操作
int EnQueue_Sq(c_SeqQ *Q, QElemType e) {
if (Q->num == MAXQSIZE) return ERROR; // 队满，溢出
Q->data[Q->rear] = e; // 元素入队
Q->rear = (Q->rear + 1) % MAXQSIZE; // 修改队尾指针值
Q->num++;
return OK;
}
// 出队操作
int DeQueue_Sq(c_SeqQ *Q, QElemType &e) {
if (Q->num == 0) return ERROR; // 队空
e = Q->data[Q->front]; // 读出队头元素
Q->front = (Q->front + 1) % MAXQSIZE; // 修改队首指针值
Q->num--;
return OK;
}
// 获取队头元素
int GetHead_Sq(c_SeqQ *Q, QElemType *e) {
if (QueueEmpty_Sq(Q)) { // 队列为空
printf("无队头元素！\n");
return ERROR;
}
*e = Q->data[Q->front]; // 将队头元素的值赋给e
return OK;
}
// 获取队尾元素
int GetTail_Sq(c_SeqQ *Q, QElemType *e) {
if (QueueEmpty_Sq(Q)) { // 队列为空
printf("无队尾元素！\n");
return ERROR;
}
// 计算队尾元素的前一个位置
int tailIndex = (Q->rear - 1 + MAXQSIZE) % MAXQSIZE;
*e = Q->data[tailIndex]; // 将队尾元素的值赋给e
return OK;
}
void DispQueue_Sq(c_SeqQ *Q) { // 输出循环队列
int p = Q->front;
printf("循环队列元素为:");
if (QueueEmpty_Sq(Q)) {
printf("队空!\n");
return;
}
do {
printf("%c ", Q->data[p]);
p = (p + 1) % MAXQSIZE;
} while (p != Q->rear);
printf("\n");
}
// 显示菜单
void showmenu() {
printf("\n\n\n");
printf("\t* --循环队列基本运算演示-- *\n");
printf("\t*********************************************\n");
printf("\t* 1---------循环队列的初始化 *\n");
printf("\t* 2---------销毁循环队列 *\n");
printf("\t* 3---------清空循环队列 *\n");
printf("\t* 4---------判断循环队列是否为空 *\n");
printf("\t* 5---------判断循环队列是否已满 *\n");
printf("\t* 6---------入队操作 *\n");
printf("\t* 7---------出队操作 *\n");
printf("\t* 8---------获取队头队尾元素 *\n");
printf("\t* *\n");
printf("\t* 0---------退出 *\n");
printf("\t*********************************************\n");
}
void Queue_Sq() {
char choice = 'N';
QElemType item;
c_SeqQ *Q; // 定义循环队列
int flag = 0; // 是否创建好了循环队列
while (choice != '0') {
//fflush(stdin);
printf("\n请选择菜单号(0--8): ");
scanf(" %c", &choice);
switch (choice) {
case '1':
printf("初始化循环队列操作\n");
if (InitQueue_Sq(Q)) {
printf("初始化成功!\n");
flag = 1; // 标志循环队列的存在
GetSize_Sq(Q);
} else {
printf("初始化失败!\n");
}
break;
case '2':
if (flag) { // 循环队列存在
DestroyQueue_Sq(Q);
flag = 0; // 循环队列已删除
printf("循环队列删除成功!\n");
} else {
printf("循环队列不存在，操作失败!\n");
}
break;
case '3':
if (flag) { // 循环队列存在
ClearQueue_Sq(Q);
printf("循环队列清空成功!\n");
} else {
printf("循环队列不存在，操作失败!\n");
}
break;
case '4':
if (flag) { // 循环队列存在
printf("循环队列%s\n", QueueEmpty_Sq(Q) ? "空" : "不空");
DispQueue_Sq(Q); // 输出循环队列
} else {
printf("循环队列不存在，操作失败!\n");
}
break;
case '5':
if (flag) { // 循环队列存在
printf("循环队列%s\n", QueueFull_Sq(Q) ? "满" : "不满");
GetSize_Sq(Q);
DispQueue_Sq(Q); // 输出循环队列
} else {
printf("循环队列不存在，操作失败!\n");
}
break;
case '6':
if (flag) { // 循环队列存在
printf("请输入要入队的元素的值: ");
scanf(" %c", &item);
if (EnQueue_Sq(Q, item))
printf("该元素已入队\n");
else {
GetSize_Sq(Q);
printf("队满，入队操作失败!\n");
}
DispQueue_Sq(Q); // 输出循环队列
} else {
printf("循环队列不存在，操作失败!\n");
}
break;
case '7':
if (flag) { // 循环队列存在
if (DeQueue_Sq(Q, item))
printf("出队元素为: %c \n", item);
else
printf("队空!\n");
DispQueue_Sq(Q); // 输出循环队列
} else {
printf("循环队列不存在，操作失败!\n");
}
break;
case '8':
if(flag) {
QElemType head, tail;
if (GetHead_Sq(Q, &head) == OK) {
printf("队头元素是：%c\n", head);
}
if (GetTail_Sq(Q, &tail) == OK) {
printf("队尾元素是：%c\n", tail);
}
DispQueue_Sq(Q); // 输出循环队列
} else {
printf("循环队列不存在，操作失败!\n");
}
break;
case '0':
printf("\n\t程序结束!\n");
DestroyQueue_Sq(Q);
break;
default:
printf("\n\t选择错误，请重新输入!\n");
break;
}
}
}
int main() {
showmenu();
Queue_Sq();
return 0;
}
4.运行结果：
5.调试：
队满测试：
尝试向循环队列中压入超过预定义的最大容量（例如，超过4个元素），验证程序是否能够正确检测到队满并输出相应的提示信息。
预期结果：程序应提示“队满”并阻止进一步的入队操作。
队空测试：
尝试从空队中弹出元素或获取元素，验证程序是否能够正确检测到队空并输出相应的提示信息。
预期结果：程序应提示“队空”并阻止弹出操作。
边界条件测试：
入队一个元素后立即出队，验证指针是否正确更新。
预期结果：头指针应正确指向下一个，且程序能够正确处理空队状态。
链队列操作
实验产出：
1.问题分析：
内存分配和释放：需要在入队时动态分配内存，在出队时释放内存，避免内存泄漏。
队空问题：需要在出队时进行检查，避免队空时删除结点。
指针操作：需要注意指针的正确使用，避免出现野指针或内存泄漏。
2.算法设计：
入队（EnQueue_L）：在rear指针指向的节点后面添加一个新节点，然后将rear指针移动到这个新节点。这个操作不会改变front指针。
出队（Dequeue_L）：移除front->next指针指向的节点，并释放该节点占用的内存，然后将front->next指针移动到下一个节点。如果队列变为空，front和rear指针会被设置为null或指向同一个节点。
查看队首元素（GetHead_L）：返回front->next指针指向的节点的数据，但不移除该节点。
检查队列是否为空（QueueEmpty_L）：检查front和rear指针是否相同，如果是，则队列为空。
3.核心代码：
//#include <stdio.h>
//#include <stdlib.h>
#include<bits/stdc++.h>
#define ERROR 0
#define OK 1
typedef char QElemType; // 定义队列中元素类型，可调整
typedef struct node { // 链队结点的结构
QElemType data;
struct node *next;
} QNode, *QueuePtr;
typedef struct {
QueuePtr front; // 队头指针
QueuePtr rear; // 队尾指针
} LQueue, *LinkQueue;
// 初始化链队
int InitQueue_L(LinkQueue &Q) {
Q = new LQueue; // 为链队结构结点分配存储空间
if (!Q) return ERROR; // 存储分配失败
Q->front = Q->rear = new QNode; // 为链队头结点分配存储空间
if (!Q->front) return ERROR; // 存储分配失败
Q->front->next = NULL; // 头结点指针域置为空
return OK;
}
// 判断链队空
int QueueEmpty_L(LinkQueue Q) {
return (Q->front == Q->rear);
}
// 获取队列大小
int GetSize_L(LinkQueue Q) {
int size = 0;
QNode* current = Q->front->next;
while (current != NULL) {
size++;
current = current->next;
}
printf("队列元素个数：%d\n", size); // 返回队列中元素的数量
return OK;
}
// 清空队列
void ClearQueue_L(LinkQueue &Q) {
QNode* p;
while (!QueueEmpty_L(Q)) {
p = Q->front->next;
Q->front->next = p->next;
free(p);
}
Q->rear = Q->front; // 确保rear指针也被设置为NULL
}
// 入队
void EnQueue_L(LinkQueue Q, QElemType e) {
QueuePtr p;
p = new QNode; // 申请新结点
p->data = e;
p->next = NULL;
Q->rear->next = p;
Q->rear = p;
}
// 出队
int DeQueue_L(LinkQueue Q, QElemType &e) {
QueuePtr p;
if (Q->front == Q->rear) return ERROR; // 队空，出队失败
p = Q->front->next; // 出队列
e = p->data; // 出队元素值赋值给e
Q->front->next = p->next;
if (Q->rear == p) Q->rear = Q->front; // 如果出队后链队为空，则修改队尾指针
delete p;
return OK;
}
// 输出链队
void DispQueue_L(LinkQueue Q) {
QueuePtr p = Q->front->next;
printf("链队元素为：");
if (Q->front == Q->rear) {
printf("链队空！\n");
} else {
while (p != NULL) {
printf("%c ", p->data);
p = p->next;
}
printf("\n");
}
}
//获取队头元素
int GetHead_L(LinkQueue Q) {
if (Q->front != Q->rear)
return Q->front->next->data;
}
//获取队尾元素
int GetTail_L(LinkQueue &Q) {
if (Q->front != Q->rear) // 队列为空
return Q->rear->data;
}
// 销毁队列
void DestroyQueue_L(LinkQueue &Q) {
QElemType e;
while(DeQueue_L(Q,e)); // 队列中所有元素出队
delete Q->front; // 释放头结点
delete Q; // 释放链队结构结点
}
// 显示菜单
void showmenu() {
printf("\n\n\n");
printf("\t* --链队基本运算演示-- *\n");
printf("\t*********************************************\n");
printf("\t* 1---------链队的初始化 *\n");
printf("\t* 2---------销毁链队 *\n");
printf("\t* 3---------清空链队 *\n");
printf("\t* 4---------判断链队是否为空 *\n");
printf("\t* 5---------入队操作 *\n");
printf("\t* 6---------出队操作 *\n");
printf("\t* 7---------获取队头队尾元素 *\n");
printf("\t* *\n");
printf("\t* 0---------退出 *\n");
printf("\t*********************************************\n");
}
void Queue_L() {
char choice = 'N';
QElemType item;
LinkQueue Q = NULL; // 定义队列
int flag = 0; // 是否创建好了链队
while (choice != '0') {
//flushall();
printf("\n请选择菜单号(0--7):");
scanf(" %c", &choice); // 注意：在%c前面加空格，用于消耗前一次输入后的换行符
switch (choice) {
case '1':
printf("初始化链队操作\n");
if (InitQueue_L(Q)) {
printf("初始化成功!\n");
flag = 1; // 标志链队存在
} else {
printf("初始化失败!\n");
}
break;
case '2':
if (flag) { // 链队存在
DestroyQueue_L(Q);
flag = 0; // 链队已删除
printf("链队删除成功!\n");
} else {
printf("链队不存在，操作失败!\n");
}
break;
case '3':
if (flag) { // 链队存在
ClearQueue_L(Q);
printf("链队清空成功!\n");
} else {
printf("链队不存在，操作失败!\n");
}
break;
case '4':
if (flag) { // 链队存在
printf("链队%s\n", QueueEmpty_L(Q) ? "空" : "不空");
GetSize_L(Q);
DispQueue_L(Q); // 输出链队
} else {
printf("链队不存在，操作失败!\n");
}
break;
case '5':
if (flag) { // 链队存在
printf("请输入要入队的元素的值: ");
scanf(" %c", &item);
EnQueue_L(Q, item);
printf("该元素已入队\n");
DispQueue_L(Q); // 输出链队
} else {
printf("链队不存在，操作失败!\n");
}
break;
case '6':
if (flag) { // 链队存在
if (DeQueue_L(Q, item))
printf("出队元素为: %c \n", item);
else
printf("队空!\n");
DispQueue_L(Q); // 输出链队
} else {
printf("链队不存在，操作失败!\n");
}
break;
case '7':
if(flag) {
if (QueueEmpty_L(Q)) { // 队列为空
printf("无队头元素！\n");
printf("无队尾元素！\n");
} else {
printf("队头元素是：%c\n", GetHead_L(Q));
printf("队尾元素是：%c\n", GetTail_L(Q));
}
DispQueue_L(Q); // 输出循链队
} else {
printf("链队不存在，操作失败!\n");
}
break;
case '0':
printf("\n\t程序结束!\n");
if (flag) {
DestroyQueue_L(Q);
}
return;
default:
printf("\n\t选择错误，请重新输入!\n");
break;
}
}
}
int main() {
showmenu();
Queue_L();
return 0;
}
4.运行结果：
5.调试：
队空测试：
尝试从空队中弹出元素或获取元素，验证程序是否能够正确检测到队空并输出相应的提示信息。
预期结果：程序应提示“队空”并阻止弹出操作。
边界条件测试：
入队一个元素后立即出队，验证指针是否正确更新。
预期结果：头指针应正确指向下一个，且程序能够正确处理空队状态。
总结
循环队列和链队列都实现了队列的基本操作，能够正确地进行入队和出队操作。
循环队列在入队和出队时效率较高，但需要预先分配足够的空间。
链队列在入队和出队时效率稍低，但不存在“假溢出”问题，存储空间利用率高。链队中，front指针本身并不存放元素，它只是用来指示队列的第一个元素的位置。当从队列中取出一个元素时，则从front指针指向的节点开始操作，取出该节点的数据，并将front指针移动到下一个节点。
在实际应用中，可以根据具体需求选择合适的队列实现方式：
如果队列的最大容量已知且固定，可以使用循环队列。
如果队列的大小不固定且需要频繁地进行插入和删除操作，可以使用链队列。
原文地址：https://blog.csdn.net/2301_80901581/article/details/145242802
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！