數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-兩個(gè)鏈表合并-星

#兩個(gè)鏈表的合并.課程設(shè)計(jì)目的實(shí)現(xiàn)對(duì)兩個(gè)的鏈表的交叉合并，輸出線形表C用直接插入排序法對(duì)C進(jìn)行升序排序，生成鏈表D,并輸出鏈表D。掌握對(duì)線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)，實(shí)現(xiàn)插入的操作。了解鏈表交叉合并的方法和直接插入排序法的思想，并深刻掌握算法的格式和應(yīng)用。提高對(duì)數(shù)據(jù)結(jié)構(gòu)的理解和應(yīng)用，增強(qiáng)個(gè)人動(dòng)手實(shí)踐能力和邏輯分析能力。.設(shè)計(jì)方案論證設(shè)計(jì)思路本課程設(shè)計(jì)將對(duì)鏈表的交叉合并和直接插入排序的實(shí)現(xiàn)。首先將兩個(gè)鏈表進(jìn)行交叉合并，合并的要求如下：建立兩個(gè)鏈表A和B，鏈表元素個(gè)數(shù)分別為m和n個(gè)。假設(shè)元素分別為（x1,x2，…xm），和（y1,y2,…yn）。把它們合并成一個(gè)線形表C，使得：當(dāng)m>=n時(shí)，C=x1,y1,x2,y2,…xn,yn,…，xm（當(dāng)口^時(shí)，C=y1,x1,y2,x2，…ym,xm,…，yn輸出線形表C。對(duì)合并的鏈表C進(jìn)行直接插入排序，輸出鏈表D。此次課程設(shè)計(jì)實(shí)驗(yàn)的數(shù)據(jù)位A表（30，41，15，12，56，80）B表（23，56，78，23，12，33，79，90，55）A表（30，41，15，12，56，80，23，12，34）B表（23，56，78，23，12）|鏈表鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。通常我們把鏈表畫成用箭頭相連接的結(jié)點(diǎn)的序列，節(jié)點(diǎn)之間的箭頭表示指針。在c語言中，鏈表用結(jié)構(gòu)指針來描述。相比于線

性表順序結(jié)構(gòu)，鏈表比較方便插入和刪除操作(1)線性表的單鏈表存儲(chǔ)結(jié)構(gòu)ypedefstructNode(ElemTypedata;structNode*next;}Node;typedefstructNode*Linklist(2)實(shí)現(xiàn)兩個(gè)鏈表的簡單合并算法如下VoidMergelist_L(Linklist&La,Linklist&Lb,Linklist&Lc){ey,[i-1].Key)){

[j+1]=[j];ey,[j].Key)T--j):\PrograiFiles\licrosoftVisualStudi :\PrograiFiles\licrosoftVisualStudi -hlxl情輸入第一個(gè)鏈表:的入鏈表的長度a：情輸入鏈表數(shù)據(jù)?123255668844117788爾剛才輸入的第一個(gè)鏈表信息二數(shù)字二12 32EE668S44請(qǐng)輸入第二個(gè)鏈表二若入鏈表的折度型情輸入鏈表疑嘉■d7C語言與數(shù)C語言與數(shù)據(jù)結(jié)構(gòu)[M].北京：電子工業(yè)出版社，：120-146[2]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)式語言版）[M].北京：清華大學(xué)出版社，：44-52[3]嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)C語言[M].北京：清華大學(xué)出版社，：110-135}[4]譚浩強(qiáng).C程序設(shè)計(jì)指導(dǎo)[M].北京：清華大學(xué)出版社,2005[5]潘新民，王燕芳.微型計(jì)算機(jī)控制技術(shù)[M],第2版.北京：電子工業(yè)出版社，：305-350附錄:源程序#include<>#include<>#include<>#include<>#defineLsizeof(structNode)structNode//結(jié)構(gòu)體longintnumber;structNode*next;structNode*create(inta)〃鏈表創(chuàng)建函數(shù){intn;structNode*p1,*p2,*head;head=NULL;n=0;p2=p1=(structNode*)malloc(L);〃分配內(nèi)存)scanf("%ld”,&p1->number);while(a)〃錄入鏈表信息{n=n+1;if(n==1)head=p1;elsep2->next=p1;:p2=p1;p1=(structNode*)malloc(L);if(a!=1)〃分配內(nèi)存scanf("%ld”,&p1->number);a--;〃控制輸入的個(gè)數(shù)}p2->next=NULL;return(head);<}〃鏈表創(chuàng)建函數(shù)結(jié)束voidprint(structNode*head)//輸出函數(shù){structNode*p;p=head;printf("數(shù)字：\n");if(head!=NULL)@do//循環(huán)實(shí)現(xiàn)輸出{printf("%ld”,p->number);printf("");p=p->next;}while(p!=NULL);printf("\n");〃鏈表的交叉合并算法structNode*inter_link(structNode*chainl,inta,structNode*chain2,intb){inttemp;structNode*head,*p1,*p2,*pos;/*判斷a，b大小并合并*/if(a>=b){head=p1=chain1;p2=chain2;}else/*b>a*/{head=p1=chain2;p2=chain1;temp=a,a=b,b=temp;/*交換@和b*/}/*下面把p1的每個(gè)元素插在p2相應(yīng)元素之前，p1長a,p2長b*/pos=head;/*此時(shí)pos指向p1中的第一個(gè)元素*/while(p2!=NULL){//漂亮，蛇形插入p1=p1->next;pos->next=p2;pos=p2;p2=p2->next;pos->next=p1;pos=p1;returnhead;}〃對(duì)合并好的鏈表進(jìn)行排序voidInsertSort(structNode*p,int皿)//排序函數(shù){inti,j,t;structNode*k;k=p;for(i=0;i<m-1;i++){for(j=0;j<m-i-1;j++){if(p->number>(p->next)->number){t=p->number;p->number=(p->next)->number;(p->next)->number=t;}p=p->next；p=k；}}〃主函數(shù)int皿@訕（）〃皿@訕函數(shù){structNode*p1,*p2；inta;intb;inth;printf（"請(qǐng)輸入第一個(gè)鏈表:\n"）;printf（"\n輸入鏈表的長度a:\n"）;（scanf（"%d",&a）;printf（"請(qǐng)輸入鏈表數(shù)據(jù)："）；p1=create（a）;printf（"\n你剛才輸入的第一個(gè)鏈表信息:""）；print（p1）;printf（"\n請(qǐng)輸入第二個(gè)鏈表:\n"）；printf（"\n輸入鏈表的長度b:\n"）；scanf（"%d",&b）；printf（"請(qǐng)輸入鏈表數(shù)據(jù)："）；p2=create（b）；printf（"\n