《數(shù)據(jù)結構課程設計》指導書

《數(shù)據(jù)結構》課程設計指導書沈陽理工大學.信息學院2013.11.1

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

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