PAT Basic 1075 链表元素分类 (25 分)
2024-10-06 13:59:25
给定一个单链表,请编写程序将链表元素进行分类排列,使得所有负值元素都排在非负值元素的前面,而 [0, K] 区间内的元素都排在大于 K 的元素前面。但每一类内部元素的顺序是不能改变的。例如:给定链表为 18→7→-4→0→5→-6→10→11→-2,K 为 10,则输出应该为 -4→-6→-2→7→0→5→10→18→11。
输入格式:
每个输入包含一个测试用例。每个测试用例第 1 行给出:第 1 个结点的地址;结点总个数,即正整数N (≤);以及正整数K (≤)。结点的地址是 5 位非负整数,NULL 地址用 − 表示。
接下来有 N 行,每行格式为:
Address Data Next
其中 Address
是结点地址;Data
是该结点保存的数据,为 [ 区间内的整数;Next
是下一结点的地址。题目保证给出的链表不为空。
输出格式:
对每个测试用例,按链表从头到尾的顺序输出重排后的结果链表,其上每个结点占一行,格式与输入相同。
输入样例:
00100 9 10
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218
输出样例:
33218 -4 68237
68237 -6 48652
48652 -2 12309
12309 7 00000
00000 0 99999
99999 5 23333
23333 10 00100
00100 18 27777
27777 11 -1
用vector去模拟链表,会简单很多
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
struct node{
string addr;
int val;
string next;
};
int main()
{
unordered_map<string,node> m;
string ini_addr;int N,K;
cin>>ini_addr>>N>>K;
node tmp_n;
for(int i=;i<N;i++){
cin>>tmp_n.addr>>tmp_n.val>>tmp_n.next;
m[tmp_n.addr]=tmp_n;
}
tmp_n=m[ini_addr];
vector<node> bef,mid,aft;/**寻址的顺序列表*/
if(tmp_n.val<) bef.push_back(tmp_n);
else if(tmp_n.val>=&&tmp_n.val<=K) mid.push_back(tmp_n);
else aft.push_back(tmp_n);
while(tmp_n.next!="-1"){
tmp_n=m[tmp_n.next];
if(tmp_n.val<) bef.push_back(tmp_n);
else if(tmp_n.val>=&&tmp_n.val<=K) mid.push_back(tmp_n);
else aft.push_back(tmp_n);
}
bef.insert(bef.end(),mid.begin(),mid.end());
bef.insert(bef.end(),aft.begin(),aft.end());
for(int i=;i<bef.size();i++)
if(i==) printf("%s %d",bef[i].addr.c_str(),bef[i].val);
else printf(" %s\n%s %d",bef[i].addr.c_str(),bef[i].addr.c_str(),bef[i].val);
printf(" -1\n");
system("pause");
return ;
}
最新文章
- 关于Checbox的操作,已选,未选,判断
- eclipse原文件编码GBK-UTF8
- MVC4中下拉菜单和单选框的简单设计方法
- python中字符串与列表的相互转换
- 在Windows 7上安装MongoDB 2.6.7
- IP配置
- 0到N数其中三个数的全排列
- Oracle 课程六之hint
- cf701C They Are Everywhere
- c++ 如何获取系统时间 - zjnig711的信息仓库 - 博客频道 - CSDN.NET
- python程序入门 基础教程
- Linux下安装、启动、停止mongodb
- 关于Jedis是否线程安全的测试
- 排名前 16 的 Java 工具类
- Vue框架的两种使用方式
- SharePoint 2013 APP 开发示例 (五)跨域访问 Web Service (REST API)
- 【转】《iOS7 by Tutorials》系列:iOS7的设计精髓(下)
- linux命令学习(6):ps命令
- 删除一个cjson导致系统死机
- div和span与块级和行内标签