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