【正文】 算法時間復雜度后綴表達式的算法，數(shù)制的換算利用本章的基本知識設計相關的應用問題循環(huán)隊列的特點及判斷溢出的條件利用隊列的特點設計相關的應用問題串的模式匹配運算算法二叉樹遍歷算法的設計利用二叉樹遍歷算法，解決簡單應用問題 哈夫曼樹的算法圖的遍歷最小生成樹最短路徑二叉排序樹查找平衡樹二叉樹堆排序快速排序 歸并排序三、教學方法與手段充分利用多媒體教學工具，配合黑板上的教學內容較難部分的算法實現(xiàn)過程演義四、教學內容、目標與學時分配教學內容 教學目標 課時分配緒論數(shù)據(jù)結構的內容邏輯結構與存儲結構算法和算法分析線性表線性表的定義與運算線性表的順序存儲線性表的鏈式存儲棧棧的定義與運算棧存儲和實現(xiàn)棧的應用舉例隊列隊列的定義與基本運算隊列的存儲與實現(xiàn)隊列的應用舉例串串的定義與基本運算串的表示與實現(xiàn)串的基本運算樹和二叉樹樹的定義和術語二叉樹樹的基本概念和術語 遍歷二叉數(shù)和線索二叉樹二叉樹的轉換二叉樹的應用哈夫曼樹及其應用圖圖的定義和術語圖的存儲結構圖的遍歷算法圖的連通性查找查找的基本概念與靜態(tài)查找 動態(tài)查找哈希表了解了解掌握熟練掌握順序表存儲地址的計算掌握單鏈表的結構特點和基本運算掌握雙鏈表的結構特點和基本運算掌握棧的定義與運算掌握棧的存儲與實現(xiàn)熟練掌握棧的各種實際應用掌握隊列的定義與基本運算熟練掌握隊列的存儲與實現(xiàn)掌握循環(huán)隊列的特征和基本運算了解串的邏輯結構掌握串的存儲結構熟練掌握串的基本運算了解了解二叉樹熟練掌握二叉樹定義和存儲結構了解二叉樹的遍歷算法掌握掌握哈夫曼的建立及編碼了解了解熟練掌握熟練掌握了解熟練掌握了解哈希表與哈希方法4學時1學時1學時2學時8學時2學時2學時4學時8學時2學時2學時4學時6學時2學時2學時2學時6學時2學時2學時2學時12學時2學時2學時2學時2學時2學時2學時8學時2學時2學時2學時2學時8學時4學時2學時2學時排序12學時 插入排序熟練掌握基本思想3學時 快速排序了解各種內部排序方法和特點3學時 選擇排序掌握2學時 各種排序方法比較掌握2學時實驗內容 實驗目標 課時分配 算法編程實驗：用指針方式編寫程序 復習C（C++）語言指針、結構體等的用法對單鏈表進行遍歷鏈表的描述與操作實現(xiàn)棧及其操作描述方法及操作編寫串子系統(tǒng)1 串的特點及順序定長存儲、操作、查找編寫串子系統(tǒng) 2 串的特點及順序定長存儲、操作、查找編寫樹子系統(tǒng)1 二叉樹的特點及存儲方式、創(chuàng)建、顯示、遍歷等編寫樹子系統(tǒng)2 二叉樹的特點及存儲方式、創(chuàng)建、顯示、遍歷等圖子系統(tǒng)圖的鄰接矩陣的存儲、遍歷、廣度/深度優(yōu)先搜索查找子系統(tǒng)理解查找基本算法、平均查找長度、靜態(tài)、動態(tài)查找等五、考試范圍與題型考試范圍與分數(shù)比例1)緒論12% 2)線性表17% 3)棧7% 4)隊列6% 5)串4% 6)樹和二叉樹14% 7)圖15% 8)查找4% 9)排序21%考試題型與分數(shù)比例1)名詞解釋18% 2)判斷對錯16% 3)填空16% 4)單項選擇18% 5)應用32%六、教材與參考資料教材： 實用數(shù)據(jù)結構基礎（譚浩強）中國鐵道出版社參考資料： 數(shù)據(jù)結構（嚴蔚敏）清華大學出版社數(shù)據(jù)結構實用教程（徐孝凱）清華大學出版社（撰寫人：，審核人： 2學時 2學時 2學時 2學時 2學時 2學時 2學時 2學時 2學時）。二、教學重點與難點數(shù)據(jù)結構中基本概念和術語，算法描述和分析方法。教學目的為：了解算法對于程序設計的重要性 ； 學習掌握基本數(shù)據(jù)結構的描述與實現(xiàn)方法，熟練掌握典型數(shù)據(jù)結構及其應用算法的設計。一、教學目的與要求了解數(shù)據(jù)的邏輯結構和物理結構；教學要求在每章教學內容給出，大體上為三個層次：了解、掌握和熟練掌握。非數(shù)值計算問題的數(shù)學模型不再是傳統(tǒng)的數(shù)學方程問題，而是諸如表、樹、圖之類的數(shù)據(jù)結構。隨著計算機硬件的發(fā)展，對計算機軟件的發(fā)展也提出了越來越高的要求?！?”號多的題目。備注：*號，表示題目的難度系數(shù)；對應的評定成績等級為及格（無*號）、中等（*號）、良好（**號）、優(yōu)秀（***號），學生完成題目的基本要求，即可得到程序設計部分的相應等級成績，完成題目提高要求，成績可以向上浮動，如果沒有完成基本要求，成績向下浮動，直至不及格。提高要求：選用兩種以上的方法實現(xiàn)字典的操作，并比較不同實現(xiàn)算法的時間復雜度和空間復雜度?；疽螅簩崿F(xiàn)字典的常用方法有：有序線性表（Memeber用二分檢索實現(xiàn)）、AVL樹（二叉搜索樹）、Patricia Trie、散列表等，任選一種方法實現(xiàn)字典的操作，查找單詞、插入單詞（插入時，先查找，找不到插入，找到提示用戶）、刪除單詞（刪除時，先查找，找到刪除，找不到提示用戶）。提高要求：“* ”、“? ”等通配符；、粘貼等功能；提示：可以考慮用雙向鏈表實現(xiàn)，每一結點表示一行字符，注意每行字符不能超過255。具體的編輯命令，可參考數(shù)據(jù)結構算法網(wǎng)絡教學平臺上提供的edlin、Vi的命令集。基本要求：編輯器應具備對文本文件的查找、插人、刪除、修改、字符串替換、統(tǒng)計字數(shù)，統(tǒng)計行數(shù)等功能，對于超過一屏的長文件，應能夠分頁顯示，查找功能用字符串匹配算法實現(xiàn)。提高要求：建立源代碼用戶標識符表，比較兩個源代碼用戶標識符出現(xiàn)的頻度，綜合關鍵字頻度和用戶標識符頻度判斷兩個程序的相似性。例如: 關鍵字 Void Int For Char if else while do break class 程序1關鍵字頻度 4 3 0 4 3 0 7 0 0 2 程序2關鍵字頻度 4 2 0 5 4 0 5 2 0 1 X1=[4,3,0,4,3,0,7,0,0,2] X2=[4,2,0,5,4,0,5,2,0,1] 設s是向量X1和X2的相對距離，s=sqrt(∑(xi1xi2)2)，當X1=X2時，s=0, 反映出可能是同一個程序；s值越大，則兩個程序的差別可能也越大。12．程序源代碼的相似性（***）問題描述：對于兩個C++語言的源程序代碼，用哈希表的方法分別統(tǒng)計兩個程序中使用C++語言關鍵字的情況，并最終按定量的計算結果，得出兩份程序的相似性?；疽螅好總€客戶到達銀行的時間和需要辦理的業(yè)務隨機產生，輸出一天客戶在銀行的平均逗留時間和每個窗口每天辦理的客戶數(shù)和每種業(yè)務數(shù)。11．銀行業(yè)務模擬（***）問題描述：設銀行有四個服務窗口，一個等待隊列, 每個窗口均可以辦理存款、取款、掛失、還貸業(yè)務，每種業(yè)務所需的服務時間不同，客戶到達銀行后，先到打號機上打號，號票上包括到達時間、編號和需要辦理的業(yè)務，然后在銀行內等候, 當任一服務窗口空閑時,處理等候客戶中排在最前面的客戶的業(yè)務。（要求按二進制位表示編碼）測試數(shù)據(jù)：英文文件。試為這樣的信息收發(fā)站編寫一個哈夫曼碼的編/譯碼系統(tǒng)。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳輸數(shù)據(jù)預先編碼；在接受端將傳來的數(shù)據(jù)進行譯碼。提高要求：（1）對于表達式中的簡單錯誤，能夠給出提示；（2）表達式中可以包括單個字母表示的變量。基本要求：從鍵盤輸入一個正確的中綴表達式，將中綴表達式轉換為對應的后綴表達式，計算后綴表達式的值。提高要求：設停車場有南、北兩個門，每個門都可以進、出車輛。測試數(shù)據(jù)：設輸入數(shù)據(jù)為：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。試為停車場編制按上述要求進行管理的模擬程序。8．停車場管理程序(**)問題描述：設停車場內只有一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。以08級某專業(yè)必修課與選修課為例，選擇12門課程及相應學分，制定一個表明各門課程先后約束關系的有向圖。教學計劃的表格格式自行設定, 可以從鍵盤讀取數(shù)據(jù)也可以從文件讀取數(shù)據(jù), 結果保存到文件中。試在這樣的前提下設計一個教學計劃編制程序。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。假設任何專業(yè)都有固定的學習年限，每學年含兩個學期，每學期的時間長度和學分上限值均相等。提高要求：顯示原始圖及選擇n1條管道后的圖。圖的信息輸入一次后, 保存到文件中, 選擇的n1條管道輸出到顯示器的同時, 也保存于文件中。6．管道鋪設施工的最佳方案（*）問題描述:需要在某個城市的n個小區(qū)鋪設管道，則在這n個小區(qū)之間鋪設n1條管道即可，假設任意兩個居民區(qū)之間都可以架設管道，但由于地理環(huán)境的不同，所需經費不同，選擇最優(yōu)的施工方案使總投資盡可能的少。測試數(shù)據(jù)：取某個單位電話號碼簿中的30個記錄。從鍵盤輸入各記錄，以用戶名為關鍵字建立哈希表，哈希函數(shù)用除留取余數(shù)法構造，采用線性探測法解決沖突。5．哈希表的設計與實現(xiàn)（*）問題描述：針對某個單位電話號碼簿，設計一個哈希表，并完成相應的建表和查表程序。程序的輸出結果是每個詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號，格式自行設計, 結果保存到文件中。試寫一個實現(xiàn)這一目標的文字統(tǒng)計系統(tǒng)，稱為“文學研究助手”。測試數(shù)據(jù)：分別選擇男生多于女生、女生多于男生、男女生相等的三組測試數(shù)據(jù) 提高要求：計算出任意一位男生(編號為X)和任意一位女生(編號為Y), 在第K曲配對跳舞的情況?；疽螅狠斎肽?、女學生的姓名、性別，由程序自動為男女生編號，可以順序編號，也可以隨機編號，輸出每曲配對情況（包括男、女生的姓名、性別和編號）。測試數(shù)據(jù)：可任意選取兩個一元多項式，可以是一般的多項式，也可以是稀疏多項式?；疽螅?1)輸入并建立多項式；(2)輸出多項式；(3)兩個多項式相加，輸出結果多項式；(4)兩個多項式相減，輸出結果多項式。(6)成績表保存在文件中, 可以從文件讀取數(shù)據(jù)?；卮饐栴}：平時考勤：核分標準：15分 15分 100分（90~100為優(yōu)、80~89為良、70~79為中、60~69為及格、60以下為不及格）五、參考書目嚴蔚敏.《數(shù)據(jù)結構》（C語言版）.清華大學出版社 劉玉龍．《數(shù)據(jù)結構與算法》.《數(shù)據(jù)結構題集》（C語言版）.清華大學出版社（C/C++描述）.北京:（使用C++語言描述）.南京:, 陶永雷, （用面向對象方法與C++描述）.北京:第四篇：數(shù)據(jù)結構與算法課程設計題目數(shù)據(jù)結構與算法課程設計題目1．成績管理問題描述：給出n個學生的考試成績表，成績表包括學生的學號、姓名、考試成績（高等數(shù)學、英語、物理），設計一個簡單的成績管理程序。通過功能的實現(xiàn)情況、界