程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 一步一步寫算法(之鏈表排序)

一步一步寫算法(之鏈表排序)

編輯:關於C

 

【 聲明:版權所有,歡迎轉載,請勿用於商業用途。  聯系信箱:feixiaoxing @163.com】

 

 

 

 

    相比較線性表的排序而言,鏈表排序的內容稍微麻煩一點。一方面,你要考慮數據插入的步驟;另外一方面你也要對指針有所顧慮。要是有一步的內容錯了,那麼操作系統會馬上給你彈出一個exception。就鏈表的特殊性而言,適合於鏈表的排序有哪些呢?

 

    (1)插入排序    (適合)

 

    (2)冒泡排序    (適合)

 

    (3)希爾排序    (適合)

 

    (4)選擇排序    (適合)

 

    (5)快速排序    (不適合)

 

    (6)合並排序    (不適合)

 

    (7)基數排序     (不適合)

 

    (8)堆排序         (不適合)

 

    其實,一般來說。如果涉及到數據之間的相對關系調配,那麼只適合線性排序;如果只是數據內容之間的相互交換,那麼這種排序方法也比較適合鏈表的排序。快速排序、合並排序、堆排序都涉及到了中間值的選取問題,所以不大適合鏈表排序。

 

    為了說明鏈表排序是怎麼進行的,我們可以利用插入排序作為示例,描述鏈表是怎麼進行插入排序的。

 

    a)首先遍歷節點,一邊是排序好的節點,一邊是待排序的節點

 

 

void sort_for_link_node(NODE** ppNode) 

    NODE* prev; 

    NODE* curr; 

 

    if(NULL == ppNode || NULL == *ppNode) 

        return; 

 

    curr = (*ppNode) ->next; 

    (*ppNode) ->next = NULL; 

 

    while(curr){ 

        prev = curr; 

        curr = curr->next; 

        insert_for_sort_operation(ppNode, prev); 

    } 

 

    return; 

void sort_for_link_node(NODE** ppNode)

{

       NODE* prev;

       NODE* curr;

 

       if(NULL == ppNode || NULL == *ppNode)

              return;

 

       curr = (*ppNode) ->next;

       (*ppNode) ->next = NULL;

 

       while(curr){

              prev = curr;

              curr = curr->next;

              insert_for_sort_operation(ppNode, prev);

       }

 

       return;

}

 

    b)對於待插入的節點,選擇合適的位置插入即可

 

 

void insert_for_sort_operation(NODE** ppNode, NODE* pNode) 

    NODE* prev; 

    NODE* cur; 

 

    /* 在第一個數據之前插入pNode */ 

    if(pNode->data < (*ppNode)->data){ 

        pNode->next = *ppNode; 

        *ppNode = pNode; 

        return; 

    } 

 

    cur = *ppNode; 

    while(cur){ 

        if(pNode->data < cur->data) 

            break; 

 

        prev = cur; 

        cur = cur->next; 

    } 

 

    pNode->next = prev->next; 

    prev->next = pNode; 

    return; 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved