數(shù)據(jù)結構實驗指導書(1)

1、數(shù)據(jù)結構實驗指導語鄭州輕工業(yè)學院2016.02.20內容前言1實驗01順序表3的基本操作實驗02單鏈表的基本操作11實驗03堆棧19的基本操作實驗04隊列21的基本操作實驗05二叉樹的基本運算23實驗06霍夫曼編碼24實驗07圖26的兩種存儲和遍歷實驗08最小生成樹、拓撲排序和最短路徑29實驗09二叉排序樹的基本操作31實驗10哈希表生成32實驗11常見內部排序算法34附件：實驗報告模板36先前的評論數(shù)據(jù)結構是計算機相關專業(yè)的核心基礎課程，是編譯原理、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)等系統(tǒng)程序和大規(guī)模應用開發(fā)的重要基礎，也是許多高校研究生入學考試的專業(yè)課程之一。主要介紹了三種邏輯結構的特點：線性結構、樹形

2、結構和圖形結構，以及它們在計算機中的存儲方法。在此基礎上，介紹了一些典型算法及其時空效率分析。本課程的主要任務是研究數(shù)據(jù)的邏輯關系以及這種邏輯關系在計算機中的表示、存儲和操作，從而訓練學生設計能有效表達和簡化算法的數(shù)據(jù)結構，從而提高他們的編程能力。通過學習，要求學生掌握各種數(shù)據(jù)結構的特點、存儲表示和典型算法的設計思想和程序實現(xiàn)，并根據(jù)實際問題選擇合適的數(shù)據(jù)表示和存儲方案，設計簡單、高效、實用的算法，為后續(xù)的課程學習和軟件開發(fā)打下良好的基礎。此外，本課程的學習過程也是復雜編程的訓練過程。通過算法設計和計算機實踐的訓練，培養(yǎng)學生的數(shù)據(jù)抽象和編程能力。學習本課程，練習和實驗是兩個關鍵環(huán)節(jié)。學生理解算

3、法，計算機實驗是最好的方法之一。因此，實驗環(huán)節(jié)的質量是學生學好數(shù)據(jù)結構的關鍵。為了更好地配合學生的實驗，實驗教學是特別準備的。一、實驗目的本課程的實驗主要是原理與應用相結合。一方面，它能使學生更好地理解數(shù)據(jù)結構的概念以及計算機中幾種常用數(shù)據(jù)結構的存儲和實現(xiàn)方法，增強學生的實踐能力；另一方面，培養(yǎng)學生從實際問題中抽象出相應的抽象數(shù)據(jù)類型，進而找到合適的計算機存儲方法和算法，為以后的課程學習、大規(guī)模軟件開發(fā)和實際工程問題的軟件開發(fā)打下良好的基礎。二、實驗要求1.每次實驗前，學生必須根據(jù)實驗內容認真準備實驗程序和調試所需的輸入數(shù)據(jù)。2.在教師的幫助下，我們可以完成實驗內容，得到正確的實驗結果。3.實

4、驗結束后，總結實驗內容，寫實驗報告。4、遵守實驗室的規(guī)章制度，不缺席，按時上下飛機。5.實驗期間，必須完成數(shù)據(jù)結構的相關內容，不允許在網(wǎng)上聊天或玩游戲。如果發(fā)現(xiàn)上述現(xiàn)象，計算機資格將被取消，并從通常的結果中扣除10分。6.實驗報告失敗一次，扣5分。如果測試報告失敗兩次或兩次以上，正常分數(shù)將記錄為零。第三，實驗環(huán)境VC 6.0或其他與c語言相關的編譯環(huán)境。四.說明1.本實驗所有算法中的元素類型應根據(jù)實際需要合理選擇。2.實驗題目中有*的要求較高，學生可以自己選擇；其余為基本內容，應盡可能完成(至少70%，否則實驗不合格)。3.數(shù)據(jù)結構是許多高校研究生入學考試的專業(yè)課程之一。我希望對研究生入學考試

5、感興趣的學生能夠在學習過程中注意對各種算法的理解，為研究生入學考試做一些準備4.寫出實驗的經驗和實驗中未解決的問題。5.實驗程序應構建為多文件程序。對應于每個算法的函數(shù)原型聲明存儲在頭文件*中。h，相應的函數(shù)實現(xiàn)存儲在源文件*中。c；main()函數(shù)存儲在另一個源文件中，其中包含頭文件*。六.績效評估措施1、期末考試占70分，閉卷。2、平時考評占30分。其中，實驗環(huán)節(jié)占20分(實驗準備、計算機、報告、驗收等)。)；10分(出勤、作業(yè)、考試等。)。七.文獻學1.數(shù)據(jù)結構 (C語言版)嚴為民等清華大學出版社2，數(shù)據(jù)結構題集 (C語言版)嚴為民等清華大學出版社3.數(shù)據(jù)結構與算法分析C語言描述，馬克艾

6、倫維斯著，機械工業(yè)出版社，2012實驗01順序表的基本操作實驗時間：2小時實驗類型：計算機背景知識：序列表的插入、刪除和應用。目的要求：1.掌握順序存儲結構的特點。2.掌握順序存儲結構的常用算法。實驗內容：編寫一個完整的程序，實現(xiàn)序列表的生成、插入、刪除和輸出等基本操作。(1)建立包含n個數(shù)據(jù)元素的序列表。(2)輸出順序表。(3)刪除序列表中具有值x的節(jié)點或具有給定位置I的節(jié)點。(4)將表中的所有奇數(shù)排列在偶數(shù)之前，即奇數(shù)在表的前面，偶數(shù)在表的后面。(5)輸入整數(shù)元素序列，利用有序表插入算法建立有序表。(6) *使用算法5建立兩個非遞減有序表A和B，并將它們合并成一個非遞減有序表C(7)在主功

7、能中設計一個簡單的菜單，分別對上述算法進行測試。(8) *綜合培訓：利用序列表實現(xiàn)班級學生信息管理(數(shù)據(jù)錄入、插入、刪除、排序、搜索等)。)。實驗表明：1.請建立一個多文件程序。對應于算法1到6的函數(shù)原型聲明存儲在頭文件SqList.h中，并且對應的函數(shù)實現(xiàn)存儲在源文件SqList.c中；main()函數(shù)存儲在另一個源文件中，它包含頭文件SqList.h2.類型定義#define MAXSIZE 100 /表中元素的最大數(shù)量typedef int元素類型；/元素類型typedef結構ElemType *elem。/線性表整數(shù)長度；/表的實際長度int listsize/當前分配的存儲容量SqL

8、ist。/序列表的類型名3.建立序列表時，可以使用隨機函數(shù)自動生成數(shù)據(jù)。注意這個問題：1.插入和刪除期間元素的移動原因、方向和順序。2.理解函數(shù)形式和實際參數(shù)之間的傳遞關系。部分源代碼：DS.h#包括#包括#包括#包括#定義真1#定義FALSE 0#定義好1#define ERROR 0類型定義int狀態(tài)；SqList.h#ifndef SQLIST_H_INCLUDED#定義SQLIST_H_INCLUDED#包括DS . htypedef int元素類型；#定義LIST_INIT_SIZE 50typedef結構ElemType *elem。整數(shù)長度；int listsizeSqList。

9、void菜單()；狀態(tài)初始化列表_ Sq(SqLiST L)；/*初始化序列表*/狀態(tài)創(chuàng)建列表_ Sq(SqLiST L)；/*創(chuàng)建序列表*/void PrintList _ Sq(SqLiST L)；/*輸出序列表*/狀態(tài)刪除列表_Sq(SqList L，int i，ElEMType e)；/*刪除ith元素*/狀態(tài)DeleteListX_Sq(SqList L，ElEMType x)；/*刪除值為x *的元素狀態(tài)調整列表_ Sq(SqLiST L)；/*奇數(shù)先于偶數(shù)*/狀態(tài)順序列表_sq(SqList L，int n)；/*插入生成增量有序表的方法*/void MergeLiST _ Sq

10、(SqLiST 1a，SqList Lb，SqLiST Lc)；/*兩個非遞減有序表A和B，并將其合并為一個非遞減有序表C*/#endif /SQLIST_H_INCLUDEDSqList.cpp#include SqList.h void菜單()printf( t t t序列表的基本操作 n n )；Printf(ttt1。建立序列表 n ；Printf(ttt2。時間順序表 n )；Printf(ttt3。刪除ith元素 n )；Printf(ttt4。刪除值為x的元素；Printf(ttt5。奇數(shù)在偶數(shù)之前 n ；Printf(ttt6。插值方法生成的增量有序表 n ；printf(tt

11、t7 .兩個非遞減有序表a音的唱名和Lb合并成非遞減有序表)；printf(ttt0).退出 n n )；/*初始化順序表*/狀態(tài)初始化列表_Sq(SqList L)l。elem=(ElEMType *)malloc(LIST _ INIT _ SIZE * sizeof(ElEMType)；如果(！L.elem)出口(OVERFLOW).l。長度=0。L.listsize=LIST _ INIT _ SIZE返回確定；/*建立順序表*/狀態(tài)創(chuàng)建列表_Sq(SqList L)國際、國內；printf(請輸入順序表長度：)；scanf(% d ，n)；if(n LIST _ INIT _ SIZ

12、E INITlist _ Sq(L)printf(請輸入%d個元素“，n)；對于(1=0；I n；掃描( %d ，l . elemI)；l。長度=n。返回確定；其他返回錯誤/*輸出順序表*/void PrintList_Sq(SqList L)國際；printf(順序表中元素為： n )；對于(1=0；長度；printf(% d ，l . elemI)；printf( n )；/*刪除第i個元素*/狀態(tài)刪除列表_Sq(SqList L，int i，ElemType e)ElemType *p，*q .if(i1)| |(ILl . length)返回錯誤p=(l . elemI-1)；e=*

13、p；q=l . elem l . length-1；(p；p=q；p)*(p-1)=* p；-長度；返回確定；/*刪除值為x的元素，刪除成功返回好的，刪除失敗返回錯誤*/狀態(tài)DeleteListX_Sq(SqList L，ElemType x)ElemType *p，*q ./*請補充完整代碼*/*奇數(shù)排在偶數(shù)之前*/狀態(tài)調整列表_Sq(SqList L)ElemType *p，*q .int temp/*請補充完整代碼*/*插入法生成遞增有序表，有序表生成成功返回好的，失敗返回錯誤*/狀態(tài)順序列表_sq(SqList L，int n)int i，j，x；/*x表示每次待插入的元素*/*請補充完整代碼*/*兩個非遞減有序表A和b、并把它們合并成一個非遞減有序表C*/void MergeList_Sq(SqList La，SqList Lb，SqList Lc)ElemType *pa，*pb，*pc，*pa_last，* pb _ lastpa=La.elempb=Lb.el