

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
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è)新的
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--- 數(shù)據(jù)結(jié)構(gòu)各章算法的演示系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--排序算法演示系統(tǒng)
- 大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)排序算法演示系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu)算法演示系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用(算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì))
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--幾種排序算法的演示
- 大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)排序算法演示系統(tǒng)58165
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)----huffman編碼
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---幾種排序算法的演示
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--內(nèi)部排序演示
- 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---prim算法
- 算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--排序算法
- 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)和演示
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
評(píng)論
0/150
提交評(píng)論