1052 Linked List Sorting （25 分）
A linked list consists of a series of structures, which are not necessarily adjacent in memory. We assume that each structure contains an integer key and a Next pointer to the next structure. Now given a linked list, you are supposed to sort the structures according to their key values in increasing order.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive N (<10?5??) and an address of the head node, where N is the total number of nodes in memory and the address of a node is a 5-digit positive integer. NULL is represented by ?1.
Then N lines follow, each describes a node in the format:
Address Key Next
where Address is the address of the node in memory, Key is an integer in [?105,105], and Next is the address of the next node. It is guaranteed that all the keys are distinct and there is no cycle in the linked list starting from the head node.
Output Specification:
For each test case, the output format is the same as that of the input, where N is the total number of nodes in the list and all the nodes must be sorted order.
Sample Input:
5 00001
11111 100 -1
00001 0 22222
33333 100000 11111
12345 -1 33333
22222 1000 12345
Sample Output:
5 12345
12345 -1 00001
00001 0 11111
11111 100 22222
22222 1000 33333
33333 100000 -1
分析
此題考查排序。解題思路比較常規(guī)，屬于簡單題，即將所有數(shù)進(jìn)行排序，自然就能得到有序的鏈表。但是解此題幾個(gè)注意點(diǎn)：
1.題目中給出的節(jié)點(diǎn)雖然在memory(內(nèi)存)中,但是不一定在鏈表上，因此需要根據(jù)頭結(jié)點(diǎn)head進(jìn)行一次遍歷收集鏈表上的節(jié)點(diǎn)，然后進(jìn)行排序。
2.有可能所有的節(jié)點(diǎn)都不在一個(gè)鏈表上，此時(shí)鏈表的size是0，頭節(jié)點(diǎn)是-1（代表NULL）。
注:注意點(diǎn)1在第一次提交時(shí)已經(jīng)想到，但是注意點(diǎn)2有點(diǎn)隱蔽，在提交時(shí)報(bào)段錯(cuò)誤,自然想到溢出或越界，那只能是最后輸出序列時(shí)默認(rèn)節(jié)點(diǎn)數(shù)大于等于1導(dǎo)致的越界，修改這個(gè)錯(cuò)誤之后，錯(cuò)誤提示變?yōu)?code>答案錯(cuò)誤,于是開始思考頭結(jié)點(diǎn)錯(cuò)誤，此時(shí)頭結(jié)點(diǎn)參考的是head，最后看博客[1]發(fā)現(xiàn)此時(shí)的頭結(jié)點(diǎn)是-1。與其說這個(gè)測(cè)試點(diǎn)隱蔽，比如說這個(gè)測(cè)試點(diǎn)詭異，因?yàn)橐呀?jīng)給出了頭結(jié)點(diǎn)的地址，說明內(nèi)存中頭結(jié)點(diǎn)是存在的，至少在訪問的時(shí)候，鏈表能收錄一個(gè)節(jié)點(diǎn)，即頭結(jié)點(diǎn)head，并且題目也沒有明確說鏈表中節(jié)點(diǎn)個(gè)數(shù)為0不能稱為為鏈表，這便是我認(rèn)為這個(gè)詭異的理由。</font>其實(shí)發(fā)現(xiàn)PAT中有很多這種至少現(xiàn)在無法理解測(cè)試點(diǎn)，或許未讀懂題意所致，或許編程題就應(yīng)該這樣嚴(yán)謹(jǐn)?shù)乜紤]，反正做一題記住一題的刁鉆測(cè)試點(diǎn)~~
博客[1]發(fā)現(xiàn)sort的cmp函數(shù)的一個(gè)新視角，其實(shí)sort本質(zhì)是排序，我們也可以用它來控制元素的移動(dòng)，以設(shè)定條件，通過條件的真假，間接控制元素的大小關(guān)系，從而調(diào)節(jié)元素間在排序過程中的移動(dòng)。這個(gè)提這一點(diǎn)，主要因?yàn)橹白鲱}一直思想僵化的將sort的cmp函數(shù)針對(duì)的是整個(gè)指定序列的排序，其實(shí)這個(gè)在cmp函數(shù)里面通過設(shè)定flag參數(shù)實(shí)現(xiàn)對(duì)指定序列中符合條件的元素進(jìn)行排序，對(duì)這個(gè)現(xiàn)象做一點(diǎn)記錄，日后再博客是可以打破思維僵化~~~。
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
map<int,int> val_ad,ad_val,ad_next;
vector<int> val;
int main(){
int n,head;
cin>>n>>head;
for(int i=0;i<n;i++){
int a,b,c;
cin>>a>>b>>c;
val_ad[b]=a;
ad_val[a]=b;
ad_next[a]=c;
}
for(int i=head;i!=-1;i=ad_next[i]){
val.push_back(ad_val[i]);
}
sort(val.begin(), val.end());
cout<<val.size();
if(val.size()==0){
printf(" -1");
return 0;
}
printf(" %05d\n",val_ad[val[0]] );
for(int i=0;i<val.size()-1;i++){
printf("%05d %d %05d\n",val_ad[val[i]],val[i],val_ad[val[i+1]] );
}
printf("%05d %d -1\n", val_ad[val[val.size()-1]],val[val.size()-1]);
return 0;
}
