題目鏈接
https://pintia.cn/problem-sets/994805260223102976/problems/994805296180871168
思路
1.設定結構體，設一個堆疊
struct node { int address, data, next, order; };2.order的初始值為maxn，接著從first開始遍歷，每k個node入堆疊，同時設定order=count++
3.sort按照order由小到大排序，最后遍歷i：0~count，輸出，
代碼
#include <iostream>
#include <algorithm>
#include <stack>
#include <cstdio>
using namespace std;
const int maxn = 100010;//5位的最大下標
struct node
{
int address, data, next, order;
};
bool cmp(node a, node b) {
return a.order < b.order;
}
node list[maxn];
int main()
{
for (int i = 0; i < maxn; i++)
{
list[i].order = 2 * maxn;
}
int first, n, k,index;
cin >> first >> n >> k;
for (int i = 0; i < n; i++)
{
cin >> index;
list[index].address = index;
cin >> list[index].data >> list[index].next;
}
int count = 0;
stack<node> stk;
for (int i = first; i != -1 || stk.size() == k;)
{
if (stk.size() != k) {
stk.push(list[i]);
i = list[i].next;
}
else {
while (!stk.empty()) {
list[stk.top().address].order = count++;
stk.pop();
}
}
}
stack<node> stk_temp;
while (!stk.empty()) {
stk_temp.push(stk.top());
stk.pop();
}
while (!stk_temp.empty()) {
list[stk_temp.top().address].order = count++;
stk_temp.pop();
}
sort(list, list + maxn, cmp);
for (int i = 0; i < count; i++)
{
if (i != count - 1) {
printf("%05d %d %05d\n", list[i].address, list[i].data, list[i + 1].address);
}
else {
printf("%05d %d -1", list[i].address, list[i].data);
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/65490.html
標籤：其他
上一篇：資料結構導論之第七章排序
下一篇：資料結構導論之第六章查找表