【正文】 構自己設定）可以訂票，如果該航班已經無票，可以提供相關可選擇航班；4）退票： 可退票，退票后修改相關數據文件；客戶資料有姓名，證件號，訂票數量及航班情況，訂單要有編號。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數，如此下去，直到所有人全部出列為止。（5）輸出形式：建立一個輸出函數，將正確的輸出序列建立二叉樹，層序、先序遍歷（用遞歸或非遞歸的方法都可以）（1）問題描述：建立二叉樹，并實行層序、先序遍歷等算法（2）要求：能夠輸入樹的各個結點，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹存儲結構的的輸入函數、輸出層序遍歷序列的函數、輸出先序遍歷序列的函數；赫夫曼樹的建立（1）問題描述：建立建立最優(yōu)二叉樹函數（2）要求：可以建立函數輸入二叉樹，并輸出其赫夫曼樹在上交資料中請寫明：存儲結構、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測試數據和結果、算法的時間復雜度、另外可以提出算法的改進方法；圖的建立及輸出（1）問題描述：建立圖的存儲結構（圖的類型可以是有向圖、無向圖、有向網、無向網，學生可以任選兩種類型）（2）要求：能夠輸入圖的頂點和邊的信息，并存儲到相應存儲結構中，而后輸出圖的鄰接矩陣。輸出的形式：數字大小逐個遞增的數列1圖的遍歷 對任意給定的圖（頂點數和邊數自定），建立它的鄰接表并輸出，然后利用隊列的五種基本運算（置空隊列、進隊、出隊、取隊頭元素、判隊空）實現圖的廣度優(yōu)先搜索周游。任何整形變量的范圍是(2^151)。（3）9999,9999；1,0000,0000,0000；應輸出“999（4）1,0001,0001；1,0001,0001；應輸出“0”。*實現提示：（1）每個結點中可以存放的最大整數為32767，才能保證兩數相加不會溢出，但若這樣存放，即相當于按32768進制存放，在十進制與32768進制數之間的轉換十分不方便，故可以在每個結點中僅存十進制的4位，即不超過9999的非負整數，整個鏈表表示為萬進制。兩操作數的頭指針存于指針數組中是簡化程序結構的一種方法。（2）基本要求：以字符序列的形式從終端上輸入語法正確的、不含變量的整數表達式。實現一個能進行稀疏矩陣基本原酸的運算器?？稍O矩陣的行數和列數均不超過20。四、時間安排《數據結構課程設計》安排在第三學期進行，時間2周（1718周）。課程設計成績?yōu)槠綍r表現30%、設計報告50%、答辯20%。答辯準確流利。③ 及格：目的明確，態(tài)度基本端正，能遵守學校紀律，在督促下能開展工作 并完成一定的設計任務，無大的違紀違規(guī)現象；撰寫了實習報告。2．成績評定依據上述考核內容，最后采用優(yōu)（90分）、良（80～89分）、中（70～79分）及格（60～69分）、不及格（七、主要參考資料《數據結構 C語言》 嚴蔚敏 清華大學出版社 《c語言程序設計》 譚浩強 清華大學出版社 《數據結構習題》 李春保 清華大學出版社 《數據結構習題》 嚴蔚敏 清華大學出版社 《c語言與數據結構》 王立柱 清華大學出版社 《數據結構（C語言篇）習題與解析》李春葆 。④ 不及格：實習態(tài)度端正，不能遵守實習單位的紀律，不服從領導，自由散漫，工作消極被動，不能完成實習任務，實習期間有失職、曠工、打架、酗酒等大的過失。能較好地完成設計任務，成績較突出，表現良好；撰寫了質量比較高的實習報告。工作認真，積極 主動，吃苦耐勞，能出色的完成設計任務。2．課程設計實行指導教師負責制，由指導教師全面負責課程設計的指導與管理工作。注意研究教科書中的算法，以便提高計算效率。稀疏矩陣的輸入形式采用三元組表示，而運算結構的矩陣則以通常的陣列形式列出。16．稀疏矩陣運算器*問題描述：稀疏矩陣是指那些多數元素為0的矩陣。1克魯斯爾算法求最小生成樹問題描述：從鍵盤上輸入一個圖的基本信息（圖用鄰矩陣表示）1)首先輸入圖的結點數num 2)依次輸入圖的各條邊3)程序所能達到的功能：能夠輸出這個圖的一棵最小生成樹1算術表達式求值演示（1）問題描述：表達式求值是實現程序設計語言的基本問題之一，也是棧的應用的一個典型例子。用其絕對值表示元素結點數目。（6）9999,9999,9999；9999,9999,9999；應輸出“1,9999,9999,9998”。*測試數據：（1）0；0；應輸出“0”。1長整數四則運算*問題描述：設計一個實現任意長的整數進行加法運算的演示程序。（2）要求：能夠以一定的方式輸入數據結點各種排序（1）問題描述：對30000個隨機整數，利用插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序等排序方法進行排序，并統(tǒng)計每一種排序上機所花費的時間。（2）要求 利用單向循環(huán)鏈表存儲結構模擬此過程，按照出列的順序輸出各個人的編號。joseph環(huán)（1）問題描述編號是1，2，??,n的n個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數）。但如果在剩余的物品中找不到合適的物品以填滿背包，則說明“剛剛”裝入背包的那件物品“不合適”，應將它取出“棄之一邊”，繼續(xù)再從“它之后”的物品中選取，如此重復，直至求得滿足條件的解，或者無解。4．答辯：課題的論述、測試及問題回答三、課程設計內容背包問題的求解：假設有一個能裝入總體積為T的背包和n件體積分別為w1 , w2 , … , wn 的物品，能否從n件物品中挑選若干件恰好裝滿背包，即使w1 +w2 + … + wn=T，要求找出所有滿足上述條件的解。要結構清晰，重點函數的重點變量，重點功能部分要加上清晰的程序注釋。給出實現功能的一組或多組測試數據，程序調試后，將按照此測試數據進行測試的結果列出來。2建立二叉樹，層序、先序遍歷（用遞歸或非遞歸的方法都可以）*問題描述：要求能夠輸入樹的各個結點，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹存儲結構的的輸入函數、輸出層序遍歷序列的函數、輸出先序遍歷序列的函數；五、參考書目《數據結構 C語言》 嚴蔚敏 清華大學出版社 《c語言程序設計》 譚浩強 清華大學出版社 《數據結構》 高教出版社《數據結構習題》 李春保 清華大學出版社 《數據結構習題》 嚴蔚敏 清華大學出版社 《c語言與數據結構》 王立柱 清華大學出版社《數據結構（C語言篇）習題與解析》李春葆 清華大學出版社計算機軟件教研室 2004年1月7日第五篇：《數據結構課程設計》教學大綱《數據結構課程設計》教學大綱課程名稱： 課程編號： 適用專業(yè)： 總 學 分： 總 學 時： 其中實驗學時 主 撰 人： 撰寫日期：一、目的與任務《數據結構》是計算機軟件的一門基礎課程，計算機科學各領域及有關的應用軟件都要用到各種類型的數據結構。例如，‘a+bamp。*輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出“全部字母數”、“數字個數”、“空格個數”、“文章總字數”（3）輸出刪除某一字符串后的文章；50，52 70，72回文判斷[問題描述]試寫一個算法，判斷依次讀入的一個以為結束符的字母序列，是否為形如‘序列1 amp。下列B樹的打印格式如下所示：1文章編輯*問題描述：輸入一頁文字，程序可以統(tǒng)計出文字、數字、空格的個數。③某種書的現存量大于零，則借出一本，登記借閱者的圖書證號和歸還期限。但是由于上述四項基本業(yè)務活動都是通過書號（即關鍵字）進行的，所以要用B樹對書號盡力索引，以獲得高效率。18．圖書管理*問題描述：圖書管理基本業(yè)務活動包括：對一本書的采編入庫、清除庫存、借閱和歸還等等。可設矩陣的行數和列數均不超過20。實現一個能進行稀疏矩陣基本原酸的運算器。（3）在識別出運算數的同時，要將其字符序列形式轉換成整數形式。*基本要求：以字符序列的形式從終端上輸入語法正確的、不含變量的整數表達式。5）當未輸入起點時，消息顯示“Error： You must set Startplace.”；未輸入終點時，顯示“Error： You must set Endplace.” 找到路徑時，屏幕顯示足跡，并在消息框出現Path found，否則消去足跡，顯示Path not ．一元稀疏多項式計算器*問題描述：一元多項式簡單計算器的基本功能是：（1）輸入并建立多項式；（2）輸出多項式，輸出形式為整數序列n,c1,e1,c2,e2,?,en，其中n是多項式的項數，ci和ei分別是第I項的系數和指數，序列指指數降序排列；（3）多項式a和b相加，建立多項式a+b；（4）多項式a和b相減，建立多項式ab。Home鍵設置迷宮起點，End鍵設終點，上下左右箭頭鍵移動，Enter鍵添加墻，Del鍵刪除墻，完成后按F9鍵演示，Esc鍵退出。1線性表的操作*問題描述：利作鏈表的插入運算建立線性鏈表，然后利用鏈表的查找、刪除、計數、輸出等運算反復實現鏈表的這些操作（插入、刪除、查找、計數、輸出單獨寫成函數的形式），并能在屏幕上輸出操作前后的結果。赫夫曼樹的建立*問題描述：建立建立最優(yōu)二叉樹函數*要求：可以建立函數輸入二叉樹，并輸出其赫夫曼樹在上交資料中請寫明：存儲結構、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測試數據和結果、算法的時間復雜度、另外可以提出算法的改進方法；圖的建立及輸出*問題描述：建立圖的存儲結構（圖的類型可以是有向圖、無向圖、有向網、無向網，學生可以任選兩種類型），能夠輸入圖的頂點和邊的信息，并存儲到相應存儲結構中，而后輸出圖的鄰接矩陣。通過輸入圖的全部邊輸入一個圖，每個邊為一個數對，可以對邊的輸入順序作出某種限制。以用戶指定的結點為起點，分別輸出每種遍歷下的結點訪問序列和相應生成樹的邊集。（2）加入更復雜的編輯操作，如對某行進行串替換；在活區(qū)內進行模式匹配等，格式可以為S和m。如果是，則為了在插入這一行之后仍保持活區(qū)大小不超過activemaxlen，應將插入點之前的活區(qū)部分中第一行輸出到輸出文件中；若插入點為第一行之前，則只得將新插入的這一行輸出。（2）初始化過程包括：請用戶提供輸入文件名（空串表示無輸入文件）和輸出文件名，兩者不能相同。一行文字可能占多個行塊。[實現提示]（1）設活區(qū)的大小用行數activemaxlen（可設為100）來描述。印出的每一行要前置以行號和一個空格符，行號固定占4位，增量為1。兩種格式的例子是：“d10↙”和“d10□14↙”（3）活區(qū)切換。設文件每行不超過320個字符，很少超過80字符。被編輯的文本文件可能很大，全部讀入編輯程序的數據空間（內存）的做法既不經濟，也不總能實現。（3）汽車可以直接從便道上開走，此時排在它前面的汽車要先開走讓路，然后再依次排到隊尾。[實現提示]需另設一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結構實現。每一組輸入數據包括三個數據項：汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時刻，其中，‘A’表示到達；‘D’表示離去，‘E’表示輸入結束。[問題描述]設停車場內只有一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進出?？梢娺@個處理過程正好和棧的特點相吻合。在上交資料中請寫明：存儲結構、基本算法（可以使用程序流程圖）、源程序、算法的時間復雜度、另外可以提出算法的改進方法；[實現提示]可以用一個二維數組存儲迷宮圖，值為1或者0分別表示通路和不通； 搜索路徑可以參考樹的深度優(yōu)先和廣度優(yōu)先算法。（2）整個統(tǒng)計過程中只對小說文字掃描一遍以提高效率。出現位置所在行的行號可以用鏈表存儲。程序的輸出結果是每個詞的出現次數和出現位置所在行的行號，格式自行設計。文學研究助手[問題描述]文學研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現次數和位置。（2）顯示輸入序列和棧的變化過程。假設操作數是正整數，運算符只含加減乘除等四種運算符，界限符有左右括號和表達式起始、結束符“”，如：（7+15）*（2328/4）。[選作內容]（1）求多個景點的最佳（最短）游覽路徑。要求能夠回答有關景點介紹、游覽路徑等問題。三．設計要求學生要發(fā)揮自主學習的能力，充分利用時間，安排好課設的時間計劃，并在課設過程中不斷檢測自己的計劃完成情況，及時的向教師匯報。要結構清晰，重點函數的重點變量，重點功