（大家好，今天分享的是数据结构的相关知识，大家可以在评论区进行互动答疑哦~加油！????）
目录
提要：实验题目
一、实验目的
二、实验内容及要求
三、算法思想
实验1
实验2
四、源程序及注释
实验1代码（循环队列）
实验2代码（链式队列）
五、实验结果
实验1结果
实验2结果
提要：实验题目
1. 循环队列的基本操作的实现
2. 链队列的基本操作的实现
一、实验目的
1.深入了解队列的定义和特性。
2.掌握队列的数组表示、链表表示以及相应操作的实现，巩固对这两种结构的构造方法的掌握。
3. 会灵活运用队列结构解决某些实际问题。
二、实验内容及要求
1. 循环队列的基本操作的实现（初始化、入队、出队、求队列长度、取队头元素、判断队空、队列的遍历、清空队列、销毁队列等），要求建立菜单进行操作选择。
2. 链队列的基本操作的实现（初始化、入队、出队、求队列长度、取队头元素、判断队空、队列的遍历、清空队列、销毁队列等），要求建立菜单进行操作选择。
3. 舞伴问题（参见教材相关描述）。
注：前两个题目必做，第3题选做。
三、算法思想
实验1
（1.）初始化
分配一个固定大小的数组，并设置两个指针（前指针和后指针）来标识队列的头和尾。
（2.）入队
检查队列是否已满（即后指针的下一个位置等于前指针）。如果未满，将新元素放入后指针位置，并更新后指针（环形移动）。
（3.）出队
检查队列是否为空（即前指针等于后指针）。如果不为空，返回前指针位置的元素，并更新前指针（环形移动）。
（4.）求队列长度
通过计算后指针与前指针的差值来获取当前队列中的元素数量，考虑环形特性。
（5.）取队头元素
检查队列是否为空，若不为空，返回前指针指向的元素。
（6.）判断队空
直接比较前指针和后指针，如果相等，则队列为空。
（7.）队列的遍历
从前指针开始，循环访问数组，直到后指针为止，收集所有元素。
（8.）清空队列
重置前后指针，使其指向同一位置，从而清空队列。
（9.）销毁队列
在语言支持下，释放数组空间，清理相关数据结构。
（10.）舞伴问题
将参与者视为队列中的元素，通过入队和出队操作模拟舞伴选择和退出的过程，可以使用循环队列来管理参与者的动态状态。
实验2
(1.)初始化
创建一个空的链表，通常使用一个头指针（指向队列的第一个节点）和一个尾指针（指向队列的最后一个节点）。初始时，两者均为 `null`。
(2.)入队
创建一个新节点，将其数据存储在新节点中。如果队列为空（头指针为 `null`），则新节点成为头和尾；否则，将当前尾节点的 `next` 指向新节点，然后更新尾指针指向新节点。
(3.)出队
检查队列是否为空。如果不为空，保存头节点的数据，更新头指针为下一个节点（即头节点的 `next`），然后返回保存的数据。若出队后队列为空，则同时将尾指针设置为 `null`。
(4.)求队列长度
从头节点开始遍历链表，计数节点数量，直到链表结束（即指针为 `null`）。
(5.)取队头元素
检查队列是否为空，若不为空，直接返回头节点的数据。
(6.)判断队空
通过检查头指针是否为 `null` 来判断队列是否为空。
(7.)队列的遍历
从头指针开始，依次访问每个节点，直到遍历完整个链表，收集所有节点的数据。
(8.)清空队列
遍历链表，逐个删除每个节点，直至所有节点都被释放，最后将头指针和尾指针设置为 `null`。
(9.)销毁队列
在清空队列后，可以选择释放链表的头指针和尾指针的内存（如果适用），确保没有内存泄漏。
(10.)舞伴问题
将参与者视为链队列中的元素，利用链队列的动态特性来模拟舞伴的选择与退出过程，入队和出队操作分别代表参与者的加入与离开。
四、源程序及注释
实验1代码（循环队列）
#include<iostream> //输入输出流头文件
#include<fstream> //文件操作头文件
#include<string> //字符串操作头文件
#include<iomanip> //输入输出操纵运算头文件
#include<stack> // 引入 STL stack 进行栈操作
#include<cctype> // 引入字符处理函数
using namespace std;//调用命名空间std中所有标识符
//预定义常量及预定义类型
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE 100
typedef int QElemType;
typedef int Status;//Status 是函数返回值类型，其值是函数结果状态代码
//表示部分：
//创建结构体
typedef struct {
QElemType *base;
int front;
int rear;
} SqQueue;
//实现部分：
//1.初始化
Status InitQueue(SqQueue &Q) {
//构造一个空队列
Q.base = new QElemType[MAXSIZE];
if (!Q.base) {
exit(OVERFLOW);
}
Q.front = Q.rear = 0;
return OK;
}
//2.循环队列入队
Status EnQueue(SqQueue &Q, QElemType e) {
if ((Q.rear + 1) % MAXSIZE == Q.front) return ERROR;
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % MAXSIZE;
return OK;
}
//3.循环队列出队
Status DeQueue(SqQueue &Q, QElemType &e) {
if (Q.front == Q.rear) {
return ERROR;
}
e = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXSIZE;
return OK;
}
//4.求长度
Status QueueLength(SqQueue Q) {
return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}
//5.求队头元素
Status GetHead(SqQueue Q, QElemType &e) {
if (Q.front == Q.rear) {
return ERROR;
}
e = Q.base[Q.front];
return OK;
}
//6.循环队列的判空
Status QueueEmpty(SqQueue Q) {
if (Q.front == Q.rear) {
return OK;
} else {
return ERROR;
}
}
//7.遍历队列
void DisplayQueue(SqQueue Q) {
int i = Q.front;
printf("队列元素为： ");
while (Q.front != Q.rear && (i + MAXSIZE) % MAXSIZE != Q.rear) {
printf("%d ", Q.base[i]);
i++;
}
printf("\n");
}
//8.清空队列
Status ClearQueue(SqQueue &Q) {
Q.front = Q.rear = 0;
return OK;
}
//9.销毁队列
Status DestroyQueue(SqQueue &Q) {
if (Q.base) {
delete Q.base;
}
Q.base = NULL;
Q.front = Q.rear = 0;
return OK;
}
// 10. 舞伴问题
struct Person
{
char sex;// 性别：'m' 或 'f'
char name[20];// 姓名
};
struct Queue
{
Person person[20];
int front=0;
int rear=0;
int count=0;
};
// 匹配函数：根据性别将人员匹配
void Match(Person* person, int num, Queue *Female, Queue *Male) {
// 为人员数组动态分配内存
person = new Person[num];
// 为男队和女队队列分配内存
Female = new Queue;
Male = new Queue;
// 初始化队列
Male->front = Male->rear = Male->count = 0;
Female->front = Female->rear = Female->count = 0;
// 输入人员信息
cout << "请输入" << num << "位人员的性别和姓名（例如：m John）：\n";
for (int i = 0; i < num; i++) {
cin >> person[i].sex; // 输入性别
cin >> person[i].name; // 输入姓名
}
// 根据性别将人员加入相应的队列
for (int i = 0; i < num; i++) {
if (person[i].sex == 'm' || person[i].sex == 'M') {
Male->person[Male->rear++] = person[i];
Male->count++;
}
if (person[i].sex == 'f' || person[i].sex == 'F') {
Female->person[Female->rear++] = person[i];
Female->count++;
}
}
// 开始匹配
cout << "开始配对:\n";
while (Male->count > 0 && Female->count > 0) {
cout << "配对: " << Male->person[Male->front].sex << " "
<< Male->person[Male->front].name << " 和 "
<< Female->person[Female->front].sex << " "
<< Female->person[Female->front].name << endl;
// 更新队列的前端索引和人数
Male->front++;
Female->front++;
Male->count--;
Female->count--;
}
// 检查是否还有未匹配的人员
if (Male->count > 0) {
cout << "下一轮等待：男队的 " << Male->person[Male->front].name << endl;
}
if (Female->count > 0) {
cout << "下一轮等待：女队的 " << Female->person[Female->front].name << endl;
}
// 释放动态分配的内存
delete[] person; // 释放人员数组的内存
delete Male; // 释放男队队列的内存
delete Female; // 释放女队队列的内存
}
void showMenu() {
cout << "****************************\n";
cout << "**** 1. 初始化 ****\n";
cout << "**** 2. 入队 ****\n";
cout << "**** 3. 出队 ****\n";
cout << "**** 4. 求队列长度 ****\n";
cout << "**** 5. 取队头元素 ****\n";
cout << "**** 6. 判断队空 ****\n";
cout << "**** 7. 队列的遍历 ****\n";
cout << "**** 8. 清空队列 ****\n";
cout << "**** 9. 销毁队列 ****\n";
cout << "**** 10. 舞伴问题 ****\n";
cout << "**** 0. 退出 ****\n";
cout << "****************************\n";
}
int main() {
SqQueue Q;
int e,n,num;
int choose= -1;
showMenu();
while (choose != 0) {
cout << "Please select（0-10）:";
cin >> choose;
switch (choose) {
case 1://初始化
InitQueue(Q);
cout << "Init successfully：\n";
break;
case 2: // 循环队列入队
cout << "Please input the elem (int): ";
cin >> e;
if (EnQueue(Q, e) == OK) {
cout << "入队成功" << endl;
} else {
cout << "入队失败" << endl;
}
break;
case 3://循环队列出队
DeQueue(Q,e);
cout << "出队元素为"<<e<<endl;
break;
case 4: //求长度
cout << "队的长度: " << QueueLength(Q) << endl;
break;
case 5: //求队头元素
GetHead(Q,e);
cout << e;
break;
case 6: //循环队列的判空
cout << (QueueEmpty(Q) == true ? "队空" : "不空") << endl;
break;
case 7: //遍历队列
DisplayQueue(Q);
break;
case 8: //清空队列
ClearQueue(Q);
cout << "队已清空" << endl;
break;
case 9: //销毁队列
DestroyQueue(Q);
cout << "队已销毁" << endl;
break;
case 10: // 舞伴问题
cout << "请输入舞伴人数: ";
cin >> num;
Person* person = nullptr; // 定义人员数组
Queue* female = nullptr; // 定义女队队列
Queue* male = nullptr; // 定义男队队列
Match(person, num, female, male); // 调用匹配函数
break;
}
}
return 0;
}
实验2代码（链式队列）
#include<iostream> //输入输出流头文件
#include<fstream> //文件操作头文件
#include<string> //字符串操作头文件
#include<iomanip> //输入输出操纵运算头文件
#include<stack> // 引入 STL stack 进行栈操作
#include<cctype> // 引入字符处理函数
using namespace std;//调用命名空间std中所有标识符
//预定义常量及预定义类型
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define MAXSIZE 100
typedef int QElemtype;
typedef int Status;
//创建结构体
typedef struct QNode {
QElemtype data;
struct QNode *next;
} QNode, *QueuePtr;
typedef struct {
QueuePtr front;
QueuePtr rear;
} LinkQueue;
//实现部分：
//1.链队列的初始化
Status InitQueue(LinkQueue &Q) {
Q.front = Q.rear = (QueuePtr) malloc(sizeof(QNode));
if (!Q.front) {
exit(OVERFLOW);
}
Q.front->next = NULL;
return OK;
}
//2.链队列的入队
Status EnQueue(LinkQueue &Q, QElemtype e) {
QueuePtr p = (QueuePtr) malloc(sizeof(QNode));
if (!p) {
exit(OVERFLOW);
}
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
//3.链队列的出队
Status DeQueue(LinkQueue &Q, QElemtype &e) {
if (Q.front == Q.rear) {
return ERROR;
}
QueuePtr p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p) {
Q.rear = Q.front;
}
delete p;
return OK;
}
//4.求队列长度
Status QueueLength(LinkQueue Q) {
int i = 0;
while (Q.front != Q.rear) {
i++;
Q.front = Q.front->next;
}
return i;
}
//5.取链列的对头元素
Status GetQueueHead(LinkQueue &Q, QElemtype &e) {
if (Q.front == Q.rear) {
return ERROR;
}
e = Q.front->next->data;
return OK;
}
//6.判断是否为空
Status QueueEmpty(LinkQueue &Q) {
if (Q.front == Q.rear) {
return true;
} else {
return false;
}
}
//7.遍历队列
Status QueueTraverse(LinkQueue Q) {
QNode *p;
if (Q.front == Q.rear) {
return ERROR;
}
p = Q.front->next;//存储头元素
printf("从队头依次读出该队列中的元素值为: ");
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
return OK;
}
//8.清空
Status ClearQueue(LinkQueue &Q) {
Q.rear = Q.front->next;
while (Q.front->next) {
Q.rear = Q.rear->next;
delete (Q.front->next);
Q.front->next = Q.rear;
}
Q.rear = Q.front;
return OK;
}
//9.队列的销毁
Status DestoryQueue(LinkQueue &Q) {
while (Q.front) {
Q.rear = Q.front->next;
delete (Q.front);
Q.front = Q.rear;
}
return OK;
}
// 10. 舞伴问题
struct Person
{
char sex;// 性别：'m' 或 'f'
char name[20];// 姓名
};
struct Queue
{
Person person[20];
int front=0;
int rear=0;
int count=0;
};
// 匹配函数：根据性别将人员匹配
void Match(Person* person, int num, Queue *Female, Queue *Male) {
// 为人员数组动态分配内存
person = new Person[num];
// 为男队和女队队列分配内存
Female = new Queue;
Male = new Queue;
// 初始化队列
Male->front = Male->rear = Male->count = 0;
Female->front = Female->rear = Female->count = 0;
// 输入人员信息
cout << "请输入" << num << "位人员的性别和姓名（例如：m John）：\n";
for (int i = 0; i < num; i++) {
cin >> person[i].sex; // 输入性别
cin >> person[i].name; // 输入姓名
}
// 根据性别将人员加入相应的队列
for (int i = 0; i < num; i++) {
if (person[i].sex == 'm' || person[i].sex == 'M') {
Male->person[Male->rear++] = person[i];
Male->count++;
}
if (person[i].sex == 'f' || person[i].sex == 'F') {
Female->person[Female->rear++] = person[i];
Female->count++;
}
}
// 开始匹配
cout << "开始配对:\n";
while (Male->count > 0 && Female->count > 0) {
cout << "配对: " << Male->person[Male->front].sex << " "
<< Male->person[Male->front].name << " 和 "
<< Female->person[Female->front].sex << " "
<< Female->person[Female->front].name << endl;
// 更新队列的前端索引和人数
Male->front++;
Female->front++;
Male->count--;
Female->count--;
}
// 检查是否还有未匹配的人员
if (Male->count > 0) {
cout << "下一轮等待：男队的 " << Male->person[Male->front].name << endl;
}
if (Female->count > 0) {
cout << "下一轮等待：女队的 " << Female->person[Female->front].name << endl;
}
// 释放动态分配的内存
delete[] person; // 释放人员数组的内存
delete Male; // 释放男队队列的内存
delete Female; // 释放女队队列的内存
}
void showMenu() {
cout << "****************************\n";
cout << "**** 1. 初始化 ****\n";
cout << "**** 2. 入队 ****\n";
cout << "**** 3. 出队 ****\n";
cout << "**** 4. 求队列长度 ****\n";
cout << "**** 5. 取队头元素 ****\n";
cout << "**** 6. 判断队空 ****\n";
cout << "**** 7. 队列的遍历 ****\n";
cout << "**** 8. 清空队列 ****\n";
cout << "**** 9. 销毁队列 ****\n";
cout << "**** 10. 舞伴问题 ****\n";
cout << "**** 0. 退出 ****\n";
cout << "****************************\n";
}
int main() {
LinkQueue Q;
int e,n,num;
int choose= -1;
showMenu();
while (choose != 0) {
cout << "Please select（0-10）:";
cin >> choose;
switch (choose) {
case 1://初始化
InitQueue(Q);
cout << "Init successfully：\n";
break;
case 2: // 循环队列入队
cout << "Please input the elem in (int): ";
cin >> e;
if (EnQueue(Q, e) == OK) {
cout << "入队成功" << endl;
} else {
cout << "入队失败" << endl;
}
break;
case 3://循环队列出队
DeQueue(Q,e);
cout << "出队元素为"<<e<<endl;
break;
case 4: //求长度
cout << "队的长度: " << QueueLength(Q) << endl;
break;
case 5: //求队头元素
GetQueueHead(Q,e);
cout << e;
break;
case 6: //循环队列的判空
cout << (QueueEmpty(Q) == true ? "队空" : "不空") << endl;
break;
case 7: //遍历队列
QueueTraverse(Q);
break;
case 8: //清空队列
ClearQueue(Q);
cout << "队已清空" << endl;
break;
case 9: //销毁队列
DestoryQueue(Q);
cout << "队已销毁" << endl;
break;
case 10: // 舞伴问题
cout << "请输入舞伴人数: ";
cin >> num;
Person* person = nullptr; // 定义人员数组
Queue* female = nullptr; // 定义女队队列
Queue* male = nullptr; // 定义男队队列
Match(person, num, female, male); // 调用匹配函数
break;
}
}
return 0;
}五、实验结果
实验1结果
实验2结果
（今日分享暂时到此为止啦！为不断努力的自己鼓鼓掌吧????。今日文案分享：人生本就是一场马不停蹄的相遇和告别。）