數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書(shū)重要參考(共35頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上前 言數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)相關(guān)專業(yè)的一門(mén)核心基礎(chǔ)課程，也是很多高?？佳袑I(yè)課之一。它主要介紹線性結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)、圖狀結(jié)構(gòu)三種邏輯結(jié)構(gòu)元素的存儲(chǔ)實(shí)現(xiàn)，在此基礎(chǔ)上介紹一些典型算法效率分析。這門(mén)課程的主要任務(wù)是培養(yǎng)學(xué)生的算法設(shè)計(jì)能力及良好的程序設(shè)計(jì)習(xí)慣。通過(guò)學(xué)習(xí)，要求學(xué)生能夠掌握典型算法的設(shè)計(jì)思想及程序?qū)崿F(xiàn)，能夠根據(jù)實(shí)際問(wèn)題選取合適的存儲(chǔ)方案設(shè)計(jì)出簡(jiǎn)潔、高效、實(shí)用的算法，為后續(xù)課程的學(xué)習(xí)及軟件開(kāi)發(fā)打下良好的基礎(chǔ)。學(xué)習(xí)這門(mén)課程，習(xí)題和實(shí)驗(yàn)是兩個(gè)關(guān)鍵環(huán)節(jié)。學(xué)生理解算法，上機(jī)實(shí)驗(yàn)是最佳的途徑之一。因此，實(shí)驗(yàn)環(huán)節(jié)的好壞是學(xué)生能否學(xué)好數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵。為了更好地配合學(xué)生實(shí)驗(yàn)，特編寫(xiě)試驗(yàn)指導(dǎo)

2、書(shū)；同時(shí)，為每個(gè)主要的知識(shí)點(diǎn)配有精選的典型習(xí)題。希望學(xué)生對(duì)習(xí)題要注意理解。一、實(shí)驗(yàn)?zāi)康?更好的理解算法的思想、培養(yǎng)編程能力。二、實(shí)驗(yàn)要求1. 每次實(shí)驗(yàn)前學(xué)生必須根據(jù)試驗(yàn)內(nèi)容認(rèn)真準(zhǔn)備實(shí)驗(yàn)程序及調(diào)試時(shí)所需的輸入數(shù)據(jù)。2. 在指導(dǎo)教師的幫助下能夠完成實(shí)驗(yàn)內(nèi)容，得出正確的實(shí)驗(yàn)結(jié)果。3. 實(shí)驗(yàn)結(jié)束后總結(jié)實(shí)驗(yàn)內(nèi)容、書(shū)寫(xiě)實(shí)驗(yàn)報(bào)告。4. 遵守實(shí)驗(yàn)室規(guī)章制度、不缺席、按時(shí)上、下機(jī)。5. 實(shí)驗(yàn)學(xué)時(shí)內(nèi)必須做數(shù)據(jù)結(jié)構(gòu)的有關(guān)內(nèi)容，不允許上網(wǎng)聊天或玩游戲，如發(fā)現(xiàn)上述現(xiàn)象，取消本次上機(jī)資格，平時(shí)成績(jī)扣10分。6. 實(shí)驗(yàn)報(bào)告有一次不合格，扣5分，兩次以上不合格者，平時(shí)成績(jī)以零分記。三、實(shí)驗(yàn)環(huán)境 Turbo C或VC+6.0四

3、、說(shuō)明1. 本實(shí)驗(yàn)的所有算法中元素類型可以根據(jù)實(shí)際需要選擇。2. 實(shí)驗(yàn)題目中帶者為較高要求，學(xué)生可自選；其余部分為基本內(nèi)容，應(yīng)盡量完成（至少完成70%，否則實(shí)驗(yàn)不合格）。3. 數(shù)據(jù)結(jié)構(gòu)是很多高校的碩士研究生入學(xué)考試的專業(yè)課之一，希望有志于考研的學(xué)生能夠在學(xué)習(xí)過(guò)程中注意各種算法的理解，以便為考研做一定的準(zhǔn)備。五、實(shí)驗(yàn)報(bào)告的書(shū)寫(xiě)要求1. 明確實(shí)驗(yàn)的目的及要求;2. 記錄實(shí)驗(yàn)的輸入數(shù)據(jù)和輸出結(jié)果;3. 說(shuō)明實(shí)驗(yàn)中出現(xiàn)的問(wèn)題和解決過(guò)程;4. 寫(xiě)出實(shí)驗(yàn)的體會(huì)和實(shí)驗(yàn)過(guò)程中沒(méi)能解決的問(wèn)題;六、成績(jī)考評(píng)辦法1 期末考試占80分，閉卷。2 平時(shí)考評(píng)占20分。其中實(shí)驗(yàn)環(huán)節(jié)占15分（實(shí)驗(yàn)準(zhǔn)備、上機(jī)、報(bào)告、考試等）；

4、平時(shí)占5分（出勤，作業(yè)，測(cè)驗(yàn)等）七、參考書(shū)目1. 數(shù)據(jù)結(jié)構(gòu)（語(yǔ)言版） 嚴(yán)蔚敏等 清華大學(xué)出版社 2. 數(shù)據(jù)結(jié)構(gòu)題集 （C語(yǔ)言版） 嚴(yán)蔚敏等 清華大學(xué)出版社 3. DATA STRUCTURE WITH C+ William Ford,William Topp清華大學(xué)出版社（影印版）實(shí)驗(yàn)一 線性表的順序存儲(chǔ)結(jié)構(gòu)實(shí)驗(yàn)學(xué)時(shí) 2學(xué)時(shí)背景知識(shí):順序表的插入、刪除及應(yīng)用。目的要求： 1掌握順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)。 2掌握順序存儲(chǔ)結(jié)構(gòu)的常見(jiàn)算法。實(shí)驗(yàn)內(nèi)容 1輸入一組整型元素序列，建立順序表。 2實(shí)現(xiàn)該順序表的遍歷。 3在該順序表中進(jìn)行順序查找某一元素,查找成功返回1,否則返回0。 4判斷該順序表中元素是否對(duì)稱,

5、對(duì)稱返回1,否則返回0。5實(shí)現(xiàn)把該表中所有奇數(shù)排在偶數(shù)之前,即表的前面為奇數(shù),后面為偶數(shù)。6輸入整型元素序列利用有序表插入算法建立一個(gè)有序表。 7利用算法6建立兩個(gè)非遞減有序表并把它們合并成一個(gè)非遞減有序表。8編寫(xiě)一個(gè)主函數(shù),調(diào)試上述算法。 * 9綜合訓(xùn)練：利用順序表實(shí)現(xiàn)一個(gè)班級(jí)學(xué)生信息管理（數(shù)據(jù)錄入、插入、刪除、排序、查找等）實(shí)驗(yàn)說(shuō)明 1.算法1至算法7可以以頭文件的方式存儲(chǔ),主函數(shù)實(shí)現(xiàn)該頭文件的包含即可調(diào)用 2.存儲(chǔ)定義 #define MAXSIZE 100 /表中元素的最大個(gè)數(shù) typedef int ElemType；/元素類型 typedef struct list ElemTyp

6、e elemMAXSIZE;/靜態(tài)線性表 int length; /表的實(shí)際長(zhǎng)度 SqList;/順序表的類型名 3.建立順序表時(shí)可利用隨機(jī)函數(shù)自動(dòng)產(chǎn)生數(shù)據(jù)。注意問(wèn)題 插入、刪除時(shí)元素的移動(dòng)原因、方向及先后順序。 解不同的函數(shù)形參與實(shí)參的傳遞關(guān)系。實(shí)驗(yàn)二 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（一）-單向鏈表的有關(guān)操作實(shí)驗(yàn)學(xué)時(shí) 學(xué)時(shí)背景知識(shí)：?jiǎn)蜗蜴湵淼牟迦?、刪除及應(yīng)用。目的要求 1掌握單向鏈表的存儲(chǔ)特點(diǎn)及其實(shí)現(xiàn)。 2掌握單向鏈表的插入、刪除算法及其應(yīng)用算法的程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容 1隨機(jī)產(chǎn)生或鍵盤(pán)輸入一組元素，建立一個(gè)帶頭結(jié)點(diǎn)的單向鏈表（無(wú)序）。 2遍歷單向鏈表。 3把單向鏈表中元素逆置（不允許申請(qǐng)新的結(jié)點(diǎn)空間）。 4在單

7、向鏈表中刪除所有的偶數(shù)元素結(jié)點(diǎn)。 5編寫(xiě)在非遞減有序鏈表中插入一個(gè)元素使鏈表元素仍有序的函數(shù)，并利用該函數(shù)建立一個(gè)非遞減有序單向鏈表。 6利用算法5建立兩個(gè)非遞減有序單向鏈表，然后合并成一個(gè)非遞增鏈表。 7利用算法5建立兩個(gè)非遞減有序單向鏈表，然后合并成一個(gè)非遞減鏈表。 8利用算法1建立的鏈表，實(shí)現(xiàn)將其分解成兩個(gè)鏈表，其中一個(gè)全部為奇數(shù)，另一個(gè)全部為偶數(shù)（盡量利用已知的存儲(chǔ)空間）。 * 9采用單向鏈表實(shí)現(xiàn)一元多項(xiàng)式的存儲(chǔ)并實(shí)現(xiàn)兩個(gè)多項(xiàng)式相加并輸出結(jié)果。10在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單，分別調(diào)試上述算法。 *11綜合訓(xùn)練：利用鏈表實(shí)現(xiàn)一個(gè)班級(jí)學(xué)生信息管理（數(shù)據(jù)錄入、插入、刪除、排序、查找等，并能

8、夠?qū)崿F(xiàn)將數(shù)據(jù)存儲(chǔ)到文件中）實(shí)驗(yàn)說(shuō)明 1類型定義 #include <stdio.h> typedef int ElemType；/元素類型 typedef struct LNode ElemType data; struct LNode *next; LNode,*LinkList; 2為了算法實(shí)現(xiàn)簡(jiǎn)單，最好采用帶頭結(jié)點(diǎn)的單向鏈表。注意問(wèn)題 1重點(diǎn)理解鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)及指針的含義。 2注意比較順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的各自特點(diǎn)。 3注意比較帶頭結(jié)點(diǎn)、無(wú)頭結(jié)點(diǎn)鏈表實(shí)現(xiàn)插入、刪除算法時(shí)的區(qū)別。 4單向鏈表的操作是數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，一定要注意對(duì)這部分的常見(jiàn)算法的理解。實(shí)驗(yàn)三 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（二）-雙

9、向鏈表的有關(guān)操作實(shí)驗(yàn)學(xué)時(shí) 學(xué)時(shí)背景知識(shí)：雙向鏈表的插入、刪除及應(yīng)用。目的要求 掌握雙向鏈表的存儲(chǔ)特點(diǎn)及其實(shí)現(xiàn)。 掌握雙向鏈表的插入、刪除算法及其應(yīng)用算法的程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容 利用尾插法建立一個(gè)雙向鏈表。 遍歷雙向鏈表。 實(shí)現(xiàn)雙向鏈表中刪除一個(gè)指定元素。 在非遞減有序雙向鏈表中實(shí)現(xiàn)插入元素e仍有序算法。 判斷雙向鏈表中元素是否對(duì)稱若對(duì)稱返回1否則返回0。 設(shè)元素為正整型,實(shí)現(xiàn)算法把所有奇數(shù)排列在偶數(shù)之前。 在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單調(diào)試上述算法。雙向鏈表的類型定義 typedef int ElemType；/元素類型 typedef struct DuLNode ElemType data;

10、struct DuLNode *prior,*next; DuLNode,*DuLinkList; 注意問(wèn)題 注意比較單向、雙向鏈表的特點(diǎn)。實(shí)驗(yàn)四 棧隊(duì)列實(shí)驗(yàn)學(xué)時(shí) 學(xué)時(shí)背景知識(shí)：入棧、出棧，入隊(duì)、出隊(duì)。目的要求 1掌握棧、隊(duì)列的思想及其存儲(chǔ)實(shí)現(xiàn)。 2掌握棧、隊(duì)列的常見(jiàn)算法的程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容 1采用鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)棧的初始化、入棧、出棧操作。 2采用順序存儲(chǔ)實(shí)現(xiàn)棧的初始化、入棧、出棧操作。 3采用鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)隊(duì)列的初始化、入隊(duì)、出隊(duì)操作。 4采用順序存儲(chǔ)實(shí)現(xiàn)循環(huán)隊(duì)列的初始化、入隊(duì)、出隊(duì)操作。 5在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單，分別測(cè)試上述算法。 *6綜合訓(xùn)練:1)利用棧實(shí)現(xiàn)表達(dá)式求值算法。 2)利用

11、棧實(shí)現(xiàn)迷宮求解。實(shí)驗(yàn)說(shuō)明 1基本要求：實(shí)現(xiàn)算法1、3或算法2、4即可。 2類型定義 順序棧示例#define MAX 100 /棧的最大值typedefstruct ElemType *base；int top；SqStack； 順序隊(duì)列示例#define MAX 100 /隊(duì)列的最大長(zhǎng)度typedefstruct ElemType *base；int front，rear；SqQueue； 3算法6的每個(gè)子功能盡可能寫(xiě)成函數(shù)形式。注意問(wèn)題 1重點(diǎn)理解棧、隊(duì)列的算法思想，能夠根據(jù)實(shí)際情況選擇合適的存儲(chǔ)結(jié)構(gòu)。 2注意算法6的各個(gè)函數(shù)之間值的傳遞情況。 3棧、隊(duì)列的算法是后續(xù)實(shí)驗(yàn)的基礎(chǔ)（廣義表、樹(shù)

12、、圖、查找、排序等）。實(shí)驗(yàn)五 二叉樹(shù)的常見(jiàn)操作實(shí)驗(yàn)學(xué)時(shí) 學(xué)時(shí)背景知識(shí)：二叉樹(shù)的存儲(chǔ)、建立、遍歷及其應(yīng)用。目的要求 1掌握二叉樹(shù)的存儲(chǔ)實(shí)現(xiàn)。 2掌握二叉樹(shù)的遍歷思想。 3掌握二叉樹(shù)的常見(jiàn)算法的程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容 1輸入字符序列，建立二叉鏈表。 2中序遍歷二叉樹(shù):遞歸算法。 3中序遍歷二叉樹(shù):非遞歸算法。（最好也能實(shí)現(xiàn)先序，后序非遞歸算法） 4求二叉樹(shù)的高度 。 5求二叉樹(shù)的葉子個(gè)數(shù)。 *6將二叉鏈表視為森林的孩子兄弟鏈表，計(jì)算森林中葉子個(gè)數(shù)。 *7建立中序線索二叉樹(shù)，并實(shí)現(xiàn)中序遍歷。 8借助隊(duì)列實(shí)現(xiàn)二叉樹(shù)的層次遍歷。 9在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單，分別調(diào)試上述算法。 *10綜合訓(xùn)練：為N個(gè)權(quán)值

13、設(shè)計(jì)哈夫曼編碼。實(shí)驗(yàn)說(shuō)明 類型定義 /二叉鏈表存儲(chǔ) #define ElemType char/元素類型 typedef struct BiTNode ElemType data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree;元素類型可以根據(jù)實(shí)際情況選取。注意問(wèn)題 1注意理解遞歸算法的執(zhí)行步驟。2注意字符類型數(shù)據(jù)在輸入時(shí)的處理。3重點(diǎn)理解如何利用棧結(jié)構(gòu)實(shí)現(xiàn)非遞歸算法。實(shí)驗(yàn)六 圖的有關(guān)操作實(shí)驗(yàn)學(xué)時(shí) 學(xué)時(shí)背景知識(shí)：圖的存儲(chǔ)、遍歷、及其應(yīng)用。目的要求 掌握?qǐng)D的存儲(chǔ)思想及其存儲(chǔ)實(shí)現(xiàn)。 掌握?qǐng)D的深度、廣度優(yōu)先遍歷算法思想及其程序?qū)崿F(xiàn)。 掌握?qǐng)D的常見(jiàn)應(yīng)用

14、算法的思想及其程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容 鍵盤(pán)輸入數(shù)據(jù)，建立一個(gè)有向圖的鄰接表。 輸出該鄰接表。 *建立一個(gè)無(wú)向圖的十字鏈表。 在有向圖的鄰接表的基礎(chǔ)上計(jì)算各頂點(diǎn)的度，并輸出。 以有向圖的鄰接表為基礎(chǔ)實(shí)現(xiàn)輸出它的拓?fù)渑判蛐蛄小?*采用鄰接矩陣存儲(chǔ)一個(gè)有向圖，輸出單源點(diǎn)到其它頂點(diǎn)的最短路徑。 采用鄰接表存儲(chǔ)實(shí)現(xiàn)無(wú)向圖的深度優(yōu)先非遞歸遍歷。 采用鄰接表存儲(chǔ)實(shí)現(xiàn)無(wú)向圖的廣度優(yōu)先遍歷。 *采用鄰接矩陣存儲(chǔ)實(shí)現(xiàn)無(wú)向圖的最小生成樹(shù)的PRIM算法。 *10判斷無(wú)向圖任意兩個(gè)頂點(diǎn)間是否有路徑，若有輸出路徑上的頂點(diǎn)序列。11在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單，分別調(diào)試上述算法。 *12綜合訓(xùn)練：為計(jì)算機(jī)專業(yè)設(shè)計(jì)教學(xué)計(jì)劃：4個(gè)

15、學(xué)年，每學(xué)年2個(gè)學(xué)期，開(kāi)設(shè)50門(mén)課程，每學(xué)期所開(kāi)課程門(mén)數(shù)盡量均衡，課程的安排必須滿足先修關(guān)系。實(shí)驗(yàn)說(shuō)明 類型定義（鄰接表存儲(chǔ)） #define MAX_VERTEX_NUM 8 /頂點(diǎn)最大個(gè)數(shù) typedef struct ArcNode int adjvex; struct ArcNode *nextarc; int weight; /邊的權(quán) ArcNode; /表結(jié)點(diǎn) #define VertexType int /頂點(diǎn)元素類型 typedef struct VNode int degree,indegree;/頂點(diǎn)的度，入度 VertexType data; ArcNode *first

16、arc; VNode/*頭結(jié)點(diǎn)*/,AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices; int vexnum,arcnum;/頂點(diǎn)的實(shí)際數(shù)，邊的實(shí)際數(shù) ALGraph; 上述類型定義可以根據(jù)實(shí)際情況適當(dāng)調(diào)整。算法、分別利用棧、隊(duì)列實(shí)現(xiàn)非遞歸算法。 注意問(wèn)題 注意理解各算法實(shí)現(xiàn)時(shí)所采用的存儲(chǔ)結(jié)構(gòu)。注意區(qū)別正、逆鄰接。實(shí)驗(yàn)七 查找的有關(guān)操作實(shí)驗(yàn)學(xué)時(shí) 2學(xué)時(shí)背景知識(shí):順序查找、樹(shù)表查找、散列查找。目的要求： 1掌握折半查找算法的思想及程序?qū)崿F(xiàn)。 2掌握二叉排序樹(shù)、AVL樹(shù)的查找、插入、刪除、建立算法的思想及程序?qū)崿F(xiàn)。3掌握散列存儲(chǔ)結(jié)構(gòu)的思想

17、，能選擇合適散列函數(shù)，實(shí)現(xiàn)不同沖突處理方法的散列表的查找、建立。實(shí)驗(yàn)內(nèi)容 1利用實(shí)驗(yàn)一建立有序表，采用折半查找實(shí)現(xiàn)某一已知的關(guān)鍵字的查找。 2隨機(jī)產(chǎn)生一組關(guān)鍵字，利用二叉排序樹(shù)的插入算法建立二叉排序樹(shù)，然后刪除某一指定關(guān)鍵字元素。 *3建立樹(shù)并實(shí)現(xiàn)刪除某一指定關(guān)鍵字元素。 4已知散列函數(shù)為H(key)=key%p（p為自定的常數(shù)），沖突處理方法分別為線性探測(cè)法、外拉鏈法實(shí)現(xiàn)散列表的建立（利用插入算法實(shí)現(xiàn)）。 實(shí)驗(yàn)說(shuō)明 1存儲(chǔ)定義（散列表的外拉鏈法） #define n 9 typedef struct node int key; struct node *next; NODE; NODE *H

18、ashTable9; 算法1、2、3可以參考順序表，二叉鏈表的存儲(chǔ)實(shí)現(xiàn)。2各種關(guān)鍵字?jǐn)?shù)據(jù)輸入可利用隨機(jī)函數(shù)自動(dòng)產(chǎn)生，以便節(jié)省上機(jī)時(shí)間。3算法1存儲(chǔ)在文件seqlist.h中,算法2、3存儲(chǔ)在文件bintree.h中,算法4存儲(chǔ)在文件hash.h中注意問(wèn)題 1注意理解折半查找的適用條件（鏈表能否實(shí)現(xiàn)折半查找？）。 2注意建立二叉排序樹(shù)、散列表時(shí)相同元素的處理。3注意理解靜態(tài)查找、動(dòng)態(tài)查找概念。4比較各種查找算法的各自特點(diǎn)，能夠根據(jù)實(shí)際情況選擇合適的查找方法。實(shí)驗(yàn)八 排序?qū)嶒?yàn)學(xué)時(shí) 學(xué)時(shí)背景知識(shí)：各種排序方法目的要求 掌握常見(jiàn)的排序算法的思想及其適用條件。 掌握常見(jiàn)的排序算法的程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容 輸

19、入一組關(guān)鍵字序列分別實(shí)現(xiàn)下列排序: 1.實(shí)現(xiàn)簡(jiǎn)單選擇排序、直接插入排序和冒泡排序。 2.實(shí)現(xiàn)希爾排序算法。 3.實(shí)現(xiàn)快速排序算法。 4.實(shí)現(xiàn)堆排序算法。 *5.快速排序的非遞歸算法。 *6.實(shí)現(xiàn)折半插入排序。 *7.采用鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)簡(jiǎn)單選擇排序、直接插入排序和冒泡排序。8.在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單，分別測(cè)試上述算法。 *9綜合訓(xùn)練：采用幾組不同數(shù)據(jù)測(cè)試各個(gè)排序算法的性能（比較次數(shù)和移動(dòng)次數(shù)）。實(shí)驗(yàn)說(shuō)明 1類型定義 #define MAXSIZE 100 /*參加排序元素的最大個(gè)數(shù)*/ typedef struct list int key; RedType; typedef struct

20、RedType rMAXSIZE+1; int length; /*參加排序元素的實(shí)際個(gè)數(shù)*/ SqList;2算法可以借助棧實(shí)現(xiàn)。注意問(wèn)題 1在RedType中增加一個(gè)數(shù)據(jù)項(xiàng)驗(yàn)證各種排序算法的穩(wěn)定性。2注意理解各種算法的思想、了解算法的適用情況及時(shí)間復(fù)雜度，能夠根據(jù)實(shí)際情況選擇合適的排序方法。/部分算法程序示例/實(shí)驗(yàn)一 線性表的順序存儲(chǔ)結(jié)構(gòu) #include "stdio.h" #include "stdlib.h" #define Status int #define OVERFLOW 0 #define TRUE 1 #define FALSE 0

21、 #define OK 1 #define MAXSIZE 100 typedef int ElemType; typedef struct list ElemType elemMAXSIZE; int length; SqList; void InitList(SqList &L) L.length=0; /*建立順序表*/ void CreateList(SqList &L) int i; printf("input the length"); scanf("%d",&L.length);/輸入表長(zhǎng) for(i=1;i<

22、=L.length;i+) scanf("%d",&L.elemi-1);/輸入元素 /順序表的遍歷 void printdata(ElemType e) printf("%4d",e); void Traverse(SqList L,void (*visit)(ElemType e) int i; printf("The elements of the lists are:n"); for(i=1;i<=L.length;i+) if (i%10=0)printf("n");/每行顯示10個(gè)元素 v

23、isit(L.elemi-1);/輸出表中元素 printf("n"); /有序順序表L中插入元素e使序列仍有序 void Insert(SqList &L,ElemType e) int i,j; if (L.length=MAXSIZE)exit(OVERFLOW);/表滿,不能插入 for(i=1;i<=L.length&&L.elemi-1<=e;i+);/向后查找 for(j=L.length;j>=i;j-) L.elemj=L.elemj-1;/元素后移 L.elemi-1=e;/插入e L.length=L.leng

24、th+1;/表長(zhǎng)加 /建立遞增有序的順序表 void CreateList_Sorted(SqList &L) int i,num; ElemType e; L.length=0; printf("Create a sorted list,Input the length of the listn"); scanf("%d",&num); printf("Input the data %d numbersn",num); for(i=1;i<=num;i+) scanf("%d",&e

25、); Insert(L,e); /*Merge two sorted lists*/ void MergeList(SqList La,SqList Lb,SqList &Lc) int *pa,*pb,*pc; if (La.length+Lb.length>MAXSIZE) exit(OVERFLOW); else pa=La.elem;pb=Lb.elem;pc=Lc.elem; while (pa<La.elem+La.length&&pb<Lb.elem+Lb.length) *pc+=(*pa<=*pb)?*pa+:*pb+;/*公共

26、部分合并*/ while (pa<La.elem+La.length) *pc+=*pa+; /*R1表的剩余部分放到R的后部*/ while (pb<Lb.elem+Lb.length) *pc+=*pb+; /*R2表的剩余部分放到R的后部*/ Lc.length=La.length+Lb.length;/*R表長(zhǎng)*/ /判斷元素是否對(duì)稱，對(duì)稱返回TRUE 否則返回FALSE Status Symmetric(SqList L) int low,high; low=0; high=L.length-1; while(low<high) if (L.elemlow=L.el

27、emhigh)low+;high-; else return(FALSE); return(TRUE); /順序表的主函數(shù)部分/#include "seqlist.h" void main() SqList L1,L2,L; int select; ElemType e; doprintf("n1 insert 2 merge"); printf("n3 symmetric 0 exit n"); printf("Please select(0-3)n"); scanf("%d",&se

28、lect); switch(select) case 1: InitList(L); CreateList_Sorted(L); Traverse(L,printdata); printf("nInput the element of insertedn"); scanf("%d",&e); Insert(L,e); Traverse(L,printdata); break; case 2: InitList(L1); CreateList_Sorted(L1); Traverse(L1,printdata); InitList(L2); Cre

29、ateList_Sorted(L2); Traverse(L2,printdata); InitList(L); MergeList(L1,L2,L); Traverse(L,printdata); break; case 3: InitList(L); CreateList(L); Traverse(L,printdata); if (Symmetric(L) printf("Yes!n"); else printf("Notn"); break; case 0:break; default:printf("Error! Try again!

30、n"); while(select); /*實(shí)驗(yàn)二 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（一）-單向鏈表的有關(guān)操作/*類型定義及頭文件部分,文件名為sllink.h*/ #include <stdio.h> #include <stdlib.h> typedef int ElemType;/元素實(shí)際類型 typedef struct LNode ElemType data; struct LNode *next; LNode,*LinkList; /定義結(jié)點(diǎn)、指針類型名 /頭插法建立無(wú)序鏈表 void CreateList(LinkList &L) LinkList p; E

31、lemType e; L=(LinkList)malloc(sizeof(LNode); L->next=NULL; printf("頭插法建立鏈表，以0結(jié)束n"); scanf("%d",&e); while(e) p=(LinkList)malloc(sizeof(LNode); p->data=e; p->next=L->next; L->next=p; scanf("%d",&e); /*非遞減有序單向鏈表L插入元素e序列仍有序*/ void Insert_Sort(LinkLis

32、t &L,ElemType e) LinkList p,s; s=(LinkList)malloc(sizeof(LNode); s->data=e; p=L; while(p->next&&p->next->data<=e) p=p->next;/*查找插入位置*/ s->next=p->next; /*插入語(yǔ)句*p結(jié)點(diǎn)后插入*s結(jié)點(diǎn)*/ p->next=s; /*建立遞增有序的單向鏈表*/ void Create_Sort(LinkList &L) ElemType e; L=(LinkList)mall

33、oc(sizeof(LNode); L->next=NULL; printf("建立有序表，輸入任意個(gè)整型數(shù)據(jù)以0結(jié)束n"); scanf("%d",&e); while(e) Insert_Sort(L,e); scanf("%d",&e); /*單向鏈表的遍歷*/ void Traverse(LinkList L) LinkList p; printf("遍歷鏈表"); for(p=L->next;p;p=p->next) printf("%5d",p-&g

34、t;data); printf("n"); /*在單向鏈表刪除元素e*/ void Delete(LinkList &L,ElemType e) LinkList p,q; p=L; q=L->next; while(q&& q->data!=e)/查找元素的刪除位置 p=q; q=q->next; if(!q) printf("nnot deleted");/*未找到元素e*/ else p->next=q->next;/*找到刪除*/ free(q); /*單向鏈表的逆置*/ void exch(

35、LinkList &L) LinkList p,s; p=L->next; L->next=NULL; while(p) s=p; p=p->next; s->next=L->next; L->next=s; /*兩個(gè)非遞減有序單向鏈表合并后仍為非遞減序列*/ void MergeIncrease(LinkList La,LinkList Lb,LinkList &Lc) LinkList p,q,s,rear; p=La->next; q=Lb->next; Lc=rear=La; free(Lb); while(p&&

36、amp;q) if (p->data<q->data) s=p;p=p->next; else s=q;q=q->next; rear->next=s;/*較小元素插入表尾*/ rear=rear->next; if (p) rear->next=p; else rear->next=q; /*主函數(shù)部分,文件名為sllink.c*/#include "sllink.h" void main() LinkList La,Lb,Lc; ElemType e; int select; do printf(" 1 建

37、立無(wú)序表，再刪除指定元素n"); printf(" 2 建立遞增有序表，再逆置n"); printf(" 3 建立兩個(gè)遞增有序表，將它們和并為一個(gè)仍遞增表n"); printf(" 0 退出，請(qǐng)輸入選項(xiàng)(0-3)n"); scanf("%d",&select); switch(select) case 0: break; case 1: CreateList(La); Traverse(La); printf("輸入需刪除的元素n"); scanf("%d"

38、,&e); Delete(La,e); Traverse(La); break; case 2: Create_Sort(La); Traverse(La); exch(La); printf("The list that is exchagedn"); Traverse(La); break; case 3: Create_Sort(La);Traverse(La); Create_Sort(Lb);Traverse(Lb); MergeIncrease(La,Lb,Lc);Traverse(Lc); break; default: printf("輸入

39、選項(xiàng)錯(cuò)誤，請(qǐng)重新輸入！n"); while(select); 實(shí)驗(yàn)三 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（二）-雙向鏈表的有關(guān)操作/*雙向鏈表的有關(guān)操作*/ #include <stdio.h> #include <stdlib.h> typedef int ElemType; typedef struct DuLNode ElemType data; struct DuLNode *prior,*next; DuLNode,*DuLinkList; /*尾插法建立雙向鏈表*/ void CreateList(DuLinkList *L) DuLinkList p; ElemTyp

40、e e; printf("Create a new double_linked_list:n"); *L=(DuLinkList)malloc(sizeof(DuLNode); (*L)->next=(*L)->prior=*L; printf("Input data(end of 0)n"); scanf("%d",&e); while(e) p=(DuLinkList)malloc(sizeof(DuLNode); p->data=e; p->next=*L; p->prior=(*L)-&g

41、t;prior; (*L)->prior=(*L)->prior->next=p; /*在*h結(jié)點(diǎn)前插入結(jié)點(diǎn)*p*/ scanf("%d",&e); /*遍歷雙向鏈表*/ void visit(DuLinkList L) DuLinkList p; printf("遍歷鏈表n"); for(p=L->next;p!=L;p=p->next) printf("%5d",p->data); printf("n"); /*設(shè)元素為整型,把所有奇數(shù)排列在偶數(shù)之前*/ void D

42、ivi(DuLinkList *L) DuLinkList p,q; p=(*L)->next; q=(*L)->prior; while (p!=q) while(p!=q&&p->data%2!=0)p=p->next; /*從前向后查找偶數(shù)*/ while(p!=q&&q->data%2=0)q=q->prior; /*從后向前查找奇數(shù)*/ (*L)->data=p->data; p->data=q->data; q->data=(*L)->data; / p, q所指結(jié)點(diǎn)的元素交換，

43、頭結(jié)點(diǎn)為中間變量 /*非遞減有序雙向鏈表的插入元素k序列仍有序*/ void Insert(DuLinkList *L,ElemType e) DuLinkList p,s; s=(DuLinkList )malloc(sizeof(DuLNode); s->data=e; p=(*L)->next; while(p!=*L && p->data<=e) p=p->next; s->next=p; s->prior=p->prior; p->prior=p->prior->next=s; /*結(jié)點(diǎn)*p之前插入結(jié)點(diǎn)

44、*s */ /*判斷雙向鏈表中元素是否對(duì)稱若對(duì)稱返回1否則返回0*/ int Symmetric(DuLinkList L) DuLinkList p,q; p=L->next; q=L->prior; while (p!=q&&q->next!=p) if (p->data=q->data) p=p->next;q=q->prior; else return(0); return(1); /*主函數(shù)部分*/ void main() DuLinkList L; ElemType e; int select; do printf(&quo

45、t;n1 Judge if the list is symmetric"); printf("n2 divide odd and even"); printf("n3 Insert an element in a sorted list"); printf("n0 退出 Please select(0-3):n"); scanf("%d",&select); switch(select) case 1: CreateList(&L); visit(L); if(Symmetric(L) p

46、rintf("n元素對(duì)稱！"); else printf("n元素不對(duì)稱！"); break; case 2: CreateList(&L);visit(L); Divi(&L);visit(L); break; case 3: CreateList(&L);visit(L); printf("Input an element"); scanf("%d",&e); Insert(&L,e); visit(L); break; case 0: break; default: p

47、rintf("Error! Again!n"); while(select); /* 實(shí)驗(yàn)四 棧和隊(duì)列 */ #include <stdio.h> #include <stdlib.h> typedef int SElemType;/棧的元素類型 /*鏈棧的定義*/ typedef struct Node SElemType data; struct Node *next; NODE; typedef struct NODE *top;/鏈?zhǔn)綏５臈ｍ斨羔?Stack; #define TRUE 1 #define FALSE 0 #define OK

48、 1 #define OVERFLOW -2 typedef int Status; /*鏈?zhǔn)綏５牟僮魇纠?/ void InitStack(Stack &S) S.top=(NODE *)malloc(sizeof(NODE); if (!S.top)exit(OVERFLOW);/棧溢出 S.top->next=NULL; Status StackEmpty(Stack S) if (S.top->next=NULL) return(TRUE); else return(FALSE); void Push(Stack &S,SElemType e) NODE *

49、p; p=(NODE *)malloc(sizeof(NODE); if (!p)return; /棧滿溢出 p->data=e; p->next=S.top->next; S.top->next=p; void Pop(Stack &S,SElemType &e) NODE *p; if (StackEmpty(S) return;/?？?else p=S.top->next; e=p->data; S.top->next=p->next; free(p); SElemType Gettop(Stack &S) NODE

50、 *p; if (StackEmpty(S)return 0;/?？?else p=S.top->next; return(p->data); /*主函數(shù)部分示例文件名為stackqueue.c*/#include "linksq.h" void main() int select; SElemType num=1,e; Stack S; InitStack(S); do printf("n1 Push 2 Popn"); printf("0 exitn please selcet(0-2)n"); scanf("%d",&select); switch(select) case 1: printf("Push%2d ",num); Push(S,num+); break; case 2: if (!StackEmpty(S) Pop(S,e); printf("Pop %2