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

無

設(shè)計(jì)主題

:

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

:

瞿有甜

組長(zhǎng)(學(xué)號(hào)):

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