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

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

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

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

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

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

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

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