DS链表—学生宿舍管理-布布扣-bubuko.com

假设某校有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

提示

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; //反向输出

}

#include <iostream>
#include<list>
using namespace std;
void initial(list<int>&L1,list<int>&L2,list<string>&L3)
{
    list<int>::iterator p1=L1.begin(),p2=L2.begin();
    list<string>::iterator p3=L3.begin();
    for(int i=0;i<20;i++)
    {
        L1.insert(p1,101+i);
        p1++;
    }
    L1.sort();
    int n,k;
    string temp;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>temp;
        cin>>k;
        for(p1=L1.begin();p1!=L1.end();p1++)
        {
            if(*p1==k)
            {
                L1.erase(p1);
                L2.insert(L2.begin(),k);
                L2.sort();
                for(p2=L2.begin(),p3=L3.begin();p2!=L2.end();p2++,p3++)
                {
                    if(*p2==k)
                        L3.insert(p3,temp);
                }
                break;
            }
        }
    }
}
int main()
{
    int n,k;
    list<int>L1,L2;
    list<string>L3;
    initial(L1,L2,L3);
    list<int>::iterator p1=L1.begin(),p2=L2.begin();
    list<string>::iterator p3=L3.begin();
    string c1,c2;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>c1;
        if(c1=="assign")
        {
            cin>>c2;
            k=*L1.begin();
            L2.insert(L2.begin(),k);
            L2.sort();
            for(p2=L2.begin(),p3=L3.begin();p2!=L2.end();p2++,p3++)
                {
                    if(*p2==k){
                        L3.insert(p3,c2);
                        break;
                    }
                }
            L1.erase(L1.begin());
        }
        if(c1=="return")
        {
            cin>>k;
            for(p2=L2.begin(),p3=L3.begin();p2!=L2.end();p2++,p3++)
                {
                    if(*p2==k)
                    {
                        L1.insert(L1.end(),k);
                        L2.erase(p2);
                        L3.erase(p3);
                        break;
                    }
                }
        }
        int flag=1;
        if(c1=="display_used")
        {
            flag=1;
            for(p2=L2.begin(),p3=L3.begin();p2!=L2.end();p2++,p3++)
            {
                if(flag==1)
                {
                    cout<<*p3<<"("<<*p2<<")";
                    flag=0;
                }
                else
                    cout<<"-"<<*p3<<"("<<*p2<<")";
            }
            cout<<endl;
        }
        if(c1=="display_free")
        {
            flag=1;
            for(p1=L1.begin();p1!=L1.end();p1++)
            {
                if(flag==1)
                {
                    cout<<*p1;
                    flag=0;
                }
                else
                    cout<<"-"<<*p1;
            }
            cout<<endl;
        }
    }
    return 0;
}

DS链表—学生宿舍管理

题目描述

输入

输出

样例输入

样例输出

提示