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

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

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

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