數(shù)據(jù)結(jié)構(gòu)課程設(shè)計教學(xué)大綱(留存版)

　　

【正文】 算法的流程圖 ⑤算法設(shè)計分析 ⑥源代碼 ⑦運行結(jié)果分析 ⑧收獲及體會 3．實施方式可設(shè)23人一題，安排在《數(shù)據(jù)結(jié)構(gòu)》課程開課學(xué)期布置題目，然后在期末前兩周完成。[基本要求]（1）從鍵盤讀入一個合法的算術(shù)表達(dá)式，輸出正確的結(jié)果。[選作內(nèi)容]（1）模式匹配要基于KMP算法。[測試數(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）。試按照這種方法實現(xiàn)一個簡單的行編輯程序。這些行塊可以組成一個數(shù)組，也可以利用動態(tài) 8 鏈表連接起來。[基本要求]以鄰接表為存儲結(jié)構(gòu)，實現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。2）根據(jù)用戶界面提示，用鍵盤輸入。利用“稀疏”特點進(jìn)行存儲和計算可以大大節(jié)省存儲空間，提高計算效率。②清除庫存：某種書已無保留價值，將它從圖書帳目中注銷。[實現(xiàn)提示]首先，序列1進(jìn)棧，然后序列1出棧并與序列2比較。首先將物品排成一列，然后順序選取物品裝入背包，假設(shè)已選取了前i 件物品之后背包還沒有裝滿，則繼續(xù)選取第i+1件物品，若該件物品“太大”不能裝入，則棄之而繼續(xù)選取下一件，直至背包裝滿為止。1線性表的操作利用鏈表的插入運算建立線性鏈表，然后利用鏈表的查找、刪除、計數(shù)、輸出等運算反復(fù)實現(xiàn)鏈表的這些操作（插入、刪除、查找、計數(shù)、輸出單獨寫成函數(shù)的形式），并能在屏幕上輸出操作前后的結(jié)果。不能給長整數(shù)位數(shù)規(guī)定上限。五、組織管理1．由院、系指派經(jīng)驗豐富的專業(yè)教師擔(dān)任指導(dǎo)教師。其目的就是要達(dá)到理論與實際相結(jié)合，使學(xué)生能夠根據(jù)數(shù)據(jù)對象的特性，學(xué)會數(shù)據(jù)組織的方法，能把現(xiàn)實世界中的實際問題在計算機內(nèi)部表示出來，并培養(yǎng)良好的程序設(shè)計技能。有關(guān)的考查相關(guān)材料（文字材料以及磁盤或光盤）統(tǒng)一妥善保管。通過了答辯。（2）程序可以對三元組的輸入順序加以限制，例如，按行優(yōu)先。（2）可以利用頭結(jié)點數(shù)據(jù)域的符號代表長整數(shù)的符號。拓?fù)渑判颍?）問題描述：編寫函數(shù)實現(xiàn)圖的拓?fù)渑判颉?．課程設(shè)計實習(xí)報告的書寫格式① 設(shè)計題目數(shù)據(jù)結(jié)構(gòu) 408104 計算機科學(xué)與技術(shù) 72 30 2012．6436104 軟件工程審 核 人：②運行環(huán)境（軟、硬件環(huán)境）③算法設(shè)計的思想 ④算法的流程圖 ⑤算法設(shè)計分析 ⑥源代碼 ⑦運行結(jié)果分析 ⑧收獲及體會 3．實施方式可設(shè)34人一題，安排在《數(shù)據(jù)結(jié)構(gòu)》課程開課學(xué)期布置題目，然后在期末兩周時間內(nèi)完成?！倚蛄? 是序列1的逆序列。（2）作為演示系統(tǒng)，不必使用文件，全部數(shù)據(jù)可以都在內(nèi)存存放。（2）在輸入表達(dá)式的字符序列的同時，完成運算符和運算數(shù)（整數(shù)）的識別處理，以及相應(yīng)的運算。*輸出的形式：數(shù)字大小逐個遞增的數(shù)列?1圖的遍歷*問題描述：對任意給定的圖（頂點數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊列的五種基本運算（置空隊列、進(jìn)隊、出隊、取隊頭元素、判隊空）實現(xiàn)圖的廣度優(yōu)先搜索周游。[選作內(nèi)容]（1）對于命令格式非法等一切錯誤作嚴(yán)格檢查和適當(dāng)處理。注意測試邊界數(shù)據(jù)，如首行、尾行。限制這些操作以行為單位進(jìn)行的編輯程序稱為行編輯程序。[測試數(shù)據(jù)]輸入 （[ ]（）），結(jié)果“匹配”輸入 [（）]，結(jié)果“此串括號匹配不合法”為起始和結(jié)束標(biāo)志。這樣，每讀入一行，就統(tǒng)計每個詞在這行中的出現(xiàn)次數(shù)。算術(shù)表達(dá)式求值[問題描述]一個算術(shù)表達(dá)式是由操作數(shù)(operand)、運算符(operator)和界限符(delimiter)組成的。②源程序（可以是一組源程序，即詳細(xì)設(shè)計部分）源程序要按照寫程序的規(guī)則來編寫。但是由于上述四項基本業(yè)務(wù)活動都是通過書號（即關(guān)鍵字）進(jìn)行的，所以要用B樹對書號盡力索引，以獲得高效率。（3）在識別出運算數(shù)的同時，要將其字符序列形式轉(zhuǎn)換成整數(shù)形式。頂點和邊均含有相關(guān)信息。（2）可以利用頭結(jié)點數(shù)據(jù)域的符號代表長整數(shù)的符號。1拓?fù)渑判?問題描述：編寫函數(shù)實現(xiàn)圖的拓?fù)渑判?。（?shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關(guān)內(nèi)容在c語言程序設(shè)計的書上，請自學(xué)解決）請在最后的上交資料中指明你用到的存儲結(jié)構(gòu)；測試數(shù)據(jù)：要求使用全部合法數(shù)據(jù)；整體非法數(shù)據(jù)；局部非法數(shù)據(jù)。如果程序不能正常運行，寫出實現(xiàn)此算法中遇到的問題，和改進(jìn)方法。二叉排序樹問題描述：完成二叉排序樹的創(chuàng)建、查找、插入和刪除操作。問題描述：實現(xiàn)線索二叉樹的生成、遍歷、查找、插入和刪除操作。課程設(shè)計是一種綜合訓(xùn)練，致力于培養(yǎng)學(xué)生全面、靈活的算法設(shè)計思想和較高的編程能力，為今后從事計算機開發(fā)與應(yīng)用打下基礎(chǔ)。佛洛依德算法求最短路徑問題描述：采用佛洛依德算法求每對頂點到其它頂點的最短路徑。六、課程設(shè)計教材及主要參考資料 教學(xué)參考書[1]李素若.《數(shù)據(jù)結(jié)構(gòu)》.北京：化學(xué)工業(yè)出版社，：[1] 朱蓉，《數(shù)據(jù)結(jié)構(gòu)實驗指導(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)課程實驗，2002，清華大學(xué)出版社；[5]孟佳娜 胡瀟琨，算法與數(shù)據(jù)結(jié)構(gòu)實驗與習(xí)題，2004，機械工業(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è)計教學(xué)大綱《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》教學(xué)大綱Data Structure Course Design一、課程的性質(zhì)、教學(xué)目的和要求《數(shù)據(jù)結(jié)構(gòu)》是計算機軟件的一門基礎(chǔ)課程，計算機科學(xué)各領(lǐng)域及有關(guān)的應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。四．設(shè)計題目運動會分?jǐn)?shù)統(tǒng)計*問題描述：參加運動會有n個學(xué)校，學(xué)校編號為1……n。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止。*測試數(shù)據(jù)：（1）0；0；應(yīng)輸出“0”。*實現(xiàn)提示：每次在多個可走位置中選擇一個進(jìn)行試探，其余未曾試探過的可走位置必須用適當(dāng)結(jié)構(gòu)妥善管理，以備試探失敗時的“回溯”(悔棋)使用。*實現(xiàn)提示：用帶頭結(jié)點的單鏈表存儲多項式，多項式的項數(shù)存在頭結(jié)點。（2）程序可以對三元組的輸入順序加以限制，例如，按行優(yōu)先。學(xué)好數(shù)據(jù)結(jié)構(gòu)對掌握實際編程能力是很有幫助的。要求能夠回答有關(guān)景點介紹、游覽路徑等問題。文學(xué)研究助手[問題描述]文學(xué)研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。在上交資料中請寫明：存儲結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、算法的時間復(fù)雜度、另外可以提出算法的改進(jìn)方法；[實現(xiàn)提示]可以用一個二維數(shù)組存儲迷宮圖，值為1或者0分別表示通路和不通； 搜索路徑可以參考樹的深度優(yōu)先和廣度優(yōu)先算法。[實現(xiàn)提示]需另設(shè)一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結(jié)構(gòu)實現(xiàn)。兩種格式的例子是：“d10↙”和“d10□14↙”（3）活區(qū)切換。（2）初始化過程包括：請用戶提供輸入文件名（空串表示無輸入文件）和輸出文件名，兩者不能相同。通過輸入圖的全部邊輸入一個圖，每個邊為一個數(shù)對，可以對邊的輸入順序作出某種限制。5）當(dāng)未輸入起點時，消息顯示“Error： You must set Startplace.”；未輸入終點時，顯示“Error： You must set Endplace.” 找到路徑時，屏幕顯示足跡，并在消息框出現(xiàn)Path found，否則消去足跡，顯示Path not ．一元稀疏多項式計算器*問題描述：一元多項式簡單計算器的基本功能是：（1）輸入并建立多項式；（2）輸出多項式，輸出形式為整數(shù)序列n,c1,e1,c2,e2,?,en，其中n是多項式的項數(shù)，ci和ei分別是第I項的系數(shù)和指數(shù)，序列指指數(shù)降序排列；（3）多項式a和b相加，建立多項式a+b；（4）多項式a和b相減，建立多項式ab?？稍O(shè)矩陣的行數(shù)和列數(shù)均不超過20。下列B樹的打印格式如下所示：1文章編輯*問題描述：輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)。給出實現(xiàn)功能的一組或多組測試數(shù)據(jù)，程序調(diào)試后，將按照此測試數(shù)據(jù)進(jìn)行測試的結(jié)果列出來。joseph環(huán)（1）問題描述編號是1，2，??,n的n個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）。*測試數(shù)據(jù)：（1）0；0；應(yīng)輸出“0”。16．稀疏矩陣運算器*問題描述：稀疏矩陣是指那些多數(shù)元素為0的矩陣。工作認(rèn)真，積極 主動，吃苦耐勞，能出色的完成設(shè)計任務(wù)。六、成績評定由指導(dǎo)教師根據(jù)學(xué)生完成任務(wù)的情況、課程設(shè)計說明書的質(zhì)量和課程設(shè)計過程中的工作態(tài)度等綜合打分。課程設(shè)計成績：上機情況（20%）包括出勤情況、調(diào)試表現(xiàn)。答辯準(zhǔn)確流利。實現(xiàn)一個能進(jìn)行稀疏矩陣基本原酸的運算器。（3）9999,9999；1,0000,0000,0000；應(yīng)輸出“999（4）1,0001,0001；1,0001,0001；應(yīng)輸出“0”。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止。如果程序不能正常運行，寫出實現(xiàn)此算法中遇到的問題，和改進(jìn)方法。*要求（1）分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）統(tǒng)計某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。注意研究教科書中的算法，以便提高計算效率。16．算術(shù)表達(dá)式求值演示*問題描述：表達(dá)式求值是實現(xiàn)程序設(shè)計語言的基本問題之一，也是棧的應(yīng)用的一個典型例子。[選作內(nèi)容]（1）借助于棧類型（自己定義和實現(xiàn)）將深度優(yōu)先遍歷用非遞歸算法實現(xiàn)。x的值可以自定，例如20。（4）活區(qū)顯示。棧中每個元素表示一輛汽車，包含兩個數(shù)據(jù)項：汽車的牌照號碼和進(jìn)入停車場的時刻。檢驗括號是否匹配的方法可用“期待的緊迫程度”這個概念來描述。[基本要求]英文小說存于一個文本文件中。（3）查詢圖中任意兩個景點間的所有路徑。二、設(shè)計要點1．設(shè)計和調(diào)試過程要規(guī)范化。（3）在用三元組表示稀疏矩陣時，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積矩陣也可以用二維數(shù)組存放。設(shè)計一個程序