數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---數(shù)據(jù)結(jié)構(gòu)相關(guān)算法的演示系統(tǒng)

1、<p><b>　　課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告</b></p><p>　　課程名稱：《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》</p><p>　　設(shè)計(jì)題目：數(shù)據(jù)結(jié)構(gòu)相關(guān)算法的演示系統(tǒng)（1）</p><p>　　院系：信息科學(xué)與工程學(xué)院</p><p><b>　　目錄</b></p><p>

2、　　需求分析………………………………… 3</p><p>　　概要設(shè)計(jì)………………………………… 4</p><p>　　詳細(xì)設(shè)計(jì)………………………………… 6</p><p>　　調(diào)試分析………………………………… 21</p><p>　　測(cè)試結(jié)果………………………………… 23</p><p>　　課程設(shè)計(jì)總結(jié)

3、…………………………… 33</p><p>　　參考文獻(xiàn)…………………………………34</p><p>　　附錄………………………………………34</p><p><b>　　一、需求分析：</b></p><p>　　設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)相關(guān)算法的演示系統(tǒng)，主要實(shí)現(xiàn)的功能如下：</p><p>　

4、　1：順序表的插入、刪除和合并等基本操作；</p><p>　　2: 利用插入運(yùn)算建立鏈表；實(shí)現(xiàn)鏈表的插入、刪除、計(jì)數(shù)、輸出及有序鏈表的合并；</p><p>　　3：串的模式匹配（包括求next值和nextval值）。</p><p>　　基于以上要求，可以在設(shè)計(jì)系統(tǒng)的時(shí)候，在主界面設(shè)計(jì)三個(gè)大模塊，即是按照要求來(lái)劃分模塊，每個(gè)模塊實(shí)現(xiàn)不同的功能要求，第一個(gè)模塊就實(shí)

5、現(xiàn)線性表的相關(guān)操作，第二個(gè)模塊就實(shí)現(xiàn)鏈表的相關(guān)操作，第三個(gè)模塊就實(shí)現(xiàn)串的相關(guān)操作。</p><p>　　（一）：在第一個(gè)模塊中，即是順序表的相關(guān)操作中，主要能實(shí)現(xiàn)順序表的循環(huán)插入賦值，插入、刪除和合并等基本操作，順序表的元素可以是數(shù)字也可以是字符等，但是在程序中已經(jīng)定義ElemType為int型，故輸入的形式為整數(shù)，采用的是動(dòng)態(tài)存儲(chǔ)分配（初始定義LIST_INIT_SIZE 100），當(dāng)輸入的元素過(guò)多內(nèi)存不足是會(huì)

6、自動(dòng)添加（LISTINCREMENT 10），當(dāng)然輸出的也是整數(shù)，第一個(gè)模塊根據(jù)功能分為幾個(gè)小菜單項(xiàng)，以下是測(cè)試數(shù)據(jù)：</p><p>　　順序表的初始化，輸入1、2、3、4以‘00’結(jié)束，輸出為：初始化后的順序表元素為NO.0 1, NO.0 2, NO.0 3, NO.0 4, 當(dāng)然元素個(gè)數(shù)沒(méi)有限制，但是單個(gè)的元素值限制，因?yàn)橐粋€(gè)int型數(shù)據(jù)通常用兩個(gè)字節(jié)存放，即是16位二進(jìn)制，當(dāng)輸入的數(shù)值超過(guò)這個(gè)范

7、圍是計(jì)算機(jī)打印出亂碼，此時(shí)可以選擇重新輸入數(shù)據(jù)。</p><p>　　在順序表的插入操作中，要求你輸入插入的位置和插入的值，例如在上面初始化的基礎(chǔ)上，在第4個(gè)位置插入4，結(jié)果為：插入元素后的順序表元素為 NO.0 1, NO.0 2, NO.0 3, NO.0 4,當(dāng)插入的位置大于了已有的表長(zhǎng)度，則系統(tǒng)會(huì)提醒輸入錯(cuò)誤，請(qǐng)重新輸入！刪除操作和插入操作一樣，首先選擇要?jiǎng)h除的元素位置，例刪除第二個(gè)元素，結(jié)果為：

8、刪除操作后順序表的元素是NO.0 1, NO.0 3, NO.0 4,同樣的當(dāng)所選擇的位置大于了當(dāng)前已有的長(zhǎng)度，則系統(tǒng)提起輸入錯(cuò)誤，請(qǐng)重新輸入！！</p><p>　　在順序表的合并操作中，主要是把兩個(gè)元素值非遞減排列的線性表合并為一個(gè)，并且合并后的順序表值也是非遞減的，輸入另外一個(gè)順序表的元素，例輸入4、5、6，結(jié)果為：合并后的順序表元素為NO.0 1, NO.0 2, NO.0 3, NO.0

9、4,、NO.0 5, NO.0 6, 當(dāng)所輸入的元素值不是按非遞減的順序，例兩表的元素分別為6、2、1和8、4、3時(shí)，結(jié)果為6、2、1、8、4、3，并無(wú)順序。</p><p>　　（二）：在第二個(gè)大模塊中，主要實(shí)現(xiàn)的是鏈表的初始化，插入，刪除，計(jì)數(shù)，查詢和有序鏈表的合并功能，并且有檢錯(cuò)和改錯(cuò)的能力，和線性表的一樣，定義的數(shù)據(jù)類型為int型，故所輸入的也是整數(shù)，元素個(gè)數(shù)不限，但是單個(gè)的元素值有限，鏈表不需要為其

10、開辟一塊內(nèi)存空間，是非隨機(jī)存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)，以下是測(cè)試數(shù)據(jù)：</p><p>　　在鏈表的初始化中，要求先輸入要插入的元素個(gè)數(shù)，如3個(gè)分別是3、2、1，并逆序插入，結(jié)果為：初始化后的鏈表的值為1、2、3，鏈表長(zhǎng)度為3，和線性表一樣當(dāng)所輸入的元素值超過(guò)int型的字節(jié)后，就會(huì)出現(xiàn)亂碼，該模塊中對(duì)鏈表的計(jì)數(shù)是結(jié)合在每一個(gè)功能中，當(dāng)對(duì)鏈表進(jìn)行操作后可以自動(dòng)返回鏈表的長(zhǎng)度即是計(jì)數(shù)功能，此時(shí)可以重新輸入元素在進(jìn)行下面的操作。&

11、lt;/p><p>　　在鏈表的插入功能中，可以根據(jù)已有的鏈表選擇插入的位置和插入值，例在初始化的基礎(chǔ)上在第4個(gè)位置插入4，結(jié)果為：插入成功，插入后鏈表的元素為1、2、3、4，鏈表長(zhǎng)度為4，如果輸入的位置大于了已有的鏈表長(zhǎng)度，那么系統(tǒng)會(huì)提醒輸入錯(cuò)誤，請(qǐng)重新輸入插入的位置和元素值，或者可以鍵入‘0’直接返回上一級(jí)菜單。刪除功能和插入功能基本上一致，首先也是要輸入要?jiǎng)h除的元素位置，例刪除第3號(hào)元素，結(jié)果為：刪除成功，刪除

12、后鏈表的元素為1、2、4，鏈表長(zhǎng)度為3，當(dāng)所輸入的位置大于當(dāng)前的鏈表長(zhǎng)度即不存在該位置，系統(tǒng)提示不存在該節(jié)點(diǎn)，請(qǐng)重新輸入要?jiǎng)h除的位置，如不想刪除操作了，可鍵入‘0’返回上一級(jí)菜單。</p><p>　　選擇了鏈表的合并功能后，系統(tǒng)會(huì)提示初始化另外一個(gè)鏈表，輸入元素個(gè)數(shù)和元素值，該合并功能也是按元素的非遞減進(jìn)行合并，合并后的鏈表元素也是按非遞減的順序排列，例輸入3個(gè)元素，分別為6、5、4逆序插入，結(jié)果為：Lb鏈表的

13、初始化元素為4、5、6，合并后的鏈表Lc的元素為1、2、4、4、5、6，鏈表長(zhǎng)度為6，當(dāng)輸入的元素沒(méi)有按照非遞減排列時(shí)，合并后的元素也沒(méi)有順序，例La鏈表的元素為2、1、5，Lb的為4、5、9，結(jié)果為合并后的鏈表Lc元素為4、5、2、1、5、9，鏈表長(zhǎng)度為6。</p><p>　　該模塊中最后的功能是查找功能，系統(tǒng)提供兩種查找，一種是按位置查找，一種是按元素的值來(lái)查找，先選擇按位置查查，首先輸入所要查找的位置，例

14、輸入5，結(jié)果是：要查找的數(shù)存在是5，當(dāng)輸入的位置不存在時(shí)系統(tǒng)提醒：該鏈表中不存在該節(jié)點(diǎn)，并要求重新輸入節(jié)點(diǎn)位置，例輸入8是，結(jié)果：該鏈表中不存在第8個(gè)結(jié)點(diǎn)，請(qǐng)重新輸入所要查找的位置。按元素的值查找中，輸入想要查找的元素，例輸入6，結(jié)果為：要查找的數(shù)存在，位置是第6個(gè)，如果輸入的元素不存在，例輸入10，結(jié)果為：要查找的數(shù)不存在，請(qǐng)重新輸入（或者按0返回上級(jí)菜單）。</p><p>　?。ㄈ┰诘谌齻€(gè)模塊中，是串的模

15、式匹配相關(guān)操作，包括簡(jiǎn)單模式匹配和KMP模式匹配，和next與nextval的值的求取，此模塊中定義的數(shù)據(jù)元素是字符型，故輸入的都是字符，輸出時(shí)若是求匹配那么返回的是布爾型即是成功或者不成功，如果是求取next和nextval值那么返回的是整型數(shù)字，以下是測(cè)試的數(shù)據(jù)：</p><p>　　選擇簡(jiǎn)單模式匹配，輸入主串‘a(chǎn)babcabcacbab’,輸入模式串‘a(chǎn)bcac’,簡(jiǎn)單匹配lndex的結(jié)果為：比較次數(shù)6次，

16、模式串t在主串中的位置從第六個(gè)字符開始，匹配成功！</p><p>　　選擇KMP算法匹配，輸入主串‘a(chǎn)babcabcacbab’，輸入模式串‘a(chǎn)bcac’，KMP_lndex的結(jié)果為：比較次數(shù)為3，模式串t在主串s中的位置從第六個(gè)字符開始，匹配成功；修正后的KMP算法匹配后的結(jié)果是比較次數(shù)為6，模式串t在主串中的位置從第六個(gè)字符開始，匹配成功！</p><p>　　求取next值，輸入模

17、式串，例‘a(chǎn)baabcac’，結(jié)果為：next[1] =0, next[2] =1, next[3] =1, next[4] =2, next[5] =2, next[6] =3, next[7] =1, next[8] =2.</p><p>　　求取nextval值，輸入字符‘a(chǎn)aaab’，結(jié)果為nextval[1]=0, nextval[2]=0, nextval[3]=0, nextval[4]=0, n

18、extval[5]=4.</p><p><b>　　二、概要設(shè)計(jì)：</b></p><p>　　（一）系統(tǒng)子程序及其功能設(shè)計(jì)：</p><p>　　本系統(tǒng)共有24個(gè)子程序，各個(gè)子程序的功能如下所示：</p><p>　?。?）Status InitList_Sq(SqList *L) //順序表的初始化，給順序表分配存

19、儲(chǔ)空間，返回值 1</p><p>　?。?）Status ListInsert_Sq(SqList *L,int i,ElemType e) //順序表的插入操作，在第i個(gè)位置插入元素e，返回值 1</p><p>　?。?）Status IsListFull(SqList * L) //如果順序表的存儲(chǔ)空間滿了，給順序表增加存儲(chǔ)空間，返回值 1</p><p>

20、　?。?）Status ListPrint_Sq(SqList *L) // 打印順序表的所有元素，返回值 1</p><p>　　（5）int ListDelete_Sq(SqList *L, int i) //刪除順序表中第i個(gè)位置上的元素，返回值 1</p><p>　　（6）Status MergeList_Sq(SqList La, SqList Lb, SqList *Lc)

21、//將La與Lb兩個(gè)順序表的元素合并為L(zhǎng)c順序表，返回值 1</p><p>　?。?）Status Creat_List(Link_List &L,ElemType n) //初始化鏈表，并插入元素值，返回值 1</p><p>　　（8）Status Insert_List(Link_List &L,int i,ElemType e) //在鏈表第i個(gè)位置之前插入元素e

22、，返回值 1</p><p>　?。?）Status Delete_List(Link_List &L,int i,ElemType &e) //刪除鏈表第i個(gè)位置的元素，返回值 1</p><p>　?。?0）Status Merge_List(Link_List La,Link_List Lb,Link_List &Lc) //合并La與Lb兩個(gè)鏈表為L(zhǎng)c鏈表，

23、返回值 1</p><p>　?。?1）Status Print_List(Link_List L) //打印鏈表的所有元素，返回值 1</p><p>　?。?2）Status GetElem_L(Link_List L,int i,ElemType &e) //返回鏈表中第i個(gè)位置上的元素，返回值 1</p><p>　?。?3）Status searc

24、h(Link_List &L,int n) //遍歷鏈表，如果有元素與n相同則返回其位置，返回值 1</p><p>　?。?4）Status getlength(Link_List L) //返回鏈表的長(zhǎng)度，，返回值 1</p><p>　　（15）int Index(char S[MAXSIZE],char T[MAXSIZE],int pos,int &time)

25、//返回子串T在主串S中第pos個(gè)字符之后的位置，并數(shù)比較次數(shù)，返回值 1</p><p>　　（16）int Index_KMP(char S[MAXSIZE],char T[MAXSIZE],int pos,int &time,int (& next)[MAXSIZE]) //返回子串T在主串S中第pos個(gè)字符之后的位置，并數(shù)比較次數(shù)，返回值 1</p><p>　?。?/p>

26、17）void get_next(char T[MAXSIZE],int next[MAXSIZE]) //求模式串T的next函數(shù)值并存入數(shù)組next</p><p>　　（18）void get_nextval(char T[MAXSIZE],int nextval[MAXSIZE]) //求模式串T的nextval函數(shù)值并存入數(shù)組nextval</p><p>　?。?9）void

27、string_adjust_S(char S[MAXSIZE]) //對(duì)輸入的主串S長(zhǎng)度進(jìn)行調(diào)整</p><p>　　(20)string_adjust_T(char T[MAXSIZE]) //對(duì)輸入的字符串T長(zhǎng)度進(jìn)行調(diào)整</p><p>　?。?1）int function_1() //順序表功能實(shí)現(xiàn)的函數(shù)，包括順序表操作的子界面</p><p>　?。?2）i

28、nt function_2() //鏈表功能實(shí)現(xiàn)的函數(shù)，包括鏈表操作的子界面</p><p>　?。?3）int function_3() //串的模式匹配功能函數(shù)，包括串的操作子界面</p><p>　?。?4）int main() //主函數(shù)，包括主界面，和對(duì)功能函數(shù)的調(diào)用</p><p>　　（二）數(shù)據(jù)類型的定義</p><p>　?。?/p>

29、1）線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)：</p><p>　　#define LIST_INIT_SIZE 100 //線性表存儲(chǔ)空間的初始分配量</p><p>　　#define LISTINCREMENT 10 //線性表存儲(chǔ)空間的分配增量</p><p>　　typedef struct{</p&g

30、t;<p>　　ElemType *elem; //存儲(chǔ)空間基址 </p><p>　　int length; //當(dāng)前長(zhǎng)度</p><p>　　int listsize; //當(dāng)前分配的存儲(chǔ)容量</p><p>&

31、lt;b>　　}SqList;</b></p><p>　　（2）鏈表的存儲(chǔ)結(jié)構(gòu)：</p><p>　　typedef struct Lnode{</p><p>　　ElemType data; //鏈表數(shù)據(jù)類型</p><p>　　struct Lnode * next;

32、 //定義鏈表節(jié)點(diǎn)</p><p>　　}LNode,*Link_List;</p><p>　　（3）串的抽象數(shù)據(jù)類型的定義：</p><p>　　ADT String{</p><p>　　數(shù)據(jù)對(duì)象:D={ai|ai∈CharacterSet,i=1,2,……,n,n>=0}</p>&l

33、t;p>　　數(shù)據(jù)關(guān)系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,……，n}</p><p><b>　　基本操作：</b></p><p>　　Index(S,T,pos) //返回子串T在主串S中第pos個(gè)字符之后的位置，并數(shù)比較次數(shù)，返回值 1</p><p>　　Index_KMP(char S[MAXSI

34、ZE],char T[MAXSIZE],int pos,int &time,int (& next)[MAXSIZE]) //返回子串T在主串S中第pos個(gè)字符之后的位置，并數(shù)比較次數(shù)，返回值 1</p><p>　　get_next(char T[MAXSIZE],int next[MAXSIZE]) //求模式串T的next函數(shù)值并存入數(shù)組next</p><p>　　

35、nextval(char T[MAXSIZE],int nextval[MAXSIZE]) //求模式串T的nextval函數(shù)值并存入數(shù)組nextval</p><p>　　(三) 主程序的流程以及各程序模塊之間的層次(調(diào)用)關(guān)系</p><p>　　進(jìn)入系統(tǒng)主程序后，會(huì)提醒進(jìn)行選擇功能模塊，本系統(tǒng)按照要求共分三個(gè)大模塊：</p><p>　　1：順序表的相關(guān)操作；

36、2：鏈表的相關(guān)操作；3：串的模式匹配，每個(gè)模塊之間互不影響，模塊與模塊之間的轉(zhuǎn)換由主函數(shù)main（）來(lái)調(diào)用，每個(gè)模塊又由幾個(gè)小程序功能組成，每個(gè)小功能實(shí)現(xiàn)后可以退回到當(dāng)前模塊菜單，整個(gè)系統(tǒng)的退出在main（）函數(shù)中，鍵入0退出系統(tǒng)，主程序和三大模塊的主要流程如下所示：</p><p><b>　　三、詳細(xì)設(shè)計(jì)</b></p><p>　　系統(tǒng)主要子程序詳細(xì)設(shè)計(jì)如下：&

37、lt;/p><p>　?。?）主函數(shù)，設(shè)定用戶操作界面以及顏色和調(diào)用工作區(qū)功能函數(shù)</p><p>　　int main(){</p><p>　　system("color 70");</p><p><b>　　while(1){</b></p><p>　　printf(&

38、quot;\t☆==☆==☆==☆==☆==☆==☆==☆==☆==☆==☆==☆==☆==☆==☆\n");</p><p>　　printf("\t☆\t\t\t\t\t\t\t☆\n");</p><p>　　printf("\t||\t\t\t\t\t\t\t||\n");</p><p>　　printf(

39、"\t☆\t\t§歡迎進(jìn)入數(shù)據(jù)結(jié)構(gòu)演示系統(tǒng)§\t\t☆\n");</p><p>　　printf("\t||\t\t\t\t\t\t\t||\n");</p><p>　　printf("\t☆\t\t\t\t\t\t\t☆\n");</p><p>　　printf("\t

40、☆\t\t 1:順序表的相關(guān)操作演示\t\t\t☆\n");</p><p>　　printf("\t||\t\t\t\t\t\t\t||\n");</p><p>　　printf("\t☆\t\t\t\t\t\t\t☆\n");</p><p>　　printf("\t||\t\t 2:鏈表的相關(guān)操作演

41、示\t\t\t||\n");</p><p>　　printf("\t☆\t\t\t\t\t\t\t☆\n");</p><p>　　printf("\t||\t\t\t\t\t\t\t||\n");</p><p>　　printf("\t☆\t\t 3:串的相關(guān)操作演示\t\t\t☆\n");

42、</p><p>　　printf("\t||\t\t\t\t\t\t\t||\n");</p><p>　　printf("\t☆\t\t 0:退出系統(tǒng)\t\t\t\t☆\n");</p><p>　　printf("\t||\t\t\t\t\t\t\t||\n");</p><p&g

43、t;　　printf("\t☆==☆==☆==☆==☆==☆==☆==☆==☆==☆==☆==☆==☆==☆==☆\n");</p><p>　　int choose;</p><p>　　printf("\t請(qǐng)選擇要實(shí)現(xiàn)的功能:");</p><p>　　scanf("%d",&choose);&

44、lt;/p><p>　　system("CLS");</p><p>　　switch(choose){</p><p><b>　　case 1:</b></p><p>　　function_1();break;</p><p><b>　　case 2:</b

45、></p><p>　　function_2();break;</p><p><b>　　case 3:</b></p><p>　　function_3();break;</p><p>　　case 0: return 1;</p><p><b>　　default:<

46、;/b></p><p>　　printf("\n輸入錯(cuò)誤，請(qǐng)重新輸入??！\n");break;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p&

47、gt;　?。?）第一大模塊的功能函數(shù)function_1(),里面包括順序表的操作界面和對(duì)順序表功能函數(shù)的調(diào)用，主要結(jié)構(gòu)還是運(yùn)用了switch，case語(yǔ)句來(lái)進(jìn)行選擇，</p><p>　　int function_1(){</p><p>　　SqList La,Lb,Lc;</p><p>　　int k=1,c=1,i,a,num;</p>&l

48、t;p>　　printf("\t\t ☆==☆==☆==☆==☆==☆==☆==☆☆☆\n");</p><p>　　printf("\t\t\t\t\t\t\t\n");</p><p>　　printf("\t\t\t☆ §歡迎進(jìn)入順序表操作界面§\t☆\n");</p>&

49、lt;p>　　printf("\t\t\t\t\t\t\t\t\n");</p><p><b>　　while(1){</b></p><p>　　printf("\t\t\t ☆ 1:順序表的初始化\t ☆\n");</p><p>　　printf("\t\t\t\t\t\t\

50、t\t\n");</p><p>　　printf("\t\t\t || 2:順序表的插入\t ||\n");</p><p>　　printf("\t\t\t\t\t\t\t\t\n");;</p><p>　　printf("\t\t\t ☆ 3:順序表的刪除\t ☆\n");&l

51、t;/p><p>　　printf("\t\t\t\t\t\t\t\t\n");</p><p>　　printf("\t\t\t || 4:順序表的合并\t ||\n");</p><p>　　printf("\t\t\t\t\t\t\t\t\n");</p><p>　　pri

52、ntf("\t\t\t ☆ 0:返回上級(jí)菜單\t ☆\n");</p><p>　　int choose;</p><p>　　printf("\n\t\t請(qǐng)選擇對(duì)順序表的操作:");</p><p>　　scanf("%d",&choose);</p><p>　　s

53、ystem("CLS");</p><p>　　switch(choose){</p><p><b>　　case 1:</b></p><p>　　printf("順序表La的初始化，給La輸入數(shù)值，以00為結(jié)束:\n");</p><p>　　InitList_Sq(&

54、;La);</p><p>　　while(1) </p><p><b>　　{ </b></p><p>　　scanf("%d", &num); </p><p>　　if(num == 00) </p><p><b>　　break;

55、 </b></p><p>　　ListInsert_Sq(&La, k, num); </p><p><b>　　k++;</b></p><p><b>　　}</b></p><p>　　printf("初始化后的La順序表的元素為：\n");&l

56、t;/p><p>　　ListPrint_Sq(&La);break;</p><p><b>　　case 2:</b></p><p>　　printf("初始化后的La順序表的元素為：\n");</p><p>　　ListPrint_Sq(&La);</p><

57、p>　　printf("請(qǐng)選擇要插入的位置和插入值："); </p><p>　　scanf("%d%d",&i,&a);getchar();</p><p>　　while(i>k){printf("\n輸入錯(cuò)誤，請(qǐng)重新輸入\n");scanf("%d%d",&i,&

58、;a);}</p><p>　　//getchar();</p><p>　　ListInsert_Sq(&La,i,a);</p><p>　　printf("插入操作后的La順序表的元素為：\n");</p><p>　　ListPrint_Sq(&La);</p><p>　　

59、break; //順序表的插入</p><p><b>　　case 3:</b></p><p>　　printf("插入操作后的La順序表的元素為：\n");</p><p>　　ListPrint_Sq(&La);</p><p>　　printf("請(qǐng)選擇要?jiǎng)h除的位置：&qu

60、ot;); </p><p>　　scanf("%d",&i);</p><p>　　while(i-1>La.length-1){printf("\n輸入錯(cuò)誤，請(qǐng)重新輸入\n"); scanf("%d",&i);}</p><p>　　ListDelete_Sq(&La,i)

61、;</p><p>　　printf("\n刪除操作后順序表的值為：\n");</p><p>　　ListPrint_Sq(&La);getchar();</p><p>　　break; //順序表的刪除</p><p><b>　　case 4:</b></p><p

62、>　　InitList_Sq(&Lb);</p><p>　　printf("順序表Lb的初始化，給Lb輸入數(shù)值，以00為結(jié)束:\n"); </p><p>　　while(1){ </p><p>　　scanf("%d", &num);getchar(); </p><p&

63、gt;　　if(num == 00) </p><p><b>　　break; </b></p><p>　　ListInsert_Sq(&Lb, c, num); </p><p><b>　　c++; </b></p><p><b>　　}</b>

64、;</p><p>　　printf("初始化后的Lb順序表的元素為：\n");</p><p>　　ListPrint_Sq(&Lb); </p><p>　　MergeList_Sq(La,Lb,&Lc);</p><p>　　printf("合并后的Lc順序表的元素為：\n");&

65、lt;/p><p>　　ListPrint_Sq(&Lc);printf("請(qǐng)選擇要?jiǎng)h除的位置："); </p><p>　　scanf("%d",&i);</p><p>　　while(i-1>Lc.length-1){printf("\n輸入錯(cuò)誤，請(qǐng)重新輸入\n"); scanf(&

66、quot;%d",&i);}ListDelete_Sq(&Lc,i);</p><p>　　printf("\n刪除操作后順序表的值為：\n");</p><p>　　ListPrint_Sq(&Lc);getchar();</p><p>　　continue; //順序表的合并</p><

67、p>　　case 0:return 1;</p><p><b>　　default:</b></p><p>　　printf("\n輸入錯(cuò)誤，請(qǐng)重新輸入?。n");break;</p><p><b>　　}</b></p><p><b>　　}</

68、b></p><p><b>　　}</b></p><p>　　以下是第一個(gè)模塊中調(diào)用到的算法：</p><p>　　Status InitList_Sq(SqList *L){</p><p>　　L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(E

69、lemType));</p><p>　　L->length = 0; //空表長(zhǎng)度為0</p><p>　　L->listsize = LIST_INIT_SIZE; //初始存儲(chǔ)容量</p><p><b>　　return 1;</b></p><p&g

70、t;　　}//InitList_Sq;//初始化線性表</p><p>　　順序表的初始化算法， 采用的是動(dòng)態(tài)分配存儲(chǔ)結(jié)構(gòu)。</p><p>　　Status ListInsert_Sq(SqList *L,int i,ElemType e){</p><p>　　//在順序線性表L中第i個(gè)位置之前插入新的元素e，</p><p>　　Ele

71、mType *newbase, *p, *q; </p><p>　　if(i<1||i>L->length+1) return ERROR; //i值不合法</p><p>　　if(L->length>=L->listsize){ //當(dāng)前存儲(chǔ)空間已滿，增加分配</p><p>　　newbase = (El

72、emType *)realloc(L->elem,(L->listsize + LISTINCREMENT)*sizeof(ElemType));</p><p>　　if(!newbase)exit(OVERFLOW); //存儲(chǔ)分配失敗</p><p>　　L->elem = newbase; //新基址</

73、p><p>　　L->listsize +=LISTINCREMENT; //增加存儲(chǔ)容量</p><p><b>　　}</b></p><p>　　q = &(L->elem[i-1]); //q為插入位置</p><p>　　for(p

74、 = &(L->elem[L->length-1]);p>=q;--p){</p><p>　　*(p+1) = *p;} //插入位置及之后的元素右移</p><p>　　*q = e; //插入e</p><p>　　++L->

75、length; //表長(zhǎng)增1</p><p><b>　　return 1;</b></p><p>　　}//ListInsert_Sq</p><p>　　順序表的插入算法，首先判斷插入位置，如果溢出返回ERROR，然后進(jìn)行內(nèi)存判斷，如果內(nèi)存不足，則增加內(nèi)存，找到插入位置，將插

76、入點(diǎn)后面的元素全部右移，然后插入值，表長(zhǎng)度加一。</p><p>　　Status IsListFull(SqList * L) </p><p><b>　　{ </b></p><p>　　//若線性列表長(zhǎng)度等于已為線性列表分配的內(nèi)存大小 </p><p>　　//在插入元素后，線性列表的長(zhǎng)度可能超過(guò)初始的l

77、istsize， </p><p>　　//則再為其分配增量為L(zhǎng)ISTINCREMENT大小的內(nèi)存空間 </p><p>　　return L->length = L->listsize; </p><p><b>　　}</b></p><p>　　順序表內(nèi)存的判斷，如果順序表的內(nèi)存已滿，則可以增加順序

78、表的內(nèi)存</p><p>　　Status ListPrint_Sq(SqList *L) </p><p><b>　　{ </b></p><p>　　int i = 0; </p><p>　　ElemType num = 0; //用于取出每個(gè)數(shù)據(jù)項(xiàng)的值 </p><p>

79、　　for(i=0;i<L->length;i++) </p><p><b>　　{ </b></p><p>　　num = L->elem[i]; </p><p>　　printf("NO.%d\t%d\n",i, num); </p><p><b>

80、　　} </b></p><p><b>　　return 1;</b></p><p><b>　　} </b></p><p>　　順序表元素的打印函數(shù)，從表頭開始，往后一直遍歷，打印出所有的元素 </p><p>　　int ListDelete_Sq(SqList *L,

81、 int i) </p><p><b>　　{ </b></p><p>　　int j; // i--; </p><p>　　//要?jiǎng)h除的元素下標(biāo)不在長(zhǎng)度范圍內(nèi) </p><p>　　if(i<1 || i>L->length+1) </p><p>　　ret

82、urn 0; </p><p>　　//刪除第i個(gè)元素，即刪除下標(biāo)為[i-1]的元素 </p><p><b>　　i--; </b></p><p>　　//使得第i-1個(gè)元素后面的所有元素往前移 </p><p>　　for(j=i;j<L->length;j++) </p>&

83、lt;p>　　L->elem[j] = L->elem[j+1]; </p><p><b>　　//i--;</b></p><p>　　//使得線性表的長(zhǎng)度減 </p><p>　　L->length--; </p><p>　　return 1; </p><p

84、><b>　　} </b></p><p>　　順序表的刪除算法，首先判斷輸入的插入位置，如果溢出返回0，否則找到該位置，使之后的所有元素左移一位，表的長(zhǎng)度減一。</p><p>　　Status MergeList_Sq(SqList La, SqList Lb, SqList *Lc) </p><p><b>　　

85、{ </b></p><p>　　ElemType *pa = La.elem, *pb = Lb.elem, *pc; </p><p>　　ElemType *pa_last, *pb_last; //確定Lc線性表的長(zhǎng)度為兩個(gè)線性表的長(zhǎng)度之和 </p><p>　　Lc->listsize = Lc->length = L

86、a.length+Lb.length; //為L(zhǎng)c線性表分配內(nèi)存空間 </p><p>　　pc = Lc->elem = (ElemType*)malloc(Lc->listsize*sizeof(ElemType)); //若分配內(nèi)存溢出，則退出 </p><p>　　if(!Lc->elem) </p><p>　　exit(

87、OVERFLOW); //使得pa_last指針指向La線性表的最后一個(gè)元素 </p><p>　　pa_last = La.elem + La.length - 1; //使得pb_last指針指向Lb線性表的最后一個(gè)元素 </p><p>　　pb_last = Lb.elem + Lb.length - 1; //將兩個(gè)線性表中的值都逐個(gè)賦值到新的線性表Lc中 &l

88、t;/p><p>　　//當(dāng)兩個(gè)線性表中的值都還未完成賦值時(shí)，先將兩個(gè)值中較小的賦值給Lc線性表的當(dāng)前元素 </p><p>　　while(pa<=pa_last&&pb<=pb_last) </p><p>　　*pc++ = (*pa <= *pb ? *pa++:*pb++); //如果兩個(gè)線性表中的任一個(gè)較長(zhǎng)的部分繼

89、續(xù)賦值給Lc線性表 </p><p>　　while(pa<=pa_last) </p><p>　　*pc++ = *pa++; </p><p>　　while(pb<=pb_last) </p><p>　　*pc++ = *pb++; </p><p>　　return 1; &

90、lt;/p><p>　　順序表的合并算法，首先定義一個(gè)表長(zhǎng)度等一兩表長(zhǎng)度之和的順序表，定義兩個(gè)指針?lè)謩e指向兩個(gè)順序表的第一個(gè)元素，然后比較元素值的大小，將較小的一個(gè)插入到新表中，指針后移，直到其中一個(gè)順序表操作完，順序插入另外一個(gè)表的剩余段。</p><p>　　} （3）第二大模塊是對(duì)鏈表的相關(guān)操作，同樣，在function_2（）中，有對(duì)鏈表的操作界面，還是運(yùn)用switch，case語(yǔ)

91、句來(lái)進(jìn)行函數(shù)的調(diào)用，</p><p>　　int function_2(){</p><p>　　Link_List L1,L2,L3;</p><p>　　ElemType e;</p><p>　　int n,y,w,i,m,choise;</p><p>　　printf("\t\t ☆==

92、☆==☆==☆==☆==☆==☆==☆☆☆\n");</p><p>　　printf("\t\t\t\t\t\t\t\n");</p><p>　　printf("\t\t ☆§歡迎進(jìn)入鏈表操作界面§ ☆\n");</p><p>　　printf("\t\t\t\

93、t\t\t\t\t\n");</p><p><b>　　while(1){</b></p><p>　　printf("\t\t\t ☆ 1:鏈表的初始化\t ☆\n");</p><p>　　printf("\t\t\t || 2:鏈表的插入\t ||\n");</p>

94、;<p>　　printf("\t\t\t\t\t\t\t\t\n");;</p><p>　　printf("\t\t\t ☆ 3:鏈表的刪除\t ☆\n");</p><p>　　printf("\t\t\t || 4:鏈表的合并\t ||\n");</p><p>　　pri

95、ntf("\t\t\t\t\t\t\t\t\n");</p><p>　　printf("\t\t\t || 5:鏈表的按位置查找||\n");</p><p>　　printf("\t\t\t || 6:鏈表的按元素查找||\n");</p><p>　　printf("\t\t\t

96、\t\t\t\t\t\n");</p><p>　　printf("\t\t\t ☆ 0:返回上級(jí)菜單\t ☆\n");</p><p>　　int choose;</p><p>　　printf("\n\t\t請(qǐng)選擇對(duì)鏈表的操作:");</p><p>　　scanf("%

97、d",&choose);</p><p>　　system("CLS");</p><p>　　switch(choose){</p><p>　　case 0:return 1;</p><p><b>　　case 1:</b></p><p>　　pri

98、ntf("建立一個(gè)數(shù)據(jù)個(gè)數(shù)為n的鏈表，情輸入n：");</p><p>　　scanf("%d",&n); </p><p>　　printf("為L(zhǎng)1表輸入%d個(gè)數(shù)據(jù),并逆序插入：",n);</p><p>　　Creat_List(L1,n);</p><p>　　pri

99、ntf("L1表的n個(gè)數(shù)據(jù)如下：");</p><p>　　Print_List(L1);getlength(L1);break;</p><p><b>　　case 2:</b></p><p>　　Print_List(L1);</p><p>　　printf("請(qǐng)選擇要插入的位置和

100、插入值："); </p><p>　　scanf("%d%d",&i,&n);</p><p>　　Insert_List(L1,i,n);</p><p>　　printf("插入操作后的L1鏈表的元素為：\n");</p><p>　　Print_List(L1);getl

101、ength(L1);break;</p><p><b>　　case 3:</b></p><p>　　Print_List(L1);</p><p>　　printf("請(qǐng)選擇要?jiǎng)h除的位置："); </p><p>　　scanf("%d",&i);getchar();

102、 </p><p>　　Delete_List(L1,i,e);</p><p>　　printf("刪除操作后的L1鏈表的元素為：\n");</p><p>　　Print_List(L1);getlength(L1);break;</p><p><b>　　case 4:</b></p&g

103、t;<p>　　printf("建立一個(gè)數(shù)據(jù)個(gè)數(shù)為m的鏈表，情輸入m：");</p><p>　　scanf("%d",&m); </p><p>　　printf("為L(zhǎng)2表輸入%d個(gè)數(shù)據(jù),并逆序插入：",m);</p><p>　　Creat_List(L2,m);</p&g

104、t;<p>　　printf("L2表的n個(gè)數(shù)據(jù)如下："); Print_List(L2);</p><p>　　printf("兩鏈表的并集為：\n");</p><p>　　Merge_List(L1,L2,L3);</p><p>　　Print_List(L3); getlength(L3);break;

105、</p><p><b>　　case 5:</b></p><p><b>　　do{</b></p><p>　　printf("\n請(qǐng)輸入要查找的鏈表，L1或L2或L3:\n");</p><p>　　scanf("%d",&choise);&l

106、t;/p><p>　　switch(choise){</p><p><b>　　case 1:</b></p><p>　　printf("按位置查找請(qǐng)輸入要查找的位置：");</p><p>　　scanf("%d",&y);</p><p>　　G

107、etElem_L(L1,y,e);break;</p><p><b>　　case 2:</b></p><p>　　printf("按位置查找請(qǐng)輸入要查找的位置：");</p><p>　　scanf("%d",&y);</p><p>　　GetElem_L(L2,y

108、,e);break;</p><p><b>　　case 3:</b></p><p>　　printf("按位置查找請(qǐng)輸入要查找的位置：");</p><p>　　scanf("%d",&y);</p><p>　　GetElem_L(L3,y,e);break;<

109、;/p><p><b>　　default :</b></p><p>　　printf("\n輸入錯(cuò)誤，請(qǐng)重新輸入?。n");break;</p><p><b>　　}</b></p><p>　　} while(choise!=0);</p><p>

110、<b>　　case 6:</b></p><p><b>　　while(1){</b></p><p>　　printf("\n請(qǐng)輸入要查找的鏈表，L1或L2或L3:\n");</p><p>　　scanf("%d",&choise);</p><p

111、>　　if(choise==0) break;</p><p>　　switch(choise){</p><p><b>　　case 1:</b></p><p>　　printf("按位置查找請(qǐng)輸入要查找的元素：");</p><p>　　scanf("%d",&

112、;w);</p><p>　　search(L1,w);break;</p><p><b>　　case 2:</b></p><p>　　printf("按位置查找請(qǐng)輸入要查找的元素：");</p><p>　　scanf("%d",&w);</p>&l

113、t;p>　　search(L1,w);break;</p><p><b>　　case 3:</b></p><p>　　printf("按位置查找請(qǐng)輸入要查找的元素：");</p><p>　　scanf("%d",&w);</p><p>　　search(L1

114、,w);break;</p><p><b>　　default :</b></p><p>　　printf("\n輸入錯(cuò)誤，請(qǐng)重新輸入！！\n");break;</p><p><b>　　} </b></p><p><b>　　}</b></p

115、><p>　　default: printf("\n輸入錯(cuò)誤，請(qǐng)重新輸入??！\n");break;</p><p><b>　　}</b></p><p><b>　　} }</b></p><p>　　以下是第二大模塊中所調(diào)用到的算法：</p><p>　　

116、Status Creat_List(Link_List &L,ElemType n){//逆序輸入n個(gè)元素的值，建立表頭結(jié)點(diǎn)的單戀線性表L。</p><p>　　L = (Link_List)malloc(sizeof(LNode));</p><p>　　L->next = NULL;Link_List p;//先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表</p><p&

117、gt;　　for(int i=n;i>0;i--){</p><p>　　p = (Link_List)malloc(sizeof(LNode));//生成新結(jié)點(diǎn)</p><p>　　scanf("%d",&p->data);//輸入元素值</p><p>　　p->next=L->next;L->next=

118、p;//插入到表頭</p><p><b>　　}</b></p><p><b>　　return 1;</b></p><p><b>　　}//鏈表的初始化</b></p><p>　　鏈表的初始化算法，采用的是非隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，首先先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表，輸入鏈

119、表的長(zhǎng)度，逐個(gè)插入元素值，邊插入邊生成新的結(jié)點(diǎn)，采用的是逆序插入，即每一個(gè)剛插入的元素都是插入到表頭</p><p>　　Status Insert_List(Link_List &L,int i,ElemType e){//在帶頭結(jié)點(diǎn)的單戀線性表L中第i個(gè)位置之前插入元素e</p><p>　　Link_List p=L;int j=0;</p><p>

120、　　while(p&&j<i-1){</p><p>　　p=p->next;++j;</p><p>　　} //尋找第i-1個(gè)結(jié)點(diǎn)</p><p>　　if(!p||j>i-1) return ERROR;//i小于1或大于表長(zhǎng)+1</p><p>　　

121、Link_List s = (Link_List)malloc(sizeof(LNode));//生成新結(jié)點(diǎn)</p><p>　　s->data=e;s->next=p->next;p->next=s;//插入L中</p><p><b>　　return 1;</b></p><p><b>　　}//鏈表的

122、插入</b></p><p>　　首先遍歷鏈表，找到要插入位置的前一個(gè)位置，然后生成新結(jié)點(diǎn)，插入帶插入的元素。</p><p>　　Status Delete_List(Link_List &L,int i,ElemType &e){//在帶頭結(jié)點(diǎn)的單戀 線性表L中，刪除第i個(gè)元素，并由e返回其值</p><p>　　Link_List

123、p=L ;</p><p><b>　　int j=0;</b></p><p>　　while(p->next&&j<i-1){</p><p>　　p=p->next;j++;</p><p>　　}//尋找第i個(gè)結(jié)點(diǎn)，并令p指向其前趨</p><p>　　i

124、f(!(p->next)||j>i-1) return ERROR;//刪除位置不合理</p><p>　　Link_List q = p->next;p->next=q->next;//刪除并釋放結(jié)點(diǎn)</p><p>　　e = q->data;</p><p><b>　　free(q);</b><

125、;/p><p><b>　　return 1;</b></p><p>　　}//鏈表的刪除算法</p><p>　　將鏈表的頭結(jié)點(diǎn)賦給p，由p開始查找要?jiǎng)h除的結(jié)點(diǎn)，如果沒(méi)有該結(jié)點(diǎn)，返回ERROR，找到后直接刪除，將其值用e返回，釋放該節(jié)點(diǎn)的內(nèi)存空間</p><p>　　Status Merge_List(Link_List

126、 La,Link_List Lb,Link_List &Lc){</p><p>　　//已知單鏈線性表La和Lb的元素按值非遞減排列</p><p>　　//歸并La和Lb得到新的單鏈線性表Lc，Lc的元素也按值非遞減排列</p><p>　　Link_List pa = La->next;</p><p>　　Link_Li

127、st pb = Lb->next;</p><p>　　Link_List pc;</p><p>　　Lc = pc = La; //用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn)</p><p>　　while(pa&&pb){</p><p>　　if(pa->data<=pb->data){</p>

128、<p>　　pc->next=pa;pc=pa;pa=pa->next;</p><p><b>　　}</b></p><p>　　else {pc->next=pb;pc=pb;pb=pb->next;}</p><p><b>　　}</b></p><p&g

129、t;　　pc->next=pa?pa:pb;//插入剩余段</p><p>　　free(Lb); //釋放Lb的頭結(jié)點(diǎn)</p><p><b>　　return 1;</b></p><p>　　}//有序鏈表的合并</p><p>　　分別給已有的兩個(gè)鏈表la和lb的頭結(jié)點(diǎn)賦指針，另建立一個(gè)新的