課程設(shè)計鏈表的交叉合并課程設(shè)計

上傳人：奔*** IP屬地：河北更新時間：2024-04-04 格式：doc 頁數(shù)：16 大?。?17.00KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩15頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、　　《兩個鏈表的交叉合并》　　課程設(shè)計論文　　學(xué)生姓名 　　學(xué) 號 　　所屬學(xué)院信息工程學(xué)院 　　專

2、業(yè) 計算機(jī)科學(xué)與技術(shù) 　　班級計算機(jī) 　　指導(dǎo)教師 　　教師職稱講師 　　目錄<

3、b>　　前言1　　1.1設(shè)計背景1　　1.1.1數(shù)據(jù)結(jié)構(gòu)簡介1　　1.1.2算法選擇的原因1　　1.2設(shè)計的原理和內(nèi)容1　　正文2<

4、;/b>　　2.1課程設(shè)計目的2　　2.2課程設(shè)計題目2　　2.2.1問題定義2　　2.2.2需求分析2　　2.3總體方案2<b

5、>　　2.4運(yùn)行環(huán)境3　　2.5設(shè)計流程圖3　　2.6設(shè)計思路3　　2.6.1.1線性表的單鏈表結(jié)構(gòu)4　　2.6.1.2實(shí)現(xiàn)兩個鏈表的簡單合并算法4　　2.

6、6.1.3把元素插入到鏈表當(dāng)中4　　2.6.1.4將元素從鏈表中刪除5　　2.6.2鏈表的合并5　　2.6.3鏈表的排序6　　2.6.4算法模塊設(shè)計7　　2.7程序運(yùn)行分析10

7、　　參考文獻(xiàn)11　　附錄11　　前言　　1.1設(shè)計背景　　1.1.1數(shù)據(jù)結(jié)構(gòu)簡介<p&

8、gt;　　數(shù)據(jù)結(jié)構(gòu)是計算機(jī)程序設(shè)計的重要理論設(shè)計基礎(chǔ)，它不僅是計算機(jī)學(xué)科的核心課程，而且成為其他理工專業(yè)的熱門選修課。數(shù)據(jù)結(jié)構(gòu)是計算機(jī)存儲、組織數(shù)據(jù)的方式。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或者存儲效率的算法。比如在計算機(jī)中央處理器中，CPU接到一個中斷請求便會停下當(dāng)前正在執(zhí)行的指令去處理這個中斷請求完成中斷操作，&

9、#160;首先要做的就是保護(hù)現(xiàn)場。保護(hù)現(xiàn)場需要將下一條指令的地址指針和當(dāng)前指令返回地址等重要的數(shù)據(jù)進(jìn)行存儲。在眾多的數(shù)據(jù)結(jié)構(gòu)中，這些重要的數(shù) 據(jù)被存儲到棧這個數(shù)據(jù)結(jié)構(gòu)中。　　1.1.2算法選擇的原因　　在許多類型的程序的設(shè)計中，數(shù)據(jù)結(jié)構(gòu)的選擇是一個基本的設(shè)計考慮因素。許多大

10、型系統(tǒng)的構(gòu)造經(jīng)驗(yàn)表明，系統(tǒng)實(shí)現(xiàn)的困難程度和系統(tǒng)構(gòu)造的質(zhì)量都嚴(yán)重的依賴于是否選擇了最優(yōu) 的數(shù)據(jù)結(jié)構(gòu)。許多時候，確定了數(shù)據(jù)結(jié)構(gòu)后，算法就容易得到了。有些時候事情也會反過來，我們根據(jù)特定算法來選擇數(shù)據(jù)結(jié)構(gòu)與之適應(yīng)。不論哪種情況，選擇合適的數(shù)據(jù)結(jié)構(gòu)都是非常重要的。　　1.2設(shè)

11、計的原理和內(nèi)容　　本次程序設(shè)計采用C語作為描述和實(shí)現(xiàn)算法的程序語言，主要的設(shè)計思路就是完成對鏈表的操作，如鏈表的插入、刪除、取鏈表頂?shù)鹊龋@些操作都是通過C語言程序來實(shí)現(xiàn)的。最后的結(jié)果就是運(yùn)行程序時能夠完成對以上設(shè)計的操作。　　正文　　鏈表是一種物理存

12、儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時動態(tài)生成。每個結(jié)點(diǎn)包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點(diǎn)地址的指針域。相比于線性表順序結(jié)構(gòu)，鏈表比較方便插入和刪除操作。　　2.1課程設(shè)計目的<p&g

13、t;　　課程設(shè)計為學(xué)生提供了一個既動手又動腦，獨(dú)立實(shí)踐的機(jī)會將課本上的理論知識和實(shí)際有機(jī)的結(jié)合起來，鍛煉學(xué)生的分析解決實(shí)際問題的能力。提高學(xué)生適應(yīng)實(shí)際，實(shí)踐編程的能力。　　2.2課程設(shè)計題目　　實(shí)現(xiàn)兩個鏈表的交叉合并。　　要求：（1）輸入兩個鏈表。&l

14、t;p>　?。?）輸出兩個鏈表合并后的鏈表。　　2.2.1問題定義　　實(shí)現(xiàn)對兩個的鏈表的交叉合并，輸出線形表C用直接插入排序法對C進(jìn)行升序排序，生成鏈表D，并輸出鏈表D。　　2.2.2需求分析

15、;　　鏈表是線性表的鏈?zhǔn)奖硎?，由于它不要求邏輯上相鄰的元素在物理上相鄰，所以它沒有不需要像順序存儲結(jié)構(gòu)在插入，刪除元素時移動大量的元素，只修改指針節(jié)點(diǎn)，并修改這些節(jié)點(diǎn)的指針域，查找過程中需平均一定指針域?yàn)楸黹L的一半，而采用順序結(jié)構(gòu)存儲線性表，插入和刪除元素操作需要平均移動表彰的一半元素。移動指針域操作比一動元素操作花費(fèi)的時間少得多。　　2.3總體方案<

16、/p>　　鏈表是一種特殊的線性表，具體表現(xiàn)在它的刪除，插入不用移動大量的元素，而且所用時間較少。這次設(shè)計的目的在于將它的快速，便捷體現(xiàn)出來。將程序分為了兩個部分程序設(shè)計和程序調(diào)試。首先查閱與鏈表合并有關(guān)的資料和文獻(xiàn)；其次設(shè)計項目的整體構(gòu)架和算法；然后先用一個門程序設(shè)計語言進(jìn)行算法的描述；最后調(diào)試程序。　　2.4運(yùn)行環(huán)境</p

17、>　　Win7 32位操作系統(tǒng)　　Microsoft Visual C++編譯器　　2.5設(shè)計流程圖　　2.6設(shè)計思路　　本課程設(shè)計將對鏈表的交叉合并和直接插入排

18、序的實(shí)現(xiàn)。首先將兩個鏈表進(jìn)行交叉合并，合并的要求如下： 　　建立兩個鏈表A和B，鏈表元素個數(shù)分別為m和n個。假設(shè)元素分別為(x1,x2,…xm)，和(y1,y2, …yn)。把它們合并成一個線形表C，使得： 　　當(dāng)m>=n時，C=x1,y1,x2,y2,…xn,yn,…,xm 　　當(dāng)n>m時，C=y1

19、,x1,y2,x2,…ym,xm,…,yn　　輸出線形表C。 　　對合并的鏈表C進(jìn)行直接插入排序，輸出鏈表D。　　2.6.1鏈表　　2.6.1.1線性表的單鏈表結(jié)構(gòu)<

20、p>　　ElemType data; 　　struct Node *next; 　　} Node; 　　typedef struct Node *Linklist;　　2.6.1.2實(shí)現(xiàn)兩個鏈表的簡單合并算法</p&g

21、t;　　Void Mergelist_L(Linklist &La,Linklist &Lb,Linklist &Lc){　　//已知單線性鏈表La和Lb的元素按值非遞減排列。 　　//歸并La和Lb得到新的線性表Lc，Lc的數(shù)據(jù)元素也按非遞減排列。 　　InitLi

22、st(Lc); 　　i=j=1;k=0; 　　La_len=Listlength(La);Lb_len=ListLength(Lb); 　　While((i<=La_len)&&(j<=Lb_len)){//La和Lb均非空 　　Getelem

23、(La, i, ai);Getelem(Lb, j, bj); 　　If(ai<=bj){Listinsert(Lc, ++k ai);++i;} 　　Else {Listinsert(Lc, ++k bj);++j;} 　　} While(i<=La_len){<p&g

24、t;　　Getelem（La, i++, ai）;Listinsert(Lc, ++k, ai); 　　} 　　While(j<=Lb_len){　　Getelem(Lb, j++, bj);Listinsert(Lc, ++k, bj); &l

25、t;p>　　}}//Mergelist　　2.6.1.3把元素插入到鏈表當(dāng)中　　在鏈表的合并中常用的操作是插入，要在線性表的兩個元素之間出入一個新的元素x。為了插入元素x，首先要生成一個數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)，然后插入數(shù)據(jù)元素x。根據(jù)插入操作的邏輯定義，還要修改結(jié)點(diǎn)a中的指針域，令其指向結(jié)點(diǎn)x，而結(jié)點(diǎn)x中的指針域應(yīng)指向結(jié)點(diǎn)b，從而實(shí)現(xiàn)3個元素a，b和x之

26、間的邏輯變化。上述指針修改語句描述為,　　s—>next=p—>next;p—>next=s;　　單鏈表中插入結(jié)點(diǎn)時的指針變化情況如圖所示： p 　　圖圖圖圖1 1 1 1　　單鏈表中插入結(jié)點(diǎn)時的指針變化情

27、單鏈表中插入結(jié)點(diǎn)時的指針變化情單鏈表中插入結(jié)點(diǎn)時的指針變化情單鏈表中插入結(jié)點(diǎn)時的指針變化情 　　插入元素的代碼如下： 　　status ListInsert_L(LinkList &L, int i,ElemType e){ 　　//在帶頭結(jié)點(diǎn)的單鏈線性表L中第i個位置之前插入元素e

28、　　p=l;j=0;　　while(p&&j<i-1){p=p->next;++j;}//尋找第i-1個結(jié)點(diǎn)　　if(!P||j>i-1)return ERROR; //i小于1或者大于表長+1　　s=（LinkList）

29、malloc(sizeof(LNode)); //生成新結(jié)點(diǎn) 　　s->date=e; s->next=p->next; //插入L中 　　p->next=s; 　　return OK;　　}//ListInsert_L&

30、lt;p>　　2.6.1.4將元素從鏈表中刪除　　在線性表中刪除元素b時，為了在單鏈表中實(shí)現(xiàn)元素a、b和c之間邏輯關(guān)系的變化，僅需改動節(jié)點(diǎn)a中的指針域即可。假設(shè)p為指向節(jié)點(diǎn)a的指針，則修改指針的語句為　　p->next=p->next->next; 　　在已知單鏈表中元素插入或插入或刪除的

31、確切位置的情況下，在單鏈表中插入刪除一個結(jié)點(diǎn)時，僅需修改指針而不需要移動元素。刪除元素代碼如下:　　Status ListInsert_L(LinkList&L,int I,ElemType e){　　//在帶頭結(jié)點(diǎn)的單鏈表線性表L中,刪除第i個元素，并由e返回其值 　　p=L;j=0

32、;　　while (p&&j<i-1){//尋找第i-1個結(jié)點(diǎn)，并令p指向其前驅(qū) 　　p=p—>next;+j:　　}　　If(!(p—>next)||j>i-1)retur

33、n ERROR;//刪除位置不合理 　　q=p—>next;p—>next=q—>next;//刪除并釋放結(jié)點(diǎn) 　　e=q—>data; free(q);//釋放函數(shù) 　　retrun OK; 　　}//ListDelete_L

34、　　2.6.2鏈表的合并　　鏈表的合并是將兩個鏈表合并成一個鏈表。假設(shè)兩個鏈表LA和LB頭指針為La，Lb，要?dú)w并La和Lb得到鏈表Lc，pa和pb分別指向La和Lb表中當(dāng)前待比較插入的結(jié)點(diǎn)，而pc指向Lc當(dāng)前最后一個結(jié)點(diǎn)，若pa—>data<pb—>data,則將pa所指結(jié)點(diǎn)鏈接到pc所指結(jié)點(diǎn)之后，，否則將pb所指結(jié)點(diǎn)鏈接到pc所指結(jié)點(diǎn)之后。當(dāng)LA和L

35、B為非空表時，pa和pb分別指向La和Lb表中第一個結(jié)點(diǎn)，否則為空；pc指向空表Lc中的頭結(jié)點(diǎn)。由于鏈表的長度為隱含的，則第一個循環(huán)執(zhí)行的條件pa和pb皆非空，當(dāng)其中一個為空時，說明有一個表的元素已歸并完，則是要將另一個表的剩余段鏈接在pc所指結(jié)點(diǎn)之在內(nèi)部排序中，如果按照排序過程中依據(jù)的不同原則進(jìn)行分類，則大致可以分為插入排序、交換排序、選擇排序、歸并排序、和計數(shù)排序5類。通常在排序過程中需進(jìn)行一下兩種基本操作：

36、　?。?）比較兩個關(guān)鍵字的大?。?　?。?）將記錄從一個位置轉(zhuǎn)移到另一個位置。前一個基本操作是對于任何排序方法來說都是必要的，而后者可以通過改變記錄的儲存方式來來予以避免。且為了研究方便起見，設(shè)關(guān)鍵字均為整數(shù)。待排序、記錄的數(shù)　　typedef struct{ 　　KeyType key;

37、 //關(guān)鍵字項　　InfoType otherinfo; //其他數(shù)據(jù)項 　　Typedef struct{ 　　RedType r[MSXSIZE+1]; //r[0]閑置或用作哨兵單元 　　Int length;

38、 //順序表長度 　　}SqList //順序表類型　　本課程設(shè)計主要是應(yīng)用直接插入排序?qū)⒑喜⒌逆湵磉M(jìn)行排序。直接插入排序是一種最簡單的排序方法，他的基本操作是將一個記錄插入已排好序的有序表中，從而得到一個新的、數(shù)據(jù)記錄增一得有序表。一般情況下，第i趟直接插入排序的操作為：在含有i-1個記錄的有序子序列r[1

39、.i-1]中插入一個記錄r[i]后，變成含有i個記錄的有序子序列r1.i[]；并且和順序表查找類似，在r[0]處設(shè)置監(jiān)視哨。在自i-1起往前收索的過程中，可以同時后已記錄。整個排序過程為進(jìn)行n-1趟插入，即：先將序列中的第一個記錄看做一個有序的子序列，然后從第二個記錄起逐個插入，直至整個序列變成按關(guān)鍵字有序序列為止。　　void InsertSort (SqList&L){

40、 //對順序表L作直接插入排序。 　　For（i=2;i<=L.length;++i） 　　If (LT(L.r[i].Key,L.r[i-1].Key)){ //“（”，需要將L.r[i]插入有序子表 　　L.r[0]=L.r[i] <

41、;p>　　L.r[i]=L.r[i-1]; 　　For (j=i-2;LT(L.r[0].Key,L.r[j].Key);--j) 　　L.r[j+1]=L.r[j]; //記錄后移 　　L.r[j+1]=L.r[0]; //插入到

42、正確位　　}　　}//InsertSort　　2.6.3鏈表的排序　　排序是計算機(jī)程序設(shè)計中的一個重要操作，他的功能是將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個按關(guān)鍵字有序的序列。由于待排序的記錄數(shù)量不同，使得排序過程中的存儲

43、器不同，可將排序方法分為兩大類；一類是內(nèi)部排序，指的是待排序記錄存放在計算機(jī)隨機(jī)存儲器中進(jìn)行的排序過程。另一類是外部排序，指的是待排序記錄的數(shù)量很大，，以至內(nèi)存一次不能容納全部記錄，在排序過程中尚需對外存進(jìn)行訪問的排序過程。在鏈表的操作中常用到兩個標(biāo)準(zhǔn)函數(shù)malloc和free。通常,在設(shè)有“指針”數(shù)據(jù)類型的高級語言中均存在與其相應(yīng)的過程與函數(shù)。假設(shè)p和q是LinkList型的結(jié)點(diǎn)，則執(zhí)行p=(LinkList)malloc(size

44、of(LNode))的作用是由系統(tǒng)生成一個Lnode型的結(jié)點(diǎn)，同時將該結(jié)點(diǎn)的起始位置賦給指針變量p；反之執(zhí)行free的作用是由系統(tǒng)回收一個LNode型的結(jié)點(diǎn)，，回收后的空間可以備做再次生成結(jié)點(diǎn)時用。因此，單鏈表和順序存儲不同，它是一種動態(tài)結(jié)構(gòu)。整個可用存儲空間可為多個鏈表共同享用，每個鏈表占用的空間不需要預(yù)先分配劃定，而是可以由系統(tǒng)即使生成。因此建立線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的過程就是動態(tài)生成鏈表的

45、　Viod CreateList_L(LinkList&L,int n){　　//逆位序輸入n個元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表L。 　　L=（LinkList）malloc(sizef(LNode)); 　　L—>next=NULL;//先建立一個帶頭節(jié)點(diǎn)的單鏈表 &l

46、t;p>　　For(i=n;i>n;--i){ 　　p=(LinkList)malloc(sizeof(LNode)), //生成新結(jié)點(diǎn) 　　scanf(&p—>data); 　　p—>next=L—>next;L—>next=p; <p

47、>　　} 　　}//CrateList_L　　2.6.4算法模塊設(shè)計　　2.6.4.1創(chuàng)建鏈表模塊　　創(chuàng)建鏈表，首先由主函數(shù)輸入要創(chuàng)建的鏈表長度n，在由主函數(shù)將參數(shù)傳遞到創(chuàng)建鏈表函數(shù)creat，由For循環(huán)控制表節(jié)點(diǎn)的創(chuàng)建，由m

48、alloc函數(shù)開辟新的結(jié)點(diǎn)空間，創(chuàng)建鏈表結(jié)束后，由print函數(shù)將鏈表元素輸出。　　創(chuàng)建鏈表函數(shù)的實(shí)現(xiàn)代碼如下：　　#include<stdlib.h>　　#include<stdio.h>　　#include<conio.h><

49、/p>　　#include<malloc.h>　　#define L sizeof(struct Node)　　struct Node //結(jié)構(gòu)體　　{　　long int number;<

50、;/p>　　struct Node *next;　　};　　struct Node *create(int a)//鏈表創(chuàng)建函數(shù)　　{ int n;　　struct

51、Node *p1, *p2, *head;　　head = NULL;　　n = 0;　　p2 = p1 = (struct Node *) malloc(L); //分配內(nèi)存　　scanf("%ld", &

52、;p1->number);　　while (a)//錄入鏈表信息　　{　　n = n + 1;　　if (n == 1)　　head = p1;

53、　　else　　p2->next = p1;　　p2 = p1;　　p1 = (struct Node *) malloc(L);　　if (a != 1)//分配內(nèi)存

54、　　scanf("%ld", &p1->number);　　a--; //控制輸入的個數(shù)　　}　　p2->next = NULL;　　return (head);</p

55、>　　}//鏈表創(chuàng)建函數(shù)結(jié)束　　2.6.4.2輸出函數(shù)模塊　　待鏈表輸入完成后，定義單鏈表的頭結(jié)點(diǎn)*p，通過運(yùn)用一個循環(huán)語句，將鏈表內(nèi)的元素一一輸出在執(zhí)行程序界面上。　　void print(struct Node *head)//輸出函數(shù)&l

56、t;b>　　{　　struct Node *p;　　p = head;　　printf("數(shù)字:\n");　　if (head != NULL)

57、　do //循環(huán)實(shí)現(xiàn)輸出　　{　　printf("%ld", p->number);　　printf(" ");　　p

58、= p->next;　　} while (p != NULL);　　printf("\n");　　}　　2.6.4.3鏈表交叉合并模塊　　struct Node *

59、inter_link(struct Node * chain1, int a, struct Node * chain2, int b) {　　int temp;　　struct Node *head, *p1, *p2, *pos;　　/*判斷a，b大小并合并 */<

60、/p>　　if (a >= b) {　　head = p1 = chain1;　　p2 = chain2;　　} else/*b>a*/ {　　head = p1 = chain2;　　p2

61、 = chain1;　　temp = a, a = b, b = temp; /*交換a和b*/　　}　　/*下面把p1的每個元素插在p2相應(yīng)元素之前，p1長a,p2長b*/　　pos = head; /*此時pos指向p1中的第一個

62、元素*/　　while (p2 != NULL) {//漂亮，蛇形插入　　p1 = p1->next;　　pos->next = p2;　　pos = p2;　　p2 = p2-&

63、gt;next;　　pos->next = p1;　　pos = p1;　　}　　return head;　　}

64、;　　2.6.4.4鏈表排序模塊　　void InsertSort(struct Node *p, int m)//排序函數(shù)　　{　　int i, j, t;　　struct Node *k;

65、　　k = p;　　for (i = 0; i < m - 1; i++) {　　for (j = 0; j < m - i - 1; j++) {　　if (p->number > (p->next)-

66、>number) {　　t = p->number;　　p->number = (p->next)->number;　　(p->next)->number = t;　　}

67、　　p = p->next;　　}　　p = k;　　}　　}<

68、p>　　2.6.4.5主函數(shù)模塊　　int main()//main函數(shù)　　{　　struct Node *p1, *p2;　　int a;<

69、b>　　int b;　　int h;　　printf("請輸入第一個鏈表:\n");　　printf("\n輸入鏈表的長度a:\n");　　scanf("%d

70、", &a);　　printf("請輸入鏈表數(shù)據(jù)：");　　p1 = create(a);　　printf("\n你剛才輸入的第一個鏈表信息:\n ");　　print(p1);<p&

71、gt;　　printf("\n 請輸入第二個鏈表:\n");　　printf("\n輸入鏈表的長度b:\n");　　scanf("%d", &b);　　printf("請輸入鏈表數(shù)據(jù)：");<p&

72、gt;　　p2 = create(b);　　printf("\n你剛才輸入的第二個鏈表的信息:\n");　　print(p2);　　p1 = inter_link(p1, a, p2, b);　　h = a + b;<p&

73、gt;　　printf("\n合并后的鏈表\n：");　　print(p1);　　InsertSort(p1, h);　　printf("\n排序后的鏈表:\n");　　print(p1);

74、　　return 0;　　}　　2.7程序運(yùn)行分析　　打開軟件，根據(jù)提示先輸入鏈表ａ的長度，再輸入鏈表ａ的元素，然后輸出鏈表ａ。　　重復(fù)上述步驟輸出鏈表ｂ。&

75、lt;/p>　　之后程序完成對鏈表ａ、ｂ合并，然后輸出鏈表ｃ最后輸出排序后的鏈表.　　當(dāng)輸入的元素長度超過鏈表的長度是只讀入并輸出與鏈表的長度相同的元素個數(shù)。　　總結(jié)　　這幾天的課程設(shè)計，讓我對以往課堂上學(xué)習(xí)到的理論知識得到了更深刻的理解，通過自己

76、設(shè)計算法，調(diào)試程序一系列操作，最后才能使程序正確無誤的運(yùn)行，這一系列操作雖然對于我來說很復(fù)雜困難，但是通過查閱資料，以及同學(xué)的幫忙最終還是完成了本次課程設(shè)計。以往對于鏈表的問題有些一知半解，有些東西也不是特別的明白清楚，有了這次課設(shè)感覺自己把以往認(rèn)為很抽象的問題變得更具體，自己親手來做這次課程設(shè)計，感覺有些明白了《數(shù)據(jù)結(jié)構(gòu)》這門課程其中的奧妙。我做兩個鏈表的合并，想象起來并不是特別的困難，用語言很容易的就可以表達(dá)出來，對于這次課設(shè)就是

77、編寫代碼來完成這一系列的操作，編寫代碼需要相當(dāng)?shù)募有⌒模粋€字母的錯誤就能導(dǎo)致整個程序的錯誤，所以編寫代碼需要心細(xì)不能馬虎任何一個小的字母。我經(jīng)過查閱資料，詢問同學(xué)，多次的修改程序才使得程序最后的成功運(yùn)行。有了這次課設(shè)，不僅讓我對這門課程有了新的認(rèn)識和對知識的更深刻的理解，同時也磨練了自己的耐心和毅力。以后學(xué)習(xí)中還需要繼續(xù)努力學(xué)好這門課程。　　參考文獻(xiàn)<

78、;/p>　　[1] 葉乃文,鄭曉紅. 數(shù)據(jù)結(jié)構(gòu)[M]. 北京：人民郵電出版社，2001.5：75-90 　　[2] 趙國玲. C語言與數(shù)據(jù)結(jié)構(gòu)[M]. 北京：電子工業(yè)出版社，1999.11：120-146 　　[3] 嚴(yán)蔚敏,吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版）[M]. 北京：清華大學(xué)出版社，2006.10：44-52 <

79、/p>　　[4] 蔡子經(jīng)，施伯樂. 數(shù)據(jù)結(jié)構(gòu)教程[M]. 上海：復(fù)旦大學(xué)出版社，2006.4:168-207　　[5]李春褒.數(shù)據(jù)結(jié)構(gòu)教程(第二版)[M].北京:清華大學(xué)出版社,2007.3:22-46 　　[6] 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu) C語言[M].北京: 清華大學(xué)出版社,2006.10: 110-135

80、　　[7] 嚴(yán)蔚敏,陳文博.數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程[M].北京:清華大學(xué)出版社,2003.6: 121-156 　　[8] 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)習(xí)題[M].北京:清華大學(xué)出版社,2002.3: 67-98 　　附錄　　#include<stdlib.h

81、>　　#include<stdio.h>　　#include<conio.h>　　#include<malloc.h>　　#define L sizeof(struct Node)　　st

82、ruct Node //結(jié)構(gòu)體　　{　　long int number;　　struct Node *next;　　};　　struct Node *cr

83、eate(int a)//鏈表創(chuàng)建函數(shù)　　{　　int n;　　struct Node *p1, *p2, *head;　　head = NULL;<

84、;b>　　n = 0;　　p2 = p1 = (struct Node *) malloc(L); //分配內(nèi)存　　scanf("%ld", &p1->number);　　while (a)//錄入鏈表信息<

85、;b>　　{　　n = n + 1;　　if (n == 1)　　head = p1;　　else　　p2->next = p1;<

86、;p>　　p2 = p1;　　p1 = (struct Node *) malloc(L);　　if (a != 1)//分配內(nèi)存　　scanf("%ld", &p1->number);　　a-

87、-; //控制輸入的個數(shù)　　}　　p2->next = NULL;　　return (head);　　}//鏈表創(chuàng)建函數(shù)結(jié)束　　void print(struct Node *head)

88、//輸出函數(shù)　　{　　struct Node *p;　　p = head;　　printf("數(shù)字:\n");　　if (head !

89、= NULL)　　do//循環(huán)實(shí)現(xiàn)輸出　　{　　printf("%ld", p->number);　　printf(" ");　　p =

90、p->next;　　} while (p != NULL);　　printf("\n");　　}　　//鏈表的交叉合并算法　　struct Node * inter_

91、link(struct Node * chain1, int a, struct Node * chain2, int b) {　　int temp;　　struct Node *head, *p1, *p2, *pos;　　/*判斷a，b大小并合并 */

92、　　if (a >= b) {　　head = p1 = chain1;　　p2 = chain2;　　} else/*b>a*/ {　　head = p1 = chain2;　　p2 = cha

93、in1;　　temp = a, a = b, b = temp; /*交換a和b*/　　}　　/*下面把p1的每個元素插在p2相應(yīng)元素之前，p1長a,p2長b*/　　pos = head; /*此時pos指向p1中的第一個元素*/&l

94、t;/p>　　while (p2 != NULL) {//漂亮，蛇形插入　　p1 = p1->next;　　pos->next = p2;　　pos = p2;　　p2 = p2->nex

95、t;　　pos->next = p1;　　pos = p1;　　}　　return head;　　}</

96、p>　　//對合并好的鏈表進(jìn)行排序　　void InsertSort(struct Node *p, int m)//排序函數(shù)　　{　　int i, j, t;　　struct Node *k;</p

97、>　　k = p;　　for (i = 0; i < m - 1; i++) {　　for (j = 0; j < m - i - 1; j++) {　　if (p->number > (p->next)->nu

98、mber) {　　t = p->number;　　p->number = (p->next)->number;　　(p->next)->number = t;　　}<p

99、>　　p = p->next;　　}　　p = k;　　}　　}&

100、lt;b>　　//主函數(shù)　　int main()//main函數(shù)　　{　　struct Node *p1, *p2;　　int a;<p&g

101、t;　　int b;　　int h;　　printf("請輸入第一個鏈表:\n");　　printf("\n輸入鏈表的長度a:\n");　　scanf(&q

102、uot;%d", &a);　　printf("請輸入鏈表數(shù)據(jù)：");　　p1 = create(a);　　printf("\n你剛才輸入的第一個鏈表信息:\n ");　　print(p1);

103、　　printf("\n 請輸入第二個鏈表:\n");　　printf("\n輸入鏈表的長度b:\n");　　scanf("%d", &b);　　printf("請輸入鏈表數(shù)據(jù)：");

104、　　p2 = create(b);　　printf("\n你剛才輸入的第二個鏈表的信息:\n");　　print(p2);　　p1 = inter_link(p1, a, p2, b);　　h = a + b;

105、　　printf("\n合并后的鏈表\n：");　　print(p1);　　InsertSort(p1, h);　　printf("\n排序后的鏈表:\n");　　print(p1);<

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

課程設(shè)計鏈表的交叉合并課程設(shè)計

文檔簡介

溫馨提示

最新文檔

評論

課程設(shè)計鏈表的交叉合并課程設(shè)計

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載