C言語數據構造 鏈表與歸並排序實例詳解。本站提示廣大學習愛好者:(C言語數據構造 鏈表與歸並排序實例詳解)文章只能為提供參考,不一定能成為您想要的結果。以下是C言語數據構造 鏈表與歸並排序實例詳解正文
C言語數據構造 鏈表與歸並排序實例詳解
歸並排序合適於對鏈表停止舊址排序,即只改動指針的銜接方式,不交流鏈表結點的內容。
歸並排序的根本思想是分治法:先把一個鏈表聯系成只要一個節點的鏈表,然後依照一定順序、自底向上兼並相鄰的兩個鏈表。
只需保證各種大小的子鏈表是有序的,那麼最後前往的鏈表就一定是有序的.
歸並排序分為聯系和兼並兩個子進程。聯系是用遞歸的辦法,把鏈表對半聯系成兩個子鏈表;兼並是在遞歸前往(回朔)的時分,把兩個有序鏈表兼並成一個有序鏈表。
(留意:只要一個節點的鏈表一定是有序的)
這裡sort進程就是聯系進程;merge進程就是兼並且排序的進程
說到聯系鏈表,那麼問題來了:鏈表不是隨機訪問的,我怎樣知道聯系點在哪裡?一個珍貴的經歷就是:維護兩個指針,一快一慢。快指針每次後移兩個單位,慢指針每次只挪動一個單位。當快指針挪動到tail或許最後一個無效節點時,慢指針就指向了兩頭的節點。
sort進程:
Node* sort (Node* beg) { if(beg==tail || beg->next==tail) return beg; Node* a = beg; Node* b = beg->next; while(b!=tail && b->next != tail) { a = a->next; b = b->next->next; } b = a->next; //the beginning of right part a->next = tail; //the end of left part return merge(sort(beg), sort(b)); }
把鏈表聯系之後就要兼並。merge操作傳入的參數是兩個有序鏈表,前往的是兼並後的有序的鏈表。兩個有序鏈表復雜拼接之後不一定是有序的,需求對每一個元素重排。這個重排的進程是從兩個鏈表各自最小(最大)元素開端,誰小(大)就把誰放到新的鏈表裡。
Node* LinkedList<T>::merge(Node* a, Node* b) { Node dummy = Node(); Node* head = &dummy; // temp是正在兼並的表的節點 Node* temp = head; while(a!=tail && b!=tail) //逐一比擬鏈表a和鏈表b的每個元素 { if(a->data <= b->data) { // 假如a比b小, 那麼以後結點的後繼就是a temp->next = a; // 把以後節點移向後繼 temp = a; // a後移 a = a->next; } else { temp->next = b; temp = b; b = b->next; } // 假如原表a曾經排完,那麼新表前面就放b的剩余元素 // 否則依然以a為規范和b停止比擬 temp->next = (a==tail) ? b : a; } return head->next; }
感激閱讀,希望能協助到大家,謝謝大家對本站的支持!