DS|链表

2023-12-21 18:19:03

问题一:DS单链表--存储结构与操作

题目描述:

实现含头结点的单链表

属性包括:data数据域、next指针域

操作包括:插入、删除、查找

注意:单链表不是数组,所以位置从1开始对应首结点,头结点不放数据

输入要求:

第1行先输入n表示有n个数据,接着输入n个数据

第2行输入要插入的位置和新数据

第3行输入要插入的位置和新数据

第4行输入要删除的位置

第5行输入要删除的位置

第6行输入要查找的位置

第7行输入要查找的位置

输出要求:

数据之间用空格隔开,

第1行输出创建后的单链表的数据

每成功执行一次操作(插入或删除),输出执行后的单链表数据

每成功执行一次查找,输出查找到的数据

如果执行操作失败(包括插入、删除、查找等失败),输出字符串error,不必输出单链表

输入样例:

6 11 22 33 44 55 66
3 777
1 888
1
11
0
5

输出样例:

11 22 33 44 55 66 
11 22 777 33 44 55 66 
888 11 22 777 33 44 55 66 
11 22 777 33 44 55 66 
error
error
44

代码示例:

#include<iostream>
#include<iomanip>
#include<cstring>
#include<string> 
#include<cmath>
#include<algorithm>
using namespace std;

struct Node {
	int data;
	Node* next;
};

class CList{
public:
	CList();
	void createList(int num[], int n);
	void printList();
	int insertNode(int i, int e);
	int removeNode(int i, int& e);
	Node* find(int i);
	int getLenth();
	bool isEmpty();
	~CList();
private:
	Node* head;
};
//初始化链表,创建头节点
CList::CList(){
	head = new Node;
	head->next = NULL;
}
//判断链表是否为空
bool CList::isEmpty() {
	return (head->next == NULL);
}
//求链表长度
int CList::getLenth() {
	Node* p = head->next;
	int count = 0;
	while (p->next) {
		count++;
		p = p->next;
	}
	return count;
}
//创建单链表
void CList::createList(int num[], int n){
	Node* tail = head;
	for (int i = 0; i < n; i++){
		Node* s = new Node;
		s->data = num[i];
		s->next = NULL;
		tail->next = s;
		tail = s;
	}
}
//插入结点
int CList::insertNode(int i, int e){
	Node* p = find(i - 1);
	if (!p) return 0;
	else{
		Node* s = new Node;
		s->data = e;
		s->next = p->next;
		p->next = s;
		return 1;
	}
}
//删除结点
int CList::removeNode(int i, int& e){
	Node* p = find(i - 1);
	if (!p) return 0;
	Node* q = p->next;
	if (!q) return 0;
	p->next = q->next;
	e = p->data;
	delete q;
	return 1;
}
//遍历单链表
void CList::printList(){
	Node* p = head->next;
	while (p->next){
		cout << p->data << " ";
		p = p->next;
	}
	cout << p->data << " " << endl;
}
//析构函数
CList::~CList(){
	Node* p = head;
	while (p) {
		Node* q = p;
		p = p->next;
		delete q;
	}
}
//查找结点
Node* CList::find(int i){
	int count;
	Node* cur;
	for (cur = head, count = 0; count < i && cur->next; count++) cur = cur->next;
	if (count == i) return cur;
	return NULL;
}

int main(){
	CList l;
	int n;
	cin >> n;
	int* arr = new int[n];
	for (int i = 0; i < n; i++) cin >> arr[i];
	l.createList(arr, n);
	l.printList();
	for (int i = 0; i < 2; i++){
		int index, datai;
		cin >> index >> datai;
		if (l.insertNode(index, datai)) l.printList();
		else cout << "error" << endl;
	}

	for (int i = 0; i < 2; i++){
		int digit, e;
		cin >> digit;
		if (l.removeNode(digit, e)) l.printList();
		else cout << "error" << endl;
	}

	for (int i = 0; i < 2; i++){
		int position;
		cin >> position;
		if (l.find(position) && l.find(position)->data != NULL) cout << l.find(position)->data << endl;
		else cout << "error" << endl;
	}
	return 0;
}

问题二:DS单链表--结点交换

题目描述:

用C++实现含头结点的单链表,然后实现单链表的两个结点交换位置。

注意不能简单交换两个结点包含数据,必须通过修改指针来实现两个结点的位置交换

交换函数定义可以参考:

swapNode(int ?pa, int pb) ?//pa和pb表示两个结点在单链表的位置序号

swapNode (ListNode * p, ListNode * q) ?//p和q表示指向两个结点的指针

输入要求:

第1行先输入n表示有n个数据,接着输入n个数据

第2行输入要交换的两个结点位置

第3行输入要交换的两个结点位置

输出要求:

第一行输出单链表创建后的所有数据,数据之间用空格隔开

第二行输出执行第1次交换操作后的单链表数据,数据之间用空格隔开

第三行输出执行第2次交换操作后的单链表数据,数据之间用空格隔开

如果发现输入位置不合法,输出字符串error,不必输出单链表

输入样例:

5 11 22 33 44 55
1 4
2 6

输出样例:

11 22 33 44 55 
44 22 33 11 55 
error

代码示例:

#include<iostream>
#include<iomanip>
#include<cstring>
#include<string> 
#include<cmath>
#include<algorithm>
using namespace std;

struct Node {
	int data;
	Node* next;
};

class CList{
public:
	CList();
	void createList(int num[], int n);
	void printList();
	int insertNode(int i, int e);
	int removeNode(int i, int& e);
	int swapNode(int pa, int pb);
	Node* find(int i);
	int getLenth();
	bool isEmpty();
	~CList();
private:
	Node* head;
};
//初始化链表,创建头节点
CList::CList(){
	head = new Node;
	head->next = NULL;
}
//判断链表是否为空
bool CList::isEmpty() {
	return (head->next == NULL);
}
//求链表长度
int CList::getLenth() {
	Node* p = head->next;
	int count = 0;
	while (p->next) {
		count++;
		p = p->next;
	}
	return count;
}
//创建单链表
void CList::createList(int num[], int n){
	Node* tail = head;
	for (int i = 0; i < n; i++){
		Node* s = new Node;
		s->data = num[i];
		s->next = NULL;
		tail->next = s;
		tail = s;
	}
}
//插入结点
int CList::insertNode(int i, int e){
	Node* p = find(i - 1);
	if (!p) return 0;
	else{
		Node* s = new Node;
		s->data = e;
		s->next = p->next;
		p->next = s;
		return 1;
	}
}
//删除结点
int CList::removeNode(int i, int& e){
	Node* p = find(i - 1);
	if (!p) return 0;
	Node* q = p->next;
	if (!q) return 0;
	p->next = q->next;
	e = p->data;
	delete q;
	return 1;
}
//交换结点
int CList::swapNode(int pa, int pb) {
	Node* p = find(pa - 1);
	Node* q = find(pb - 1);
	if (!q || !p || !p->next || !q->next) return 0;
	Node* tmp = p->next;
	p->next = q->next;
	q->next = tmp;

	tmp = p->next->next;
	p->next->next = q->next->next;
	q->next->next = tmp;
	return 1;
}
//遍历单链表
void CList::printList(){
	Node* p = head->next;
	while (p->next){
		cout << p->data << " ";
		p = p->next;
	}
	cout << p->data << " " << endl;
}
//析构函数
CList::~CList(){
	Node* p = head;
	while (p) {
		Node* q = p;
		p = p->next;
		delete q;
	}
}
//查找结点
Node* CList::find(int i){
	int count;
	Node* cur;
	for (cur = head, count = 0; count < i && cur->next; count++) cur = cur->next;
	if (count == i) return cur;
	return NULL;
}

int main(){
	CList l;
	int n;
	cin >> n;
	int* arr = new int[n];
	for (int i = 0; i < n; i++) cin >> arr[i];
	l.createList(arr, n);
	l.printList();
	
	for (int i = 0; i < 2; i++) {
		int pos1, pos2;
		cin >> pos1 >> pos2;
		if (l.swapNode(pos1, pos2)) l.printList();
		else cout << "error" << endl;
	}

	return 0;
}

问题三:DS单链表--合并

题目描述:

假定两个单链表是递增有序,定义并实现以下函数,完成两个单链表的合并,继续保持递增有序

int LL_merge(ListNode *La, ListNode *Lb)

输入要求:

第1行先输入n表示有n个数据,接着输入n个数据

第2行先输入m表示有M个数据,接着输入m个数据

输出要求:

输出合并后的单链表数据,数据之间用空格隔开

输入样例:

3 11 33 55
4 22 44 66 88

输出样例:

11 22 33 44 55 66 88 

代码示例:

#include<iostream>
#include<iomanip>
#include<cstring>
#include<string> 
#include<cmath>
#include<algorithm>
using namespace std;

struct Node {
	int data;
	Node* next;
};

class CList{
public:
	CList();
	void createList(int num[], int n);
	void printList();
	int insertNode(int i, int e);
	int removeNode(int i, int& e);
	int swapNode(int pa, int pb);
	Node* find(int i);
	int getLenth();
	bool isEmpty();
	CList& mergeList(CList& LB);
	~CList();
private:
	Node* head;
};
//初始化链表,创建头节点
CList::CList(){
	head = new Node;
	head->next = NULL;
}
//判断链表是否为空
bool CList::isEmpty() {
	return (head->next == NULL);
}
//求链表长度
int CList::getLenth() {
	Node* p = head->next;
	int count = 0;
	while (p->next) {
		count++;
		p = p->next;
	}
	return count;
}
//创建单链表
void CList::createList(int num[], int n){
	Node* tail = head;
	for (int i = 0; i < n; i++){
		Node* s = new Node;
		s->data = num[i];
		s->next = NULL;
		tail->next = s;
		tail = s;
	}
}
//插入结点
int CList::insertNode(int i, int e){
	Node* p = find(i - 1);
	if (!p) return 0;
	else{
		Node* s = new Node;
		s->data = e;
		s->next = p->next;
		p->next = s;
		return 1;
	}
}
//删除结点
int CList::removeNode(int i, int& e){
	Node* p = find(i - 1);
	if (!p) return 0;
	Node* q = p->next;
	if (!q) return 0;
	p->next = q->next;
	e = p->data;
	delete q;
	return 1;
}
//交换结点
int CList::swapNode(int pa, int pb) {
	Node* p = find(pa - 1);
	Node* q = find(pb - 1);
	if (!q || !p || !p->next || !q->next) return 0;
	Node* tmp = p->next;
	p->next = q->next;
	q->next = tmp;

	tmp = p->next->next;
	p->next->next = q->next->next;
	q->next->next = tmp;
	return 1;
}
//遍历单链表
void CList::printList(){
	Node* p = head->next;
	while (p->next){
		cout << p->data << " ";
		p = p->next;
	}
	cout << p->data << " " << endl;
}
//析构函数
CList::~CList(){
	Node* p = head;
	while (p) {
		Node* q = p;
		p = p->next;
		delete q;
	}
}
//查找结点
Node* CList::find(int i){
	int count;
	Node* cur;
	for (cur = head, count = 0; count < i && cur->next; count++) cur = cur->next;
	if (count == i) return cur;
	return NULL;
}
//合并有序链表
CList& CList::mergeList(CList& LB) {
	CList* LC = new CList;

	Node* pa = head->next;
	Node* pb = LB.head->next;
	Node* pc = LC->head;

	while (pa && pb) {
		if (pa->data <= pb->data) {
			pc->next = pa;
			pa = pa->next;
		}
		else {
			pc->next = pb;
			pb = pb->next;
		}
		pc = pc->next;
	}
	pc->next = pa ? pa : pb ? pb : NULL;
	head->next = NULL;
	LB.head->next = NULL;
	LC->printList();
	return *LC;
}

int main(){
	CList l1, l2;
	int n;
	cin >> n;
	int* arr = new int[n];
	for (int i = 0; i < n; i++) cin >> arr[i];
	l1.createList(arr, n);
	
	int m;
	cin >> m;
	int* brr = new int[m];
	for (int i = 0; i < m; i++) cin >> brr[i];
	l2.createList(brr, m);

	l1.mergeList(l2);
	return 0;
}

问题四:DS循环链表--约瑟夫环(Ver. I - A)

题目描述:

N个人坐成一个圆环(编号为1 - N),从第S个人开始报数,数到K的人出列,后面的人重新从1开始报数。问最后剩下的人的编号。

例如:N = 3,K = 2,S = 1。2号先出列,然后是1号,最后剩下的是3号。

要求使用循环链表实现。

输入要求:

测试数据有多组

每组包括3个数N、K、S,表示有N个人,从第S个人开始,数到K出列。(2 <= N <= 10^6,1 <= K <= 10,? 1 <= S <= N)

输出要求:

出列的人的编号

输入样例:

13 3 1
3 2 1

输出样例:

3 6 9 12 2 7 11 4 10 5 1 8 13 
2 1 3 

代码示例:

#include<iostream>
#include<iomanip>
#include<cstring>
#include<string> 
#include<cmath>
#include<algorithm>
using namespace std;

struct Node {
	int data;
	Node* next;
};

class CList{
public:
	CList();
	void createList(int num[], int n);
	void createSCList(int num[], int n);
	void printList();
	int insertNode(int i, int e);
	int removeNode(int i, int& e);
	int swapNode(int pa, int pb);
	Node* find(int i);
	int getLenth();
	bool isEmpty();
	CList& mergeList(CList& LB);
	void Jring(int num);
	~CList();
private:
	Node* head;
};
//初始化链表,创建头节点
CList::CList(){
	head = new Node;
	head->next = NULL;
}
//判断链表是否为空
bool CList::isEmpty() {
	return (head->next == NULL);
}
//求链表长度
int CList::getLenth() {
	Node* p = head->next;
	int count = 0;
	while (p->next) {
		count++;
		p = p->next;
	}
	return count;
}
//创建单链表
void CList::createList(int num[], int n){
	Node* tail = head;
	for (int i = 0; i < n; i++){
		Node* s = new Node;
		s->data = num[i];
		s->next = NULL;
		tail->next = s;
		tail = s;
	}
}
//创建单向循环链表
void CList::createSCList(int num[], int n) {
	Node* tail = head;
	for (int i = 0; i < n; i++) {
		Node* s = new Node;
		s->data = num[i];
		s->next = NULL;
		tail->next = s;
		tail = s;
	}
	tail->next = head;
}
//插入结点
int CList::insertNode(int i, int e){
	Node* p = find(i - 1);
	if (!p) return 0;
	else{
		Node* s = new Node;
		s->data = e;
		s->next = p->next;
		p->next = s;
		return 1;
	}
}
//删除结点
int CList::removeNode(int i, int& e){
	Node* p = find(i - 1);
	if (!p) return 0;
	Node* q = p->next;
	if (!q) return 0;
	p->next = q->next;
	e = p->data;
	delete q;
	return 1;
}
//交换结点
int CList::swapNode(int pa, int pb) {
	Node* p = find(pa - 1);
	Node* q = find(pb - 1);
	if (!q || !p || !p->next || !q->next) return 0;
	Node* tmp = p->next;
	p->next = q->next;
	q->next = tmp;

	tmp = p->next->next;
	p->next->next = q->next->next;
	q->next->next = tmp;
	return 1;
}
//遍历单链表
void CList::printList(){
	Node* p = head->next;
	while (p->next){
		cout << p->data << " ";
		p = p->next;
	}
	cout << p->data << " " << endl;
}
//析构函数
CList::~CList(){
	Node* p = head;
	while (p) {
		Node* q = p;
		p = p->next;
		if (p == head) break;
		delete q;
	}
}
//查找结点
Node* CList::find(int i){
	int count;
	Node* cur;
	for (cur = head, count = 0; count < i && cur->next; count++) cur = cur->next;
	if (count == i) return cur;
	return NULL;
}
//合并有序链表
CList& CList::mergeList(CList& LB) {
	CList* LC = new CList;

	Node* pa = head->next;
	Node* pb = LB.head->next;
	Node* pc = LC->head;

	while (pa && pb) {
		if (pa->data <= pb->data) {
			pc->next = pa;
			pa = pa->next;
		}
		else {
			pc->next = pb;
			pb = pb->next;
		}
		pc = pc->next;
	}
	pc->next = pa ? pa : pb ? pb : NULL;
	head->next = NULL;
	LB.head->next = NULL;
	LC->printList();
	return *LC;
}
//约瑟夫环
void CList::Jring(int num) {
	int k, s, total = num;
	cin >> k >> s;
	int count = 1;
	Node* p = head;
	for (int i = 0; i < s - 1; i++) p = p->next;
	while (total) {
		if (p->next == head) p = p->next;
		for (int i = 0; i < k - 1; i++){
			p = p->next;
			if (p->next == head) p = p->next;
		}
		Node* q = p->next;
		cout << q->data << " ";
		p->next = q->next;
		delete q;
		total--;
	}
	cout << endl;
}
int main(){
	CList l;
	int n;
	while (cin >> n) {
		int* arr = new int[n];
		for (int i = 0; i < n; i++) arr[i] = i + 1;
		l.createSCList(arr, n);
		l.Jring(n);
	}
	return 0;
}

问题五:DS线性表--多项式相加

题目描述:

对于一元多项式p(x)=p0+p1x+p2x2+…+pnxn,每个项都有系数和指数两部分,例如p2x2的系数为p2,指数为2。

编程实现两个多项式的相加。

例如5+x+2x2+3x3,-5-x+6x2+4x4,两者相加结果:8x2+3x3+4x4

其中系数5和-5都是x的0次方的系数,相加后为0,所以不显示。x的1次方同理不显示。

要求用单链表实现。

输入要求:

第1行:输入t表示有t组测试数据

第2行:输入n表示有第1组的第1个多项式包含n个项

第3行:输入第一项的系数和指数,以此类推输入n行

接着输入m表示第1组的第2个多项式包含m项

同理输入第2个多项式的m个项的系数和指数

参考上面输入第2组数据,以此类推输入t组

假设所有数据都是整数

输出要求:

对于每1组数据,先用两行输出两个原来的多项式,再用一行输出运算结果,不必考虑结果全为0的情况

输出格式参考样本数据,格式要求包括:

1.如果指数或系数是负数,用小括号括起来。

2.如果系数为0,则该项不用输出。

3.如果指数不为0,则用符号^表示,例如x的3次方,表示为x^3。

4.多项式的每个项之间用符号+连接,每个+两边加1个空格隔开。

输入样例:

2
4
5 0
1 1
2 2
3 3
4
-5 0
-1 1
6 2
4 4
3
-3 0
-5 1
2 2
4
9 -1
2 0
3 1
-2 2

输出样例:

5 + 1x^1 + 2x^2 + 3x^3
(-5) + (-1)x^1 + 6x^2 + 4x^4
8x^2 + 3x^3 + 4x^4
(-3) + (-5)x^1 + 2x^2
9x^(-1) + 2 + 3x^1 + (-2)x^2
9x^(-1) + (-1) + (-2)x^1

代码示例:

#include<iostream>
#include<iomanip>
#include<cstring>
#include<string> 
#include<cmath>
#include<algorithm>
using namespace std;

struct Node{
	int coefficient;
	int expoenet;
	Node* next;
};

class CList{
public:
	CList();
	void createList(int** num, int n);
	void printList();
	CList& addList(CList& LB);
	~CList();
private:
	Node* head;
};

CList::CList(){
	head = new Node;
}

void CList::createList(int** num, int n){
	Node* tail = head;
	for (int i = 0; i < n; i++){
		Node* s = new Node;
		s->coefficient = num[i][0];
		s->expoenet = num[i][1];
		s->next = NULL;
		tail->next = s;
		tail = s;
	}
}

void CList::printList(){
	Node* p = head->next;
	while (p->next){
		if (p->coefficient < 0) cout << "(" << p->coefficient << ")";
		else cout << p->coefficient;
		if (p->expoenet < 0) cout << "x^(" << p->expoenet << ")";
		else if (p->expoenet > 0) cout << "x^" << p->expoenet;
		cout << " + ";
		p = p->next;
	}
	if (p->coefficient < 0) cout << "(" << p->coefficient << ")";
	else cout << p->coefficient;
	if (p->expoenet < 0) cout << "x^(" << p->expoenet << ")";
	else if (p->expoenet > 0) cout << "x^" << p->expoenet;
	cout << endl;
}

CList::~CList(){
	Node* p = head;
	while (p) {
		Node* q = p;
		p = p->next;
		if (p == head) break;
		delete q;
	}
}

CList& CList::addList(CList& LB){
	CList* LC = new CList;

	Node* pa = head->next;
	Node* pb = LB.head->next;
	Node* pc = LC->head;

	while (pa && pb){
		if (pa->expoenet < pb->expoenet) {
			pc->next = pa;
			pa = pa->next;
			pc = pc->next;
		}
		else if (pa->expoenet == pb->expoenet) {
			if (pa->coefficient + pb->coefficient != 0) {
				Node* temp = new Node;
				temp->coefficient = pa->coefficient + pb->coefficient;
				temp->expoenet = pa->expoenet;
				temp->next = NULL;
				pc->next = temp;
				pc = pc->next;
			}
			pa = pa->next;
			pb = pb->next;
		}
		else if (pa->expoenet > pb->expoenet) {
			pc->next = pb;
			pb = pb->next;
			pc = pc->next;
		}
	}
	pc->next = pa ? pa : pb ? pb : NULL;
	head->next = NULL;
	LB.head->next = NULL;
	return *LC;
}

int main(){
	CList l1, l2;
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		int** arr = new int* [n];
		for (int i = 0; i < n; i++) {
			arr[i] = new int[2];
			for (int j = 0; j < 2; j++) {
				cin >> arr[i][j];
			}
		}
		l1.createList(arr, n);
		l1.printList();

		int m;
		cin >> m;
		int** brr = new int* [m];
		for (int i = 0; i < m; i++) {
			brr[i] = new int[2];
			for (int j = 0; j < 2; j++) {
				cin >> brr[i][j];
			}
		}
		l2.createList(brr, m);
		l2.printList();

		CList l3 = l1.addList(l2);
		l3.printList();
	}
	return 0;
}

问题六:DS链表--学生宿舍管理(双向列表容器List)

题目描述:

假设某校有20间宿舍,宿舍编号101,102,...,120。每间只住一名学生。初始部分宿舍已用。用两个链表(已用宿舍链表和可用宿舍链表)维护宿舍的管理,实现宿舍分配、宿舍交回。

约定已用宿舍链表按宿舍号升序链接。初始可用宿舍链表也按宿舍号升序链接。

宿舍分配从可用宿舍链表中摘取第一间宿舍分配给学生。学生交回的宿舍挂在可用宿舍链表最后。

备注:使用list容器或静态链表。不用考虑宿舍分配和交回不成功的情况。

输入要求:

初始宿舍状态,第一行输入n,表示已用宿舍n间

后跟n行数据,每行格式为:学生姓名 宿舍号?

操作次数m,后跟m行操作,操作格式如下:

assign 学生? //为学生分配宿舍,从可用宿舍链表头摘取一间宿舍,

//按宿舍号升序挂在已用宿舍链表中。

return? 宿舍号?? //学生退宿舍,删除已用宿舍链表中对应结点,

//挂在可用宿舍链表尾部。

display_free?? //输出可用宿舍链表信息。

display_used?? //输出已用宿舍链表信息。

输出要求:

display_free依次输出当前可用宿舍链表中的宿舍号,具体格式见样例。

display_used依次输出当前已用宿舍链表中的宿舍号,具体格式见样例。

输入样例:

5
李明  103
张三  106
王五  107
钱伟  112
章立  118
8
assign 李四
assign 赵六
return 118
return 101
assign 马山
display_used
assign 林立
display_free

输出样例:

赵六(102)-李明(103)-马山(104)-张三(106)-王五(107)-钱伟(112)
108-109-110-111-113-114-115-116-117-119-120-118-101

代码示例:

#include <iostream>
#include <list>
using namespace std;

class Dormitory {
public:
    Dormitory() {}

    // 初始化宿舍,参数包括学生姓名数组、宿舍号数组和学生总数
    void initialDorm(string Student[], int dormNumber[], int totalNum) {
        int count = 0;
        for (int i = 101; i <= 120; i++) {
            // 如果宿舍号不在已分配的宿舍中,则加入可用宿舍列表
            if (i != dormNumber[count]) freeDorms.push_back(i);
            else {
                // 否则,加入已使用宿舍列表
                usedDorms.push_back({ Student[count],dormNumber[count] });
                count++;
            }
        }
    }

    // 分配宿舍给学生
    void assignDorm(const string& student) {
        int dormNum = freeDorms.front();
        freeDorms.pop_front();
        usedDorms.push_back({ student, dormNum });
        usedDorms.sort([](const pair<string, int>& a, const pair<string, int>& b) {
            return a.second < b.second;
        });
    }

    // 归还宿舍
    void returnDorm(int dormNum) {
        for (auto it = usedDorms.begin(); it != usedDorms.end(); ++it) {
            if (it->second == dormNum) {
                freeDorms.push_back(dormNum);
                usedDorms.erase(it);
                return;
            }
        }
    }

    // 显示空闲宿舍
    void displayFree() {
        int count = 0;
        for (int dormNum : freeDorms) {
            cout << dormNum;
            if (count < freeDorms.size() - 1) cout << "-";
            count++;
        }
    }

    // 显示已分配的宿舍和学生信息
    void displayUsed() {
        int count = 0;
        for (const auto& dorm : usedDorms) {
            cout << dorm.first << "(" << dorm.second << ")";
            if (count < usedDorms.size() - 1) cout << "-";
            count++;
        }
        cout << endl;
    }

private:
    list<pair<string, int>> usedDorms;  // 已分配的宿舍和学生信息
    list<int> freeDorms;                // 可用的宿舍列表
};

int main() {
    int n;
    cin >> n;
    Dormitory dorm;
    string* student = new string[n];
    int* dormNum = new int[n];
    for (int i = 0; i < n; i++) cin >> student[i] >> dormNum[i];

    dorm.initialDorm(student, dormNum, n);

    int m;
    cin >> m;
    for (int i = 0; i < m; ++i) {
        string operation;
        cin >> operation;
        if (operation == "assign") {
            string student;
            cin >> student;
            dorm.assignDorm(student);
        }
        else if (operation == "return") {
            int dormNum;
            cin >> dormNum;
            dorm.returnDorm(dormNum);
        }
        else if (operation == "display_free") {
            dorm.displayFree();
        }
        else if (operation == "display_used") {
            dorm.displayUsed();
        }
    }

    return 0;
}

文章来源:https://blog.csdn.net/2203_75720729/article/details/135129374
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。