【正文】 通過了答辯。評分標準：① 優(yōu)秀：目的明確，態(tài)度端正，模范遵守學校的各項紀律。（2）程序可以對三元組的輸入順序加以限制，例如，按行優(yōu)先。利用教材中給出的算符優(yōu)先關系，實現(xiàn)對算術四則混合運算表達式的求值，并仿照教材例31演示在求值中運算符棧、運算數(shù)棧、輸入字符和主要操作的變化過程。（2）可以利用頭結點數(shù)據域的符號代表長整數(shù)的符號。輸入和輸出形式：按中國對于長整數(shù)的表示習慣，每四位一組，組間用逗號隔開。拓撲排序（1）問題描述：編寫函數(shù)實現(xiàn)圖的拓撲排序。5）修改航班信息：當航班信息改變可以修改航班數(shù)據文件（2）要求根據以上功能說明，設計航班信息，訂票信息的存儲結構，設計程序完成功能；迷宮求解（1）問題描述可以輸入一個任意大小的迷宮數(shù)據，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；（2）要求在上交資料中請寫明：存儲結構、基本算法（可以使用程序流程圖）、源程序、測試數(shù)據和結果、算法的時間復雜度、另外可以提出算法的改進方法；dijkstra算法求最短路徑問題描述：從鍵盤上輸入一個圖的基本信息（圖用鄰矩陣表示）1)首先輸入圖的結點數(shù)num 2)依次輸入圖的各條邊3）程序所能達到的功能：輸出用dijkstra算法求出的一條最短路徑。2．課程設計實習報告的書寫格式① 設計題目數(shù)據結構 408104 計算機科學與技術 72 30 2012．6436104 軟件工程審 核 人：②運行環(huán)境（軟、硬件環(huán)境）③算法設計的思想 ④算法的流程圖 ⑤算法設計分析 ⑥源代碼 ⑦運行結果分析 ⑧收獲及體會 3．實施方式可設34人一題，安排在《數(shù)據結構》課程開課學期布置題目，然后在期末兩周時間內完成。二、教學基本要求1．設計和調試過程要規(guī)范化需求分析：將題目中要求的功能進行敘述分析，并且設計解決此問題的數(shù)據存儲結構，（有些題目已經指定了數(shù)據存儲的，按照指定的設計），設計或敘述解決此問題的算法，描述算法建議使用流程圖，進行算法分析指明關鍵語句的時間復雜度?！?，且序列2 是序列1的逆序列。這個操作是為了調試和維護的目的而設置的。（2）作為演示系統(tǒng)，不必使用文件，全部數(shù)據可以都在內存存放。*實現(xiàn)提示：（1）首先應輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個矩陣的行、列數(shù)對于所要求作的運算是否匹配。（2）在輸入表達式的字符序列的同時，完成運算符和運算數(shù)（整數(shù)）的識別處理，以及相應的運算。此外，因受圖形界面限制，不能保存或載入測試文件（此功能可在Maze_text中實現(xiàn)）。*輸出的形式：數(shù)字大小逐個遞增的數(shù)列?1圖的遍歷*問題描述：對任意給定的圖（頂點數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊列的五種基本運算（置空隊列、進隊、出隊、取隊頭元素、判隊空）實現(xiàn)圖的廣度優(yōu)先搜索周游。[實現(xiàn)提示]設圖的結點不超過30個，每個結點用一個編號表示（如果一個圖有n個結點，則它們的編號分別為1,2,?,n）。[選作內容]（1）對于命令格式非法等一切錯誤作嚴格檢查和適當處理。行插入將引起隨后各行行號的順序下推。注意測試邊界數(shù)據，如首行、尾行。格式：d[□]刪除活區(qū)中第行（到第行）。限制這些操作以行為單位進行的編輯程序稱為行編輯程序。棧以順序結構實現(xiàn)，隊列以鏈表實現(xiàn)。[測試數(shù)據]輸入 （[ ]（）），結果“匹配”輸入 [（）]，結果“此串括號匹配不合法”為起始和結束標志。（4）推廣到更一般的模式集匹配問題，并設待查模式串可以跨行（提示：定義操作getachar）[問題描述]可以輸入一個任意大小的迷宮數(shù)據，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；[基本要求]含有兩個以上的迷宮圖，由用戶選擇哪一張迷宮圖； 實現(xiàn)深度優(yōu)先、廣度優(yōu)先兩種回溯法。這樣，每讀入一行，就統(tǒng)計每個詞在這行中的出現(xiàn)次數(shù)。操作數(shù)類型擴充到實數(shù)。算術表達式求值[問題描述]一個算術表達式是由操作數(shù)(operand)、運算符(operator)和界限符(delimiter)組成的。四．設計題目校園導游程序[問題描述]用無向網表示你所在學校的校園景點平面圖，圖中頂點表示主要景點，存放景點的編號、名稱、簡介等信息，圖中的邊表示景點間的道路，存放路徑長度等信息。②源程序（可以是一組源程序，即詳細設計部分）源程序要按照寫程序的規(guī)則來編寫。下列B樹的打印格式如下所示：50，52 70，728第四篇：數(shù)據結構課程設計教學大綱《數(shù)據結構課程設計》教學大綱Data Structure Course Design一、課程的性質、教學目的和要求《數(shù)據結構》是計算機軟件的一門基礎課程，計算機科學各領域及有關的應用軟件都要用到各種類型的數(shù)據結構。但是由于上述四項基本業(yè)務活動都是通過書號（即關鍵字）進行的，所以要用B樹對書號盡力索引，以獲得高效率?？稍O矩陣的行數(shù)和列數(shù)均不超過20。（3）在識別出運算數(shù)的同時，要將其字符序列形式轉換成整數(shù)形式。5）當未輸入起點時，消息顯示“Error： You must set Startplace.”；未輸入終點時，顯示“Error： You must set Endplace.” 找到路徑時，屏幕顯示足跡，并在消息框出現(xiàn)Path found，否則消去足跡，顯示Path not ．一元稀疏多項式計算器*問題描述：一元多項式簡單計算器的基本功能是：（1）輸入并建立多項式；（2）輸出多項式，輸出形式為整數(shù)序列n,c1,e1,c2,e2,?,en，其中n是多項式的項數(shù)，ci和ei分別是第I項的系數(shù)和指數(shù)，序列指指數(shù)降序排列；（3）多項式a和b相加，建立多項式a+b；（4）多項式a和b相減，建立多項式ab。頂點和邊均含有相關信息。*測試數(shù)據：由讀者指定,可自行指定一個馬的初始位置。（2）可以利用頭結點數(shù)據域的符號代表長整數(shù)的符號。輸入和輸出形式：按中國對于長整數(shù)的表示習慣，每四位一組，組間用逗號隔開。1拓撲排序*問題描述：編寫函數(shù)實現(xiàn)圖的拓撲排序。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個仍開始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。（數(shù)據文件的數(shù)據讀寫方法等相關內容在c語言程序設計的書上，請自學解決）請在最后的上交資料中指明你用到的存儲結構；測試數(shù)據：要求使用全部合法數(shù)據；整體非法數(shù)據；局部非法數(shù)據。為保證質量，需要每個學生將每天的上機調試程序的時間記錄下來，作為評判成績的標準之一。如果程序不能正常運行，寫出實現(xiàn)此算法中遇到的問題，和改進方法。成績評定：課程設計成績分兩部分，設計報告占40％，設計作品占60％。二叉排序樹問題描述：完成二叉排序樹的創(chuàng)建、查找、插入和刪除操作。4）每一個函數(shù)要有必要的注釋，在課程設計論文中有流程圖。問題描述：實現(xiàn)線索二叉樹的生成、遍歷、查找、插入和刪除操作。學生雖然可以通過與課堂教學同步的上機實驗完成相關內容的練習，但卻往往局限于一些功能簡單、彼此之間關系獨立的算法和程序。*要求：利用單向循環(huán)鏈表存儲結構模擬此過程，按照出列的順序輸出各個人的編號。4）考核方式課程設計結束時，要求學生寫出課程設計報告（附源程序），可運行的軟件系統(tǒng) 課程設計成績分兩部分，設計報告占30％，設計作品占70％。對有些題目提出算法改進方案，比較不同算法的優(yōu)缺點。數(shù)據結構是一門較為抽象的課程，在學習完該課程后，學生往往會覺得其實際應用難以理解?；疽螅?）設計和調試過程要規(guī)范化。盡量避免出現(xiàn)操作錯誤時出現(xiàn)死循環(huán)。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個仍開始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。三、時間進度學生課程設計時間安排如下： 第1周初，布置題目 第2周末，中期檢查第3周末，個別指導難度突破 第4周末，驗收四、閱讀參考書目：《數(shù)據結構 C語言》 嚴蔚敏 清華大學出版社 2007年3月《《數(shù)據結構》算法實現(xiàn)及解析》（第二版）高一凡 西安電子科技大學出版社 2004年10月《c語言程序設計》 譚浩強 清華大學出版社《數(shù)據結構習題與解析》 李春保 清華大學出版社 2004年2月 《數(shù)據結構習題》 嚴蔚敏 清華大學出版社 1999年2月 《c/c++與數(shù)據結構》 王立柱 清華大學出版社 2008年3月《數(shù)據結構（C語言篇）習題與解析》李春葆 清華大學出版社 2005年4月第二篇：《數(shù)據結構》課程設計教學大綱《數(shù)據結構》課程設計教學大綱適用專業(yè)：計算機科學與技術 課程周數(shù)：2周一、大綱說明本大綱根據計算機科學與技術專業(yè)人才培養(yǎng)方案制訂。線索二叉樹問題描述：實現(xiàn)線索二叉樹的生成、遍歷、查找、插入和刪除操作。要求：1）先生成一個網圖，該網圖既能是無向網圖，有能是有向網圖； 2）要求分別采用鄰接矩陣和鏈接表存儲來完成； 3）最后打印輸出最小生成樹；4）每一個函數(shù)要有必要的注釋，在課程設計論文中有流程圖。要求：1）可以循環(huán)查找，可以選擇退出；2）分別采用順序存儲和鏈式存儲完成分塊查找，其中在順序存儲結果下，索引表的查找采用二分查找；3）分別用函數(shù)完成索引表查找和塊中查找；4）每一個函數(shù)要有必要的注釋，在課程設計論文中有流程圖。要求：1）定義一個哈希表，并打印輸出結果； 2）分別編寫函數(shù)完成查找、插入和刪除； 3）測試查找、插入和刪除，分別打印測試結果；4）每一個函數(shù)要有必要的注釋，在課程設計論文中有流程圖。① 需求分析將題目中要求的功能進行敘述分析，并且設計解決此問題的數(shù)據存儲結構，（有些題目已經指定了數(shù)據存儲的，按照指定的設計），設計或敘述解決此問題的算法，描述算法建議使用流程圖，進行算法分析指明關鍵語句的時間復雜度。2．課程設計實習報告的書寫格式① 設計題目（任選其一）②運行環(huán)境（軟、硬件環(huán)境）③算法設計的思想 ④算法的流程圖 ⑤算法設計分析 ⑥源代碼 ⑦運行結果分析 ⑧收獲及體會 3．實施方式可設34人一題，安排在《數(shù)據結構》課程開課學期布置題目，然后在期末兩周時間內完成。（m1).可以輸入各個項目的前三名或前五名的成績； 2)．能統(tǒng)計各學?？偡?，3)．可以按學校編號、學?？偡帧⒛信畧F體總分排序輸出；4).可以按學校編號查詢學校某個項目的情況；可以按項目編號查詢取得前三或前五名的學校。*要求（1）分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字數(shù)；（2）統(tǒng)計某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。*輸出形式：建立一個輸出函數(shù)，將正確的輸出序列猴子選大王*問題描述：一堆猴子都有編號，編號是1，2，3...m ,這群猴子（m個）按照1m的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第N個，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。1長整數(shù)四則運算*問題描述：設計一個實現(xiàn)任意長的整數(shù)進行加法運算的演示程序。（6）9999,9999,9999；9999,9999,9999；應輸出“1,9999,9999,9998”。1馬踏棋盤*問題描述：將馬隨機放在國際象棋的8 8棋盤Bord[8Ⅱ8]的某個方格中，馬按走棋規(guī)則進行移動。（3）為來訪客人提供圖中任意景點相關信息的查詢。3）橙色的實心小圓圈表示起點，綠色實心圓圈表示終點，空心圓圈表示足跡，紅色方塊表示墻。利用教材中給出的算符優(yōu)先關系，實現(xiàn)對算術四則混合運算表達式的求值，并仿照教材例31演示在求值中運算符棧、運算數(shù)棧、輸入字符和主要操作的變化過程。*基本要求：以“帶行邏輯鏈接信息”的三元組順序表示稀疏矩陣，實現(xiàn)兩個矩陣相加、相減和相乘的運算。試設計一個圖書管理系統(tǒng)，將上述業(yè)務活動借助于計算機系統(tǒng)完成。④歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量。給出實現(xiàn)功能的一組或多組測試數(shù)據，程序調試后，將按照此測試數(shù)據進行測試的結果列出來。三．設計要求學生要發(fā)揮自主學習的能力，充分利用時間，安排好課設的時間計劃，并在課設過程中不斷檢測自己的計劃完成情況，及時的向教師匯報。[選作內容]（1）求多個景點的最佳（最短）游覽路徑。（2）顯示輸入序列和棧的變化過程。程序的輸出結果是每個詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號，格式自行設計。（2）整個統(tǒng)計過程中只對小說文字掃描一遍以提高效率?？梢娺@個處理過程正好和棧的特點相吻合。每一組輸入數(shù)據包括三個