栈与队列案例练习
在开始练习案例时我们首先要了解文件读写操作
1. 文件操作
程序运行时产生的数据都属于临时数据，程序一旦运行结束都会被释放
通过 文件可以将数据持久化
C++中对文件操作需要包含头文件
文件类型分为两种：
- 文本文件：文件以文本的 ASCII码形式存储在计算机中
- 二进制文件：文件以文本的二进制形式存储在计算机中，用户一般不能直接读懂它们
操作文件的三大类
- ofstream：写操作—output：输出到文件中，为写文件
- ifstream：读操作—input：输入到屏幕中
- fstream：读写操作
1.1 文本文件
1.1.1 写文件
写文件步骤如下：
-
包含头文件
#include <fstream> -
创建流对象
ofstream ofs; -
打开文件
ofs.open("文件路径"，打开方式) -
写数据
ofs << "写入的数据"; -
关闭文件
ofs.close();
文件打开方式：
| 打开方式 | 解释 |
|---|---|
| ios::in | 为读文件而打开文件 |
| ios::out | 为写文件而打开文件 |
| ios::ate | 初始位置：文件尾 |
| ios::app | 追加方式写文件 |
| ios::trunc | 如果文件存在先删除，再创建 |
| ios::binary | 二进制方式 |
注意：文件打开方式可以配合使用，利用 | 操作符
例如：用二进制方式写文件 ios::binary | ios::out
示例：
#include <iostream>
using namespace std;
#include <fstream> //包含头文件
//文本文件 写文件
void test01()
{
//1.包含头文件
//2.创建流对象
ofstream ofs; //输出流，写文件
//3.指定打开方式
ofs.open("text.txt", ios::out);
//4.写内容
ofs << "你真是个小可爱" << endl;
ofs << "你真是个小可爱" << endl;
ofs << "你真是个小可爱" << endl;
//5.关闭文件
ofs.close();
}
int main()
{
test01();
system("pause");
return 0;
}
总结：
- 文件操作必须包含头文件 fstream
- 读文件可以利用 ofstream，或者 fstream类
- 打开文件的时候需要指定操作文件的路径，以及打开方式
- 利用 << 可以向文件中写数据
- 操作完毕，要关闭文件
1.1.2 读文件
读文件与写文件步骤相似，但是读取方式相对于比较多
-
包含头文件
#include <fstream> -
创建流对象
ifstream ifs; -
打开文件并判断文件是否打开成功
ifs.open("文件路径", 打开方式); -
读数据
四种方式读取
-
关闭文件
ifs.close();
示例：
#include <iostream>
using namespace std;
#include <fstream>
#include <string>
//文本文件-读文件
void test01()
{
//1.包含头文件
//2.创建流对象
ifstream ifs;
//3.打开文件 并且判断是否打开成功
ifs.open("text.txt", ios::in);
if (!ifs.is_open()) //如果没有打开成功
{
cout << "读取文件失败！" << endl;
return;
}
//4.读数据
//第一种读取方法：创建一个长度为1024的字符数组，初始化全为0
char buf[1024] = { 0 };
//利用while循环 把ifs通过右移运算符全部读取到字符数组buf中
//因为读文件的特殊机制，会使得读到内容为空时返回假值
while (ifs >> buf)
{
cout << buf << endl;
}
//第二种读取方法：创建一个长度为1024的字符数组，初始化全为0
char buf2[1024] = { 0 };
while (ifs.getline(buf2, sizeof(buf2)))
{
cout << buf2 << endl;
}
//第三种读取方法：创建string字符串，使用string头文件的getline(流对象名，读取到字符串的变量名);函数
string buf3;
while (getline(ifs, buf3))
{
cout << buf3 << endl;
}
//第四种（不推荐）：创建一个字符变量，然后利用while循环输出字符
char c;
while ((c = ifs.get()) != EOF) //EOF: end of file
{
cout << c;
}
//5.关闭文件
ifs.close();
}
int main()
{
test01();
//system("pasue");
return 0;
}
总结：
- 读文件可以利用 ifstream，或者 fstream类
- 利用 is_open 函数可以判断文件是否打开成功
- close 关闭文件
1.2 二进制文件
以二进制的方式对文件进行读写操作
打开方式要指定为 ios::binary
1.2.1 写文件
二进制方式写文件主要利用流对象调用成员函数 write
函数原型：ostream& write(const char* buffer, int len);
参数解释：字符指针 buffer指向1内存中一段存储空间。len是读写的字节数
示例：
#include <iostream>
using namespace std;
#include <fstream>
//二进制文件 写文件
class Person
{
public:
char m_Name[64];
int m_Age;
};
void test01()
{
//1.包含头文件
//2.创建流对象
ofstream ofs;
//3.打开文件
ofs.open("person.txt", ios::out | ios::binary);
//也可以直接ofstream ofs("person.txt", ios::out | ios::binary)
//4.写文件
Person p = { "张三", 18 };
ofs.write((const char*)&p, sizeof(Person));
//5.关闭文件
ofs.close();
}
int main()
{
test01();
system("pause");
return 0;
}
总结：
- 文件输出流对象，可以通过 write函数，以二进制方式写数据
1.2.2 读文件
二进制方式读文件主要利用流对象调用成员函数 read
函数原型：istream& read(char* buffer, int len)
参数解释：字符指针 buffer指向内存中一段存储空间，len是读写的字节数
示例：
#include <iostream>
using namespace std;
#include <fstream>
class Person
{
public:
char m_Name[64];
int m_Age;
};
//二进制文件 读文件
void test01()
{
//1.包含头文件
//2.创建流对象
ifstream ifs;
//3.打开文件，判断文件是否打开成功
ifs.open("person.txt", ios::in | ios::binary);
if (!ifs.is_open())
{
cout << "读取文件操作失败！" << endl;
return;
}
//4.读文件
Person p;
ifs.read((char*)&p, sizeof(Person));
cout << "姓名：" << p.m_Name << " 年龄：" << p.m_Age << endl;
//5.关闭文件
ifs.close();
}
int main()
{
test01();
system("pause");
return 0;
}
2. 利用顺序队列解决舞伴匹配问题
需求：假设在周末的舞会上，男士们和女士们进入舞厅时，各自排成一队
跳舞开始时，依次从男队和女队的队头各出一人配成舞伴。若链队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲
现要求写一算法模拟上述舞伴配对问题
先入队的男士或女士应先出队配成舞伴，因此该问题具有典型的先进先出特性，可用队列作为算法的数据结构
实验数据：
思路：
- 先写出顺序队列的各项基本操作然后再完善信息
- 进入舞伴匹配函数，传入 舞伴者数组dancer和舞者人数
- 定义男队和女队
- 初始化男队和女队
- 定义舞者结构体p，用来存放单个舞者的信息
- 进入循环语句
- 将人数num作为循环语句的循环条件
- 将结构体数组dancer[i]中的第i个位置的信息 赋值给 舞者结构体p
- 进入判断
- 如果单个舞者结构体p 中的sex性别为
‘F'，则执行入队操作，传入 女队 和 单个舞者结构体p - 如果单个舞者结构体p 中的sex性别不为
‘F'，则执行入队操作，传入 男队 和 单个舞者结构体p
- 如果单个舞者结构体p 中的sex性别为
- 为舞者分配队伍后，进入配对操作，进入循环
- 当 男队和女队都不为空时执行出队操作，将结果输出，左边女，右边男
- 进入判断
- 当男队空、女队非空时，输出队头女士的姓名，等待下一轮舞会后优先匹配男士
- 当女队空、男队非空时，输出队头男士的姓名，等待下一轮舞会后优先匹配女士
- 完成操作
头文件部分：
#pragma once
#include <iostream>
using namespace std;
#define MAXSIZE 100
//跳舞者的个人信息
struct Person
{
char name[20]; //姓名
char sex; //性别，'F'表示女性，'M'表示男性
};
typedef struct Person Person;
//顺序队列的数据结构
struct SqQueue
{
Person* base;
int front;
int rear;
};
typedef struct SqQueue SqQueue;
//SqQueue Mdancers, Fdancers;
//初始化顺序队列
int InitSqQueue(SqQueue& Q)
{
Q.base = new Person[MAXSIZE];
if (Q.base == NULL)
{
cout << "初始化空间失败！" << endl;
return 0;
}
Q.rear = 0;
Q.front = 0;
Q.rear = Q.front;
return 1;
}
//求循环队列的长度
int QueueLength(SqQueue Q)
{
return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}
//顺序队列的入队操作
int EnQueue(SqQueue& Q, Person e)
{
if ((Q.rear + 1) % MAXSIZE == Q.front)
{
cout << "入队操作失败，队列已满！" << endl;
return 0;
}
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % MAXSIZE;
return 1;
}
//顺序队列的出队操作
int DeQueue(SqQueue& Q, Person& e)
{
if (Q.rear == Q.front)
{
cout << "队列为空！出队操作失败！" << endl;
return 0;
}
e = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXSIZE;
return 1;
}
bool QueueEmpty(SqQueue Q)
{
if (Q.rear == Q.front)
{
//cout << "队列为空！出队操作失败！" << endl;
return true;
}
return false;
}
//取队头的元素
Person GetHead(SqQueue Q)
{
if (Q.front != Q.rear)
{
return Q.base[Q.front];
}
}
源文件部分：
#include "SqQueue.h"
#include <fstream>
void DancePartner(Person dancer[], int num)
{
SqQueue Mdancers, Fdancers; //定义男队列和女队列
InitSqQueue(Mdancers); //初始化
InitSqQueue(Fdancers);
Person p; //定义舞者的结构体p，存放单个舞者的信息
for (int i = 0; i < num; i++)
{
p = dancer[i]; //将 单个舞者的信息 存放到 结构体数组dancer[i]里
if (p.sex == 'F')
{
EnQueue(Fdancers, p); //插入女队
}
else
{
EnQueue(Mdancers, p); //插入男队
}
}
cout << "配对成功的舞伴分别是:" << endl;
//男队和女队都不为空时执行出队操作，将结果输出，左边女，右边男
while (QueueEmpty(Fdancers) != true && QueueEmpty(Mdancers) != true)
{
DeQueue(Fdancers, p);
cout << p.name << " ";
DeQueue(Mdancers, p);
cout << p.name << endl;
}
cout << endl;
//当男队空、女队非空时，输出队头女士的姓名
if (QueueEmpty(Fdancers) != true)
{
p = GetHead(Fdancers);
cout << p.name << "女士 将在下一轮中最先得到舞伴" << endl;
}
//在女队空、男队非空时，输出队头男士的姓名
else if (QueueEmpty(Mdancers) != true)
{
p = GetHead(Mdancers);
cout << p.name << "先生 将在下一轮中最先得到舞伴" << endl;
}
}
//文件中读取姓名和性别，存储到person数组中，n为存储个数
void readFile(Person* person, int& n)
{
fstream file;
file.open("舞伴名单.txt");
if (!file)
{
cout << "未找到文件！" << endl;
exit(0);
}
//一直读取文件，直到读取到结尾
while (!file.eof())
{
file >> person[n].name >> person[n].sex;
n++;
}
}
int main()
{
Person person[MAXSIZE]; //首先定义一个存放舞伴的结构体数组
int n = 0; //舞伴的人数
readFile(person, n); //调用读取文件的操作，传入结构体数组person和人数n
DancePartner(person, n); //调用舞伴匹配函数，传入结构体数组person和人数n
return 0;
}
实验结果：
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存失败,源站可能有防盗链机制,建议将图片保存下来直接上传下上传(iBTgqykIvncm-1636789238235)(E:\笔记\数据结构与算法\image\image-20211113123930702.png)( E:\笔记\数据结构与算法\image\image-20211113123930702.png)]](https://img-blog.csdnimg.cn/a969ce362cf7450893aa8f513a04987b.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAdnVsbmVyYWJsZSBtYXJrZXI=,size_8,color_FFFFFF,t_70,g_se,x_16)
3. 利用链式队列解决舞伴匹配问题
需求：假设在周末的舞会上，男士们和女士们进入舞厅时，各自排成一队
跳舞开始时，依次从男队和女队的队头各出一人配成舞伴。若链队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲
现要求写一算法模拟上述舞伴配对问题
先入队的男士或女士应先出队配成舞伴，因此该问题具有典型的先进先出特性，可用队列作为算法的数据结构
实验数据：
核心代码：
void DancePartner(Person dancer[], int num)
{
LinkQueue Mdancers, Fdancers;
InitQueue(Mdancers);
InitQueue(Fdancers);
Person p;
for (int i = 0; i < num; i++)
{
p = dancer[i];
if (p.sex == 'F')
{
EnQueue(Fdancers, p);
}
else
{
EnQueue(Mdancers, p);
}
}
cout << "配对成功的舞伴分别是：" << endl;
while (QueueEmpty(Mdancers) != true && QueueEmpty(Fdancers) != true)
{
DeQueue(Mdancers, p);
cout << p.name << " ";
DeQueue(Fdancers, p);
cout << p.name << endl;
}
cout << endl;
//如果男队非空、女队为空
if (QueueEmpty(Fdancers) != true)
{
p = GetHead(Fdancers);
cout << p.name << "女士 将在下一轮最先得到舞伴" << endl;
}
else if (QueueEmpty(Mdancers) != true)
{
p = GetHead(Mdancers);
cout << p.name << "先生 将在下一轮最先得到舞伴" << endl;
}
}
源代码：
#include <iostream>
#include <fstream>
using namespace std;
#define OK 1
#define ERROR 0
typedef int Status;
//跳舞者的个人信息
struct Person
{
char name[20]; //姓名
char sex; //性别，'F'表示女性，'M'表示男性
};
typedef struct Person Person;
typedef Person QElemType;
//队列的链式存储结构
struct QNode
{
QElemType data; //链队结点的数据域
struct QNode* next; //链队结点的指针域
};
typedef struct QNode QNode;
typedef struct QNode* QueuePtr;
struct LinkQueue
{
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
};
typedef struct LinkQueue LinkQueue;
//链队的初始化操作
//创造一个空队列Q
Status InitQueue(LinkQueue& Q)
{
Q.rear = new QNode;
Q.front = Q.rear;
Q.front->next = NULL;
return OK;
}
//链队的入队操作
//插入元素e为Q的新的队尾元素
Status EnQueue(LinkQueue& Q, QElemType e)
{
QNode* p;
p = new QNode;
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = Q.rear->next;
return OK;
}
//链队的出队操作
//删除Q的队头元素，用e返回其值
Status DeQueue(LinkQueue& Q, QElemType& e)
{
if (Q.front == Q.rear)
{
return ERROR;
}
QNode* p;
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if(Q.rear == p)
{
Q.rear = Q.front;
}
delete p;
return OK;
}
//链队取队头元素
//返回Q的队头元素，不修改队头指针
QElemType GetHead(LinkQueue Q)
{
if (Q.front != Q.rear)
{
return Q.front->next->data;
}
}
//判断队是否为空
Status QueueEmpty(LinkQueue Q)
{
if (Q.front == Q.rear)
{
return true;
}
return false;
}
void DancePartner(Person dancer[], int num)
{
LinkQueue Mdancers, Fdancers;
InitQueue(Mdancers);
InitQueue(Fdancers);
Person p;
for (int i = 0; i < num; i++)
{
p = dancer[i];
if (p.sex == 'F')
{
EnQueue(Fdancers, p);
}
else
{
EnQueue(Mdancers, p);
}
}
cout << "配对成功的舞伴分别是：" << endl;
while (QueueEmpty(Mdancers) != true && QueueEmpty(Fdancers) != true)
{
DeQueue(Mdancers, p);
cout << p.name << " ";
DeQueue(Fdancers, p);
cout << p.name << endl;
}
cout << endl;
//如果男队非空、女队为空
if (QueueEmpty(Fdancers) != true)
{
p = GetHead(Fdancers);
cout << p.name << "女士 将在下一轮最先得到舞伴" << endl;
}
else if (QueueEmpty(Mdancers) != true)
{
p = GetHead(Mdancers);
cout << p.name << "先生 将在下一轮最先得到舞伴" << endl;
}
}
//文件中读取姓名和性别，存储到person数组中，n为存储个数
void readFile(Person* person, int& n)
{
fstream file;
file.open("舞伴名单.txt");
if (!file)
{
cout << "未找到文件！" << endl;
exit(0);
}
//一直读取文件，直到读取到结尾
while (!file.eof())
{
file >> person[n].name >> person[n].sex;
n++;
}
}
int main()
{
Person person[100];
int n = 0;
readFile(person, n);
DancePartner(person, n);
return 0;
}