题目描述

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

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

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

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

输入

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

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

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

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

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

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

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

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

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

输出

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

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

IO模式

本题IO模式为标准输入/输出(Standard IO)，你需要从标准输入流中读入数据，并将答案输出至标准输出流中。

---

输入样例1

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

输出样例1

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

---

提示

list是一种序列式容器, list实际上就构成了一个双向循环链,

List类使用的参考代码

包含头文件<list>  ：  #include <list>

List定义和初始化：

list<int>lst1;          //创建空list

list<int> lst2(5);       //创建含有5个元素的list

list<int>lst3(3,2);  //创建含有3个元素的list

list<int>lst4(lst2);    //使用lst2初始化lst4

list<int>lst5(lst2.begin(),lst2.end());  //同lst4

创建一个list对象l（注意list是模板类）：list<char>  l; //堆栈的数据类型是字符型

把一个字符ct添加到链表末尾： s.push_back(ct);

把一个字符ct插入到链表头部： s.push_front(ct);

获取链表第一个元素和最后一个元素：front()和back()，获取链表第一个元素，放入变量c2： c2 = s.front();

删除链表第一个元素和最后一个元素pop_front()和pop_back();

判断 判断list是否为空:empty()： l.empty()，如果为空则函数返回true，如果不空则返回false

begin() 返回指向第一个元素的迭代器

end() 返回末尾的迭代器

rbegin() 返回指向第一个元素的逆向迭代器

rend() 指向list末尾的逆向迭代器

程序示列：

#include <iostream>

using namespace std;

typedef list<int> LISTINT;

void main()

{

//用LISTINT创建一个list对象

LISTINT listOne;

//声明i为迭代器

LISTINT::iterator i;

listOne.push_front(3);

listOne.push_front(2);

listOne.push_front(1);

listOne.push_back(4);

listOne.push_back(5);

listOne.push_back(6);

cout << "listOne.begin()--- listOne.end():" << endl;

for (i = listOne.begin(); i != listOne.end(); ++i)

cout << *i << " ";

cout << endl;    //正向输出

LISTINT::reverse_iterator ir;

cout << "listOne.rbegin()---listOne.rend():" << endl;

for (ir = listOne.rbegin(); ir != listOne.rend(); ir++) {

cout << *ir << " ";

}

cout << endl;    //反向输出

}

---

AC代码

#include<iostream>
using namespace std;
class LNode {
public:
	int num;
	string name;
	LNode* prior;
	LNode* next;
	LNode() {
		name = " ";
		num = 0;
		next = NULL;
		prior = NULL;
	}
	LNode(string na, int nu) {
		name = na;
		num = nu;
		next = NULL;
		prior = NULL;
	}
};
class List {
	int len;
	LNode* head;
public:
	List(){
		head = new LNode;
		head->next = head;
		head->prior = head;
		len = 0;
	}
	void create_used(int l) {
		len = l;
		LNode* p = head, * s;
		for (int i = 1; i <= len; i++) {
			s = new LNode;
			cin >> s->name >> s->num;
			p->next = s;
			s->prior = p;
			s->next = NULL;
			p = p->next;
		}
		p->next = head;
		head->prior = p;//保证头尾相连
	}
	void insert_used(LNode* s) {
		LNode* p = head->next;
		while (p != head && p->num < s->num) {
			p = p->next;
		}
		s->next = p;
		s->prior = p->prior;
		p->prior->next = s;
		p->prior = s;
		len++;
	}
	void insert_free(int num) {
		LNode* p = head->prior,*s;
		s = new LNode("", num);
		p->next = s;
		s->prior = p;
		s->next = head;
		head->prior = s;
		len++;
	}
	void create_free(const List &used) {//不能缺少&,否则会导致拷贝而在析构时报错
		LNode* p = head;
		LNode* s;
		for (int i = 101; i <= 120; i++) {
			int ins = 1;
			for (LNode* p = used.head->next; p !=used.head; p = p->next) {
				if (p->num == i) {
					ins = 0;
					break;
				}
			}
			if (ins) {
				s = new LNode(" ", i);
				p->next = s;
				s->prior = p;
				s->next = head;
				p = p->next;
				len++;
			}
		}
		p->next = head;
		head->prior = p;
	}
	int remove_free() {
		LNode* p = head->next;
		int n = p->num;
		p->prior->next = p->next;
		p->next->prior = p->prior;
		len--;
		delete p;
		return n;//返回第一个空房间的房号
	}
	void assign(List&free) {
		string na;
		cin >> na;
		LNode* s = new LNode;
		s->name = na;
		s->num = free.remove_free();
		insert_used(s);
	}
	int return_room(const List&free,int num) {
		int tem=-1;
		LNode* p = head->next;
		while(p!=head) {
			if (p->num == num) {
				p->prior->next = p->next;
				p->next->prior = p->prior;
				len--;
				tem = p->num;
				delete p;
				break;
			}
			else p = p->next;
		}
		return tem;
	}
	void display_free() {
		LNode* p = head->next;
		int first = 1;
		while(p!=head) {
			if (!first)cout << "-";
			cout << p->num;
			first = 0;
			p = p->next;
		}
		cout << endl;
	}
	void display_used() {
		LNode* p = head->next;
		int first = 1;
		while(p!=head) {
			if (!first)cout << "-";
			cout << p->name << "("
				<< p->num << ")";
			first = 0;
			p = p->next;
		}
		cout << endl;
	}
	~List() {
		LNode* p = head->next;
		while (p != head) {
			LNode* nxt = p->next;
			delete p;
			p = nxt;
		}
		delete head;
      	len = 0;
	}
};
int main() {
	int n;
	cin >> n;
	List Used,Free;
	Used.create_used(n);
	Free.create_free(Used);

	int op_num;
	cin >> op_num;
	while (op_num--) {
		string operate;
		cin >> operate;
		if (operate == "assign") {
			Used.assign(Free);
		}
		else if (operate == "return") {
			int room_num;
			cin >> room_num;
			int res = Used.return_room(Free, room_num);
			Free.insert_free(res);
		}
		else if (operate == "display_used") {
			Used.display_used();
		}
		else if (operate == "display_free") {
			Free.display_free();
		}
	}
	return 0;
}