第一篇：算法與數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)書
北 京 郵 電 大 學(xué)
計 算 機 科 學(xué) 與 技 術(shù) 學(xué) 院
算 法 與 數(shù) 據(jù) 結(jié) 構(gòu)
實 驗 指 導(dǎo) 書
楊俊、徐塞虹、漆濤 編著
2006年9月 算法與數(shù)據(jù)結(jié)構(gòu) 實驗指導(dǎo)書
目錄
實驗要求....................................................................................................................................3 試驗
一、約瑟夫環(huán)..............................................................................…………………..……4 試驗
二、長整數(shù)四則運算運算………………………………………………………………4 實驗三、八皇后.....................................……..........................................................................5 實驗
四、騎士遍歷......................................……………………..............................................5 實驗
五、桌面計算器...............................……………..............................................................6 實驗
六、平衡排序二叉樹....................…...…….....................................................................6 試驗
七、多重集合的實現(xiàn)……......................................………………………………………7 試驗
八、圖論………………………………………………………………………….……..8 實驗
八、內(nèi)部排序性能的比較..........………………….............................................................8 教材及主要參考文獻(xiàn)………………………………………………………………………………..9 2 北京郵電大學(xué) 計算機科學(xué)與技術(shù)學(xué)院 算法與數(shù)據(jù)結(jié)構(gòu) 實驗指導(dǎo)書
實驗要求
一、本課程在講課期間需要做上機實驗，目的之一是檢查學(xué)生對所學(xué)算法的掌握和理解程度；其次是鍛煉學(xué)生的團隊合作精神。
二、成績：
1、編碼：占整個實驗成績的50%；
2、測試：占整個實驗成績的20%；
3、文檔：占整個實驗成績的30%。
三、按時提交上機文檔，實驗文檔包含以下各項：
1、問題描述：實驗題目、內(nèi)容和要求；
2、算法思路：實驗小組對問題的解決方法的文字描述；
3、算法描述：用類算法語言等對算法進(jìn)行描述；
4、源程序及驅(qū)動程序：上機實驗編制的代碼源程序及程序運行環(huán)境；
5、測試數(shù)據(jù)：對算法的測試用例；
6、結(jié)果分析和結(jié)論：對算法及測試結(jié)果的分析及結(jié)論；
7、心得體會：通過實驗獲得的心得體會；
8、分工及簽名：最后是小組成員的分工及簽名。
北京郵電大學(xué) 計算機科學(xué)與技術(shù)學(xué)院-1-算法與數(shù)據(jù)結(jié)構(gòu) 實驗指導(dǎo)書
實驗
一、約瑟夫環(huán)
一、實驗類別：設(shè)計型實驗。
二、問題描述：約瑟夫環(huán)問題是：n個人p0,p1,…pn 圍坐成一個圓環(huán)。每個人pk持有一個秘密的數(shù)字ck。0 < ck <= m。開始時隨機選取一個數(shù) c = c0。每個人從p0 開始從1開始報數(shù)。報到數(shù)c 的人出對。然后以出隊的人的秘密數(shù)字作為新的c 值。從出隊者的下一個人順時針從1 開始再報數(shù)。直到所有的人全部出隊。
三、實驗?zāi)康模簷z查學(xué)生對各種線性表的實現(xiàn)的掌握程度。
四、實驗學(xué)時：2小時
五、實驗組人數(shù)：1人。
六、實驗設(shè)備環(huán)境：計算機。
七、實驗原理及要點（知識點）：各種隊列的實現(xiàn)。
八、實驗內(nèi)容和要求：至少用3種以上的線性表來完成此試驗?？梢栽趲ь^節(jié)點的和不帶頭節(jié)點的線性表、循環(huán)的和非循環(huán)線性表、動態(tài)鏈表和靜態(tài)鏈表以及向量（數(shù)組）之間選擇三種。從空表開始，為每個人生成一個隨機數(shù)。然后將此人加入到線性表之中。
九、可研究與探索的問題：給出各種實現(xiàn)的優(yōu)缺點比較。
十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。給出各種線性表實現(xiàn)的優(yōu)缺點分析。
實驗
二、長整數(shù)四則運算
一、實驗類別：驗證實驗。
二、問題描述：計算機CPU本身可以做32位或者64位的整數(shù)四則運算。本試驗要求對任意大小的整數(shù)實現(xiàn)其四則運算。將一個整數(shù)N表示為
N = ±(d0 + d1*B + d2*B2 + ….+ bk*Bk)
其中 1< B <= 256 為一個取定的整數(shù)。0 <= dk < B。用線性表存儲{bk}。給出整數(shù)的四則運算程序。
三、實驗?zāi)康模簩唧w的問題選擇適當(dāng)?shù)木€性表實現(xiàn)。
四、實驗學(xué)時：2小時
五、實驗組人數(shù)：3人。
六、實驗設(shè)備環(huán)境：計算機。
七、實驗原理及要點（知識點）：各種隊列的實現(xiàn)。
八、實驗內(nèi)容和要求：至少用2種以上的線性表來完成此試驗。比較不同線性表實現(xiàn)的速度。
九、可研究與探索的問題：1）對具體問題選擇合適的線性表實現(xiàn)。2）B 的選取問題?？?否選擇更大的基B。B的選擇所應(yīng)考慮的因素。
十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。能夠得出用向量（數(shù)組）實現(xiàn)的線性表速度最快。
實驗三、八皇后問題
一、實驗類別：設(shè)計型實驗。
二、問題描述：在n*n 的國際象棋棋盤上放置n個皇后，使每個皇后不受其他皇后的攻擊。
三、實驗?zāi)康模簷z查學(xué)生對堆棧和遞歸程序掌握程度。
四、實驗學(xué)時：2小時
五、實驗組人數(shù)：1人。
六、實驗設(shè)備環(huán)境：計算機。
七、實驗原理及要點（知識點）：遞歸程序與堆棧
八、實驗內(nèi)容和要求： 分別用遞歸和堆棧完成此試驗。統(tǒng)計程序運行時間與問題規(guī)模n 的關(guān)系。
九、可研究與探索的問題：問題的復(fù)雜度。當(dāng)n 比較大時，討論提高程序運行的方法。
十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。找出程序運行速度的瓶頸。
實驗
四、騎士遍歷
一、實驗類別：設(shè)計型實驗。
二、問題描述：在國際象棋n*n的棋盤中，一匹馬從棋盤中任意一格出發(fā)，要求用n2-1步走完所有的n2個格子。每個格子走且只走過一次。應(yīng)如何走？ 試給出算法實現(xiàn)。
三、實驗?zāi)康模簷z查學(xué)生對堆棧與回溯算法的掌握。
四、實驗學(xué)時：2小時
五、實驗組人數(shù)：3人。
六、實驗設(shè)備環(huán)境：計算機。
七、實驗原理及要點（知識點）：堆棧與回溯
八、實驗內(nèi)容和要求：用堆棧完成此試驗。統(tǒng)計程序運行時間與問題規(guī)模n 的關(guān)系。
九、可研究與探索的問題：怎樣枚舉所有馬下一步可走的位置。選擇下一步所走位置的策略。注意由于這個程序非常耗時，在初期程序調(diào)試時應(yīng)取較小的n。
十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。找出程序運行速度的瓶頸。給出不同選擇策略的程序運行 速度的比較結(jié)果。
實驗
五、桌面計算器（表達(dá)式求值）
一、實驗類別：設(shè)計型實驗。
二、問題描述：模仿Unix系統(tǒng)下的dc命令。輸入表達(dá)式字符串，按回車鍵后給出表達(dá)式的值。操作數(shù)為實數(shù)。
1）操作符有 “+”、“-”、“*”、“/”、“^”（乘方）
2）還可以有臨時變量。用法如 pi = 3.1415926，r = 3, r*pi^2 3）還可以有事先定義的函數(shù)如：“sin()”（正弦）、“cos()”（余弦）、“l(fā)og()”（對數(shù)）、“l(fā)n()”（自然對數(shù)）等函數(shù)。
三、實驗?zāi)康模簷z查學(xué)生用堆棧解決實際問題。為本課程后續(xù)的內(nèi)容提供伏筆。也為后繼的課程如編譯原理預(yù)習(xí)。
四、實驗學(xué)時：2小時
五、實驗組人數(shù)：3人。
六、實驗設(shè)備環(huán)境：計算機。
七、實驗原理及要點（知識點）：堆棧，線性表，命令行參數(shù)的處理。
八、實驗內(nèi)容和要求：學(xué)生應(yīng)至少應(yīng)實現(xiàn)處理五個運算符：“+”、“-”、“*”、“/”、“^”（乘方）?？梢杂靡粋€線性表來存儲臨時變量。另一個線性表來存儲預(yù)定義的函數(shù)名。
九、可研究與探索的問題：查找臨時變量名的不同方法。如哈希表，二叉樹。
十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。
實驗
六、平衡排序二叉樹
一、實驗類別：設(shè)計型實驗。
二、問題描述：隨機生成一組整數(shù)p0,p1,…pn－１。將這組整數(shù)按生成的次序插入到一個平衡排序二叉樹中。然后將p0,p1,…pn－１隨機重新排列為q0,q1,…qn－１。再按照次次序?qū)⑦@些整數(shù)從生成的平衡排序二叉樹刪除。
三、實驗?zāi)康模浩胶馀判蚨鏄涞牟迦牒蛣h除。
四、實驗學(xué)時：2小時
五、實驗組人數(shù)：3人。
六、實驗設(shè)備環(huán)境：計算機。
七、實驗原理及要點（知識點）：平衡排序二叉樹的插入和刪除中的旋轉(zhuǎn)。
八、實驗內(nèi)容和要求：統(tǒng)計在平衡排序二叉樹的插入和刪除過程中各種旋轉(zhuǎn)的出現(xiàn)次數(shù)。
九、可研究與探索的問題：研究平衡排序二叉樹與一般的排序二叉樹在插入和刪除方面的性能比較。
十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。給出在均勻的隨機分布下，平衡排序二叉樹與一般排序二叉樹的性能比較。
實驗
七、多重集合的實現(xiàn)
一、實驗類別：設(shè)計型實驗。
二、問題描述：實現(xiàn)數(shù)學(xué)上多重集合。所謂的多重集合類似于集合，但是一件東西可以放置多個副本。就如一個菜籃子里面可以放兩個蘋果。
三、實驗?zāi)康模翰檎医Y(jié)構(gòu)的各種實現(xiàn)。
四、實驗學(xué)時：2小時
五、實驗組人數(shù)：3人。
六、實驗設(shè)備環(huán)境：計算機。
七、實驗原理及要點（知識點）：平衡排序二叉樹的插入和刪除、遍歷，查找。哈希查找結(jié)構(gòu)。
八、實驗內(nèi)容和要求： 假設(shè)集合中包含的元素是可以排序的。將多重集合封裝成一個類。具體的實現(xiàn)可以是中序線索化的平衡排序二叉樹，或者帶父節(jié)點指針的平衡排序二叉樹。多重集合的界面如下：
template
{
Multi_set(void);//構(gòu)造函數(shù)，初始化為空集合~Multi_set(void);//析構(gòu)函數(shù)
Multi_set& operator=(Multi_set const a);//重載運算符=
bool contains(T const& v)const;//如果集合包含v 則返回true，否則返回false
Multi_set& operator+=(Multi_set const&a);//將集合a 并到自身中。
Multi_set& operator-=(Multi_set const& a);//自身減去集合a
Multi_set& operator-=(T const& a);//自身減去一個元素a
};//~class Multi_set
//返回集合a,b的并
template
//返回集合a,b的差
template
//返回 a –{v}
template
Multi_set
九、可研究與探索的問題：哈希函數(shù)的選取。比較哈希與平衡排序二叉樹的優(yōu)缺點、性能和速度。
十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。給出平衡排序二叉樹實現(xiàn)的多重集合和用哈希實現(xiàn)的多重集合的性能比較。
實驗
八、圖論
一、實驗類別：設(shè)計型實驗。
二、問題描述：實現(xiàn)圖論中的各種算法。
1）最小代價生成樹的Krscal 算法和Prim算法。2）單源點的最短路徑的Dijstra 算法。3）深度優(yōu)先遍歷與廣度優(yōu)先遍歷。4）拓?fù)渑判?/p>
5）求所有節(jié)點之間的最短路徑Floyd算法
（在這五個小題中只要選作一個即可。）
三、實驗?zāi)康模簩W(xué)習(xí)根據(jù)不同的運算來選取不同的存儲結(jié)構(gòu)。
四、實驗學(xué)時：2小時
五、實驗組人數(shù)：3人。
六、實驗設(shè)備環(huán)境：計算機。
七、實驗原理及要點（知識點）：圖論中的各種算法及其復(fù)雜度。根據(jù)不同的操作來決定圖的存儲結(jié)構(gòu)。
八、實驗內(nèi)容和要求：至少實現(xiàn)上面五個小題目中的一個。從文件中讀入一個圖的信息。
九、可研究與探索的問題：高級數(shù)據(jù)結(jié)構(gòu)如堆、并查集在圖論算法中的應(yīng)用。
十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。給出在均勻的隨機分布下，平衡排序二叉樹與一般排序二叉樹的性能比較。
實驗
九、內(nèi)部排序性能的比較
一、實驗類別：設(shè)計型實驗。
二、問題描述：隨機生成一組整數(shù)p0,p1,…pn－１。對這組數(shù)據(jù)進(jìn)行排序。
三、實驗?zāi)康模罕容^不同排序算法的性能。
四、實驗學(xué)時：2小時
五、實驗組人數(shù)：3人。
六、實驗設(shè)備環(huán)境：計算機。
七、實驗原理及要點（知識點）：各種內(nèi)部排序算法。
八、實驗內(nèi)容和要求： 1）實現(xiàn)插入排序，選擇排序，希爾排序，堆排序以及快速排序。2）快速排序的多種版本。3）對單鏈表實現(xiàn)歸并排序。4）基數(shù)排序。
5）對小型問題（n = 10）、中型問題（n = 1000）以及大型問題（n = 1百萬）分別統(tǒng)計不同排序算法的鍵值比較次數(shù)、鍵值移動次數(shù)以及程序運行時間。
26）排序算法的時間復(fù)雜度可以有O(n)和 O(n log n)。對相同復(fù)雜度的算法，給出他們運行時間與時間復(fù)雜度的比值。
九、可研究與探索的問題：研究快速排序算法的不同改進(jìn)方法。自省排序算法。只需要移動而不需要交換的快速排序方法。
十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。給出在均勻的隨機分布下，對大中小問題的最快的排序算法。
教材及主要參考文獻(xiàn)
[1] 嚴(yán)蔚敏、吳偉民，數(shù)據(jù)結(jié)構(gòu)習(xí)題集，清華大學(xué)出版社，1999年
[2] John R.Hubbard, Data Structures with C++, China Machine Press, 2002.[3] Mark Allen Weiss, Data Structures and Problem Solving Using C++, 2ed, 清華大學(xué)出版社。2004年。[4] Robert Sedgewick，Algorithms in C Part 1 – 4: Fundamentals, Data Structures, Sorting, rdSearching, 3, 中國電力出版社，2003年。
[5] 嚴(yán)蔚敏、吳偉民，數(shù)據(jù)結(jié)構(gòu)(C語言版)，清華大學(xué)出版社，2006年
第二篇：算法與數(shù)據(jù)結(jié)構(gòu)實驗
金陵科技學(xué)院實驗報告
學(xué) 生 實 驗 報 告 冊
課程名稱：
學(xué)生學(xué)號：
所屬院部：
（理工類）
算法與數(shù)據(jù)結(jié)構(gòu) 專業(yè)班級： 13網(wǎng)絡(luò)工程
1305106009 學(xué)生姓名： 陳韜
網(wǎng)絡(luò)與通信工程學(xué)院 指導(dǎo)教師： 沈奇 14 ——20 15 學(xué)年 第 1 學(xué)期
金陵科技學(xué)院教務(wù)處制
金陵科技學(xué)院實驗報告
實驗報告書寫要求
實驗報告原則上要求學(xué)生手寫，要求書寫工整。若因課程特點需打印的，要遵照以下字體、字號、間距等的具體要求。紙張一律采用A4的紙張。
實驗報告書寫說明
實驗報告中一至四項內(nèi)容為必填項，包括實驗?zāi)康暮鸵?；實驗儀器和設(shè)備；實驗內(nèi)容與過程；實驗結(jié)果與分析。各院部可根據(jù)學(xué)科特點和實驗具體要求增加項目。
填寫注意事項
（1）細(xì)致觀察，及時、準(zhǔn)確、如實記錄。（2）準(zhǔn)確說明，層次清晰。
（3）盡量采用專用術(shù)語來說明事物。
（4）外文、符號、公式要準(zhǔn)確，應(yīng)使用統(tǒng)一規(guī)定的名詞和符號。（5）應(yīng)獨立完成實驗報告的書寫，嚴(yán)禁抄襲、復(fù)印，一經(jīng)發(fā)現(xiàn)，以零分論處。
實驗報告批改說明
實驗報告的批改要及時、認(rèn)真、仔細(xì)，一律用紅色筆批改。實驗報告的批改成績采用百分制，具體評分標(biāo)準(zhǔn)由各院部自行制定。
實驗報告裝訂要求
實驗批改完畢后，任課老師將每門課程的每個實驗項目的實驗報告以自然班為單位、按學(xué)號升序排列，裝訂成冊，并附上一份該門課程的實驗大綱。
金陵科技學(xué)院實驗報告
實驗項目名稱： 順序表 實驗學(xué)時： 2 同組學(xué)生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間：
金陵科技學(xué)院實驗報告
實驗1 順序表
一、實驗?zāi)康暮鸵?/p>
掌握順序表的定位、插入、刪除等操作。
二、實驗儀器和設(shè)備
Turbo C 2.0/ Visual C++
三、實驗內(nèi)容與過程（含程序清單及流程圖）
1、必做題
（1）編寫程序建立一個順序表，并逐個輸出順序表中所有數(shù)據(jù)元素的值。編寫主函數(shù)測試結(jié)果。
（2）編寫順序表定位操作子函數(shù)，在順序表中查找是否存在數(shù)據(jù)元素x。如果存在，返回順序表中和x值相等的第1個數(shù)據(jù)元素的序號（序號從0開始編號）；如果不存在，返回－1。編寫主函數(shù)測試結(jié)果。（3）在遞增有序的順序表中插入一個新結(jié)點x，保持順序表的有序性。
解題思路：首先查找插入的位置，再移位，最后進(jìn)行插入操作；從第一個元素開始找到第一個大于該新結(jié)點值x的元素位置i即為插入位置；然后將從表尾開始依次將元素后移一個位置直至元素i；最后將新結(jié)點x插入到i位置。
（4）刪除順序表中所有等于X的數(shù)據(jù)元素。
2、選做題
（5）已知兩個順序表A和B按元素值遞增有序排列，要求寫一算法實現(xiàn)將A和B歸并成一個按元素值遞減有序排列的順序表（允許表中含有值相同的元素）。
程序清單：
#include
金陵科技學(xué)院實驗報告
} sequenlist;sequenlist L={{1,3,5,5,7,8,10,12,17},8};void print_list(){ int i;for(i=0;i<=L.last;i++)printf(“%4d”,L.data[i]);} void find_all_x(int x){ int found=0,i;for(i=0;i<=L.last;i++)if(L.data[i]==x){ printf(“%3d”,i+1);found=1;} if(found==0)printf(“-1n”);} void insert_x(int x){ int loc,i;for(i=0;i<=L.last;i++)if(x 金陵科技學(xué)院實驗報告 loc=i;for(i=L.last;i>=loc;i--)L.data[i+1]=L.data[i];L.data[loc]=x;L.last++;} void delete_x(int x){ int i,j,found=0;for(i=0;i<=L.last;i++)if(x==L.data[i]){ found=1;for(j=i+1;j<=L.last;j++)L.data[j-1]=L.data[j];i--;L.last--;} if(found==0)printf(“x is not foundn”);else { printf(“x is deletedn”);printf(“the list after deletion is:n”);print_list(); 金陵科技學(xué)院實驗報告 } } void main(){ int x,choice;while(1){ printf(“**********menu**********n”);printf(“ 1--printn”);printf(“ 2--searchn”);printf(“ 3--insertn”);printf(“ 4--deleten”);printf(“ 5--exitn”);printf(“please input your choice:”);scanf(“%d”,&choice); switch(choice){case 1: printf(“the original list is:n”);print_list();break;case 2: printf(“pls input x you want to search:n”); 金陵科技學(xué)院實驗報告 scanf(“%d”,&x);find_all_x(x);break;case 3: printf(“pls input x you want to insert:n”);scanf(“%d”,&x);insert_x(x);printf(“the list after insertion is:n”);print_list();break;case 4: printf(“pls input x you want to delete:n”);scanf(“%d”,&x);delete_x(x);printf(“the list after deletion is:n”);print_list();break;case 5: exit(0);} } } 金陵科技學(xué)院實驗報告 金陵科技學(xué)院實驗報告 四、實驗結(jié)果與分析（程序運行結(jié)果及其分析） 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學(xué)院實驗報告 實驗項目名稱： 單鏈表 實驗學(xué)時： 2 同組學(xué)生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學(xué)院實驗報告 實驗2 單鏈表 一、實驗?zāi)康暮鸵?/p> 1、實驗?zāi)康?/p> 掌握單鏈表的定位、插入、刪除等操作。 2、實驗要求 （1）注意鏈表的空間是動態(tài)分配的，某結(jié)點不用之后要及時進(jìn)行物理刪除，以便釋放其內(nèi)存空間。 （2）鏈表不能實現(xiàn)直接定位，一定注意指針的保存，防止丟失。 二、實驗儀器和設(shè)備 Turbo C 2.0/ Visual C++ 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）編寫程序建立一個單鏈表，并逐個輸出單鏈表中所有數(shù)據(jù)元素。（2）在遞增有序的單鏈表中插入一個新結(jié)點x，保持單鏈表的有序性。 解題思路：首先查找插入的位置然后進(jìn)行插入操作；從第一個結(jié)點開始找到第一個大于該新結(jié)點值的結(jié)點即為插入位置；然后在找到的此結(jié)點之前插入新結(jié)點；注意保留插入位置之前結(jié)點的指針才能完成插入操作。 （3）編寫實現(xiàn)帶頭結(jié)點單鏈表就地逆置的子函數(shù)，并編寫主函數(shù)測試結(jié)果。 2、選做題 已知指針LA和LB分別指向兩個無頭結(jié)點單鏈表的首元結(jié)點。要求編一算法實現(xiàn)，從表LA中刪除自第i個元素起共len個元素后，將它們插入到表LB中第j個元素之前。程序清單： 金陵科技學(xué)院實驗報告 金陵科技學(xué)院實驗報告 四、實驗結(jié)果與分析（程序運行結(jié)果及其分析） 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學(xué)院實驗報告 實驗項目名稱： 堆棧和隊列 實驗學(xué)時： 2 同組學(xué)生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學(xué)院實驗報告 實驗3 堆棧和隊列 一、實驗?zāi)康暮鸵?/p> （1）掌握應(yīng)用棧解決問題的方法。（2）掌握利用棧進(jìn)行表達(dá)式求和的算法。 （3）掌握隊列的存儲結(jié)構(gòu)及基本操作實現(xiàn)，并能在相應(yīng)的應(yīng)用問題中正確選用它們。 二、實驗儀器和設(shè)備 Turbo C 2.0/ Visual C++ 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）判斷一個算術(shù)表達(dá)式中開括號和閉括號是否配對。（2）測試“漢諾塔”問題。 （3）假設(shè)稱正讀和反讀都相同的字符序列為”回文”，試寫一個算法判別讀入的一個以’@’為結(jié)束符的字符序列是否是“回文”。 2、選做題 在順序存儲結(jié)構(gòu)上實現(xiàn)輸出受限的雙端循環(huán)隊列的入列和出列算法。設(shè)每個元素表示一個待處理的作業(yè)，元素值表示作業(yè)的預(yù)計時間。入隊列采取簡化的短作業(yè)優(yōu)先原則，若一個新提交的作業(yè)的預(yù)計執(zhí)行時間小于隊頭和隊尾作業(yè)的平均時間，則插入在隊頭，否則插入在隊尾。程序清單： 金陵科技學(xué)院實驗報告 四、實驗結(jié)果與分析（程序運行結(jié)果及其分析） 金陵科技學(xué)院實驗報告 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學(xué)院實驗報告 實驗項目名稱： 串 實驗學(xué)時： 2 同組學(xué)生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學(xué)院實驗報告 實驗4 串 一、實驗?zāi)康暮鸵?/p> 掌握串的存儲及應(yīng)用。 二、實驗儀器和設(shè)備 Turbo C 2.0/ Visual C++ 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）編寫輸出字符串s中值等于字符ch的第一個字符的函數(shù)，并用主函數(shù)測試結(jié)果。 （2）編寫輸出字符串s中值等于字符ch的所有字符的函數(shù)，并用主函數(shù)測試結(jié)果。 解題思路：可以將第一題程序改進(jìn)成一個子函數(shù)，在本題中循環(huán)調(diào)用。（3）設(shè)字符串采用單字符的鏈?zhǔn)酱鎯Y(jié)構(gòu)，編程刪除串s從位置i開始長度為k的子串。 2、選做題 假設(shè)以鏈結(jié)構(gòu)表示串，編寫算法實現(xiàn)將串S插入到串T中某個字符之后，若串T中不存在這個字符，則將串S聯(lián)接在串T的末尾。 提示：為提高程序的通用性，插入位置字符應(yīng)設(shè)計為從鍵盤輸入。程序清單： 金陵科技學(xué)院實驗報告 四、實驗結(jié)果與分析（程序運行結(jié)果及其分析） 金陵科技學(xué)院實驗報告 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學(xué)院實驗報告 實驗項目名稱： 二叉樹 實驗學(xué)時： 2 同組學(xué)生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學(xué)院實驗報告 實驗5 二叉樹 一、實驗?zāi)康暮鸵?/p> （1）掌握二叉樹的生成，以及前、中、后序遍歷算法。（2）掌握應(yīng)用二叉樹遞歸遍歷思想解決問題的方法。 二、實驗儀器和設(shè)備 Turbo C 2.0/ Visual C++ 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）建立一棵二叉樹。對此樹進(jìn)行前序遍歷、中序遍歷及后序遍歷，輸出遍歷序列。 （2）在第一題基礎(chǔ)上，求二叉樹中葉結(jié)點的個數(shù)。（3）在第一題基礎(chǔ)上，求二叉樹中結(jié)點總數(shù)。（4）在第一題基礎(chǔ)上，求二叉樹的深度。 2、選做題 已知一棵完全二叉樹存于順序表sa中，sa.elem[1…sa.last]存儲結(jié)點的值。試編寫算法由此順序存儲結(jié)構(gòu)建立該二叉樹的二叉鏈表。 解題思路：根據(jù)完全二叉樹順序存儲的性質(zhì)來確定二叉樹的父子關(guān)系即“還原”了二叉樹，之后再按照二叉樹二叉鏈表的構(gòu)造方法進(jìn)行建立。完全二叉樹順序存儲的一個重要性質(zhì)為，第i個結(jié)點的左孩子是編號為2i的結(jié)點，第i個結(jié)點的右孩子是編號為2i+1的結(jié)點。程序清單： 金陵科技學(xué)院實驗報告 四、實驗結(jié)果與分析（程序運行結(jié)果及其分析） 金陵科技學(xué)院實驗報告 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學(xué)院實驗報告 實驗項目名稱： 圖 實驗學(xué)時： 2 同組學(xué)生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學(xué)院實驗報告 實驗6 圖 一、實驗?zāi)康暮鸵?/p> （1）熟練掌握圖的基本概念、構(gòu)造及其存儲結(jié)構(gòu)。 （2）熟練掌握對圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷的算法。 二、實驗儀器和設(shè)備 Turbo C 2.0/ Visual C++ 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）構(gòu)造一個無向圖（用鄰接矩陣表示存儲結(jié)構(gòu)）。 （2）對上面所構(gòu)造的無向圖，進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，輸出遍歷序列。 2、選做題 采用鄰接表存儲結(jié)構(gòu)，編寫一個判別無向圖中任意給定的兩個頂點之間是否存在一條長度為k的簡單路徑的算法。簡單路徑是指其頂點序列中不含有重復(fù)頂點的路徑。提示：兩個頂點及k值均作為參數(shù)給出。程序清單： 金陵科技學(xué)院實驗報告 四、實驗結(jié)果與分析（程序運行結(jié)果及其分析） 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學(xué)院實驗報告 實驗項目名稱： 排序 實驗學(xué)時： 2 同組學(xué)生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學(xué)院實驗報告 實驗7 排序 一、實驗?zāi)康暮鸵?/p> （1）熟練掌握希爾排序、堆排序、直接插入排序、起泡排序、快速排序、直接選擇排序、歸并排序和基數(shù)排序的基本概念。 （2）掌握以上各種排序的算法。區(qū)分以上不同排序的優(yōu)、缺點。 二、實驗儀器和設(shè)備 Turbo C 2.0/ Visual C++ 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 用隨機數(shù)產(chǎn)生100000個待排序數(shù)據(jù)元素的關(guān)鍵字值。測試下列各排序函數(shù)的機器實際執(zhí)行時間（至少測試兩個）：直接插入排序、希爾排序（增量為4，2，1）、冒泡排序、快速排序、直接選擇排序、堆排序。 2、選做題 假設(shè)含n個記錄的序列中，其所有關(guān)鍵字為值介于v和w之間的整數(shù)，且其中很多關(guān)鍵字的值是相同的。則可按如下方法排序：另設(shè)數(shù)組number[v…w]，令number[i]統(tǒng)計關(guān)鍵字為整數(shù)i的紀(jì)錄個數(shù)，然后按number重排序列以達(dá)到有序。試編寫算法實現(xiàn)上述排序方法，并討論此種方法的優(yōu)缺點。程序清單： 金陵科技學(xué)院實驗報告 四、實驗結(jié)果與分析（程序運行結(jié)果及其分析） 金陵科技學(xué)院實驗報告 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學(xué)院實驗報告 實驗項目名稱： 查找 實驗學(xué)時： 2 同組學(xué)生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學(xué)院實驗報告 實驗8 查找 一、實驗?zāi)康暮鸵?/p> （1）掌握順序表查找、有序表查找、索引順序表查找的各種算法。（2）掌握哈希表設(shè)計。 二、實驗儀器和設(shè)備 Turbo C 2.0/ Visual C++ 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）在一個遞增有序的線性表中利用二分查找法查找數(shù)據(jù)元素X。 2、選做題 （2）構(gòu)造一個哈希表，哈希函數(shù)采用除留余數(shù)法，哈希沖突解決方法采用鏈地址法。設(shè)計一個測試程序進(jìn)行測試。 提示：構(gòu)造哈希表只是完成查找的第一步，大家應(yīng)該掌握在哈希表上進(jìn)行查找的過程，可以試著編程序?qū)崿F(xiàn)。程序清單： 金陵科技學(xué)院實驗報告 四、實驗結(jié)果與分析（程序運行結(jié)果及其分析） 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 《數(shù)據(jù)結(jié)構(gòu)》實驗(訓(xùn))指導(dǎo)書 電氣與信息工程學(xué)院實驗中心 前 言 《數(shù)據(jù)結(jié)構(gòu)》是計算機相關(guān)專業(yè)的一門核心基礎(chǔ)課程，也是很多高校研究生入學(xué)考試專業(yè)課必考課程之一。它主要介紹線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖形結(jié)構(gòu)三種邏輯結(jié)構(gòu)元素的存儲實現(xiàn)，在此基礎(chǔ)上介紹一些典型算法及時、空效率分析。這門課程的主要任務(wù)是培養(yǎng)學(xué)生的算法分析、設(shè)計能力及良好的程序設(shè)計習(xí)慣。通過學(xué)習(xí)，要求學(xué)生能夠掌握典型算法的設(shè)計思想及程序?qū)崿F(xiàn)，能夠根據(jù)實際問題選取合適的存儲方案，設(shè)計出簡潔、高效、實用的算法，為后續(xù)課程的學(xué)習(xí)及軟件開發(fā)打下良好的基礎(chǔ)。學(xué)習(xí)這門課程，習(xí)題和實驗是兩個關(guān)鍵環(huán)節(jié)。學(xué)生理解算法的最佳途徑是上機實驗。因此，實驗環(huán)節(jié)的好壞是學(xué)生能否學(xué)好《數(shù)據(jù)結(jié)構(gòu)》的關(guān)鍵。為了更好地配合學(xué)生實驗，特編寫該實驗指導(dǎo)書。 一、實驗?zāi)康?、要求和任?wù) 計算機編程中加工處理的對象是數(shù)據(jù)，而數(shù)據(jù)具有一定的組織結(jié)構(gòu)，所以學(xué)習(xí)編寫計算機程序僅僅了解計算機語言是不夠的，還必須掌握數(shù)據(jù)組織、存儲和運算的一般方法，這是數(shù)據(jù)結(jié)構(gòu)課程中學(xué)習(xí)和研究的內(nèi)容。由于數(shù)據(jù)結(jié)構(gòu)的原理和算法較抽象，而該課程一般在本科低年級開設(shè)，對于計算機程序設(shè)計知識的初學(xué)者，理解和掌握其中的原理就顯得較為困難。 1.熟練掌握C語言的編輯、編譯、調(diào)試程序。2.會書寫類C語言的算法，并將算法轉(zhuǎn)變?yōu)槌绦驅(qū)崿F(xiàn)。 3.正確理解各種數(shù)據(jù)結(jié)構(gòu)的邏輯特性和存儲表示和基本操作的算法實現(xiàn)。4.有較強的邏輯分析能力。 5.針對問題的不同選擇合適的數(shù)據(jù)結(jié)構(gòu)，提高算法設(shè)計的能力和動手實驗的技能。 6.學(xué)會分析研究計算機加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用設(shè)計的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及其相應(yīng)的算法，并初步掌握算法的時間分析和空間分析的技術(shù)。 7.本課程的學(xué)習(xí)過程也是復(fù)雜程序設(shè)計的訓(xùn)練過程，要求學(xué)生編寫的程序結(jié)構(gòu)清楚、正確易讀，符合軟件過程的規(guī)范，從而培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力。 8.通過若干數(shù)據(jù)結(jié)構(gòu)應(yīng)用實例，引導(dǎo)學(xué)生學(xué)習(xí)數(shù)據(jù)類型的使用，為今后學(xué)習(xí)面向?qū)ο蟮某绦蜃鲆恍╀亯|。 二、實驗基本內(nèi)容及學(xué)時分配 為了達(dá)到實驗?zāi)康?，本課程安排了4個實驗單元，訓(xùn)練的重點在于基本的數(shù)據(jù)結(jié)構(gòu)，而不是強調(diào)面面俱到。各實驗單元與教科書的各章只具有粗略的對應(yīng)關(guān)系，一個實驗題常常涉及到幾部分教學(xué)內(nèi)容?？倢W(xué)時：8學(xué)時。 1、線性表（2學(xué)時） （1）熟悉線性表的基本運算在兩種存儲結(jié)構(gòu)（順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)）上的實現(xiàn)；（2）以線性表的各種操作（建立、插入、刪除等）的實現(xiàn)為重點； （3）通過本次實驗幫助學(xué)生提高C語言的編程能力（特別是函數(shù)參數(shù)、指針類型、鏈表的使用）。 2、數(shù)組和廣義表（2學(xué)時）（1）掌握稀疏矩陣的壓縮存儲 （2）掌握稀疏矩陣的轉(zhuǎn)置算法 3、樹與二叉樹（2學(xué)時） 常見的二叉樹遍歷算法有先序遍歷，中序遍歷和后序遍歷算法。實現(xiàn)簡單的先序遍歷，中序遍歷和后序遍歷算法。 4、排序（2學(xué)時） 常見的內(nèi)部排序算法，插入類排序算法，如直接插入排序和希爾排序；交換類排序算法，如冒泡排序和快速排序；選擇類排序算法，如簡單選擇排序、樹形選擇類排序和堆排序。實冒泡排序或者直接插入排序算法。 三、說明 該課程采用理論與實踐相結(jié)合的教學(xué)方法，集知識性與趣味性于一體，達(dá)到良好的教學(xué)效果。硬件要求：在多媒體教室講解及演示。為保證教學(xué)順利進(jìn)行，要求實驗室提供電腦等設(shè)備。學(xué)生每次上機實驗都必須遵守實驗室的有關(guān)規(guī)定。 四、實驗報告規(guī)范 實驗報告的內(nèi)容包括： 1、實驗?zāi)康模赫f明實驗所驗證的知識點。 2、需求分析：以無歧義的陳述說明程序設(shè)計的任務(wù)、約束條件、輸入輸出要求、對功能的規(guī)定及模型。 3、邏輯設(shè)計：說明本程序中用到的所有抽象的數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次調(diào)用關(guān)系。 4、詳細(xì)設(shè)計：邏輯設(shè)計中定義的所有數(shù)據(jù)類型的實現(xiàn)，核心算法的設(shè)計描述、人機界面設(shè)計、函數(shù)之間調(diào)用關(guān)系的描述，主要功能的算法框架，測試數(shù)據(jù)設(shè)計。 5、測試分析：測試結(jié)果的分析與討論，測試過程中遇到的主要問題及采取的解決措施。 6、心得：軟件設(shè)計與實現(xiàn)過程中的經(jīng)驗與體會，進(jìn)一步改進(jìn)的設(shè)想。 7、程序清單：源程序中應(yīng)有足夠的注釋。如果提交源程序軟盤，列出程序文件名。 五、如何提高上機效率 為了提高上機的效率，真正達(dá)到實驗?zāi)康?，要求同學(xué)做好實驗前的準(zhǔn)備工作，寫好實驗預(yù)習(xí)報告，即實驗報告規(guī)范中的1）、2）、3）、4）部分，編寫好程序，并用一組測試數(shù)據(jù)手工執(zhí)行程序靜態(tài)檢查程序是否有錯，通過閱讀、執(zhí)行程序或給別人講解自己的程序而深入全面地理解程序邏輯，提高程序的正確性。對C語言程序不熟悉的同學(xué)，上機時最好帶上C語言程序設(shè)計的教材，以備查閱。調(diào)試中遇到問題，應(yīng)認(rèn)真分析，確定可疑點，設(shè)置調(diào)試斷點或輸出斷點處變量的值，以便發(fā)現(xiàn)問題，迅速排除問題，加快調(diào)試速度。 實驗室要求： 不能曠課，不遲到，不穿拖鞋進(jìn)實驗室 實驗需預(yù)習(xí)報告（不能單純抄寫，預(yù)習(xí)程序代碼）實驗報告（總結(jié)，注釋，實驗結(jié)果） 目 錄 實驗一 線性表實驗（設(shè)計性實驗）..........................................4 實驗二 數(shù)組和廣義表實驗（設(shè)計性實驗）....................................6 實驗三 樹與二叉樹（設(shè)計性實驗）..........................................8 實驗四 排序（設(shè)計性實驗）................................................9 實驗一 線性表實驗（設(shè)計性實驗） 一、實驗?zāi)康?/p> 1.熟悉C語言的上機環(huán)境，進(jìn)一步掌握C語言的結(jié)構(gòu)特點。2.掌握線性表的順序存儲結(jié)構(gòu)的定義及C語言實現(xiàn)。 3.掌握線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)——單鏈表的定義及C語言實現(xiàn)。4.掌握線性表在順序存儲結(jié)構(gòu)即順序表中的各種基本操作。5.掌握線性表在鏈?zhǔn)酱鎯Y(jié)構(gòu)——單鏈表中的各種基本操作。 二、實驗內(nèi)容 1.順序線性表的建立、插入及刪除。2.鏈?zhǔn)骄€性表的建立、插入及刪除。 三、實驗儀器設(shè)備與器材 上機電腦 四、實驗步驟 1.建立含n個數(shù)據(jù)元素的順序表并輸出該表中各元素的值及順序表的長度。 2.利用前面的實驗先建立一個順序表L={21，23，14，5，56，17，31}，然后在第i個位置插入元素68。 3.建立一個帶頭結(jié)點的單鏈表，結(jié)點的值域為整型數(shù)據(jù)。要求將用戶輸入的數(shù)據(jù)按尾插入法來建立相應(yīng)單鏈表。 五、實驗提示 1.由于C語言的數(shù)組類型也有隨機存取的特點，一維數(shù)組的機內(nèi)表示就是順序結(jié)構(gòu)。因此，可用C語言的一維數(shù)組實現(xiàn)線性表的順序存儲。 在此，我們利用C語言的結(jié)構(gòu)體類型定義順序表： #define MAXSIZE 1024 typedef int elemtype;/* 線性表中存放整型元素 */ typedef struct { elemtype vec[MAXSIZE];int len;/* 順序表的長度 */ }sequenlist;將此結(jié)構(gòu)定義放在一個頭文件sqlist.h里，可避免在后面的參考程序中代碼重復(fù)書寫，另外在該頭文件里給出順序表的建立及常量的定義。 2.注意如何取到第i個元素，在插入過程中注意溢出情況以及數(shù)組的下標(biāo)與位序（順序表中元素的次序）的區(qū)別。 3.單鏈表的結(jié)點結(jié)構(gòu)除數(shù)據(jù)域外，還含有一個指針域。用C語言描述結(jié)點結(jié)構(gòu)如下： typedef int elemtype;typedef struct node { elemtype data;//數(shù)據(jù)域 struct node *next;//指針域 }linklist; 注意結(jié)點的建立方法及構(gòu)造新結(jié)點時指針的變化。構(gòu)造一個結(jié)點需用到C語言的標(biāo)準(zhǔn)函數(shù)malloc()，如給指針變量p分配一個結(jié)點的地址： p=(linklist *)malloc(sizeof(linklist));該語句的功能是申請分配一個類型為linklist的結(jié)點的地址空間，并將首地址存入指針變量p 中。當(dāng)結(jié)點不需要時可以用標(biāo)準(zhǔn)函數(shù)free(p)釋放結(jié)點存儲空間，這時p為空值（NULL）。 六、實驗總結(jié)與思考 1.如果按由表尾至表頭的次序輸入數(shù)據(jù)元素，應(yīng)如何建立順序表。2.在main函數(shù)里如果去掉L=&a語句，會出現(xiàn)什么結(jié)果？ 實驗二 數(shù)組和廣義表實驗（設(shè)計性實驗） 一、實驗?zāi)康?/p> 1.掌握稀疏矩陣的壓縮存儲 2.掌握稀疏矩陣的轉(zhuǎn)置算法 二、實驗內(nèi)容 1.實現(xiàn)上三角陣的壓縮存儲。 2.用三元組順序表存儲稀疏矩陣，并實現(xiàn)矩陣的轉(zhuǎn)置。 三、實驗儀器設(shè)備與器材 上機電腦 四、實驗步驟 1.創(chuàng)建一個數(shù)組。2.輸入數(shù)據(jù) 3.給定矩陣任一元素的下標(biāo)，4.打印給定下標(biāo)所對應(yīng)的數(shù)據(jù)。5.創(chuàng)建三元組順序表。?a22 7.A輸出對應(yīng)的矩陣。?? 21五、實驗提示 ?aaa6.輸入矩陣中的數(shù)據(jù)。?11?a11??a?313233a2122?1.對于如下對稱矩陣： ??A?aaa?4243?41?a31a32a33??1個位置，a21存入到第二個位置，?將它們存入到一個線性數(shù)組中B，不存非零元素，a11存入到第a41a42aija44????aij的位則aij能存到第幾個位置，我們要以用梯形公式算面積。置是它上面的元素之和再加上左邊的元素之和。 它上面的元素之和為((1+(i-1))×(i-1)/2，左邊的元素為(j-1)所以這個元素存儲的位置為k=i(i-1)/2+j-1。 因為矩陣A為對稱矩陣，(另一部分沒有寫出)，所以另一部分的元素為 k=j(j-1)/2+i-1.所以存在關(guān)系k=i(i-1)/2+j-1(i>j)和k=j(j-1)/2+i-1(i 2.結(jié)點結(jié)構(gòu) struct triple{ int i,j;//非零元的行下標(biāo)和列下標(biāo) elemtype e;//非零元數(shù)據(jù)} 三元組順序表存儲類型 struct tsmatrix{ triple data[12500];aa?????a44?? int mu,nu,tu;} 三元順序表的轉(zhuǎn)置 方法：(1)將矩陣行列互換，(2)重排矩陣 六、實驗總結(jié)與思考 1.如何存儲三對角陣？ 2.如何用行邏輯鏈接順序表及十字鏈表存儲稀疏矩陣？ 實驗三 樹與二叉樹（設(shè)計性實驗） 一、實驗?zāi)康?/p> 1.掌握稀疏矩陣的壓縮存儲 2.掌握稀疏矩陣的轉(zhuǎn)置算法 二、實驗內(nèi)容 1.練習(xí)二叉樹的建立與存儲 2.練習(xí)二叉樹的遍歷 三、實驗儀器設(shè)備與器材 上機電腦 四、實驗步驟 1.建立自己的頭文件BT.H，內(nèi)容包括二叉鏈表的結(jié)構(gòu)描述、二叉樹的建立、二叉樹的先序、中序與后序遍歷算法。 2.建立二叉樹,并通過調(diào)用函數(shù),，輸出先序遍歷、中序遍歷與后序遍歷的結(jié)果。 五、實驗提示 建立二叉樹的代碼如下： BTCHINALR * createbt(){ BTCHINALR *q;struct node1 *s[30];int j,i,x;printf(“建立二叉樹，輸入結(jié)點對應(yīng)的編號和值,編號和值之間用逗號隔開nn”);printf(“i,x = ”);scanf(“%d,%c”,&i,&x);while(i!= 0 && x!= '$') {q =(BTCHINALR*)malloc(sizeof(BTCHINALR));/*建立一個新結(jié)點q*/ q->data = x;q->lchild = NULL;q->rchild = NULL; s[i] = q;/*q新結(jié)點地址存入s指針數(shù)組中*/ if(i!= 1)/*i = 1，對應(yīng)的結(jié)點是根結(jié)點*/ {j = i / 2;/*求雙親結(jié)點的編號j*/ if(i % 2 == 0)s[j]->lchild = q;/*q結(jié)點編號為偶數(shù)則掛在雙親結(jié)點j的左邊*/ else s[j]->rchild = q;} /*q結(jié)點編號為奇數(shù)則掛在雙親結(jié)點j的右邊*/ printf(“i,x = ”); scanf(“%d,%c”,&i,&x);} return s[1];/*返回根結(jié)點地址*/ } 六、實驗總結(jié)與思考 1.如何用孩子兄弟表示法存儲樹？ 2.熟悉及難赫夫曼樹。 實驗四 排序（設(shè)計性實驗） 一、實驗?zāi)康?/p> 1.掌握常用的排序方法，并掌握用高級語言實現(xiàn)排序算法的方法； 2.深刻理解排序的定義和各種排序方法的特點，并能加以靈活應(yīng)用； 3.了解各種方法的排序過程及其時間復(fù)雜度的分析方法。 二、實驗內(nèi)容 統(tǒng)計成績 給出n個學(xué)生的考試成績表，每條信息由姓名和分?jǐn)?shù)組成，試設(shè)計一個算法： （1）按分?jǐn)?shù)高低次序，打印出每個學(xué)生在考試中獲得的名次，分?jǐn)?shù)相同的為同一名次；（2）按名次列出每個學(xué)生的姓名與分?jǐn)?shù)。 三、實驗儀器設(shè)備與器材 上機電腦 四、實驗步驟 1.定義結(jié)構(gòu)體。2.定義結(jié)構(gòu)體數(shù)組。 3.定出主程序，對數(shù)據(jù)進(jìn)行排序。 五、實驗提示 #define n 30 typedef struct student { char name[8];int score;} student R[n];main(){ int num, i, j, max, temp;printf(“n請輸入學(xué)生成績: n”);for(i=0;i if(max!=i){ temp = R[max];R[max]=R[i];R[i]= temp;} if((i>0)&&(R[i].score 六、實驗總結(jié)與思考 1.快速排序算法解決本問題。2.較各種排序算法的優(yōu)缺點及。 3.使用其它排序算法實現(xiàn)該問題（直接插入排序、希爾排序、簡單選擇排序、堆排序等）。 數(shù) 據(jù) 結(jié) 構(gòu) 實 驗 指 導(dǎo) 書 南京工程學(xué)院 信息管理與信息系統(tǒng)教研室 2014年3月 實驗一 線性表操作 一、實驗?zāi)康?/p> 1.熟悉C語言的上機環(huán)境，進(jìn)一步掌握C語言的結(jié)構(gòu)特點。2.掌握線性表的順序存儲結(jié)構(gòu)的定義及C語言實現(xiàn)。 3.掌握線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)——單鏈表的定義及C語言實現(xiàn)。4.掌握線性表在順序存儲結(jié)構(gòu)即順序表中的各種基本操作。5.掌握線性表在鏈?zhǔn)酱鎯Y(jié)構(gòu)——單鏈表中的各種基本操作。 二、實驗內(nèi)容 1.順序線性表的建立、插入及刪除。 2.鏈?zhǔn)骄€性表的建立、插入及刪除。 三、實驗步驟 1.建立含n個數(shù)據(jù)元素的順序表并輸出該表中各元素的值及順序表的長度。2.利用前面的實驗先建立一個順序表L={21，23，14，5，56，17，31}，然后在第i個位置插入元素68。 3.建立一個帶頭結(jié)點的單鏈表，結(jié)點的值域為整型數(shù)據(jù)。要求將用戶輸入的數(shù)據(jù)按尾插入法來建立相應(yīng)單鏈表。 四、實現(xiàn)提示 1.由于C語言的數(shù)組類型也有隨機存取的特點，一維數(shù)組的機內(nèi)表示就是順序結(jié)構(gòu)。因此，可用C語言的一維數(shù)組實現(xiàn)線性表的順序存儲。 在此，我們利用C語言的結(jié)構(gòu)體類型定義順序表： #define MAXSIZE 1024 typedef int elemtype;/* 線性表中存放整型元素 */ typedef struct { elemtype vec[MAXSIZE];int len;/* 順序表的長度 */ }sequenlist;將此結(jié)構(gòu)定義放在一個頭文件sqlist.h里，可避免在后面的參考程序中代碼重復(fù)書寫，另外在該頭文件里給出順序表的建立及常量的定義。 2.注意如何取到第i個元素，在插入過程中注意溢出情況以及數(shù)組的下標(biāo)與位序（順序表中元素的次序）的區(qū)別。 3.單鏈表的結(jié)點結(jié)構(gòu)除數(shù)據(jù)域外，還含有一個指針域。用C語言描述結(jié)點結(jié)構(gòu)如下： typedef int elemtype;typedef struct node { elemtype data;//數(shù)據(jù)域 struct node *next;//指針域 }linklist;注意結(jié)點的建立方法及構(gòu)造新結(jié)點時指針的變化。構(gòu)造一個結(jié)點需用到C語言的標(biāo)準(zhǔn)函數(shù)malloc()，如給指針變量p分配一個結(jié)點的地址： p=(linklist *)malloc(sizeof(linklist));該語句的功能是申請分配一個類型為linklist的結(jié)點的地址空間，并將首地址存入指針變量p 中。當(dāng)結(jié)點不需要時可以用標(biāo)準(zhǔn)函數(shù)free(p)釋放結(jié)點存儲空間，這時p為空值（NULL）。 五、思考與提高 1.如果按由表尾至表頭的次序輸入數(shù)據(jù)元素，應(yīng)如何建立順序表。2.在main函數(shù)里如果去掉L=&a語句，會出現(xiàn)什么結(jié)果？ 實驗二 棧和隊列的應(yīng)用 一、實驗?zāi)康?/p> 1.掌握棧的順序表示和實現(xiàn) 2.掌握隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn) 二、實驗內(nèi)容 1.編寫一個程序?qū)崿F(xiàn)順序棧的各種基本運算。2.實現(xiàn)隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)。 三、實驗步驟 1.順序棧(1)初始化順序棧;(2)插入元素(3)刪除棧頂元素(4)取棧頂元素(5)遍歷順序棧(6)置空順序棧 2.鏈隊列 (1)初始化并建立鏈隊列(2.)入鏈隊列(3)出鏈隊列(4)遍歷鏈隊列 四、實現(xiàn)提示 1./*定義順序棧的存儲結(jié)構(gòu)*/ typedef struct { ElemType stack[MAXNUM];int top;}SqStack; /*初始化順序棧函數(shù)*/ void InitStack(SqStack *p) {q=(SqStack*)malloc(sizeof(SqStack));/*申請空間*/} /*入棧函數(shù)*/ void Push(SqStack *p,ElemType x){if(p->top SqStack S; ElemType e; int N; /*初始化順序棧*/ /*入棧*/ /*出棧*/ /*遍歷順序棧*/ getch();} 2./*定義鏈隊列*/ typedef struct Qnode { ElemType data;struct Qnode *next;}Qnodetype;typedef struct { Qnodetype *front;Qnodetype *rear;}Lqueue; /*初始化并建立鏈隊列函數(shù)*/ void creat(Lqueue *q) { h=(Qnodetype*)malloc(sizeof(Qnodetype));/*初始化申請空間*/ h->next=NULL;q->front=h;q->rear=h;for(i=1;i<=n;i++)*利用循環(huán)快速輸入數(shù)據(jù)*/ { scanf(“%d”,&x);Lappend(q,x);} /*利用入鏈隊列函數(shù)快速輸入數(shù)據(jù)*/ } /*入鏈隊列函數(shù)*/ void Lappend(Lqueue *q,int x){ s->data=x;s->next=NULL;q->rear->next=s;q->rear=s;} /*出鏈隊列函數(shù)*/ ElemType Ldelete(Lqueue *q){ p=q->front->next;q->front->next=p->next;if(p->next==NULL)q->rear=q->front;x=p->data;free(p);} /*釋放空間*/ /*遍歷鏈隊列函數(shù)*/ void display(Lqueue *q){ while(p!=NULL)/*利用條件判斷是否到隊尾*/ { printf(“%d-->”,p->data);p=p->next;} } 可參考如下代碼： #include “stdio.h” #define MaxSize 100 typedef int ElemType;main(){ LinkQueue Q; ElemType e; /*初始化并建立鏈隊列*/ /*入鏈隊列*/ /*出鏈隊列*/ *遍歷鏈隊列*/ } DestoryQueue(&Q); getch();} 五、思考與提高 1.讀棧頂元素的算法與退棧頂元素的算法有何區(qū)別？ 試寫一個算法，判別讀入的一個以‘@’為結(jié)束符的字符序列是否是?回文?。實驗三 樹操作 一、實驗?zāi)康?/p> 1.通過實驗，掌握二叉樹的建立與存儲 2.通過實驗，掌握二叉樹的遍歷方法 二、實驗內(nèi)容 1.練習(xí)二叉樹的建立與存儲 2.練習(xí)二叉樹的遍歷 三、實驗步驟 1.建立二叉鏈表的結(jié)構(gòu)描述、二叉樹的建立、二叉樹的先序、中序與后序遍歷算法。 2.建立二叉樹,并通過調(diào)用函數(shù), 輸出先序遍歷、中序遍歷與后序遍歷的結(jié)果。 四、實現(xiàn)提示 1.采用遞歸方法建立二叉樹： 首先建立二叉樹的根 結(jié)點，然后建立其左右子樹，直到空子樹為止。 2.先序遍歷、中序遍歷與后序遍歷二叉樹。#include BiTree CreateBiTree(BiTree &T){ } /*先序遍歷*/ Status PreOrderTraverse(BiTree T){ } /*中序遍歷*/ Status InOrderTraverse(BiTree T){ } /*后序遍歷*/ Status PostOrderTraverse(BiTree T){ } int main(){ BiTree T;CreateBiTree(T);PreOrderTraverse(T);printf(“n”);/*先序遍歷*/ InOrderTraverse(T);printf(“n”);/*中序遍歷*/ PostOrderTraverse(T);printf(“n”);/*后序遍歷*/ return 0;} 五、思考與提高 編寫遞歸算法，計算二叉樹中葉子結(jié)點的數(shù)目。 目 錄 實驗規(guī)則················································2 實驗環(huán)境················································2 實驗報告要求············································3 實驗一 單鏈表 （一）······································4 實驗二 單鏈表 （二）······································5 實驗三 ?！ぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁ? 實驗四 二叉樹···········································7 實驗五 最短路徑·········································8 實驗六 內(nèi)部排序·········································9 實 驗 規(guī) 則 為了順利完成實驗教學(xué)任務(wù)，確保人身、設(shè)備的安全，培養(yǎng)嚴(yán)謹(jǐn)、踏實、實事求是的科學(xué)作風(fēng)和愛護(hù)國家財產(chǎn)的優(yōu)良品質(zhì)，特制定以下實驗規(guī)則： 1、實驗前必須充分預(yù)習(xí)，完成指定的預(yù)習(xí)任務(wù)。預(yù)習(xí)要求如下： （1）認(rèn)真閱讀指導(dǎo)書，進(jìn)行必要的設(shè)計與計算。（2）熟悉實驗內(nèi)容。 （3）預(yù)先復(fù)習(xí)，并按要求編寫程序。（4）未完成預(yù)習(xí)任務(wù)者不得進(jìn)入實驗室。 2、遵守以下紀(jì)律： （1）在實驗室不得做和實驗無關(guān)的事情。 （2）進(jìn)行任課老師指定內(nèi)容以外的實驗，必須經(jīng)指導(dǎo)教師同意。（3）遵守紀(jì)律，不遲到。 （4）保持實驗室內(nèi)安靜、整潔，愛護(hù)公物，不許亂寫亂畫。 實 驗 環(huán) 境 本實驗在386以上的微機上進(jìn)行，運行環(huán)境為VC6.0。 實驗報告要求 1、實驗題目 2．實驗?zāi)康?3．實驗環(huán)境 4．實驗內(nèi)容與完成情況（可以附上自主設(shè)計的源程序）5．出現(xiàn)的問題及對問題的解決方案 6．實驗思考：（學(xué)生對本次實驗的收獲的總結(jié)） 實驗一 單鏈表 （一）一、實驗?zāi)康?/p> 掌握線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其基本操作。 二、預(yù)習(xí)要求 1、看懂書上的算法，深入理解鏈表的物理存儲模式和邏輯模式。 2、根據(jù)要求，編寫程序準(zhǔn)備上機調(diào)試。 三、實驗內(nèi)容 實現(xiàn)一個簡單的學(xué)生信息管理系統(tǒng)，該系統(tǒng)的功能有： 1、利用單鏈表建立學(xué)生基本信息表 2、瀏覽每個學(xué)生的信息 3、根據(jù)學(xué)號查詢某個學(xué)生的基本信息 4、添加學(xué)生信息到單鏈表中 5、刪除一個學(xué)生的信息 四、實現(xiàn)提示 設(shè)計結(jié)點的結(jié)構(gòu)體類型，包括學(xué)生的學(xué)號、姓名、年齡、性別；要求設(shè)計一個簡單的菜單界面，根據(jù)需要選擇所要進(jìn)行的操作；構(gòu)造函數(shù)，每一個函數(shù)實現(xiàn)上述的一個功能。 實驗二 單鏈表 （二）一、實驗?zāi)康?/p> 掌握線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其基本操作。 二、預(yù)習(xí)要求 1、看懂書上的算法，深入理解鏈表的物理存儲模式和邏輯模式。 2、根據(jù)要求，編寫程序準(zhǔn)備上機調(diào)試。 三、實驗內(nèi)容 1、實現(xiàn)單鏈表的就地逆置。 2、建立兩個非遞減有序單鏈表，然后合并成一個非遞減鏈表。 3、建立兩個非遞減有序單鏈表，然后合并成一個非遞增鏈表。 4、編寫一個主函數(shù),調(diào)試上述算法。 四、選做題、思考題 1、如何用帶表頭結(jié)點的單鏈表作為多項式的存儲表示，實現(xiàn)兩個多項式的相加。 2、約毖夫環(huán)的實現(xiàn)。 3、如何利用文件實現(xiàn)學(xué)生信息的存取。 實驗三 棧 一、實驗?zāi)康?/p> 深入了解并掌握棧的特性及其在實際中的應(yīng)用；熟練掌握棧的算法實現(xiàn)；運用棧操作求解實際問題。 二、預(yù)習(xí)要求 1、看懂書上的算法，深入理解棧的特性和存儲結(jié)構(gòu)，以便在實際問題背景下靈活運用。 2、根據(jù)要求，編寫程序準(zhǔn)備上機調(diào)試。 三、實驗內(nèi)容 利用棧實現(xiàn)數(shù)據(jù)的分類，要求當(dāng)輸入為偶數(shù)時進(jìn)棧1，當(dāng)輸入為奇數(shù)時進(jìn)棧2，最后分別從棧1和棧2輸出偶數(shù)和奇數(shù)序列。 四、實現(xiàn)提示 1、開辟一個連續(xù)的存儲空間，實現(xiàn)兩個棧順序存儲空間的共享；分別在兩端設(shè)置棧頂指針，并按要求實現(xiàn)棧操作。 2、采用順序存儲實現(xiàn)棧的初始化、入棧、出棧操作。 五、選做題、思考題 1、兩棧空間共享時，棧滿的條件是什么？ 2、為停車場編制進(jìn)行管理的模擬程序（習(xí)題集P96，2.1）。 3、編寫程序，利用棧實現(xiàn)表達(dá)式求值。 實驗四 二叉樹 一、實驗?zāi)康?/p> 通過實踐掌握二叉樹的存儲結(jié)構(gòu)和遍歷思想；掌握二叉樹的常見算法的程序?qū)崿F(xiàn)。 二、預(yù)習(xí)要求 二叉樹的三種遍歷方法。 三、實驗內(nèi)容 1、輸入字符序列，建立二叉鏈表。 2、利用棧，編寫非遞歸算法，編程實現(xiàn)二叉樹的中序遍歷。 3、求二叉樹的葉子結(jié)點個數(shù)。 4、在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。 四、選做題、思考題 1、如何實現(xiàn)二叉樹的后序遍歷（非遞歸）。 2、如何求二叉樹的高度。 實驗五 最短路徑（旅游景點導(dǎo)游咨詢模擬） 一、實驗?zāi)康?/p> 利用圖的最短路徑原理為用戶提供路徑咨詢，掌握求最短路徑的算法并編程實現(xiàn)。 二、預(yù)習(xí)要求 學(xué)習(xí)了解圖的存儲結(jié)構(gòu)，掌握求最短路徑的兩種算法。 三、實驗內(nèi)容 設(shè)計一個旅游景點導(dǎo)游模擬程序，為來訪的客人提供景點最短路徑的信息查詢服務(wù)，任意選取n城市，構(gòu)成一個有向帶權(quán)圖，圖中頂點表示城市，邊上的權(quán)值表示兩點間的距離，根據(jù)用戶指定的始點和終點輸出相應(yīng)的最短路徑。 四、實現(xiàn)提示 咨詢以用戶和計算機的對話方式進(jìn)行，由用戶輸入起始點和終點，輸出信息：最短路徑是多少？并指出所經(jīng)過的城市。存儲結(jié)構(gòu)可選用鄰接矩陣。 五、選做題、思考題 1．如何實現(xiàn)對城市信息進(jìn)行編輯（如：添加或刪除）的功能。 2．用鄰接表作存儲結(jié)構(gòu)，求一指定景點出發(fā)，到其余各景點的最短路徑。 實驗六 內(nèi)部排序 一、實驗?zāi)康?/p> 直觀感受算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)。 二、預(yù)習(xí)要求 1、常見的排序算法(插入排序、交換排序、選擇排序、歸并排序、基數(shù)排序等)的思想、特點及其適用條件。 2、根據(jù)要求，編寫程序準(zhǔn)備上機調(diào)試。 三、實驗內(nèi)容 1、對直接插入排序和簡單選擇排序算法進(jìn)行關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)的比較。 2、利用鏈?zhǔn)酱鎯Y(jié)構(gòu)，編寫程序，實現(xiàn)直接插入排序和冒泡排序。 四、實現(xiàn)提示 測試數(shù)據(jù)可以為幾組典型的數(shù)據(jù)：正序、逆序、亂序。 五、選做題、思考題 1、快速排序算法的非遞歸實現(xiàn)。 2、結(jié)合實驗，理解針對不同待排元素的特點而選擇不同排序方法的重要性。 3、如何對本實驗進(jìn)行時間、空間的復(fù)雜度分析。第三篇：《數(shù)據(jù)結(jié)構(gòu)》實驗指導(dǎo)書
第四篇：《數(shù)據(jù)結(jié)構(gòu)》實驗指導(dǎo)書
第五篇：數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)書
點擊咨詢 