DS链表—学生宿舍管理（双向列表容器List）
温馨提示：本题为深大OJ原题，深大的同学请勿直接抄袭，以免出现多个代码相同以致评0分的情况，代码和思路仅供参考，希望大家能逐步成长。
题目描述
假设某校有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;
}腾讯云开发者
