PAT乙 1075.連結串列元素分類

NO IMAGE

題目地址:1075.連結串列元素分類

易錯分析:

1.    可能存在多餘結點,即部分結點即使輸入了,也不在連結串列中

2.    可能存在大於K的陣列不存在元素

解題過程:

    建立一個結構體陣列,並用空間換時間的方法,把地址作為下標,值作為結構體物件,其中儲存Data和Next。通過一個三維向量儲存屬於不同類的元素,最後輸出即可。

程式:

#include <vector>
#include <iostream>
#include <cstdio>
using namespace std;
struct Node
{
int Data;
int Next;
}LinkList[100001];
int main(int argc, char const *argv[])
{
int start, N, K, Add, Data, Next;
cin >> start >> N >> K;
vector <int> v[3];
for (int i = 0; i < N; i  )  // 儲存結點資訊
{
cin >> Add >> Data >> Next;
LinkList[Add].Data = Data;
LinkList[Add].Next = Next;
}
while (start != -1)  // 這裡不要用for迴圈,因為會存在有多餘結點的情況。
{
if (LinkList[start].Data < 0)   // 如果小於0放入第一個向量
v[0].push_back(start);
else if (LinkList[start].Data > K)  // 如果大於K放入第三個向量
v[2].push_back(start);
else                        // 如果在區間內放入第二個向量
v[1].push_back(start);
start = LinkList[start].Next;       // start往後移
}
int flag = 0;       // 方便輸出
/* 這種輸出方式可以避免沒有大於K的情況而出現單獨輸出v[3]最後一個元素出現問題 */     
for (int i = 0; i < 3; i  )         
for (int j = 0; j < v[i].size(); j  )
{
if (flag == 0)
{
printf("%05d %d ", v[i][j], LinkList[v[i][j]].Data);
flag = 1;
}
else
printf("%05d\n%05d %d ", v[i][j], v[i][j], LinkList[v[i][j]].Data);
}
printf("-1");
return 0;    
}