數(shù)據(jù)結構演示系統(tǒng)1與3的介紹

1、數(shù)據(jù)結構課程設計報告數(shù)據(jù)結構（C語言版）課程設計題 目 數(shù)據(jù)結構演示系統(tǒng)1和3學生學 號指導教師學 院信息科學與工程學院專業(yè)班級計算機類完成時間七月czlzdjsohu.目錄第一章項目概述31.1 問題的要求分析與描述 31.2 問題的要求和限制3第二章概要設計4第三章詳細設3.1 系統(tǒng)程序的組成框圖.83.2 程序的流程圖 113.3 算法的源程序15第四章調試分析244.1 調試方法.244.2 算法時間復雜度25第五章測試結果265.1 正確的輸入與輸出.265.2 錯誤的輸入與輸出32第六章課程設計總結6.1個人的體會和感想.41附錄A:演示系統(tǒng)1源代碼有詳細注釋.43附錄B:演示系統(tǒng)

2、2源代碼.60參考文.82第一章項目概述1.1 問題的描述與分析本次課程設計，我完成了兩個題目，數(shù)據(jù)結構演示系統(tǒng)1、數(shù)據(jù)結構演示系統(tǒng)2。 數(shù)據(jù)結構演示系統(tǒng)1主要有兩種數(shù)據(jù)的存儲結構要實現(xiàn)，順序和鏈式，每種存儲結構都 要實現(xiàn)至少四種算法插入、刪除、查詢、合并。對于申還要實現(xiàn)模式匹配，使用KMP 的快速算法，減小時間復雜度。1、順序表的插入、刪除和合并等基本操作。2、利用 插入運算建立鏈表；實現(xiàn)鏈表的查找、刪除、計數(shù)、輸出等功能以及有序鏈表的合并。 3、串的模式匹配（包括求next和nextval的值）。數(shù)據(jù)結構演示系統(tǒng)2涉及了數(shù)據(jù)結構常用的三種存儲結構，順序、鏈式、散列， 算法主要是查找和排序。

3、1、實現(xiàn)靜態(tài)查找（包括順序查找、折半查找和插入查找）和 動態(tài)查找（包括二叉排序樹和二叉平衡樹）。2、根據(jù)輸入的數(shù)據(jù)實現(xiàn)下列部排序： 直接插入排序、折半插入排序、表插入排序和希爾排序；快速排序；簡單選擇排序 和堆排序；歸并排序；鏈式基數(shù)排序。1.2 問題的要求和限制1.2.1 我做的界面以用戶為主，還兼容了容錯能力。首先就是菜單的選擇均有容錯能 力。整形數(shù)字的圍是-3276832767,要求用戶輸入顯示在用戶界面上的整形數(shù)字（1、2、 3、4、），當用戶輸入不正確的選項時，會自動提示輸入錯誤，并返回原菜單要求用戶從 新輸入。其次，每一個子菜單同樣有相同的容錯能力，對于某些子系統(tǒng)，用戶必須先建立線

4、 性表才能進行操作，若不先建立線性表，程序同樣會回到主菜單，并提示用戶建立線性表。1.2.2 由于用戶能輸入任意個數(shù)字進行演示，并且長度由用戶規(guī)定。系統(tǒng)規(guī)定用戶輸入 的長度應該在1100以。長度小于1就沒有意義了，但也不能太大，輸入長度太大，用 戶會沒有時間去輸入線性表的元素。在輸入數(shù)字時，理論上是表的長度不能小于1。如果小 于1,則會提示輸入錯誤，菜單自動返回。此外，在進行某些操作，如插入刪除時，用戶能 在任意位置插入且能在任意位置刪除，不過位置必須在線性表的圍之。若超過線性表的現(xiàn)有 長度，那么同樣會報錯。1.2.3 在用戶界面（DOS界面），用戶每執(zhí)行完一次操作，都會有相應的提示。若用 戶

5、建立了線性表，則會顯示建立成功。若用戶進行查找，都會提示查找成功與否。輸出地形 式是以用戶存入線性表的數(shù)字為準，一般都是整形。輸入其它形式的數(shù)字，會自動轉化為整 形。在串的模式匹配中，模式串和主串的長度輸入是整形，規(guī)定用戶必須輸入1100的數(shù) 字，否則會提示錯誤，要求從新輸入。而串的值是字符型。必須輸入字符，才能得到正確的 結果c1.2.4 數(shù)據(jù)結構演示系統(tǒng)1主要有四個模塊，一個主模塊，三個子模塊。主模塊調用 三個函數(shù)，SqListfun（）,LinkListfun（）,Index_SS）,分別指向三個不同功能的子模塊。 SqListfunO實現(xiàn)上述順序線性表的算法，LinkListfunO實

6、現(xiàn)上述連是線性表的算法，最后 一個Index_SS（）實現(xiàn)上述串的模式匹配算法。每一個模塊的調用以及返回都是通過用戶選 擇菜單來實現(xiàn)的。這些模塊能夠演示順序表建立、插入、刪除、查找、無序合并和有序合并, 鏈表的建立、插入、刪除、查找有序合并，用KMP算法實現(xiàn)串的模式匹配，給用戶看每一 次匹配失敗的地方，和字串的next和nextval值。正確輸入以及出入結果：正確的菜單選擇是界面上面的數(shù)字，正確的大小圍是1到100 的長度建立，正確的插入圍是線性表的長度圍，正確的字符串長度也是1到100,正確的 模式匹配應輸入字符。有了正確的輸入，系統(tǒng)會按要求，顯示正常的結果，如表中的元素是 什么，表插入成功

7、后表的元素也會增加，刪除成功會顯示刪除的是哪個元素哪個位置。錯誤的輸入會導致錯誤的輸出，輸入不在菜單圍的數(shù)字系統(tǒng)會自動提示，接著返回原菜 單。輸入超過線性表長度圍的位置，系統(tǒng)不會進行插入或者刪除，并自動返回原菜單。在有 序合并的共能當中，沒有按遞增序列輸入數(shù)字，合并后的鏈表也不會是有序的。第二章概要設計2.1 數(shù)據(jù)類型定義數(shù)據(jù)機構演示系統(tǒng)1定義了五種存儲結構，typedef int Status;是定義函數(shù)的返回值 類型，也可以定義數(shù)據(jù)的類型，在數(shù)據(jù)有變動時而算法不變時，只需要改變其中的“int” 就可以。SqList是順序表的數(shù)據(jù)類型，其中包含三個成員，一個是ElemType的指針變量, 第

8、二個是表中元素的個數(shù)，第三個是表的當前容量。第三個是上面提到的ElemType,主要 表示各種元素的數(shù)據(jù)類型。第四個是typedef struct LNodeO *LinkList,這個是鏈表的元素 類型，每次用鏈表都用這個來定義新結點。最后是typedef unsigned char SStringMAXSTRLEN +1;這個是字符串數(shù)組，在模式匹配中用到。ElemTypetypedef int ElemType;typedef structElemType *elem;int length;int listsize;SqList;typedef unsigned char SString

9、MAXSTRLEN +1;typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;順序表的各種抽象數(shù)據(jù)類型的定義如下ADT list_Sq數(shù)據(jù)對象：D=ai| ai ElemSet,i=l,2,-,n,n=0數(shù)據(jù)關系：Rl=|ai-l,aiD,i=2,n基本操作：Status InitList_Sq(SqList &L)操作結果：構造一個空的線性順序表L。Status GetElem(SqList L,ElemType i,ElemType &e)初始條件：線性表L巳存在，l=i=Listlength(L)。操作

10、結果：把線性表L中的第i個元素傳遞給e。Status ListInsert_Sq(SqList &L,int i,ElemType e)初始條件：線性表L巳存在，l=i=Listlength(L)+lo操作結果：在順序表L中第i個位置之前插入新的元素e, L的長度加1。Status ListDelete_Sq(SqList &L,int i,ElemType &e)初始條件：線性順序表L巳存在且非空，i的合法值為l=i=L.length。操作結果：在順序線性表L中刪除第i個元素，并用e返回其值，L的長度減1。Status LocateElem_Sq(SqList L,ElemType e,St

11、atus (*compare) (ElemType, ElemType)初始條件：線性表L巳存在，l=i=0數(shù)據(jù)關系：Rl=|ai-l,aiD,i=2,n基本操作：void CreateList_L(LinkList &L,int n)操作結果：順位序輸入n個元素的值，建立帶頭結點的單鏈表L。void print_L(LinkList head)操作結果：在界面上打印head結點。初始條件：單鏈線性表L存在。操作結果：返回單鏈線性表的長度。Status ListInsert_L(LinkList &L,int i,ElemType e)初始條件：單鏈線性表L存在且不為空，l=i=Listlen

12、gth(L)+lo操作結果：在帶頭結點的單鏈表L中第i個位置之前插入元素eoStatus ListDelete_L(LinlList &L, int i, ElemType &e)初始條件：單鏈線性表L存在,，i的合法值為l=i=L.length。在帶頭結點的單鏈線性表L中，刪除第i個元素，并由e返回其值。int LocateElem_L(LinkList L,ElemType e)初始條件：單鏈線性表L巳存在且非空。操作結果：在單鏈表L中從頭開始找第1個值域與e相等的節(jié)點，若存在這樣的 節(jié)點，則返回位直，并打印該結點的值。Status GetElem_L(LinkList L,int i,E

13、lemType &e)初始條件：L為帶頭結點的單鏈表的頭指針，l=i=0數(shù)據(jù)關系：Rl=|ai-1 ,aiD,i=2，,n基本操作：void get_next(SString T,int next。)操作結果：求模式串T的next函數(shù)值并存入數(shù)組next.。void get_nextval(SString T,int nextval。)初始條件：T非空。操作結果：求模式串T的next函數(shù)修正值并存入數(shù)組nextval。int Index_IMP(SString S,SString T,int &pos, int nextvalj)初始條件：T 非空，l=pos=StrLength(S)。操作結

14、果：利用模式串T的next函數(shù)求T在主串中第pos個字符之后 的位置的KMP算法。I f2.2 各個函數(shù)的調用關系各個函數(shù)的調用關系：main。調用 SqListfunO, LinlListfun(), Index_SS()；oSqListfun。調用 InitL運t_Sq(&L), ListInsert_Sq(SqList &L,int i,ElemType e), ListDelete_Sq(SqList &L,int i,ElemType &e), print_Sq(SqList L), GetElem(SqList L,ElemType i,ElemType &e), unionSq(

15、SqList &La,SqList Lb)和 MergeList(SqList La,SqList Lb,SqList &Lc)o其中,unionSq(SqList &La,SqList Lb)調用 LocateElem_Sq(SqList L,ElemType e,Status (*compare)(ElemType, ElemType), 和 compare(ElemType al, ElemType a2)oLinkListfimO調用 CreateList_L(LinkList &L,int n), ListInsert_L(LinkList &L,int i,ElemType e),

16、 ListDelete_L(LinlList &L, int i, ElemType &e),int ListLength_L(LinkList L) , LocateElem_L(LinkList L,ElemType e), GetElem_L(LinkL運t L,int i,ElemType &e), MergeList_L(LinkList &La,LinliList &Lb,LinkList &Lc)和 print_L(LinkList head)。而 Index_SS()調用了 get_next(SString T,int next) , get_nextxal(SString T

17、,int nextval), Index_KMP(SString S,SString T,int &pos, int nextval)o第三章詳細設計3.1系統(tǒng)程序的組成框圖主函數(shù)對各個函數(shù)的調用關系圖。歡迎界面0：退出系統(tǒng)；1:順序表的運算;2：鏈表的運算；3：串的模式匹配SqListfun ()對各個函數(shù)的調用1:用戶輸 入人一個 數(shù)字，建立 一個順序 表。2：用戶輸入 要插入的位 置和數(shù)字， 把數(shù)字插入 到之前建立 的線性表中3：用戶愉入要刪除的位置刪除元素4：用戶輸入 要查找的元 素位置，終 端顯示元 素。5：用戶要再 建立一個線 性表B,系 統(tǒng)吧表B合 并到表A 中。6.用戶重新 建

18、立兩升序 的順序表， 合并它們， 且合并后有 序。Oo：返回上 一層，就是 放回到主函 數(shù)。Main()LinkListfun()鏈表的運算1：鏈表的建立2鏈表的插入;3: 鏈表的查找;4:鏈表的刪除;5:鏈 表的計數(shù):6:鏈表的輸出;7:有序 鏈表的合并;0：返回上一層；1：用戶輸 入人一連 串數(shù)字，建 立一個線 性鏈表。2：用戶輸入 要插入的位 置和數(shù)字， 把數(shù)字插入 到之前建立 的鏈表中3：用戶輸 入要刪除 的位置4：用戶輸 入要查找 的元素位 置,終端顯 不兀素。5 .把鏈表 中元素的 個數(shù)以整 數(shù)的形式 輸出。6 .系統(tǒng)把 鏈表中的 數(shù)字全部 輸出到界 面上。7 .用戶重 新建立兩

19、升序的順 序表，合并 它們，且合 并后有序0.返回到 主菜單。L按數(shù)字 的值來查 詢。3：按數(shù)字 的位置來 查詢。Index_SS()錯誤的輸入， 會提示用戶并 自動返回。模式匹配0：返回；求next的值;2:求 nextval 的值;3:進行模式匹配；-JL0.返回主界而。直 接回到主菜單。3.2 程序的流程圖我設計的程序，主函數(shù)的流程圖如下:結束順序表的運算choice=0力；真choice=2Q假 choice=3 choice=2順序表的7 j 建立真順序表的插入/版序表的查找1 1 ,假choice=47,真假Choi e=5X._ Choice=6/順序表的刪/順序表的無序匍f順序

20、表的有J拾并鋅表的運算choice=0串的模式匹配choice=0返回主 菜單3.3 算法實現(xiàn)的原程序typedef unsigned char SStringMAXSTRLEN +1；/字符串的數(shù)據(jù)類型/ typedef int Status;typedef int ElemType;typedef structElemType *elem;int length;int listsize;SqList;/*順序表的數(shù)據(jù)類型/typedef struct LNodeElemType data;struct LNode *next;LNodeJLinkList;/單鏈表的數(shù)據(jù)類型/每一個抽象數(shù)據(jù)

21、結構對應的算法如下void print_Sq(SqList L)打印順序表的全部元素。int i;int aMaxSize;for(i-0;iL.length;i+)從第o個元素開始，一直到LJength輸出L的值 ai-L.elemi;printf(,%4dM,ai);printf(,nt,)；/print.Sq void print.Sq(SqList L)打印原序表的全部元素。int i;int aMaxSize;for(i-0;iL.length;i+)從第0個元素開始，一直到L.length輸出L的值ai-L.elemi;printf(r,%4dH,ai); printfrnM);/

22、print_Sqvoid MergeList(SqList La,SqList Lb,SqList &Lc)/巳知線性表La和Lb中的數(shù)據(jù)元素按值非遞減排列歸并La和Lb得到新的線性表Lc,Lc的數(shù)據(jù)元素也按值非遞減持列。int ai,bj,i,j,k,Lclen,Lb.len;InitList_Sq(Lc);H-l；k-0;La_len,La. length;Lb_len-Lb .length;卬地6(卜4加口)&。-口5上嘲當其中任意一個表沒有選擇充的時候GetElem(La,i,ai)；調用GetElem()函數(shù)，獲取La的值，并賦給aiGetElem(Lb,j,bj); il(ai-b

23、j)把其中小的插入到Lc中ListInsert_Sq(Lc,+k,ai);/*flListInsert_Sq 把小的值插入到中*/+i；/*i的值加1,指向下一個元素*/ elseListins ert_Sq(Lc,+k,b j);+j;/else /while while(i-Laen)/*把La中剩余的元素賦給Lc*/GetElem(La,i+,ai);ListInsert_Sq(Lc,+k,ai);while(j-Lb_len)/*把Lb中剩余的元素賦給Lc*/GetElem(Lb,j+,bj);ListInsert_Sq(Lc,+k,bj);/while/MergeListStatus

24、 GetElem(SqList L,ElemType i,ElemType &e)/把線性表L中的第i個元素傳遞給eif(iL.length) 1的固有誤，要重新輸入printf(WtWn 聽return 0;e-L.elemM; /吧線性表的第i個元素取出來。 return 1; /GetElemvoid unionSq(SqList &La,SqList Lb)將所有在線性表Lb中但不在La中的數(shù)據(jù)元素插入到La中ElemType LaJeri,LbJen,i;ElemType e;LaenLaength; Lben-Lb .length; for(i-l ;i-Lb_len;i+)Get

25、Elem(Lb,i,e);謂用GetElem。函數(shù)，獲取Lb中的第i個值，并賦給e if(ILocateElem_Sq(La,e, compare)/*調用 LocateElem.Sq 函數(shù),如果在 La 中找不到與 e相等的函數(shù)， 就把e插入到La中，否則不進行插入*/ ListInsert_Sq(La,+Laen,e); ) /unionSqStatus LfOcateElem_Sq(SqList L, ElemType e, Status (*compare) (ElemType, ElemType)在順序線性表中查找第一個與e值滿足compare關系的位序若找到則返回其在L中的位序，否

26、者返回0ElemType i-1;ElemType *p-L.elem; 把L的背元素的地址給p*/while(iv-L.length&l(*compare)(*p+,e) /*找到與e相等的元素，并且i在合法的 值以/ +i； if(i-L.length)/i的值比元素個數(shù)少，是正常的查找*/ return i; else return 0;查找不成功，返回0./LocateElem_SqStatus ListDelete_Sq(SqList &L,int i,ElemType &e) 在屆序線性表L中刪除第i個元素，并用e返回其值 /i 的合法值為 1T-L.length。 ElemTyp

27、e *p,*q;il(iL.length) return ERROR;/*輸入i的位置不合法，函數(shù)退出，返回 0*/p-&(L.elemM); 把線性表的第i個值的地址給P e-*p；把的p所指元素值賦給eq-L. elem+L.length-1; /*q 指向最后一個元素*/ for(+p;p-q;+p)*(P-l)-*P；/*從i開始，把所有的元素都向前移動*/-L.length;/*順序表的長度減少1*/return OK;/ListDelete.SqStatus compare(ElemType al, ElemType a2)如果al和a2相答，則返回1,否者返回0if(al=a2)

28、return 1;elsereturn 0;/listDelete_SqStatus ListInsert_Sq(SqList &L,int i,ElemType e)/在順序表L中第i個位宣之前插入新的元素e/i 的合法值為 l-iL.length+l) /i 值不合法print!(國錯誤而新輸入城)；return ERROR;if(L.length=L.listsize)/當前空間已滿，增加分配newbase- (ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(EleniType);if(lnewbase)print!(

29、空間巳經(jīng)滿了，無法獲得新空間rT);exit(OVERFLOW)；)存儲分配失敗L. elem-newbase;L.listsize+LISTINCREMENT; 容工相應地增加)q-&(L.elemi-l); 口為插入位篁 for(p-&(L.elemL.length-l);p-q;-p)(p+l)-*p; 插入位置及之后的元素右移*q-e;+L.length; 郎增 1return OK;/ListInsert_SqStatus InitList.Sq(SqList &L)/構造一個空的線性表L. elem-(ElemType *)malloc(LIST_INIT_SIZE*sizeof(

30、ElemType);if(IL.elem) printf(分配不了地址方exit(OVERFLOW);L.length-0;初始化沒有元素，順序表的長度為0L.Ustsize-LIST_INIT_SIZE; 存儲空間初始化的空間 return OK;/ /InitList_Sqint Index_KMP(SString S,SString T,int &pos, int nextval) 利用模式串T的next函數(shù)求T在主串中第pos個字符之后 的位直的KMP算法。其中，T非空，13pos-StrLength(S) int i-pos; int whne(i=SO&jTO) prinH果后匹配

31、成功，在第4d個位亶n?-TOD； return i-TO; 返回成功匹配的位置 elseprintf (最后匹配不成功八n);return 0; /Index_KMPvoid get_nextval(SString T,int nextvalQ)求模式串T的next函數(shù)修正值并存入數(shù)組nextval int nextvall-O;while(iT0)ifO-01 |Ti-TD) /*1 的 nextval 是 0*/+i；/*i 和 j 各加 1*/+j；nextvali-j;/*字符申不相等，就上一次的j賦給nextval*/else nextvali-nextvalj; /*相等的話就把

32、前一個nextval的值賦給 這個/ /if else j-nextvalj;/*若不相等的話，就可以吧nextval賦給j*/ /whileget_nextvalvoid get_next(SString T,int next)求模式串T的next函數(shù)值并存入數(shù)組next.nextl-O; /*1 的 next 是 0*/j=0;while(inext;/*后面的就指向La*/pb-Lb-next;Lc-pc-La;while(pa&pb)if(pa-datadata)pc-next-pa; /*pa指向的節(jié)點值小，就把該連到Lc中*/pc-pa;/*pc指最新連人的節(jié)點*/pa-pa-ne

33、xt; /*pa 指向下一個節(jié)點*/elsepc-next-pb;/*pb指向的節(jié)點值小，就把該連到Lc中/ pc-pb;/*pc指新連入的節(jié)點*/pb-pb-next;/*pb 指向下一個節(jié)點/)pc-next-pa?pa:pb; /指向不為空的那個結點/free(Lb)；/*釋放Lb的空間*/MergeList_void print_L(LinkList head)LinkList p-head-next;wbdle(p!-NULL) /*p 不為空*/printf(0%5d,p-data);p-p-next;/p指向下一個結點*/) prmtf(n);/print_Lint ListLe

34、ngth_L(LinkList L) LinkList p-L;int i=0;while(p-nextlNULL)/*當 p 不為空/ i+；/有加1*/p-p-next;/while return (i);/ListLength_LStatus ListDelete_L(LinkList &L, int i, ElemType &e)/在帶頭結點的單鏈線性表L中，刪除第i個元素，并由e返回其值 LinkList q,p-L;int j-0;while(p-next&jvi-l)尋找第i個結點，并令p指向其前盟 p-p-next;/*p指向下一個節(jié)點*/+J;if(!(p-next) | j

35、i-l) /*i 的值小于 1 或者大于 L.length*/ print!(刪除位置不合理I iT);return ERROR;) q-p-next;p-next-q-next; 刪除第i個結點 e-q-data;把該節(jié)點的值賦給efree(q);/*釋放已刪結點的空間*/print!(刪除4 成功！ n*e); return OK;/ListDeleteStatus QetElem_L(LinkList L,int i,ElemType &e)L為帶頭結點的單鏈表的頭指針當?shù)趇個元素存在時，其值賦給e并返回OK,否者返回ERROR LNode *p;ElemType j;p-L-next;

36、j-l;while(p&jnext; +j;)if(!pIIji) i小于1或者大于表長printC第4d個元素不存在”,i);return ERROR;)e-p-data; /*找到地i個元素，并賦給e*/printf(%4d 元素為 4d”,i,e);return OK;/GetElem_Lint LocateElem_L(LinkList L,ElemType e)/*在單鏈表L中從頭開始找第1個值域與e相等的節(jié)點，若存在這樣的節(jié)點，則返回位1L并打印該結點的值*/LinkList p-L-next;int i-1;while(p!-NULL&ap-data!-e) /*p沒有指向表尾，

37、并且沒有找到元素e*/p-p-next;/*p指向下一個結點/i+;/whileif(p-NULL)找到表尾，沒有找到元素eprintfC這個數(shù)值不存在；return NULL;elseprintf(你所查詢的數(shù)d是第d個,e,i);return (i);)/ /LocateElem_LStatus ListInsert_L(LinkList &L,int i,ElemType e)在帶頭結點的單鏈表L中第i個位置之前插入元素eLinkList s,p-L;int j-0;while(p&jnext; /p指向下一個節(jié)點+j；)printfC第4d節(jié)點不存在p為空，或者i小于1或者大于表長加1

38、 return ERROR;)s.(LinkList)malloc(sizeof(LNode); 生成新的結點s-data-e;s-next-p-next; 插入L中，使s成為第i個結點p-next-s;printfC插入成功！ n);return OK;/ListInsert_Lvoid CreateList_L(LinkList &L,int n)順位序輸入n個元素的值，建立帶頭結點的單鏈表LLinkList s,r;int i;L- (LinkList)malloc(sizeof(LNode);/開辟一個新的空間r-L；if(nl)長度要大于等于1printf(長度有問題n);retur

39、n;for(i-l;idata);/給該節(jié)點賦值/r-next-s; /*把新的節(jié)點連接到表尾*/r-s;/什指向表尾/r-next-NULL;尾指針的next為空/ CreateList-Lint mainQsystem(Mcolor 1A; 選擇顏色的函數(shù)int choice;int lag-0;while用while和switch來控制菜單，三個子模塊和這個算法相同 system(CLS);清屏函數(shù)puts(HnM);puts(ttXtt歡迎使用數(shù)據(jù)結構演示系統(tǒng)t史puts(”ttXtt 順序表的運算tt聽puts(ttXtt 鏈表的運算 tt叱puts(ttXtt 串的模式匹配tt聽p

40、uts(=ttXtt 退出tt叱puts(tmtt請輸入你的選擇:tt叱putsettwttt 叱printfCtttt .scan! (M%d&choice);switch(int)choice)case 0: return 1;case 1: SqListfunQ； break; 順序表的運算 case 2: LinkListfunQ; break; 鏈表的運算 case 3: Index.SSO； break; 模式匹配 default: printf(輸入的序號不正確！請重新輸入n);system(HPAUSEw);break;/ /switch/while/main第四章調試分析4.

41、1 調試中的問題在寫第一個系統(tǒng)的過程中，發(fā)現(xiàn)要實現(xiàn)的功能很多，這樣寫起來，系統(tǒng)會很龐雜。我 用傳遞參數(shù)解決了這個問題。為了避免主菜但中有過多的程序。我把每一個子模塊都寫在一 個函數(shù)中，主菜單只要調用這些函數(shù)就可以了。這樣主菜單就能夠很簡短。其次，每一個子 菜單的功能是獨立的，又可以在于菜單中重新定義函數(shù)，實現(xiàn)各種功能。這樣修改起來會很 方便，并且符合結構化的程序設計。最開始遇到的問題是與傳遞參數(shù)有關的問題c當時我寫了很個子程序的算法，編譯結 果0個錯誤，。個警告。我就以為程序可以運行，可以一旦調用程序，電腦就報出存不 能為written或者存不能為read。我找不到解決的方法，因為沒有語法的錯

42、誤我把結構 也改為結構體指針，在把所有的調用重新改一遍，還是不行。沒辦法，這個超出我的能力圍 之外。我巳經(jīng)寫了那么多程序了，想要改變算法重新寫估計也不可能了。一方面，我暫時放 開題目1,就靜下心來寫第三個程序。另外一方面，我找到程序設計很熟練的人幫我改錯。 功夫不負有心人，他一下子就看到我的錯誤。要再每一個需要改變的形參前加一個“& ”， 不讓程序無法運行。這代表傳遞參數(shù)。我終于明白是怎么回事。馬上修改自己的程序，果然 全都能運行并的到正確的結果。在課程設計過程中，相互幫助非常重要。最開始我只會寫菜單，而不知道怎樣去實現(xiàn) 一個個算法。而我的一位同學把這些算法都寫過一遍，卻對程序設計不怎么熟練。

43、我們正好 互補，他給我指明了方向，如何實現(xiàn)這些算法。而我教了他如何把這些算法整合到一起形成 一個系統(tǒng)。此外，有些問題經(jīng)過討論才得出來。比如，在寫順序表和鏈表的操作時，就遇到一個 問題，用戶必須懸著菜單1建立順序表或者菜單，才能夠進行后面的操作。如果用戶沒喲 建立線性表就進行操作，系統(tǒng)不會報錯，但是程序會無法執(zhí)行。這樣，我就想出了要寫一個 先把程序，只有當這個菜單執(zhí)行后，其它的菜單才能夠開通。若用戶直接選擇后面的菜單， 就會提示用戶先建立。這個功能是我在設計系統(tǒng)前沒喲想到的。有了這個經(jīng)驗后，在串的模 式匹配的子模塊中，由于第三個菜單中KMP模式匹配算法用的是菜單二中的nextval,而 菜單二中

44、的nextval又是從菜單一中的字串中的到的。那么必須先執(zhí)行菜單1,在執(zhí)行菜單 2,最后執(zhí)行菜單三，才能的到正確的結果。用上述的方法，設置兩個LAG很快就能夠實 現(xiàn)這個功能了。在寫代碼的過程中，有時候會遇到一些莫名的錯誤，比如以前能夠的到的結果，現(xiàn)在 卻得不到了。有些程序明明沒有錯誤，卻得不到正確的結果。其實這都是在一些小的方面出 了問題。比如i,j看不清，兩個數(shù)組一下子忘記改變了，該加1的沒有加。在進行插入或者 刪除操作時，對i的長度的限定，是length+1,還是length,也都需要詳細的推敲。又是后 需要用某些變量做標記，卻忘記給該變量賦初值，導致出現(xiàn)-2566的數(shù)字。又是后指針和 地

45、址沒有分辨清楚，打印出的結果也會很奇怪。后來想要把界面做的美觀，就想到用一些特殊的符號來裝飾界面。我懸著了有花紋的 粗邊框?？上胍蛇@個符號整合成一個完整的矩形，還是要細細的琢唇。沒調試一下就上機 運行一次。方框做好了，又要保證字體在正中央，還得重新調試。在和同學的不斷交流中，我知道了怎么利用，清屏函數(shù)，暫停函數(shù)，還有顏色配置函 數(shù)來把我的界面變成彩色。并且沒執(zhí)行完一個工功能都會暫停，顯得更人性化。要做到很好的設計程序，還是要嚴格推敲，多編程，所實踐，多思考。4.2 算法的時間復雜度以下是各個菜單的時間復雜度的列表，以及如何改進。主菜main有幾個子菜單就有要比較幾次，時間復雜度為O(n)；同

46、樣三個子菜單的時間復雜度也都是0(n);由于便要用戶來選擇，儕要和每一個選項比 較，無法提高復雜度，可以設置指針，如果用戶輸入一個選項，就自動連接到該選項指定的 命令，時間K親度就可以變?yōu)?(1)了；InitList_Sq(&L),O (1),初始化，一次性分配空間ListInsert_Sq(SqList &L,int i,ElemType e), O (n),在插入的位宣之后的元素全部 都要向后移動ListDelete_Sq(SqList &L,int i,ElemType &e), O (n),在刪除的位宣之后的元素全 部都要向前移動print_Sq(SqList L), O (n),打印 n 個數(shù)字。GetElem(SqList L,ElemType i,ElemType &