數(shù)據(jù)結(jié)構(gòu)演示系統(tǒng)1與3介紹

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告數(shù)據(jù)結(jié)構(gòu)（c語言版）課程設(shè)計(jì)題 目 數(shù)數(shù)據(jù)結(jié)構(gòu)演示示系統(tǒng)1 和3 學(xué)生姓名 學(xué) 號(hào) 指導(dǎo)教師 學(xué) 院 信信息科學(xué)與工工程學(xué)院 專業(yè)班級(jí) 計(jì)算機(jī)機(jī)類 完成時(shí)間 七月 czlzdj目錄第一章 項(xiàng)目目概述31.1 問題題的要求分析析與描述.331.2 問題題的要求和限限制3第二章 概要設(shè)設(shè)計(jì) 4第三章 詳細(xì)細(xì)設(shè)計(jì).83.1系統(tǒng)程序序的組成框圖圖. 83.2 程序的的流程圖.113.3 算法的的源程序15第四章 調(diào)試試分析244.1 調(diào)試方方法.244.2 算法時(shí)時(shí)間復(fù)雜度225第五章 測(cè)試試結(jié)果265.1 正確的的輸入與輸出出.265.2 錯(cuò)誤的的輸入與輸出出332第六章 課程程

2、設(shè)計(jì)總結(jié)6.1 個(gè)人的的體會(huì)和感想想.41附錄A：演示系系統(tǒng)1源代碼碼有詳細(xì)注釋釋.43附錄B：演示系系統(tǒng)2源代碼碼.600參考文獻(xiàn).822項(xiàng)目概述 1.1 問題的描述述與分析 本次課程程設(shè)計(jì)，我完完成了兩個(gè)題題目，數(shù)據(jù)結(jié)結(jié)構(gòu)演示系統(tǒng)統(tǒng)1、數(shù)據(jù)結(jié)結(jié)構(gòu)演示系統(tǒng)統(tǒng)2。數(shù)據(jù)結(jié)構(gòu)演示系系統(tǒng)1主要有有兩種數(shù)據(jù)的的存儲(chǔ)結(jié)構(gòu)要要實(shí)現(xiàn)，順序序和鏈?zhǔn)?每每種存儲(chǔ)結(jié)構(gòu)構(gòu)都要實(shí)現(xiàn)至至少四種算法法插入、刪除除、查詢、合合并。對(duì)于串串還要實(shí)現(xiàn)模模式匹配，使使用KMP的的快速算法，減減小時(shí)間復(fù)雜雜度。1、順順序表的插入入、刪除和合合并等基本操操作。2、利利用插入運(yùn)算算建立鏈表；實(shí)現(xiàn)鏈表的的查找、刪除除、計(jì)數(shù)、輸輸出等功能

3、以以及有序鏈表表的合并。33、串的模式式匹配（包括括求nextt和nexttval的值值）。數(shù)據(jù)結(jié)構(gòu)演示系系統(tǒng)2 涉及及了數(shù)據(jù)結(jié)構(gòu)構(gòu)常用的三種種存儲(chǔ)結(jié)構(gòu)，順順序、鏈?zhǔn)?、散散列，算法主主要是查找和和排序?、實(shí)實(shí)現(xiàn)靜態(tài)查找找（包括順序序查找、折半半查找和插入入查找）和動(dòng)動(dòng)態(tài)查找（包包括二叉排序序樹和二叉平平衡樹）。22、根據(jù)輸入入的數(shù)據(jù)實(shí)現(xiàn)現(xiàn)下列內(nèi)部排排序：直接接插入排序、折折半插入排序序、表插入排排序和希爾排排序；快速速排序；簡簡單選擇排序序和堆排序；歸并排序序；鏈?zhǔn)交鶖?shù)排序。1.2 問題的的要求和限制制 1.2.1 我做的界面面以用戶為主主，還兼容了了容錯(cuò)能力。首首先就是菜單單的選擇均有有

4、容錯(cuò)能力。整整形數(shù)字的范范圍是-322768-327677，要求用戶戶輸入顯示在在用戶界面上上的整形數(shù)字字（1、2、33、4、），當(dāng)用戶戶輸入不正確確的選項(xiàng)時(shí)，會(huì)會(huì)自動(dòng)提示輸輸入錯(cuò)誤，并并返回原菜單單要求用戶從從新輸入。其其次，每一個(gè)個(gè)子菜單同樣樣有相同的容容錯(cuò)能力，對(duì)對(duì)于某些子系系統(tǒng)，用戶必必須先建立線線性表才能進(jìn)進(jìn)行操作，若若不先建立線線性表，程序序同樣會(huì)回到到主菜單，并并提示用戶建建立線性表。 1.22.2 由于于用戶能輸入入任意個(gè)數(shù)字字進(jìn)行演示，并并且長度由用用戶規(guī)定。系系統(tǒng)規(guī)定用戶戶輸入的長度度應(yīng)該在1100以內(nèi)內(nèi)。長度小于于1就沒有意意義了，但也也不能太大，輸輸入長度太大大，用戶會(huì)

5、沒沒有時(shí)間去輸輸入線性表的的元素。在輸輸入數(shù)字時(shí)，理理論上是表的的長度不能小小于1。如果果小于1，則則會(huì)提示輸入入錯(cuò)誤，菜單單自動(dòng)返回。此此外，在進(jìn)行行某些操作，如如插入刪除時(shí)時(shí)，用戶能在在任意位置插插入且能在任任意位置刪除除，不過位置置必須在線性性表的范圍之之內(nèi)。若超過過線性表的現(xiàn)現(xiàn)有長度，那那么同樣會(huì)報(bào)報(bào)錯(cuò)。 1.2.3 在在用戶界面（DDOS界面），用用戶每執(zhí)行完完一次操作，都都會(huì)有相應(yīng)的的提示。若用用戶建立了線線性表，則會(huì)會(huì)顯示建立成成功。若用戶戶進(jìn)行查找，都都會(huì)提示查找找成功與否。輸輸出地形式是是以用戶存入入線性表的數(shù)數(shù)字為準(zhǔn)，一一般都是整形形。輸入其它它形式的數(shù)字字，會(huì)自動(dòng)轉(zhuǎn)轉(zhuǎn)化為

6、整形。在在串的模式匹匹配中，模式式串和主串的的長度輸入是是整形，規(guī)定定用戶必須輸輸入1100的數(shù)數(shù)字，否則會(huì)會(huì)提示錯(cuò)誤，要要求從新輸入入。而串的值值是字符型。必必須輸入字符符，才能得到到正確的結(jié)果果。 1.2.4 數(shù)數(shù)據(jù)結(jié)構(gòu)演示示系統(tǒng)1主要要有四個(gè)模塊塊，一個(gè)主模模塊，三個(gè)子子模塊。主模模塊調(diào)用三個(gè)個(gè)函數(shù)，SqqListffun(),LinkLListfuun(),IIndex_SS(),分別指向三三個(gè)不同功能能的子模塊。SSqListtfun()實(shí)現(xiàn)上述順順序線性表的的算法，LiinkLisstfun()實(shí)現(xiàn)上述述連是線性表表的算法，最最后一個(gè)Inndex_SSS()實(shí)現(xiàn)現(xiàn)上述串的模模式匹配

7、算法法。每一個(gè)模模塊的調(diào)用以以及返回都是是通過用戶選選擇菜單來實(shí)實(shí)現(xiàn)的。這些些模塊能夠演演示順序表建建立、插入、刪刪除、查找、無無序合并和有有序合并，鏈鏈表的建立、插插入、刪除、查查找有序合并并，用KMPP算法實(shí)現(xiàn)串串的模式匹配配，給用戶看看每一次匹配配失敗的地方方，和字串的的 nextt和nexttval值。 正確輸輸入以及出入入結(jié)果：正確確的菜單選擇擇是界面上面面的數(shù)字，正正確的大小范范圍是1到1100的長度度建立，正確確的插入范圍圍是線性表的的長度范圍，正正確的字符串串長度也是11到100，正正確的模式匹匹配應(yīng)輸入字字符。有了正正確的輸入，系系統(tǒng)會(huì)按要求求，顯示正常常的結(jié)果，如如表中的元

8、素素是什么，表表插入成功后后表的元素也也會(huì)增加，刪刪除成功會(huì)顯顯示刪除的是是哪個(gè)元素哪哪個(gè)位置。 錯(cuò)誤的的輸入會(huì)導(dǎo)致致錯(cuò)誤的輸出出，輸入不在在菜單范圍內(nèi)內(nèi)的數(shù)字系統(tǒng)統(tǒng)會(huì)自動(dòng)提示示，接著返回回原菜單。輸輸入超過線性性表長度范圍圍的位置，系系統(tǒng)不會(huì)進(jìn)行行插入或者刪刪除，并自動(dòng)動(dòng)返回原菜單單。在有序合合并的共能當(dāng)當(dāng)中，沒有按按遞增序列輸輸入數(shù)字，合合并后的鏈表表也不會(huì)是有有序的。第二章 概要要設(shè)計(jì)2.1 數(shù)據(jù)類類型定義數(shù)據(jù)機(jī)構(gòu)演示系系統(tǒng)1定義了了五種存儲(chǔ)結(jié)結(jié)構(gòu)，typpedef int SStatuss;是定義函函數(shù)的返回值值類型，也可可以定義數(shù)據(jù)據(jù)的類型，在在數(shù)據(jù)有變動(dòng)動(dòng)時(shí)而算法不不變時(shí)，只需需要

9、改變其中中的“int”就可以。SSqListt是順序表的的數(shù)據(jù)類型，其其中包含三個(gè)個(gè)成員，一個(gè)個(gè)是ElemmType的的指針變量，第第二個(gè)是表中中元素的個(gè)數(shù)數(shù)，第三個(gè)是是表的當(dāng)前容容量。第三個(gè)個(gè)是上面提到到的ElemmType，主主要表示各種種元素的數(shù)據(jù)據(jù)類型。第四四個(gè)是typpedef strucct LNoode *LinkkList,這個(gè)是鏈表表的元素類型型，每次用鏈鏈表都用這個(gè)個(gè)來定義新結(jié)結(jié)點(diǎn)。最后是是typeddef unnsigneed chaar SSttringMAXSTTRLEN +1;這這個(gè)是字符串串?dāng)?shù)組，在模模式匹配中用用到。ElemTyppetypedeff int E

10、lemTType;typedeff struuct ElemTType *elem; int llengthh; int llistsiize; SqLiist;typedeff unsiigned char SStriingMAAXSTRLLEN +11;typedeff struuct LNNode ElemTType ddata; strruct LLNode *nextt;LNode,*LinkkList; 順序表的的各種抽象數(shù)數(shù)據(jù)類型的定定義如下 ADT llist_SSq數(shù)據(jù)對(duì)象：D=ai|aaiElemSSet,i=1,2,n,n=0數(shù)據(jù)關(guān)系：R11=|ai-1,aiD,i=22

11、,n基本操作： Stattus InnitLisst_Sq(SqLisst &L) 操作作結(jié)果：構(gòu)造造一個(gè)空的線線性順序表LL。 Stattus GeetElemm(SqLiist L,ElemTType ii,ElemmType &e) 初始條件：線性表L已已存在，1=i=LListleength(L)。操作結(jié)果：把線線性表L中的的第i個(gè)元素素傳遞給e。 Stattus LiistInssert_SSq(SqLList &L,intt i,EllemTyppe e) 初初始條件：線線性表L已存存在，1=i=Liistlenngth(LL)+1。 操操作結(jié)果：在在順序表L中中第i個(gè)位置置之前插

12、入新新的元素e，LL的長度加11。 Stattus LiistDellete_SSq(SqLList &L,intt i,EllemTyppe &e) 初初始條件：線線性順序表LL已存在且非非空，i的合合法值為1=i=LL.lenggth。 操作結(jié)果果：在順序線線性表L中刪刪除第i個(gè)元元素，并用ee返回其值，LL的長度減11。 Stattus LoocateEElem_SSq(SqLList LL,ElemmType e,Staatus (*comppare)(ElemTType, ElemTType) 初初始條件：線線性表L已存存在，1=i=0數(shù)據(jù)關(guān)系：R11=|ai-1,aiD,i=22,

13、n基本操作：void CrreateLList_LL(LinkkList &L,innt n)操作結(jié)果：順位位序輸入n個(gè)個(gè)元素的值，建建立帶頭結(jié)點(diǎn)點(diǎn)的單鏈表LL。void prrint_LL(LinkkList head)操作結(jié)果：在界界面上打印hhead結(jié)點(diǎn)點(diǎn)。 初始條件：單鏈線性表表L存在。 操作結(jié)果：返回單鏈線線性表的長度度。Status ListIInsertt_L(LiinkLisst &L,int ii,ElemmType e) 初始條件：單鏈線性表表L存在且不不為空，1=i=LListleength(L)+1。操作結(jié)果：在帶帶頭結(jié)點(diǎn)的單單鏈表L中第第i個(gè)位置之之前插入元素素e。S

14、tatus ListDDeletee_L(LiinkLisst &L, int i, EllemTyppe &e) 初始條件件：單鏈線性性表L存在，ii的合法值為為1=i=L.leength。 在帶頭結(jié)結(jié)點(diǎn)的單鏈線線性表L中，刪刪除第i個(gè)元元素，并由ee返回其值。int LoccateEllem_L(LinkLList LL,ElemmType e)初始條件：單鏈鏈線性表L已已存在且非空空。 操作結(jié)果果：在單鏈表表L中從頭開開始找第1個(gè)個(gè)值域與e相相等的節(jié)點(diǎn)，若若存在這樣的的節(jié)點(diǎn)，則返返回位置，并并打印該結(jié)點(diǎn)點(diǎn)的值。Status GetEllem_L(LinkLList LL,int i,El

15、eemTypee &e) 初始始條件： LL為帶頭結(jié)點(diǎn)點(diǎn)的單鏈表的的頭指針，11=i=0數(shù)據(jù)關(guān)系：R11=|ai-1,aiD,i=22,n基本操作：void geet_nexxt(SSttring T,intt nextt)操作結(jié)果：求模模式串T的nnext函數(shù)數(shù)值并存入數(shù)數(shù)組nextt.。 voiid gett_nexttval(SSStrinng T,iint neextvall) 初始條件：T非空。操作結(jié)果：求模模式串T的nnext函數(shù)數(shù)修正值并存存入數(shù)組neextvall。 intt Indeex_KMPP(SStrring SS,SStrring TT,int &pos, int n

16、extvval)初始條件：T非非空，1=pos=StrLeength(S)。操作結(jié)果：利用用模式串T的的next函函數(shù)求T在主主串中第poos個(gè)字符之之后的位置的KMPP算法。2.2 各個(gè)函函數(shù)的調(diào)用關(guān)關(guān)系各個(gè)函數(shù)的調(diào)用用關(guān)系：maain()調(diào)調(diào)用SqLiistfunn()，LinkLListfuun()，Indexx_SS();。SqListffun()調(diào)調(diào)用InittList_Sq(&LL), LiistInssert_SSq(SqLList &L,intt i,EllemTyppe e), ListtDelette_Sq(SqLisst &L,int ii,ElemmType &e),

17、prinnt_Sq(SqLisst L), GetEElem(SSqListt L,EllemTyppe i,EElemTyype &ee)，unionnSq(SqqList &La,SSqListt Lb)和和MergeeList(SqLisst La,SqLisst Lb,SqLisst &Lcc)。其中，unioonSq(SSqListt &La,SqLisst Lb)調(diào)用LocaateEleem_Sq(SqLisst L,EElemTyype e,Statuus (*ccomparre)(EllemTyppe, EllemTyppe)，和和compaare(EllemTyppe a1,

18、 ElemmType a2)。 LinkLiistfunn()調(diào)用CreaateLisst_L(LLinkLiist &LL,int n)，ListIInsertt_L(LiinkLisst &L,int ii,ElemmType e)，ListDDeletee_L(LiinkLisst &L, int i, EllemTyppe &e)，int LisstLenggth_L(LinkLList LL)，LocatteElemm_L(LiinkLisst L,EElemTyype e), GetEElem_LL(LinkkList L,intt i,EllemTyppe &e), Mergge

19、Listt_L(LiinkLisst &Laa,LinkkList &Lb,LLinkLiist &LLc)和printt_L(LiinkLisst heaad)。而Index_SS()調(diào)調(diào)用了gett_nextt(SStrring TT,int next)，get_nnextvaal(SSttring T,intt nexttval)，Indexx_KMP(SStriing S,SStriing T,int &pos, int nnextvaal)。 第三章 詳細(xì)細(xì)設(shè)計(jì)3.1系統(tǒng)程序序的組成框圖圖主函數(shù)對(duì)各個(gè)函函數(shù)的調(diào)用關(guān)關(guān)系圖。 歡迎界面0：退出系統(tǒng)； 1：順序表的運(yùn)算；2：鏈表的運(yùn)算；

20、3：串的模式匹配 歡迎界面0：退出系統(tǒng)； 1：順序表的運(yùn)算；2：鏈表的運(yùn)算； 3：串的模式匹配其它選項(xiàng)，輸入錯(cuò)誤返回主菜單。0：退出系統(tǒng)，安全退出。3：串的模式匹配又有四個(gè)選項(xiàng)。2：鏈表的運(yùn)算又有八個(gè)選項(xiàng)。1其它選項(xiàng)，輸入錯(cuò)誤返回主菜單。0：退出系統(tǒng)，安全退出。3：串的模式匹配又有四個(gè)選項(xiàng)。2：鏈表的運(yùn)算又有八個(gè)選項(xiàng)。1：SqListfun() 順序表的運(yùn)算又有七個(gè)選項(xiàng)。SqListffun()對(duì)對(duì)各個(gè)函數(shù)的的調(diào)用錯(cuò)誤輸入，系統(tǒng)自動(dòng)返回菜單 順序表的運(yùn)算0：返回上一層； 1：順序表的建立；2：順序表的插入；錯(cuò)誤輸入，系統(tǒng)自動(dòng)返回菜單 順序表的運(yùn)算0：返回上一層； 1：順序表的建立；2：順序表的

21、插入； 3：順序表的刪除；4：順序表的查找 ；5：順序表的無序合并；6：順序表的有序合并；0。：返回上一層，就是放回到主函數(shù)。Main()6用戶重新建立兩升序的順序表，合并它們，且合并后有序。5：用戶要再建立一個(gè)線性表B，系統(tǒng)吧表B合并到表A中。4：用戶輸入要查找的元素位置，終端顯示元素。3：用戶輸入要?jiǎng)h除的位置刪除元素2：用戶輸入要插入的位置和數(shù)字，把數(shù)字插入到之前建立的線性表中0。：返回上一層，就是放回到主函數(shù)。Main()6用戶重新建立兩升序的順序表，合并它們，且合并后有序。5：用戶要再建立一個(gè)線性表B，系統(tǒng)吧表B合并到表A中。4：用戶輸入要查找的元素位置，終端顯示元素。3：用戶輸入要?jiǎng)h

22、除的位置刪除元素2：用戶輸入要插入的位置和數(shù)字，把數(shù)字插入到之前建立的線性表中1： 用戶輸入人一個(gè)數(shù)字，建立一個(gè)順序表。錯(cuò)誤的輸入，會(huì)提示用戶并自動(dòng)返回。 鏈表的運(yùn)算1:錯(cuò)誤的輸入，會(huì)提示用戶并自動(dòng)返回。 鏈表的運(yùn)算1: 鏈表的建立;2: 鏈表的插入;3: 鏈表的查找;4: 鏈表的刪除;5: 鏈表的計(jì)數(shù):6: 鏈表的輸出;7: 有序鏈表的合并;0:返回上一層;LinkLisstfun()7用戶重新建立兩升序的順序表，合并它們，且合并后有序0.返回到主菜單。0。：返回上一層，就是放回到主函數(shù)。Main()6.系統(tǒng)把鏈表中的數(shù)字全部輸出到界面上。5把鏈表中元素的個(gè)數(shù)以整數(shù)的形式輸出。2：用戶輸入要

23、插入的位置和數(shù)字，把數(shù)字插入到之前建立的鏈表中17用戶重新建立兩升序的順序表，合并它們，且合并后有序0.返回到主菜單。0。：返回上一層，就是放回到主函數(shù)。Main()6.系統(tǒng)把鏈表中的數(shù)字全部輸出到界面上。5把鏈表中元素的個(gè)數(shù)以整數(shù)的形式輸出。2：用戶輸入要插入的位置和數(shù)字，把數(shù)字插入到之前建立的鏈表中1： 用戶輸入人一連串?dāng)?shù)字，建立一個(gè)線性鏈表。4：用戶輸入要查找的元素位置，終端顯示元素。3：用戶輸入要?jiǎng)h除的位置3：按數(shù)字的位置來查詢。1.按數(shù)字的值來查詢。3：按數(shù)字的位置來查詢。1.按數(shù)字的值來查詢。錯(cuò)誤的輸入，會(huì)提示用戶并自動(dòng)返回。模式匹配0：返回；1:求next的值;2: 求nextv

24、al的值;錯(cuò)誤的輸入，會(huì)提示用戶并自動(dòng)返回。模式匹配0：返回；1:求next的值;2: 求nextval的值;3:進(jìn)行模式匹配;0.返回主界面。直接回到主菜單。3.在已經(jīng)求出nextal的情況下，進(jìn)行模式匹配。顯示每一次匹配失敗的位置。1.用戶輸入字串，幾面輸出next 的值。2.選擇這一項(xiàng)，界面直接顯示nextval的值。0.返回主界面。直接回到主菜單。3.在已經(jīng)求出nextal的情況下，進(jìn)行模式匹配。顯示每一次匹配失敗的位置。1.用戶輸入字串，幾面輸出next 的值。2.選擇這一項(xiàng)，界面直接顯示nextval的值。3.2 程序序的流程圖我設(shè)計(jì)的程序，主主函數(shù)的流程程圖如下：開始開始 輸入

25、輸入 假choice=0choice=0 choice=0choice=0 假choice=1 choice=1 真 假choice=2真 choice=2順序表的運(yùn)算順序表的運(yùn)算 真 假choice=3 choice=3鏈表的運(yùn)算 真真 鏈表的運(yùn)算 真 choice=0choice=0串的模式匹配串的模式匹配 串的模式匹配串的模式匹配choice=0 choice=0 真 choice=0 choice=0 假 真真 真 結(jié)束結(jié)束順序表的運(yùn)算順序表的運(yùn)算 輸入 輸入 假choice=0 choice=0 choice=1 假choice=1 choice=3 choice=3choice=2

26、 真 假 假假choice=2choice=2真 choice=2順序表的建立 真順序表的建立 真 假順序表的插入choice=4 順序表的插入choice=4 真 假Choice=64Choice=64Choice=54 真 真真 返回主菜單返回主菜單鏈表的運(yùn)算鏈表的運(yùn)算 輸入 輸入 假choice=0 choice=0 choice=1 假choice=1 choice=3 choice=3choice=2 真 假 假假choice=2choice=2真 choice=2單鏈表的建立 真單鏈表的建立 真 假單鏈表的插入choice=4 單鏈表的插入choice=4 真 假Choice=74

27、CChoice=74Choice=64 真 真真 返回主菜單返回主菜單串的模式匹配串的模式匹配 輸入 輸入 假choice=0 choice=0 choice=1 假choice=1 假假choice=3 choice=3choice=2 真 假 choice=2choice=2真 choice=2求next的值 真求next的值 真 求字串nextval 求字串nextval 返回主菜單返回主菜單3.3 算法實(shí)實(shí)現(xiàn)的原程序序typedeff unsiigned char SStriingMAAXSTRLLEN +11;/*字字符串的數(shù)據(jù)據(jù)類型*/typedeff int Statuus;ty

28、pedeff int ElemTType;typedeff struuct ElemTType *elem; int llengthh; int llistsiize; SqLiist;/*順序表的數(shù)數(shù)據(jù)類型*/typedeff struuct LNNode ElemTType ddata; strruct LLNode *nextt;LNode,*LinkkList;/*單鏈表表的數(shù)據(jù)類型型*/每一個(gè)抽象數(shù)據(jù)據(jù)結(jié)構(gòu)對(duì)應(yīng)的的算法如下void prrint_SSq(SqLList LL)/打印順序序表的全部元元素。int i;int aMaxSiize;for(i=0;iLL.lenggth;i

29、+)/從第00個(gè)元素開始始，一直到LL.lenggth輸出LL的值ai=LL.elemmi;printff(%4dd,aii);printff(n);/prinnt_Sq void printt_Sq(SSqListt L)/打印順序序表的全部元元素。int i;int aMaxSiize;for(i=0;iLL.lenggth;i+)/從第00個(gè)元素開始始，一直到LL.lenggth輸出LL的值ai=LL.elemmi;printff(%4dd,aii);printff(n);/prinnt_Sq void MeergeLiist(SqqList La,SqqList Lb,SqqList

30、&Lc)/已知線性性表La和LLb中的數(shù)據(jù)據(jù)元素按值非非遞減排列/歸并Laa和Lb得到到新的線性表表Lc,Lcc的數(shù)據(jù)元素素也按值非遞遞減排列。 intt ai,bbj,i,jj,k,Laa_len,Lb_leen; IniitListt_Sq(LLc);i=j=1;k=0;La_lenn=La.llengthh;Lb_lenn=Lb.llengthh;while(i=LLa_lenn)&(jj=Lb_len)/當(dāng)其其中任意一個(gè)個(gè)表沒有選擇擇完的時(shí)候GetEleem(La,i,ai); /調(diào)用用GetEllem()函函數(shù)，獲取LLa的值，并并賦給aiGetEleem(Lb,j,bj);if(a

31、i=bj) /把其其中小的插入入到Lc中 LisstInseert_Sqq(Lc,+k,aii);/*調(diào)調(diào)用ListtInserrt_Sq把把小的值插入入到中*/ +i; /*ii的值加1，指指向下一個(gè)元元素*/else ListIInsertt_Sq(LLc,+kk,bj); +j;/elsse/whiilewhile(i=Laa_len)/*把LLa中剩余的的元素賦給LLc*/GetEllem(Laa,i+,ai); ListInnsert_Sq(Lcc,+k,ai);while(j=Lbb_len) /*把LLb中剩余的的元素賦給LLc*/GetEleem(Lb,j+,bbj); Lis

32、tInnsert_Sq(Lcc,+k,bj);/whiile/MerggeListtStatus GetEllem(SqqList L,EleemTypee i,EllemTyppe &e)/把線性表表L中的第ii個(gè)元素傳遞遞給e if(iL.llengthh) /i的范圍圍有誤，要重重新輸入printtf(范圍圍錯(cuò)誤!nn);returrn 0; ee=L.ellemi-1; /吧線性性表的第i個(gè)個(gè)元素取出來來。 retturn 11; /GetEllemvoid unnionSqq(SqLiist &LLa,SqLList LLb)/將所有在在線性表Lbb中但不在LLa中的數(shù)據(jù)據(jù)元素插入到

33、到La中ElemTyype Laa_len,Lb_leen,i;ElemTyype e;La_len=La.leength; Lb_len=LLb.lenngth;for(i=11;i=LLb_lenn;i+)GetElemm(Lb,ii,e); /調(diào)用GettElem()函數(shù)，獲獲取Lb中的的第i個(gè)值，并并賦給e if(!LoccateEllem_Sqq(La,ee, commpare)/*調(diào)用用LocatteElemm_Sq函數(shù)數(shù)，如果在LLa中找不到到與e相等的的函數(shù)， 就把把e插入到LLa中，否則則不進(jìn)行插入入*/ListInssert_SSq(La,+La_len,ee);/unio

34、onSqStatus LocatteElemm_Sq(SSqListt L,EllemTyppe e,SStatuss (*coomparee)(EleemTypee, EleemTypee) /在在順序線性表表中查找第一一個(gè)與e值滿滿足comppare關(guān)系系的位序/若找到則則返回其在LL中的位序，否否者返回0 EleemTypee i=1; EleemTypee *p=LL.elemm; /*把LL的首元素的的地址給p*/ whiile(i=L.leength&!(*ccomparre)(*pp+,e) /*找找到與e相等等的元素，并并且i在合法法的值以內(nèi)*/ +i; if(i=L.leng

35、tth)/*ii的值比元素素個(gè)數(shù)少，是是正常的查找找*/ reeturn i; elsse retuurn 0; /查找不成功功，返回0./LocaateEleem_SqStatus ListDDeletee_Sq(SSqListt &L,iint i,ElemTType &e)/在順序線線性表L中刪刪除第i個(gè)元元素，并用ee返回其值/i的合法法值為1=i=L.lengtth。ElemTyype *pp,*q; if(iiL.lengtth) rreturnn ERROOR;/*輸輸入i的位置置不合法，函函數(shù)退出，返返回0*/ p=&(LL.elemmi-1); /把線性表表的第i個(gè)值值的地址

36、給pp e=*p; /把的pp所指元素值值賦給e q=L.eelem+LL.lenggth-1; /*qq指向最后一一個(gè)元素*/ for(+p;p=q;+p) *(p-1)=*pp; /*從i開開始，把所有有的元素都向向前移動(dòng)*/ -L.lengtth; /*順序表的的長度減少11*/ returrn OK; /LiistDellete_SSq Statuss comppare(EElemTyype a11, EleemTypee a2) /如果aa1和a2相相等，則返回回1，否者返返回0 iif(a1=a2) retturn 11; eelse retturn 00;/listtDelett

37、e_SqStatus ListIInsertt_Sq(SSqListt &L,iint i,ElemTType ee) /在順序序表L中第ii個(gè)位置之前前插入新的元元素e /i的合合法值為1=i=LL.lenggth+1 ElemTyype *nnewbasse,*p,*q;if(iL.lengtth+1) /i值值不合法printff(范圍錯(cuò)錯(cuò)誤,請(qǐng)重新新輸入n);returnn ERROOR;if(L.leength=L.liistsizze)/當(dāng)前空間已已滿，增加分分配 newwbase=(ElemmType *)reaalloc(L.eleem,(L.listssize+LLISTIN

38、NCREMEENT)*ssizeoff(ElemmType);if(!neewbasee) priintf(空間已經(jīng)滿滿了，無法獲獲得新空間n); exiit(OVEERFLOWW); /存儲(chǔ)分配失失敗 L.ellem=neewbasee; L.liistsizze+=LIISTINCCREMENNT; /容量相應(yīng)地地增加 q=&(LL.elemmi-1); /q為插入入位置 for(pp=&(L.elemL.lenngth-11);p=q;-p) *(p+11)=*p; /插入入位置及之后后的元素右移移 *q=e; +L.llengthh;/表長長增1 returrn OK;/ListtIn

39、serrt_SqStatus InitLList_SSq(SqLList &L)/構(gòu)造一個(gè)空空的線性表 L.elem=(ElemmType *)mallloc(LLIST_IINIT_SSIZE*ssizeoff(ElemmType); iff(!L.eelem) printff(分配不不了地址);exitt(OVERRFLOW); L.lenngth=00; /初始化沒沒有元素，順順序表的長度度為0 L.lisstsizee=LISTT_INITT_SIZEE; /存存儲(chǔ)空間初始始化的空間 returrn OK; /InittList_Sqint Inddex_KMMP(SSttring S

40、,SSttring T,intt &poss, intt nexttval)/利用模式串串T的nexxt函數(shù)求TT在主串中第第pos個(gè)字字符之后/的位置的的KMP算法法。其中，TT非空，1=pos=StrLLengthh(S) int i=pos; int j=1,k=11; while(i=S0&jjTT0)printff(最后匹匹配成功,在在第%4d個(gè)個(gè)位置n,i-T0);returnn i-T0; /返回成成功匹配的位位置else printff(最后匹匹配不成功!n);returnn 0;/Indeex_KMPPvoid geet_nexxtval(SStriing T,int nne

41、xtvaal)/求模式串串T的nexxt函數(shù)修正正值并存入數(shù)數(shù)組nexttvalint i=1,j=00;nextvaal1=0;while(iT00)if(j=0|TTi=Tj) /*11的nexttval是00*/+i; /*i和jj各加1*/+j; if(TTi!=Tj) nexxtvali=j; /*字符符串不相等，就就上一次的jj賦給nexxtval*/elsee nexttvalii=nexxtvalj; /*相等的的話就把前一一個(gè)nexttval的值值賦給這個(gè)*/iff elsee j=neextvallj;/*若不相等等的話，就可可以吧nexxtval賦賦給j*/whiile/

42、get_nextvvalvoid geet_nexxt(SSttring T,intt nextt)/求模式串串T的nexxt函數(shù)值并并存入數(shù)組 i=1,j;next11=0; /*1的的next是是0*/j=0;while(inext; /*后面的就就指向La*/pb=Lb-next;Lc=pc=LLa;while(ppa&pbb)if(pa-dataadataa) pc-next=pa; /*pa指指向的節(jié)點(diǎn)值值小，就把該該連到Lc中中*/ pc=ppa; /*pcc指最新連入入的節(jié)點(diǎn)*/ ppa=pa-nextt; /*pa指向下下一個(gè)節(jié)點(diǎn)*/elseppc-neext

43、=pbb;/*pbb指向的節(jié)點(diǎn)點(diǎn)值小，就把把該連到Lcc中*/ ppc=pb; /*pcc指最新連入入的節(jié)點(diǎn)*/ pb=ppb-neext;/*pb指向下下一個(gè)節(jié)點(diǎn)*/pc-neext=paa?pa:ppb; /*指向不為為空的那個(gè)結(jié)結(jié)點(diǎn)*/free(LLb); /*釋放LLb的空間*/MerggeListt_void prrint_LL(LinkkList head) LinkkList p=heaad-neext; whille(p!=NULL) /*p不不為空*/ printtf(%55d,p-dataa ); p=p-next; /*p指向下一一個(gè)結(jié)點(diǎn)*/printff(n);/pri

44、nnt_Lint LisstLenggth_L(LinkLList LL) LinkkList p=L; int i=0; whille(p-next!=NULLL)/*當(dāng)pp不為空*/ ii+; /*i加1*/ pp=p-nnext; /wwhile retuurn (ii);/ListtLengtth_LStatus ListDDeletee_L(LiinkLisst &L, int i, EllemTyppe &e) /在帶帶頭結(jié)點(diǎn)的單單鏈線性表LL中，刪除第第i個(gè)元素，并并由e返回其其值 LinkLList qq,p=L; int jj=0; whilee(p-nnext&jneext

45、; /*p指向下下一個(gè)節(jié)點(diǎn)*/ +j; if(!(p-neext)|ji-11) /*i的值小小于1或者大大于L.leength*/ prinntf(刪刪除位置不合合理!n); retuurn ERRROR; q=p-next; p-neext=q-nextt; /刪除第i個(gè)個(gè)結(jié)點(diǎn) e=q-data; /把該節(jié)點(diǎn)的的值賦給e free(q); /*釋放已已刪結(jié)點(diǎn)的空空間*/ printtf(刪除除%d成功！n,ee); returrn OK;/ListtDeletteStatus GetEllem_L(LinkLList LL,int i,EleemTypee &e)/L為帶頭頭結(jié)點(diǎn)的單鏈鏈表

46、的頭指針針 /當(dāng)當(dāng)?shù)趇個(gè)元素素存在時(shí)，其其值賦給e并并返回OK，否否者返回ERRRORLNode *p;ElemTyppe j;p=L-neext;j=1;while(pp&jnnext; +j;if(!p|ji) /ii小于1或者者大于表長printff(第%44d個(gè)元素不不存在,ii);returnn ERROOR;e=p-daata; /*找到到地i個(gè)元素素，并賦給ee*/printf(第%4dd元素為%44d,i,e);return OK;/GetEElem_LLint LoccateEllem_L(LinkLList LL,ElemmType e) /*在單鏈鏈表L中從頭頭開始找第1

47、1個(gè)值域與ee相等的節(jié)點(diǎn)點(diǎn)， *若存在在這樣的節(jié)點(diǎn)點(diǎn)，則返回位位置，并打印印該結(jié)點(diǎn)的值值 */ LinnkListt p=L-nextt;int i=1;while(p!=NUULL&pp-datta!=e) /*pp沒有指向表表尾，并且沒沒有找到元素素e*/ p=p-nextt;/*p指指向下一個(gè)結(jié)結(jié)點(diǎn)*/ i+;/whiileif(p=NULL) /找到表尾，沒沒有找到元素素eprinttf(這個(gè)個(gè)數(shù)值%d不不存在,ee);returrn NULLL;elseprinttf(你所所查詢的數(shù)%d是第%dd個(gè),e,i);returrn (i);/LocaateEleem_LStatus Lis

48、tIInsertt_L(LiinkLisst &L,int ii,ElemmType e)/在帶頭結(jié)結(jié)點(diǎn)的單鏈表表L中第i個(gè)個(gè)位置之前插插入元素eLinkLisst s,pp=L; int j=00;while(pp&jneext; /p指向向下一個(gè)節(jié)點(diǎn)點(diǎn) +j;if(!p|ji-11)printff(第%44d節(jié)點(diǎn)不存存在n,i); /p為空，或或者i小于11或者大于表表長加1returnn ERROOR;s=(LinkkList)mallooc(sizzeof(LLNode);/生生成新的結(jié)點(diǎn)點(diǎn)s-dataa=e;s-nextt=p-nnext; /插入LL中,使s成成為第i個(gè)結(jié)結(jié)點(diǎn)p-n

49、extt=s;printf(插入成功功！n);return OK;/ListtInserrt_Lvoid CrreateLList_LL(LinkkList &L,innt n)/順位序輸輸入n個(gè)元素素的值，建立立帶頭結(jié)點(diǎn)的的單鏈表L LinkkList s,r; int i; L=(LLinkLiist)maalloc(sizeoof(LNoode);/開辟一一個(gè)新的空間間 r=L; if(nn1) /長長度要大于等等于1 priintf(長度有問題題n); retturn; for(i=1;iidaata);/*給該節(jié)點(diǎn)點(diǎn)賦值*/ r-nextt=s; /*把新的節(jié)節(jié)點(diǎn)連接到表表尾*/ r

50、=s; /*rr指向表尾*/ r-nnext=NNULL;/尾指針的的next為為空/CreaateLisst_Lint maiin()systemm(collor 1AA);/選擇顏色的的函數(shù) int cchoicee; innt lagg=0; whhile(11)/用用whilee和swittch來控制制菜單，三個(gè)個(gè)子模塊和這這個(gè)算法相同同 systtem(CCLS);/清屏函函數(shù) putss(n); priintf(ttn); putts(ttttt歡歡迎使用數(shù)據(jù)據(jù)結(jié)構(gòu)演示系系統(tǒng)t);puts(tttt tt); puuts(tttt 順序序表的運(yùn)算 tt); puts(ttttt 鏈

51、表表的運(yùn)算 tt); puts(ttttt 串的的模式匹配 tt); puts(ttttt 退退出 ttt); puuts(tttt 請(qǐng)輸入你的的選擇:ttt); puts(ttttt tt); printtf(tttn); printtf(ttttt ); sscanf(%d,&choiice);switchh(intt)choiice) casse 0: returrn 1;case 11: SqLListfuun(); breeak; /順序表表的運(yùn)算case 22: LinnkListtfun(); breeak; /鏈表的的運(yùn)算 casse 3: Indexx_SS(); break

52、k; /模式匹配defaullt: prrintf(輸入的序序號(hào)不正確！請(qǐng)重新輸入入n);systeem(PAAUSE);breakk;/swiitch /whhile/mainn調(diào)試分析4.1 調(diào)試中中的問題 在寫第一個(gè)個(gè)系統(tǒng)的過程程中，發(fā)現(xiàn)要要實(shí)現(xiàn)的功能能很多，這樣樣寫起來，系系統(tǒng)會(huì)很龐雜雜。我用傳遞遞參數(shù)解決了了這個(gè)問題。為為了避免主菜菜但中有過多多的程序。我我把每一個(gè)子子模塊都寫在在一個(gè)函數(shù)中中，主菜單只只要調(diào)用這些些函數(shù)就可以以了。這樣主主菜單就能夠夠很簡短。其其次，每一個(gè)個(gè)子菜單的功功能是獨(dú)立的的，又可以在在子菜單中重重新定義函數(shù)數(shù)，實(shí)現(xiàn)各種種功能。這樣樣修改起來會(huì)會(huì)很方便，并并且

53、符合結(jié)構(gòu)構(gòu)化的程序設(shè)設(shè)計(jì)。最開始遇到的問問題是與傳遞遞參數(shù)有關(guān)的的問題。當(dāng)時(shí)時(shí)我寫了很個(gè)個(gè)子程序的算算法，編譯結(jié)結(jié)果0個(gè)錯(cuò)誤誤，0個(gè)警告告。我就以為為程序可以運(yùn)運(yùn)行，可以一一旦調(diào)用程序序，電腦就報(bào)報(bào)出內(nèi)存不能為wrrittenn或者內(nèi)存不不能為reaad。我找不不到解決的方方法，因?yàn)闆]沒有語法的錯(cuò)錯(cuò)誤。我把結(jié)結(jié)構(gòu)也改為結(jié)結(jié)構(gòu)體指針，在在把所有的調(diào)調(diào)用重新改一一遍，還是不不行。沒辦法法，這個(gè)超出出我的能力范范圍之外。我我已經(jīng)寫了那那么多程序了了，想要改變變算法重新寫寫估計(jì)也不可可能了。一方方面，我暫時(shí)時(shí)放開題目11,就靜下心心來寫第三個(gè)個(gè)程序。另外外一方面，我我找到程序設(shè)設(shè)計(jì)很熟練的的人幫我改錯(cuò)

54、錯(cuò)。功夫不負(fù)負(fù)有心人，他他一下子就看看到我的錯(cuò)誤誤。要再每一一個(gè)需要改變變的形參前加加一個(gè)“&“，不讓程序序無法運(yùn)行。這這代表傳遞參參數(shù)。我終于于明白是怎么么回事。馬上上修改自己的的程序，果然然全都能運(yùn)行行并的到正確確的結(jié)果。在課程設(shè)計(jì)過程程中，相互幫幫助非常重要要。最開始我我只會(huì)寫菜單單，而不知道道怎樣去實(shí)現(xiàn)現(xiàn)一個(gè)個(gè)算法法。而我的一一位同學(xué)把這這些算法都寫寫過一遍，卻卻對(duì)程序設(shè)計(jì)計(jì)不怎么熟練練。我們正好好互補(bǔ)，他給給我指明了方方向，如何實(shí)實(shí)現(xiàn)這些算法法。而我教了了他如何把這這些算法整合合到一起形成成一個(gè)系統(tǒng)。此外，有些問題題經(jīng)過討論才才得出來。比比如，在寫順順序表和鏈表表的操作時(shí)，就就遇到一

55、個(gè)問問題，用戶必必須懸著菜單單1建立順序序表或者菜單單，才能夠進(jìn)進(jìn)行后面的操操作。如果用用戶沒喲建立立線性表就進(jìn)進(jìn)行操作，系系統(tǒng)不會(huì)報(bào)錯(cuò)錯(cuò)，但是程序序會(huì)無法執(zhí)行行。這樣，我我就想出了要要寫一個(gè)先把把程序，只有有當(dāng)這個(gè)菜單單執(zhí)行后，其其它的菜單才才能夠開通。若若用戶直接選選擇后面的菜菜單，就會(huì)提提示用戶先建建立。這個(gè)功功能是我在設(shè)設(shè)計(jì)系統(tǒng)前沒沒喲想到的。有有了這個(gè)經(jīng)驗(yàn)驗(yàn)后，在串的的模式匹配的的子模塊中，由由于第三個(gè)菜菜單中KMPP模式匹配算算法用的是菜菜單二中的nnextvaal，而菜單單二中的neextvall又是從菜單單一中的字串串中的到的。那那么必須先執(zhí)執(zhí)行菜單1，在在執(zhí)行菜單22，最后執(zhí)

56、行行菜單三，才才能的到正確確的結(jié)果。用用上述的方法法，設(shè)置兩個(gè)個(gè)LAG很快快就能夠?qū)崿F(xiàn)現(xiàn)這個(gè)功能了了。在寫代碼的過程程中，有時(shí)候候會(huì)遇到一些些莫名的錯(cuò)誤誤，比如以前前能夠的到的的結(jié)果，現(xiàn)在在卻得不到了了。有些程序序明明沒有錯(cuò)錯(cuò)誤，卻得不不到正確的結(jié)結(jié)果。其實(shí)這這都是在一些些小的方面出出了問題。比比如i,j看不清清，兩個(gè)數(shù)組組一下子忘記記改變了，該該加1的沒有有加。在進(jìn)行行插入或者刪刪除操作時(shí)，對(duì)對(duì)i的長度的的限定，是llengthh+1,還是是lengtth，也都需需要詳細(xì)的推推敲。又是后后需要用某些些變量做標(biāo)記記，卻忘記給給該變量賦初初值，導(dǎo)致出出現(xiàn)-25666的數(shù)字。又又是后指針和和地址沒

57、有分分辨清楚，打打印出的結(jié)果果也會(huì)很奇怪怪。后來想要把界面面做的美觀，就就想到用一些些特殊的符號(hào)號(hào)來裝飾界面面。我懸著了了有花紋的粗粗邊框。可想想要吧這個(gè)符符號(hào)整合成一一個(gè)完整的矩矩形，還是要要細(xì)細(xì)的琢磨磨。沒調(diào)試一一下就上機(jī)運(yùn)運(yùn)行一次。方方框做好了，又又要保證字體體在正中央，還還得重新調(diào)試試。在和同學(xué)的不斷斷交流中，我我知道了怎么么利用，清屏屏函數(shù)，暫停停函數(shù)，還有有顏色配置函函數(shù)來把我的的界面變成彩彩色。并且沒沒執(zhí)行完一個(gè)個(gè)工功能都會(huì)會(huì)暫停，顯得得更人性化。要做到很好的設(shè)設(shè)計(jì)程序，還還是要嚴(yán)格推推敲，多編程程，所實(shí)踐，多多思考。4.2算法的時(shí)時(shí)間復(fù)雜度以下是各個(gè)菜單單的時(shí)間復(fù)雜雜度的列表，

58、以以及如何改進(jìn)進(jìn)。主菜main 有幾個(gè)子菜菜單就有要比比較幾次，時(shí)時(shí)間復(fù)雜度為為O(n);同樣三個(gè)子菜單單的時(shí)間復(fù)雜雜度也都是OO(n);由由于需要用戶戶來選擇，需需要和每一個(gè)個(gè)選項(xiàng)比較，無無法提高復(fù)雜雜度，可以設(shè)設(shè)置指針，如如果用戶輸入入一個(gè)選項(xiàng)，就就自動(dòng)連接到到該選項(xiàng)指定定的命令，時(shí)時(shí)間復(fù)雜度就就可以變?yōu)镺O(1)了； InitLisst_Sq(&L),OO（1），初初始化，一次次性分配空間間 ListInnsert_Sq(SqqList &L,innt i,EElemTyype e), O（n），在在插入的位置置之后的元素素全部都要向向后移動(dòng)ListDellete_SSq(SqLList

59、 &L,intt i,EllemTyppe &e), O（n），在在刪除的位置置之后的元素素全部都要向向前移動(dòng)print_SSq(SqLList LL), O（nn），打印nn個(gè)數(shù)字。GetElemm(SqLiist L,ElemTType ii,ElemmType &e)，OO（1），直直接定位置unionSqq(SqLiist &LLa,SqLList LLb) OO(m*n),表B中的的元素要和表表A中的每一一個(gè)元素比較較MergeLiist(SqqList La,SqqList Lb,SqqList &Lc)。OO(m+n),有序合并并，相對(duì)應(yīng)比比較就行。unionSqq(SqLiis

60、t &LLa,SqLList LLb)，O(m+n),有序合并，相相對(duì)應(yīng)比較就就行。 LocateeElem_Sq(SqqList L,EleemTypee e,Sttatus (*commpare)(ElemmType, ElemmType)O（n），把整整個(gè)表都找一一遍comparee(ElemmType a1, EElemTyype a22)，O(11),CreateLList_LL(LinkkList &L,innt n),O(n),用戶輸入nn個(gè)數(shù)字ListInssert_LL(LinkkList &L,innt i,EElemTyype e)，O（1），只只需要改變節(jié)節(jié)點(diǎn)指針Lis