《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》課程設(shè)計(jì)方案

算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)方案Course Design of Data Structure適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)專業(yè) 本科課程代碼：B08233004一、課程設(shè)計(jì)的性質(zhì)和目的軟件設(shè)計(jì)能力培養(yǎng)對(duì)學(xué)生是很重要。通過數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)，使學(xué)生對(duì)軟件編程能力有一定的提高。數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)是鍛煉學(xué)生在進(jìn)一步掌握模塊化、結(jié)構(gòu)化程序設(shè)計(jì)的方法的同時(shí)，培養(yǎng)學(xué)生運(yùn)用已學(xué)知識(shí)分析問題、解決問題及編寫實(shí)用程序的能力，通過對(duì)線性化、層次化、網(wǎng)絡(luò)化數(shù)據(jù)結(jié)構(gòu)的了解進(jìn)一步掌握自然數(shù)據(jù)的結(jié)構(gòu)方式及組織方式，讓學(xué)生深入體會(huì)存儲(chǔ)在計(jì)算機(jī)中的數(shù)據(jù)及程序，如何運(yùn)用數(shù)據(jù)實(shí)現(xiàn)編程。課程設(shè)計(jì)是數(shù)據(jù)結(jié)構(gòu)課程教學(xué)必不可缺的一個(gè)重要環(huán)節(jié)，它可加深學(xué)生對(duì)該課程所學(xué)內(nèi)容的進(jìn)一步的理解與鞏固，是將計(jì)算機(jī)課程與實(shí)際問題相聯(lián)接的關(guān)鍵步驟。通過課程設(shè)計(jì)，能夠提高學(xué)生分析問題、解決問題，從而運(yùn)用所學(xué)知識(shí)解決實(shí)際問題的能力，因而必須給予足夠的重視。主要目的如下：1、培養(yǎng)學(xué)生運(yùn)用算法與數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)解決實(shí)際編程中的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)和算法設(shè)計(jì)問題。2、培養(yǎng)學(xué)生獨(dú)立設(shè)計(jì)程序與解決問題的能力，培養(yǎng)學(xué)生團(tuán)隊(duì)協(xié)作集成程序模塊及調(diào)試能力。3、培養(yǎng)學(xué)生初步的軟件設(shè)計(jì)及軟件測(cè)試的能力。二、課程設(shè)計(jì)的基本要求學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課設(shè)的時(shí)間計(jì)劃，并在課設(shè)過程中不斷檢測(cè)自己的計(jì)劃完成情況。1、設(shè)計(jì)和調(diào)試過程要規(guī)范化。(1)需求分析將題目中要求的功能進(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ù)雜度。給出實(shí)現(xiàn)功能的一組或多組測(cè)試數(shù)據(jù)，程序調(diào)試后，將按照此測(cè)試數(shù)據(jù)進(jìn)行測(cè)試的結(jié)果列出來 。對(duì)有些題目提出算法改進(jìn)方案，比較不同算法的優(yōu)缺點(diǎn)。如果程序不能正常運(yùn)行，寫出實(shí)現(xiàn)此算法中遇到的問題，和改進(jìn)方法。(2)源程序（可以是一組源程序，即詳細(xì)設(shè)計(jì)部分）源程序要按照寫程序的規(guī)則來編寫。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部分要加上清晰的程序注釋。程序能夠運(yùn)行，要有基本的容錯(cuò)功能。盡量避免出現(xiàn)操作錯(cuò)誤時(shí)出現(xiàn)死循環(huán)。2、實(shí)施方式可設(shè)1-3人一題，安排在數(shù)據(jù)結(jié)構(gòu)課程開課學(xué)期布置題目，然后在期末一周時(shí)間內(nèi)完成。三、課程設(shè)計(jì)進(jìn)度安排課程設(shè)計(jì)大體分五個(gè)階段:1、選題與搜集資料：每人選擇相應(yīng)題目,進(jìn)行課程設(shè)計(jì)課題的資料搜集.2、分析與概要設(shè)計(jì)：根據(jù)搜集的資料,進(jìn)行程序功能與數(shù)據(jù)結(jié)構(gòu)分析,并選擇合適的數(shù)據(jù)結(jié)構(gòu),并在此基礎(chǔ)上進(jìn)行實(shí)現(xiàn)程序功能的算法設(shè)計(jì).3、程序設(shè)計(jì)用掌握C語言編寫程：運(yùn)序,實(shí)現(xiàn)所程序的各個(gè)模塊功能.4、調(diào)試與測(cè)試程序,成：自行調(diào)試員交叉測(cè)試程序,并記錄測(cè)試情況.5、實(shí)習(xí)報(bào)告：編寫實(shí)習(xí)報(bào)告6、驗(yàn)收與評(píng)分：指導(dǎo)教師對(duì)每個(gè)小組的開發(fā)的系統(tǒng),及每個(gè)成員開發(fā)的模塊進(jìn)行綜合答辯驗(yàn)收.結(jié)合設(shè)計(jì)報(bào)告,根據(jù)課程設(shè)計(jì)成績的評(píng)定方法,評(píng)出成績.四、課程設(shè)計(jì)報(bào)告的書寫設(shè)計(jì)結(jié)束后要寫出課程設(shè)計(jì)報(bào)告,字?jǐn)?shù)不少于6000，以作為整個(gè)課程設(shè)計(jì)評(píng)分的書面依據(jù)和存檔材料.設(shè)計(jì)報(bào)告以規(guī)定格式的電子文檔書寫（具體格式要求詳見附錄1和附錄2）,打印并裝訂,排版及圖,表要清楚,工整。裝訂順序如下：封面、任務(wù)書、目錄、正文。報(bào)告中除了在封面中應(yīng)有題目、班級(jí)、姓名、學(xué)號(hào)和課程設(shè)計(jì)日期以外，其正文一般有如下幾個(gè)方面的內(nèi)容：正文包括以下7個(gè)內(nèi)容:1、問題分析和任務(wù)定義：根據(jù)設(shè)計(jì)題目的要求，充分地分析和理解問題，明確問題要求做什么？（而不是怎么做？）限制條件是什么？ 2、邏輯設(shè)計(jì)：對(duì)問題描述中涉及的操作對(duì)象定義相應(yīng)的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。邏輯設(shè)計(jì)的結(jié)果應(yīng)寫出每個(gè)抽象數(shù)據(jù)類型的定義(包括數(shù)據(jù)結(jié)構(gòu)的描述和每個(gè)基本操作的功能說明)，各個(gè)主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖；3、詳細(xì)設(shè)計(jì)：定義相應(yīng)的存儲(chǔ)結(jié)構(gòu)并寫出各函數(shù)的偽碼算法。在這個(gè)過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡(jiǎn)單和易于調(diào)試，抽象數(shù)據(jù)類型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體。詳細(xì)設(shè)計(jì)的結(jié)果是對(duì)數(shù)據(jù)結(jié)構(gòu)和基本操作作出進(jìn)一步的求精，寫出數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的類型定義，寫出函數(shù)形式的算法框架；4、程序編碼：把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語言程序。同時(shí)加入一些注解和斷言，使程序中邏輯概念清楚；5、程序調(diào)試與測(cè)試：采用自底向上，分模塊進(jìn)行，即先調(diào)試低層函數(shù)。能夠熟練掌握調(diào)試工具的各種功能，設(shè)計(jì)測(cè)試數(shù)據(jù)確定疑點(diǎn)，通過修改程序來證實(shí)它或繞過它。調(diào)試正確后，認(rèn)真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果；6、結(jié)果分析：程序運(yùn)行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果。算法的時(shí)間、空間復(fù)雜性分析；7、附錄或參考資料：附錄源程序及參考文獻(xiàn)。五、課程設(shè)計(jì)的內(nèi)容及安排根據(jù)教材數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)（滕國文編著）選擇課程設(shè)計(jì)題目，或選擇下列與實(shí)際應(yīng)用緊密結(jié)合的較綜合性的題目，要求通過設(shè)計(jì)，在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇應(yīng)用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面加深對(duì)課程基本內(nèi)容的理解和綜合運(yùn)用。1、運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)*問題描述：參加運(yùn)動(dòng)會(huì)有n個(gè)學(xué)校，學(xué)校編號(hào)為1n。比賽分成m個(gè)男子項(xiàng)目，和w個(gè)女子項(xiàng)目。項(xiàng)目編號(hào)為男子1m，女子m+1m+w。不同的項(xiàng)目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學(xué)生自己設(shè)定。（m<=20,n<=20）*功能要求：1).可以輸入各個(gè)項(xiàng)目的前三名或前五名的成績；2).能統(tǒng)計(jì)各學(xué)?？偡郑?).可以按學(xué)校編號(hào)、學(xué)校總分、男女團(tuán)體總分排序輸出；4).可以按學(xué)校編號(hào)查詢學(xué)校某個(gè)項(xiàng)目的情況；可以按項(xiàng)目編號(hào)查詢?nèi)〉们叭蚯拔迕膶W(xué)校。規(guī)定：輸入數(shù)據(jù)形式和范圍：20以內(nèi)的整數(shù)（如果做得更好可以輸入學(xué)校的名稱，運(yùn)動(dòng)項(xiàng)目的名稱）輸出形式：有中文提示，各學(xué)校分?jǐn)?shù)為整形界面要求：有合理的提示，每個(gè)功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。*存儲(chǔ)結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計(jì)，但是要求運(yùn)動(dòng)會(huì)的相關(guān)數(shù)據(jù)要存儲(chǔ)在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關(guān)內(nèi)容在c語言程序設(shè)計(jì)的書上，請(qǐng)自學(xué)解決）請(qǐng)?jiān)谧詈蟮纳辖毁Y料中指明你用到的存儲(chǔ)結(jié)構(gòu)；測(cè)試數(shù)據(jù)：要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進(jìn)行程序測(cè)試，以保證程序的穩(wěn)定。測(cè)試數(shù)據(jù)及測(cè)試結(jié)果請(qǐng)?jiān)谏辖坏馁Y料中寫明；2、一元多項(xiàng)式計(jì)算*問題描述：能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式；能夠完成兩個(gè)多項(xiàng)式的相加、相減，并將結(jié)果輸入；在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、多項(xiàng)式相加的基本過程的算法（可以使用程序流程圖） 、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；3、訂票系統(tǒng)*問題描述：通過此系統(tǒng)可以實(shí)現(xiàn)如下功能：1）錄入：可以錄入航班情況（數(shù)據(jù)可以存儲(chǔ)在一個(gè)數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）2）查詢：可以查詢某個(gè)航線的情況（如，輸入航班號(hào)，查詢起降時(shí)間，起飛抵達(dá)城市，航班票價(jià)，票價(jià)折扣，確定航班是否滿倉）；可以輸入起飛抵達(dá)城市，查詢飛機(jī)航班情況；3）訂票：（訂票情況可以存在一個(gè)數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定）可以訂票，如果該航班已經(jīng)無票，可以提供相關(guān)可選擇航班；4）退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶資料有姓名，證件號(hào)，訂票數(shù)量及航班情況，訂單要有編號(hào)。5）修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件*要求：根據(jù)以上功能說明，設(shè)計(jì)航班信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)程序完成功能；4、迷宮求解*問題描述：可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；*要求：在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；5、文章編輯*問題描述：輸入一頁文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。靜態(tài)存儲(chǔ)一頁文章，每行最多不超過80個(gè)字符，共N行。*要求（1）分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。*存儲(chǔ)結(jié)構(gòu)使用線性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；*輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號(hào)。*輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出"全部字母數(shù)"、"數(shù)字個(gè)數(shù)"、"空格個(gè)數(shù)"、"文章總字?jǐn)?shù)"（3）輸出刪除某一字符串后的文章；6、joseph環(huán) *問題描述：編號(hào)是1，2，,n的n個(gè)人按照順時(shí)針方向圍坐一圈，每個(gè)人只有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)仍開始順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直到所有人全部出列為止。設(shè)計(jì)一個(gè)程序來求出出列順序。*要求：利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個(gè)人的編號(hào)。*測(cè)試數(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)鏈表。*輸出形式：建立一個(gè)輸出函數(shù)，將正確的輸出序列7、猴子選大王*問題描述：一堆猴子都有編號(hào)，編號(hào)是1，2，3 .m ,這群猴子（m個(gè)）按照1-m的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第N個(gè)，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。*輸入數(shù)據(jù)：輸入m,n m,n 為整數(shù)，n<m*輸出形式：中文提示按照m個(gè)猴子，數(shù)n 個(gè)數(shù)的方法，輸出為大王的猴子是幾號(hào) ，建立一個(gè)函數(shù)來實(shí)現(xiàn)此功能 8、建立二叉樹，層序、先序遍歷（ 用遞歸或非遞歸的方法都可以）*問題描述：要求能夠輸入樹的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹存儲(chǔ)結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)； 9、赫夫曼樹的建立*問題描述：建立建立最優(yōu)二叉樹函數(shù)*要求：可以建立函數(shù)輸入二叉樹，并輸出其赫夫曼樹在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、 基本算法（可以使用程序流程圖） 、輸入輸出、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；10、紙牌游戲*問題描述：編號(hào)為1-52張牌，正面向上，從第2張開始，以2為基數(shù)，是2的倍數(shù)的牌翻一次，直到最后一張牌；然后，從第3張開始，以3為基數(shù)，是3的倍數(shù)的牌翻一次，直到最后一張牌；然后從第4張開始，以4為基數(shù)，是4的倍數(shù)的牌翻一次， 直到最后一張牌；.再依次5的倍數(shù)的牌翻一次，6的，7的 直到 以52為基數(shù)的 翻過。輸出：這時(shí)正面向上的牌有哪些？ 11、圖的建立及輸出*問題描述：建立圖的存儲(chǔ)結(jié)構(gòu)（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學(xué)生可以任選兩種類型），能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。 12、拓?fù)渑判?問題描述：編寫函數(shù)實(shí)現(xiàn)圖的拓?fù)渑判颉?3、各種排序*問題描述：對(duì)30000個(gè)隨機(jī)整數(shù)，利用插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序等排序方法進(jìn)行排序，并統(tǒng)計(jì)每一種排序上機(jī)所花費(fèi)的時(shí)間。*輸入的數(shù)據(jù)形式為任何一個(gè)正整數(shù)，大小不限。*輸出的形式：數(shù)字大小逐個(gè)遞增的數(shù)列?14、圖的遍歷*問題描述：對(duì)任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊(duì)列的五種基本運(yùn)算（置空隊(duì)列、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空）實(shí)現(xiàn)圖的廣度優(yōu)先搜索周游。15、線性表的操作*問題描述：利作鏈表的插入運(yùn)算建立線性鏈表，然后利用鏈表的查找、刪除、計(jì)數(shù)、輸出等運(yùn)算反復(fù)實(shí)現(xiàn)鏈表的這些操作（插入、刪除、查找、計(jì)數(shù)、輸出單獨(dú)寫成函數(shù)的形式），并能在屏幕上輸出操作前后的結(jié)果。16、長整數(shù)四則運(yùn)算*問題描述：設(shè)計(jì)一個(gè)實(shí)現(xiàn)任意長的整數(shù)進(jìn)行加法運(yùn)算的演示程序。*基本要求：利用雙向循環(huán)鏈表實(shí)現(xiàn)長整數(shù)的存儲(chǔ)，每個(gè)結(jié)點(diǎn)含一個(gè)整形變量。任何整形變量的范圍是 -(215 - 1) (215 - 1)。輸入和輸出形式：按中國對(duì)于長整數(shù)的表示習(xí)慣，每四位一組，組間用逗號(hào)隔開。 *測(cè)試數(shù)據(jù)：（1）0；0；應(yīng)輸出“0”。（2）-2345,6789；-7654,3211；應(yīng)輸出“-1,0000,0000”。（3）-9999,9999；1,0000,0000,0000；應(yīng)輸出“999（4）1,0001,0001；-1,0001,0001；應(yīng)輸出“0”。（5）1,0001,0001；-1,0001,0000；應(yīng)輸出“1”。（6）-9999,9999,9999；-9999,9999,9999；應(yīng)輸出“1,9999,9999,9998”。（7）1,0000,9999,9999；1；應(yīng)輸出“1,0001,0000,0000”。*實(shí)現(xiàn)提示：（1）每個(gè)結(jié)點(diǎn)中可以存放的最大整數(shù)為32767，才能保證兩數(shù)相加不會(huì)溢出，但若這樣存放，即相當(dāng)于按32768進(jìn)制存放，在十進(jìn)制與32768進(jìn)制數(shù)之間的轉(zhuǎn)換十分不方便，故可以在每個(gè)結(jié)點(diǎn)中僅存十進(jìn)制的4位，即不超過9999的非負(fù)整數(shù)，整個(gè)鏈表表示為萬進(jìn)制。（2）可以利用頭結(jié)點(diǎn)數(shù)據(jù)域的符號(hào)代表長整數(shù)的符號(hào)。用其絕對(duì)值表示元素結(jié)點(diǎn)數(shù)目。相加過程中不要破壞兩個(gè)操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡(jiǎn)化程序結(jié)構(gòu)的一種方法。不能給長整數(shù)位數(shù)規(guī)定上限。17、馬踏棋盤*問題描述：將馬隨機(jī)放在國際象棋的8* 8棋盤Bord88的某個(gè)方格中，馬按走棋規(guī)則進(jìn)行移動(dòng)。要求每個(gè)方格上只進(jìn)入一次，走遍棋盤上全部64個(gè)方格。編制非遞歸程序，求出馬的行走路線 ，并按求出的行走路線，將數(shù)字1，2，64依次填入個(gè)8* 8的方陣，輸出之。*測(cè)試數(shù)據(jù)：由讀者指定,可自行指定一個(gè)馬的初始位置。*實(shí)現(xiàn)提示：每次在多個(gè)可走位置中選擇一個(gè)進(jìn)行試探，其余未曾試探過的可走位置必須用適當(dāng)結(jié)構(gòu)妥善管理，以備試探失敗時(shí)的“回溯”(悔棋)使用。18、校園導(dǎo)游咨詢*問題描述： （1）設(shè)計(jì)你的學(xué)校的校園平面圖，所含景點(diǎn)不少于10個(gè)。以圖中頂點(diǎn)表示學(xué)校各景點(diǎn)，存放景點(diǎn)名稱、代號(hào)、簡(jiǎn)介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。（2）為來訪客人提供圖中任意景點(diǎn)的問路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短的簡(jiǎn)單路徑。 （3）為來訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。*測(cè)試數(shù)據(jù)：由讀者根據(jù)實(shí)際情況指定。*實(shí)現(xiàn)提示：一般情況下，校園的道路是雙向通行的，可設(shè)校園平面圖是一個(gè)無向網(wǎng)。頂點(diǎn)和邊均含有相關(guān)信息。19、編制一個(gè)求解迷宮通路的圖形界面演示程序*問題描述：1） 輸入一個(gè)任意大小的迷宮，任設(shè)起點(diǎn)、終點(diǎn)、障礙，用棧求出一條走出迷宮的路徑，并顯示在屏幕上。2） 根據(jù)用戶界面提示，用鍵盤輸入。Home鍵設(shè)置迷宮起點(diǎn)，End鍵設(shè)終點(diǎn)，上下左右箭頭鍵移動(dòng)，Enter鍵添加墻，Del鍵刪除墻，完成后按F9鍵演示，Esc鍵退出。3）橙色的實(shí)心小圓圈表示起點(diǎn)，綠色實(shí)心圓圈表示終點(diǎn)，空心圓圈表示足跡，紅色方塊表示墻。4）本程序只求出一條成功的通路，但若對(duì)求解函數(shù)MazePath稍加更改即可求得全部路徑。此外，因受圖形界面限制，不能保存或載入測(cè)試文件（此功能可在Maze_text中實(shí)現(xiàn)）。5）當(dāng)未輸入起點(diǎn)時(shí)，消息顯示“Error： You must set Startplace.”；未輸入終點(diǎn)時(shí)，顯示“Error： You must set Endplace.” 找到路徑時(shí)，屏幕顯示足跡，并在消息框出現(xiàn)Path found，否則消去足跡，顯示Path not found.20一元稀疏多項(xiàng)式計(jì)算器*問題描述：一元多項(xiàng)式簡(jiǎn)單計(jì)算器的基本功能是：（1）輸入并建立多項(xiàng)式；（2）輸出多項(xiàng)式，輸出形式為整數(shù)序列n,c1,e1,c2,e2,cn,en，其中n是多項(xiàng)式的項(xiàng)數(shù)，ci和ei分別是第I項(xiàng)的系數(shù)和指數(shù)，序列指指數(shù)降序排列；（3）多項(xiàng)式a和b相加，建立多項(xiàng)式a+b；（4）多項(xiàng)式a和b相減，建立多項(xiàng)式a-b。*實(shí)現(xiàn)提示：用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式，多項(xiàng)式的項(xiàng)數(shù)存在頭結(jié)點(diǎn)。21算術(shù)表達(dá)式求值演示*問題描述：表達(dá)式求值是實(shí)現(xiàn)程序設(shè)計(jì)語言的基本問題之一，也是棧的應(yīng)用的一個(gè)典型例子。設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的過程。*基本要求：以字符序列的形式從終端上輸入語法正確的、不含變量的整數(shù)表達(dá)式。利用教材中給出的算符優(yōu)先關(guān)系，實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值，并仿照教材例3-1演示在求值中運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的變化過程。*實(shí)現(xiàn)提示：（1）設(shè)置運(yùn)算棧和運(yùn)算數(shù)棧輔助分析算符優(yōu)先關(guān)系。（2）在輸入表達(dá)式的字符序列的同時(shí)，完成運(yùn)算符和運(yùn)算數(shù)（整數(shù)）的識(shí)別處理，以及相應(yīng)的運(yùn)算。（3）在識(shí)別出運(yùn)算數(shù)的同時(shí)，要將其字符序列形式轉(zhuǎn)換成整數(shù)形式。*選作內(nèi)容：（1）擴(kuò)充運(yùn)算符集，如增加乘方、單目減、賦值等運(yùn)算；（2）運(yùn)算量可以是變量；（3）運(yùn)算量可以是實(shí)數(shù)類型；（4）計(jì)數(shù)器的功能和仿鎮(zhèn)界面。22稀疏矩陣運(yùn)算器*問題描述：稀疏矩陣是指那些多數(shù)元素為0的矩陣。利用“稀疏”特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大節(jié)省存儲(chǔ)空間，提高計(jì)算效率。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本原酸的運(yùn)算器。*基本要求：以“帶行邏輯鏈接信息”的三元組順序表示稀疏矩陣，實(shí)現(xiàn)兩個(gè)矩陣相加、相減和相乘的運(yùn)算。稀疏矩陣的輸入形式采用三元組表示，而運(yùn)算結(jié)構(gòu)的矩陣則以通常的陣列形式列出。*實(shí)現(xiàn)提示：（1）首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個(gè)矩陣的行、列數(shù)對(duì)于所要求作的運(yùn)算是否匹配?？稍O(shè)矩陣的行數(shù)和列數(shù)均不超過20。（2）程序可以對(duì)三元組的輸入順序加以限制，例如，按行優(yōu)先。注意研究教科書中的算法，以便提高計(jì)算效率。（3）在用三元組表示稀疏矩陣時(shí)，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積矩陣也可以用二維數(shù)組存放。23圖書管理系統(tǒng)*問題描述：圖書管理基本業(yè)務(wù)活動(dòng)包括：對(duì)一本書的采編入庫、清除庫存、借閱和歸還等等。試設(shè)計(jì)一個(gè)圖書管理系統(tǒng)，將上述業(yè)務(wù)活動(dòng)借助于計(jì)算機(jī)系統(tǒng)完成。*基本要求：（1）每種書的登記內(nèi)容至少包括書號(hào)、書名、作者、現(xiàn)存量和總庫存量等五4。（2）作為演示系統(tǒng)，不必使用文件，全部數(shù)據(jù)可以都在內(nèi)存存放。但是由于上述四項(xiàng)基本業(yè)務(wù)活動(dòng)都是通過書號(hào)（即關(guān)鍵字）進(jìn)行的，所以要用B樹對(duì)書號(hào)盡力索引，以獲得高效率。（3）系統(tǒng)應(yīng)實(shí)現(xiàn)的操作及功能定義如下：采編入庫：新購入一種書，經(jīng)分類和確定書號(hào)后登記到圖書帳目中去。如果這種書在帳目中已有，則只將總庫存量增加。清除庫存：某種書已無保留價(jià)值，將它從圖書帳目中注銷。某種書的現(xiàn)存量大于零，則借出一本，登記借閱者的圖書證號(hào)和歸還期限。歸還：注銷對(duì)借閱者的登記，改變?cè)摃默F(xiàn)存量。顯示：以凹入表的形式顯示B樹。這個(gè)操作是為了調(diào)試和維護(hù)的目的而設(shè)置的。下列B樹的打印格式如下所示：六、本課程與其它課程的聯(lián)系與分工本課程是數(shù)據(jù)結(jié)構(gòu)的配套課程，學(xué)完數(shù)據(jù)結(jié)構(gòu)后進(jìn)行的綜合性課程設(shè)計(jì)。七、課程設(shè)計(jì)考核方法及成績?cè)u(píng)定由指導(dǎo)教師根據(jù)學(xué)生完成任務(wù)的情況、課程設(shè)計(jì)說明書的質(zhì)量和課程設(shè)計(jì)過程中的工作態(tài)度等綜合打分。課程設(shè)計(jì)結(jié)束時(shí)，要求學(xué)生寫出課程設(shè)計(jì)報(bào)告，可運(yùn)行的軟件系統(tǒng)（包括源程序）。課程設(shè)計(jì)成績：上機(jī)情況（20%）包括出勤情況、調(diào)試表現(xiàn)。設(shè)計(jì)報(bào)告占40，設(shè)計(jì)作品占40。成績?cè)u(píng)定實(shí)行優(yōu)、良、中、及格和不及格五個(gè)等級(jí)。1、評(píng)定為優(yōu)的是：出勤率良好、設(shè)計(jì)報(bào)告優(yōu)秀、軟件演示優(yōu)秀、答辯三個(gè)問題全部正確。2、評(píng)定為良的是：出勤率良好、設(shè)計(jì)報(bào)告良好、軟件演示良好、答辯三個(gè)問題全部良好。3、評(píng)定為中的是：出勤率合格、設(shè)計(jì)報(bào)告中等、軟件演示中等、答辯三個(gè)問題基本正確。4、評(píng)定為及格的是：出勤率合格、設(shè)計(jì)報(bào)告及格、軟件演示及格、答辯三個(gè)問題基本及格。5、評(píng)定為合格的是：出勤率不合格、或設(shè)計(jì)報(bào)告不及格、或軟件演示不及格、或答辯三個(gè)問題不及格。優(yōu)秀者人數(shù)一般不得超過總?cè)藬?shù)的30%。不及格者不能得到相應(yīng)的學(xué)分，需重新做課程設(shè)計(jì)，經(jīng)指導(dǎo)教師考核及格后，方可取得相應(yīng)學(xué)分。有關(guān)的考查相關(guān)材料統(tǒng)一交系部資料室妥善保管。八、建議教材與教學(xué)參考書1數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)滕國文 編著，清華大學(xué)出版社2數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏 吳偉民 編著，清華大學(xué)出版社3數(shù)據(jù)結(jié)構(gòu)題集嚴(yán)蔚敏 吳偉民 米寧 編著，清華大學(xué)出版社4c語言程序設(shè)計(jì)譚浩強(qiáng) 編著，清華大學(xué)出版社5數(shù)據(jù)結(jié)構(gòu)（C語言篇）習(xí)題與解析李春葆 編著，清華大學(xué)出版社 10附錄1：鄭州科技學(xué)院算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書專業(yè) 班級(jí) 學(xué)號(hào) 姓名 一、設(shè)計(jì)題目：二、基本要求三、設(shè)計(jì)任務(wù)四、設(shè)計(jì)時(shí)間 2010 年 月 日 至 2011 年 月 日指導(dǎo)教師： 教研室主任： 附錄2：宋體二號(hào)加黑華文新魏小初號(hào)，簡(jiǎn)體鄭州科技學(xué)院算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 3號(hào)黑體，論文題目不得超過25個(gè)漢字題 目 _ _所填內(nèi)容為黑體3號(hào)學(xué)生姓名 專業(yè)班級(jí) 學(xué) 號(hào) 所 在 系 指導(dǎo)教師 固定內(nèi)容為宋體3號(hào)完成時(shí)間 年 月 日 目錄目錄3號(hào)黑體4號(hào)黑體1 1 1.11 1.1.12小4號(hào)宋體，目錄只到三級(jí)編號(hào)，正文可以到四級(jí)編號(hào)4號(hào)宋體結(jié)束語60致謝61參考文獻(xiàn)62（附錄）63注：表示一個(gè)空格（兩個(gè)字符位置） 括號(hào)內(nèi)的內(nèi)容表示視論文而定的內(nèi)I課程設(shè)計(jì)論文題目（將自己的課程設(shè)計(jì)論文題目作為頁眉）小5號(hào)宋體居中格3號(hào)黑體左頂格1一級(jí)節(jié)標(biāo)題為1.1，1.2，1.3，小3號(hào)黑體1.1二級(jí)節(jié)標(biāo)題為1.1.1，1.1.2，1.1.3，4號(hào)黑體1.1.1三級(jí)節(jié)標(biāo)題為1.1.1.1，1.1.1.2，1.1.1.3，小4號(hào)黑體1.1.1.1注：如果下面還有編號(hào)，可依次用(1)，(2)，(3) 和，。正文中具體對(duì)某個(gè)問題進(jìn)行說明，但并不屬于全文的整體編號(hào)時(shí)，使用第一，第二，第三進(jìn)行分點(diǎn)說明。文中參考文獻(xiàn)的標(biāo)注，企業(yè)集團(tuán)的轉(zhuǎn)移定價(jià)決策問題不僅為企業(yè)管理層所高度重視，同時(shí)也是學(xué)術(shù)界討論的熱門話題。Hirshleifer(1956) 1最先提出在確定性環(huán)境下當(dāng)中間產(chǎn)品轉(zhuǎn)移價(jià)格等于邊際成本時(shí)，公司利潤達(dá)到最大。Baldenius（1999）2在考慮特定關(guān)系投資的前提下，提出了兩部轉(zhuǎn)移定價(jià)法。正文部分：文字小4號(hào)，中文宋體；英文和數(shù)字Times New Roman圖中英文文字為5號(hào)正體Times New Roman賣出看跌賣出看漲Long putl optionLong calll option 圖2-5期權(quán)的基本交付模式圖中中文文字為5號(hào)楷體圖號(hào)按大標(biāo)題加編，如圖2-5表示第2章中的第5個(gè)圖。圖題在圖下，小4號(hào)宋體正文開始標(biāo)注頁碼，位置居中zhong 1公式：公式另起一行居中打印同行靠右注明公式序號(hào)，編號(hào)方法與圖相同 (2-7)（如果有的話）表題在表上，小4號(hào)宋體，與圖的編號(hào)方法相同表內(nèi)文字5號(hào)，分別用宋體和Times New Roman表6-1中外基金的規(guī)模比較（1997年值，單位：億美元）品種數(shù)基金總資產(chǎn)基金資產(chǎn)占流通市值的比率中國7516.910.38美國160004000049.5香港13008505 數(shù)據(jù)來源：1996年中國經(jīng)濟(jì)年鑒，1997年中國統(tǒng)計(jì)年鑒數(shù)據(jù)必須注明來源。表注小5號(hào)宋體和Times New Roman（正文部分字?jǐn)?shù)不少于6000字）25致謝致謝3號(hào)黑體空1行。小4號(hào)宋體參考文獻(xiàn)參考文獻(xiàn)小3號(hào)黑體空1行1 Hirshleifer J. On the Economics of Transfer PricingJ. Journal of Business, 1956, 29(3): 172 - 184.2 Baldenius T, Reichelstein S, Sahay S A. Negotiated Versus Cost-Based Transfer PricingJ.Review of Accounting Studies,1999,4: 67-915號(hào)宋體和Times New Roman3 夏普WF, 亞歷山大GJ，貝利JV. 趙錫軍，龍永紅，季冬生，等譯. 投資學(xué).北京：中國人民大學(xué)出版社，1996，124 約瑟夫 AA. 王微等譯. 期權(quán)市場(chǎng)運(yùn)作. 北京：清華大學(xué)出版社，1998，45 陳共，周生業(yè)，吳曉求. 證券投資分析. 北京：中國人民大學(xué)出版社，1998，86 林文俏. 股市風(fēng)險(xiǎn)透視與防范. 廣州：廣東經(jīng)濟(jì)出版社，1997，8網(wǎng)址標(biāo)注到引用文章處7 門明. 論期權(quán)與風(fēng)險(xiǎn)投資管理. 對(duì)外經(jīng)濟(jì)貿(mào)易大學(xué)學(xué)報(bào)，1999，2：10158 秦海波. “太陽”為何與微軟打“世界官司”. 經(jīng)濟(jì)日?qǐng)?bào)，1999年5月27日9 唐曉強(qiáng). 中國通信產(chǎn)業(yè)研究 注：（1）按論文中參考文獻(xiàn)出現(xiàn)的先后順序用阿拉伯?dāng)?shù)字連續(xù)編號(hào)，并與文中的編號(hào)順序相對(duì)應(yīng)。 小3號(hào)黑體（2）參考文獻(xiàn)中每條項(xiàng)目應(yīng)齊全。文獻(xiàn)中的作者不超過三位時(shí)全部列出；超過三位時(shí)只列出前三位，后而加“等”字；作者姓名之間用逗號(hào)分開；中外人名一體采用姓在前，名在后的著錄法。附錄附錄注：論文的附錄依次為附錄1，附錄2，編號(hào)。附錄中的圖表公式另編排序號(hào)，與正文分開。