東華大學(xué)2013數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

1、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-個(gè)人設(shè)計(jì)報(bào)告專 業(yè)：班 級(jí)：姓 名：學(xué) 號(hào)：指導(dǎo)教師：日 期： 目錄1 課程設(shè)計(jì)目的32 課程設(shè)計(jì)內(nèi)容和要求33 任務(wù)完成情況34 設(shè)計(jì)報(bào)告44.1順序表44.1.1 設(shè)計(jì)目的44.1.2 設(shè)計(jì)內(nèi)容及要求44.1.3 需求分析44.1.4 概要設(shè)計(jì)54.1.5 詳細(xì)代碼64.1.6 使用說明64.1.7 測(cè)試結(jié)果與分析74.1.8 參考文獻(xiàn)104.2鏈表114.2.1 設(shè)計(jì)目的114.2.2 設(shè)計(jì)內(nèi)容及要求114.2.3 需求分析114.2.4 概要設(shè)計(jì)114.2.5 詳細(xì)代碼114.2.6 使用說明114.2.7 測(cè)試結(jié)果與分析114.2.8 參考文獻(xiàn)114.3樹和二叉樹

2、124.3.1 設(shè)計(jì)目的124.3.2 設(shè)計(jì)內(nèi)容及要求124.3.3 需求分析124.3.5 詳細(xì)代碼124.3.6 使用說明124.3.7 測(cè)試結(jié)果與分析124.3.8 參考文獻(xiàn)125 體會(huì)與感想13附錄：14設(shè)計(jì)一（順序表）的代碼14設(shè)計(jì)二（鏈表）的代碼17設(shè)計(jì)三（樹和二叉樹）的代碼171 課程設(shè)計(jì)目的1、 學(xué)習(xí)獲取知識(shí)的方法；2、 提高發(fā)現(xiàn)問題、分析問題和解決實(shí)際問題的能力；3、 加強(qiáng)創(chuàng)新意識(shí)和創(chuàng)新精神；4、 加強(qiáng)團(tuán)隊(duì)的分工與合作；5、 掌握面向?qū)嶋H背景思考問題的方法。2 課程設(shè)計(jì)內(nèi)容和要求內(nèi)容：前言第一章 順序表第二章 鏈表第三章 樹和二叉樹個(gè)人基本任務(wù)：完成第1,2,3章，其中選做題

3、可不做。3 任務(wù)完成情況任務(wù)完成情況介紹，如表3-1.表3-1 任務(wù)完成情況表完成任務(wù)名稱順序表鏈表樹和二叉樹4 設(shè)計(jì)報(bào)告4.1 順序表4.1.1 設(shè)計(jì)目的熟悉順序表的應(yīng)用4.1.2 設(shè)計(jì)內(nèi)容及要求本程序用C語言編寫，完成以下功能：1）實(shí)現(xiàn)二路歸并排序算法。2）實(shí)現(xiàn)快速排序算法。3）實(shí)現(xiàn)堆排序算法。4）實(shí)現(xiàn)冒泡排序和選擇排序算法5）刪除線性表中所有值為item的數(shù)據(jù)元素6）五種排序方法性能測(cè)試 4.1.3 需求分析本程序用C編寫，完成5種排序和性能測(cè)試，刪除線性表中所有值為item的數(shù)據(jù)元素等功能，并且需要一個(gè)菜單讓用戶自主選擇執(zhí)行的功能。 輸入的形式和輸入值的范圍：輸入的元素是整形，輸入值的

4、范圍是0-9，輸入-1結(jié)束。 輸出的形式：在每次選擇菜單后，輸出相應(yīng)的結(jié)果，并且詢問下次操作的項(xiàng)目。 程序所能達(dá)到的功能：完成5種排序和性能測(cè)試，刪除線性表中所有值為item的數(shù)據(jù)元素。每次操作結(jié)束后，都會(huì)有菜單方便用戶進(jìn)行下一步的操作。 測(cè)試數(shù)據(jù)：A菜單顯示為：請(qǐng)輸入您要測(cè)試的項(xiàng)目：1順序存儲(chǔ)的線性表5種排序算法 選擇 1 顯示 請(qǐng)輸入元素個(gè)數(shù) 輸入 整數(shù) 輸出 5種排序方法排序后的元素2刪除線性表中所有值為item的數(shù)據(jù)元素 選擇 2 顯示 請(qǐng)輸入元素個(gè)數(shù) 輸入 整數(shù) 顯示 依次輸入元素，按空格分開 輸入 整數(shù) 顯示 請(qǐng)輸入item的值（整數(shù)） 輸入 整數(shù) 輸出 剩下的元素3性能測(cè)試 選擇

5、 3 輸出 5種排序（有序/隨機(jī)元素）的時(shí)間0退出管理系統(tǒng) 選擇 0 退出當(dāng)前程序4.1.4 概要設(shè)計(jì)1） 為了實(shí)現(xiàn)上述程序功能，需要定義順序表的抽象數(shù)據(jù)類型：typedef struct listint key;/關(guān)鍵字項(xiàng) RedType;/記錄類型 typedef structRedType rMAXSIZE;/r0閑置或用作哨兵單元 int length; /順序表長度，參加排序元素的實(shí)際個(gè)數(shù)SqList;/順序表類型2） 本程序包含16個(gè)函數(shù)： void InitialRandom(SqList *L)ContactList void Initial(SqList *L) void M

6、erge(RedType SR, RedType TR,int i,int m,int n) void Msort(RedType SR ,RedType TR1 ,int s ,int t) void Mergesort(SqList *L ) void choice(SqList *L) void bubble(SqList *L) void quicksort(SqList *L,int start,int end) void Heapsort(SqList *L) void HeapAdjust(SqList *L,int s,int m) void out(SqList *L) in

7、t Delete(SqList *L, int item) void OrderInitial(SqList *L) void InOrderInitial(SqList *L) void Performance() int main()4.1.5 詳細(xì)代碼見附錄一4.1.6 使用說明程序執(zhí)行后出現(xiàn)如圖4.1-2的菜單：圖4.1-2 菜單菜單共有四個(gè)選項(xiàng)，選擇不同的選項(xiàng)會(huì)出現(xiàn)相應(yīng)的提示進(jìn)行下一步操作：選擇1：順序存儲(chǔ)的線性表5種排序算法選擇2：刪除線性表中所有值為item的數(shù)據(jù)元素選擇3：性能測(cè)試選擇0：退出4.1.7 測(cè)試結(jié)果與分析1 順序存儲(chǔ)的線性表5種排序算法，如圖4.1-3：圖4.1-

8、3 實(shí)驗(yàn)結(jié)果：生成隨機(jī)數(shù)，用5種方法從小到大排序2 刪除線性表中所有值為item的數(shù)據(jù)元素，如圖4.1-4：圖4.1-4 刪除元素實(shí)驗(yàn)結(jié)果：分三類討論，分別是刪除第一個(gè)，最后一個(gè)，當(dāng)中元素3 性能測(cè)試，如圖4.1-5：如圖4.1-5 一萬元素性能測(cè)試如圖4.1-6 五十萬元素性能測(cè)試實(shí)驗(yàn)結(jié)果：分別生成有序和無需的元素，用5種排序方法分別排序，并輸出時(shí)間注意：VS6.0中10萬元素以上就會(huì)溢出，特別是快速排序只能在1萬元素時(shí)實(shí)現(xiàn)，否則棧會(huì)溢出，故在50萬測(cè)試時(shí)把快速排序的函數(shù)用“/”注釋掉，因此時(shí)間為0。4 輸入0退出4.1.8 參考文獻(xiàn)1 嚴(yán)蔚敏等著， 數(shù)據(jù)結(jié)構(gòu)（C語言版）， 清華大學(xué)出版社2

9、 高一凡著， 數(shù)據(jù)結(jié)構(gòu)算法解析， 清華大學(xué)出版社4.2鏈表的應(yīng)用4.2.1 設(shè)計(jì)目的熟悉鏈表的應(yīng)用4.2.2 設(shè)計(jì)內(nèi)容及要求本程序用C語言編寫，完成以下功能：1）刪除元素使兩個(gè)鏈表相等。2）猴子選大王。3）非循環(huán)雙向鏈表按頻度排序。4）稀疏矩陣的存儲(chǔ)4.2.3 需求分析本程序用C編寫，完成4種鏈表功能，并且需要一個(gè)菜單讓用戶自主選擇執(zhí)行的功能。 輸入的形式和輸入值的范圍：輸入的元素是整形，輸入值的范圍是0-9，輸入-1結(jié)束。 輸出的形式：在每次選擇菜單后，輸出相應(yīng)的結(jié)果，并且詢問下次操作的項(xiàng)目。 程序所能達(dá)到的功能：完成4種鏈表功能。每次操作結(jié)束后，都會(huì)有菜單方便用戶進(jìn)行下一步的操作。 測(cè)試數(shù)

10、據(jù)：A菜單顯示為：請(qǐng)輸入您要測(cè)試的項(xiàng)目：1順序存儲(chǔ)的線性表5種排序算法 選擇 1 顯示 創(chuàng)建鏈表A/B,請(qǐng)將遞增輸入整數(shù)，用空格分開，輸入-1結(jié)束 輸入 整數(shù). -1 顯示 刪除元素后A,B鏈表為: 輸出 A,B中的元素2猴子選大王 選擇 2 顯示 請(qǐng)輸入猴子總數(shù)n 輸入 整數(shù) 顯示 請(qǐng)輸入出局猴子報(bào)的數(shù)m(mn) 輸入 整數(shù) 輸出 i號(hào)猴子為大王3非循環(huán)雙向鏈表按頻度排序 選擇 3 顯示 請(qǐng)輸入元素值(1-10整數(shù))，用空格分開,-1表示結(jié)束 輸入 整數(shù). -1 顯示 隨機(jī)訪問10次元素，令元素freq加1并，使此鏈表中結(jié)點(diǎn)保持按訪問頻度遞減的順序排列，隨機(jī)訪問的元素為 輸出 按freq排序

11、后的元素4稀疏矩陣的存儲(chǔ) 選擇 4 顯示 請(qǐng)輸入矩陣的總行數(shù)，總列數(shù)，用空格分開,行與列從0記起 輸入 a b (整數(shù)) 顯示 建立第一/二個(gè)矩陣 輸入 例如 輸出 輸出第一/二個(gè)矩陣 輸出 輸出相加后的矩陣0退出管理系統(tǒng) 選擇 0 退出當(dāng)前程序4.2.4 概要設(shè)計(jì)1）為了實(shí)現(xiàn)上述程序功能，需要定義鏈表的抽象數(shù)據(jù)類型：/這是單鏈表 typedef struct LNodeint data;struct LNode* next;LNode,*LinkList;/雙向鏈表 typedef struct DuLNodeint data,freq;/freq是頻率 struct DuLNode *pr

12、ev,*next;/前后兩個(gè)指針DuLNode,*DuLinkList;/矩陣結(jié)點(diǎn) typedef struct MatrixNodeint row,column,data;/行 列 數(shù)值 struct MatrixNode *next;MatrixNode,*MatrixList;2）本程序包含17個(gè)函數(shù)： void Initial(LinkList &L)/建立鏈表 int not_in_L(int m,LinkList L)/判斷元素是否在L中 void del(LinkList L1,LinkList L2)/對(duì)L1操作，刪除在L1中而不在L2中的元素void output(LinkL

13、ist L)/輸出鏈表void fun1() void Monkey()/猴子選大王 void fun2() void InitDuList(DuLinkList &L)/創(chuàng)建有表頭結(jié)點(diǎn)的雙向鏈表 DuLNode* Locate(DuLNode*L,int x)/在L中找到值為x的節(jié)點(diǎn)，freq值加一，返回找到結(jié)點(diǎn)的地址，類型為指針型/對(duì)p所指結(jié)點(diǎn)進(jìn)行插入，使鏈表中結(jié)點(diǎn)保持按訪問頻度遞減排列void OutputDuLink(DuLinkList L)輸出雙向鏈表 void fun3() void InitMatrix(MatrixList &L)/創(chuàng)建稀疏矩陣 int FindData(Ma

14、trixList L,int a,int b)/返回矩陣L的a行b列的值 void AddMatrix(MatrixList A,MatrixList B,MatrixList &C,int hang,int lie)/矩陣C=A+B void MatrixOutput(MatrixList L,int hang,int lie)/輸出矩陣 void fun4() int main()4.2.5 詳細(xì)代碼見附錄二4.2.6 使用說明程序執(zhí)行后出現(xiàn)如圖4.2-2的菜單：圖4.2-2 菜單菜單共有五個(gè)選項(xiàng)，選擇不同的選項(xiàng)會(huì)出現(xiàn)相應(yīng)的提示進(jìn)行下一步操作：選擇1：刪除元素使兩個(gè)鏈表相等選擇2：猴子選大

15、王選擇3：非循環(huán)雙向鏈表按頻度排序選擇4：稀疏矩陣的存儲(chǔ)選擇0：退出4.2.7 測(cè)試結(jié)果與分析1 刪除元素使兩個(gè)鏈表相等，如圖4.2-3：圖4.2-3 實(shí)驗(yàn)結(jié)果：輸出刪除元素后的A,B鏈表，若有相同的元素則保留2 猴子選大王，如圖4.2-4：圖4.2-4 刪除元素實(shí)驗(yàn)結(jié)果：輸出幾號(hào)猴子是大王3 非循環(huán)雙向鏈表按頻度排序，如圖4.2-5：圖4.2-5 實(shí)驗(yàn)結(jié)果：隨機(jī)訪問鏈表10次，按照頻度由大到小排列輸出4 稀疏矩陣的存儲(chǔ)，如圖4.2-6輸入數(shù)據(jù)： + = 圖4.2-6實(shí)驗(yàn)結(jié)果：輸出相加后的矩陣5 輸入0退出4.2.8 參考文獻(xiàn)1 嚴(yán)蔚敏等著， 數(shù)據(jù)結(jié)構(gòu)（C語言版）， 清華大學(xué)出版社2 高一凡著

16、， 數(shù)據(jù)結(jié)構(gòu)算法解析， 清華大學(xué)出版社4.3 樹與二叉樹 4.3.1 設(shè)計(jì)目的熟悉二叉樹的應(yīng)用4.3.2 設(shè)計(jì)內(nèi)容及要求本程序用C語言編寫，完成以下功能：1）輸入字符序列，建立二叉鏈表，中序遍歷二叉樹輸出。2）二叉樹的葉子結(jié)點(diǎn)按從左到右的順序連成一個(gè)單鏈表3）判斷某二叉樹是否是完全二叉樹。4）判斷某二叉樹是否是二叉排序樹4.3.3 需求分析本程序用C編寫，完成4種二叉樹功能，并且需要一個(gè)菜單讓用戶自主選擇執(zhí)行的功能。 輸入的形式和輸入值的范圍：輸入的元素是整形，輸入值的范圍是一位整數(shù)，輸入空格開標(biāo)節(jié)點(diǎn)為空。 輸出的形式：在每次選擇菜單后，輸出相應(yīng)的結(jié)果，并且詢問下次操作的項(xiàng)目。 程序所能達(dá)到的

17、功能：完成4種二叉樹功能。每次操作結(jié)束后，都會(huì)有菜單方便用戶進(jìn)行下一步的操作。 測(cè)試數(shù)據(jù)：A菜單顯示為：請(qǐng)輸入您要測(cè)試的項(xiàng)目：1輸入字符序列，建立二叉鏈表，中序遍歷二叉樹輸出 選擇 1 顯示 請(qǐng)依次先序輸入，兩個(gè)元素之間不需要空格，結(jié)點(diǎn)為空輸入空格，按回車結(jié)束 輸入 例如：123 4 5 回車 輸出 中序遍歷輸出二叉樹2二叉樹的葉子結(jié)點(diǎn)按從左到右的順序連成一個(gè)單鏈表 選擇 2 顯示 請(qǐng)依次先序輸入，兩個(gè)元素之間不需要空格，結(jié)點(diǎn)為空輸入空格，按回車結(jié)束 輸入 例如：123 4 5 回車 輸出 先序遍歷葉子節(jié)點(diǎn)，鏈表輸出葉子節(jié)點(diǎn)3判斷某二叉樹是否是完全二叉樹 選擇 3 顯示 請(qǐng)依次先序輸入，兩個(gè)元

18、素之間不需要空格，結(jié)點(diǎn)為空輸入空格，按回車結(jié)束 輸入 例如：123 4 5 回車 輸出 是否是完全二叉樹4判斷某二叉樹是否是二叉排序樹 選擇 4 顯示 請(qǐng)依次先序輸入，兩個(gè)元素之間需要空格，結(jié)點(diǎn)為空輸入0，按回車結(jié)束 輸入 例如：1 2 3 0 0 4 0 0 5 0 0 回車 輸出 是否是二叉排序0退出管理系統(tǒng) 選擇 0 退出當(dāng)前程序4.3.4 概要設(shè)計(jì)1）為了實(shí)現(xiàn)上述程序功能，需要定義鏈表的抽象數(shù)據(jù)類型：/data是char類型的二叉樹 typedef struct BiTNodechar data;struct BiTNode * lchild,*rchild;BiTNode,*BiTr

19、ee;/data是int類型的二叉樹 typedef struct BiTNode2int data;struct BiTNode2 * lchild,*rchild;BiTNode2,*BiTree2;2）本程序包含13個(gè)函數(shù)/創(chuàng)建 data是char類型的二叉樹 void CreateBiTree(BiTree & T) / 創(chuàng)建 data是int類型的二叉樹 void CreateBiTree2(BiTree2 &T)/中序遍歷 void InOrder(BiTree T)/把二叉樹的葉子結(jié)點(diǎn)按從左到右的順序連成一個(gè)單鏈表，表頭指針為head void LeafLinkList(BiTr

20、ee T)/先序遍歷葉子結(jié)點(diǎn) void PreOrderLeaf(BiTree T)/判斷是否是完全二叉樹 層次遍歷二叉樹 返回 是true，否false int CompleteBiTree(BiTree T)/int型中序遍歷2 void InOrder2(BiTree2 T)/判斷是否是二叉排序樹 返回 是true，否false /二叉排序樹的中序遍歷是有序遞增的 int SortTree()void fun1()void fun2()void fun3()void fun4()int main() 4.3.5 詳細(xì)代碼見附錄三4.3.6 使用說明程序執(zhí)行后出現(xiàn)如圖4.2-2的菜單：圖4

21、.32 菜單菜單共有五個(gè)選項(xiàng)，選擇不同的選項(xiàng)會(huì)出現(xiàn)相應(yīng)的提示進(jìn)行下一步操作：選擇1：輸入字符序列，建立二叉鏈表，中序遍歷二叉樹輸出選擇2：二叉樹的葉子結(jié)點(diǎn)按從左到右的順序連成一個(gè)單鏈表選擇3：判斷某二叉樹是否是完全二叉樹選擇4：判斷某二叉樹是否是二叉排序樹選擇0：退出4.3.7 測(cè)試結(jié)果與分析1 輸入字符序列，建立二叉鏈表，中序遍歷二叉樹輸出，如圖4.33：測(cè)試數(shù)據(jù)為：圖4.33 實(shí)驗(yàn)結(jié)果：中序遍歷輸出二叉樹2 二叉樹的葉子結(jié)點(diǎn)按從左到右的順序連成一個(gè)單鏈表，如圖4.4：圖4.34 實(shí)驗(yàn)結(jié)果：先序遍歷葉子節(jié)點(diǎn)，鏈表輸出葉子節(jié)點(diǎn)3 判斷某二叉樹是否是完全二叉樹，如圖4.35：測(cè)試數(shù)據(jù)：圖4.35

22、實(shí)驗(yàn)結(jié)果：第一棵樹是完全二叉樹，第二棵不是。4 判斷某二叉樹是否是二叉排序樹，如圖4.36測(cè)試數(shù)據(jù)： 圖4.36實(shí)驗(yàn)結(jié)果：第一棵樹是二叉排序樹，第二棵不是5 輸入0退出4.3.8 參考文獻(xiàn)1 嚴(yán)蔚敏等著， 數(shù)據(jù)結(jié)構(gòu)（C語言版）， 清華大學(xué)出版社2 高一凡著， 數(shù)據(jù)結(jié)構(gòu)算法解析， 清華大學(xué)出版社5 體會(huì)與感想經(jīng)過這次實(shí)驗(yàn)，我對(duì)數(shù)據(jù)結(jié)構(gòu)中的順序表，鏈表，二叉樹有了進(jìn)一步的認(rèn)識(shí)。對(duì)于實(shí)現(xiàn)算法我總結(jié)出以下幾點(diǎn)： 1. 問題是否是已經(jīng)學(xué)過的數(shù)據(jù)結(jié)構(gòu)，如果不是，就閱讀相關(guān)參考書，并加以自己的思考。2. 在測(cè)試數(shù)據(jù)是要注意分類討論，考慮問題必須全面。例如：刪除鏈表節(jié)點(diǎn)時(shí)，要考慮刪除的元素位于鏈表中的第一個(gè)，

23、最后一個(gè)，中間，刪除后鏈表為空，鏈表本來為空，這5中情況進(jìn)行測(cè)試。3.在實(shí)現(xiàn)代碼編譯正確的同時(shí)，要注重代碼的質(zhì)量，其中包括代碼實(shí)際的模塊化，代碼的風(fēng)格（上下括號(hào)要匹配），測(cè)試代碼要全面，沒有漏洞。 4.在實(shí)現(xiàn)線性表第三個(gè)函數(shù)：“分別生成有序和無需的元素，用5種排序方法分別排序，并輸出時(shí)間時(shí)” 快速排序會(huì)出現(xiàn)一些問題。VS6.0中10萬元素以上就會(huì)報(bào)錯(cuò)，特別是快速排序只能在1萬元素時(shí)實(shí)現(xiàn)，否則棧會(huì)溢出，故在50萬測(cè)試時(shí)把快速排序的函數(shù)用“/”注釋掉，因此時(shí)間為0。因此本實(shí)驗(yàn)中就用1萬元素進(jìn)行實(shí)驗(yàn)。5. 碰到一道題目如果沒有思路時(shí)，可以先在紙上畫出流程圖，寫出算法的分析，把題目的結(jié)果推算出來（例如

24、畫出完全二叉樹、二叉排序樹，寫出中序遍歷和先序遍歷），這樣可以使自己的變成思路變得清晰、明了。對(duì)于解決復(fù)雜的問題有幫助。對(duì)于算法的實(shí)現(xiàn)，盡量保證程序執(zhí)行的高效率，盡量做到程序代碼結(jié)構(gòu)清晰，可讀性良好，針對(duì)輸入的數(shù)據(jù)進(jìn)行多方面的分類討論，程序的適應(yīng)性良好。操作界面加入提示，做到人性化。為了實(shí)現(xiàn)這幾個(gè)算法，經(jīng)過思考后，我參考了書上的算法，并參考了一些課外資料，并加以自己的算法優(yōu)化。今后爭(zhēng)取提高編程的速度與正確率，并進(jìn)一步思考更有難度的代碼。附錄：設(shè)計(jì)一的代碼#include #include#include#includeusing namespace std;#define MAXSIZE 10

25、000 /50萬 (vs6.0中10萬以上就會(huì)報(bào)錯(cuò))/結(jié)構(gòu)體typedef struct listint key;/關(guān)鍵字項(xiàng) RedType;/記錄類型 typedef structRedType rMAXSIZE;/r0閑置或用作哨兵單元 int length; /順序表長度，參加排序元素的實(shí)際個(gè)數(shù)SqList;/順序表類型 void InitialRandom(SqList *L) int i;cout請(qǐng)輸入元素個(gè)數(shù)L-length;srand(unsigned)time(NULL); cout隨機(jī)生成數(shù)字endl;for(i=0;ilength;i+) L-ri.key=rand()%1

26、00;coutri.key ;coutendl;void Initial(SqList *L) int i;cout請(qǐng)輸入元素個(gè)數(shù)L-length;cout依次輸入元素，按空格分開endl;for(i=0;ilength;i+)cinL-ri.key;void Merge(RedType SR, RedType TR,int i,int m,int n)/將有序的SRi.m和SRm+1.n由小到大合并成有序表TRi.n /i開始。m中間。n結(jié)尾 int j,k,p,q;k=i;j=m+1;p=i; /將較小的放入TR中，i,j是指針，i指向開頭，j指向中間 while( i=m & j=n)

27、if(SRi.keySRj.key)TRk+.key=SRi+.key;elseTRk+.key=SRj+.key; while( i=m )TRk+=SRi+;/將剩余的SRi.m復(fù)制到TR while( j=n )TRk+.key=SRj+.key;/將剩余的SRj.m復(fù)制到TR for(q=p; qlength; RedType *b=new RedTypen;Msort( L-r, b , 0 , n-1 );/a歸并到b /選擇排序void choice(SqList *L)int i,j,k;int temp;for(i=0;ilength;i+)k=i;for(j=i+1;jle

28、ngth;j+)if(L-rj.keyrk.key)k=j;if(i!=k)/第i個(gè)元素與第k個(gè)元素交換temp=L-ri.key;L-ri.key=L-rk.key;L-rk.key=temp;/冒泡排序void bubble(SqList *L)int i,j,temp;for(i=0;ilength;i+)for(j=L-length-1;ji;j-)if(L-ri.keyL-rj.key)temp=L-ri.key;L-ri.key=L-rj.key;L-rj.key=temp;/快速排序算法void quicksort(SqList *L,int start,int end)int

29、i,j;int mid;if(start=end)return;i=start;j=end;mid=L-ri.key;while(ij)while(irj.keymid)/找到比mid小的數(shù)j-;if(iri.key=L-rj.key;i+;while(iri.key=mid)/找到比mid大的數(shù)i+;if(irj.key=L-ri.key;j-;L-ri.key=mid;/一次劃分得到基準(zhǔn)值的正確位置quicksort(L,start,i-1);/遞歸調(diào)用左子區(qū)間quicksort(L,i+1,end);/遞歸調(diào)用右子區(qū)間/堆排序算法void Heapsort(SqList *L)void

30、HeapAdjust(SqList *L,int s,int m);/函數(shù)申明int temp;/臨時(shí)變量 int i;/forfor(i=L-length/2;i=0;-i)HeapAdjust(L,i,L-length-1);for(i=L-length-1;i0;-i)temp=L-r0.key;L-r0.key=L-ri.key;L-ri.key=temp;HeapAdjust(L,0,i-1);/單個(gè)結(jié)點(diǎn)調(diào)整void HeapAdjust(SqList *L,int s,int m)int j;int temp=L-rs.key;for(j=2*s;j=m;j*=2)if(jrj.k

31、eyrj+1.key)+j;if(temp=L-rj.key)break;L-rs.key=L-rj.key;s=j;L-rs.key=temp;void out(SqList *L)/cout遍歷輸出endl;for(int i=0;ilength;i+)/遍歷輸出coutri.key ;coutlength-1; /設(shè)立數(shù)組頭尾指針 while(iri.key!=item) i+; /若值不為item，頭指針右移 if(L-rj.key=item) j-;/若數(shù)組尾值為item,尾指針左移 if(L-ri.key=item&L-rj.key!=item) L-ri+.key=L-rj-.k

32、ey;/用末尾元素代替item if(j=0)/表為空時(shí)的情況 cout表為空nlength=j+1; out(L); return (1); void OrderInitial(SqList *L) /生成50萬有序的數(shù)字 int i;L-length=MAXSIZE;for(i=0;ilength;i+)L-ri.key=i;void InOrderInitial(SqList *L) /生成50萬隨機(jī)的數(shù)字 int i;srand(unsigned)time(NULL); L-length=MAXSIZE;for(i=0;ilength;i+)L-ri.key=rand()%100;vo

33、id Performance()SqList L;clock_t start,finish;double time; cout元素個(gè)數(shù)MAXSIZEendl;/二路歸并 OrderInitial(&L); /out(&L);start=clock();Mergesort(&L);finish=clock();cout二路歸并 有序(double)(finish-start)/CLK_TCKsendl;InOrderInitial(&L);start=clock();Mergesort(&L);finish=clock();cout二路歸并 無序(double)(finish-start)/CL

34、K_TCKsendl;/快速排序 OrderInitial(&L); /out(&L);start=clock();quicksort(&L,0,L.length-1);finish=clock();cout快速排序 有序(double)(finish-start)/CLK_TCKsendl;InOrderInitial(&L);/warning:此處快速排序無序元素時(shí)可能造成崩潰 start=clock();quicksort(&L,0,L.length-1);/here finish=clock();cout快速排序 無序(double)(finish-start)/CLK_TCKsend

35、l;/堆排序 OrderInitial(&L); /out(&L);start=clock();Heapsort(&L);finish=clock();cout堆排序 有序(double)(finish-start)/CLK_TCKsendl;InOrderInitial(&L);start=clock();Heapsort(&L);finish=clock();cout堆排序 無序(double)(finish-start)/CLK_TCKsendl;/冒泡排序OrderInitial(&L); /out(&L);start=clock();bubble(&L);finish=clock()

36、;cout冒泡排序 有序(double)(finish-start)/CLK_TCKsendl;InOrderInitial(&L);start=clock();bubble(&L);finish=clock();cout冒泡排序 無序(double)(finish-start)/CLK_TCKsendl;/選擇排序OrderInitial(&L); /out(&L);start=clock();choice(&L);finish=clock();cout選擇排序 有序(double)(finish-start)/CLK_TCKsendl;InOrderInitial(&L);start=cl

37、ock();choice(&L);finish=clock();cout選擇排序 無序(double)(finish-start)/CLK_TCKsendl;int main()int a;int item;SqList L; cout 1、順序表的應(yīng)用endl;cout*endl;cout 1.順序存儲(chǔ)的線性表5種排序算法endl;cout 2.刪除線性表中所有值為item的數(shù)據(jù)元素endl;cout 3.性能測(cè)試endl;cout 0.退出endl;cout*endl;while(1)cout請(qǐng)選擇:a;switch(a)case 0:return 0;case 1:InitialRand

38、om(&L);cout二路歸并排序算法endl;Mergesort(&L);out(&L);cout快速排序算法endl;quicksort(&L,0,L.length-1);out(&L);cout堆排序算法endl;Heapsort(&L);out(&L);cout冒泡排序算法endl;bubble(&L);out(&L);cout選擇排序算法endl;choice(&L);out(&L);break;case 2: Initial(&L); cout請(qǐng)輸入item的值（整數(shù)）item; Delete(&L,item); break;case 3: Performance(); break

39、; 設(shè)計(jì)二的代碼#include#include#include#includeusing namespace std;/這是單鏈表 typedef struct LNodeint data;struct LNode* next;LNode,*LinkList;/雙向鏈表 typedef struct DuLNodeint data,freq;/freq是頻率 struct DuLNode *prev,*next;/前后兩個(gè)指針DuLNode,*DuLinkList;/矩陣結(jié)點(diǎn) typedef struct MatrixNodeint row,column,data;/行 列 數(shù)值 struc

40、t MatrixNode *next;MatrixNode,*MatrixList;/建立鏈表 void Initial(LinkList &L)coutx;if(x=-1) break;p-next=new LNode;p=p-next;p-data=x;p-next=NULL; /判斷元素是否在L中int not_in_L(int m,LinkList L) /元素在L中返回0，不再L中返回1 LNode*p;for(p=L-next;p!=NULL;p=p-next) if(m=p-data) /找到 return 0; return 1;/對(duì)L1操作，刪除在L1中而不在L2中的元素 v

41、oid del(LinkList L1,LinkList L2)LNode *p=L1;while(p-next!=NULL) if(not_in_L(p-next-data,L2)/在L1不在L2里 p-next=p-next-next;/刪除元素 else p=p-next; /輸出鏈表void output(LinkList L)LNode *p;p=L-next;while(p)coutdatanext; coutendl;void fun1() LinkList A,B; cout創(chuàng)建鏈表A:endl; Initial(A);cout創(chuàng)建鏈表B:endl;Initial(B);del(A,B);del(B,A);cout刪除元素后A,B鏈表為:next=NULL;L-data=1; LNode *p=L; cout請(qǐng)輸入猴子總數(shù)nn;cout請(qǐng)輸入出局猴子報(bào)的數(shù)m(mn)m;/建立循環(huán)鏈表，開始時(shí)，頭結(jié)點(diǎn)指向其自身/沒有頭節(jié)點(diǎn)，建立頭指針和尾指針 for