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

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

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

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

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

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

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

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

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

9、har SStringMAXSTRLEN +1;typedef struct LNode ElemType data; struct LNode *next;LNode,*LinkList; 順序表的各種抽象數(shù)據(jù)類型的定義如下 ADT list_Sq數(shù)據(jù)對象：D=ai|aiElemSet,i=1,2,n,n>=0數(shù)據(jù)關(guān)系：R1=<ai-1,ai>|ai-1,aiD,i=2,n基本操作： Status InitList_Sq(SqList &L) 操作結(jié)果：構(gòu)造一個空的線性順序表L。 Status GetElem(SqList L,ElemType i,ElemType

10、 &e) 初始條件：線性表L已存在，1<=i<=Listlength(L)。操作結(jié)果：把線性表L中的第i個元素傳遞給e。 Status ListInsert_Sq(SqList &L,int i,ElemType e) 初始條件：線性表L已存在，1<=i<=Listlength(L)+1。 操作結(jié)果：在順序表L中第i個位置之前插入新的元素e，L的長度加1。 Status ListDelete_Sq(SqList &L,int i,ElemType &e) 初始條件：線性順序表L已存在且非空，i的合法值為1<=i<=L.leng

11、th。 操作結(jié)果：在順序線性表L中刪除第i個元素，并用e返回其值，L的長度減1。 Status LocateElem_Sq(SqList L,ElemType e,Status (*compare)(ElemType, ElemType) 初始條件：線性表L已存在，1<=i<=Listlength(L)。操作結(jié)果：在順序線性表中查找第一個與e值滿足compare關(guān)系的位序 若找到則返回其在L中的位序，否者返回0void print_Sq(SqList L)初始條件：線性表L已存在。 操作結(jié)果：打印順序表的全部元素。 void unionSq(SqList &La,SqLis

12、t Lb)初始條件：線性順序表La和Lb已存在且非空。 操作結(jié)果：將所有在線性表Lb中但不在La中的數(shù)據(jù)元素插入到La中. void MergeList(SqList La,SqList Lb,SqList &Lc) 初始條件：已知線性表La和Lb已存在且非空，其中的數(shù)據(jù)元素按值非遞減排列 操作結(jié)果：歸并La和Lb得到新的線性表Lc,Lc的數(shù)據(jù)元素也按值非遞減排列。void print_Sq(SqList L)初始條件：線性表L已存在。 操作結(jié)果：打印順序表的全部元素。 Status compare(ElemType a1, ElemType a2) 操作結(jié)果：比較a1和a2的值，如果

13、a1和a2相等，者返回1,否則返回0； 鏈表的各種抽象數(shù)據(jù)類型定義如下：ADT list_L數(shù)據(jù)對象：D=ai|aiElemSet,i=1,2,n,n>=0數(shù)據(jù)關(guān)系：R1=<ai-1,ai>|ai-1,aiD,i=2,n基本操作：void CreateList_L(LinkList &L,int n)操作結(jié)果：順位序輸入n個元素的值，建立帶頭結(jié)點的單鏈表L。void print_L(LinkList head)操作結(jié)果：在界面上打印head結(jié)點。 初始條件：單鏈線性表L存在。 操作結(jié)果：返回單鏈線性表的長度。Status ListInsert_L(LinkList &

14、amp;L,int i,ElemType e) 初始條件：單鏈線性表L存在且不為空，1<=i<=Listlength(L)+1。操作結(jié)果：在帶頭結(jié)點的單鏈表L中第i個位置之前插入元素e。Status ListDelete_L(LinkList &L, int i, ElemType &e) 初始條件：單鏈線性表L存在，i的合法值為1<=i<=L.length。 在帶頭結(jié)點的單鏈線性表L中，刪除第i個元素，并由e返回其值。int LocateElem_L(LinkList L,ElemType e)初始條件：單鏈線性表L已存在且非空。 操作結(jié)果：在單鏈表L

15、中從頭開始找第1個值域與e相等的節(jié)點，若存在這樣的節(jié)點，則返回位置，并打印該結(jié)點的值。Status GetElem_L(LinkList L,int i,ElemType &e) 初始條件： L為帶頭結(jié)點的單鏈表的頭指針，1<=i<=L.length。 操作結(jié)果：當(dāng)?shù)趇個元素存在時，其值賦給e并返回OK，否者返回ERROR。 void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) 初始條件：單鏈表La和Lb非空，且其中的元素按值非遞減排列。 操作結(jié)果：歸并La和Lb得到新單鏈表Lc，Lc的元素

16、也按值非遞減排列。 Status compare(ElemType a1, ElemType a2) 操作結(jié)果：比較a1和a2的值，如果a1和a2相等，者返回1,否則返回0；串的抽象數(shù)據(jù)類型的定義如下：ADT String 數(shù)據(jù)對象：D=ai|aiElemSet,i=1,2,n,n>=0數(shù)據(jù)關(guān)系：R1=<ai-1,ai>|ai-1,aiD,i=2,n基本操作：void get_next(SString T,int next)操作結(jié)果：求模式串T的next函數(shù)值并存入數(shù)組next.。 void get_nextval(SString T,int nextval) 初始條件：T非

17、空。操作結(jié)果：求模式串T的next函數(shù)修正值并存入數(shù)組nextval。 int Index_KMP(SString S,SString T,int &pos, int nextval)初始條件：T非空，1<=pos<=StrLength(S)。操作結(jié)果：利用模式串T的next函數(shù)求T在主串中第pos個字符之后的位置的KMP算法。2.2 各個函數(shù)的調(diào)用關(guān)系各個函數(shù)的調(diào)用關(guān)系：main()調(diào)用SqListfun()，LinkListfun()，Index_SS();。SqListfun()調(diào)用InitList_Sq(&L), ListInsert_Sq(SqList &

18、amp;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(SqList &La,SqList Lb)和MergeList(SqList La,SqList Lb,SqList &Lc)。其中，unionSq(SqList &La,SqList Lb)調(diào)用LocateElem_Sq(SqList L,ElemType e,Status

19、 (*compare)(ElemType, ElemType)，和compare(ElemType a1, ElemType a2)。 LinkListfun()調(diào)用CreateList_L(LinkList &L,int n)，ListInsert_L(LinkList &L,int i,ElemType e)，ListDelete_L(LinkList &L, int i, ElemType &e)，int ListLength_L(LinkList L)，LocateElem_L(LinkList L,ElemType e), GetElem_L(Link

20、List L,int i,ElemType &e), MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)和print_L(LinkList head)。而Index_SS()調(diào)用了get_next(SString T,int next)，get_nextval(SString T,int nextval)，Index_KMP(SString S,SString T,int &pos, int nextval)。 第三章 詳細(xì)設(shè)計3.1系統(tǒng)程序的組成框圖主函數(shù)對各個函數(shù)的調(diào)用關(guān)系圖。 歡迎界面0：退出系統(tǒng)

21、； 1：順序表的運算；2：鏈表的運算； 3：串的模式匹配 其它選項，輸入錯誤返回主菜單。0：退出系統(tǒng)，安全退出。3：串的模式匹配又有四個選項。2：鏈表的運算又有八個選項。1：SqListfun() 順序表的運算又有七個選項。SqListfun()對各個函數(shù)的調(diào)用錯誤輸入，系統(tǒng)自動返回菜單 順序表的運算0：返回上一層； 1：順序表的建立；2：順序表的插入； 3：順序表的刪除；4：順序表的查找 ；5：順序表的無序合并；6：順序表的有序合并； 0。：返回上一層，就是放回到主函數(shù)。Main()6用戶重新建立兩升序的順序表，合并它們，且合并后有序。5：用戶要再建立一個線性表B，系統(tǒng)吧表B合并到表A中。4

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

23、輸入要插入的位置和數(shù)字，把數(shù)字插入到之前建立的鏈表中1： 用戶輸入人一連串?dāng)?shù)字，建立一個線性鏈表。4：用戶輸入要查找的元素位置，終端顯示元素。3：用戶輸入要刪除的位置3：按數(shù)字的位置來查詢。1.按數(shù)字的值來查詢。錯誤的輸入，會提示用戶并自動返回。模式匹配0：返回；1:求next的值;2: 求nextval的值;3:進(jìn)行模式匹配;Index_SS() 0.返回主界面。直接回到主菜單。3.在已經(jīng)求出nextal的情況下，進(jìn)行模式匹配。顯示每一次匹配失敗的位置。1.用戶輸入字串，幾面輸出next 的值。2.選擇這一項，界面直接顯示nextval的值。3.2 程序的流程圖我設(shè)計的程序，主函數(shù)的流程圖如

24、下：開始 輸入 假choice=0choice=0 假choice=1 真 假choice=2真 順序表的運算 真 假choice=3 鏈表的運算 真 真 choice=0串的模式匹配串的模式匹配 choice=0 真 choice=0 假 真 真 結(jié)束順序表的運算 輸入 假choice=0 choice=1 假 choice=3 choice=2 真 假 假choice=2真 順序表的建立 真 真 假順序表的插入choice=4 順序表的查找 真 假Choice=64Choice=54順序表的刪除 真 真 順序表的有序合并順序表的無序合并 返回主菜單鏈表的運算 輸入 假choice=0 ch

25、oice=1 假 choice=3 假choice=2 真 假 假choice=2真 單鏈表的建立 真 真 假單鏈表的插入choice=4 單鏈表的查找 真 假Choice=74Choice=64單鏈表的刪除 真 真 單鏈表的有序合并鏈表的輸出 返回主菜單串的模式匹配 輸入 假choice=0 choice=1 假 假choice=3 choice=2 真 假 choice=2真 求next的值 真 真 求字串nextval 串的模式匹配 返回主菜單3.3 算法實現(xiàn)的原程序typedef unsigned char SStringMAXSTRLEN +1;/*字符串的數(shù)據(jù)類型*/typedef

26、 int Status;typedef int ElemType;typedef struct ElemType *elem; int length; int listsize; SqList;/*順序表的數(shù)據(jù)類型*/typedef struct LNode ElemType data; struct LNode *next;LNode,*LinkList;/*單鏈表的數(shù)據(jù)類型*/每一個抽象數(shù)據(jù)結(jié)構(gòu)對應(yīng)的算法如下void print_Sq(SqList L)/打印順序表的全部元素。int i;int aMaxSize;for(i=0;i<L.length;i+)/從第0個元素開始，一直到

27、L.length輸出L的值ai=L.elemi;printf("%4d",ai);printf("n");/print_Sq void print_Sq(SqList L)/打印順序表的全部元素。int i;int aMaxSize;for(i=0;i<L.length;i+)/從第0個元素開始，一直到L.length輸出L的值ai=L.elemi;printf("%4d",ai);printf("n");/print_Sq void MergeList(SqList La,SqList Lb,SqList

28、&Lc)/已知線性表La和Lb中的數(shù)據(jù)元素按值非遞減排列/歸并La和Lb得到新的線性表Lc,Lc的數(shù)據(jù)元素也按值非遞減排列。 int ai,bj,i,j,k,La_len,Lb_len; InitList_Sq(Lc);i=j=1;k=0;La_len=La.length;Lb_len=Lb.length;while(i<=La_len)&&(j<=Lb_len)/當(dāng)其中任意一個表沒有選擇完的時候GetElem(La,i,ai); /調(diào)用GetElem()函數(shù)，獲取La的值，并賦給aiGetElem(Lb,j,bj);if(ai<=bj) /把其中小的

29、插入到Lc中 ListInsert_Sq(Lc,+k,ai);/*調(diào)用ListInsert_Sq把小的值插入到中*/ +i; /*i的值加1，指向下一個元素*/else ListInsert_Sq(Lc,+k,bj); +j;/else/whilewhile(i<=La_len)/*把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/MergeListS

30、tatus GetElem(SqList L,ElemType i,ElemType &e)/把線性表L中的第i個元素傳遞給e if(i<1|i>L.length) /i的范圍有誤，要重新輸入printf("范圍錯誤!n");return 0; e=L.elemi-1; /吧線性表的第i個元素取出來。 return 1; /GetElemvoid unionSq(SqList &La,SqList Lb)/將所有在線性表Lb中但不在La中的數(shù)據(jù)元素插入到La中ElemType La_len,Lb_len,i;ElemType e;La_len=L

31、a.length; Lb_len=Lb.length;for(i=1;i<=Lb_len;i+)GetElem(Lb,i,e); /調(diào)用GetElem()函數(shù)，獲取Lb中的第i個值，并賦給e if(!LocateElem_Sq(La,e, compare)/*調(diào)用LocateElem_Sq函數(shù)，如果在La中找不到與e相等的函數(shù)， 就把e插入到La中，否則不進(jìn)行插入*/ListInsert_Sq(La,+La_len,e);/unionSqStatus LocateElem_Sq(SqList L,ElemType e,Status (*compare)(ElemType, ElemTyp

32、e) /在順序線性表中查找第一個與e值滿足compare關(guān)系的位序/若找到則返回其在L中的位序，否者返回0 ElemType i=1; ElemType *p=L.elem; /*把L的首元素的地址給p*/ while(i<=L.length&&!(*compare)(*p+,e) /*找到與e相等的元素，并且i在合法的值以內(nèi)*/ +i; if(i<=L.length)/*i的值比元素個數(shù)少，是正常的查找*/ return i; else return 0; /查找不成功，返回0./LocateElem_SqStatus ListDelete_Sq(SqList &

33、amp;L,int i,ElemType &e)/在順序線性表L中刪除第i個元素，并用e返回其值/i的合法值為1<=i<=L.length。ElemType *p,*q; if(i<1)|(i>L.length) return ERROR;/*輸入i的位置不合法，函數(shù)退出，返回0*/ p=&(L.elemi-1); /把線性表的第i個值的地址給p e=*p; /把的p所指元素值賦給e q=L.elem+L.length-1; /*q指向最后一個元素*/ for(+p;p<=q;+p) *(p-1)=*p; /*從i開始，把所有的元素都向前移動*/

34、-L.length; /*順序表的長度減少1*/ return OK; /ListDelete_Sq Status compare(ElemType a1, ElemType a2) /如果a1和a2相等，則返回1，否者返回0 if(a1=a2) return 1; else return 0;/listDelete_SqStatus ListInsert_Sq(SqList &L,int i,ElemType e) /在順序表L中第i個位置之前插入新的元素e /i的合法值為1<=i<=L.length+1 ElemType *newbase,*p,*q;if(i<1

35、|i>L.length+1) /i值不合法printf("范圍錯誤,請重新輸入n");return ERROR;if(L.length>=L.listsize)/當(dāng)前空間已滿，增加分配 newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase) printf("空間已經(jīng)滿了，無法獲得新空間n"); exit(OVERFLOW); /存儲分配失敗 L.elem=newbase; L.listsize+=LISTINCREM

36、ENT; /容量相應(yīng)地增加 q=&(L.elemi-1); /q為插入位置 for(p=&(L.elemL.length-1);p>=q;-p) *(p+1)=*p; /插入位置及之后的元素右移 *q=e; +L.length;/表長增1 return OK;/ListInsert_SqStatus InitList_Sq(SqList &L)/構(gòu)造一個空的線性表 L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem) printf("分配不了地址");exi

37、t(OVERFLOW); L.length=0; /初始化沒有元素，順序表的長度為0 L.listsize=LIST_INIT_SIZE; /存儲空間初始化的空間 return OK; /InitList_Sqint Index_KMP(SString S,SString T,int &pos, int nextval)/利用模式串T的next函數(shù)求T在主串中第pos個字符之后/的位置的KMP算法。其中，T非空，1<=pos<=StrLength(S) int i=pos; int j=1,k=1; while(i<=S0&&j<=T0) /T為

38、非空串。若主串中第pos個字符之后存在與T相等的子串 /則返回第一個這樣的子串在S中的位置，否則返回0 if(j=0|Si=Tj) /*兩個字符相等，則繼續(xù)向后匹配*/+i;+j;else printf("第%d次在%d匹配失敗!n",k,i);k+;j=nextvalj; /*若匹配不成功，則把nextval賦給j從nextval開始匹配*/ if(j>T0)printf("最后匹配成功,在第%4d個位置n",i-T0);return i-T0; /返回成功匹配的位置else printf("最后匹配不成功!n");retur

39、n 0;/Index_KMPvoid get_nextval(SString T,int nextval)/求模式串T的next函數(shù)修正值并存入數(shù)組nextvalint i=1,j=0;nextval1=0;while(i<T0)if(j=0|Ti=Tj) /*1的nextval是0*/+i; /*i和j各加1*/+j; if(Ti!=Tj) nextvali=j; /*字符串不相等，就上一次的j賦給nextval*/else nextvali=nextvalj; /*相等的話就把前一個nextval的值賦給這個*/if else j=nextvalj;/*若不相等的話，就可以吧next

40、val賦給j*/while/get_nextvalvoid get_next(SString T,int next)/求模式串T的next函數(shù)值并存入數(shù)組 i=1,j;next1=0; /*1的next是0*/j=0;while(i<T0) if(j=0|Ti=Tj) +i;+j;nexti=j;/*前后相等或者j為0的時候，就把j賦給next*/else j=nextj; /*不相等就要返回，把next賦給j*/get_nextvoid MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)/已知單

41、鏈表La和Lb的元素按值非遞減排列 /歸并La和Lb得到新單鏈表Lc，Lc的元素也按值非遞減排列LinkList pa,pb,pc;/定義三個指針，前兩個指向La和Lb的nextpa=La->next; /*后面的就指向La*/pb=Lb->next;Lc=pc=La;while(pa&&pb)if(pa->data<=pb->data) pc->next=pa; /*pa指向的節(jié)點值小，就把該連到Lc中*/ pc=pa; /*pc指最新連入的節(jié)點*/ pa=pa->next; /*pa指向下一個節(jié)點*/elsepc->next=

42、pb;/*pb指向的節(jié)點值小，就把該連到Lc中*/ pc=pb; /*pc指最新連入的節(jié)點*/ pb=pb->next;/*pb指向下一個節(jié)點*/pc->next=pa?pa:pb; /*指向不為空的那個結(jié)點*/free(Lb); /*釋放Lb的空間*/MergeList_void print_L(LinkList head) LinkList p=head->next; while(p!=NULL) /*p不為空*/ printf("%5d",p->data ); p=p->next; /*p指向下一個結(jié)點*/printf("n");/print_Lint ListLength_L(LinkList L) LinkList p=L; int i=0; while(p->next!=NULL)/*當(dāng)p不為空*/ i+; /*i加1*/ p=p->next; /while return (i);/ListLength_LStatus ListDelete_L(LinkList &