資料結構實驗指導書
淮陰工學院計算機工程學院
二o一一年八月
實驗1 線性表及其應用1
實驗2 棧和佇列及其應用5
實驗3 二叉樹及其應用10
實驗4 圖及其應用13
實驗5 查詢14
實驗6 排序16
實驗目的
1. 加深對線性表的結構特性的理解；
2. 熟練掌握單鏈錶類的描述方法及其c++實現；
3. 掌握線性表的鏈式儲存結構的應用方法；
4. 從時間和空間的角度對操作演算法進行分析；
5. 加強程式的設計能力和除錯能力。
實驗學時：建議2~4學時
實驗內容
內容1：製作體育彩票（10選7）的選號器類。
【說明】
（1） 體育彩票（10選7）的7個號可以重複；
（2） 建議選號器類從單鏈錶類繼承。用首尾相連的鏈式結構，這樣可以更逼真地模擬「搖獎」過程；而每個號的「搖動」次數可用隨機數來確定。
（3） 怎樣產生隨機數？可以利用c++語言中的種子函式srand( )和產生偽隨機數函式rand( )來實現。（include）
a) 首先，給srand(m )提供乙個「種子」m，它的取值範圍是從0～65535。
b) 然後，呼叫rand( )，是偽隨機數，它會根據提供給srand( )的「種子」值返回乙個隨機數（在0～32767之間）。
c) 根據需要多次呼叫rand( )，從而不斷地得到新的隨機數。
d) 無論何時，你都可以給srand( )提供乙個新的「種子」，從而進一步「隨機化」rand( )的輸出結果。
例如，取m=17，則執行了srand(17)之後，再執行rand( )函式，將得到輸出值94；第二次呼叫rand( )，會得到26,……反覆呼叫rand( )就能產生一系列的隨機數。
注意：若m不變，則rand( )的輸出系列也不變，總是94,26,602,…等等。所以，建議搖號的「種子」選當前日期或時間，以保證每天的搖號值都不相同。
【選做內容】 實現搖獎和對獎操作。
內容2：約瑟夫（joseph）環問題
【問題描述】
約瑟夫問題的一種描述是：編號為1，2，…，n的n個人按順時針方向圍坐一圈,從1起報到k則出圈，下乙個人再從1報起，如此下去直到圈中只有一人為止。求最後剩下的人的編號。
【說明】
1） 建議用迴圈鍊錶儲存方式，設計迴圈鍊錶類和約瑟夫類。
2） 問題改進：在人數n、k及起始報數人確定的情況下，最後剩下的人的編號事前是可以確定的。若每人有乙個密碼ki（整數），留作其出圈後的報到ki後出圈。
密碼ki可用隨機數產生。這樣事前無法確定誰是最後一人。
【選做內容】
1） 約瑟夫問題的改進演算法。
2） 約瑟夫問題的報數方法若採用順時針報數和逆時針報數交替進行，則如何設計資料結構？
【實現提示】
//結點結構和單迴圈鍊錶類定義
enum resultcode;
template
struct node
node(t e,node*next)
t data;
node*link;
};template
class linklist
t currentdata()
void tolocatioin(t &t); //將current指向元素為t的結點
void output() const ; //輸出鍊錶
}; // class linklist
//單迴圈鍊錶類部分成員函式實現
template
linklist::linklist(int msize) //建構函式
front->link=current;
}// joseph類定義
template
class joseph
void getwinner();
};// joseph類
// joseph類實現
template
void joseph::getwinner()
cout<<"\nthe winner is "<}
//主函式main
void main()
catch(enum resultcode err)
}}內容3：多項式的表示和相加
【問題描述】
建立鏈式多項式類，並設計演算法實現多項式的相加。
【要求】
1）設計多項式鍊錶類並實現。
2）相加後可將原多項式銷毀，也可以保留。
【選做內容】多項式的減法、乘法及除法運算。
【問題思考】
建立的鍊錶不帶頭結點與帶頭結點,則在操作實現上有何差異?
實驗目的
1. 加深理解棧和佇列的特性；
2. 能根據實際問題的需要靈活運用棧和佇列；
3. 了解遞迴演算法的設計；
4. 掌握棧和佇列的應用方法。
實驗學時：建議2~4學時
實驗內容
內容1：設計算術表示式求值類
【問題描述】
表示式計算是實現程式語言的基本問題之一，也是棧的應用的乙個典型例子。設計乙個表示式類程式，演示用算符優先法算術表示式求值的過程。
【基本要求】
以字串行的形式輸入語法正確且不含變數的整數表示式。利用教材中給出的算符優先關係表，實現對算術四則混合運算表示式的求值。
【實現提示】
（1） 表示式類說明：
class expression
//建構函式
void del_blank();//刪除串str中所有空格
void calculate(); //對表示式串str進行計算
double getresult() const //獲取表示式的值
}; // class expression
class expression
; // class expression
（2） 順序棧類說明
template
class seqstack //線性表抽象類
{private:
t *s儲存棧空間的首位址
int top棧頂指標
int maxsize棧空間總規模
資料結構實驗指導書 2019級
資料結構實驗指導書 計算機學院專業基礎教研室 2008年3月 實驗一線性表及其應用 1.熟悉c語言的上機環境，進一步掌握c語言的結構特點。2.掌握線性表的順序儲存結構的定義及c語言實現。3.掌握線性表的鏈式儲存結構 單鏈表的定義及c語言實現。4.掌握線性表在順序儲存結構即順序表中的各種基本操作。5....
資料結構實驗指導書
第一部分課程概述 資料結構是計算機程式設計的重要理論技術基礎，它不僅是計算機學科的核心課程，而且已成為其它立功專業的熱門選修課。資料結構實驗可以使學生對資料結構課程所教授的內容通過實驗環節加以實踐，提高學生的程式設計 編寫及除錯能力，是一門基礎的實驗課程。第二部分實驗要求 通過實驗，學生對常用資料結...
資料結構實驗指導書
實驗名稱資料結構試驗 課程名稱資料結構 專業班級學生姓名 學號成績 指導老師實驗日期 2010年3月 5月 實驗報告如列印，紙張用a4，左裝訂 頁邊距 上下2.5cm，左2.5cm，右2.0cm 字型 字型小四號，1.25倍行距。驗證性 綜合性實驗報告應包含的主要內容 一 實驗目的及要求 1 實驗目...