【正文】 2．成績評定依據(jù)上述考核內(nèi)容，最后采用優(yōu)（90分）、良（80～89分）、中（70～79分）及格（60～69分）、不及格（七、主要參考資料《數(shù)據(jù)結(jié)構(gòu) C語言》 嚴(yán)蔚敏 清華大學(xué)出版社 《c語言程序設(shè)計(jì)》 譚浩強(qiáng) 清華大學(xué)出版社 《數(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í)題與解析》李春葆 。④ 不及格：實(shí)習(xí)態(tài)度端正，不能遵守實(shí)習(xí)單位的紀(jì)律，不服從領(lǐng)導(dǎo)，自由散漫，工作消極被動(dòng)，不能完成實(shí)習(xí)任務(wù)，實(shí)習(xí)期間有失職、曠工、打架、酗酒等大的過失。③ 及格：目的明確，態(tài)度基本端正，能遵守學(xué)校紀(jì)律，在督促下能開展工作 并完成一定的設(shè)計(jì)任務(wù)，無大的違紀(jì)違規(guī)現(xiàn)象；撰寫了實(shí)習(xí)報(bào)告。能較好地完成設(shè)計(jì)任務(wù)，成績較突出，表現(xiàn)良好；撰寫了質(zhì)量比較高的實(shí)習(xí)報(bào)告。答辯準(zhǔn)確流利。工作認(rèn)真，積極 主動(dòng)，吃苦耐勞，能出色的完成設(shè)計(jì)任務(wù)。課程設(shè)計(jì)成績?yōu)槠綍r(shí)表現(xiàn)30%、設(shè)計(jì)報(bào)告50%、答辯20%。2．課程設(shè)計(jì)實(shí)行指導(dǎo)教師負(fù)責(zé)制，由指導(dǎo)教師全面負(fù)責(zé)課程設(shè)計(jì)的指導(dǎo)與管理工作。四、時(shí)間安排《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》安排在第三學(xué)期進(jìn)行，時(shí)間2周（1718周）。注意研究教科書中的算法，以便提高計(jì)算效率?？稍O(shè)矩陣的行數(shù)和列數(shù)均不超過20。稀疏矩陣的輸入形式采用三元組表示，而運(yùn)算結(jié)構(gòu)的矩陣則以通常的陣列形式列出。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本原酸的運(yùn)算器。16．稀疏矩陣運(yùn)算器*問題描述：稀疏矩陣是指那些多數(shù)元素為0的矩陣。（2）基本要求：以字符序列的形式從終端上輸入語法正確的、不含變量的整數(shù)表達(dá)式。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è)典型例子。兩操作數(shù)的頭指針存于指針數(shù)組中是簡化程序結(jié)構(gòu)的一種方法。用其絕對值表示元素結(jié)點(diǎn)數(shù)目。*實(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)制。（6）9999,9999,9999；9999,9999,9999；應(yīng)輸出“1,9999,9999,9998”。（3）9999,9999；1,0000,0000,0000；應(yīng)輸出“999（4）1,0001,0001；1,0001,0001；應(yīng)輸出“0”。*測試數(shù)據(jù)：（1）0；0；應(yīng)輸出“0”。任何整形變量的范圍是(2^151)。1長整數(shù)四則運(yùn)算*問題描述：設(shè)計(jì)一個(gè)實(shí)現(xiàn)任意長的整數(shù)進(jìn)行加法運(yùn)算的演示程序。輸出的形式：數(shù)字大小逐個(gè)遞增的數(shù)列1圖的遍歷 對任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊(duì)列的五種基本運(yùn)算（置空隊(duì)列、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空）實(shí)現(xiàn)圖的廣度優(yōu)先搜索周游。（2）要求：能夠以一定的方式輸入數(shù)據(jù)結(jié)點(diǎn)各種排序（1）問題描述：對30000個(gè)隨機(jī)整數(shù)，利用插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序等排序方法進(jìn)行排序，并統(tǒng)計(jì)每一種排序上機(jī)所花費(fèi)的時(shí)間。（5）輸出形式：建立一個(gè)輸出函數(shù)，將正確的輸出序列建立二叉樹，層序、先序遍歷（用遞歸或非遞歸的方法都可以）（1）問題描述：建立二叉樹，并實(shí)行層序、先序遍歷等算法（2）要求：能夠輸入樹的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹存儲(chǔ)結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；赫夫曼樹的建立（1）問題描述：建立建立最優(yōu)二叉樹函數(shù)（2）要求：可以建立函數(shù)輸入二叉樹，并輸出其赫夫曼樹在上交資料中請寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；圖的建立及輸出（1）問題描述：建立圖的存儲(chǔ)結(jié)構(gòu)（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學(xué)生可以任選兩種類型）（2）要求：能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。（2）要求 利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個(gè)人的編號。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直到所有人全部出列為止。joseph環(huán)（1）問題描述編號是1，2，??,n的n個(gè)人按照順時(shí)針方向圍坐一圈，每個(gè)人只有一個(gè)密碼（正整數(shù)）。訂票系統(tǒng)（1）問題描述通過此系統(tǒng)可以實(shí)現(xiàn)如下功能： 1）錄入：可以錄入航班情況（數(shù)據(jù)可以存儲(chǔ)在一個(gè)數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）2）查詢： 可以查詢某個(gè)航線的情況（如，輸入航班號，查詢起降時(shí)間，起飛抵達(dá)城市，航班票價(jià)，票價(jià)折扣，確定航班是否滿倉）；可以輸入起飛抵達(dá)城市，查詢飛機(jī)航班情況；3）訂票：（訂票情況可以存在一個(gè)數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定）可以訂票，如果該航班已經(jīng)無票，可以提供相關(guān)可選擇航班；4）退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。但如果在剩余的物品中找不到合適的物品以填滿背包，則說明“剛剛”裝入背包的那件物品“不合適”，應(yīng)將它取出“棄之一邊”，繼續(xù)再從“它之后”的物品中選取，如此重復(fù)，直至求得滿足條件的解，或者無解。提示：可利用回溯法的設(shè)計(jì)思想來解決背包問題。4．答辯：課題的論述、測試及問題回答三、課程設(shè)計(jì)內(nèi)容背包問題的求解：假設(shè)有一個(gè)能裝入總體積為T的背包和n件體積分別為w1 , w2 , … , wn 的物品，能否從n件物品中挑選若干件恰好裝滿背包，即使w1 +w2 + … + wn=T，要求找出所有滿足上述條件的解。盡量避免出現(xiàn)操作錯(cuò)誤時(shí)出現(xiàn)死循環(huán)。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部分要加上清晰的程序注釋。如果程序不能正常運(yùn)行，寫出實(shí)現(xiàn)此算法中遇到的問題，和改進(jìn)方法。給出實(shí)現(xiàn)功能的一組或多組測試數(shù)據(jù)，程序調(diào)試后，將按照此測試數(shù)據(jù)進(jìn)行測試的結(jié)果列出來。為了學(xué)好《數(shù)據(jù)結(jié)構(gòu)》，必須編寫一些在特定數(shù)據(jù)結(jié)構(gòu)上的算法，通過上機(jī)調(diào)試，才能更好地掌握各種數(shù)據(jù)結(jié)構(gòu)及其特點(diǎn)，同時(shí)提高解決計(jì)算機(jī)應(yīng)用實(shí)際問題的能力。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é)大綱課程名稱： 課程編號： 適用專業(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)。３－１’則不是。例如，‘a(chǎn)+bamp。其中序列1和序列2 中都不含字符‘a(chǎn)mp。*輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出“全部字母數(shù)”、“數(shù)字個(gè)數(shù)”、“空格個(gè)數(shù)”、“文章總字?jǐn)?shù)”（3）輸出刪除某一字符串后的文章；50，52 70，72回文判斷[問題描述]試寫一個(gè)算法，判斷依次讀入的一個(gè)以為結(jié)束符的字母序列，是否為形如‘序列1 amp。*要求（1）分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。下列B樹的打印格式如下所示：1文章編輯*問題描述：輸入一頁文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。⑤顯示：以凹入表的形式顯示B樹。③某種書的現(xiàn)存量大于零，則借出一本，登記借閱者的圖書證號和歸還期限。如果這種書在帳目中已有，則只將總庫存量增加。但是由于上述四項(xiàng)基本業(yè)務(wù)活動(dòng)都是通過書號（即關(guān)鍵字）進(jìn)行的，所以要用B樹對書號盡力索引，以獲得高效率。*基本要求：（1）每種書的登記內(nèi)容至少包括書號、書名、作者、現(xiàn)存量和總庫存量等五4。18．圖書管理*問題描述：圖書管理基本業(yè)務(wù)活動(dòng)包括：對一本書的采編入庫、清除庫存、借閱和歸還等等。注意研究教科書中的算法，以便提高計(jì)算效率?？稍O(shè)矩陣的行數(shù)和列數(shù)均不超過20。稀疏矩陣的輸入形式采用三元組表示，而運(yùn)算結(jié)構(gòu)的矩陣則以通常的陣列形式列出。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本原酸的運(yùn)算器。17．稀疏矩陣運(yùn)算器*問題描述：稀疏矩陣是指那些多數(shù)元素為0的矩陣。（3）在識別出運(yùn)算數(shù)的同時(shí)，要將其字符序列形式轉(zhuǎn)換成整數(shù)形式。*實(shí)現(xiàn)提示：（1）設(shè)置運(yùn)算棧和運(yùn)算數(shù)棧輔助分析算符優(yōu)先關(guān)系。*基本要求：以字符序列的形式從終端上輸入語法正確的、不含變量的整數(shù)表達(dá)式。16．算術(shù)表達(dá)式求值演示*問題描述：表達(dá)式求值是實(shí)現(xiàn)程序設(shè)計(jì)語言的基本問題之一，也是棧的應(yīng)用的一個(gè)典型例子。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 ．一元稀疏多項(xiàng)式計(jì)算器*問題描述：一元多項(xiàng)式簡單計(jì)算器的基本功能是：（1）輸入并建立多項(xiàng)式；（2）輸出多項(xiàng)式，輸出形式為整數(shù)序列n,c1,e1,c2,e2,?,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)式ab。4）本程序只求出一條成功的通路，但若對求解函數(shù)MazePath稍加更改即可求得全部路徑。Home鍵設(shè)置迷宮起點(diǎn)，End鍵設(shè)終點(diǎn)，上下左右箭頭鍵移動(dòng)，Enter鍵添加墻，Del鍵刪除墻，完成后按F9鍵演示，Esc鍵退出。*問題描述：1）輸入一個(gè)任意大小的迷宮，任設(shè)起點(diǎn)、終點(diǎn)、障礙，用棧求出一條走出迷宮的路徑，并顯示在屏幕上。1線性表的操作*問題描述：利作鏈表的插入運(yùn)算建立線性鏈表，然后利用鏈表的查找、刪除、計(jì)數(shù)、輸出等運(yùn)算反復(fù)實(shí)現(xiàn)鏈表的這些操作（插入、刪除、查找、計(jì)數(shù)、輸出單獨(dú)寫成函數(shù)的形式），并能在屏幕上輸出操作前后的結(jié)果。*輸入的數(shù)據(jù)形式為任何一個(gè)正整數(shù)，大小不限。赫夫曼樹的建立*問題描述：建立建立最優(yōu)二叉樹函數(shù)*要求：可以建立函數(shù)輸入二叉樹，并輸出其赫夫曼樹在上交資料中請寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測試數(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)中，而后輸出圖的鄰接矩陣。[選作內(nèi)容]（1）借助于棧類型（自己定義和實(shí)現(xiàn)）將深度優(yōu)先遍歷用非遞歸算法實(shí)現(xiàn)。通過輸入圖的全部邊輸入一個(gè)圖，每個(gè)邊為一個(gè)數(shù)對，可以對邊的輸入順序作出某種限制。注意測試邊界數(shù)據(jù)，如單個(gè)結(jié)點(diǎn)。以用戶指定的結(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下的結(jié)點(diǎn)訪問序列和相應(yīng)生成樹的邊集。試寫一個(gè)程序，演示無向圖的遍歷操作。（2）加入更復(fù)雜的編輯操作，如對某行進(jìn)行串替換；在活區(qū)內(nèi)進(jìn)行模式匹配等，格式可以為S和m。（5）可令前三條命令執(zhí)行后自動(dòng)調(diào)用活區(qū)顯示。如果是，則為了在插入這一行之后仍保持活區(qū)大小不超過