【正文】 和廣度優(yōu)先算法。出現(xiàn)位置所在行的行號(hào)可以用鏈表存儲(chǔ)。文學(xué)研究助手[問題描述]文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。假設(shè)操作數(shù)是正整數(shù)，運(yùn)算符只含加減乘除等四種運(yùn)算符，界限符有左右括號(hào)和表達(dá)式起始、結(jié)束符“”，如：（7+15）*（2328/4）。要求能夠回答有關(guān)景點(diǎn)介紹、游覽路徑等問題。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部分要加上清晰的程序注釋。學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)掌握實(shí)際編程能力是很有幫助的。（3）系統(tǒng)應(yīng)實(shí)現(xiàn)的操作及功能定義如下：①采編入庫：新購入一種書，經(jīng)分類和確定書號(hào)后登記到圖書帳目中去。（2）程序可以對(duì)三元組的輸入順序加以限制，例如，按行優(yōu)先。*選作內(nèi)容：（1）擴(kuò)充運(yùn)算符集，如增加乘方、單目減、賦值等運(yùn)算；（2）運(yùn)算量可以是變量；（3）運(yùn)算量可以是實(shí)數(shù)類型；（4）計(jì)數(shù)器的功能和仿鎮(zhèn)界面。*實(shí)現(xiàn)提示：用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式，多項(xiàng)式的項(xiàng)數(shù)存在頭結(jié)點(diǎn)。1編制一個(gè)求解迷宮通路的圖形界面演示程序。*實(shí)現(xiàn)提示：每次在多個(gè)可走位置中選擇一個(gè)進(jìn)行試探，其余未曾試探過的可走位置必須用適當(dāng)結(jié)構(gòu)妥善管理，以備試探失敗時(shí)的“回溯”(悔棋)使用。用其絕對(duì)值表示元素結(jié)點(diǎn)數(shù)目。*測試數(shù)據(jù)：（1）0；0；應(yīng)輸出“0”。1各種排序*問題描述：對(duì)30000個(gè)隨機(jī)整數(shù)，利用插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序等排序方法進(jìn)行排序，并統(tǒng)計(jì)每一種排序上機(jī)所花費(fèi)的時(shí)間。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直到所有人全部出列為止。進(jìn)行程序測試，以保證程序的穩(wěn)定。四．設(shè)計(jì)題目運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)*問題描述：參加運(yùn)動(dòng)會(huì)有n個(gè)學(xué)校，學(xué)校編號(hào)為1……n。②源程序（可以是一組源程序，即詳細(xì)設(shè)計(jì)部分）源程序要按照寫程序的規(guī)則來編寫。六、課程設(shè)計(jì)教材及主要參考資料 教學(xué)參考書[1]李素若.《數(shù)據(jù)結(jié)構(gòu)》.北京：化學(xué)工業(yè)出版社，：[1] 朱蓉，《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書》[2]嚴(yán)蔚敏 吳偉民，.數(shù)據(jù)結(jié)構(gòu)(C語言版)，1999，清華大學(xué)出版社； [3]嚴(yán)蔚敏 吳偉民，.數(shù)據(jù)結(jié)構(gòu)題集(C語言版)，1999，清華大學(xué)出版社； [4]徐孝凱，數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)，2002，清華大學(xué)出版社；[5]孟佳娜 胡瀟琨，算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)與習(xí)題，2004，機(jī)械工業(yè)出版社；七、其他 i=[1] t=[12] i=[2] t=[4] i=[3] t=[10] i=[4] t=[12] i=[5] t=[1] i=[6] t=[2] i=[7] t=[2] i=[8] t=[11] i=[9] t=[5] i=[10] t=[10] i=[11] t=[11] i=[12] t=[8] i=[13] t=[2] i=[14] t=[3] i=[15] t=[9] i=[16] t=[7] i=[17] t=[5] i=[18] t=[6] i=[19] t=[12] i=[20] t=[7] i=[21] t=[3] i=[22] t=[7] i=[23] t=[8] i=[24] t=[6] i=[25] t=[7] i=[26] t=[8] i=[27] t=[3] i=[28] t=[2] i=[29] t=[7] i=[30] t=[4] i=[31] t=[3] i=[32] t=[8] i=[33] t=[9] i=[34] t=[1] i=[35] t=[1] i=[36] t=[3] i=[37] t=[8] i=[38] t=[1] i=[39] t=[10] i=[40] t=[12] i=[41] t=[10] i=[42] t=[9] i=[43] t=[12] i=[44] t=[2] i=[45] t=[1] i=[46] t=[6] i=[47] t=[4] i=[48] t=[7] i=[49] t=[1]第三篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)教學(xué)大綱《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》教學(xué)大綱Data Structure Course Design一、課程的性質(zhì)、教學(xué)目的和要求《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)軟件的一門基礎(chǔ)課程，計(jì)算機(jī)科學(xué)各領(lǐng)域及有關(guān)的應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。要求：1）創(chuàng)建一顆二叉排序樹，并打印輸出；2）分別編寫函數(shù)完成二叉排序樹的查找、插入和刪除； 3）測試二叉排序樹的查找、插入和刪除，分別打印測試結(jié)果； 4）每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖。佛洛依德算法求最短路徑問題描述：采用佛洛依德算法求每對(duì)頂點(diǎn)到其它頂點(diǎn)的最短路徑。要求：1）可以循環(huán)測試，可以選擇退出程序；2）打印這n個(gè)自然數(shù)進(jìn)行加減的表達(dá)式（注意：中間結(jié)果不能為負(fù)）； 例如：輸入1,2,3，最后打印出321=0 3）輸入數(shù)據(jù)要進(jìn)行合法性檢查；4）每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖。課程設(shè)計(jì)是一種綜合訓(xùn)練，致力于培養(yǎng)學(xué)生全面、靈活的算法設(shè)計(jì)思想和較高的編程能力，為今后從事計(jì)算機(jī)開發(fā)與應(yīng)用打下基礎(chǔ)。1． 上機(jī)情況（20%）包括出勤情況、調(diào)試表現(xiàn)。3．借助適當(dāng)題材的程序設(shè)計(jì)實(shí)訓(xùn)，加深體會(huì)利用數(shù)據(jù)結(jié)構(gòu)的算法技法和C語言程序設(shè)計(jì)解決實(shí)際問題的基本環(huán)節(jié)的思維過程。是《數(shù)據(jù)結(jié)構(gòu)》課程的后續(xù)配套實(shí)踐性課程。三、課程的基本要求要求通過本實(shí)踐性環(huán)節(jié),能較好地鞏固前導(dǎo)相關(guān)的C語言程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)課程的相關(guān)知識(shí),強(qiáng)化程序的編寫和閱讀能力，能較好地滿足全國計(jì)算機(jī)軟件專業(yè)技術(shù)資格和水平考試之初級(jí)程序員的水平考核要求。值得注意的是，要注意要求學(xué)生實(shí)習(xí)報(bào)告的各種文檔資料要在程序開發(fā)的過程中逐漸充實(shí)形成，而不是最后補(bǔ)寫。要求：1）采用函數(shù)形式完成轉(zhuǎn)置、相加、相減和相乘； 2）有輸入數(shù)據(jù)合法性檢查； 3）矩陣的存儲(chǔ)采用動(dòng)態(tài)數(shù)組；4）兩個(gè)矩陣產(chǎn)生后要分別打印出來，完成相應(yīng)處理后結(jié)果要打印出來； 5）每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖?？唆斔箍査惴ㄇ笞钚∩蓸鋯栴}描述：用克魯斯卡爾算法求有向網(wǎng)圖或無向網(wǎng)圖的最小生成樹。分塊查找問題描述：采用分塊查找的方法查找指定的關(guān)鍵碼。1哈希表查找問題描述：定義一個(gè)哈希表和對(duì)哈希表進(jìn)行插入、查找和刪除、打印。二、設(shè)計(jì)要點(diǎn)1．設(shè)計(jì)和調(diào)試過程要規(guī)范化。盡量避免出現(xiàn)操作錯(cuò)誤時(shí)出現(xiàn)死循環(huán)。不同的項(xiàng)目取前五名或前三名積分；取前五名的積分分別為：1，前三名的積分分別為：2；哪些取前五名或前三名由學(xué)生自己設(shè)定。靜態(tài)存儲(chǔ)一頁文章，每行最多不超過80個(gè)字符，共N行。*測試數(shù)據(jù)：m的初值為20，n=7 ,7個(gè)人的密碼依次為3，1，7，2，4，7，4，首先m=6,則正確的輸出是什么？*輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m的初值，n，輸入每個(gè)人的密碼，建立單循環(huán)鏈表。1線性表的操作*問題描述：利作鏈表的插入運(yùn)算建立線性鏈表，然后利用鏈表的查找、刪除、計(jì)數(shù)、輸出等運(yùn)算反復(fù)實(shí)現(xiàn)鏈表的這些操作（插入、刪除、查找、計(jì)數(shù)、輸出單獨(dú)寫成函數(shù)的形式），并能在屏幕上輸出操作前后的結(jié)果。（5）1,0001,0001；1,0001,0000；應(yīng)輸出“1”。不能給長整數(shù)位數(shù)規(guī)定上限。（2）為來訪客人提供圖中任意景點(diǎn)的問路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短的簡單路徑。Home鍵設(shè)置迷宮起點(diǎn)，End鍵設(shè)終點(diǎn)，上下左右箭頭鍵移動(dòng)，Enter鍵添加墻，Del鍵刪除墻，完成后按F9 鍵演示，Esc鍵退出。*基本要求：以字符序列的形式從終端上輸入語法正確的、不含變量的整數(shù)表達(dá)式。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本原酸的運(yùn)算器。23．圖書管理*問題描述：圖書管理基本業(yè)務(wù)活動(dòng)包括：對(duì)一本書的采編入庫、清除庫存、借閱和歸還等等。③某種書的現(xiàn)存量大于零，則借出一本，登記借閱者的圖書證號(hào)和歸還期限。① 需求分析將題目中要求的功能進(jìn)行敘述分析，并且設(shè)計(jì)解決此問題的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，（有些題目已經(jīng)指定了數(shù)據(jù)存儲(chǔ)的，按照指定的設(shè)計(jì)），設(shè)計(jì)或敘述解決此問題的算法，描述算法建議使用流程圖，進(jìn)行算法分析指明關(guān)鍵語句的時(shí)間復(fù)雜度。2．課程設(shè)計(jì)實(shí)習(xí)報(bào)告的書寫格式① 設(shè)計(jì)題目（任選其一）②運(yùn)行環(huán)境（軟、硬件環(huán)境）③算法設(shè)計(jì)的思想 ④算法的流程圖 ⑤算法設(shè)計(jì)分析 ⑥源代碼 ⑦運(yùn)行結(jié)果分析 ⑧收獲及體會(huì) 3．實(shí)施方式可設(shè)23人一題，安排在《數(shù)據(jù)結(jié)構(gòu)》課程開課學(xué)期布置題目，然后在期末前兩周完成。（4）增加、刪除、更新有關(guān)景點(diǎn)和道路的信息。[基本要求]（1）從鍵盤讀入一個(gè)合法的算術(shù)表達(dá)式，輸出正確的結(jié)果。待統(tǒng)計(jì)的詞匯集合要一次輸入完畢，即統(tǒng)計(jì)工作必須在程序的一次運(yùn)行之后就全部完成。[選作內(nèi)容]（1）模式匹配要基于KMP算法。例如：考慮下列的括號(hào)序列：[([ ] [ ])]8當(dāng)計(jì)算機(jī)接受了第1個(gè)括號(hào)以后，他期待著與其匹配的第8個(gè)括號(hào)的出現(xiàn)，然而等來的卻是第2個(gè)括號(hào)，此時(shí)第1個(gè)括號(hào)“[”只能暫時(shí)靠邊，而迫切等待與第2個(gè)括號(hào)相匹配的 第7個(gè)括號(hào)“）”的出現(xiàn)，類似的，因只等來了第3個(gè)括號(hào)“[”，此時(shí)，其期待的緊迫程度較第2個(gè)括號(hào)更緊迫，則第2個(gè)括號(hào)只能靠邊，讓位于第3個(gè)括號(hào)，顯然第3個(gè)括號(hào)的期待緊迫程度高于第2個(gè)括號(hào)，而第2個(gè)括號(hào)的期待緊迫程度高于第1個(gè)括號(hào)；在接受了第4個(gè)括號(hào)之后，第3個(gè)括號(hào)的期待得到了滿足，消解之后，第2個(gè)括號(hào)的期待匹配就成了最急迫的任務(wù)了，??，依次類推。[測試數(shù)據(jù)]設(shè)n=2,輸入數(shù)據(jù)為：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。[選作內(nèi)容]（1）兩個(gè)棧共享空間，思考應(yīng)開辟數(shù)組的空間是多少？（2）汽車可有不同種類，則它們的占地面積不同，收費(fèi)標(biāo)準(zhǔn)也不同，1輛十輪卡車占地面積相當(dāng)于3輛小汽車的占地面積。試按照這種方法實(shí)現(xiàn)一個(gè)簡單的行編輯程序。格式：p逐頁地（每頁20行）顯示活區(qū)內(nèi)容，每顯示一頁之后請(qǐng)用戶決定是否繼續(xù)顯示以后各頁（如果存在）。這些行塊可以組成一個(gè)數(shù)組，也可以利用動(dòng)態(tài) 8 鏈表連接起來。（3）在執(zhí)行行插入命令的過程中，每接收到一行時(shí)到要檢查活區(qū)大小是否已達(dá)activemaxlen。[基本要求]以鄰接表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。（2）以鄰接多重表為存儲(chǔ)結(jié)構(gòu)建立深度優(yōu)先生成樹和廣度優(yōu)先生成樹，再按凹入表或樹形打印生成樹（3）實(shí)現(xiàn)有向圖的遍歷操作。2）根據(jù)用戶界面提示，用鍵盤輸入。設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的過程。利用“稀疏”特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大節(jié)省存儲(chǔ)空間，提高計(jì)算效率。（3）在用三元組表示稀 疏矩陣時(shí)，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積矩陣也可以用二維數(shù)組存放。②清除庫存：某種書已無保留價(jià)值，將它從圖書帳目中注銷。*存儲(chǔ)結(jié)構(gòu)使用線性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；*輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號(hào)。[實(shí)現(xiàn)提示]首先，序列1進(jìn)棧，然后序列1出棧并與序列2比較。②源程序（可以是一組源程序，即詳細(xì)設(shè)計(jì)部分）源程序要按照寫程序的規(guī)則來編寫。首先將物品排成一列，然后順序選取物品裝入背包，假設(shè)已選取了前i 件物品之后背包還沒有裝滿，則繼續(xù)選取第i+1件物品，若該件物品“太大”不能裝入，則棄之而繼續(xù)選取下一件，直至背包裝滿為止。設(shè)計(jì)一個(gè)程序來求出出列順序。1線性表的操作利用鏈表的插入運(yùn)算建立線性鏈表，然后利用鏈表的查找、刪除、計(jì)數(shù)、輸出等運(yùn)算反復(fù)實(shí)現(xiàn)鏈表的這些操作（插入、刪除、查找、計(jì)數(shù)、輸出單獨(dú)寫成函數(shù)的形式），并能在屏幕上輸出操作前后的結(jié)果。（5）1,0001,0001；1,0001,0000；應(yīng)輸出“1”。不能給長整數(shù)位數(shù)規(guī)定上限。*基本要求：以“帶行邏輯鏈接信息”的三元組順序表示稀疏矩陣，實(shí)現(xiàn)兩個(gè)矩陣相加、相減和相乘的運(yùn)算。五、組織管理1．由院、系指派經(jīng)驗(yàn)豐富的專業(yè)教師擔(dān)任指導(dǎo)教師。② 良好：目的明確，態(tài)度端正，能遵守學(xué)校的各項(xiàng)紀(jì)律，工作比較積極主動(dòng)