2有序表的合并

1、數據結構實驗報告實驗題目：有序表的合并姓名：張耀班級：計嵌151學號 實驗目的把兩個有序表歸并為一個有序表。2、 數據結構設計(1) 存儲設計：采用帶頭結點的單鏈表存儲數據。輸入：數據通過鍵盤有序輸入輸出：屏幕顯示兩個有序表及歸并后的表(2) 函數設計：CreateList(intn)；/創(chuàng)建具有n個元素的線性鏈表ListDisplay(；)/輸出表元素Combine(LinkListLA,LinkListLB);叼并單鏈表LA,LB(3) 兩個有序表合并算法描述：Stepl初始化。3.1 設置工作指針pa,pb,分別指向兩個有序表LA,LB的首元結點。3.2 生成新

2、表LC的頭結點，工作指針pc指向LCStep2:只要pa和pb有所指，循環(huán)執(zhí)行下列操作。2.1 生成一新節(jié)點，鏈到LC表尾，pc指向它。2.2 如果pa->data<=pb->data:pc->data=pa->data;p而移。2.3 否則:pc->data=pb->data;pb后移。Step3如果pa空，把pb開始的結點依次復制到pc后。Step4:如果pb空，把pa開始的結點依次復制到pc后。三、算法設計與N-S圖(1) 算法設計：求歸并表的過程是在元素有序的情況下不斷地從兩表中取出元素，添加到新表中，所以元素采取表尾插入。設兩個有序表SASB

3、,歸并后的有序表為SC取元素的過程是：依次掃描SA,SB中的元素，比較當前元素的值，將較小的元素賦給SC,直到一個順序有序表掃描完畢,然后將另一個順序有序表中余下元素復制到SC中。(2) 程序流程圖四、程序清單#include<iostream>usingnamespacestd;#include"process.h"structNodeintdata;數據域，存放表元素Node*next;/指針域，指向下一個結點;classLinkListprivate:Node*Head;/鏈表頭指針public:LinkList();構造函數，創(chuàng)建空鏈表voidCreat

4、eList(intn);創(chuàng)建具有n個元素的線性鏈表voidListDisplay();輸出表元素voidCombine(LinkList,LinkList);/令并;LinkList:LinkList()/構建函數，建一空鏈表Head=newNode;Head->next=NULL;voidLinkList:CreateList(intn)/尾插法(正序)創(chuàng)建具有n個元素的線性表Node*p,*s;/設置工作指針。p指向尾結點p=Head;cout<<"請依次輸入"<<n<<"個元素值："<<endl

5、;for(inti=1;i<=n;i+)s=newNode;/新建元素結點cin>>s->data;/偉俞入新建數據元素值s->next=p->next;/新結點鏈入表尾p->next=s;p=s;voidLinkList:ListDisplay()/遍歷顯示鏈表Node*p;/設置工作指針p=Head->next;/從首元結點開始遍歷inti=1;/元素位序while(p)cout<<p->data<<"t"p=p->next;i+;cout<<endl;voidLinkLis

6、t:Combine(LinkListLA,LinkListLB)Node*pa,*pb,*pc;pa=LA.Head->next;pb=LB.Head->next;pc=Head;while(pa!=NULL&&pb!=NULL)Node*p=newNode;p->next=NULL;pc->next=p;pc=p;if(pa->data<=pb->data)pc->data=pa->data;pa=pa->next;elsepc->data=pb->data;pb=pb->next;if(pa=NU

7、LL)while(pb!=NULL)Node*p1=newNode;p1->next=NULL;pc->next=p1;pc=p1;pc->data=pb->data;pb=pb->next;elseif(pb=NULL)while(pa!=NULL)Node*p2=newNode;p2->next=NULL;pc->next=p2;pc=p2;pc->data=pa->data;pa=pa->next;voidmain()LinkListSA,SB,SC;intla_len,lb_len;cout<<”請輸入要創(chuàng)建SA集

8、合中的元素個數：cin>>la_len;cout<<endl;SA.CreateList(la_len);cout<<"請輸入要創(chuàng)建的SB集合中的元素個數:cin>>lb_len;cout<<endl;SB.CreateList(lb_len);cout<<"SA:"<<endl;SA.ListDisplay();cout<<endl;cout<<"SB:"<<endl;SB.ListDisplay();cout<<

9、;endl;SC.Combine(SA,SB);cout<<"SC:"<<endl;SC.ListDisplay();cout<<endl;五、運行與測試1、測試數據如下:SASBSC11,22,33,441,13,17,391,11,13,17,22,33,39,44111,13,17,391,11,13,17,3911,22,33,4411,11,22,33,4411,22,33,44Void11,22,33,44Void1,13,17,391,13,17,39VoidVoidVoid551,13,17,391,13,17,39,55

10、*1H$JJGrj_2Debugk12_i.e»ei2、運行結果如下:事I人復制建wH告申團兀累i型r松晡IMi二聿*13Fa3J在佃方如建工含呻的口|=;由11修儲出廝人,小F*IL|mPlllTH44»ELrciinnii科btX$J孫rU&DefcugWNeKe,I'rviEVanyheytnrentinu#,產陸無萱汕H*也中助i勃耳不肅fttkliF量也IMt3S：lXis.A»Miir£吉坤團+l*上斜t1卜進猛斯入14F事或EA；Ll±2J344flunntt!""*+fMhayLUitiHtbilM六、實驗分析及體會