第一篇：數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)實驗1

浙江大學(xué)城市學(xué)院實驗報告

課程名稱

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

實驗項目名稱

實驗一

熟悉Project組織應(yīng)用程序

學(xué)生姓名

專業(yè)班級

學(xué)號

實驗成績

指導(dǎo)老師（簽名）

日期

一.實驗?zāi)康暮鸵?/p>

1、熟悉VC6.0開發(fā)環(huán)境；使用Workspace和Project組織應(yīng)用程序；

2、回顧C語言程序設(shè)計，編寫完整的實驗應(yīng)用程序，并調(diào)試通過。

3、掌握文件包含，以及庫函數(shù)iostream.h中的標準輸入、輸出流對象cin和cout，理解“引用（&）”方式的參數(shù)傳遞。

二.實驗內(nèi)容

1、按下述介紹的方法，練習(xí)并掌握使用Project組織應(yīng)用程序的方法。步驟：

① 啟動VC++，選擇“文件（File）”菜單中的“新建（New）”項，選擇“工程（Projects）頁，然后選擇“Win32 Console Application”，在右上角輸入project的名稱（如：test1），再選擇合適的存儲路徑，然后按下“確定”按鈕。這樣就建立了一個新的工程。如下圖所示：

② 在窗口左側(cè)出現(xiàn)WorkSpace視圖，選擇“FileView”頁可瀏覽該工程所包含的文件。然后可在項目中新建源文件（菜單：文件?新建），包括“C/C++Header File”和“C/C++Source File”兩類文件，或?qū)⒁延械脑次募尤氲竭@個工程中（菜單：工程?增加到工程）。如下圖：

完成后程序組織結(jié)構(gòu)如下圖：

其中Source Fileste中包含主程序等源程序文件（如：test1_main.cpp），Header Fileste中包含頭文件等（如：test1_function.h）。

2、在VC中建立工程（取名為test1），并編寫如下程序加入到工程中，編譯執(zhí)行該程序。要求使用cin和cout進行數(shù)據(jù)的輸入輸出。程序題目如下：

設(shè)a為長度為n的整數(shù)型一維數(shù)組。

（1）試編寫求a中的最大值、最小值和平均值的函數(shù)。

請分別用兩種方法完成：

? 分別編寫三個函數(shù)int aMAX(int *a,int n)、int aMIN(int *a,int n)、int aAVE(int *a,int n)實現(xiàn)求最大值、最小值和平均值。

? 用一個函數(shù)void aMAX_MIN_AVE(int *a, int n, int &max, int &min, int &aver)實現(xiàn)求上述三個值，用“引用參數(shù)”帶回結(jié)果。

（2）試編寫函數(shù) int prime_SUM(int *a, int n)計算a中所有素數(shù)之和。（3）編寫函數(shù) void aSORT(int *a,int n)對a進行從小到大的排序，并輸出排序結(jié)果。

要求：

把以上函數(shù)存放在頭文件test1.h中，并自行設(shè)計主函數(shù)來測試各類操作實現(xiàn)的正確性，主函數(shù)存放在文件test1.cpp中。

3、填寫實驗報告，實驗報告文件取名為report1.doc。

4、上傳實驗報告文件report1.doc、源程序文件test1.cpp及test1.h到Ftp服務(wù)器上（ftp://10.61.14.240:5000）自己的文件夾下。

三.函數(shù)的功能說明及算法思路

（包括每個函數(shù)的功能說明，及一些重要函數(shù)的算法實現(xiàn)思路）

1、求a中的最大值 int aMAX(int *a,int n){ int i,max;max=a[0];for(i=0;i

if(max

max=a[i];} return max;}

2、求a中的最小值 int aMIN(int *a,int n){ int i,min=a[0];for(i=0;i

if(min>a[i])

min=a[i];} return min;}

3、求a中的平均值 int aAVE(int *a,int n){ int i,sum=0,ave;for(i=0;i

sum=sum+a[i];

ave=sum/n;

return ave;}

4、用一個函數(shù)求a中的最大值、最小值、平均值

void aMAX_MIN_AVE(int *a, int n, int &max, int &min, int &aver){ int sum,i;sum=0;max=a[0];min=a[0];aver=a[0];for(i=0;i

if(a[i]>max)max=a[i];

if(a[i]

sum=sum+a[i];} aver=sum/n;}

5、計算a中所有素數(shù)之和 int prime_SUM(int *a, int n){ int i,sum=0;for(i=0;i

if(prime(a[i]))

sum=sum+a[i];} return sum;}

int prime(int x)

//判斷一個數(shù)是否是素數(shù) { int i;for(i=2;i<(x/2);i++)

if(x%i==0)break;

if(i>=x/2)

return 1;

else

return 0;}

6、對a進行從小到大的排序，并輸出排序結(jié)果 void aSORT(int *a,int n){ int i, index,j,temp;for(i=0;i

index=i;

for(j=i+1;j

if(a[j]

index=j;

temp=a[i];

a[i]=a[index];

a[index]=temp;} } 四.實驗結(jié)果與分析

（包括運行結(jié)果截圖、結(jié)果分析等）input data:0 1 2 3 4 5 6 7 8 9 max in a:9 min in a:0 ave in a:4 sum of prime:18 max in a:9 min in a:0 ave in a:4 the sort is:0 1 2 3 4 5 6 7 8 9Press any key to continue 五.心得體會

（記錄實驗感受、上機過程中遇到的困難及解決辦法、遺留的問題、意見和建議等。）

最開始編譯時，總是有十幾個錯誤，或是變量未定義，或是函數(shù)中有錯誤，在經(jīng)過調(diào)試和與同學(xué)交流之后，終于解決了這些問題。這使我意識到自己在綜合編程方面的不足，函數(shù)一多容易搞混，以后一定改正?！靖戒?---源程序】

Test1_func.h int prime(int x)

////判斷一個數(shù)是否是素數(shù) {

}

int aMAX(int *a,int n){

}

int aMIN(int *a,int n)int i,max;max=a[0];for(i=0;i

} return max;if(max

if(x%i==0)break;if(i>=x/2)return 1;else return 0;{

}

int aAVE(int *a,int n){

}

int prime_SUM(int *a, int n){ return ave;ave=sum/n;int i,sum=0,ave;for(i=0;i

} return min;if(min>a[i])min=a[i];

} int i,sum=0;for(i=0;i

} return sum;if(prime(a[i]))sum=sum+a[i];void aMAX_MIN_AVE(int *a, int n, int &max, int &min, int &aver){

} int sum,i;sum=0;max=a[0];min=a[0];aver=a[0];for(i=0;i

} aver=sum/n;if(a[i]>max)max=a[i];if(a[i]

void aSORT(int *a,int n){

int i, index,j,temp;for(i=0;i

} index=i;for(j=i+1;j

if(a[j]

Test1_main.cpp }#include #include #include“test1_func.h” void main(){

} int a[10],i,max,min,ave;cout<<“input data:”;for(i=0;i<10;i++)cin>>“%d”,&a[i];cout<<“max in a:”<

第二篇：數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)__實驗總結(jié)

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)實驗總結(jié)

本學(xué)期開設(shè)的《數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)》課程已經(jīng)告一段落，現(xiàn)就其知識點及其掌握情況、學(xué)習(xí)體會以及對該門課程的教學(xué)建議等方面進行學(xué)習(xí)總結(jié)。

各章知識點概要

第一章交代了該學(xué)科的相關(guān)概念，如數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型以及數(shù)據(jù)結(jié)構(gòu)的定義。其中，數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運算集合。邏輯結(jié)構(gòu)分為四類：集合型、線性、樹形和圖形結(jié)構(gòu)。緊接著介紹了一些常用的數(shù)據(jù)運算。最后著重介紹算法性能分析，包括算法的時間性能分析以及算法的空間性能分析。

第二章具體地介紹了線性表的概念、基本運算及其應(yīng)用?；具\算有：初始化表、求表長、排序、元素的查找、插入及刪除等。鏈表與順序表相比，鏈表的插入、刪除不需要移動元素，給算法的效率帶來較大的提高。鏈表這一章中介紹了鏈表的節(jié)點結(jié)構(gòu)、靜態(tài)與動態(tài)鏈表的概念、鏈表的基本運算（如求表長、插入、查找、刪除等）、單鏈表的建立（頭插法和尾插法）、定義、結(jié)構(gòu)、功能和基本算法。

第四章堆棧與隊列是兩種運算受限制的線性結(jié)構(gòu)。其基本運算方法與順序表和鏈表運算方法基本相同，不同的是堆棧須遵循“先進后出”的規(guī)則，對堆棧的操作只能在棧頂進行；而隊列要遵循“先進先出”的規(guī)則，教材中列出了兩種結(jié)構(gòu)的相應(yīng)算法，如入棧、出棧、入隊、出隊等。

第五章二叉樹的知識是重點內(nèi)容。在介紹有關(guān)概念時，提到了二叉樹的性質(zhì)以及兩種特殊的二叉樹：完全二叉樹和滿二叉樹。接著介紹二叉樹的順序存儲和鏈接存儲以及生成算法。重點介紹二叉樹的遍歷算法：遞歸算法、先序、中序和后序遍歷非遞歸算法。樹與二叉樹是不同的概念。教材介紹了樹的概念、遍歷和存儲結(jié)構(gòu)，還有樹和二叉樹的相互關(guān)系，樹怎樣轉(zhuǎn)化成二叉樹，二叉樹又如何轉(zhuǎn)換為樹等。

第七章介紹了圖的概念及其應(yīng)用，是本書的難點。圖的存儲結(jié)構(gòu)的知識點有：鄰接矩陣、鄰接表。圖的遍歷包括圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。其余知識點有：有向圖、連通圖、最短路徑問題。

學(xué)習(xí)體會和教學(xué)建議

這是一門純屬于設(shè)計的科目，它需用把理論變?yōu)樯蠙C調(diào)試。剛開始學(xué)的時候確實有很多地方我很不理解，每次上課時老師都會給我們出不同的設(shè)計題目，對于我們一個初學(xué)者來說，無疑是一個具大的挑戰(zhàn)，撞了幾次壁之后，我決定靜下心來，仔細去寫程序。老師會給我們需要編程的內(nèi)容一些講解，順著老師的思路，來完成自己的設(shè)計，我們可以開始運行自己的程序。

這門課結(jié)束之后，我總結(jié)了學(xué)習(xí)中遇到的一些問題，最為突出的，書本上的知識與老師的講解都比較容易理解，但是當自己采用剛學(xué)的知識點編寫程序時卻感到十分棘手，有時表現(xiàn)在想不到適合題意的算法，有時表現(xiàn)在算法想出來后，只能將書本上原有的程序段謄寫到自己的程序中再加以必要的連接以完成程序的編寫。

其實現(xiàn)在想起來，收獲還真是不少，雖然說以前非常不懂這門語言，在它上面花費了好

多心血，覺得它很難，是需用花費了大量的時間編寫出來的?，F(xiàn)在真正的明白了一些代碼的應(yīng)用，每個程序都有一些共同點，通用的結(jié)構(gòu)，相似的格式。只要努力去學(xué)習(xí)，就會靈活的去應(yīng)用它。

建議在上課過程中加大隨堂練習(xí)的分量，以便學(xué)生能當堂消化課堂上學(xué)習(xí)的知識，也便于及時了解學(xué)生對知識點的掌握情況，同時有助于學(xué)生保持良好的精神狀態(tài)。

以上便是我對《數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)》這門課的學(xué)習(xí)總結(jié)，我會抓緊時間將沒有吃透的知識點補齊。因為我們還要學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)與算法》，所以今后我會繼續(xù)學(xué)習(xí)，克服學(xué)習(xí)中遇到的難關(guān)，在打牢基礎(chǔ)的前提下向更深入的層面邁進！

第三篇：《數(shù)據(jù)結(jié)構(gòu)》實驗指導(dǎo)書

《數(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ù)選擇適當?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é)時分配

為了達到實驗?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)和鏈式結(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é)方法，集知識性與趣味性于一體，達到良好的教學(xué)效果。硬件要求：在多媒體教室講解及演示。為保證教學(xué)順利進行，要求實驗室提供電腦等設(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、詳細設(shè)計：邏輯設(shè)計中定義的所有數(shù)據(jù)類型的實現(xiàn)，核心算法的設(shè)計描述、人機界面設(shè)計、函數(shù)之間調(diào)用關(guān)系的描述，主要功能的算法框架，測試數(shù)據(jù)設(shè)計。

5、測試分析：測試結(jié)果的分析與討論，測試過程中遇到的主要問題及采取的解決措施。

6、心得：軟件設(shè)計與實現(xiàn)過程中的經(jīng)驗與體會，進一步改進的設(shè)想。

7、程序清單：源程序中應(yīng)有足夠的注釋。如果提交源程序軟盤，列出程序文件名。

五、如何提高上機效率

為了提高上機的效率，真正達到實驗?zāi)康?，要求同學(xué)做好實驗前的準備工作，寫好實驗預(yù)習(xí)報告，即實驗報告規(guī)范中的1）、2）、3）、4）部分，編寫好程序，并用一組測試數(shù)據(jù)手工執(zhí)行程序靜態(tài)檢查程序是否有錯，通過閱讀、執(zhí)行程序或給別人講解自己的程序而深入全面地理解程序邏輯，提高程序的正確性。對C語言程序不熟悉的同學(xué)，上機時最好帶上C語言程序設(shè)計的教材，以備查閱。調(diào)試中遇到問題，應(yīng)認真分析，確定可疑點，設(shè)置調(diào)試斷點或輸出斷點處變量的值，以便發(fā)現(xiàn)問題，迅速排除問題，加快調(diào)試速度。

實驗室要求：

不能曠課，不遲到，不穿拖鞋進實驗室

實驗需預(yù)習(xí)報告（不能單純抄寫，預(yù)習(xí)程序代碼）實驗報告（總結(jié)，注釋，實驗結(jié)果）

目 錄

實驗一 線性表實驗（設(shè)計性實驗）..........................................4 實驗二 數(shù)組和廣義表實驗（設(shè)計性實驗）....................................6 實驗三 樹與二叉樹（設(shè)計性實驗）..........................................8 實驗四 排序（設(shè)計性實驗）................................................9

實驗一

線性表實驗（設(shè)計性實驗）

一、實驗?zāi)康?/p>

1.熟悉C語言的上機環(huán)境，進一步掌握C語言的結(jié)構(gòu)特點。2.掌握線性表的順序存儲結(jié)構(gòu)的定義及C語言實現(xiàn)。

3.掌握線性表的鏈式存儲結(jié)構(gòu)——單鏈表的定義及C語言實現(xiàn)。4.掌握線性表在順序存儲結(jié)構(gòu)即順序表中的各種基本操作。5.掌握線性表在鏈式存儲結(jié)構(gòu)——單鏈表中的各種基本操作。

二、實驗內(nèi)容

1.順序線性表的建立、插入及刪除。2.鏈式線性表的建立、插入及刪除。

三、實驗儀器設(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ù)組的下標與位序（順序表中元素的次序）的區(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語言的標準函數(shù)malloc()，如給指針變量p分配一個結(jié)點的地址：

p=(linklist *)malloc(sizeof(linklist));該語句的功能是申請分配一個類型為linklist的結(jié)點的地址空間，并將首地址存入指針變量p 中。當結(jié)點不需要時可以用標準函數(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.給定矩陣任一元素的下標，4.打印給定下標所對應(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;//非零元的行下標和列下標 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é)生的考試成績表，每條信息由姓名和分數(shù)組成，試設(shè)計一個算法：

（1）按分數(shù)高低次序，打印出每個學(xué)生在考試中獲得的名次，分數(shù)相同的為同一名次；（2）按名次列出每個學(xué)生的姓名與分數(shù)。

三、實驗儀器設(shè)備與器材 上機電腦

四、實驗步驟

1.定義結(jié)構(gòu)體。2.定義結(jié)構(gòu)體數(shù)組。

3.定出主程序，對數(shù)據(jù)進行排序。

五、實驗提示

#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;iR[max].score)max=j;

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)書

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

南京工程學(xué)院

信息管理與信息系統(tǒng)教研室

2014年3月

實驗一 線性表操作

一、實驗?zāi)康?/p>

1.熟悉C語言的上機環(huán)境，進一步掌握C語言的結(jié)構(gòu)特點。2.掌握線性表的順序存儲結(jié)構(gòu)的定義及C語言實現(xiàn)。

3.掌握線性表的鏈式存儲結(jié)構(gòu)——單鏈表的定義及C語言實現(xiàn)。4.掌握線性表在順序存儲結(jié)構(gòu)即順序表中的各種基本操作。5.掌握線性表在鏈式存儲結(jié)構(gòu)——單鏈表中的各種基本操作。

二、實驗內(nèi)容

1.順序線性表的建立、插入及刪除。

2.鏈式線性表的建立、插入及刪除。

三、實驗步驟

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ù)組的下標與位序（順序表中元素的次序）的區(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語言的標準函數(shù)malloc()，如給指針變量p分配一個結(jié)點的地址：

p=(linklist *)malloc(sizeof(linklist));該語句的功能是申請分配一個類型為linklist的結(jié)點的地址空間，并將首地址存入指針變量p 中。當結(jié)點不需要時可以用標準函數(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.掌握隊列的鏈式表示和實現(xiàn)

二、實驗內(nèi)容

1.編寫一個程序?qū)崿F(xiàn)順序棧的各種基本運算。2.實現(xiàn)隊列的鏈式表示和實現(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->toptop=p->top+1;/*棧頂+1*/ p->stack[p->top]=x;} /*數(shù)據(jù)入棧*/ } /*出棧函數(shù)*/ ElemType Pop(SqStack *p){x=p->stack[p->top];/*將棧頂元素賦給x*/ p->top=p->top-1;} /*棧頂-1*/ /*獲取棧頂元素函數(shù)*/ ElemType GetTop(SqStack *p){ x=p->stack[p->top];} /*遍歷順序棧函數(shù)*/ void OutStack(SqStack *p){ for(i=p->top;i>=0;i--)printf(“第%d個數(shù)據(jù)元素是：%6dn”,i,p->stack[i]);} /*置空順序棧函數(shù)*/ void setEmpty(SqStack *p){ p->top=-1;} 可參考代碼： #include “stdio.h” #define StackSize 100 typedef int ElemType;main(){

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 #include typedef int Status;typedef char ElemType;typedef struct BiTNode { ElemType data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;/*建立二叉樹*/

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ù)目。

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

目 錄

實驗規(guī)則················································2 實驗環(huán)境················································2 實驗報告要求············································3 實驗一 單鏈表

（一）······································4 實驗二 單鏈表

（二）······································5 實驗三 棧···············································6 實驗四 二叉樹···········································7 實驗五 最短路徑·········································8 實驗六 內(nèi)部排序·········································9

實 驗 規(guī) 則

為了順利完成實驗教學(xué)任務(wù)，確保人身、設(shè)備的安全，培養(yǎng)嚴謹、踏實、實事求是的科學(xué)作風(fēng)和愛護國家財產(chǎn)的優(yōu)良品質(zhì)，特制定以下實驗規(guī)則：

1、實驗前必須充分預(yù)習(xí)，完成指定的預(yù)習(xí)任務(wù)。預(yù)習(xí)要求如下：

（1）認真閱讀指導(dǎo)書，進行必要的設(shè)計與計算。（2）熟悉實驗內(nèi)容。

（3）預(yù)先復(fù)習(xí)，并按要求編寫程序。（4）未完成預(yù)習(xí)任務(wù)者不得進入實驗室。

2、遵守以下紀律：

（1）在實驗室不得做和實驗無關(guān)的事情。

（2）進行任課老師指定內(nèi)容以外的實驗，必須經(jīng)指導(dǎo)教師同意。（3）遵守紀律，不遲到。

（4）保持實驗室內(nèi)安靜、整潔，愛護公物，不許亂寫亂畫。

實 驗 環(huán) 境

本實驗在386以上的微機上進行，運行環(huán)境為VC6.0。

實驗報告要求

1、實驗題目 2．實驗?zāi)康?3．實驗環(huán)境

4．實驗內(nèi)容與完成情況（可以附上自主設(shè)計的源程序）5．出現(xiàn)的問題及對問題的解決方案 6．實驗思考：（學(xué)生對本次實驗的收獲的總結(jié)）

實驗一 單鏈表

（一）一、實驗?zāi)康?/p>

掌握線性表的鏈式存儲結(jié)構(gòu)及其基本操作。

二、預(yù)習(xí)要求

1、看懂書上的算法，深入理解鏈表的物理存儲模式和邏輯模式。

2、根據(jù)要求，編寫程序準備上機調(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ù)需要選擇所要進行的操作；構(gòu)造函數(shù)，每一個函數(shù)實現(xiàn)上述的一個功能。

實驗二 單鏈表

（二）一、實驗?zāi)康?/p>

掌握線性表的鏈式存儲結(jié)構(gòu)及其基本操作。

二、預(yù)習(xí)要求

1、看懂書上的算法，深入理解鏈表的物理存儲模式和邏輯模式。

2、根據(jù)要求，編寫程序準備上機調(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ù)要求，編寫程序準備上機調(diào)試。

三、實驗內(nèi)容

利用棧實現(xiàn)數(shù)據(jù)的分類，要求當輸入為偶數(shù)時進棧1，當輸入為奇數(shù)時進棧2，最后分別從棧1和棧2輸出偶數(shù)和奇數(shù)序列。

四、實現(xiàn)提示

1、開辟一個連續(xù)的存儲空間，實現(xiàn)兩個棧順序存儲空間的共享；分別在兩端設(shè)置棧頂指針，并按要求實現(xiàn)棧操作。

2、采用順序存儲實現(xiàn)棧的初始化、入棧、出棧操作。

五、選做題、思考題

1、兩?？臻g共享時，棧滿的條件是什么？

2、為停車場編制進行管理的模擬程序（習(xí)題集P96，2.1）。

3、編寫程序，利用棧實現(xiàn)表達式求值。

實驗四 二叉樹

一、實驗?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īng)過的城市。存儲結(jié)構(gòu)可選用鄰接矩陣。

五、選做題、思考題

1．如何實現(xiàn)對城市信息進行編輯（如：添加或刪除）的功能。

2．用鄰接表作存儲結(jié)構(gòu)，求一指定景點出發(fā)，到其余各景點的最短路徑。

實驗六 內(nèi)部排序

一、實驗?zāi)康?/p>

直觀感受算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)。

二、預(yù)習(xí)要求

1、常見的排序算法(插入排序、交換排序、選擇排序、歸并排序、基數(shù)排序等)的思想、特點及其適用條件。

2、根據(jù)要求，編寫程序準備上機調(diào)試。

三、實驗內(nèi)容

1、對直接插入排序和簡單選擇排序算法進行關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)的比較。

2、利用鏈式存儲結(jié)構(gòu)，編寫程序，實現(xiàn)直接插入排序和冒泡排序。

四、實現(xiàn)提示

測試數(shù)據(jù)可以為幾組典型的數(shù)據(jù)：正序、逆序、亂序。

五、選做題、思考題

1、快速排序算法的非遞歸實現(xiàn)。

2、結(jié)合實驗，理解針對不同待排元素的特點而選擇不同排序方法的重要性。

3、如何對本實驗進行時間、空間的復(fù)雜度分析。