《數(shù)據(jù)結(jié)構(gòu)》實驗課件

1、精品教學課件設計| Excellent teaching plan本實驗講義共分為十五個單元，每個單元對應一次上機實驗課。不帶 “ * ” 號的上機實驗題目， 主要是為幫助學生深化理解教學內(nèi)容， 澄清基本概念， 并以基本程序設計技能訓練為主要目的而設； 而帶號的上機實驗題目，可激起學生的學習潛能，并對廣泛開拓思路有益。單元一 順序存儲的線性表【學習要點】了解線性表的邏輯結(jié)構(gòu)特征，熟練掌握線性表的順序存儲結(jié)構(gòu)的描述方法，及在其上實現(xiàn)各種基本運算的方法。設線性表存放在向量Aarrsize 的前 elenum 個分量中， 且遞增有序。試設計一算法， 將 x 插入到線性表的適當位置上， 以保持線性表的

2、有序性。用向量作存儲結(jié)構(gòu)，試設計一個算法，僅用一個輔助結(jié)點，實現(xiàn)將線性表中的結(jié)點循環(huán)右移 k 位的運算。用向量作存儲結(jié)構(gòu)，試設計一個算法，僅用一個輔助結(jié)點，實現(xiàn)將線性表逆置的運算。單鏈表單元二【學習要點】熟練掌握線性表的單鏈式鏈接存儲結(jié)構(gòu)及在其上實現(xiàn)線性表的各種基本運算的方法。實驗一：已知帶頭結(jié)點的動態(tài)單鏈表L 中的結(jié)點是按整數(shù)值遞增排序的，試寫一算法將值為 x 的結(jié)點插入到表L 中，使 L 仍然有序。實驗二：設計一算法，逆置帶頭結(jié)點的動態(tài)鏈表L 。要求利用原表的結(jié)點空間，并要求用盡可能少的時間完成。實驗三：假設有兩個按元素值遞增有序的線性表A 和 B, 均以單鏈表作存儲結(jié)構(gòu)，試編寫算法將A表

3、和B表歸并成一個按元素值遞減有序的線性表C,并要求利用原表的空間存放C。單元三 棧和隊列【學習要點】1. 掌握棧和隊列的數(shù)據(jù)結(jié)構(gòu)的特點； 2. 熟練掌握在兩種存儲結(jié)構(gòu)上實現(xiàn)棧和隊列的基本運算； 3. 學會利用棧和隊列解決一些實際問題。實驗一:設單鏈表中存放著n 個字符，設計算法，判斷該字符串中是否有中心對稱關(guān)系。例如： xyzzyx 、 xyzyx 都算是中心對稱的字符串。實驗二:設計算法判斷一個算術(shù)表達式的圓括號是否配對。 （提示： 對表達式進行掃描，遇 （ 進棧，遇 ） 退掉棧頂?shù)?（ ，表達式被掃描完畢，棧為空 ）實驗三 :假設以帶頭結(jié)點的循環(huán)鏈表表示隊列，并只設一個指針指向隊尾，編寫相

4、應的置隊空、入隊和出隊算法。單元四 串【學習要點】熟練掌握串的順序和鏈接存儲結(jié)構(gòu)的實現(xiàn)方法；熟練掌握在兩種存儲結(jié)構(gòu)上實現(xiàn)串的各種運算。實驗一：若 X 和 Y 是用結(jié)點大小為1 的單鏈表表示的串，設計算法找出 X 中第一個不在 Y 中出現(xiàn)的字符。實驗二：設計一算法，在順序串上實現(xiàn)串的比較運算strcmp(S,T) 。單元五 多維數(shù)組和廣義表【學習要點】理解稀疏矩陣的兩種存儲方式的特點和適用范圍，領會以三元組表示稀疏矩陣試進行矩陣運算采用的處理方法；熟悉廣義表的定義及其存儲結(jié)構(gòu)，學會廣義表的表頭、表尾分析方法，學習編制相應的遞歸算法。* 實驗一：假設稀疏矩陣A 和 B 均以三元組表作為存儲結(jié)構(gòu)，試

5、分別寫出滿足以下條件的矩陣相加運算的算法：(1) 另設三元組表C 存放結(jié)果矩陣。(2)假設三元組表 A的空間足夠大，將矩陣B加到矩陣A上，不增加A B之外的附加空間，要求算法的時間復雜度為O(m+n),其中m,n為A、B矩陣中非零元素的數(shù)目。實驗二：設計一個以三元組形式輸出用十字鏈表表示的稀疏矩陣中非零元素及 其下標的算法。單元六 樹(一)【學習要點】熟悉二叉樹的各種存儲結(jié)構(gòu)的特點及適用范圍；掌握建立二叉樹的存儲結(jié)構(gòu)的方法；熟練掌握二叉樹的前序、中序、后序遍歷的遞歸及非遞歸算法；靈活運用遞歸的遍歷算法實現(xiàn)二叉樹的其它各種運算。實驗一：以二叉鏈表作存儲結(jié)構(gòu)，設計求二叉樹高度的算法。實驗二：一棵

6、n 個結(jié)點的完全二叉樹用向量作存儲結(jié)構(gòu)，用非遞歸算法實現(xiàn)對該二叉樹進行前序遍歷。實驗三 :以二叉鏈表作存儲結(jié)構(gòu)，編寫非遞歸的前序、中序、后序遍歷算法。單元八七 樹（二）【學習要點】靈活運用非遞歸的遍歷算法實現(xiàn)二叉樹的其它各種運算；掌握按層次順序遍歷二叉樹的方法；熟練掌握在中序線索二叉樹上找給定結(jié)點的指定順序下的前驅(qū)和后繼的方法。* 實驗一：以二叉鏈表作存儲結(jié)構(gòu)，設計按層次順序（同一層自左向右）遍歷二叉樹的算法。* 實驗二：在二叉樹中查找值為 x 的結(jié)點，編寫算法打印值為 x 的結(jié)點的所有祖先。假設值為 x 的結(jié)點不多于1 個。單元八 圖（一）【學習要點】熟練掌握圖的兩種存儲結(jié)構(gòu)的實現(xiàn)方法；熟練

7、掌握遍歷圖的遞歸和非遞歸算法。實驗一：設計算法，構(gòu)造圖的鄰接鏈表，并遞歸地實現(xiàn)基于鄰接鏈表的圖的深度優(yōu)先搜索遍歷。* 實驗二：利用基于鄰接矩陣的圖的深度優(yōu)先搜索算法，判別有向圖中是否存在由頂點Vi到頂點Vj的路徑（i wj ）。單元十 排序（一）【學習要點】熟練掌握在順序表上實現(xiàn)排序的各種方法；深刻理解各種排序方法的特點，并能靈活運用。實驗一：編寫雙向起泡排序算法。實驗二：編寫算法，使得在盡可能少的時間內(nèi)重排數(shù)組，將所有取負值的關(guān)鍵字放在所有取非負值的關(guān)鍵字的前面。單元十一排序（二）【學習要點】熟練掌握在動態(tài)鏈表及靜態(tài)鏈表上實現(xiàn)各種排序算法; 掌握基數(shù)排序的實現(xiàn)方法。實驗一：以單鏈表為存儲結(jié)構(gòu)實現(xiàn)直接選擇排序。實驗二：用先查找插入位置， 后插入的方法， 在靜態(tài)鏈表上實現(xiàn)直接插入排序。單元十二查找（一）【學習要點】熟練掌握順序查找、二分查找、分塊查找的遞歸及非遞歸算法；熟練掌握散列表上的各種操作。實驗一：給出遞歸的二分查找算法。實驗二：設計用拉鏈法解決沖突