【文章內(nèi)容簡介】 分析和比較，內(nèi)容非常豐富。本課程的學(xué)習(xí)將為后續(xù)課程的學(xué)習(xí) 以及軟件設(shè)計水平的提高打下良好的基礎(chǔ)。 由于以下原因，使得掌握這門課程具有較大難度： 內(nèi)容多，時間短，給學(xué)習(xí)帶來困難； 貫穿全書的動態(tài)鏈表存儲結(jié)構(gòu)和遞歸技術(shù)是學(xué)習(xí)中的重點和難點； 隱含在各部分的技術(shù)和方法豐富，也是學(xué)習(xí)的重點和難點； 先修課程中所介紹的專業(yè)性知識不多，加大了學(xué)習(xí)難度。 由于數(shù)據(jù)結(jié)構(gòu)課程的技術(shù)性與實踐性，《數(shù)據(jù)結(jié)構(gòu)課程實驗》的設(shè)置十分必要。為了幫助學(xué)生更好地學(xué)習(xí)本課程，理解和掌握算法設(shè)計所需的技術(shù)，為整個專業(yè)學(xué)習(xí)打好基礎(chǔ)，要求運用所學(xué)知識，上機解決一些典型問題，通過分析、設(shè)計、 編碼、調(diào)試等各環(huán)節(jié)的訓(xùn)練，使學(xué)生深刻理解、牢固掌握所用到的一些技術(shù)。 上機實踐是對學(xué)生的一種全面綜合訓(xùn)練，是與課堂聽講、自學(xué)和練習(xí)相輔相成的必不可少的一個教學(xué)環(huán)節(jié)。通過上機實踐，使學(xué)生在可能短的時間內(nèi)對數(shù)據(jù)結(jié)構(gòu)知識的實踐和應(yīng)用有一個比較全面和系統(tǒng)的認識，達到理論與實踐相結(jié)合的目的。 為了達到上述目的，本指導(dǎo)書安排了 8個實驗題目，它們與教科書的各章有緊密的關(guān)系，使學(xué)生在實驗后能加深對課程內(nèi)容的理解，增強動手能力。 每個實驗題目采取了統(tǒng)一的格式，由問題描述、基本要求、測試數(shù)據(jù)、實現(xiàn)提示等部分組成。 問題描述旨在 為讀者建立問題提出的背景環(huán)境，指明問題 “ 是什么 ” ； 要求則對問題進一步求精，劃出問題的邊界，指出具體的參量或前提條件，并規(guī)定該題的最低限度要求； 測試部分旨在為檢查學(xué)生上機作業(yè)提供方便，在完成實習(xí)題時應(yīng)自己設(shè)計完整和 嚴格的測試方案，當數(shù)據(jù)輸入量較大時，提倡以文件形式向程序提供輸入數(shù)據(jù)； 實現(xiàn)提示對實現(xiàn)中的難點及其解法思路等問題作了簡要提示，個別問題給出了參考實現(xiàn)。 下面帶 *的題目為選做題目。 上機實驗題目 實驗一 C語言相關(guān)知識復(fù)習(xí) 一、實驗?zāi)康? 復(fù)習(xí) C語言中函數(shù)、數(shù)組、結(jié)構(gòu)體、文件等概念，掌握它們的描述與操作方法；熟悉掌握 C++中 typedef、引用參數(shù)調(diào)用（ ）的概念及使用方法，為理解數(shù)據(jù)結(jié)構(gòu)課程的后續(xù)內(nèi)容以及算法書寫奠定基礎(chǔ)。 二、實驗內(nèi)容 問題描述：編寫一個函數(shù)，求一個整數(shù)數(shù)組中的最大、最小值。 要求：在函數(shù)聲明中采用引用參數(shù)傳遞方式實現(xiàn)最大、最小值的返回。測試：在主函數(shù)中輸入 10個數(shù)，調(diào)用此函數(shù)，打印輸出最大和最小值。 2 關(guān)于指針的使用： 用 malloc方式分別申請兩個指針，并實現(xiàn)兩個指針內(nèi)容的比較大小操作。要求：此功能在一個函數(shù)內(nèi)實現(xiàn)，該 函數(shù)接受兩個整數(shù)值，存儲到兩個指針內(nèi)容中，輸出兩者中的最大值。 測試：從主函數(shù)中輸入兩個數(shù)，調(diào)用該函數(shù)，打印輸出交換后的值。 實驗二 單鏈表的插入、刪除 一、實驗?zāi)康? 熟悉某種數(shù)據(jù)結(jié)構(gòu)在計算機上實現(xiàn)的方法。 掌握單鏈表的定義、創(chuàng)建、插入、刪除、遍歷等基本操作的實現(xiàn)。 體會單鏈表操作、有序表插入、刪除的一般方法。 二、實驗內(nèi)容 問題描述：已知遞增有序的單鏈表 A，編寫算法實現(xiàn)向 A中插入或刪除一個元素，并保持 A的有序性。 實驗要求： 結(jié)點的數(shù)據(jù)均為整型。 若表中已經(jīng)存在此元素，則不插入 三、實 現(xiàn)提示 ，需要下面的輔助函數(shù)：線性表的創(chuàng)建、線性表的遍歷 ，需依次實現(xiàn)： a)單鏈表結(jié)構(gòu)的定義 b)單鏈表的創(chuàng)建（頭插法或尾插法建表） c)單鏈表的遍歷 d)單鏈表的插入、刪除（采用順序查找方法，順頭指針往后，查找插入或刪除位置，再修改指針） //頭文件 include “” // 預(yù)定義常量 define NULL 0 //單鏈表的定義 typedef struct LNode{ int data。struct LNode *next。}LNode,*LinkList。//單鏈表的創(chuàng)建 void Create_List(LinkList L){ int data。LinkList p,q。L=(LinkList)malloc(sizeof(LNode))。Lnext=NULL。 q=L。 scanf(“%d”,data)。while(data!=0){ p=(LinkList)malloc(sizeof(LNode))。 pdata=data。 pnext=qnext。 qnext=p。 q=p。 scanf(“%d”,data)。} } //單鏈表的遍歷 void TranverseList(LinkList L){ LinkList p。 p=Lnext。 if(p==NULL) { printf(“niln”)。 return。 } while(p!=NULL) { printf(“%d ”,p data)。 p=pnext。 } printf(“n”)。} 實驗三 棧及其應(yīng)用 一、實驗?zāi)康? 熟悉棧的順序表示與實現(xiàn)。 熟悉棧的應(yīng)用。 理解并掌握遞歸函數(shù)的設(shè)計與實現(xiàn)。 二、實驗內(nèi)容 問題描述：利用棧實現(xiàn)十進制數(shù) n轉(zhuǎn)化為 d進制數(shù) 要求： 1)輸入一個 n和 d，打印輸出 d進制數(shù)序列。 2)利用順序棧來實現(xiàn)十進制數(shù) n轉(zhuǎn)化為其他 d進制數(shù)。此時，需要同時實現(xiàn)初始化空棧、入棧、出棧、判棧空等輔助功能。測試數(shù)據(jù)： （ 1）輸入 n:1348 d:8 輸出： 2504（ 2）輸入 n:9 d:8 輸出： 11（ 3）輸入 n:0 d:8 輸出： 0 2 問題描述：利用棧實現(xiàn)算術(shù)表達式求值。要求： 1)參與運算的操作數(shù)為 10 以內(nèi)的數(shù)值。測試數(shù)據(jù)： 自擬。 實驗四 二叉樹的遞歸算法 一、實驗?zāi)康? 掌握二叉樹 的表示與實現(xiàn)。 掌握二叉樹的定義、創(chuàng)建、遍歷等基本操作的實現(xiàn)。 熟悉求二叉樹深度等遞歸算法的設(shè)計與實現(xiàn)。 二、實驗內(nèi)容 問題描述：已知二叉樹 t，分別采用順序存儲結(jié)構(gòu)、二叉鏈表存儲結(jié)構(gòu)實現(xiàn)求二叉樹的深度，并對二叉樹分別進行中序遍歷。要求： 二叉樹分別采用順序或二叉鏈表存儲。 樹中的數(shù)據(jù)類型約定為整型。測試數(shù)據(jù)： 輸入序列： +a216。216。*b216。216。c216。216。d216。216。/e216。216。f216。216。創(chuàng)建二叉樹； 輸出：深度： 5 前序序列： +a*bcd/ef 中序序列： a+b*cde/f 后序序列： abcd*+ef/T:d / e f t=nil 輸入： 216。 輸出：深度： 0 實驗五 圖的遍歷 一、實驗?zāi)康? 熟悉圖的基本操作，掌握圖遍歷的設(shè)計與實現(xiàn)。 二、實驗內(nèi)容 問題描述：已知的描述校園景點的圖，實現(xiàn)對該圖的深度優(yōu)先和廣度優(yōu)先遍歷。要求： 圖采用鄰接矩陣存儲，頂點信息包括景點的名稱和簡單描述。 實驗六 有序表的查找 一、實驗?zāi)康? 理解各種查找方法的基本思想 熟悉有序表查找方法的算法實現(xiàn) 二、實驗內(nèi)容 已知一有序的序列 {1,3,5,7,9}，采用折半法分別查找 3和 6。 2已知輸入一無序的序列 {5,1,3,9,7}，創(chuàng)建一棵二叉排序樹，然后對其遍歷，輸出遞增有序的序列。 實驗七 哈希表 一、實驗?zāi)康? 理解哈希表的概念和基本操作；熟悉哈希表的創(chuàng)建、查找、插入的算法實現(xiàn)。 二、實驗內(nèi)容 問題描述：已知 11位好友的名字各不相同，設(shè)計并實現(xiàn)一個哈希表，根據(jù)好友的名字，可以取得其生日。要求： 好友的信息包含名字和生日兩個數(shù)據(jù)項，其中好友的名字為主鍵，用漢語拼音形式存放； 哈希函數(shù)采?。汉糜衙种兴衅匆糇帜?ASCII碼值的和 MOD 11(除以 1取余 )； 采取線性探測再散 列的方式處理沖突。 實驗八 內(nèi)部排序算法的應(yīng)用 一、實驗?zāi)康? 理解各種內(nèi)部排序方法的基本思想；熟悉各種內(nèi)部排序方法的算法實現(xiàn) 二、實驗內(nèi)容 問題描述：已知一序列 {503， 087， 512， 061， 908， 170， 897， 275， 653， 426}，分別采取下列排序方法對其進行排序： （ 1）直接插入排序； （ 2）簡單選擇排序； （ 3）起泡排序；（ 4）快速排序；（ 5）堆排序。 第三篇：數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)書 目 錄 實驗規(guī)則 2 實驗環(huán)境 2 實驗報告要求 3 實驗一 單鏈表 （一） 4 實驗二 單鏈表 （二） 5 實驗三 棧 18