《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》指導(dǎo)書

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)指導(dǎo)書沈陽理工大學(xué).信息學(xué)院2013.11.1

一．目的與意義軟件設(shè)計(jì)能力對(duì)計(jì)算機(jī)專業(yè)的學(xué)生是很重要。通過數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)，使學(xué)生對(duì)軟件編程能力有一定的提高。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)是鍛煉學(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ì)使學(xué)生對(duì)面向?qū)ο蟮脑O(shè)計(jì)過程有初的認(rèn)識(shí)，并對(duì)面向?qū)ο蟮母吣苷Z言的學(xué)習(xí)打下基礎(chǔ)，通過不同類型的程序設(shè)計(jì)使學(xué)生進(jìn)一步掌握數(shù)據(jù)的幾種不同的組織和存儲(chǔ)方式，為高級(jí)編程做準(zhǔn)備，為專業(yè)課的深入學(xué)習(xí)和畢業(yè)設(shè)計(jì)打基礎(chǔ)二．任務(wù)和要求分析每一組題目，按要求完成相應(yīng)的題目：題目參照附錄中《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》題目選題。2.要求：對(duì)相應(yīng)的題目進(jìn)行算法設(shè)計(jì)編寫源代碼上機(jī)調(diào)試顯示調(diào)試結(jié)果寫出實(shí)驗(yàn)總結(jié)3．課程設(shè)計(jì)說明書設(shè)計(jì)完成后，將自己選定的題目按上述要求完成課程設(shè)計(jì)說明書。課程設(shè)計(jì)說明書內(nèi)容包含：題目、要求、初步設(shè)計(jì)（可以是流程圖、功能模塊圖）、詳細(xì)設(shè)計(jì)、程序代碼、測試數(shù)據(jù)、運(yùn)行結(jié)果、遇到的問題及總結(jié)幾部分。三．進(jìn)度安排設(shè)計(jì)總學(xué)時(shí)為2周第一周：查閱資料、小組討論、進(jìn)行模塊劃分寫出分析報(bào)告，畫Ｎ－Ｓ結(jié)構(gòu)化框圖,編寫程序清單，上機(jī)調(diào)試.第二周周四、五:驗(yàn)收（計(jì)算機(jī)機(jī)房）,并將課程設(shè)計(jì)報(bào)告交上來.四.考核標(biāo)準(zhǔn)與成績?cè)u(píng)定方式成績?cè)u(píng)定有如下幾項(xiàng)參考：初步設(shè)計(jì)內(nèi)容的考核：是否有查閱資料能力？是否有設(shè)計(jì)思想？程序編碼能力調(diào)試能力的考核：程序是否清晰、易讀？在技算計(jì)上是否可獨(dú)立完成程序的調(diào)試，是否熟練？說明書質(zhì)量的考核：設(shè)計(jì)結(jié)構(gòu)是否合理？敘述是否正確？方案是否可行？答辯：設(shè)計(jì)結(jié)果的調(diào)試能力，對(duì)自己設(shè)計(jì)是否熟練？出勤率極平時(shí)表現(xiàn)的考核：出勤超過2次不到者成績?yōu)椴患案?。五．選題參考按學(xué)號(hào)對(duì)應(yīng)相應(yīng)題目號(hào)，例：學(xué)號(hào)1203050101----》選擇題目1。本次設(shè)計(jì)是為加強(qiáng)學(xué)生的軟件編程能力而進(jìn)行的專門訓(xùn)練。選題考慮到學(xué)生在數(shù)據(jù)結(jié)構(gòu)中學(xué)過的各種算法、數(shù)據(jù)組織方式進(jìn)行選題，考慮數(shù)據(jù)結(jié)構(gòu)算法所涉及的操作系統(tǒng)、網(wǎng)絡(luò)、編譯方法等中的實(shí)例，進(jìn)行設(shè)計(jì)。六.課程設(shè)計(jì)主要窗口展示部分

1.主窗口2.分層菜單附錄題目：根據(jù)字符使用權(quán)值不同，設(shè)計(jì)哈夫曼編碼，具體功能如下：①輸入N個(gè)權(quán)值。②先構(gòu)造哈夫曼樹，然后再求各結(jié)點(diǎn)的編碼。將編碼寫入文件③顯示指定字符的哈夫曼編碼④求指定兩個(gè)結(jié)點(diǎn)的公共編碼（先找到共同的祖先）。鍵盤輸入一個(gè)含有括號(hào)的四則運(yùn)算表達(dá)式，實(shí)現(xiàn)功能如下：①輸出后綴表達(dá)式—即逆波蘭；②將表達(dá)式的逆波蘭式寫入文件③對(duì)文件中的逆波蘭表達(dá)式讀出并求值。迷宮求解：在迷宮中求一條路徑的算法，基本思想：若當(dāng)前、位置可通過，則壓入棧中，否則探索下一位置，若走不通，則回溯，迷宮大?。篗*N。迷宮設(shè)置自定義。已知二叉樹的中序序列和后序序列，求出這棵二叉樹，并判別給定的二叉樹是否是完全二叉樹。輸入數(shù)據(jù)對(duì)數(shù)據(jù)按菜單選擇對(duì)數(shù)據(jù)進(jìn)行插入排序。要求①菜單列出所有插入排序②對(duì)數(shù)據(jù)按菜單選擇的進(jìn)行排序③統(tǒng)計(jì)比較和交換的次數(shù)，將結(jié)果寫入文件。2人完成輸入數(shù)據(jù)對(duì)數(shù)據(jù)按菜單選擇對(duì)數(shù)據(jù)進(jìn)行選擇排序。要求①菜單列出所有選擇排序②對(duì)數(shù)據(jù)按菜單選擇的進(jìn)行排序③統(tǒng)計(jì)比較和交換的次數(shù)，將結(jié)果寫入文件。輸入數(shù)據(jù)對(duì)數(shù)據(jù)按菜單選擇對(duì)數(shù)據(jù)進(jìn)行交換排序。要求①菜單列出所有交換排序②對(duì)數(shù)據(jù)按菜單選擇的進(jìn)行排序③統(tǒng)計(jì)比較和交換的次數(shù)，將結(jié)果寫入文件。對(duì)一個(gè)存儲(chǔ)為鄰接表的圖求：①其鄰接矩陣表示，將其儲(chǔ)存到文件中。②求其所有連通分量并顯示。③統(tǒng)計(jì)結(jié)點(diǎn)的度。內(nèi)存分配算法：利用靜態(tài)鏈表，模擬實(shí)現(xiàn)內(nèi)存分配（分區(qū)、分頁）請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的四則運(yùn)算。航空公司每天起落的航班有很多，設(shè)計(jì)程序?qū)崿F(xiàn)對(duì)航班信息的管理。具體功能包含：錄入功能、查詢功能、修改功能等。計(jì)算機(jī)外部輸出設(shè)備（如顯示器）和的CPU處理數(shù)據(jù)的速度不同。按先來先服務(wù)的方式進(jìn)行管理，設(shè)計(jì)緩沖隊(duì)列，實(shí)現(xiàn)外設(shè)與CPU的匹配。已知高校排課AOV網(wǎng)，給出一個(gè)排課序列（利用棧）二叉樹用二叉鏈存儲(chǔ)，鏈接時(shí)用葉子結(jié)點(diǎn)的rchild域存放指針。請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法完成①對(duì)一棵二叉樹加線索（中序）；②把二叉樹的葉子結(jié)點(diǎn)按從左到右的順序連成一個(gè)單鏈表。③統(tǒng)計(jì)二叉樹中0到2度結(jié)點(diǎn)了。處理器中有一就緒隊(duì)列，若干個(gè)進(jìn)程依到達(dá)的時(shí)刻依次進(jìn)入就緒隊(duì)列，每個(gè)進(jìn)程有進(jìn)程名和處理器處理此進(jìn)程的所需空間，仿靜態(tài)鏈表形式分配內(nèi)存所需空間，編程序?qū)崿F(xiàn)cpu調(diào)度算法。學(xué)籍管理：對(duì)學(xué)生、課程、成績分別建立三個(gè)數(shù)據(jù)文件（學(xué)生、課程、成績屬性自定）。完成下列各題：①對(duì)數(shù)據(jù)錄入②查詢（如：某個(gè)學(xué)生的選課情況、成績不及格的學(xué)生情況）③插入、刪除、修改④排序（如：對(duì)課程名按不及格學(xué)生人數(shù)進(jìn)行）等功能。工資管理：自己建立數(shù)據(jù)文件（提示可建立：職工、工資級(jí)別、職工工資）完成：①數(shù)據(jù)錄入②查詢（如：職工的平均工資查詢、某一級(jí)別人員的平均工資查詢）③插入、刪除、修改④排序（將職工姓名按工資額度進(jìn)行）等功能。房產(chǎn)信息管理按上述建立數(shù)據(jù)文件的方式對(duì)房產(chǎn)信息進(jìn)行如下管理：①數(shù)據(jù)錄入②查詢③插入、刪除、修改④排序等功能。供貨信息管理按上述建立數(shù)據(jù)文件的方式對(duì)供貨信息進(jìn)行如下管理：①數(shù)據(jù)錄入②查詢③插入、刪除、修改④排序等功能。圖書管理建立圖書數(shù)據(jù)文件進(jìn)行如下管理：①數(shù)據(jù)錄入②查詢③插入、刪除、修改④排序等功能。圖書借閱管理建立借閱數(shù)據(jù)文件進(jìn)行如下管理：①數(shù)據(jù)錄入②查詢③插入、刪除、修改④排序等功能。通訊錄：建立通訊錄數(shù)據(jù)文件。完成下列功能：①對(duì)數(shù)據(jù)錄入②查詢（如：某個(gè)電話號(hào)、某個(gè)名字等）③插入、刪除、修改④排序等。人事檔案管理：建立數(shù)據(jù)文件（職工、部門、職稱）完成：①數(shù)據(jù)錄入②查詢③插入、刪除、修改④排序等功能。俄羅斯方塊將堆排序的過程通過圖示顯示出來。要求：①輸入一組數(shù)據(jù)②在順序結(jié)構(gòu)上完成,先建堆然后重建堆,最后實(shí)現(xiàn)全部排序。③圖示上述過程。例如在菜單上：給出2則顯示第二趟堆排序過程。④將排序結(jié)果寫入文件。實(shí)現(xiàn)連通無向圖的深度與廣度遍歷?；鶖?shù)排序的演示過程。最小生成樹(普里母算法實(shí)現(xiàn))的求解演示過程關(guān)鍵路徑、拓?fù)渑判虻那蠼庋菔具^程萬年歷：通過給定的年，求該年的日歷，閏年判斷：{Y%4&&!Y%100}||Y%400＝＝0要求：①輸入年份②選擇列數(shù)③打印日歷并寫入文件。說明：列數(shù)表示打印格式12行一列、6行二列、四行三列。。。。。給定兩個(gè)串X和Y，①求子串在主串中的所有位置并記錄②找出X和Y的一個(gè)最長公共子串。③置換①所定位的所有子串。將地圖存儲(chǔ)20個(gè)城市，求任意兩個(gè)城市間的最短路徑。分子式是用來表達(dá)分子組成結(jié)構(gòu)的表達(dá)式，一般表達(dá)形式為A1c1A2c2A3c3...其中Ai(i=1,2,.......)表示原子或原子團(tuán)，ci(i=1,2,....)表示原子或原子團(tuán)Ai重復(fù)的次數(shù)。當(dāng)ci=1時(shí)，ci必須省略不寫，且原子團(tuán)的括號(hào)也不要。例如N的原子量為14，H的原子量為1，C的原子量為12，O的原子量為16，因此(NH4）2CO3的分子量為（14+1*4）*2+12+16*3=96。試編寫程序求出給定的各個(gè)分子式所對(duì)應(yīng)的分子量。設(shè)明文P=P0P1P2…Pn和密鑰K=K0K1K2…Km(n>=m)中的字符Pi(1<=i<=n)或Kj(1<=j<=m)的ASCII為00~7FH，用密鑰K對(duì)明文P進(jìn)行加密得到密文C=C0C1C2…Cn,用密鑰K對(duì)密文C解密得到明文P。加密：Ci=Pi+Kj(j=imod(m+1))(當(dāng)Ci<=7FH)Ci=Pi+Kj-80H(j=imod(m+1))(當(dāng)Ci>7FH)解密：：Pi=Ci-Kj(j=imod(m+1))(當(dāng)Ci>=Kj)Pi=Ci-Kj+80H(j=imod(m+1))(當(dāng)Ci<Kj)要求：①將明文加密后別存入文件中②將密文文件解密后存入另一文件中③將明文中的某字符u替換為v，同時(shí)將密文中的字符做相應(yīng)修改。矩陣A中的元素若滿足：A[i,j]是第i行中值最小的元素，且又是第j列中值最大的元素，則稱元素A[i,j]為該矩陣的一個(gè)馬鞍點(diǎn)。求出用一維數(shù)組壓縮存儲(chǔ)表示的稀疏矩陣m×n矩陣的所有馬鞍點(diǎn)。銀行業(yè)務(wù)模擬問題描述：客戶業(yè)務(wù)分為兩種。第一種是申請(qǐng)從銀行得到一筆資金，即取款或借款。第二種是向銀行投入一筆資金，即存款或還款。銀行有兩個(gè)服務(wù)窗口，相應(yīng)的有兩個(gè)隊(duì)列?？蛻舻竭_(dá)銀行后先排第一個(gè)隊(duì)。處理每個(gè)客戶業(yè)務(wù)時(shí)，如果屬于第一種，且申請(qǐng)額超出銀行現(xiàn)存資金總額而得不到滿足，則立即排入第二隊(duì)等候，直至滿足時(shí)才離開銀行，否則業(yè)務(wù)處理完后立即離開銀行。每接待完一個(gè)第二種業(yè)務(wù)的客戶，則順序檢查和處理（如果可能）第二個(gè)隊(duì)列的客戶，對(duì)能滿足的申請(qǐng)者予以滿足，不能滿足者重新排到第二個(gè)隊(duì)列的隊(duì)尾。注意，在此檢查過程中，一旦銀行資金總額少于或等于剛才第一個(gè)隊(duì)列中最后一個(gè)客戶（第二種業(yè)務(wù)）被接待之前的數(shù)額，或者本次已將第二個(gè)隊(duì)列檢查或處理了一遍，就停止檢查（因?yàn)榇藭r(shí)已不可能還有能滿足者）轉(zhuǎn)而繼續(xù)接待第一個(gè)隊(duì)列的客戶。任何時(shí)刻都只開一個(gè)窗口。假設(shè)檢查不需要時(shí)間。營業(yè)時(shí)間結(jié)束時(shí)所有客戶立即離開銀行。寫一個(gè)上述銀行業(yè)務(wù)的事件驅(qū)動(dòng)模擬系統(tǒng)，通過模擬方法求出客戶在銀行內(nèi)逗留的平均時(shí)間。五子棋在圍棋比賽中，某一方（假設(shè)為黑方）在棋盤的某個(gè)位置（i，j）下子后，有可能提取對(duì)方（白方的一串子）。以W[19][19]表示一個(gè)棋盤，若W[i][j]=0表示在位置(i,j)上沒有子，W[i][j]=1表示該位置上的是黑子，W[i][j]=-1表示該位置上是白子。模擬實(shí)現(xiàn)五子棋過程。運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)程序的設(shè)計(jì)（2人）運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)任務(wù)：參加運(yùn)動(dòng)會(huì)有n個(gè)學(xué)校，學(xué)校編號(hào)為1……n。比賽分成m個(gè)男子項(xiàng)目，和w個(gè)女子項(xiàng)目。項(xiàng)目編號(hào)為男子1……m，女子m+1……m+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é)?？偡?，3)．可以按學(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)；測試數(shù)據(jù)：要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進(jìn)行程序測試，以