數(shù)據(jù)構(gòu)造實(shí)驗(yàn)指導(dǎo)書(shū)2計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)目錄TOC\o“1-2“\h\z\u\l“_TOC_250012“試驗(yàn)?zāi)康呐c要求 1\l“_TOC_250011“試驗(yàn)環(huán)境 1\l“_TOC_250010“試驗(yàn)一般步驟 1\l“_TOC_250009“試驗(yàn)時(shí)數(shù) 2\l“_TOC_250008“試驗(yàn)內(nèi)容和要求 3\l“_TOC_250007“試驗(yàn)一 線性表的挨次存儲(chǔ)構(gòu)造 3\l“_TOC_250006“試驗(yàn)二 鏈?zhǔn)酱鎯?chǔ)構(gòu)造〔一〕單向鏈表的有關(guān)操作………………… 4\l“_TOC_250005“試驗(yàn)三 鏈?zhǔn)酱鎯?chǔ)構(gòu)造〔二〕雙向鏈表的有關(guān)操作 5\l“_TOC_250004“試驗(yàn)四 棧和隊(duì)列的有關(guān)操作 6\l“_TOC_250003“試驗(yàn)五 二叉樹(shù)的常見(jiàn)操作 7\l“_TOC_250002“試驗(yàn)六 圖的有關(guān)操作 8\l“_TOC_250001“試驗(yàn)七 查找的有關(guān)操作 9\l“_TOC_250000“試驗(yàn)八 排序的有關(guān)操作 10試驗(yàn)?zāi)康呐c要求從以往的教學(xué)事先實(shí)習(xí)的閱歷來(lái)看，在初學(xué)階段執(zhí)行嚴(yán)格的實(shí)習(xí)步驟標(biāo)準(zhǔn)〔包括上機(jī)〕，機(jī)時(shí)利用率會(huì)大大提高，有助于養(yǎng)成良好的程序編制風(fēng)格，培育嚴(yán)謹(jǐn)、科學(xué)、高效的工作方式。其害的。實(shí)習(xí)步驟標(biāo)準(zhǔn)不但可以培育科學(xué)化的工作作風(fēng)，而且還能有效地避開(kāi)錯(cuò)誤。試驗(yàn)環(huán)境計(jì)算機(jī)的硬件配置PC計(jì)算機(jī)的軟件配置DOS6.22Windows98、Windowsxp、Windows2023。CTurboCV3.0，VisualC++6.0。試驗(yàn)一般步驟⑴問(wèn)題分析與系統(tǒng)的構(gòu)造設(shè)計(jì)充分地分析和理解問(wèn)題本身，弄清要求作什么，限制條件是什么。依據(jù)以數(shù)據(jù)構(gòu)造為中心的原則劃分模塊，即定義數(shù)據(jù)構(gòu)造及其在這些構(gòu)造之上的操作，使得對(duì)數(shù)據(jù)構(gòu)造的存合理、簡(jiǎn)潔并且易于調(diào)試。最終寫(xiě)出每個(gè)子程序〔過(guò)程或函數(shù)〕的規(guī)格說(shuō)明，列出它們之間的調(diào)用關(guān)系，可以使用調(diào)用關(guān)系圖表示則更加清楚，這樣便完成了系統(tǒng)構(gòu)造設(shè)計(jì)。⑵具體設(shè)計(jì)和編碼具體設(shè)計(jì)的目的是對(duì)子程序〔過(guò)程或函數(shù)〕的進(jìn)一步求精。用IF、WHILE以對(duì)具體設(shè)計(jì)的結(jié)果進(jìn)一步求精，用高級(jí)語(yǔ)言表示出來(lái)。60〔或過(guò)程、函數(shù)〕通常不要太長(zhǎng)，40〔或過(guò)程、函數(shù)〕包含的程序行數(shù)太多，易于造成理解的困難。掌握用，除格外明顯的除外〔如：x=x+1;x1，沒(méi)有什么意義〕，都應(yīng)加以注釋。這中的有關(guān)規(guī)定。⑶上機(jī)預(yù)備和靜態(tài)檢查①高級(jí)語(yǔ)言文本②生疏機(jī)器的用戶(hù)手冊(cè)，生疏常用的命令。自己先設(shè)計(jì)一些以供使用。④靜態(tài)檢查的規(guī)律。⑷上機(jī)調(diào)試程序后將源程序和運(yùn)行結(jié)果加以列印輸出。⑸實(shí)習(xí)報(bào)告的整理①需求及規(guī)格說(shuō)明問(wèn)題描述，求解的問(wèn)題是什么。②設(shè)計(jì)：設(shè)計(jì)思想：存儲(chǔ)構(gòu)造、主要的算法思想?！策^(guò)程或函數(shù)〕的規(guī)格說(shuō)明，通過(guò)調(diào)用關(guān)系圖表示它們之間的調(diào)用關(guān)系。實(shí)現(xiàn)注釋?zhuān)壕唧w設(shè)計(jì)表示：主要算法的框架。③用戶(hù)手冊(cè)：使用說(shuō)明。等。⑤附錄用英文描述。⑥試驗(yàn)報(bào)告要求：電子文檔的形式進(jìn)展書(shū)寫(xiě)。試驗(yàn)時(shí)數(shù)總試驗(yàn)時(shí)數(shù)不得少于16學(xué)時(shí)。試驗(yàn)內(nèi)容和要求程中，對(duì)各種算法的時(shí)、空簡(jiǎn)單性的分析，將幫助您在更高的角度解決各種應(yīng)用問(wèn)題?！?〕試驗(yàn)題目、班級(jí)、學(xué)號(hào)、；〔2〕簡(jiǎn)要的需求分析與概要設(shè)計(jì)；〔3〕具體的算法描述；〔4〕程序清單與運(yùn)行結(jié)果；〔5〕收獲與體會(huì)。試驗(yàn)一線性表的挨次存儲(chǔ)構(gòu)造一、試驗(yàn)學(xué)時(shí)：2學(xué)時(shí)挨次表的插入、刪除及應(yīng)用。三、目的要求：⑴把握挨次存儲(chǔ)構(gòu)造的特點(diǎn)。⑴輸入一組整型元素序列，建立挨次表。四、試驗(yàn)內(nèi)容：⑴輸入一組整型元素序列，建立挨次表。⑵實(shí)現(xiàn)該挨次表的遍歷。⑵實(shí)現(xiàn)該挨次表的遍歷。1，0。1，0。⑸實(shí)現(xiàn)把該表中全部奇數(shù)排在偶數(shù)之前，即表的前面為奇數(shù)，后面為偶數(shù)。⑸實(shí)現(xiàn)把該表中全部奇數(shù)排在偶數(shù)之前，即表的前面為奇數(shù)，后面為偶數(shù)。⑹輸入整型元素序列利用有序表插入算法建立一個(gè)有序表。6⑻編寫(xiě)一個(gè)主函數(shù)，調(diào)試上述算法?！膊檎业取澄濉⒃囼?yàn)說(shuō)明：17⑵存儲(chǔ)定義#defineMAXSIZE100 中元素的最大個(gè)數(shù)typedefint ElemType；//元素類(lèi)型typedefstructlist{ElemTypeelem[MAXSIZE]；//靜態(tài)線性表intlength； //表的實(shí)際長(zhǎng)度}SqList；//挨次表的類(lèi)型名六、留意問(wèn)題：解不同的函數(shù)形參與實(shí)參的傳遞關(guān)系。試驗(yàn)二鏈?zhǔn)酱鎯?chǔ)構(gòu)造〔一〕單向鏈表的有關(guān)操作一、試驗(yàn)學(xué)時(shí)：２學(xué)時(shí)單向鏈表的插入、刪除及應(yīng)用。三、目的要求：⑴把握單向鏈表的存儲(chǔ)特點(diǎn)及其實(shí)現(xiàn)。四、試驗(yàn)內(nèi)容：⑴隨機(jī)產(chǎn)生或鍵盤(pán)輸入一組元素，建立一個(gè)帶頭結(jié)點(diǎn)的單向鏈表〔無(wú)序〕。⑵遍歷單向鏈表。⑶把單向鏈表中元素逆置〔不允許申請(qǐng)的結(jié)點(diǎn)空間〕。⑷在單向鏈表中刪除全部的偶數(shù)元素結(jié)點(diǎn)。立一個(gè)非遞減有序單向鏈表。55全部為偶數(shù)〔盡量利用的存儲(chǔ)空間〕。*⑼承受單向鏈表實(shí)現(xiàn)一元多項(xiàng)式的存儲(chǔ)并實(shí)現(xiàn)兩個(gè)多項(xiàng)式相加并輸出結(jié)果。⑽在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)潔的菜單，分別調(diào)試上述算法?！矓?shù)據(jù)錄入、插入、刪除、排序、查找等，并能夠?qū)崿F(xiàn)將數(shù)據(jù)存儲(chǔ)到文件中〕五、試驗(yàn)說(shuō)明：⑴類(lèi)型定義#include<stdio.h>typedefint 元素類(lèi)型typedef structLNode{ElemTypedata；structLNode*next；}LNode，*LinkList；六、留意問(wèn)題：⑴重點(diǎn)理解鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)及指針的含義。⑵留意比較挨次存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的各自特點(diǎn)。⑶留意比較帶頭結(jié)點(diǎn)、無(wú)頭結(jié)點(diǎn)鏈表實(shí)現(xiàn)插入、刪除算法時(shí)的區(qū)分。⑷單向鏈表的操作是數(shù)據(jù)構(gòu)造的根底，肯定要留意對(duì)這局部的常見(jiàn)算法的理解。試驗(yàn)三鏈?zhǔn)酱鎯?chǔ)構(gòu)造〔二〕雙向鏈表的有關(guān)操作一、試驗(yàn)學(xué)時(shí)：２學(xué)時(shí)雙向鏈表的插入、刪除及應(yīng)用。三、目的要求：⑴把握雙向鏈表的存儲(chǔ)特點(diǎn)及其實(shí)現(xiàn)。四、試驗(yàn)內(nèi)容：⑴利用尾插法建立一個(gè)雙向鏈表。⑵遍歷雙向鏈表。⑶實(shí)現(xiàn)雙向鏈表中刪除一個(gè)指定元素。e10。⑹設(shè)元素為正整型，實(shí)現(xiàn)算法把全部奇數(shù)排列在偶數(shù)之前。五、雙向鏈表的類(lèi)型定義：typedef intElemType；//元素類(lèi)型typedef structDuLNode{ ElemTypedata；structDuLNode*prior，*next；}DuLNode，*DuLinkList；六、留意問(wèn)題：留意比較單向、雙向鏈表的特點(diǎn)。試驗(yàn)四棧和隊(duì)列的有關(guān)操作一、試驗(yàn)學(xué)時(shí)：２學(xué)時(shí)二、背景學(xué)問(wèn)：入棧、出棧，入隊(duì)、出隊(duì)。三、目的要求：⑴把握棧、隊(duì)列的思想及其存儲(chǔ)實(shí)現(xiàn)。四、試驗(yàn)內(nèi)容：⑴承受鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)棧的初始化、入棧、出棧操作。⑵承受挨次存儲(chǔ)實(shí)現(xiàn)棧的初始化、入棧、出棧操作。⑶承受鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)隊(duì)列的初始化、入隊(duì)、出隊(duì)操作。⑷承受挨次存儲(chǔ)實(shí)現(xiàn)循環(huán)隊(duì)列的初始化、入隊(duì)、出隊(duì)操作。⑸在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)潔的菜單，分別測(cè)試上述算法。*⑹綜合訓(xùn)練：①利用棧實(shí)現(xiàn)表達(dá)式求值算法。五、試驗(yàn)說(shuō)明：1、32、4#defineMAX100//棧的最大值typedefstruct{ ElemType*base；inttop；}SqStack；#defineMAX100//隊(duì)列的最大長(zhǎng)度typedefstruct{ ElemType*base；intfront，rear；}SqQueue；六、留意問(wèn)題：⑴重點(diǎn)理解棧、隊(duì)列的算法思想，能夠依據(jù)實(shí)際狀況選擇適宜的存儲(chǔ)構(gòu)造。6⑶棧、隊(duì)列的算法是后續(xù)試驗(yàn)的根底〔廣義表、樹(shù)、圖、查找、排序等〕。試驗(yàn)五二叉樹(shù)的常見(jiàn)操作一、試驗(yàn)學(xué)時(shí)：２學(xué)時(shí)二叉樹(shù)的存儲(chǔ)、建立、遍歷及其應(yīng)用。三、目的要求：⑴把握二叉樹(shù)的存儲(chǔ)實(shí)現(xiàn)。⑵把握二叉樹(shù)的遍歷思想。四、試驗(yàn)內(nèi)容：⑴輸入字符序列，建立二叉鏈表。⑵中序遍歷二叉樹(shù)：遞歸算法。⑶中序遍歷二叉樹(shù)：非遞歸算法?！沧詈靡材軐?shí)現(xiàn)先序，后序非遞歸算法〕⑷求二叉樹(shù)的高度。⑸求二叉樹(shù)的葉子個(gè)數(shù)。*⑹將二叉鏈表視為森林的孩子兄弟鏈表，計(jì)算森林中葉子個(gè)數(shù)。*⑺建立中序線索二叉樹(shù)，并實(shí)現(xiàn)中序遍歷。⑻借助隊(duì)列實(shí)現(xiàn)二叉樹(shù)的層次遍歷。⑼在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)潔的菜單，分別調(diào)試上述算法。五、試驗(yàn)說(shuō)明：//二叉鏈表存儲(chǔ)#defineElemTypechar//元素類(lèi)型typedefstructBiTNode{ ElemTypedata；structBiTNode*lchild，*rchild；}BiTNode，*BiTree；六、留意問(wèn)題：⑴留意理解遞歸算法的執(zhí)行步驟。⑵留意字符類(lèi)型數(shù)據(jù)在輸入時(shí)的處理。⑶重點(diǎn)理解如何利用棧構(gòu)造實(shí)現(xiàn)非遞歸算法。試驗(yàn)六圖的有關(guān)操作一、試驗(yàn)學(xué)時(shí)：２學(xué)時(shí)圖的存儲(chǔ)、遍歷、及其應(yīng)用。三、目的要求：⑴把握?qǐng)D的存儲(chǔ)思想及其存儲(chǔ)實(shí)現(xiàn)。⑵把握?qǐng)D的深度、廣度優(yōu)先遍歷算法思想及其程序?qū)崿F(xiàn)。四、試驗(yàn)內(nèi)容：⑴鍵盤(pán)輸入數(shù)據(jù)，建立一個(gè)有向圖的鄰接表。⑵輸出該鄰接表。*⑶建立一個(gè)無(wú)向圖的十字鏈表。⑷在有向圖的鄰接表的根底上計(jì)算各頂點(diǎn)的度，并輸出。⑸以有向圖的鄰接表為根底實(shí)現(xiàn)輸出它的拓?fù)渑判蛐蛄小?⑹承受鄰接矩陣存儲(chǔ)一個(gè)有向圖，輸出單源點(diǎn)到其它頂點(diǎn)的最短路徑。⑺承受鄰接表存儲(chǔ)實(shí)現(xiàn)無(wú)向圖的深度優(yōu)先非遞歸遍歷。⑻承受鄰接表存儲(chǔ)實(shí)現(xiàn)無(wú)向圖的廣度優(yōu)先遍歷。*⑼PRIM*⑽推斷無(wú)向圖任意兩個(gè)頂點(diǎn)間是否有路徑，假設(shè)有輸出路徑上的頂點(diǎn)序列。⑾在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)潔的菜單，分別調(diào)試上述算法。4250課程，每學(xué)期所開(kāi)課程門(mén)數(shù)盡量均衡，課程的安排必需滿足先修關(guān)系。五、試驗(yàn)說(shuō)明：⑴類(lèi)型定義〔鄰接表存儲(chǔ)〕#defineMAX_VERTEX_NUM8 typedefstructArcNode{ int adjvex；structArcNode*nextarc；intweight；//邊的權(quán)}ArcNode； //表結(jié)點(diǎn)#defineVertexTypeint//頂點(diǎn)元素類(lèi)型typedefstructVNode{intdegree，indegree；//頂點(diǎn)的度，入度VertexTypedata；ArcNode*firstarc；頭結(jié)點(diǎn)*/，AdjList[MAX_VERTEX_NUM]；typedefstruct{AdjListvertices；intvexnum，arcnum；//頂點(diǎn)的實(shí)際數(shù)，邊的實(shí)際數(shù)}ALGraph；⑵上述類(lèi)型定義可以依據(jù)實(shí)際狀況適當(dāng)調(diào)整。六、留意問(wèn)題：⑴留意理解各算法實(shí)現(xiàn)時(shí)所承受的存儲(chǔ)構(gòu)造。⑵留意區(qū)分正、逆鄰接。試驗(yàn)七查找的有關(guān)操作一、試驗(yàn)學(xué)時(shí)：2學(xué)時(shí)挨次查找、樹(shù)表查找、散列查找。三、目的要求：⑴把握折半查找算法的思想及程序?qū)崿F(xiàn)。⑵把握二叉排序樹(shù)、AVL的查找、建立。四、試驗(yàn)內(nèi)容：⑴利用試驗(yàn)一建立有序表，承受折半查找實(shí)現(xiàn)某一的關(guān)鍵字的查找。指定關(guān)鍵字元素。*⑶建立ＡＶＬ樹(shù)并實(shí)現(xiàn)刪除某一指定關(guān)鍵字元素?！?，沖突處理方法分別為線性探測(cè)法、外拉鏈法實(shí)現(xiàn)散列表的建立〔利用插入算法實(shí)現(xiàn)〕。五、試驗(yàn)說(shuō)明：⑴存儲(chǔ)定義〔散列表的外拉鏈法〕#definen9typedefstructnode{intkey；structnode*next；}NODE；NODE*HashTable[9]；算法1、2、3可以參考挨次表，二叉鏈表的存儲(chǔ)實(shí)現(xiàn)。⑵各種關(guān)鍵字?jǐn)?shù)據(jù)輸入可利用隨機(jī)函數(shù)自動(dòng)產(chǎn)生，以便節(jié)約上機(jī)時(shí)間。1seqlist.h2、3bintree.h4hash.h六、留意問(wèn)題：⑴留意理解折半查找的適用條件〔鏈表能否實(shí)現(xiàn)折半查找？〕。⑵留意建立二叉排序樹(shù)、散列表時(shí)一樣元素的處理。⑶留意理解靜態(tài)查找、動(dòng)態(tài)查找概念。⑷比較各種查找算法的各自特點(diǎn)，能夠依據(jù)實(shí)際狀況選擇適宜的查找方法。試驗(yàn)八排序的有關(guān)操作一、試驗(yàn)學(xué)時(shí)：２學(xué)時(shí)各種排序方法三、目的要求：⑴把握常見(jiàn)的排序算法的思想及其適用條件。四、試驗(yàn)內(nèi)容：輸入一組關(guān)鍵字序列分別實(shí)現(xiàn)以下排序：⑴實(shí)現(xiàn)簡(jiǎn)潔選擇排序、直接插入排序和冒泡排序。⑵實(shí)現(xiàn)希爾排序算法。⑶實(shí)現(xiàn)快速排序算法。⑷實(shí)現(xiàn)堆排序算法。*⑸快速排序的