數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)報(bào)告VIP

1、數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)報(bào)告編制老師 袁宇麗 審定 何文孝（適用于計(jì)算機(jī)科學(xué)學(xué)院2022級(jí)本科同學(xué)）專業(yè):班級(jí)： 級(jí) 班學(xué)號(hào):姓名:2022至2022學(xué)年其次學(xué)期計(jì)算機(jī)科學(xué)學(xué)院試驗(yàn)總結(jié)及意見:試驗(yàn)評(píng)價(jià)（老師）:試驗(yàn)名稱：線性表的應(yīng)用指導(dǎo)老師：余文春試驗(yàn)日期：2022年 月 日 試驗(yàn)地點(diǎn)：北503 成果：試驗(yàn)?zāi)康模?、把握線性表及其挨次存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的概念。2、把握兩種存儲(chǔ)方式的基本運(yùn)算、實(shí)現(xiàn)方法和技術(shù)。3、敏捷應(yīng)用線性表進(jìn)行程序設(shè)計(jì)，解決實(shí)際問(wèn)題。試驗(yàn)內(nèi)容：約瑟夫(Joseph)問(wèn)題的一種描述是：編號(hào)為1, 2,，n的n個(gè) 人按順時(shí)針?lè)较驀蝗?，一開頭任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m, 從第一個(gè)

2、人開頭按順時(shí)針?lè)较蜃?開頭挨次報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。 報(bào)m的人出列，從他在順時(shí)針?lè)较蛏系南乱粋€(gè)人開頭重新從1報(bào)數(shù)， 同樣報(bào)到m的人出列，如此下去，直至全部人全部出列為止。采用循 環(huán)鏈表為存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程，根據(jù)出列的挨次輸出依次出列人的編 號(hào)?；疽螅?、寫出完成試驗(yàn)內(nèi)容的試驗(yàn)方法和源代碼。2、寫出試驗(yàn)數(shù)據(jù)及運(yùn)行結(jié)果。3、寫出在試驗(yàn)過(guò)程中所遇到的問(wèn)題及解決方法。試驗(yàn)總結(jié)及意見:試驗(yàn)評(píng)價(jià)（老師）:試驗(yàn)名稱：棧及隊(duì)列的應(yīng)用指導(dǎo)老師：余文春試驗(yàn)日期：2022年 月 日 試驗(yàn)地點(diǎn)：北503 成果：試驗(yàn)?zāi)康模?、把握隊(duì)列及其存儲(chǔ)結(jié)構(gòu)的概念。2、把握棧、隊(duì)列的基本運(yùn)算、實(shí)現(xiàn)方法和技術(shù)。3、能用棧、隊(duì)列

3、的學(xué)問(wèn)和操作技術(shù)設(shè)計(jì)有肯定難度的程序。試驗(yàn)內(nèi)容：1、假設(shè)算術(shù)表達(dá)式僅由加(+)、減(-)、乘(*)、除()運(yùn)算符組 成，編寫一個(gè)借助堆棧把中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的函數(shù)，為使 問(wèn)題簡(jiǎn)化，可不考慮中綴表達(dá)式不正確的狀況。2、假設(shè)在周末舞會(huì)上，男士們和女士們進(jìn)入舞廳時(shí)，各自排成 一隊(duì)。跳舞開頭時(shí)，依次從男隊(duì)和女隊(duì)的隊(duì)頭上各出一人配成舞伴。 若兩隊(duì)初始人數(shù)不相同，則較長(zhǎng)的那一隊(duì)中未配對(duì)者等待下一輪舞 曲?，F(xiàn)要求寫一算法模擬上述舞伴配對(duì)問(wèn)題?；疽螅?、寫出完成試驗(yàn)內(nèi)容的試驗(yàn)方法和源代碼。2、寫出試驗(yàn)數(shù)據(jù)及運(yùn)行結(jié)果。3、寫出在試驗(yàn)過(guò)程中所遇到的問(wèn)題及解決方法。試驗(yàn)總結(jié)及意見:試驗(yàn)評(píng)價(jià)（老師）:試驗(yàn)

4、名稱：二叉樹的建立與遍歷算法指導(dǎo)老師：余文春試驗(yàn)日期：2022年 月 日 試驗(yàn)地點(diǎn)：北503成果：試驗(yàn)?zāi)康模?、把握二叉樹的定義。2、二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中三種遍歷（前序, 中序，后序）操作的實(shí)現(xiàn)及應(yīng)用。試驗(yàn)內(nèi)容：1、編寫程序，建立一棵二叉樹（以鏈表存儲(chǔ)），對(duì)該二叉樹進(jìn)行 遍歷并輸出該二叉樹的前序，中序，后序遍歷序列。要求前序、中序 遍歷用非遞歸方法，后序遍歷用遞歸方法完成。2、編寫程序，建立一棵二叉樹（以鏈表存儲(chǔ)），實(shí)現(xiàn)二叉樹左右 子樹的交換。3、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)。（要求用非遞歸算法完成） 基本要求：1、寫出完成試驗(yàn)內(nèi)容的試驗(yàn)方法和源代碼。2、寫出試驗(yàn)數(shù)據(jù)及運(yùn)行結(jié)果。

5、3、寫出在試驗(yàn)過(guò)程中所遇到的問(wèn)題及解決方法。試驗(yàn)總結(jié)及意見:試驗(yàn)評(píng)價(jià)（老師）:試驗(yàn)名稱：查找及排序算法指導(dǎo)老師：余文春試驗(yàn)日期：2022年 月 日 試驗(yàn)地點(diǎn)：北503 成果：試驗(yàn)?zāi)康模?、把握基本查找和排序技術(shù)的原理及其實(shí)現(xiàn)方法。2、對(duì)于不同的要求，能選擇比較合理的查找、排序算法，得到 初步的算法分析的訓(xùn)練，提高算法設(shè)計(jì)的力量。試驗(yàn)內(nèi)容：定義一最大長(zhǎng)度為20的結(jié)構(gòu)體數(shù)組（可以在結(jié)構(gòu)體中只定義關(guān) 鍵字域），從鍵盤輸入結(jié)構(gòu)體數(shù)組各元素的關(guān)鍵字值，以輸入-9999 為結(jié)束，對(duì)該數(shù)組中的元素按關(guān)鍵字非遞減的挨次進(jìn)行排序，分別用 冒泡排序，非遞歸的快速排序，遞歸的快速排序方法完成，再用折半 查找方法對(duì)已

6、經(jīng)有序的結(jié)構(gòu)體數(shù)組進(jìn)行操作，輸入一待查紀(jì)錄關(guān)鍵 字，若查找勝利輸出“success”，查找不勝利則輸出“unsuccess，以 上各功能模塊均用函數(shù)實(shí)現(xiàn)。設(shè)計(jì)相應(yīng)算法并分析各排序方法的效 率。該程序運(yùn)行狀況舉例說(shuō)明：運(yùn)行主界面如下圖所示：提示用戶輸入相應(yīng)選項(xiàng)，鍵入數(shù)字1則 進(jìn)行待排序數(shù)據(jù)值的輸入；鍵入數(shù)字2進(jìn)行冒泡排序；鍵入數(shù)字3進(jìn) 行遞歸的快速排序；鍵入數(shù)字4則進(jìn)行遞歸的快速排序；鍵入數(shù)字5 則進(jìn)行折半（二分）查找；鍵入數(shù)字。程序結(jié)束并退出。基本要求：1、寫出完成試驗(yàn)內(nèi)容的試驗(yàn)方法和源代碼。2、寫出試驗(yàn)數(shù)據(jù)及運(yùn)行結(jié)果。3、寫出在試驗(yàn)過(guò)程中所遇到的問(wèn)題及解決方法:|主菜單如下:select 1:輸入待排序元素值select 2:直接插入排序select 3:直接