【正文】 找長度；理解并掌握二叉排序樹，平衡二叉樹B樹的各種算法。數(shù)組和廣義表()實驗六 稀疏矩陣的應(yīng)用要求：理解多維數(shù)組的結(jié)構(gòu)特點和在內(nèi)存中的兩種順序存儲方式；理解并掌握矩陣和特殊矩陣元素在存儲區(qū)中地址的計算；領(lǐng)會稀疏矩陣的壓縮方式和簡單運算；了解廣義表的定義和基本運算。四、實驗教學(xué)內(nèi)容的基本要求及學(xué)時分配線性表(1學(xué)時)實驗一 順序表的應(yīng)用 實驗二 鏈表的應(yīng)用要求：理解線性表的定義及其運算；理解順序表和鏈表的定義，組織形式，結(jié)構(gòu)特征和類型說明；掌握在這兩種表上實現(xiàn)的插入，刪除和按值查找的算法；了解循環(huán)鏈表，雙(循環(huán))鏈表的結(jié)構(gòu)特點和在其上施加的插入，刪除等操作。知識點：排序、直接插入排序、折半插入排序、表插入排序、希爾排序、起泡排序、快速排序、簡單選擇排序、堆排序、2路歸并排序、基數(shù)排序、排序方法的綜合比較。排序方法有不同的分類方法，基于“關(guān)鍵字間的比較”進行排序的方法可以按排序過程所依據(jù)的不同原則分為插入排序、交換排序、選擇排序、歸并排序和計數(shù)排序等五類；(2)掌握各種排序方法的時間復(fù)雜度的分析方法。查找(6學(xué)時)學(xué)習(xí)目標：(1)理解“查找表”的結(jié)構(gòu)特點以及各種表示方法的適用性；(2)熟練掌握以順序表或有序表表示靜態(tài)查找表時的查找方法；(3)熟悉靜態(tài)查找樹的構(gòu)造方法和查找算法，理解靜態(tài)查找樹和折半查找的關(guān)系；(4)熟練掌握二叉查找樹的構(gòu)造和查找方法；(5)理解二叉平衡樹的構(gòu)造過程；(6)熟練掌握哈希表的構(gòu)造方法，深刻理解哈希表與其它結(jié)構(gòu)的表的實質(zhì)性的差別；(7)掌握描述查找過程的判定樹的構(gòu)造方法，以及按定義計算各種查找方法在等概率情況下查找成功時的平均查找長度。知識點：樹的類型定義、二叉樹的類型定義、二叉樹的存儲表示、二叉樹的遍歷以及其它操作的實現(xiàn)、線索二叉樹、樹和森林的存儲表示、樹和森林的遍歷以及其它操作的實現(xiàn)、最優(yōu)樹和赫夫曼編碼。重點和難點：本章重點是學(xué)習(xí)數(shù)組類型的定義及其存儲表示。重點和難點：相對于其它各個知識點而言，本章非整個課程的重點，鑒于串已是多數(shù)高級語言中已經(jīng)實現(xiàn)的數(shù)據(jù)類型，因此本章重點僅在于了解串類型定義中各基本操作的定義以及串的實現(xiàn)方法，并學(xué)會利用這些基本操作來實現(xiàn)串的其它操作。棧和隊列(4學(xué)時)學(xué)習(xí)目標：(1)掌握棧和隊列這兩種抽象數(shù)據(jù)類型的特點，并能在相應(yīng)的應(yīng)用問題中正確選用它們；(2)熟練掌握棧類型的兩種實現(xiàn)方法；(3)熟練掌握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法；(4)理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程。用前者表示的線性表簡稱為順序表，用后者表示的線性表簡稱為鏈表；(2)熟練掌握這兩類存儲結(jié)構(gòu)的描述方法以及線性表的基本操作在這兩種存儲結(jié)構(gòu)上的實現(xiàn)；(3)能夠從時間和空間復(fù)雜度的角度綜合比較線性表兩種存儲結(jié)構(gòu)的不同特點及其適用場合；(4)結(jié)合線性表類型的定義增強對抽象數(shù)據(jù)類型的理解。三、理論教學(xué)內(nèi)容的基本要求及學(xué)時分配序論(2學(xué)時)學(xué)習(xí)目標：熟悉各類文件的特點，構(gòu)造方法以及如何實現(xiàn)檢索，插入和刪除等操作。算法分析強調(diào)最基本的算法設(shè)計技術(shù)和分析方法。課程內(nèi)容由數(shù)據(jù)結(jié)構(gòu)和算法分析初步兩部分組成。內(nèi)容包括：數(shù)組、鏈接表、棧和隊列、串、樹與森林、圖、排序、查找、索引與散列結(jié)構(gòu)等。課程以結(jié)構(gòu)化程序設(shè)計語言C語言作為算法的描述工具，強化數(shù)據(jù)結(jié)構(gòu)基本知識和結(jié)構(gòu)化程序設(shè)計基本能力的雙基訓(xùn)練。數(shù)據(jù)結(jié)構(gòu)是針對處理大量非數(shù)值性程序問題而形成的一門學(xué)科，內(nèi)涵豐富、應(yīng)用范圍廣。要求學(xué)生從算法和數(shù)據(jù)結(jié)構(gòu)的相互依存關(guān)系中把握應(yīng)用算法設(shè)計的藝術(shù)和技能。重點與難點：本章無。重點與難點：鏈表是本章的重點和難點。重點與難點：棧和隊列是在程序設(shè)計中被廣泛使用的兩種線性數(shù)據(jù)結(jié)構(gòu)，因此本章的學(xué)習(xí)重點在于掌握這兩種結(jié)構(gòu)的特點，以便能在應(yīng)用問題中正確使用。本章的難點是理解實現(xiàn)串匹配的KMP算法的思想。知識點：數(shù)組的類型定義、數(shù)組的存儲表示、特殊矩陣的壓縮存儲表示方法、隨機稀疏矩陣的壓縮存儲表示方法。圖(8學(xué)時)學(xué)習(xí)目標：(1)領(lǐng)會圖的類型定義；(2)熟悉圖的各種存儲結(jié)構(gòu)及其構(gòu)造算法，了解各種存儲結(jié)構(gòu)的特點及其選用原則；(3)熟練掌握圖的兩種遍歷算法；(4)理解各種圖的應(yīng)用問題的算法。重點和難點：本章重點在于理解查找表的結(jié)構(gòu)特點及其各種表示方法的特點和適用場合。能從“關(guān)鍵字間的比較次數(shù)”分析排序算法的平均情況和最壞情況的時間性能。文件(4學(xué)時)學(xué)習(xí)目標：熟悉各類文件的特點，構(gòu)造方法以及如何實現(xiàn)檢索，插入和刪除等操作。棧()實驗三 棧的應(yīng)用要求：理解棧的定義，特征及在其上所定義的基本運算；掌握在兩種存儲結(jié)構(gòu)上對棧所施加的基本運算的實現(xiàn)。樹與二叉樹(4學(xué)時)實驗七 樹與二叉樹的應(yīng)用要求：理解樹的定義，術(shù)語；領(lǐng)會并掌握樹的各種存儲結(jié)構(gòu)；熟練掌握森林與二叉樹間的相互轉(zhuǎn)換；領(lǐng)會樹和森林的遍歷；了解樹的簡單應(yīng)用。排序(3學(xué)時)實驗十三 插入排序 實驗十四 選擇排序 實驗十五 排序綜合練習(xí)要求：領(lǐng)會排序的基本思想和基本概念；理解并掌握插入排序，冒泡排序，快速排序，直接選擇排序，堆排序，歸并排序和基數(shù)排序的基本思想，步驟，算法及時空效率分析；了解外排序的定義和基本方法。課內(nèi)學(xué)時安排說明：前8周每周4學(xué)時全為理論課，從第9周開始理論和上機為1：1，也即2學(xué)時理論，2學(xué)時上機訓(xùn)練。 Algorithms）一、基本信息課程編號：E1132107 課程類別：學(xué)科基礎(chǔ)課必修課 適用層次：本科適用專業(yè)：計算機科學(xué)與技術(shù)、網(wǎng)絡(luò)工程、軟件工程等 開課學(xué)期：3 學(xué) 分：2學(xué)分 學(xué) 時：2周 考核方式：考查二、教學(xué)目的數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計不僅是數(shù)據(jù)結(jié)構(gòu)與算法課程的實踐教學(xué)環(huán)節(jié)，而且是一門綜合性實驗項目。3．使學(xué)生初步具備查閱資料、分析設(shè)計、上機實現(xiàn)和書寫科技 報告的能力。、保量、保時間進度地提交規(guī)范的課程設(shè)計報告，審查由指導(dǎo)教師負責(zé)。：第13天，選定題目，明確題目要求、確定數(shù)據(jù)結(jié)構(gòu)、設(shè)計算法，并分析算法復(fù)雜度；第48天，編寫程序、調(diào)試程序、測試程序；第910天，撰寫設(shè)計報告，準備答辯（上機演示，回答教師提問）。對內(nèi)容有創(chuàng)新者，成績評定將適當提高）。六、教材與參考資料 ：[1] 數(shù)據(jù)結(jié)構(gòu)(C++)版，王紅梅、胡明、王濤編著，清華大學(xué)出版社， [2] 自編教材：[1] 許卓群，楊冬青，唐世渭， [2] 嚴蔚敏, , [3] (第一版).成都: 電子科技大學(xué)出版社, [4] Clifford ， [5] （用面向?qū)ο蠓椒ㄅcC++描述）.清華大學(xué)出版社， [6] Ford W., Topp STRUCTURES with C++.清華大學(xué)出版社（影印版），附錄一參考題目（可分若干組，每個學(xué)生選擇其中一個題目）1．商廈家電庫存管理 3．使用哈希表技術(shù)判斷兩個源程序的相似性 4．以隊列實現(xiàn)的仿真技術(shù)預(yù)測理發(fā)館的經(jīng)營狀況 6．用樹型結(jié)構(gòu)的搜索算法模擬因特網(wǎng)域名的查詢 7．管道鋪設(shè)施工的最佳方案選擇 8．表達式分析與求值程序 9．安排教學(xué)計劃 編碼器與解碼器 11．在國際象棋盤上馬遍歷問題 12．八皇后問題 13．民航售票系統(tǒng) 14．模擬旅館管理系統(tǒng)中的床位分配和加收 15．銀行業(yè)務(wù)活動的模擬16．文字統(tǒng)計系統(tǒng)—文字研究助手 17．修道士野人問題 18．考試問題19．計算機輔助考核系統(tǒng) 20．學(xué)籍管理系統(tǒng)注：學(xué)生可以自選題目或選擇指導(dǎo)老師擬定的題目。由于軟件的核心是算法，而算法實際上是對加工數(shù)據(jù)過程的描述，所以研究數(shù)據(jù)結(jié)構(gòu)對提高編程能力和設(shè)計高性能的算法是至關(guān)重要的。他們的含義大致為：了解是正確理解概念，掌握是學(xué)會所學(xué)知識，熟練掌握就是運用所學(xué)知識解決實際問題。鏈表插入、刪除運算的算法。另一方面，本課程的學(xué)習(xí)過程也是進行復(fù)雜程序設(shè)計的訓(xùn)練過程，要求學(xué)生會書寫符合軟件工程規(guī)范的文件，編寫的程序代碼應(yīng)結(jié)構(gòu)清晰、正確易讀，能上機調(diào)試并排除錯誤。二、教學(xué)內(nèi)容第一章 緒論（一）教學(xué)目的要求介紹數(shù)據(jù)結(jié)構(gòu)的一些基本概念，算法的時間復(fù)雜度和空間復(fù)雜度的分析方法，抽象數(shù)據(jù)類型的定義和使用以及算法的描述方法。算法時間復(fù)雜度和空間復(fù)雜度的分析。（四）教學(xué)時數(shù)4學(xué)時。教學(xué)重點：在順序表和鏈表上各種基本算法的實現(xiàn)及相關(guān)的時間性能分析。（四）教學(xué)時數(shù)8學(xué)時。教學(xué)重點：棧和隊列在兩種存儲結(jié)構(gòu)上實現(xiàn)的基本運算。第四章 串（一）教學(xué)目的與要求介紹串的基本概念和操作，串的存儲結(jié)構(gòu)以及基本操作的算法實現(xiàn)。教學(xué)難點：利用串的基本操作來實現(xiàn)串的其它操作。掌握數(shù)組的基本概念和基本操作的算法實現(xiàn)；掌握稀疏矩陣的定義和各種存儲結(jié)構(gòu)，掌握稀疏矩陣的轉(zhuǎn)置和相加的方法并了解其算法；掌握廣義表的定義、存儲結(jié)構(gòu)和求廣義表的長度及深度的算法，掌握建立廣義表和輸出廣義表的方法并了解其算法。第一節(jié) 第二節(jié)一、數(shù)組的存儲方式二、數(shù)組元素存儲位置的計算三、基本操作的實現(xiàn)第三節(jié)一、特殊矩陣二、稀疏矩陣第四節(jié)一、廣義表的基本概念二、廣義表的三個重要結(jié)論第五節(jié)一、頭尾鏈表存儲表示二、擴展線性鏈表存儲表示第六節(jié)廣義表的遞歸算法 廣義表的存儲表示 廣義表的定義 矩陣的壓縮存儲 數(shù)組類型 數(shù)組的順序表示和實現(xiàn)一、求廣義表的深度二、復(fù)制廣義表三、建立廣義表的存儲結(jié)構(gòu)