實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)一、課程設(shè)計(jì)題目：實(shí)現(xiàn)兩個(gè)鏈表的合并二、基本功能要求：1.建立兩個(gè)鏈表A和B，鏈表元素個(gè)數(shù)分別為m和n個(gè)。2.假設(shè)元素分別為(x1,x2,…xm)，和(y1,y2,…yn)。把它們合并成一個(gè)線性表C，使得：當(dāng)m>=n時(shí)，C=x1,y1,x2,y2,…xn,yn,…,xm當(dāng)n>m時(shí)，C=y1,x1,y2,x2,…ym,xm,…,yn3.輸出線性表C：用直接插入排序法對(duì)C進(jìn)行升序排序，生成鏈表D，并輸出鏈表D。三、測(cè)試數(shù)據(jù)：1.A表（30，41，15，12，56，80）B表（23，56，78，23，12，33，79，90，55）2.A表（30，41，15，12，56，80，23，12，34）B表（23，56，78，23，12）四、理論分析結(jié)果：1.A表的數(shù)據(jù)元素個(gè)數(shù)m=6，B表的數(shù)據(jù)元素個(gè)數(shù)n=9，此時(shí)m<n分析合并結(jié)果：當(dāng)m<n時(shí)，應(yīng)該先插入B表中的數(shù)據(jù)元素，在偶數(shù)位插入B表中的數(shù)據(jù)元素，在奇數(shù)位插入A表中的數(shù)據(jù)元素，最后插入B表中剩余的數(shù)據(jù)元素。C=23，30，56，41，78，15，23，12，12，56，33，80，79，90，55排序結(jié)果：D=12，12，15，23，23，30，33，41，55，56，56，78，79，80，902.A表的數(shù)據(jù)元素個(gè)數(shù)m=9，B表的數(shù)據(jù)元素個(gè)數(shù)n=5，此時(shí)m>n分析合并結(jié)果：當(dāng)m>=n時(shí)，應(yīng)該先插入A表中的數(shù)據(jù)元素，在偶數(shù)位插入A表中的數(shù)據(jù)元素，在奇數(shù)位插入B表中的數(shù)據(jù)元素，最后插入A表中剩余的數(shù)據(jù)元素。C=30，23，41，56，15，78，12，23，56，12，80，23，12，34排序結(jié)果：實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第1頁(yè)。D=12，12，12，15，23，23，23，30，34，41，56，56，78，80實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第1頁(yè)。五、設(shè)計(jì)步驟：5.1分析問(wèn)題，給出數(shù)學(xué)模型，設(shè)計(jì)相應(yīng)的數(shù)據(jù)結(jié)構(gòu)：1)分析問(wèn)題特點(diǎn)，用數(shù)學(xué)表達(dá)式或其它形式描述其數(shù)學(xué)模型。2)選擇能夠體現(xiàn)問(wèn)題本身特點(diǎn)的一種或幾種邏輯結(jié)構(gòu)。3)依據(jù)邏輯結(jié)構(gòu)和問(wèn)題特點(diǎn)，設(shè)計(jì)并選擇相應(yīng)的存儲(chǔ)結(jié)構(gòu)（順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)對(duì)應(yīng)的算法實(shí)現(xiàn)有區(qū)別）。5.2算法設(shè)計(jì)：1)確定所需模塊：對(duì)于復(fù)雜的程序設(shè)計(jì)，要充分利用模塊化程序設(shè)計(jì)方法和面向?qū)ο笏枷?，自頂向下，逐步?xì)化。2)各子模塊功能描述：給出主要模塊的算法描述，用流程圖或偽代碼表示。3)模塊之間的調(diào)用關(guān)系：給出算法各模塊之間的關(guān)系圖示。5.3上機(jī)實(shí)現(xiàn)程序：為提高工作效率，充分利用上機(jī)調(diào)試時(shí)間，在上機(jī)之前應(yīng)列出程序清單。5.4有代表性的各種測(cè)試數(shù)據(jù)去驗(yàn)證算法及程序的正確性： 根據(jù)課程設(shè)計(jì)的要求對(duì)給定的數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證算法以及程序的正確性。5.5算法分析及優(yōu)化：經(jīng)過(guò)上機(jī)調(diào)試，源程序運(yùn)行正確，并且實(shí)現(xiàn)算法要求的功能，解決課程設(shè)計(jì)題目中給出的問(wèn)題后，分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度，如有可能對(duì)程序進(jìn)行優(yōu)化改進(jìn)。六、模塊劃分：?jiǎn)捂湵眍^文件：LinList.h主要包括單鏈表的存儲(chǔ)結(jié)構(gòu)、初始化、求數(shù)據(jù)元素個(gè)數(shù)、插入、刪除數(shù)據(jù)元素、取數(shù)據(jù)元素、撤消單鏈表的函數(shù)。2.單鏈表操作頭文件：MyList.h主要包括單鏈表測(cè)試、單鏈表合并、單鏈表合并排序函數(shù)。3.測(cè)試主函數(shù)文件：TestLinList.h實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第2頁(yè)。主要包括文件包含、數(shù)據(jù)導(dǎo)入和操作模塊程序。實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第2頁(yè)。七、算法設(shè)計(jì)：7.1帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)結(jié)構(gòu)typedefstructNode{ DataTypedata; structNode*next;}SLNode;7.2單鏈表的初始化voidListInitiate(SLNode**head){ /*如果有內(nèi)存空間，申請(qǐng)頭結(jié)點(diǎn)空間并使頭指針head指向頭結(jié)點(diǎn)*/ if((*head=(SLNode*)malloc(sizeof(SLNode)))==NULL) exit(1); (*head)->next=NULL;/*尾標(biāo)記NULL*/}7.3求單鏈表中的數(shù)據(jù)元素個(gè)數(shù)intListLength(SLNode*head){ SLNode*p=head;/*p指向頭結(jié)點(diǎn)*/ intsize=0;/*size初始為0*/ while(p->next!=NULL)/*循環(huán)計(jì)數(shù)*/ { p=p->next;size++;} returnsize;}7.4向單鏈表中插入數(shù)據(jù)元素intListInsert(SLNode*head,inti,DataTypex){ SLNode*p,*q; intj; p=head; 實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第3頁(yè)。 j=-1;實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第3頁(yè)。 while(p->next!=NULL&&j<i-1) { p=p->next;j++; } if(j!=i-1) { printf("Eorror:插入位置參數(shù)錯(cuò)!\n"); return0; } if((q=(SLNode*)malloc(sizeof(SLNode)))==NULL)exit(1); q->data=x; q->next=p->next; p->next=q; return1;}//注：此單鏈表是帶頭結(jié)點(diǎn)的7.5從單鏈表中刪除數(shù)據(jù)元素intListDelete(SLNode*head,inti,DataType*x){ SLNode*p,*s; intj; p=head; j=-1; while(p->next!=NULL&&p->next->next!=NULL&&j<i-1) { p=p->next;j++; } if(j!=i-1) { printf("Eorror:刪除位置參數(shù)錯(cuò)!\n"); return0; } s=p->next; *x=s->data; p->next=p->next->next; free(s); return1;實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第4頁(yè)。實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第4頁(yè)。7.6從單鏈表中取數(shù)據(jù)元素ListGet(SLNode*head,inti,DataType*x){ SLNode*p; intj; p=head; j=-1; while(p->next!=NULL&&j<i) { p=p->next;j++; } if(j!=i) { printf("Eorror:取數(shù)據(jù)元素位置參數(shù)出錯(cuò)!\n"); return0; } *x=p->data; return1;}7.7撤消單鏈表voidDestroy(SLNode**head){ SLNode*p,*p1; p=*head; while(p!=NULL) { p1=p;p=p->next;free(p1); } *head=NULL;}7.8單鏈表測(cè)試函數(shù)voidSingleList(inta[],intal){ inti,x; SLNode*head;實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第5頁(yè)。實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第5頁(yè)。 //向單鏈表插入數(shù)據(jù)元素 for(i=0;i<al;i++) { if(ListInsert(head,i,a[i])==0) { printf("Error:插入數(shù)據(jù)元素錯(cuò)誤!\n");return; } } //從單鏈表取數(shù)據(jù)元素 printf("結(jié)果:"); for(i=0;i<ListLength(head);i++) { if(ListGet(head,i,&x)==0) { printf("Error:取數(shù)據(jù)元素錯(cuò)誤!\n");return; } elseprintf("%d",x); } printf("\n"); Destroy(&head);//撤消單鏈表 printf("\n");}7.9單鏈表合并函數(shù)voidCombineList(inta[],intb[],intal,intbl){ inti,j=0,x; int*list; SLNode*head; list=(int*)malloc((al+bl)*sizeof(int)); if(al<bl)//a[]數(shù)組的數(shù)據(jù)元素個(gè)數(shù)<b[]數(shù)組的數(shù)據(jù)元素個(gè)數(shù) { //較長(zhǎng)數(shù)組的數(shù)據(jù)元素賦給動(dòng)態(tài)數(shù)組的偶數(shù)位 for(i=0;i<2*al;i+=2) { if(i%2==0) { list[i]=b[j];j++;實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第6頁(yè)。實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第6頁(yè)。 } j=0;//恢復(fù)公共下標(biāo)初始值 //較短數(shù)組的數(shù)據(jù)元素賦給動(dòng)態(tài)數(shù)組的奇數(shù)位 for(i=0;i<2*al;i++) { if(i%2==1) { list[i]=a[j];j++; } } //較長(zhǎng)數(shù)組剩余數(shù)據(jù)元素賦值 for(i=2*al;i<al+bl;i++) { list[i]=b[j];j++; } } else//a[]數(shù)組的數(shù)據(jù)元素個(gè)數(shù)>=b[]數(shù)組的數(shù)據(jù)元素個(gè)數(shù) { //較長(zhǎng)數(shù)組b[]的數(shù)據(jù)元素賦給動(dòng)態(tài)數(shù)組的偶數(shù)位 for(i=0;i<2*bl;i+=2) { if(i%2==0) { list[i]=a[j];j++; } } j=0;//恢復(fù)公共下標(biāo)初始值 //較短數(shù)組a[]的數(shù)據(jù)元素賦給動(dòng)態(tài)數(shù)組的奇數(shù)位 for(i=0;i<2*bl;i++) { if(i%2==1) { list[i]=b[j];j++; } } //較長(zhǎng)數(shù)組a[]剩余數(shù)據(jù)元素賦值 for(i=2*bl;i<al+bl;i++) {實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第7頁(yè)。實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第7頁(yè)。 } } ListInitiate(&head); //向單鏈表插入數(shù)據(jù)元素 for(i=0;i<al+bl;i++) { if(ListInsert(head,i,list[i])==0) { printf("Error:插入A的數(shù)據(jù)元素錯(cuò)誤!\n"); } } free(list); //從單鏈表取數(shù)據(jù)元素 for(i=0;i<ListLength(head);i++) { if(ListGet(head,i,&x)==0) { printf("Error:取數(shù)據(jù)元素錯(cuò)誤!\n");return; } else printf("%d",x); } printf("\n"); Destroy(&head);//撤消單鏈表}7.10直接插入法排序for(i=0;i<al+bl-1;i++){ temp=list[i+1]; j=i; while(j>-1&&temp<list[j]) { list[j+1]=list[j];j--; } list[j+1]=temp;實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第8頁(yè)。}//直接插入法對(duì)數(shù)組list[]排序?qū)崿F(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第8頁(yè)。7.11操作模塊設(shè)計(jì)printf("**********數(shù)據(jù)結(jié)構(gòu)單鏈表合并測(cè)試實(shí)驗(yàn)************\n");printf("****1.測(cè)試單鏈表A****\n");printf("****2.測(cè)試單鏈表B****\n");printf("****3.合并單鏈表A、B得到單鏈表C****\n");printf("****4.對(duì)單鏈表C升序排序得到單鏈表D****\n");printf("****0.退出合并單鏈表的測(cè)試程序****\n");printf("**********數(shù)據(jù)結(jié)構(gòu)單鏈表合并測(cè)試實(shí)驗(yàn)************\n");…………while(flag==1){ printf("輸入功能號(hào)碼:"); scanf("%d",&flag); switch(flag) { case1: printf("測(cè)試單鏈表A\n"); SingleList(&a,al); flag=1;//功能循環(huán)標(biāo)志 break; case2: printf("測(cè)試單鏈表B\n"); SingleList(&b,bl); flag=1;//功能循環(huán)標(biāo)志 break; case3: printf("測(cè)試單鏈表A、B的合并\n"); CombineList(&a,&b,al,bl); flag=1;//功能循環(huán)標(biāo)志 break; case4: printf("測(cè)試單鏈表C的排序\n"); SortList(&a,&b,al,bl); flag=1;//功能循環(huán)標(biāo)志 break; case0: printf("Message:歡迎下次再次測(cè)試單鏈表合并程序!\n"); break;//flag!=0退出程序標(biāo)志實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第9頁(yè)。 default:實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第9頁(yè)。 printf("Error:功能號(hào)碼選擇錯(cuò)誤,請(qǐng)重新選擇!\n"); flag=1;//功能循環(huán)標(biāo)志 break; }}八、測(cè)試程序運(yùn)行結(jié)果：8.1測(cè)試第1組數(shù)據(jù)（1）單鏈表測(cè)試：測(cè)試目的：測(cè)試單鏈表是否能夠進(jìn)行插入、讀取等操作。測(cè)試結(jié)果：?jiǎn)捂湵鞟=30，41，15，12，56，80單鏈表B=23，56，78，23，12，33，79，90，55（2）單鏈表合并測(cè)試：實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第10頁(yè)。實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第10頁(yè)。測(cè)試目的：測(cè)試兩個(gè)單鏈表是否能夠按照要求進(jìn)行合并測(cè)試結(jié)果：?jiǎn)捂湵鞢=23，30，56，41，78，15，23，12，12，56，33，80，79，90，55（3）單鏈表合并后排序測(cè)試：測(cè)試目的：測(cè)試兩個(gè)合并后的單鏈表是否能夠升序排序后輸出測(cè)試結(jié)果：?jiǎn)捂湵鞤=12，12，15，23，23，30，33，41，55，56，56，78，79，80，908.2測(cè)試第2組數(shù)據(jù)（1）單鏈表測(cè)試：測(cè)試目的：測(cè)試單鏈表是否能夠進(jìn)行插入、讀取等操作。測(cè)試結(jié)果：?jiǎn)捂湵鞟=30，41，15，12，56，80，23，12，34單鏈表B=23，56，78，23，12實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第11頁(yè)。（2）單鏈表合并測(cè)試：實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第11頁(yè)。測(cè)試目的：測(cè)試兩個(gè)單鏈表是否能夠按照要求進(jìn)行合并測(cè)試結(jié)果：?jiǎn)捂湵鞢=30，23，41，56，15，78，12，23，56，12，80，23，12，34（3）單鏈表合并后排序測(cè)試： 測(cè)試目的：測(cè)試兩個(gè)合并后的單鏈表是否能夠升序排序后輸出測(cè)試結(jié)果：?jiǎn)捂湵鞤=12，12，12，15，23，23，23，30，34，41，56，56，78，808.3測(cè)試說(shuō)明：經(jīng)過(guò)反復(fù)的程序調(diào)試和修改，最終實(shí)現(xiàn)了本次課程設(shè)計(jì)的任務(wù)。限于篇幅，程序運(yùn)行結(jié)果只有調(diào)試修改正確以后的的運(yùn)行結(jié)果。為了方便測(cè)試，在測(cè)試過(guò)程中，把要測(cè)試的數(shù)據(jù)直接通過(guò)添加數(shù)據(jù)程序代碼導(dǎo)入到程序中。把程序運(yùn)行結(jié)果和理論分析結(jié)果進(jìn)行對(duì)比，驗(yàn)證程序的正確性。8.4測(cè)試結(jié)論：實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第12頁(yè)。在程序完成編寫之后，程序的連接、編譯、運(yùn)行開始不能夠正常通過(guò)，經(jīng)過(guò)調(diào)試、修改之后，最終都能夠正常通過(guò)，修改過(guò)后的程序中沒(méi)有語(yǔ)法錯(cuò)誤。實(shí)現(xiàn)兩個(gè)鏈表的合并-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共14頁(yè)，當(dāng)前為第12頁(yè)。把測(cè)試結(jié)構(gòu)和理論的分析結(jié)構(gòu)進(jìn)行對(duì)比，通過(guò)程序運(yùn)行結(jié)果的觀察得知程序運(yùn)行結(jié)果和理論分析結(jié)果基本吻合。通過(guò)單鏈表的操作可以完成兩個(gè)單鏈表的合并，除此之外，還能夠?qū)捂湵砗喜⒑蟮臄?shù)據(jù)元素進(jìn)行排序。課程設(shè)計(jì)總結(jié)：9.1課程設(shè)計(jì)題目的選擇在本次的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)中，我選擇的題目是“實(shí)現(xiàn)兩個(gè)單鏈表的合并”，從所學(xué)習(xí)過(guò)的知識(shí)入手進(jìn)行