程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 將遞增單鏈表A和遞增單鏈表B合並為遞減單鏈表C

將遞增單鏈表A和遞增單鏈表B合並為遞減單鏈表C

編輯:關於C語言

24 假設有兩個按元素值遞增有序排列的線性表A和B,均以單鏈表作存儲結構,請編寫算法將A表和B表歸並成一個按元素值遞減有序(即非遞增有序,允許表中含有值相同的元素)排列的線性表C,並要求利用原表(即A表和B表)的結點空間構造C表。

 

 001 #define true 1 

002 #define false 0 

003 #define ok 1 

004 #define error 0 

005 #define infeasible -1 

006 #define overflow -2 

007 #include<stdio.h> 

008 #include<malloc.h> 

009 typedef int ElemType; 

010 typedef int Status; 

011   

012 typedef struct LNode 

013 { 

014     ElemType data; 

015     struct LNode * next; 

016 } LNode,*LinkList; 

017   

018 void CreateList_TailInsert(LinkList *L)//尾插法構造鏈表; 

019 { 

020     LinkList p,r; 

021     int ch; 

022     scanf("%d",&ch); 

023     r=(*L);//剛開始時,L是一個只有頭結點的空表,r指向該結點,也就是r指向L的尾巴. 

024     while(ch!=0) 

025     { 

026         p=(LinkList)malloc(sizeof(LNode)); 

027         p->data=ch; 

028         r->next=p;//增加p後,將p加到r後面 

029         r=p;//重新將r指向L的尾巴; 

030         scanf("%d",&ch); 

031     } 

032     r->next=NULL; 

033 } 

034 void InitList(LinkList *L)//初始化鏈表,構造帶頭結點的單鏈表; 

035 { 

036     *L=(LinkList)malloc(sizeof(LNode)); 

037     (*L)->next=NULL; 

038 } 

039   

040 Status Merger_AandB_toC(LinkList*La,LinkList*Lb,LinkList*Lc) 

041 { 

042     //利用升序單鏈表A和升序單鏈表B的空間生成降序單鏈表C 

043     LinkList pa,pb,qa,qb; 

044     (*Lc)->next=NULL; 

045     qa=(*La); 

046     qb=(*Lb); 

047     pa=(*La)->next; 

048     pb=(*Lb)->next; 

049     while(pa&&pb) 

050     { 

051   

052         if(pa->data<pb->data) 

053         { 

054             qa=pa; 

055             pa=pa->next; 

056             qa->next=(*Lc)->next; 

057             (*Lc)->next=qa; 

058         } 

059         else

060         { 

061             qb=pb; 

062             pb=pb->next; 

063             qb->next=(*Lc)->next; 

064             (*Lc)->next=qb; 

065         } 

066     } 

067     if(!pa) 

068     { 

069         while(pb) 

070         { 

071             qb=pb; 

072             pb=pb->next; 

073             qb->next=(*Lc)->next; 

074             (*Lc)->next=qb; 

075         } 

076     } 

077     if(!pb) 

078     { 

079         while(pa) 

080         { 

081             qa=pa; 

082             pa=pa->next; 

083             qa->next=(*Lc)->next; 

084             (*Lc)->next=qa; 

085         } 

086     } 

087 } 

088 int main() 

089 { 

090     LinkList La,Lb,p,Lc; 

091     int i; 

092     ElemType e; 

093     InitList(&La); 

094     printf("\n請逐個輸入數字,輸入0的時候結束\n"); 

095     CreateList_TailInsert(&La); 

096     p=La; 

097     printf("新建的單鏈表La打印為:\n"); 

098     while(p->next!=NULL) 

099     { 

100         printf("%d\t",p->next->data); 

101         p=p->next; 

102     } 

103     InitList(&Lb); 

104     printf("\n請逐個輸入數字,輸入0的時候結束\n"); 

105     CreateList_TailInsert(&Lb); 

106     p=Lb; 

107     printf("新建的單鏈表Lb打印為:\n"); 

108     while(p->next!=NULL) 

109     { 

110         printf("%d\t",p->next->data); 

111         p=p->next; 

112     } 

113     InitList(&Lc); 

114     printf("\nLa和Lb合並成為Lc後打印為:\n"); 

115     Merger_AandB_toC(&La,&Lb,&Lc); 

116     p=Lc; 

117     while(p->next!=NULL) 

118     { 

119         printf("%d\t",p->next->data); 

120         p=p->next; 

121     } 

122     return 0; 

123 }

畫圖很重要。

 


作者:耀耀

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