數據結構課程設計總結.doc

1、數據結構課程設計指導書粧選課程設計周（時）數：1 1周指導方式，集體輔導與個別輔導相結合課程設計適用專業(yè)=網絡工程系一.課程設計的目的1、掌握數據結構與算法的設計方法，初步具備根據應用需求選擇合理數據結構并 進行算法設訃的能力；2、進一步提升C語言的應用能力；2、初步掌握軟件開發(fā)過程的問題分析、系統設計、程序編碼、測試等基本方法和 技能；3、提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；4、訓練用系統的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應具 備的科學的工作方法和作風；5、提升文檔寫作能力。二課程設計要求1、認真分析課題內容和要求，明確設計任務。2、仔細分析課題，合

2、理設計算法。3、一人一題，必須獨立完成。4、必須在規(guī)定的時間內完成課設任務，否則沒有資格參加答辯，無成績。5、嚴禁抄襲，否則取消答辯資格或成績作廢。6、設訃達到一定工作量（300行以上代碼7、課程設訃說明書不少于15貝（不包括代碼）。三、課程設計方法與步驟1、問題定義與需求分析：根據設計題U的要求，充分地分析和理解問題，確定功 能需求和限制條件。2、數據結構設計：對問題描述中涉及的操作對象定義相應的數據類型和各抽象數 據類型，寫出每個抽象數據類型的定義（包括數據結構的描述和每個基本操作的功能說 明）。3、總體設訃：采用結構化設計方法，按照以數據結構為中心的原則劃分模塊，設 計軟件層次結構和模塊

3、間的調用關系，定義主程序，畫出模塊之間的調用關系圖。在這 個過程中，要綜合考慮系統功能，使得系統結構清晰、合理、簡單和易于調試。4、詳細設訃：定義數據存儲結構，各個主要模塊的算法定義。詳細設訃的結果是 對數據結構和基本操作作出進一步的求精，寫出數據存儲結構的類型定義，用偽碼寫出 函數的算法。5、程序編碼：把詳細設訃的結果進一步求精為程序設訃語言程序。同時加入一些 注解，使程序中邏輯概念清楚。要求用C語言編寫。6、程序調試與測試：采用自底向上，分模塊進行，即先調試低層函數。能夠熟練 掌握調試工具的各種功能，設訃測試數據確定疑點，通過修改程序來證實它或繞過它。 調試正確后，認真整理源程序及其注釋，

4、形成格式和風格良好的源程序清單和結果。7、 設計結果分析：程序運行結果包括正確的輸入及其輸出結果和含有錯誤的輸入 及其輸出結果。算法的時間、空間復雜性分析。課程設計名稱：數據結構課程設計指導老師&*粧選8、 編寫課程設訃報告。四.設計選題：1.在圍棋比賽中，某一方（假設為黑方）在棋盤的某個位置（i, j）下子后，有 可能提取對方（0方的一審子）。以W1919表示一個棋盤，若Wij=0表示在位置（i,j）上沒有子，Wij=l表示該位置上的是黑子,Wij=-1表示該位置上是白子。 模擬實現五子棋功能。2.商店貨架以棧的形式擺放商品，生產日期越近的越黑近棧底，出棧是從棧頂取貨，一天營業(yè)結束，

5、如果貨架不滿，則需上貨，如果直接將商品擺放到貨架上，則會使生產 日期越近的越鼎近棧頂這就需要倒貨架，仍使生產日期越近的越幕近棧底。寫出貨物 進棧、出棧算法。3.銀行業(yè)務模擬：銀行業(yè)務模擬問題描述：客戶業(yè)務分為兩種。第一種是申請從銀行得到一筆資金，即取款或借款。第二種是 向銀行投入一筆資金，即存款或還款。銀行有兩個服務窗口，相應的有兩個隊列?？蛻?到達銀行后先排第一個隊。處理每個客戶業(yè)務時，如果屬于第一種，且申請額超出銀行 現存資金總額而得不到滿足，則立即排入第二隊等候，直至滿足時才離開銀行，否則業(yè) 務處理完后立即離開銀行。每接待完一個第二種業(yè)務的客戶，則順序檢查和處理（如果 可能）第二個隊列的

6、客戶，對能滿足的申請者予以滿足，不能滿足者重新排到第二個隊 列的隊尾。注意，在此檢査過程中，一旦銀行資金總額少于或等于剛才第一個隊列中最 后一個客戶（第二種業(yè)務）被接待之前的數額，或者本次已將第二個隊列檢查或處理了 一遍，就停止檢査（因為此時已不可能還有能滿足者）轉而繼續(xù)接待第一個隊列的客戶。 任何時刻都只開一個窗口。假設檢査不需要時間。營業(yè)時間結束時所有客戶立即離開銀 行。寫一個上述銀行業(yè)務的事件驅動模擬系統，通過模擬方法求出客戶在銀行內逗留的 平均時間。4.運動會分數統計程序的設計任務：參加運動會有n個學校，學校編號為1n。比賽分成m個男子項U,和w個女子項U。項U編號為男子1m,女子m+

7、lm+wo不同的項U取前五名或前三 名積分；取前五名的積分分別為：7、5、3、2、1,前三名的積分分別為：5、3、2；哪 些取前五名或前三名山學生自己設定。（ni=20,n=20）功能要求：1） .可以輸入各個項U的前三名或前五名的成績；2） .能統計各學?？偡?，3） .可以按學校編號、學校總分、男女團體總分排序輸db4） ,可以按學校編號査詢學校某個項U的悄況；可以按項U編號査詢取得前三或前 五名的學校。規(guī)定：輸入數據形式和范IS： 20以內的整數（如果做得更好可以輸入學校的名稱， 運動項U的名稱）輸出形式：有中文提示，各學校分數為整形界面要求：有合理的提示，每個功能可以設立菜單，根據提示，

8、可以完成相關的功 能要求。存儲結構：學生自己根據系統功能要求自己設計，但是要求運動會的相關數據要存 儲在數據文件中。 （數據文件的數據讀寫方法等相關內容在C語言程序設計的書上，請 自學解決）請在最后的上交資料中指明你用到的存儲結構；測試數據：要求使用1、全部合法數據；2、整體非法數據；3、局部非法數據。進 行程序測試，以保證程序的穩(wěn)定。測試數據及測試結果請在上交的資料中寫明；5.八皇后問題問題描述：八皇后問題是一個古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀著名的數學 家高斯1850年提出：在8X8格的國際象棋上擺放八個皇后，使其不能互相攻由，即任意兩個皇后 都不能處于同一行、同一

9、列或同一斜線上，基本要求：在一個8 X 8的棋盤里放魚8個皇后，列只有一個皇后）.6.圖書管理基本業(yè)務模擬1）書的登記內容包括書號、 書名、2）號建立索引表（線性表）以提高査找效率;3）主要功能如下：a）釆編入庫：新購一種書，確定書號后，登記到圖書帳B表中，如果表中已有， 則只將庫存量增加；b）借閱.如果一種書的現存量大于0.則借出一本，登記借閱者的書證號和歸還 期限，改變現存量；C）歸還：注銷對借閱者的登記，改變該書的現存量。輸出形式：能按書號、書名、著作者査找?guī)齑娴臅畔⒛馨磳W生的借書證號顯示學生信息和借閱信息書籍入庫 借書功能實現 還書功能實現7.漫步迷宮問題描述：用m行n列的個正方格

10、表示一個迷宮，其中劃有斜線的方格表示不可通行，未劃有斜線的 方格表示可以通行。請編寫尋找從入口到出口的一條最短路徑的程序?；疽螅?）迷宮的規(guī)格（即行數與列數），狀態(tài)設置（即各方格能否通行的狀態(tài)），以及入口和出口的位苣, 均應由輸入隨機確定。2）求得的最短路徑，應該以從入口到出口的路徑上的各個方格的坐標的線性序列輸出。當無通 路時，應該報告無路徑的信息。3）盡量采用結構化程序設計方法，要求對$個模塊的功能及參數作必要的說明。實現提示：（1）迷宮可以采用matrix類型的二維數組A表示。A. rownum與A. colnum分別表示迷宮的實際 的行數打列數。而A. mazeij表示迷宮中第i行

11、第j列的一個方格，用A. mazeij=0表示該 方格可以通行用A. mazeij=l表示該方格不可以通行?；掃x問有多少種擺法。要求毎個皇后兩兩之間不相沖突（在每一橫列豎列斜著作者、現存量和庫存量;粧選(2)由于要尋找從入口到出口的一條最短路徑.最好將迷宮看作是一個圖結構。 則問題轉化為尋 找從對應于入口頂點到對應于出口頂點的一條最短路徑的問題。該問題可以采用從入口頂點出發(fā)， 進行廣度優(yōu)先搜索遍歷，直到遇到出口頂點或者遍歷完畢也沒有遇到出口頂點為止。這二種情況分 別對應于最短路徑探索成功與查無通路的事實。(3)基于上述分析，涉及到數據結構的轉換，即將二維數組表示的迷宮A轉換為以adjlist類

12、型的鄰接表表示的圖結構G。在圖結構中，將迷宮中的每個方格看作是一個頂點。不可通行的方 格都是孤立頂點：相鄰的可通行的方格所對應的頂點之間看作是有邊相連。因此迷宮可以看作是由m如個頂點及無向邊構成的一個非連通的無向圖。盡皆圖是不連通的，但不影響本問 題的求解，而且本問題有解的條件是：入口頂點與出口頂點在同一個連通分量中。 圖結構G中，G. adjk表示編號為k的頂點的鄰接情況的單鏈表的頭指針：G.實際頂點數，而且具有如下關系：G. vexnum=A. rownum*A. colnum(4)為了避免迷宮數據的重復輸入，我們期望A能夠自動地轉換為G。因此應該設訃一個轉換算 法create_adjli

13、st(A. G)o而圖結構中頂點是要編號的，我們約定以行為序，順序給迷宮A中的方 格所對應的頂點編號。這樣迷宮中方格的坐標(即行row和列coD與圖G中所對應的頂點的編號(KP verno)之間具有如下關系：verno= (row-1) * n + colrow= (verno-1) / n + 1col= (verno-1) % n + 1(5)在廣度優(yōu)先搜索遍歷求解最短路徑過程中，應該設置一個隊列queue作為輔助數搖結構：路 徑采用一個整數數組pred來表示。這二個數據結構的存儲結構類型均為list類型，其說明立義如E： typedef intlistMAXVER；隊列queue應該設置

14、front和rear分別指示列首與列尾,queuek表示第k個入列的頂點編號。 采用pred記錄路徑，predEi表示頂點i在廣度優(yōu)先搜索遍歷過程中的前趨頂點的編號，它表明是 經過邊(predi, i)達到頂點i的。這樣，當路徑探索成功時，我們可以從出口頂點倒推出從入 口到出口的一條路徑來。當然要涉及到從頂點編號向方格坐標的反轉換，這個公式在上面已經給出To則輸出的最短路徑應該是：6,106, 95, 95, 85, 7 5, 6 4, 64, 5-4, 4-5, 4 5,3 5, 25,14, 1-3, 1 217 18.交通咨詢系統(最短路徑問題)問題描述：設計一個交通咨詢系統，能讓旅客咨

15、詢從任一個城市頂點到列一個城市頂點之間的最短路徑或 最低費用或最少時間等問題。對于不同咨詢要求，可以輸入城市間的路程或所需要時間或所需費用。 設計分三個部分，一是建立交通網絡圖的存儲結構；二是解決單源最短路徑問題；最后再實現兩個 城市頂點之間的最短路徑問題?；疽螅?）、對城市信息（城市需、城市間的里程）進行編輯：具備添加、修改、刪除功能：2）、對城市間的兩種交通工具：飛機和火車。對飛機航班和列車時刻表進行編輯：里程、航班 和列車vexnum表示圖G中的測試數據：設有如下5行10列的迷宮1 1 11 0 00 0 1000A.&C.raaze=0 01111111 0 0 0 1 1

16、10 10 0 1入口坐標為1,10 1 1 0 0 0 1 1 0 10 0 1 0 0 0 0 1出口坐標為6, 10 11111100粧選班次的添加、修改、刪除；3）、提供兩種最優(yōu)決策：最快到達或最省錢到達。全程只考慮一種交通工具，可以不考慮回程：4）、旅途中的耗費的總時間應包括中轉站的等候時間。其中飛機至少二小時，火車至少一小時：5）、咨詢以用戶和計算機對話方式進行，要注意人機交互的屏幕界而。由用戶選擇最優(yōu)決策原 則和交通工具，輸入超始站、終點站、岀發(fā)時間，輸出信息：最快需要多長時間才能到達及旅費， 或者最少需要多少旅費才能到達及時間，井詳細說明依次于何時何地乘坐哪一趟班機或列車何時到

17、 達何地。實現提示：1）、算法思路（1）數據存儲。城市信息（城市需、代碼）、交通信息（城市間的里程、各航班和列車時刻）存儲 于磁盤文件。建議把城市信息存于文件前面，交通信息存于文件的后而，用fread和fwrite函數操 作。（2）數據的邏輯結構。根據設計任務的描述，其城市之間的旅游交通問題是典型的圖結構，可 看作為有向圖，圖的頂點是城市，邊是城市之間所耗費的時間（要包括中轉站的等候時間）或旅費。（3）數據的存儲結構。采用鄰接表和鄰接矩陣都可作為數據的存儲結構，但當鄰接邊不多時， 宜采用鄰接表，以提高空間的存儲效率。這里建議采用鄰接表作為數據的存儲結構。（4）用不同的功能模塊對城市信息和交通信

18、息進行編輯。添加、修改、刪除功能可用菜單方式 或命令提示方式。只要能方便的對城市信息和交通信息進行管理即可，但要注意人機界面，具體實 現由學生自行設計，也可參考有關程序（屆時在網上提供）。這些工作有不小的工作量。（5）最優(yōu)決策功能模塊（fast or province）=1讀入城市信息和交通信息，用鄰接表生成含權網絡，表頭數組中的元素存放城市名及對方城 市到達該元素所代表城市的所有信息：表頭數組中的元素所對應的單鏈表存放與該元素所代表的城 市有交通聯系的城市（代碼、里程、航班、列車車次）。2根據具體最優(yōu)決策的要求，用Dijkstra法求出岀發(fā)城市到其它各城市的最優(yōu)值（最短時間 或最小的費用），

19、搜索過程中所經過城市的局部最優(yōu)信息都保存在鄰接表的表頭數組中。其目的城市 所代表的元素中就保存了所需的最優(yōu)決策結果。這過程中，要用隊列或棧保存局部最優(yōu)決策值（局部 最短的時間或最省的費用）變小的城市，其相應的初始值可為 8,并在表頭數組對應的城市元素中保 存響應的信息。開始時，棧（隊）中只有岀發(fā)地城市，隨著對棧（隊）頂（首）城市有交通聯系的城市求 得決策值（最短時間或最小的費用），若該值是局部最優(yōu)值且該城市不在棧（隊）中，則進棧（隊），直 至棧（隊）為空。3輸岀結果。從目的城市出發(fā)，搜索到出發(fā)城市，所經過的城市均入棧，再逐一出棧棧中的城 市，輸出保存在表頭數組中對應城市的信息（對方城市的出發(fā)信

20、息，里程、時間、費用等）及最終結 果。即輸出依次于何時何地乘坐幾點的飛機或火車于何時到達何地：最終所需的最快需要多長時間 才能到達及旅費，或者最少需要多少旅費才能到達及時間。（6）主程序可以有系統界面、菜單：也可用命令提示方式；選擇功能模塊執(zhí)行，要求在程序運 行過程中可以反復操作。測試數據：飛機最快到達咨詢：北京到烏魯木齊，北京11點出發(fā)：火車最快到達咨詢：廣州到哈爾濱，廣州10點出發(fā)：飛機最省錢到達咨詢：烏魯木齊到南京，烏魯木齊12點出發(fā)：火車最省錢到達咨詢：沈陽到杭州，沈陽12點出發(fā)：五課程設計考核標準考核時主要有如下兒項參考：1.初步設計內容的考核：是否有查閱資料能力？是否有設計思想？2

21、.程序編碼能力調試能力的考核：程序是否清晰、易讀？在技算計上是否可獨 立完成程序的調試，是否熟練？3.4.六設訃結束后要寫出課程設計報告，以作為整個課程設計評分的書面依據和存檔材料. 設計報告以規(guī)定專用課程設計報告書來寫，版面整潔，圖，表要清楚，工整正文包括以下12個內容：1.設訃U的2.設計內容與要求3.課題分析：以無歧義的陳述說明程序設訃的任務,強調的是程序要做什么，需要 什么結果、所能達到的功能-4.算法思想：闡述要達到課題分析功能準備采用的算法思路。例如：本程序是掃描一個C源程序,有Hash表存儲程序中出現的關鍵字,并統汁該程序中的關鍵字 岀現的頻度。用線性探測法解決Hash沖突。設H

22、ash函數為:Hash (key) =(key的第一個字母序 號)*100+ (Xey的最后一個字母序號)J MOD 4i。算法思想如下:建立一個結構體數組的hash表,存放讀入的關鍵字和其出現的次數。先初始化并建立該hash表,先初始化為”0 ,0,再從文件中一個個讀入所有關鍵字,存放在hash表中相應位宜。從坍一文件中一行行讀入,找出其中非注釋中的也非中的,長度2 8個字符的小寫字 符串,用hash查找,看該單詞是否關鍵字,如是其出現次數加一， 若不是就繼續(xù)下一個這樣的字符串,直至文件尾。崔找這樣的字符串途中,遇到無法匹配的單或雙引號打印出出現在第幾行。Hash表建立好后打印出來。其中核心

23、算法分為兩塊:1. hash表的建立和hash査找。2.尋找上述的字符串。Z建立Hash表的算法:該函數實參為已建立的hash表和住。源程序中找到的一個小寫字母字符串。該字符串key為下標處依次開始查找,到數組末尾是返回數組頭(kcy= (key+1) U4;),分兩種 情況:1若先找到空位,說明該字符串不是關鍵字。則不改變hash表。2若先找到了該關鍵字的紀錄,則該字符串是關鍵字,Khash處y num：2尋找疑似關鍵字字符串的算法說明書質量的考核：設計結構是否合理？敘述是否正確？方案是否可行? 答辯：設計結果的調試能力，對自己設計是否熟練？課程設計報告的內容功能:依次找出被非標識符且非 、

24、/*/隔開的,長度為2 8個字符、非注釋中的.也非 中的小寫字母字符串,因為它可能是關鍵字?；掃x粧選首先,一行行讀入C源程序,用續(xù)行符柑連的幾行當一行一起讀入。（1）.casecase0和case 1：雙引號中的不算,跳過。（T）“”匹配中，“”不算.“II像2單引號中的戲引號不算,而且單引號中不會有關鍵字,所以單引號中的也跳過。3匹配中,T不算,Tl韋、case 2：注釋中的不算,跳過。分為/*/ /1設一個標志符找到/*但在該行沒找到*/時,滬1;此時隹下行中尋找*/ ,以此 類推,直至找到*/后“薩0,以后字符恢復有效。2當找到時放棄該行之后的所有字符,讀入下一行（3）、case 3：讀

25、到大寫字母、下劃線或數字時,肯定該字符串不是關鍵字,則淸除已存在s中的 字符串,井跳過緊接宦后而的允許在標識符中岀規(guī)的字符。4:讀到的是小寫字碌,則存放到字符串S中。case 5：本算法以除“，、/、/*、*/之外的不能在標識符中出現的字符隔開整行字符串, 并判斷被隔開的長度2-8個字符,不含大寫字母、下劃線、數字的字符串（即小寫字母字符串）是 否關鍵字,是則増加其統計個數（判斷方法為hash査找）。5.概要設計：說明本程序中用到的所有抽象數據類型的定義,主程序的流程以及各 程序模塊之間的層次（調用）關系.包括數據結構定義、程序結構、界面設計。例如：（1）數據結構定義struct edgeno

26、defII定義鄰接表的邊結點類型(4) case、int adjvex;該弧所指向的頂點的位置edgenocie * next;指向下條條弧的指針定義鄰接表類型typedef edgenode * * adjUst：(2)程序結構粧選EqualO粧選如圖,main 0函數調用 了PQ個子函數,chu_shi_hash 0、crcatc_hash ()、Gusn_Jian_Zi ()、print 0其中,chii_shi_hashO把hash表初始化為“0000 0,標記空位,便于U后操作。C creatjhashO實規(guī)hash表的創(chuàng)建,從放關鍵字的文件一個個關鍵字,它調用了兩個子函數,equa

27、l ()判斷兩數組是否相等，用來確定某處是否空位.copyO把一個數組賦給另一數組、隹確定插入 位這插入該關鍵字。Guan_Jian_Zi()從C源程序中依次找到可能是關鍵字的字符串,然后用hash查找判斷它是否 關鍵字,是則增加其統汁次數。它調用了兩個子函數:PanDuan (char)和chang_hash (Hash,const char ch J),前者用來判斷一個字符的的類別,后者在hash表中査找判斷ch是否關鍵字,是則 增加其在hash表中的統汁量。而chandhash ()調用了函數equal 0,用來確定某處是否空位或ch .print (bash)用來打印hash表界而設計

28、(略)6.詳細設計:進一步細化概要設計中定義的各模塊或函數功能，畫出算法實現流程 圖-7.測試數據定義：定義典型的測試輸入數據，包括各種體現課設正常功能的數據, 也包括各種異常測試數據。測試數據應與課題分析所要求的U標一致。&源碼：打印9.測試結果：打印例如：錨A圖的頂點數M M新、是否!2!Ul!-!-!2!-!-!1!-!-!1!1 1 : :U2rU2r- -13!*!13!*!3 3 !U4!-!-!eri!U4!-!-!eri目的深應 ft 無M 歷序列：1313 4 4 2 2歷序列1313 2 2 4 4將選2 2 !U3!-!U3!-10.算法分析：算法的時空分析(包括基本操作和其他算法的時間復雜度和空間復 雜度的分析)和改進設想；12使用說明：13.總結與體會：要寫出自己的真實感受。例如一：轉眼,為期兩周的數據結構課程設計實習即將結束了。在這次實習中,自己的C語言知識和數據結構知識得到了鞏固,編程能力也有了一定的提高。同時也學會了解 決問題的方法?？偨Y起來,自己主要有以下兒點體會:1必須牢固掌握基礎知識。山于C語言是大一所學知識,有所遺忘,且未掌握好這 學期所學的數據結構這門課,所以在實習之初感到棘手。不知如何下手,但在后來 的實習過程中自己通過看書和課外資料,