數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)教學(xué)大綱(完整版)

　　

【正文】 用鏈表的查找、刪除、計(jì)數(shù)、輸出等運(yùn)算反復(fù)實(shí)現(xiàn)鏈表的這些操作（插入、刪除、查找、計(jì)數(shù)、輸出單獨(dú)寫成函數(shù)的形式），并能在屏幕上輸出操作前后的結(jié)果。*測(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)鏈表。靜態(tài)存儲(chǔ)一頁文章，每行最多不超過80個(gè)字符，共N行。不同的項(xiàng)目取前五名或前三名積分；取前五名的積分分別為：1，前三名的積分分別為：2；哪些取前五名或前三名由學(xué)生自己設(shè)定。盡量避免出現(xiàn)操作錯(cuò)誤時(shí)出現(xiàn)死循環(huán)。二、設(shè)計(jì)要點(diǎn)1．設(shè)計(jì)和調(diào)試過程要規(guī)范化。1哈希表查找問題描述：定義一個(gè)哈希表和對(duì)哈希表進(jìn)行插入、查找和刪除、打印。分塊查找問題描述：采用分塊查找的方法查找指定的關(guān)鍵碼。克魯斯卡爾算法求最小生成樹問題描述：用克魯斯卡爾算法求有向網(wǎng)圖或無向網(wǎng)圖的最小生成樹。要求：1）采用函數(shù)形式完成轉(zhuǎn)置、相加、相減和相乘； 2）有輸入數(shù)據(jù)合法性檢查； 3）矩陣的存儲(chǔ)采用動(dòng)態(tài)數(shù)組；4）兩個(gè)矩陣產(chǎn)生后要分別打印出來，完成相應(yīng)處理后結(jié)果要打印出來； 5）每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖。第一篇：《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)教學(xué)大綱《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)教學(xué)大綱適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 課程周數(shù)：2周一、大綱說明本大綱根據(jù)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)人才培養(yǎng)方案制訂。線索二叉樹問題描述：實(shí)現(xiàn)線索二叉樹的生成、遍歷、查找、插入和刪除操作。要求：1）先生成一個(gè)網(wǎng)圖，該網(wǎng)圖既能是無向網(wǎng)圖，有能是有向網(wǎng)圖； 2）要求分別采用鄰接矩陣和鏈接表存儲(chǔ)來完成； 3）最后打印輸出最小生成樹；4）每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖。要求：1）可以循環(huán)查找，可以選擇退出；2）分別采用順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)完成分塊查找，其中在順序存儲(chǔ)結(jié)果下，索引表的查找采用二分查找；3）分別用函數(shù)完成索引表查找和塊中查找；4）每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖。要求：1）定義一個(gè)哈希表，并打印輸出結(jié)果； 2）分別編寫函數(shù)完成查找、插入和刪除； 3）測(cè)試查找、插入和刪除，分別打印測(cè)試結(jié)果；4）每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖。① 需求分析將題目中要求的功能進(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ù)雜度。2．課程設(shè)計(jì)實(shí)習(xí)報(bào)告的書寫格式① 設(shè)計(jì)題目（任選其一）②運(yùn)行環(huán)境（軟、硬件環(huán)境）③算法設(shè)計(jì)的思想 ④算法的流程圖 ⑤算法設(shè)計(jì)分析 ⑥源代碼 ⑦運(yùn)行結(jié)果分析 ⑧收獲及體會(huì) 3．實(shí)施方式可設(shè)34人一題，安排在《數(shù)據(jù)結(jié)構(gòu)》課程開課學(xué)期布置題目，然后在期末兩周時(shí)間內(nèi)完成。（m1).可以輸入各個(gè)項(xiàng)目的前三名或前五名的成績(jī)； 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é)校。*要求（1）分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。*輸出形式：建立一個(gè)輸出函數(shù)，將正確的輸出序列猴子選大王*問題描述：一堆猴子都有編號(hào)，編號(hào)是1，2，3...m ,這群猴子（m個(gè)）按照1m的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第N個(gè)，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。1長(zhǎng)整數(shù)四則運(yùn)算*問題描述：設(shè)計(jì)一個(gè)實(shí)現(xiàn)任意長(zhǎng)的整數(shù)進(jìn)行加法運(yùn)算的演示程序。（6）9999,9999,9999；9999,9999,9999；應(yīng)輸出“1,9999,9999,9998”。1馬踏棋盤*問題描述：將馬隨機(jī)放在國際象棋的8 8棋盤Bord[8Ⅱ8]的某個(gè)方格中，馬按走棋規(guī)則進(jìn)行移動(dòng)。（3）為來訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。3）橙色的實(shí)心小圓圈表示起點(diǎn)，綠色實(shí)心圓圈表示終點(diǎn)，空心圓圈表示足跡，紅色方塊表示墻。利用教材中給出的算符優(yōu)先關(guān)系，實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值，并仿照教材例31演示在求值中運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的變化過程。*基本要求：以“帶行邏輯鏈接信息”的三元組順序表示稀疏矩陣，實(shí)現(xiàn)兩個(gè)矩陣相加、相減和相乘的運(yùn)算。試設(shè)計(jì)一個(gè)圖書管理系統(tǒng)，將上述業(yè)務(wù)活動(dòng)借助于計(jì)算機(jī)系統(tǒng)完成。④歸還：注銷對(duì)借閱者的登記，改變?cè)摃默F(xiàn)存量。給出實(shí)現(xiàn)功能的一組或多組測(cè)試數(shù)據(jù)，程序調(diào)試后，將按照此測(cè)試數(shù)據(jù)進(jìn)行測(cè)試的結(jié)果列出來。三．設(shè)計(jì)要求學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課設(shè)的時(shí)間計(jì)劃，并在課設(shè)過程中不斷檢測(cè)自己的計(jì)劃完成情況，及時(shí)的向教師匯報(bào)。[選作內(nèi)容]（1）求多個(gè)景點(diǎn)的最佳（最短）游覽路徑。（2）顯示輸入序列和棧的變化過程。程序的輸出結(jié)果是每個(gè)詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號(hào)，格式自行設(shè)計(jì)。（2）整個(gè)統(tǒng)計(jì)過程中只對(duì)小說文字掃描一遍以提高效率?？梢娺@個(gè)處理過程正好和棧的特點(diǎn)相吻合。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號(hào)碼及到達(dá)或離去的時(shí)刻，其中，‘A’表示到達(dá)；‘D’表示離去，‘E’表示輸入結(jié)束。（3）汽車可以直接從便道上開走，此時(shí)排在它前面的汽車要先開走讓路，然后再依次排到隊(duì)尾。設(shè)文件每行不超過320個(gè)字符，很少超過80字符。印出的每一行要前置以行號(hào)和一個(gè)空格符，行號(hào)固定占4位，增量為1。一行文字可能占多個(gè)行塊。如果是，則為了在插入這一行之后仍保持活區(qū)大小不超過activemaxlen，應(yīng)將插入點(diǎn)之前的活區(qū)部分中第一行輸出到輸出文件中；若插入點(diǎn)為第一行之前，則只得將新插入的這一行輸出。以用戶指定的結(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下的結(jié)點(diǎn)訪問序列和相應(yīng)生成樹的邊集。赫夫曼樹的建立*問題描述：建立建立最優(yōu)二叉樹函數(shù)*要求：可以建立函數(shù)輸入二叉樹，并輸出其赫夫曼樹在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；圖的建立及輸出*問題描述：建立圖的存儲(chǔ)結(jié)構(gòu)（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學(xué)生可以任選兩種類型），能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。Home鍵設(shè)置迷宮起點(diǎn)，End鍵設(shè)終點(diǎn)，上下左右箭頭鍵移動(dòng)，Enter鍵添加墻，Del鍵刪除墻，完成后按F9鍵演示，Esc鍵退出。*基本要求：以字符序列的形式從終端上輸入語法正確的、不含變量的整數(shù)表達(dá)式。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本原酸的運(yùn)算器。18．圖書管理*問題描述：圖書管理基本業(yè)務(wù)活動(dòng)包括：對(duì)一本書的采編入庫、清除庫存、借閱和歸還等等。③某種書的現(xiàn)存量大于零，則借出一本，登記借閱者的圖書證號(hào)和歸還期限。*輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出“全部字母數(shù)”、“數(shù)字個(gè)數(shù)”、“空格個(gè)數(shù)”、“文章總字?jǐn)?shù)”（3）輸出刪除某一字符串后的文章；50，52 70，72回文判斷[問題描述]試寫一個(gè)算法，判斷依次讀入的一個(gè)以為結(jié)束符的字母序列，是否為形如‘序列1 amp。2建立二叉樹，層序、先序遍歷（用遞歸或非遞歸的方法都可以）*問題描述：要求能夠輸入樹的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹存儲(chǔ)結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；五、參考書目《數(shù)據(jù)結(jié)構(gòu) C語言》 嚴(yán)蔚敏 清華大學(xué)出版社 《c語言程序設(shè)計(jì)》 譚浩強(qiáng) 清華大學(xué)出版社 《數(shù)據(jù)結(jié)構(gòu)》 高教出版社《數(shù)據(jù)結(jié)構(gòu)習(xí)題》 李春保 清華大學(xué)出版社 《數(shù)據(jù)結(jié)構(gòu)習(xí)題》 嚴(yán)蔚敏 清華大學(xué)出版社 《c語言與數(shù)據(jù)結(jié)構(gòu)》 王立柱 清華大學(xué)出版社《數(shù)據(jù)結(jié)構(gòu)（C語言篇）習(xí)題與解析》李春葆 清華大學(xué)出版社計(jì)算機(jī)軟件教研室 2004年1月7日第四篇：《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》教學(xué)大綱《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》教學(xué)大綱課程名稱： 課程編號(hào)： 適用專業(yè)： 總 學(xué) 分： 總 學(xué) 時(shí)： 其中實(shí)驗(yàn)學(xué)時(shí) 主 撰 人： 撰寫日期：一、目的與任務(wù)《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)軟件的一門基礎(chǔ)課程，計(jì)算機(jī)科學(xué)各領(lǐng)域及有關(guān)的應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部分要加上清晰的程序注釋。但如果在剩余的物品中找不到合適的物品以填滿背包，則說明“剛剛”裝入背包的那件物品“不合適”，應(yīng)將它取出“棄之一邊”，繼續(xù)再從“它之后”的物品中選取，如此重復(fù)，直至求得滿足條件的解，或者無解。（2）要求 利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個(gè)人的編號(hào)。1長(zhǎng)整數(shù)四則運(yùn)算*問題描述：設(shè)計(jì)一個(gè)實(shí)現(xiàn)任意長(zhǎng)的整數(shù)進(jìn)行加法運(yùn)算的演示程序。（6）9999,9999,9999；9999,9999,9999；應(yīng)輸出“1,9999,9999,9998”。1克魯斯?fàn)査惴ㄇ笞钚∩蓸鋯栴}描述：從鍵盤上輸入一個(gè)圖的基本信息（圖用鄰矩陣表示）1)首先輸入圖的結(jié)點(diǎn)數(shù)num 2)依次輸入圖的各條邊3)程序所能達(dá)到的功能：能夠輸出這個(gè)圖的一棵最小生成樹1算術(shù)表達(dá)式求值演示（1）問題描述：表達(dá)式求值是實(shí)現(xiàn)程序設(shè)計(jì)語言的基本問題之一，也是棧的應(yīng)用的一個(gè)典型例子。稀疏矩陣的輸入形式采用三元組表示，而運(yùn)算結(jié)構(gòu)的矩陣則以通常的陣列形式列出。2．課程設(shè)計(jì)實(shí)行指導(dǎo)教師負(fù)責(zé)制，由指導(dǎo)教師全面負(fù)責(zé)課程設(shè)計(jì)的指導(dǎo)與管理工作。能較好地完成設(shè)計(jì)任務(wù)，成績(jī)較突出，表現(xiàn)良好；撰寫了質(zhì)量比較高的實(shí)習(xí)報(bào)告。二、課程設(shè)計(jì)內(nèi)容及學(xué)時(shí)分配寫出不少于3000字的課程設(shè)計(jì)說明書。成績(jī)?cè)u(píng)定實(shí)行優(yōu)、良、中、及格和不及格五個(gè)等級(jí)。不及格者不能得到相應(yīng)的學(xué)分，需重新做課程設(shè)計(jì)，經(jīng)指導(dǎo)教師考核及格后，方可取得相應(yīng)學(xué)分。1． 運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)系統(tǒng)； 2． 停車場(chǎng)管理系統(tǒng)； 3． 民航售票系統(tǒng)； 4． 有理數(shù)四則運(yùn)算器； 5． 文本格式化器； 6． 哈夫曼編/譯碼器； 7． 教學(xué)計(jì)劃編制； 8． 計(jì)算機(jī)輔助考核系統(tǒng)；9． 學(xué)籍管理系統(tǒng)； 10． 圖書管理系統(tǒng)。③ 及格：目的明確，態(tài)度基本端正，能遵守學(xué)校紀(jì)律，在督促下能開展工作 并完成一定的設(shè)計(jì)任務(wù)，無大的違紀(jì)違規(guī)現(xiàn)象；撰寫了實(shí)習(xí)報(bào)告。課程設(shè)計(jì)成績(jī)?yōu)槠綍r(shí)表現(xiàn)30%、設(shè)計(jì)報(bào)告50%、答辯20%?？稍O(shè)矩陣的行數(shù)和列數(shù)均不超過20。（2）基本要求：以字符序列的形式從終端上輸入語法正確的、不含變量的整數(shù)表達(dá)式。*實(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^151)。（5）輸出形式：建立一個(gè)輸出函數(shù)，將正確的輸出序列建立二叉樹，層序、先序遍歷（用遞歸或非遞歸的方法都可以）（1）問題描述：建立二叉樹，并實(shí)行層序、先序遍歷等算法（2）要求：能夠輸入樹的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹存儲(chǔ)結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；赫夫曼樹的建立（1）問題描述：建立建立最優(yōu)二叉樹函數(shù)（2）要求：可以建立函數(shù)輸入二叉樹，并輸出其赫夫曼樹在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測(cè)試數(shù)據(jù)和結(jié)果、