數據結構考研分類復習真題 第二章 答案[42]

　　()要求編程實現帶頭結點的單鏈表的逆置首先建立一單鏈表然後逆置

　　typedef  struct  node
　　{int  data;∥假定結點數據域為整型
　　struct  node  *next;
　　}node*LinkedList;
　　LinkedList creat( )
　　{LinkedList headp
　　int  x;
　　head=(LinkedList)malloc(sizeof(node));
　　head>next=null; /*設置頭結點*/
　　scanf(%d&x);
　　while(x!=) /*約定輸入時退出本函數*/
　　{p=(LinkedList)malloc(sizeof(node));
　　p>data=x;
　　p>next=head>next;/* 將新結點鏈入鏈表*/
　　head>next=p;
　　scanf(%d&x);
　　}
　　return(head);
　　}∥結束creat函數
　　LinkedList invert(LinkedList head)
　　/*逆置單鏈表*/
　　{LinkedList p=head>next; /*p為工作指針*/
　　head>next=null;
　　while(p!=null)
　　{r=p>next;         /*暫存p的後繼*/
　　p>next=head>next;
　　head>next=p;
　　p=r;
　　}
　　return(head);
　　}/*結束invert函數*/
　　main()
　　{LinkedList la;
　　la=creat( );    /*生成單鏈表*/
　　la=invert(la);/*逆置單鏈表*/
　　}

　　()本題要求將數據項遞減有序的單鏈表重新排序使數據項遞增有序要求算法復雜度為O(n)雖沒說要求將鏈表逆置這只是敘述不同本質上是將單鏈表逆置現編寫如下

　　LinkedList invert(LinkedList la)∥la是帶頭結點且數據項遞減有序的單鏈表本算法將其排列成數據項遞增有序的單鏈表
　　{p=la>next;     /*p為工作指針*/
　　la>next=null;
　　while(p!=null)
　　{r=p>next;   /*暫存p的後繼*/
　　p>next=la>next;/*將p結點前插入頭結點後*/
　　la>next=p;p=r;
　　}
　　}∥結束算法

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/23333.html