(大家好,今天分享的是数据结构的相关知识,大家可以在评论区进行互动答疑哦~加油!💕)
目录
提要:实验题目
一、实验目的
二、实验内容及要求
三、算法思想
实验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 100typedef 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结果
(今日分享暂时到此为止啦!为不断努力的自己鼓鼓掌吧🥳。今日文案分享:人生本就是一场马不停蹄的相遇和告别。)