數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告

浙江師范大學(xué)數(shù)理與信息學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法解析報告班級：計算機(jī)051班曹瑋（05190101）葛生生（05190107）董毅（04190107）指導(dǎo)老師：瞿有甜數(shù)理與信息工程學(xué)院《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計》課程設(shè)計組號:

無

設(shè)計主題

:

數(shù)據(jù)結(jié)構(gòu)相關(guān)實(shí)現(xiàn)程序指導(dǎo)老師

:

瞿有甜

組長(學(xué)號):

曹瑋（05190101）組員(學(xué)號):葛生生（05190107）、董毅（04190107）完成時間:2007年1月26日課程設(shè)計內(nèi)容描述:課程設(shè)計要求學(xué)生必定仔細(xì)閱讀《數(shù)據(jù)結(jié)構(gòu)與算法解析》課程設(shè)計方案，仔細(xì)主動完成課程設(shè)計的要求。有問題及時主動經(jīng)過各種方式與教師聯(lián)系溝通。學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時間，安排好課程設(shè)計的時間計劃，并在課程設(shè)計過程中不斷檢測自己的計劃完成情況，及時的向教師報告。課程設(shè)計依照授課要求需要兩周時間完成，兩周中每天（按每周5天）最少要上3-4小時的機(jī)來調(diào)試C語言設(shè)計的程序，總合最少要上機(jī)調(diào)試程序30小時。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計的詳細(xì)內(nèi)容本次課程設(shè)計完成以下模塊（共9個模塊，學(xué)生能夠在其中最少優(yōu)選6個功能塊完成，但有**號的模塊是必定要選擇的）（1）運(yùn)動會分?jǐn)?shù)統(tǒng)計**（2）訂票系統(tǒng)（3）約瑟夫環(huán)（Joseph）（4）猴子選大王**（5）建立二叉樹，層序、先序遍歷（用遞歸或非遞歸的方法都能夠）**（6）赫夫曼樹的建立（7）紙牌游戲**（8）圖的建立及輸出基本目標(biāo):《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》課程，可使學(xué)生深入理解書本知識，致力于用學(xué)過的理論知識和上機(jī)獲取的實(shí)踐經(jīng)驗(yàn)，解決詳細(xì)、復(fù)雜的實(shí)責(zé)問題，培養(yǎng)軟件工作者所需的著手能力、獨(dú)立解決問題的能力。該課程設(shè)計重視軟件設(shè)計的綜合訓(xùn)練，包括問題解析、整體結(jié)構(gòu)設(shè)計、用戶界面設(shè)計、程序設(shè)計基本技術(shù)和技巧、多人合作，致使一整套軟件工作規(guī)范的訓(xùn)練和科學(xué)作風(fēng)的培養(yǎng)。技術(shù)簡述(設(shè)計思想、技術(shù)方案、制作環(huán)境、方法描述等):該實(shí)驗(yàn)采用模塊化設(shè)計方案，界面友好，可讀性強(qiáng)，用vc環(huán)境編程。該程序?qū)崿F(xiàn)菜單化、可視化、界面優(yōu)異的輸入和輸出收效，各部分之間用模塊連接。第一部分模塊實(shí)現(xiàn)輸入功能，用戶可依照提示按要求輸入；在選擇數(shù)字后，就進(jìn)入了第二部分的各個分模塊中。第一模塊是約瑟夫環(huán)（Joseph）問題，這是一個模擬報數(shù)的問題，用戶依照提示輸入總的人數(shù)和要循環(huán)報的數(shù)，經(jīng)過運(yùn)行程序輸出最后剩下的人的編號。第二模塊是相關(guān)二叉樹的層序和先序遍歷問題，輸入結(jié)點(diǎn)數(shù)，建立二叉樹，爾后層序和先序輸出結(jié)果。第三模塊是相關(guān)哈夫曼樹的建立，輸入要建立的哈夫曼樹各結(jié)點(diǎn)的權(quán)值，依照最優(yōu)生成樹的建立方法建立哈夫曼樹，最后輸出最小全值。第四模塊是紙牌游戲，用戶按要求輸入和輸出，這是一道典型的模擬試題。第五模塊是相關(guān)圖的廣度優(yōu)先遍歷和深度優(yōu)先遍歷問題，輸入各邊的兩端點(diǎn)和長度，建立儲藏結(jié)構(gòu)，按兩種方法輸出。第六模塊是相關(guān)運(yùn)動會分?jǐn)?shù)統(tǒng)計的問題。最后的就是第三部分內(nèi)容，即輸出部分。分工情況:1）運(yùn)動會分?jǐn)?shù)統(tǒng)計**葛生生2）訂票系統(tǒng)董毅3）文章編寫**略4）約瑟夫環(huán)（Joseph）葛生生5）猴子選大王**曹瑋（6）建立二叉樹，層序、先序遍歷（用遞歸或非遞歸的方法都能夠）**董毅7）赫夫曼樹的建立曹瑋8）紙牌游戲**葛生生9）圖的建立及輸出葛生生主菜單程序編寫：董毅、葛生生、曹瑋程序匯總和說明：董毅、葛生生、曹瑋報告整合，文字編寫：曹瑋需求解析：該程序?qū)崿F(xiàn)菜單化、可視化、界面優(yōu)異的輸入和輸出收效，各部分之間用模塊連接。第一部分模塊實(shí)現(xiàn)輸入功能，用戶可依照提示按要求輸入；在選擇數(shù)字后，就進(jìn)入了各個分模塊中。第一模塊是約瑟夫環(huán)（Joseph）問題，這是一個模擬報數(shù)的問題，用戶依照提示輸入總的人數(shù)和要循環(huán)報的數(shù)，經(jīng)過運(yùn)行程序輸出最后剩下的人的編號。第二部分是相關(guān)二叉樹的層序和先序遍歷問題，輸入結(jié)點(diǎn)數(shù)，建立二叉樹，爾后層序和先序輸出結(jié)果。第三部分是相關(guān)哈夫曼樹的建立，輸入要建立的哈夫曼樹各結(jié)點(diǎn)的權(quán)值，依照最優(yōu)生成樹的建立方法建立哈夫曼樹，最后輸出最小全值。第四部分是紙牌游戲，用戶按要求輸入和輸出，這是一道典型的模擬試題。第五部分是相關(guān)圖的廣度優(yōu)先遍歷和深度優(yōu)先遍歷問題，輸入各邊的兩端點(diǎn)和長度，建立儲藏結(jié)構(gòu)，按兩種方法輸出。第六部分是相關(guān)運(yùn)動會分?jǐn)?shù)統(tǒng)計的問題。大綱設(shè)計：第一部分：相關(guān)運(yùn)動會分?jǐn)?shù)統(tǒng)計的問題，涉及排序、找尋算法，用到結(jié)構(gòu)體，鏈表的運(yùn)用以及數(shù)組等數(shù)據(jù)結(jié)構(gòu)，按要求實(shí)現(xiàn)即可。第二部分：飛機(jī)定票系統(tǒng)，經(jīng)過結(jié)構(gòu)體，和兩個單鏈表的運(yùn)用完成飛機(jī)定票系統(tǒng)的各項(xiàng)功能設(shè)計，再在主函數(shù)里實(shí)現(xiàn)這些功能。第三部分：約瑟夫環(huán)（Joseph）問題實(shí)際上是一個模擬問題，我們能夠利用鏈表這一數(shù)據(jù)結(jié)構(gòu)來求解，利用鏈表的刪除結(jié)點(diǎn)來模擬人的退出，直到最后只剩下一個結(jié)點(diǎn)。第四部分：猴子選大王的思想和約瑟夫環(huán)相同，不做解析。第五部分：二叉樹的層序和先序遍歷問題，我們能夠經(jīng)過建立二叉樹來實(shí)現(xiàn)這一要求，遍歷能夠用遞歸或非遞歸算法實(shí)現(xiàn)。第六部分：建立哈夫曼樹并編碼，所用的數(shù)據(jù)結(jié)構(gòu)也是二叉樹，算法就是生成最優(yōu)二叉樹的算法最后依照左0右1的序次編碼，并輸出哈夫曼樹和各個字符的哈夫曼編碼。第七部分：模擬紙牌游戲，依照數(shù)的因子的個數(shù)是否是偶數(shù)，奇數(shù)來確定牌的向上還是朝下，在循環(huán)的時候，時間復(fù)雜度明顯降低。第八部分：圖的廣度優(yōu)先遍歷，用毗鄰矩陣儲藏。算法就是圖的固定算法。詳細(xì)設(shè)計：見源程序。調(diào)試解析：第一部分是相關(guān)運(yùn)動會的，時間和空間復(fù)雜度計算都比較復(fù)雜，運(yùn)動會在調(diào)試的時候出現(xiàn)的問題最多，頭文件就有很多問題，一開始的時候出現(xiàn)的120個錯誤都是相關(guān)頭文件的，因?yàn)榧扔胹tudio.h又用iostream，所以問題比很多，隨后一致為studio,h則問題獲取解決，從中知道，兩個頭文件不能夠混雜使用，運(yùn)動會數(shù)涉及到文件的輸入輸出，這里也碰到很多問題，第一是文件不能夠正常的讀出，以及一些格式的錯誤，最后也獲取解決，整個程序最主要的是建立學(xué)校和項(xiàng)目這兩個鏈表，以及兩者之間的詳細(xì)關(guān)系，所以這個地方比較簡單搞錯，只要能熟練運(yùn)用鏈表，就沒問題。第二部分的任務(wù)：設(shè)計系統(tǒng)，實(shí)現(xiàn)飛機(jī)定票，退票，盤問航班信息，自定義儲藏結(jié)構(gòu)，設(shè)計程序完成功能.程序設(shè)計：用單鏈表數(shù)據(jù)結(jié)構(gòu)分別儲藏航班和乘客的信息。定票：用鏈表查找方法查找出乘客鏈表c的尾節(jié)點(diǎn)，用來增加定票乘客的信息。查找航班鏈表h的第一個還有空座位的節(jié)點(diǎn)，更正其中的座位信息。退票：在乘客鏈表中按名字找到該乘客的節(jié)點(diǎn)，做鏈表的刪除操作。再找到航班.鏈表h的第一個還有空座位的節(jié)點(diǎn)，其中的座位信息加1。盤問：即兩個鏈表的遍歷，在遍歷過程中輸出各節(jié)點(diǎn)的信息。1、用于儲藏的數(shù)據(jù)結(jié)構(gòu)的選擇：單鏈表。2、如何用鏈表實(shí)現(xiàn)各個功能的實(shí)現(xiàn)。以前一般做一些只有一個鏈表的題目，而且自己又缺少實(shí)踐練習(xí)，現(xiàn)在要實(shí)現(xiàn)系統(tǒng)的定票和退票功能時必定要用到二個鏈表，一開始無從下手。今后仔細(xì)解析，再經(jīng)過翻書看程序?qū)W習(xí)如何辦理兩個鏈表，牢固了鏈表插入、查找、刪除、遍歷的基本知識，也搞清楚了一些原來不懂的問題，似懂非懂的問題。還有一些很微小的錯誤，編程的時候一不小心就錯了，但找錯誤要花很多時間，有的時候甚至要比重新遍一次還難，找到錯誤才發(fā)現(xiàn)可是一個很簡單的語句。這就是基本功的問題了，現(xiàn)在這個程序還知識簡單地實(shí)現(xiàn)了一點(diǎn)功能，還可是一個不完滿的系統(tǒng)，今后要加強(qiáng)鍛煉。第三部分的約瑟夫環(huán)（Joseph）問題采用鏈表實(shí)現(xiàn)功能，時間復(fù)雜度為O(n2)的，若采用數(shù)學(xué)方法，則復(fù)雜度為O(n)的。第四部分和第三部分相同。第五部分是二叉樹的層序和先序遍歷若采用遞歸算法，復(fù)雜度為O(n),但空間開銷比較大，若用非遞歸算法，時間上開銷大些，空間省些。第六部分建立哈夫曼樹并編碼的時間和空間上的開銷都是O(n*logn)的。第七部分：模擬紙牌游戲，運(yùn)用到的是一個數(shù)的因子，因?yàn)橹蝗羰撬囊蜃?，他就會被翻一次，所以只要計算出它的因子就可以了，這樣使時間復(fù)雜度大大降低，小于O(n2)；也能夠先把使素數(shù)的先定下來，因?yàn)樗槐环幌?，也即朝下，但是要先找到素?shù)，這個時間就比較浪費(fèi)。第八部分是圖的圖的廣度優(yōu)先遍歷，也用矩陣儲藏，時間復(fù)雜度為O(n2)的。在編寫的時候發(fā)現(xiàn)用深度找尋不能夠正常輸出答案，這個問題還沒有獲取解決，因?yàn)槲覀冇玫氖沁f歸的算法，還沒有找到解決方法。課設(shè)總結(jié)：本學(xué)期我們學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)課程，在此以前，我們中的很多人參加了暑期ACM訓(xùn)練，經(jīng)過基本的訓(xùn)練和基礎(chǔ)知識的牢固，在對數(shù)據(jù)結(jié)構(gòu)算法進(jìn)行初步認(rèn)識的同時也提高了語言設(shè)計能力，本次短學(xué)期在經(jīng)過一個學(xué)期數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)后，我們總結(jié)歸納了重點(diǎn)知識，并經(jīng)過重點(diǎn)知識的運(yùn)用設(shè)計了一個多功能菜單，以實(shí)現(xiàn)多方面的需求。就我們計算機(jī)專業(yè)看來，編程能力是很重要的，一個計算機(jī)專業(yè)學(xué)生第一需要認(rèn)識的運(yùn)用的知識就是程序語言設(shè)計。而要學(xué)習(xí)編程,必定明確學(xué)習(xí)的目的，也就是學(xué)習(xí)編程是為了什么。是為了認(rèn)識計算機(jī)，還是為了自己的發(fā)展也許是因?yàn)閭€人愛好。程序的實(shí)現(xiàn)不是一時愛好就可以完成的。一般來說在學(xué)習(xí)程序設(shè)計方法和語言時掌握基本理論及語法時比較簡單，但是在實(shí)質(zhì)應(yīng)用和算法預(yù)計時卻感覺無從下手。比方本次程序設(shè)計中的第一個程序，運(yùn)動會分?jǐn)?shù)統(tǒng)計，拿到題目的時候感覺很簡單，能夠經(jīng)過結(jié)構(gòu)體輸入文本和數(shù)據(jù)，爾后經(jīng)過幾個函數(shù)的計算得出分?jǐn)?shù)，但是在語言編寫過程中，發(fā)現(xiàn)無法區(qū)分各學(xué)校以及各選手，無法用合適的方法儲蓄數(shù)據(jù)和字符，這就是知識在實(shí)質(zhì)中的運(yùn)用問題。如何編寫吻合要求的程序、如何編寫高質(zhì)量的程序更是我們所面對的難題。這就要求我們仔細(xì)領(lǐng)悟，在屢次實(shí)踐的過程中掌握編程技巧，經(jīng)過不斷的戰(zhàn)勝困難來提高自己的編程能力。這是一個長遠(yuǎn)的過程，所以必定有堅定的恒心才能開始學(xué)習(xí)。這是我們在本次課程設(shè)計中獲取的領(lǐng)悟之一。經(jīng)過本次課程設(shè)計，我們領(lǐng)悟到編程能力的高低主若是由以下幾點(diǎn)決定：①編程的習(xí)慣；②數(shù)學(xué)應(yīng)用能力，其中包括邏輯思想，解析問題的能力；③對數(shù)據(jù)結(jié)構(gòu)的認(rèn)識能力；④經(jīng)驗(yàn)的多少，包括各種語言的掌握能力。其實(shí)，最主要的一點(diǎn)還是要仔細(xì)勤奮，為自己的目標(biāo)而不怕困難不斷前進(jìn)，這不行是對程序設(shè)計而言，學(xué)習(xí)其他所有的東西都應(yīng)這樣。為了做出一個程序，我們組組員甚至一大早到機(jī)房編程，向到達(dá)深夜。數(shù)據(jù)結(jié)構(gòu)重在算法，據(jù)我們的認(rèn)識，數(shù)據(jù)結(jié)構(gòu)為數(shù)據(jù)的一種組織形式。每一種結(jié)構(gòu)就是一種容