【正文】 個小題目中的一個。九、可研究與探索的問題：高級數(shù)據(jù)結(jié)構(gòu)如堆、并查集在圖論算法中的應(yīng)用。要求程序必須上機編譯通過并且正確運行。給出在均勻的隨機分布下，平衡排序二叉樹與一般排序二叉樹的性能比較。二、問題描述：隨機生成一組整數(shù)p0,p1,…pn－１。三、實驗?zāi)康模罕容^不同排序算法的性能。六、實驗設(shè)備環(huán)境：計算機。八、實驗內(nèi)容和要求： 1）實現(xiàn)插入排序，選擇排序，希爾排序，堆排序以及快速排序。3）對單鏈表實現(xiàn)歸并排序。5）對小型問題（n = 10）、中型問題（n = 1000）以及大型問題（n = 1百萬）分別統(tǒng)計不同排序算法的鍵值比較次數(shù)、鍵值移動次數(shù)以及程序運行時間。對相同復雜度的算法，給出他們運行時間與時間復雜度的比值。自省排序算法。十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。給出試驗報告。教材及主要參考文獻[1] 嚴蔚敏、吳偉民，數(shù)據(jù)結(jié)構(gòu)習題集，清華大學出版社，1999年[2] John , Data Structures with C++, China Machine Press, 2002.[3] Mark Allen Weiss, Data Structures and Problem Solving Using C++, 2ed, 清華大學出版社。[4] Robert Sedgewick，Algorithms in C Part 1 – 4: Fundamentals, Data Structures, Sorting, rdSearching, 3, 中國電力出版社，2003年。若因課程特點需打印的，要遵照以下字體、字號、間距等的具體要求。實驗報告書寫說明實驗報告中一至四項內(nèi)容為必填項，包括實驗?zāi)康暮鸵?；實驗儀器和設(shè)備；實驗內(nèi)容與過程；實驗結(jié)果與分析。填寫注意事項（1）細致觀察，及時、準確、如實記錄。（3）盡量采用專用術(shù)語來說明事物。（5）應(yīng)獨立完成實驗報告的書寫，嚴禁抄襲、復印，一經(jīng)發(fā)現(xiàn)，以零分論處。實驗報告的批改成績采用百分制，具體評分標準由各院部自行制定。金陵科技學院實驗報告實驗項目名稱： 順序表 實驗學時： 2 同組學生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間：金陵科技學院實驗報告實驗1 順序表一、實驗?zāi)康暮鸵笳莆枕樞虮淼亩ㄎ弧⒉迦?、刪除等操作。編寫主函數(shù)測試結(jié)果。如果存在，返回順序表中和x值相等的第1個數(shù)據(jù)元素的序號（序號從0開始編號）；如果不存在，返回－1。（3）在遞增有序的順序表中插入一個新結(jié)點x，保持順序表的有序性。（4）刪除順序表中所有等于X的數(shù)據(jù)元素。程序清單：include include define MAXSIZE 100 typedef struct { int data[MAXSIZE]。金陵科技學院實驗報告} sequenlist。void print_list(){ int i。i金陵科技學院實驗報告loc=i。i=loc。[loc]=x。} void delete_x(int x){ int i,j,found=0。i金陵科技學院實驗報告} }void main(){ int x,choice。printf(“ 1printn”)。printf(“ 3insertn”)。printf(“ 5exitn”)。scanf(“%d”,amp。switch(choice){case 1: printf(“the original list is:n”)。break。金陵科技學院實驗報告scanf(“%d”,amp。find_all_x(x)。case 3: printf(“pls input x you want to insert:n”)。x)。printf(“the list after insertion is:n”)。break。scanf(“%d”,amp。delete_x(x)。print_list()。case 5: exit(0)。實驗要求（1）注意鏈表的空間是動態(tài)分配的，某結(jié)點不用之后要及時進行物理刪除，以便釋放其內(nèi)存空間。二、實驗儀器和設(shè)備Turbo C ++三、實驗內(nèi)容與過程（含程序清單及流程圖）必做題（1）編寫程序建立一個單鏈表，并逐個輸出單鏈表中所有數(shù)據(jù)元素。解題思路：首先查找插入的位置然后進行插入操作；從第一個結(jié)點開始找到第一個大于該新結(jié)點值的結(jié)點即為插入位置；然后在找到的此結(jié)點之前插入新結(jié)點；注意保留插入位置之前結(jié)點的指針才能完成插入操作。選做題已知指針LA和LB分別指向兩個無頭結(jié)點單鏈表的首元結(jié)點。程序清單：金陵科技學院實驗報告金陵科技學院實驗報告四、實驗結(jié)果與分析（程序運行結(jié)果及其分析）五、實驗體會（遇到問題及解決辦法，編程后的心得體會）金陵科技學院實驗報告實驗項目名稱： 堆棧和隊列 實驗學時： 2 同組學生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間：金陵科技學院實驗報告實驗3 堆棧和隊列一、實驗?zāi)康暮鸵螅?）掌握應(yīng)用棧解決問題的方法。（3）掌握隊列的存儲結(jié)構(gòu)及基本操作實現(xiàn)，并能在相應(yīng)的應(yīng)用問題中正確選用它們。（2）測試“漢諾塔”問題。選做題在順序存儲結(jié)構(gòu)上實現(xiàn)輸出受限的雙端循環(huán)隊列的入列和出列算法。入隊列采取簡化的短作業(yè)優(yōu)先原則，若一個新提交的作業(yè)的預(yù)計執(zhí)行時間小于隊頭和隊尾作業(yè)的平均時間，則插入在隊頭，否則插入在隊尾。二、實驗儀器和設(shè)備Turbo C ++三、實驗內(nèi)容與過程（含程序清單及流程圖）必做題（1）編寫輸出字符串s中值等于字符ch的第一個字符的函數(shù)，并用主函數(shù)測試結(jié)果。解題思路：可以將第一題程序改進成一個子函數(shù)，在本題中循環(huán)調(diào)用。選做題假設(shè)以鏈結(jié)構(gòu)表示串，編寫算法實現(xiàn)將串S插入到串T中某個字符之后，若串T中不存在這個字符，則將串S聯(lián)接在串T的末尾。程序清單：金陵科技學院實驗報告四、實驗結(jié)果與分析（程序運行結(jié)果及其分析）金陵科技學院實驗報告五、實驗體會（遇到問題及解決辦法，編程后的心得體會）金陵科技學院實驗報告實驗項目名稱： 二叉樹 實驗學時： 2 同組學生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間：金陵科技學院實驗報告實驗5 二叉樹一、實驗?zāi)康暮鸵螅?）掌握二叉樹的生成，以及前、中、后序遍歷算法。二、實驗儀器和設(shè)備Turbo C ++三、實驗內(nèi)容與過程（含程序清單及流程圖）必做題（1）建立一棵二叉樹。（2）在第一題基礎(chǔ)上，求二叉樹中葉結(jié)點的個數(shù)。（4）在第一題基礎(chǔ)上，求二叉樹的深度。試編寫算法由此順序存儲結(jié)構(gòu)建立該二叉樹的二叉鏈表。完全二叉樹順序存儲的一個重要性質(zhì)為，第i個結(jié)點的左孩子是編號為2i的結(jié)點，第i個結(jié)點的右孩子是編號為2i+1的結(jié)點。（2）熟練掌握對圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷的算法。（2）對上面所構(gòu)造的無向圖，進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，輸出遍歷序列。簡單路徑是指其頂點序列中不含有重復頂點的路徑。程序清單：金陵科技學院實驗報告四、實驗結(jié)果與分析（程序運行結(jié)果及其分析）五、實驗體會（遇到問題及解決辦法，編程后的心得體會）金陵科技學院實驗報告實驗項目名稱： 排序 實驗學時： 2 同組學生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間：金陵科技學院實驗報告實驗7 排序一、實驗?zāi)康暮鸵螅?）熟練掌握希爾排序、堆排序、直接插入排序、起泡排序、快速排序、直接選擇排序、歸并排序和基數(shù)排序的基本概念。區(qū)分以上不同排序的優(yōu)、缺點。測試下列各排序函數(shù)的機器實際執(zhí)行時間（至少測試兩個）：直接插入排序、希爾排序（增量為4，2，1）、冒泡排序、快速排序、直接選擇排序、堆排序。則可按如下方法排序：另設(shè)數(shù)組number[v…w]，令number[i]統(tǒng)計關(guān)鍵字為整數(shù)i的紀錄個數(shù)，然后按number重排序列以達到有序。程序清單：金陵科技學院實驗報告四、實驗結(jié)果與分析（程序運行結(jié)果及其分析）金陵科技學院實驗報告五、實驗體會（遇到問題及解決辦法，編程后的心得體會）金陵科技學院實驗報告實驗項目名稱： 查找 實驗學時： 2 同組學生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間：金陵科技學院實驗報告實驗8 查找一、實驗?zāi)康暮鸵螅?）掌握順序表查找、有序表查找、索引順序表查找的各種算法。二、實驗儀器和設(shè)備Turbo C ++三、實驗內(nèi)容與過程（含程序清單及流程圖）必做題（1）在一個遞增有序的線性表中利用二分查找法查找數(shù)據(jù)元素X。設(shè)計一個測試程序進行測試。程序清單：金陵科技學院實驗報告四、實驗結(jié)果與分析（程序運行結(jié)果及其分析）五、實驗體會（遇到問題及解決辦法，編程后的心得體會）第三篇：《數(shù)據(jù)結(jié)構(gòu)》實驗指導書《數(shù)據(jù)結(jié)構(gòu)》實驗(訓)指導書電氣與信息工程學院實驗中心前 言《數(shù)據(jù)結(jié)構(gòu)》是計算機相關(guān)專業(yè)的一門核心基礎(chǔ)課程，也是很多高校研究生入學考試專業(yè)課必考課程之一。這門課程的主要任務(wù)是培養(yǎng)學生的算法分析、設(shè)計能力及良好的程序設(shè)計習慣。學習這門課程，習題和實驗是兩個關(guān)鍵環(huán)節(jié)。因此，實驗環(huán)節(jié)的好壞是學生能否學好《數(shù)據(jù)結(jié)構(gòu)》的關(guān)鍵。一、實驗?zāi)康?、要求和任?wù)計算機編程中加工處理的對象是數(shù)據(jù)，而數(shù)據(jù)具有一定的組織結(jié)構(gòu)，所以學習編寫計算機程序僅僅了解計算機語言是不夠的，還必須掌握數(shù)據(jù)組織、存儲和運算的一般方法，這是數(shù)據(jù)結(jié)構(gòu)課程中學習和研究的內(nèi)容。、編譯、調(diào)試程序。，以便為應(yīng)用設(shè)計的數(shù)據(jù)選擇適當?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及其相應(yīng)的算法，并初步掌握算法的時間分析和空間分析的技術(shù)。，引導學生學習數(shù)據(jù)類型的使用，為今后學習面向?qū)ο蟮某绦蜃鲆恍╀亯|。各實驗單元與教科書的各章只具有粗略的對應(yīng)關(guān)系，一個實驗題常常涉及到幾部分教學內(nèi)容。線性表（2學時）（1）熟悉線性表的基本運算在兩種存儲結(jié)構(gòu)（順序結(jié)構(gòu)和鏈式結(jié)構(gòu)）上的實現(xiàn)；（2）以線性表的各種操作（建立、插入、刪除等）的實現(xiàn)為重點；（3）通過本次實驗幫助學生提高C語言的編程能力（特別是函數(shù)參數(shù)、指針類型、鏈表的使用）。實現(xiàn)簡單的先序遍歷，中序遍歷和后序遍歷算法。實冒泡排序或者直接插入排序算法。硬件要求：在多媒體教室講解及演示。學生每次上機實驗都必須遵守實驗室的有關(guān)規(guī)定。需求分析：以無歧義的陳述說明程序設(shè)計的任務(wù)、約束條件、輸入輸出要求、對功能的規(guī)定及模型。詳細設(shè)計：邏輯設(shè)計中定義的所有數(shù)據(jù)類型的實現(xiàn)，核心算法的設(shè)計描述、人機界面設(shè)計、函數(shù)之間調(diào)用關(guān)系的描述，主要功能的算法框架，測試