DS链表—学生宿舍管理（双向列表容器List）

温馨提示：本题为深大OJ原题，深大的同学请勿直接抄袭，以免出现多个代码相同以致评0分的情况，代码和思路仅供参考，希望大家能逐步成长。

目录

题目描述

思路分析

AC代码 

---

题目描述

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

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

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

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

输入

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

后跟n行数据，每行格式为：学生姓名 宿舍号 

操作次数m，后跟m行操作，操作格式如下：

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

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

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

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

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

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

输出

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

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

输入样例1

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

输出样例1

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

思路分析

C++的STL我也会一些，但里面的list从未用过，只会用set、vector、map之类的，主要是我觉得list不好用，但现在必须现学现用了。

先讲解决思路，用两个结构体链表操作，一个used存用过的，一个access存可用的，一上来先给access编上号，然后已用的就插入used，并从access里面删掉，这里必须要注意，删完一定要break出来，否则会运行异常。

分配宿舍就插入used，access弹掉前面的，退宿舍就删uesd，插入access，记得删完一定要break。

排序直接调用list自己的排序函数，不过要自己写排序规则函数，用算法库里面的sort会报错的。

AC代码 

#include<bits/stdc++.h>
using namespace std;
struct dorm {
	string student;
	int ID;
};
bool compare(dorm&a, dorm&b) {
	return a.ID < b.ID;
}
int main() {
	list<dorm>used, access;
	for (int i = 101; i <= 120; i++) {
		dorm temp;
		temp.ID = i;
		access.push_back(temp);
	}
	int n, m;
	cin >> n;
	while (n--) {
		dorm temp;
		cin >> temp.student >> temp.ID;
		used.push_back(temp);
		for (list<dorm>::iterator it = access.begin(); it != access.end(); it++) {
			if ((*it).ID == temp.ID) {
				access.erase(it);
				break;
			}
		}
	}
	cin >> m;
	while (m--) {
		string action;
		dorm temp;
		cin >> action;
		if (action == "assign") {
			cin >> temp.student;
			temp.ID = access.front().ID;
			access.pop_front();
			used.push_back(temp);
		} else if (action == "return") {
			cin >> temp.ID;
			access.push_back(temp);
			for (list<dorm>::iterator it = used.begin(); it != used.end(); it++)
				if ((*it).ID == temp.ID){
					used.erase(it);
					break;
				}				
		} else if (action == "display_free") {
			int i = 1;
			for (auto&it : access) {
				if (i++ < access.size())
					cout << it.ID << '-';
				else cout << it.ID << endl;
			}
		} else {
			int i = 1;
			for (auto&it : used) {
				if (i++ < used.size())
					cout << it.student << '(' << it.ID << ')' << '-';
				else cout << it.student << '(' << it.ID << ')' << endl;
			}
		}
		used.sort(compare);
	}
	return 0;
}