鏈結串列的排序問題

Question

小弟最近要交作業...老師出了一個關於鏈結串列的問題!
就是"在鏈結串列加入節點"...就是把輸入的數值列出來...
但是老師似乎是心情不太好...改了題目...
除了要加入節點...還要把輸入的數值由小到大排列...
"在鏈結串列加入節點"這個我們會...但是由小到大排列...
我們嘗試很久都失敗...不知道有哪位高手大大可以幫小弟解惑一下...
小弟必將以重'點數'回禮!!
以下是"在鏈結串列加入節點" :
------------------------------------------------------------------------------------------------------------
#include
#include
typedef struct list /* 宣告鏈結串列結構 */
{
int data; /* 資料欄位 */
struct list *link; /* 指標欄位 */
}node;
void main( )
{
node *head=NULL; /* 鏈結串列起始指標 */
node *new_node; /* 新節點指標 */
node *ptr; /* 走訪鏈結串列指標 */
int input; /* 使用者輸入值 */
printf("請輸入Ctrl+Z表示資料輸入結束\n");
printf("請輸入節點內容(int)=>\n");
while(scanf("%d", &input) != EOF)
{ /* 若輸入值為EOF(檔案結束碼)才停止迴圈 */
new_node=(node *)malloc(sizeof(node)); /* 配置記憶體空間 */
if(new_node == NULL) /* 檢查記憶體指標 */
{
printf("記憶體配置失敗!\n");
exit(1); /* 結束程式 */
}
new_node->data=input; /* 將輸入值放入新節點的資料欄位 */
if(head == NULL) /* 若鏈結串列為空串列時 */
{
head=new_node; /* 鏈結串列的起始節點即為新加入的節點 */
new_node->link=NULL; /* 將新節點的鏈結欄位設為NULL */
}
else /* 先走訪至最後一個節點，再將新節點接到後面 */
{
for(ptr=head; ptr->link!=NULL; ptr=ptr->link);
new_node->link=ptr->link;
ptr->link=new_node;
}
}
printf("\n印出鏈結串列內容:\n");
/* 利用指標走訪鏈結串列 */
for(ptr=head; ptr!=NULL; ptr=ptr->link)
printf("[%d]", ptr->data); /* 印出鏈結串列節點內容 */
printf("\n");
}
---------------------------------------------------------------------------------------------------------------
要修改或是加入來達到把輸入的數值由小到大排列!
希望有好心的高手可以幫小弟的忙...感恩!!

Answer 1

我將您的程式這三行處理排序的地方，也就是原本用作照輸入順序排序的地方
--------------------------------------------------------------------------------------------
for(ptr=head; ptr->link!=NULL; ptr=ptr->link);
new_node->link=ptr->link;
ptr->link=new_node;
--------------------------------------------------------------------------------------------
改成以下程式，完成由小到大的排列，並且加了比程式還多的註解(汗):
--------------------------------------------------------------------------------------------
if(new_node->data < head->data){ /*如果 new_node->link=head; /*將new_node的link指向原本的head*/
head=new_node; /*將head設為new_node*/
}else{
ptr=head; /*ptr從頭開始*/
while(ptr->link!=NULL){
/*注意!!new_node跟目前ptr的下一筆比較 即ptr if(new_node->data < ptr->link->data){
break; /*此還未插入資料，只是跳出while迴圈，取得目前ptr，就是插入在目前ptr之後*/
}
ptr=ptr->link; /*ptr指向下一筆*/
}

/*插入資料在此處理，【ptr】→【new_node】→【原本ptr的後一筆資料】*/
if(ptr->link==NULL){ /*如果ptr為null代表此時ptr為資料結尾，也就是最後一筆，直接將new_node銜接在其後*/
ptr->link=new_node; /*目前結尾資料link指向new_node*/
new_node->link=NULL; /*new_node的link設為null*/
}else{ /*ptr不為null，代表在中間插入*/
new_node->link=ptr->link; /*new_node的link指向原本的ptr後一筆*/
ptr->link=new_node; /*將ptr改為link指向new_node*/
}
}
--------------------------------------------------------------------------------------------
希望對您有幫助，這些註解寫了比寫程式還要多的時間，希望可以幫助您學習，而不只是交作業而已，如果有問題歡迎您在發問。

補充一下，我的寫法式在插入新節點時就作排序，而且排序的是整個節點的排序，樓下的米奇大大排序方式應該屬於節點的data交換。
以下是我的流程：
判斷是否新節點<第一個節點，確保第一個節點是最小的
是：新節點成為第一個節點，並指向原本的第一個節點
【new_node】→【head】
否：新節點以迴圈與下一個節點比較。
原本的資料鏈結【第一個節點】→【第二個節點】，
當ptr為第一個節點時(此時new_node->data > ptr->data)，new_node其實是與第二個節點比較(ptr->link->data)，如果 new_node->data < ptr->link->data 代表new_node應該插入在目前的ptr(第一個節點)與ptr的下一個節點(第二個節點)之間(使用break跳出while迴圈，此時ptr為第一個節點)，若否ptr就繼續往下一個節點移動。

ptr在迴圈外作插入節點，ptr指向新節點，新節點再指向ptr的後一個節點。
排序後的資料鏈結：【第一個節點】→【新節點】→【第二個節點】，

此時如果ptr為null代表直到迴圈結束都沒有找到應插入位置，即新節點為最大的，直接放在資料鏈結的最後一筆。
此狀況排序後的資料練結：【第一個節點】→【第二個節點】→【新節點】

2005-11-09 01:13:09 補充：
阿~請您複製程式碼到您的編譯器貼上在處理一下縮排，會容易看懂。

2005-11-09 11:53:30 補充：
米奇大大的寫法是先將new_node照順序新增到資料結尾，在要print以前在重新排序各節點的data值(這裡我想排序節點應該也可以吧)，資結當初沒好好學，今天見識到實作氣泡排序，小弟又受益了。

Answer 2

阿拉布丁 大大血滴好複雜~布過還是看懂ㄌ0.0+

Answer 3

縮排問題是奇摩知識網的問題
任何縮排放上去都會變成沒有縮排

Answer 4

這個程式是你自己寫的嗎？
如果是的話我覺得你很厲害~單向鏈結觀念很清楚QQ

(1)首先在main函數內宣告一個
int count=0;
new_node->data=input; /* 將輸入值放入新節點的資料欄位 */
count++;//count放在這邊，如果有加入新節點成功的話就會累計

(2)在印出陣列之前呼叫sort函數排列，即
sort(head,count);//排列大小
printf("\n印出鏈結串列內容:\n");

(3)sort函數放在main函數的上方，typedef的下方，因為我懶得宣告函數原型@@

void sort(node *p,int count){//*p參數為原本鏈結的首節點，count為資料數量
int i,value;
node *ptr;//設定一個暫時的指標
ptr=p;//把p送到暫時指標內

for (i=1;i<=count;i++){//for之內的排序就是泡沫排序法
while(ptr->link !=NULL){//如果ptr的下個鏈結不為空的則瘋狂回圈
if ( ptr->link->data < ptr->data ){//if 裡面的為比大小然後把小的排在前面
value=(ptr->link)->data;
(ptr->link)->data=ptr->data;
ptr->data=value;
}
ptr=ptr->link;//ptr指向首節點，把ptr指向後一個節點，第二節點再跟第三比
}//while迴圈跳出時，能保證最大的數值跑到最後一個鏈結
ptr=p;//記得把ptr重新指向首節點，因為下次while要重首節點開始
}
}
P.S.想了大概一個小時，不過感謝你也讓我學到很多0.0