數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)書

《數(shù)據(jù)結(jié)構(gòu)》實驗課程指導(dǎo)書本實驗課程配合《數(shù)據(jù)結(jié)構(gòu)》課程同步開設(shè)，包括驗證性實驗和綜合課程設(shè)計，32學(xué)時，2學(xué)分。地點安排在學(xué)院機房。本實驗課程的先導(dǎo)課程為：《C++程序設(shè)計》及配套實驗。指導(dǎo)書的內(nèi)容分為兩大部分：第一部分介紹實驗步驟；第二部分是具體的實驗安排。本實驗的環(huán)境配置要求：硬件配置：586以上PC兼容機或品牌機，配有彩色顯示器、鼠標(biāo)、鍵盤，內(nèi)存不小于64MB，硬盤自由空間不少于200MB。推薦配置為內(nèi)存128MB或256MB（或以上），硬盤自由空間500MB以上。操作系統(tǒng)：Windows98或Windows2000Professional.集成開發(fā)環(huán)境：MicrosoftVisualC++6.0以上版本第一部分實驗步驟集成開發(fā)環(huán)境（IDE）是一個將程序編輯器、編譯器、調(diào)試工具和其他工具集成在一起的用于開發(fā)應(yīng)用程序的軟件系統(tǒng)。程序員可以在不離開該環(huán)境的情況下編輯、編譯、調(diào)試和運行一個應(yīng)用程序。此外，IDE還提供大量在線幫助信息，以幫助程序員快速地開發(fā)出應(yīng)用程序。實驗步驟：）啟動VisualC++；（2）選擇“文件”菜單中的“新建”項；（3）選擇文件中的C++SourceFile,并填寫文件名和存儲的目錄；（4）單擊“確定”按鈕，進入源程序的編輯狀態(tài)；（5）源程序編輯完后，選擇“編譯”菜單進行編譯，此時，有窗口提示是否建立一個默認(rèn)的活動工作區(qū)（工程），選擇“是（Y）”,若有語法錯，則按提示信息修改源程序，直到編譯沒有錯誤為止；（6）編譯通過后，選擇“編譯”菜單中的“執(zhí)行”，運行目標(biāo)程序；（7）注意在編輯源程序時，適時存盤，保存文件。第二部分實驗安排序號學(xué)時數(shù)實驗內(nèi)容12線性表的順序存儲22順序堆棧32線性表的鏈?zhǔn)酱鎯?2鏈?zhǔn)疥犃?2二叉樹62圖72排序82查找916綜合設(shè)計注意事項：每次實驗以前，請詳細(xì)閱讀實驗?zāi)康募皩嶒瀮?nèi)容，每個實驗必須有相關(guān)的測試數(shù)據(jù)，并給出測試結(jié)果。實驗1為引導(dǎo)性實驗，提供基本的程序框架和實驗報告書寫規(guī)范。實驗1、線性表的順序存儲一、實驗?zāi)康模?、理解線性表的邏輯結(jié)構(gòu)；2、掌握線性表的順序存儲結(jié)構(gòu)；3、熟練掌握線性表的順序存儲結(jié)構(gòu)的基本算法。二、實驗內(nèi)容：設(shè)有結(jié)構(gòu)體定義：structperson{charname[6];intage;charsex;};分析函數(shù)SeqList（）和Insert（）的具體功能；完成成員函數(shù)printbyage(constinta)，實現(xiàn)遍歷順序表，并打印年齡為a的所有數(shù)據(jù)元素；完成主函數(shù)main()，設(shè)計測試數(shù)據(jù)，并分析結(jié)果。三、程序框架：#include<iostream.h>#include<stdlib.h>//頭文件constintmaxlistsize=100;//順序表的最大值structperson{ charname[20]; intage; charsex;};typedefpersondatatype;classSeqList{ private: datatypedata[maxlistsize]; //存儲空間 intsize;//表中有效元素的個數(shù) public: SeqList(void);//構(gòu)造函數(shù) voidInsert(constdatatype&item,intpos); voidprintbyage(constinta);};SeqList::SeqList(void):size(0){}voidSeqList::Insert(constdatatype&item,intpos){ inti; if(size==maxlistsize) {cerr<<"表已滿"<<endl; exit(1); } if(pos<0||pos>size) {cerr<<"pos值越界！"<<endl; exit(1); } for(i=size;i>pos;i--)data[i]=data[i-1]; data[pos]=item; size++;}voidSeqList::printbyage(constinta){補充代碼}voidmain(void){補充代碼}四、測試結(jié)果及分析五、實驗體會實驗2、順序堆棧一、實驗?zāi)康模?、理解棧的特點；2、掌握棧順序存儲結(jié)構(gòu)；3、熟練掌握入棧和出棧操作。二、實驗內(nèi)容：輸入序列為abcde,應(yīng)用棧的操作，得到輸出序列abcde；輸入序列為abcde,應(yīng)用棧的操作，得到輸出序列edcba；輸入序列為abcde，能否得到輸出序列dbace?實驗3、線性表的鏈?zhǔn)酱鎯σ弧嶒災(zāi)康模?、理解線性表的邏輯結(jié)構(gòu)；2、掌握線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)；3、熟練掌握鏈表算法的應(yīng)用。二、實驗內(nèi)容：設(shè)計一個有序單鏈表，鏈表中的元素按大小遞增有序，并完成：設(shè)計成員函數(shù)insert(datatypeitem),使新元素item加入后，鏈表仍然有序；設(shè)計外部函數(shù)concate(),將有序表A和B，合并到有序表C中。實驗4、鏈?zhǔn)疥犃幸?、實驗?zāi)康模?、理解隊列的特點；2、掌握鏈?zhǔn)疥犃械幕静僮?；二、實驗?nèi)容：1、初始化鏈隊列；2、入隊列元素（6個），輸出3個元素；3、再入隊列5個元素，輸出所有的元素。實驗5、二叉樹一、實驗?zāi)康模豪斫舛鏄涞奶攸c；掌握二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)；2、掌握二叉樹的先序、中序和后序遍歷算法。二、實驗內(nèi)容：1、編程建立一棵二叉樹（不少于6個結(jié)點）；2、編寫先序、中序和后序遍歷算法。實驗6、圖一、實驗?zāi)康模豪斫鈭D的邏輯結(jié)構(gòu)；掌握圖的鄰接矩陣存儲結(jié)構(gòu)；2、掌握圖的深度優(yōu)先遍歷過程。二、實驗內(nèi)容：1、編程建立一張圖（不少于6個結(jié)點）；2、采用深度優(yōu)算法對圖進行遍歷。實驗7、排序一、實驗?zāi)康模?、理解各種排序算法；2、實現(xiàn)直接插入排序算法和冒泡排序排序算法。二、實驗內(nèi)容：1、將記錄關(guān)鍵字{23，37，11，6，77，21，78}(也可自定)存入數(shù)組A；2、分別編寫直接插入排序算法和冒泡排序算法，對數(shù)組A中數(shù)據(jù)排序；比較兩者的結(jié)果。實驗8、查找一、實驗?zāi)康模?、理解各種查找算法；2、實現(xiàn)順序查找和折半查找算法。二、實驗內(nèi)容：1、將記錄關(guān)鍵字{5,8,11,21,33,37,61,77,96，105}(也可自定)存入數(shù)組A；2、分別編寫順序查找和折半查找算法。3、分別輸入有效和無效數(shù)據(jù),比較不同算法的查找次數(shù)。實驗9、綜合設(shè)計目的：著眼于理論與應(yīng)用的結(jié)合，學(xué)會如何將書上的知識運用于解決實際問題，掌握小型項目的開發(fā)流程，培養(yǎng)動手能力和協(xié)作能力。分組：題目1-3，兩人一組，提交磁盤及一份完整的報告（格式參照題目一），磁盤中包含可執(zhí)行的代碼和源文件，報告中分工要明確，注明執(zhí)筆者、設(shè)計者、模塊編程者（每人必須參與編程）、測試數(shù)據(jù)的完成者，并進行答辯。題目4-5，單獨完成,提交磁盤及一份完整的論文，并回答相關(guān)問題。注意事項：論文內(nèi)容應(yīng)自行組織，有自己的觀點，嚴(yán)禁抄襲網(wǎng)上文章?！额}目一：查找及內(nèi)部排序》(難度系數(shù)0.90)一：需求分析：1、待排序表的長度為4K（4096），數(shù)據(jù)類型為整型，由隨機函數(shù)產(chǎn)生整型序列存于數(shù)組A[4096]中；2、對待排序表分別進行直接插入排序、起泡排序和基數(shù)排序，結(jié)果存于數(shù)組B[4096]中。在排序的過程中統(tǒng)計：①：關(guān)鍵字的比較次數(shù)；②：數(shù)據(jù)的移動次數(shù)；=3\*GB3③：統(tǒng)計算法的執(zhí)行時間（毫秒）。排序結(jié)果輸出：①：輸出各算法執(zhí)行完后B[1000]-B[1020]的內(nèi)容；②：輸出不同排序算法執(zhí)行完后的統(tǒng)計數(shù)據(jù)。3、對A采用順序查找，B采用折半查找，隨機產(chǎn)生100個關(guān)鍵字，分別統(tǒng)計查找成功時的平均查找次數(shù)。4、選作希爾排序、歸并排序、基數(shù)排序及統(tǒng)計算法的執(zhí)行時間。二、概要設(shè)計：1、選擇合適的存儲結(jié)構(gòu)，有數(shù)據(jù)類型定義，并標(biāo)明每項含義；2、定義各功能模塊，并標(biāo)明模塊的功能及參數(shù)含義；3、主程序框架。三、詳細(xì)設(shè)計：源代碼及必要的說明。四、調(diào)試分析：（碰到的問題及解決方法）五、測試數(shù)據(jù)及結(jié)果分析：（與理論值進行比較）六、思考題：如何在程序中檢測算法的穩(wěn)定性。《題目二：航空定票系統(tǒng)模擬》(難度系數(shù)1.0)一：需求分析：1、每條航線包括：航班號、起始站、終點站名、票價、日期及總票量；2、客戶訂：客戶姓名、航班號、數(shù)量（最少為1，最多為總票量的1/10）；3、允許客戶退票；4、提供航班信息查詢、統(tǒng)計每航班的日銷售額并排序：（如：航班信息顯示）航班號日期起始站終點站名總票量已售票量剩余票量5、提供客戶信息查詢。二、概要設(shè)計：1、選擇合適的存儲結(jié)構(gòu)，有數(shù)據(jù)類型定義，并標(biāo)明每項含義；2、定義各功能模塊，并標(biāo)明模塊的功能及參數(shù)含義；3、主程序框架。三、詳細(xì)設(shè)計：源代碼及必要的說明。四、調(diào)試分析：（碰到的問題及解決方法）五、測試數(shù)據(jù)及結(jié)果：《題目三：成績管理系統(tǒng)》(難度系數(shù)1.0)一：需求分析：1、基本信息：學(xué)號、姓名、班級、課程、成績；2、實現(xiàn)成績錄入、成績查詢功能3、提供班成績排序功能、顯示課程中成績的分布情況。二、概要設(shè)計：1、選擇合適的存儲結(jié)構(gòu)，有數(shù)據(jù)類型定義，并標(biāo)明每項含義；2、定義各功能模塊，并標(biāo)明模塊的功能及參數(shù)含義；3、主程序框架。三、詳細(xì)設(shè)計：源代碼及必要的說明。四、調(diào)試分析：（碰到的問題及解決方法）五、測試數(shù)據(jù)及結(jié)果：《題目四：分析硬盤的數(shù)據(jù)組織結(jié)構(gòu)》(難度系數(shù)0.85)提交論文：（3000字）題目；中文摘要及關(guān)鍵字；//英文摘要及關(guān)鍵字；正文；結(jié)束語；參考文獻(xiàn)；注：正文中應(yīng)包括分析自己所用電腦的MBR（MainBoo