1075.連結串列元素分類(25)

1075.連結串列元素分類(25)

PAT (Basic Level) Practise (中文)

1075.連結串列元素分類(25)

(這是我人生中第一篇CSDN部落格,這個題17號考的,18號在寢室裡請教了老師後AC的,考試的時候主要錯誤是STL erase的使用。還算新鮮,網上的分享應該還不多。)
*時間限制
400 ms
記憶體限制
65536 kB
程式碼長度限制
8000 B
判題程式
Standard
作者
CHEN, Yue*
給定一個單連結串列,請編寫程式將連結串列元素進行分類排列,使得所有負值元素都排在非負值元素的前面,而[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行給出:第1個結點的地址;結點總個數,即正整數N (<= 105);以及正整數K (<=1000)。結點的地址是5位非負整數,NULL地址用-1表示。

接下來有N行,每行格式為:

Address Data Next

其中Address是結點地址;Data是該結點儲存的資料,為[-105, 105]區間內的整數;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 V先實現靜態連結串列。再利用一個vector ans儲存要輸出的結點。“使得所有負值元素都排在非負值元素的前面”,“[0, K]區間內的元素都排在大於K的元素前面”——整個程式被這3個條件分成了3個迴圈,每個迴圈內執行的語句都類似——遍歷容器,將符合條件的結點壓入ans。這樣子是不會改變段內部的順序的!得到的連結串列應該是【負數】 【0,k區間內的數】 【大於k的數】。維護好ans後,按照要求輸出,注意ans[i].next=ans[i 1].address;,要更改結點的next資訊!注意最後一個結點的next域是-1。

錯誤分析

考試的時候一直有stack的想法,覺得已經到ans的結點應該在V中刪除,結果沒有注意STL vector中的細節,出了錯誤,導致我第二個迴圈不能很好的執行if判斷,在考場裡百思不得其解,最後導致損失了很多分數,成績不甚理想。
在一個用迭代器遍歷容器的迴圈裡,一定要注意刪除erase方法的使用!!!所以在此我就不刪除了,如果想要刪除已經入ans的結點,應該使用如下程式碼:

    for (auto it = V.begin(); it<V.end();)
{
if (it->data >= 0 && it->data <= K)
{
ans.push_back(*it);
it = V.erase(it);
}
else
{
it  ;
}
}

以下為原始碼

/*
Name: 1075. 連結串列元素分類(25)
Author: spencercjh
Date: 2017年9月18日 08:26:56
Description:PAT Basic Level C/C   9月17日考題
*/
#include<iostream>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<numeric>
using namespace::std;
struct node
{
int address;
int data;
int next;
};
int main()
{
int begin,N,K;
node table[100000];
scanf("%d %d %d",&begin,&N,&K);
node* A=new node[N];
vector<node> V;
for(int i=0; i<N; i  )
{
scanf("%d %d %d",&A[i].address,&A[i].data,&A[i].next);
table[A[i].address]=A[i];
}
for(int add=begin; add!=-1; add=table[add].next)
V.push_back(table[add]);
vector<node> ans;
for(int i=0; i<V.size(); i  )
{
if(V[i].data<0)
{
ans.push_back(V[i]);
//      auto it=V.erase(V.begin() i);   考試的時候執行了這2行語句,程式就不能有效執行了,去掉後就                                                           
//      it=V.begin() i;                 AC,很遺憾……
}
}
for(int i=0; i<V.size(); i  )
{
if(V[i].data>=0&&V[i].data<=K)
{
ans.push_back(V[i]);
//      auto it=V.erase(V.begin() i);
//      it=V.begin() i;
}
}
for(int i=0; i<V.size(); i  )
{
if(V[i].data>K)
{
ans.push_back(V[i]);
//      auto it=V.erase(V.begin() i);
//      it=V.begin() i;
}
}
for(int i=0; i<ans.size(); i  )
{
if(i!=ans.size()-1)
{
ans[i].next=ans[i 1].address;
//      cout<<ans[i].address<<" "<<ans[i].data<<" "<<ans[i].next<<endl;//  輸出五位補0的數字
printf("%05d %d %05d\n",ans[i].address,ans[i].data,ans[i].next);
}
else
//      cout<<ans[i].address<<" "<<ans[i].data<<" "<<-1<<endl;
printf("%05d %d %d\n",ans[i].address,ans[i].data,-1);
}
return 0; 
}

AC