【正文】 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告《數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言版）》課程設(shè)計(jì)題 目 數(shù)據(jù)結(jié)構(gòu)演示系統(tǒng)1 和3 學(xué)生姓名 學(xué) 號(hào) 指導(dǎo)教師 學(xué) 院 信息科學(xué)與工程學(xué)院 專業(yè)班級(jí) 計(jì)算機(jī)類 完成時(shí)間 七月 czlzdj@目錄第一章 項(xiàng)目概述…………………………3 問(wèn)題的要求分析與描述………………………………………………........3 問(wèn)題的要求和限制…………………………………………………………3第二章 概要設(shè)計(jì) …………………………4第三章 詳細(xì)設(shè)計(jì)………………………….8……………………………………. 8 程序的流程圖………………………………………........11 算法的源程序……………………………………………15第四章 調(diào)試分析………………………24 調(diào)試方法……………………………………………...24 算法時(shí)間復(fù)雜度………………………………………25第五章 測(cè)試結(jié)果………………………26 正確的輸入與輸出…………………………………...26 錯(cuò)誤的輸入與輸出……………………………………32第六章 課程設(shè)計(jì)總結(jié) 個(gè)人的體會(huì)和感想…………………………………….41附錄A：演示系統(tǒng)1源代碼有詳細(xì)注釋………………………………………….43附錄B：演示系統(tǒng)2源代碼………………………………………………………..60參考文獻(xiàn)……………………………………………………………………………..82 第一章 項(xiàng)目概述 問(wèn)題的描述與分析 本次課程設(shè)計(jì)，我完成了兩個(gè)題目，數(shù)據(jù)結(jié)構(gòu)演示系統(tǒng)數(shù)據(jù)結(jié)構(gòu)演示系統(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)都要實(shí)現(xiàn)至少四種算法插入、刪除、查詢、合并。對(duì)于串還要實(shí)現(xiàn)模式匹配，使用KMP的快速算法，減小時(shí)間復(fù)雜度。順序表的插入、刪除和合并等基本操作。利用插入運(yùn)算建立鏈表；實(shí)現(xiàn)鏈表的查找、刪除、計(jì)數(shù)、輸出等功能以及有序鏈表的合并。串的模式匹配（包括求next和nextval的值）。數(shù)據(jù)結(jié)構(gòu)演示系統(tǒng)2 涉及了數(shù)據(jù)結(jié)構(gòu)常用的三種存儲(chǔ)結(jié)構(gòu)，順序、鏈?zhǔn)?、散列，算法主要是查找和排序。?shí)現(xiàn)靜態(tài)查找（包括順序查找、折半查找和插入查找）和動(dòng)態(tài)查找（包括二叉排序樹和二叉平衡樹）。根據(jù)輸入的數(shù)據(jù)實(shí)現(xiàn)下列內(nèi)部排序：①直接插入排序、折半插入排序、表插入排序和希爾排序；②快速排序；③簡(jiǎn)單選擇排序和堆排序；④歸并排序；⑤鏈?zhǔn)交鶖?shù)排序。 問(wèn)題的要求和限制 我做的界面以用戶為主，還兼容了容錯(cuò)能力。首先就是菜單的選擇均有容錯(cuò)能力。整形數(shù)字的范圍是3276832767，要求用戶輸入顯示在用戶界面上的整形數(shù)字（…），當(dāng)用戶輸入不正確的選項(xiàng)時(shí)，會(huì)自動(dòng)提示輸入錯(cuò)誤，并返回原菜單要求用戶從新輸入。其次，每一個(gè)子菜單同樣有相同的容錯(cuò)能力，對(duì)于某些子系統(tǒng)，用戶必須先建立線性表才能進(jìn)行操作，若不先建立線性表，程序同樣會(huì)回到主菜單，并提示用戶建立線性表。 由于用戶能輸入任意個(gè)數(shù)字進(jìn)行演示，并且長(zhǎng)度由用戶規(guī)定。系統(tǒng)規(guī)定用戶輸入的長(zhǎng)度應(yīng)該在1—100以內(nèi)。長(zhǎng)度小于1就沒(méi)有意義了，但也不能太大，輸入長(zhǎng)度太大，用戶會(huì)沒(méi)有時(shí)間去輸入線性表的元素。在輸入數(shù)字時(shí)，理論上是表的長(zhǎng)度不能小于1。如果小于1，則會(huì)提示輸入錯(cuò)誤，菜單自動(dòng)返回。此外，在進(jìn)行某些操作，如插入刪除時(shí)，用戶能在任意位置插入且能在任意位置刪除，不過(guò)位置必須在線性表的范圍之內(nèi)。若超過(guò)線性表的現(xiàn)有長(zhǎng)度，那么同樣會(huì)報(bào)錯(cuò)。 在用戶界面（DOS界面），用戶每執(zhí)行完一次操作，都會(huì)有相應(yīng)的提示。若用戶建立了線性表，則會(huì)顯示建立成功。若用戶進(jìn)行查找，都會(huì)提示查找成功與否。輸出地形式是以用戶存入線性表的數(shù)字為準(zhǔn)，一般都是整形。輸入其它形式的數(shù)字，會(huì)自動(dòng)轉(zhuǎn)化為整形。在串的模式匹配中，模式串和主串的長(zhǎng)度輸入是整形，規(guī)定用戶必須輸入1—100的數(shù)字，否則會(huì)提示錯(cuò)誤，要求從新輸入。而串的值是字符型。必須輸入字符，才能得到正確的結(jié)果。 數(shù)據(jù)結(jié)構(gòu)演示系統(tǒng)1主要有四個(gè)模塊，一個(gè)主模塊，三個(gè)子模塊。主模塊調(diào)用三個(gè)函數(shù)，SqListfun(),LinkListfun(),Index_SS(),分別指向三個(gè)不同功能的子模塊。SqListfun()實(shí)現(xiàn)上述順序線性表的算法，LinkListfun()實(shí)現(xiàn)上述連是線性表的算法，最后一個(gè)Index_SS()實(shí)現(xiàn)上述串的模式匹配算法。每一個(gè)模塊的調(diào)用以及返回都是通過(guò)用戶選擇菜單來(lái)實(shí)現(xiàn)的。這些模塊能夠演示順序表建立、插入、刪除、查找、無(wú)序合并和有序合并，鏈表的建立、插入、刪除、查找有序合并，用KMP算法實(shí)現(xiàn)串的模式匹配，給用戶看每一次匹配失敗的地方，和字串的 next和nextval值。 正確輸入以及出入結(jié)果：正確的菜單選擇是界面上面的數(shù)字，正確的大小范圍是1到100的長(zhǎng)度建立，正確的插入范圍是線性表的長(zhǎng)度范圍，正確的字符串長(zhǎng)度也是1到100，正確的模式匹配應(yīng)輸入字符。有了正確的輸入，系統(tǒng)會(huì)按要求，顯示正常的結(jié)果，如表中的元素是什么，表插入成功后表的元素也會(huì)增加，刪除成功會(huì)顯示刪除的是哪個(gè)元素哪個(gè)位置。 錯(cuò)誤的輸入會(huì)導(dǎo)致錯(cuò)誤的輸出，輸入不在菜單范圍內(nèi)的數(shù)字系統(tǒng)會(huì)自動(dòng)提示，接著返回原菜單。輸入超過(guò)線性表長(zhǎng)度范圍的位置，系統(tǒng)不會(huì)進(jìn)行插入或者刪除，并自動(dòng)返回原菜單。在有序合并的共能當(dāng)中，沒(méi)有按遞增序列輸入數(shù)字，合并后的鏈表也不會(huì)是有序的。第二章 概要設(shè)計(jì) 數(shù)據(jù)類型定義數(shù)據(jù)機(jī)構(gòu)演示系統(tǒng)1定義了五種存儲(chǔ)結(jié)構(gòu)，typedef int Status。是定義函數(shù)的返回值類型，也可以定義數(shù)據(jù)的類型，在數(shù)據(jù)有變動(dòng)時(shí)而算法不變時(shí)，只需要改變其中的“int”就可以。SqList是順序表的數(shù)據(jù)類型，其中包含三個(gè)成員，一個(gè)是ElemType的指針變量，第二個(gè)是表中元素的個(gè)數(shù)，第三個(gè)是表的當(dāng)前容量。第三個(gè)是上面提到的ElemType，主要表示各種元素的數(shù)據(jù)類型。第四個(gè)是typedef struct LNode{} *LinkList,這個(gè)是鏈表的元素類型，每次用鏈表都用這個(gè)來(lái)定義新結(jié)點(diǎn)。最后是typedef unsigned char SString[MAXSTRLEN +1]。這個(gè)是字符串?dāng)?shù)組，在模式匹配中用到。ElemTypetypedef int ElemType。typedef struct{ ElemType *elem。 int length。 int listsize。 }SqList。typedef unsigned char SString[MAXSTRLEN +1]。typedef struct LNode{ ElemType data。 struct LNode *next。}LNode,*LinkList。 順序表的各種抽象數(shù)據(jù)類型的定義如下 ADT list_Sq{數(shù)據(jù)對(duì)象：D={ai|ai∈ElemSet,i=1,2,…,n,n=0}數(shù)據(jù)關(guān)系：R1={ai1,ai|ai1,ai∈D,i=2,…,n}基本操作： Status InitList_Sq(SqList amp。L) 操作結(jié)果：構(gòu)造一個(gè)空的線性順序表L。 Status GetElem(SqList L,ElemType i,ElemType amp。e){ 初始條件：線性表L已存在，1=i=Listlength(L)。操作結(jié)果：把線性表L中的第i個(gè)元素傳遞給e。 Status ListInsert_Sq(SqList amp。L,int i,ElemType e) 初始條件：線性表L已存在，1=i=Listlength(L)+1。 操作結(jié)果：在順序表L中第i個(gè)位置之前插入新的元素e，L的長(zhǎng)度加1。 Status ListDelete_Sq(SqList amp。L,int i,ElemType amp。e) 初始條件：線性順序表L已存在且非空，i的合法值為1=i=。 操作結(jié)果：在順序線性表L中刪除第i個(gè)元素，并用e返回其值，L的長(zhǎng)度減1。 Status LocateElem_Sq(SqList L,ElemType e,Status (*pare)(ElemType, ElemType)) 初始條件：線性表L已存在，1=i=Listlength(L)。操作結(jié)果：在順序線性表中查找第一個(gè)與e值滿足pare關(guān)系的位序 若找到則返回其在L中的位序，否者返回0void print_Sq(SqList L)初始條件：線性表L已存在。 操作結(jié)果：打印順序表的全部元素。 void unionSq(SqList amp。La,SqList Lb)初始條件：：線性順序表La和Lb已存在且非空。 操作結(jié)果：將所有在線性表Lb中但不在La中的數(shù)據(jù)元素插入到La中. void MergeList(SqList La,SqList Lb,SqList amp。Lc){ 初始條件：已知線性表La和Lb已存在且非空，其中的數(shù)據(jù)元素按值非遞減排列 操作結(jié)果：歸并La和Lb得到新的線性表Lc,Lc的數(shù)據(jù)元素也按值非遞減排列。void print_Sq(SqList L)初始條件：線性表L已存在。 操作結(jié)果：打印順序表的全部元素。 Status pare(ElemType a1, ElemType a2) 操作結(jié)果：比較a1和a2的值，如果a1和a2相等，者返回1,否則返回0；} 鏈表的各種抽象數(shù)據(jù)類型定義如下：ADT list_L{數(shù)據(jù)對(duì)象：D={ai|ai∈ElemSet,i=1,2,…,n,n=0}數(shù)據(jù)關(guān)系：R1={ai1,ai|ai1,ai∈D,i=2,…,n}基本操作：void CreateList_L(LinkList amp。L,int n)操作結(jié)果：順位序輸入n個(gè)元素的值，建立帶頭結(jié)點(diǎn)的單鏈表L。void print_L(LinkList head)操作結(jié)果：在界面上打印head結(jié)點(diǎn)。 初始條件：?jiǎn)捂溇€性表L存在。 操作結(jié)果：返回單鏈線性表的長(zhǎng)度。Status ListInsert_L(LinkList amp。L,int i,ElemType e) 初始條件：?jiǎn)捂溇€性表L存在且不為空，1=i=Listlength(L)+1。操作結(jié)果：在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)位置之前插入元素e。Status ListDelete_L(LinkList amp。L, int i, ElemType amp。e) 初始條件：?jiǎn)捂溇€性表L存在，i的合法值為1=i=。 在帶頭結(jié)點(diǎn)的單鏈線性表L中，刪除第i個(gè)元素，并由e返回其值。int LocateElem_L(LinkList L,ElemType e)初始條件：?jiǎn)捂溇€性表L已存在且非空。 操作結(jié)果：在單鏈表L中從頭開始找第1個(gè)值域與e相等的節(jié)點(diǎn)，若存在這樣的節(jié)點(diǎn)，則返回位置，并打印該結(jié)點(diǎn)的值。Status GetElem_L(LinkList L,int i,ElemType amp。e) 初始條件： L為帶頭結(jié)點(diǎn)的單鏈表的頭指針，1=i=。 操作結(jié)果：當(dāng)?shù)趇個(gè)元素存在時(shí)，其值賦給e并返回OK，否者返回ERROR。 void MergeList_L(LinkList amp。La,LinkList amp。Lb,LinkList amp。Lc) 初始條件：?jiǎn)捂湵鞮a和Lb非空，且其中的元素按值非遞減排列。 操作結(jié)果：歸并La和Lb得到新單鏈表Lc，Lc的元素也按值非遞減排列。 Status pare(ElemType a1, ElemType a2) 操作結(jié)果：比較a1和a2的值，如果a1和a2相等，者返回1,否則返回0；}串的抽象數(shù)據(jù)類型的定義如下：ADT String{ 數(shù)據(jù)對(duì)象：D={ai|ai∈ElemSet,i=1,2,…,n,n=0}數(shù)據(jù)關(guān)系：R1={ai1,ai|ai1,ai∈D,i=2,…,n}基本操作：void get_next(SString T,int next[])操作結(jié)果：求模式串T的next函數(shù)值并存入數(shù)組next.。 void get_nextval(SString T,int nextval[]) 初始條件：T非空。操作結(jié)果：求模式串T的next函數(shù)修正值并存入數(shù)組nextval。 int Index_KMP(SString S,SString T,int amp。pos, int nextval[])初始條件：T非空，1=pos=StrLength(S)。操作結(jié)果：利用模式串T的next函數(shù)求T在主串中第pos個(gè)字符之后的位置的KMP算法。} 各個(gè)函數(shù)的調(diào)用關(guān)系各個(gè)函數(shù)的調(diào)用關(guān)系：main()調(diào)用SqListfun()，LinkListfun()，Index_SS()。SqListfun()調(diào)用InitList_Sq(amp。L), List