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

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

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

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

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

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

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

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

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

9、改變其中中的“int”就可以。SSqListt是順序表的的數(shù)據(jù)類型，其其中包含三個個成員，一個個是ElemmType的的指針變量，第第二個是表中中元素的個數(shù)數(shù)，第三個是是表的當前容容量。第三個個是上面提到到的ElemmType，主主要表示各種種元素的數(shù)據(jù)據(jù)類型。第四四個是typpedef strucct LNoode *LinkkList,這個是鏈表表的元素類型型，每次用鏈鏈表都用這個個來定義新結(jié)結(jié)點。最后是是typeddef unnsigneed chaar SSttringMAXSTTRLEN +1;這這個是字符串串數(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ù)對象：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)造造一個空的線線性順序表LL。 Stattus GeetElemm(SqLiist L,ElemTType ii,ElemmType &e) 初始條件：線性表L已已存在，1=i=LListleength(L)。操作結(jié)果：把線線性表L中的的第i個元素素傳遞給e。 Stattus LiistInssert_SSq(SqLList &L,intt i,EllemTyppe e) 初初始條件：線線性表L已存存在，1=i=Liistlenngth(LL)+1。 操操作結(jié)果：在在順序表L中中第i個位置置之前插

12、入新新的元素e，LL的長度加11。 Stattus LiistDellete_SSq(SqLList &L,intt i,EllemTyppe &e) 初初始條件：線線性順序表LL已存在且非非空，i的合合法值為1=i=LL.lenggth。 操作結(jié)果果：在順序線線性表L中刪刪除第i個元元素，并用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個個元素的值，建建立帶頭結(jié)點點的單鏈表LL。void prrint_LL(LinkkList head)操作結(jié)果：在界界面上打印hhead結(jié)點點。 初始條件：單鏈線性表表L存在。 操作結(jié)果：返回單鏈線線性表的長度度。Status ListIInsertt_L(LiinkLisst &L,int ii,ElemmType e) 初始條件：單鏈線性表表L存在且不不為空，1=i=LListleength(L)+1。操作結(jié)果：在帶帶頭結(jié)點的單單鏈表L中第第i個位置之之前插入元素素e。S

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

15、eemTypee &e) 初始始條件： LL為帶頭結(jié)點點的單鏈表的的頭指針，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個字符之之后的位置的KMPP算法。2.2 各個函函數(shù)的調(diào)用關(guān)關(guān)系各個函數(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)。 第三章 詳細細設(shè)計3.1系統(tǒng)程序序的組成框圖圖主函數(shù)對各個函函數(shù)的調(diào)用關(guān)關(guān)系圖。 歡迎界面0：退出系統(tǒng)； 1：順序表的運算；2：鏈表的運算；

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

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

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

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

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

25、輸入 假choice=0choice=0 choice=0choice=0 假choice=1 choice=1 真 假choice=2真 choice=2順序表的運算順序表的運算 真 假choice=3 choice=3鏈表的運算 真真 鏈表的運算 真 choice=0choice=0串的模式匹配串的模式匹配 串的模式匹配串的模式匹配choice=0 choice=0 真 choice=0 choice=0 假 真真 真 結(jié)束結(jié)束順序表的運算順序表的運算 輸入 輸入 假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 真 真真 返回主菜單返回主菜單鏈表的運算鏈表的運算 輸入 輸入 假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 算法實實現(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ù)類型型*/每一個抽象數(shù)據(jù)據(jù)結(jié)構(gòu)對應(yīng)的的算法如下void prrint_SSq(SqLList LL)/打印順序序表的全部元元素。int i;int aMaxSiize;for(i=0;iLL.lenggth;i

29、+)/從第00個元素開始始，一直到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個元素開始始，一直到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)/當其其中任意一個個表沒有選擇擇完的時候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，指指向下一個元元素*/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個元素傳遞遞給e if(iL.llengthh) /i的范圍圍有誤，要重重新輸入printtf(范圍圍錯誤!nn);returrn 0; ee=L.ellemi-1; /吧線性性表的第i個個元素取出來來。 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個值，并并賦給e if(!LoccateEllem_Sqq(La,ee, commpare)/*調(diào)用用LocatteElemm_Sq函數(shù)數(shù)，如果在LLa中找不到到與e相等的的函數(shù)， 就把把e插入到LLa中，否則則不進行插入入*/ListInssert_SSq(La,+La_len,ee);/unio

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

36、給pp e=*p; /把的pp所指元素值值賦給e q=L.eelem+LL.lenggth-1; /*qq指向最后一一個元素*/ for(+p;p=q;+p) *(p-1)=*pp; /*從i開開始，把所有有的元素都向向前移動*/ -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個位置之前前插入新的元元素e /i的合合法值為1=i=LL.lenggth+1 ElemTyype *nnewbasse,*p,*q;if(iL.lengtth+1) /i值值不合法printff(范圍錯錯誤,請重新新輸入n);returnn ERROOR;if(L.leength=L.liistsizze)/當前空間已已滿，增加分分配 newwbase=(ElemmType *)reaalloc(L.eleem,(L.listssize+LLISTIN

38、NCREMEENT)*ssizeoff(ElemmType);if(!neewbasee) priintf(空間已經(jīng)滿滿了，無法獲獲得新空間n); exiit(OVEERFLOWW); /存儲分配失失敗 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)造一個空空的線性表 L.elem=(ElemmType *)mallloc(LLIST_IINIT_SSIZE*ssizeoff(ElemmType); iff(!L.eelem) printff(分配不不了地址);exitt(OVERRFLOW); L.lenngth=00; /初始化沒沒有元素，順順序表的長度度為0 L.lisstsizee=LISTT_INITT_SIZEE; /存存儲空間初始始化的空間 returrn OK; /InittList_Sqint Inddex_KMMP(SSttring S

40、,SSttring T,intt &poss, intt nexttval)/利用模式串串T的nexxt函數(shù)求TT在主串中第第pos個字字符之后/的位置的的KMP算法法。其中，TT非空，1=pos=StrLLengthh(S) int i=pos; int j=1,k=11; while(i=S0&jjTT0)printff(最后匹匹配成功,在在第%4d個個位置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; /*相等的的話就把前一一個nexttval的值值賦給這個*/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é)點值值小，就把該該連到Lc中中*/ pc=ppa; /*pcc指最新連入入的節(jié)點*/ ppa=pa-nextt; /*pa指向下下一個節(jié)點*/elseppc-neext

43、=pbb;/*pbb指向的節(jié)點點值小，就把把該連到Lcc中*/ ppc=pb; /*pcc指最新連入入的節(jié)點*/ pb=ppb-neext;/*pb指向下下一個節(jié)點*/pc-neext=paa?pa:ppb; /*指向不為為空的那個結(jié)結(jié)點*/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指向下一一個結(jié)點*/printff(n);/pri

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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