陳祎智

　 實驗報告<2> 1. 問題描述: 雙向鏈表的排序。

　要求：

　輸入一個雙向鏈表，顯示些雙向鏈表并對此雙向鏈表排序

　2.課題分析(結構圖):

　 3.數據結構的設計: typedef struct node { int info;

　 struct node *llink,*rlink;

　}NODE; 雙向鏈表的排序 雙向鏈表存儲結構 快速排序定義 輸入數據結點

　4.流程圖

　5．源程序：

　#include<iostream.h> #include<stdlib.h> #include <stdio.h> 開始 創建鏈表 初始化鏈表 從中間分成兩部 排序鏈表 插入 10 個值 輸出排序鏈表 終止

　typedef struct Link/*雙向鏈表結構體*/ {

　int data;

　struct Link *lift;

　struct Link *right; }linkx,*linky; linky Init();/*建立雙向鏈表*/ void PrLink(linky p);/*輸出雙向鏈表*/ linky Sort(linky head);/*對雙向鏈表排序*/ linky S head,linky one,linky two);/*任意交換雙向鏈表兩個結點的地址*/ void main(void) {

　linky head;

　head=Init();

　head=Sort(head);

　PrLink(head); } linky (Init())/*建立鏈表*/ {

　linky p,q,head;

　int n=0;

　head=p=q=(linky)malloc(sizeof(linkx));

　 printf("排序前的鏈表: ");

　scanf("%d",&p->data);/*輸入數據*/

　head->lift=NULL;

　n++;

　while(n!=10)/*一直輸入到規定的數字個數停止*/ {

　 q=p;

　 p=(linky)malloc(sizeof(linkx));

　 scanf("%d",&p->data);/*輸入數據*/

　 q->right=p;

　 p->lift=q;

　 n++; }

　p->right=NULL;

　return(head); } linky S head,linky one,linky two)/*任意交換兩個結點*/ {linky temp;

　if(one->lift==NULL&&two->right==NULL)/*首和尾巴的交換*/

　{

　 if(one->right==two)/*只有兩個結點的情況下*/

　{

　two->right=one;

　two->lift=NULL;

　one->lift=two;

　one->right=NULL;

　head=two;

　 }

　 else/*有間隔的首尾交換*/

　 {

　 one->right->lift=two;

　 two->lift->right=one;

　 two->right=one->right;

　 one->lift=two->lift;

　 two->lift=one->right=NULL;

　 head=two;/*尾結點成為頭結點*/

　 }

　}

　else if(two->right==NULL)/*尾和任意一個交換*/

　 {

　if(one->right==two)/*交換最后兩個結點*/

　{

　one->lift->right=two;

　 two->lift=one->lift;

　two->right=one;

　one->lift=two;

　one->right=NULL;

　}

　else/*和前面其他結點交換*/

　{

　temp=two->lift;

　temp->right=one;

　one->lift->right=two;

　one->right->lift=two;

　two->lift=one->lift;

　two->right=one->right;

　one->lift=temp;

　one->right=NULL;

　}

　 }

　else if(one->lift==NULL)/*頭和任意一個交換*/

　{

　if(one->right==two)/*交換頭兩個結點*/

　 {

　 two->right->lift=one;

　one->right=two->right;

　 one->lift=two;

　 two->right=one;

　 two->lift=NULL;

　 head=two;

　 }

　else/*頭結點和后面其他結點交換*/

　 {

　temp=one->right;

　temp->lift=two;

　one->lift=two->lift;

　one->right=two->right;

　two->lift->right=one;

　two->right->lift=one;

　two->right=temp;

　two->lift=NULL;

　 head=two;/*交換的結點成為頭結點*/

　 }

　}

　else/*當中的任意兩個交換*/

　 {

　 if(one->right==two)/*交換連在一起的兩個結點*/

　{

　 temp=one->lift;

　 one->lift->right=two;

　 one->right->lift=two;

　 one->lift=two;

　 one->right=two->right;

　 two->right->lift=one;

　 two->right=one;

　 two->lift=temp;

　 }

　 else/*交換隔開的兩個結點*/

　 {

　 one->lift->right=two;

　 one->right->lift=two;

　 one->lift=two->lift;

　 temp=one->right;

　 one->right=two->right;

　 two->lift->right=one;

　 two->right->lift=one;

　 two->right=temp;

　 two->lift=one->lift;

　 }

　 }

　return(head); } linky Sort(linky head)/*對鏈表排序*/ {

　linky i,j,t,p;

　int max;

　p=head;

　for(i=p;i->right!=NULL;i=i->right)/*用選擇法的思想對這些結點排序*/

　 {

　max=i->data;

　for(j=i->right;j!=NULL;j=j->right)

　 if(j->data<max)

　 {

　 max=j->data;

　 t=j;

　 }

　if(max!=i->data)/*假如沒有找到比 i 小的結點*/

　{

　head=S);/*因為最終返回的是頭結點,而頭結點又有可能變化,所以每次頭結點返回*/

　i=t;

　 }

　 }

　return(head); } void PrLink(linky p)/*輸出鏈表*/ {

　linky q;

　printf("排序后: ");

　do

　{

　 q=p;

　 printf("%d ",p->data);

　 p=p->right;

　 free(q);/*釋放輸出結點*/

　}

　while(p!=NULL);

　}

　6．調試記錄：

　 第一次輸入 136 134 158 123 197 124 156 170 103 101 實現排序

　 第二次調試 輸入 12367 15842 12564 13729 49875 1546 15423 15794 54612 1543

　 ７．軟件說明

　程序調試運行成功后，排序前隨機輸入十個不同的數值，快速排序后將由小到大輸出這十個數值的排序。如上圖說明

　. 8. 設計總結

　一周的上機實踐課程結束了，我們也按要求完成了實踐內容，這次上機實踐，使我鞏固了所學的計算機知識，對 C 語言知識有了更進一步的了解。但是知識是學無止境的，我相信，這次的課程設計對我以后在計算機編程這方面有很好的指導意義，讓我通過這次實踐了解到計算機編程的冰山一角。我此次設計的雙向鏈表的排序程序雖然比較典型，對我們認識數據結構和 C 程序設計卻有很好的幫助。

　在設計中我遇到了很多編程方面的難點，在老師的辛勤指導和同學們的熱心幫助下，我慢慢的找到了解決問題的方法。在老師的指導下我學到很多實用的知識，在此表示感謝！感謝老師和同學們的幫助和支持。

推薦訪問： 雙向 排序 鏈表