數(shù)據(jù)結構課程設計---數(shù)據(jù)結構相關算法的演示系統(tǒng)

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：35 大小：575.50KB 人氣指數(shù)：12 舉報 版權申訴

數(shù)據(jù)結構課程設計---數(shù)據(jù)結構相關算法的演示系統(tǒng)_第1頁

已閱讀1頁，還剩34頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　課程設計實驗報告　　課程名稱：《數(shù)據(jù)結構課程設計》　　設計題目：數(shù)據(jù)結構相關算法的演示系統(tǒng)（1）　　院系：信息科學與工程學院　　目錄

2、　　需求分析………………………………… 3　　概要設計………………………………… 4　　詳細設計………………………………… 6　　調試分析………………………………… 21　　測試結果………………………………… 23　　課程設計總結

3、…………………………… 33　　參考文獻…………………………………34　　附錄………………………………………34　　一、需求分析：　　設計一個數(shù)據(jù)結構相關算法的演示系統(tǒng)，主要實現(xiàn)的功能如下：

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

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

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

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

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

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

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

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

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

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

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

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

16、模式串t在主串中的位置從第六個字符開始，匹配成功！　　選擇KMP算法匹配，輸入主串‘ababcabcacbab’，輸入模式串‘abcac’，KMP_lndex的結果為：比較次數(shù)為3，模式串t在主串s中的位置從第六個字符開始，匹配成功；修正后的KMP算法匹配后的結果是比較次數(shù)為6，模式串t在主串中的位置從第六個字符開始，匹配成功！　　求取next值，輸入模

17、式串，例‘abaabcac’，結果為：next[1] =0, next[2] =1, next[3] =1, next[4] =2, next[5] =2, next[6] =3, next[7] =1, next[8] =2.　　求取nextval值，輸入字符‘aaaab’，結果為nextval[1]=0, nextval[2]=0, nextval[3]=0, nextval[4]=0, n

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

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

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

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

22、，返回值 1　　（9）Status Delete_List(Link_List &L,int i,ElemType &e) //刪除鏈表第i個位置的元素，返回值 1　　（10）Status Merge_List(Link_List La,Link_List Lb,Link_List &Lc) //合并La與Lb兩個鏈表為Lc鏈表，

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

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

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

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

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

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

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

30、t;　　ElemType *elem; //存儲空間基址 　　int length; //當前長度　　int listsize; //當前分配的存儲容量&

31、lt;b>　　}SqList;　?。?）鏈表的存儲結構：　　typedef struct Lnode{　　ElemType data; //鏈表數(shù)據(jù)類型　　struct Lnode * next;

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

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

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

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

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

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

38、quot;\t☆==☆==☆==☆==☆==☆==☆==☆==☆==☆==☆==☆==☆==☆==☆\n");　　printf("\t☆\t\t\t\t\t\t\t☆\n");　　printf("\t||\t\t\t\t\t\t\t||\n");　　printf(

39、"\t☆\t\t§歡迎進入數(shù)據(jù)結構演示系統(tǒng)§\t\t☆\n");　　printf("\t||\t\t\t\t\t\t\t||\n");　　printf("\t☆\t\t\t\t\t\t\t☆\n");　　printf("\t

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

41、示\t\t\t||\n");　　printf("\t☆\t\t\t\t\t\t\t☆\n");　　printf("\t||\t\t\t\t\t\t\t||\n");　　printf("\t☆\t\t 3:串的相關操作演示\t\t\t☆\n");

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

43、t;　　printf("\t☆==☆==☆==☆==☆==☆==☆==☆==☆==☆==☆==☆==☆==☆==☆\n");　　int choose;　　printf("\t請選擇要實現(xiàn)的功能:");　　scanf("%d",&choose);&

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

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

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

47、gt;　?。?）第一大模塊的功能函數(shù)function_1(),里面包括順序表的操作界面和對順序表功能函數(shù)的調用，主要結構還是運用了switch，case語句來進行選擇，　　int function_1(){　　SqList La,Lb,Lc;　　int k=1,c=1,i,a,num;&l

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

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

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

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

52、ntf("\t\t\t ☆ 0:返回上級菜單\t ☆\n");　　int choose;　　printf("\n\t\t請選擇對順序表的操作:");　　scanf("%d",&choose);　　s

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

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

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

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

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

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

59、break; //順序表的插入　　case 3:　　printf("插入操作后的La順序表的元素為：\n");　　ListPrint_Sq(&La);　　printf("請選擇要刪除的位置：&qu

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

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

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

63、gt;　　if(num == 00) 　　break; 　　ListInsert_Sq(&Lb, c, num); 　　c++; 　　}

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

65、lt;/p>　　ListPrint_Sq(&Lc);printf("請選擇要刪除的位置："); 　　scanf("%d",&i);　　while(i-1>Lc.length-1){printf("\n輸入錯誤，請重新輸入\n"); scanf(&

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

67、p>　　case 0:return 1;　　default:　　printf("\n輸入錯誤，請重新輸入！！\n");break;　　}　　}</

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

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

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

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

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

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

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

75、length; //表長增1　　return 1;　　}//ListInsert_Sq　　順序表的插入算法，首先判斷插入位置，如果溢出返回ERROR，然后進行內存判斷，如果內存不足，則增加內存，找到插入位置，將插

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

77、istsize， 　　//則再為其分配增量為LISTINCREMENT大小的內存空間 　　return L->length = L->listsize; 　　}　　順序表內存的判斷，如果順序表的內存已滿，則可以增加順序

78、表的內存　　Status ListPrint_Sq(SqList *L) 　　{ 　　int i = 0; 　　ElemType num = 0; //用于取出每個數(shù)據(jù)項的值

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

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

81、 int i) 　　{ 　　int j; // i--; 　　//要刪除的元素下標不在長度范圍內 　　if(i<1 || i>L->length+1) 　　ret

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

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

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

85、{ 　　ElemType *pa = La.elem, *pb = Lb.elem, *pc; 　　ElemType *pa_last, *pb_last; //確定Lc線性表的長度為兩個線性表的長度之和 　　Lc->listsize = Lc->length = L

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

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

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

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

90、lt;/p>　　順序表的合并算法，首先定義一個表長度等一兩表長度之和的順序表，定義兩個指針分別指向兩個順序表的第一個元素，然后比較元素值的大小，將較小的一個插入到新表中，指針后移，直到其中一個順序表操作完，順序插入另外一個表的剩余段。　　} （3）第二大模塊是對鏈表的相關操作，同樣，在function_2（）中，有對鏈表的操作界面，還是運用switch，case語

91、句來進行函數(shù)的調用，　　int function_2(){　　Link_List L1,L2,L3;　　ElemType e;　　int n,y,w,i,m,choise;　　printf("\t\t ☆==

92、☆==☆==☆==☆==☆==☆==☆☆☆\n");　　printf("\t\t\t\t\t\t\t\n");　　printf("\t\t ☆§歡迎進入鏈表操作界面§ ☆\n");　　printf("\t\t\t\

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

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

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

96、\t\t\t\t\t\n");　　printf("\t\t\t ☆ 0:返回上級菜單\t ☆\n");　　int choose;　　printf("\n\t\t請選擇對鏈表的操作:");　　scanf("%

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

98、ntf("建立一個數(shù)據(jù)個數(shù)為n的鏈表，情輸入n：");　　scanf("%d",&n); 　　printf("為L1表輸入%d個數(shù)據(jù),并逆序插入：",n);　　Creat_List(L1,n);　　pri

99、ntf("L1表的n個數(shù)據(jù)如下：");　　Print_List(L1);getlength(L1);break;　　case 2:　　Print_List(L1);　　printf("請選擇要插入的位置和

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

101、ength(L1);break;　　case 3:　　Print_List(L1);　　printf("請選擇要刪除的位置："); 　　scanf("%d",&i);getchar();

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

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

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

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

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

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

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

109、;/p>　　default :　　printf("\n輸入錯誤，請重新輸入??！\n");break;　　}　　} while(choise!=0);

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

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

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

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

114、,w);break;　　default :　　printf("\n輸入錯誤，請重新輸入?。n");break;　　} 　　}</p

115、>　　default: printf("\n輸入錯誤，請重新輸入！！\n");break;　　}　　} }　　以下是第二大模塊中所調用到的算法：

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

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

118、p;//插入到表頭　　}　　return 1;　　}//鏈表的初始化　　鏈表的初始化算法，采用的是非隨機存取的存儲結構，首先先建立一個帶頭結點的單鏈表，輸入鏈

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

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

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

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

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

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

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

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

127、st pb = Lb->next;　　Link_List pc;　　Lc = pc = La; //用La的頭結點作為Lc的頭結點　　while(pa&&pb){　　if(pa->data<=pb->data){

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

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

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

溫馨提示

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

數(shù)據(jù)結構課程設計---數(shù)據(jù)結構相關算法的演示系統(tǒng)

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結構課程設計---數(shù)據(jù)結構相關算法的演示系統(tǒng)

文檔簡介

溫馨提示

最新文檔

評論

免費下載