题目描述
假设某校有20间宿舍，宿舍编号101，102，...,120。每间只住一名学生。初始部分宿舍已用。用两个链表（已用宿舍链表和可用宿舍链表）维护宿舍的管理，实现宿舍分配、宿舍交回。
约定已用宿舍链表按宿舍号升序链接。初始可用宿舍链表也按宿舍号升序链接。
宿舍分配从可用宿舍链表中摘取第一间宿舍分配给学生。学生交回的宿舍挂在可用宿舍链表最后。
备注：使用list容器或静态链表。不用考虑宿舍分配和交回不成功的情况。
输入
初始宿舍状态，第一行输入n，表示已用宿舍n间
后跟n行数据，每行格式为：宿舍号 学生姓名
操作次数m，后跟m行操作，操作格式如下：
assign 学生 //为学生分配宿舍，从可用宿舍链表头摘取一间宿舍，
//按宿舍号升序挂在已用宿舍链表中。
return 宿舍号 //学生退宿舍，删除已用宿舍链表中对应结点，
//挂在可用宿舍链表尾部。
display_free //输出可用宿舍链表信息。
display_used //输出已用宿舍链表信息。
输出
display_free依次输出当前可用宿舍链表中的宿舍号，具体格式见样例。
display_used依次输出当前已用宿舍链表中的学生和宿舍号，具体格式见样例。
样例查看模式
正常显示查看格式
输入样例1 <-复制
输出样例1
提示
list是一种序列式容器, list实际上就构成了一个双向循环链,
List类使用的参考代码
包含头文件 ： #include
List定义和初始化：
listlst1; //创建空list
list lst2(5); //创建含有5个元素的list
listlst3(3,2); //创建含有3个元素的list
listlst4(lst2); //使用lst2初始化lst4
listlst5(lst2.begin(),lst2.end()); //同lst4
创建一个list对象l（注意list是模板类）：list 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
using namespace std;
typedef list 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; //反向输出
}
语言: 编译选项
主题:
167
cout<name<<"(";
168
cout<data<<")";
169
p=p->next;
170
if (p!=NULL)
171
{
172
cout<<"-";
173
}
174
}
175
cout<176
}
177
intmain()
#include
using namespace std;
#define ok 0
#define error -1class ListNode
{
public:int data;string name;ListNode* next;ListNode(){next = NULL;}
};class LinkList
{
public:ListNode* head;int len;LinkList();~LinkList();ListNode* LL_index(int i);int LL_insert(int i, int item, string name);int LL_del(int i);int getlen();int assign(LinkList& f, string n);int fanhui(LinkList& f, int number);void display_free();void display_used();
};
LinkList::LinkList()
{head = new ListNode();len = 0;
}
LinkList::~LinkList()
{ListNode* p, * q;p = head;while (p != NULL){q = p;p = p->next;delete q;}len = 0;head = NULL;
}
ListNode* LinkList::LL_index(int i)
{if (i < 0 || i > len){return NULL;}ListNode* p = head;for (int j = 0; j < i; j++){p = p->next;}return p;
}
int LinkList::LL_insert(int i, int item, string n)
{if (i <= 0 || i > len + 1){return error;}else{ListNode* p = LL_index(i - 1);ListNode* s = new ListNode();s->data = item;s->name = n;s->next = p->next;p->next = s;len += 1;return ok;}
}
int LinkList::LL_del(int i)
{if (i <= 0 || i > len){return error;}else{ListNode* p = LL_index(i - 1);ListNode* s = p->next;p->next = s->next;p = NULL;delete p;len -= 1;return ok;}
}
int LinkList::getlen()
{return len;
}
int LinkList::assign(LinkList& f, string n)
{//传进来的是空闲的房间ListNode* p = f.LL_index(1);for (int i = 1; i <= 20; i++){ListNode* q = LL_index(i);//已使用的房间if (q->next != NULL){if (p->data < q->data){LL_insert(i, p->data, n);break;}}else{LL_insert(i, p->data, n);break;}}//空余的首个房间要被释放f.LL_del(1);delete p;return ok;
}
int LinkList::fanhui(LinkList& f, int item)
{for (int i = 1; i <= 20; i++){ListNode* p = LL_index(i);if (p->data == item){LL_del(i);break;}}f.LL_insert(f.getlen() + 1, item, "");;return ok;
}
void LinkList::display_used()
{ListNode* p = head;p = head->next;while (p){cout << p->name << "(";cout << p->data << ")";p = p->next;if (p != NULL){cout << "-";}}cout << endl;}
void LinkList::display_free()
{ListNode* p = head;p = head->next;while (p){cout << p->data;p = p->next;if (p != NULL){cout << "-";}}cout << endl;
}
int main()
{int n, item;string name, op;LinkList used, free;for (int i = 1; i <= 20; i++){free.LL_insert(i, i + 100, "");}cin >> n;for (int i = 0; i < n; i++){cin >> name;cin >> item;used.LL_insert(i + 1, item, name);free.LL_del(item - 100 - i);//得到的空闲和工作的房间都是按顺序排列的}cin >> n;while (n--){cin >> op;if (op == "assign"){cin >> name;used.assign(free, name);}else if (op == "return"){cin >> item;used.fanhui(free, item);}else if (op == "display_free"){free.display_free();}else{used.display_used();}}return 0;
}
