《數(shù)據(jù)結(jié)構(gòu)》學(xué)習(xí)指南《數(shù)據(jù)結(jié)構(gòu)》是計算機(jī)學(xué)科的主干課，編譯原理、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)等多個專業(yè)課的重要基礎(chǔ)課程，同時也是計算機(jī)程序設(shè)計與開發(fā)所需的必備知識。學(xué)習(xí)本課程要注意數(shù)據(jù)結(jié)構(gòu)與算法緊密結(jié)合，對典型算法掌握其時間復(fù)雜性的分析過程，學(xué)會基本的算法正確性證明方法。教材中每章附帶的習(xí)題和習(xí)題集中的習(xí)題可根據(jù)推薦的難度等級由淺入深、獨(dú)立思考逐步完成。如遇到較難習(xí)題，要逐級參考分級啟發(fā)式提示并結(jié)合自己的思路嘗試解決。在學(xué)習(xí)過程中，通過ADL語言描述快速理解并掌握算法的設(shè)計思想，再結(jié)合上機(jī)實驗和課程設(shè)計等實踐環(huán)節(jié)利用C++語言進(jìn)行驗證實驗、設(shè)計實驗以及綜合運(yùn)用所學(xué)知識進(jìn)行綜合實驗和創(chuàng)新實驗，在理論和實踐相結(jié)合的過程中不斷鞏固和加深對數(shù)據(jù)結(jié)構(gòu)知識的理解，并提高編程能力，更好的完成本課程的學(xué)習(xí)。本課程主要包括緒論，線性表、樹、圖等基本數(shù)據(jù)結(jié)構(gòu)，遞歸、排序、查找等基本算法，內(nèi)存管理，文件等五部分。下面針對每一部分內(nèi)容總結(jié)主要知識點(diǎn)并給出一些學(xué)習(xí)建議，并列出部分參考書目，以期能夠幫助學(xué)生更好地完成本門課程的學(xué)習(xí)：緒論（第一章）知識點(diǎn)：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)等概念和術(shù)語的含義；數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)；ADL書寫算法的規(guī)范；算法的定義及其特性；評估算法的基本準(zhǔn)則；算法時間復(fù)雜性的分析方法；時間與空間分析。學(xué)習(xí)指南：本部分知識以知道和理解為主，需要理解什么是數(shù)據(jù)結(jié)構(gòu)，特別是數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)運(yùn)算的含義及其相互關(guān)系，理解并熟悉ADL語言。熟練掌握算法的時間復(fù)雜度和空間復(fù)雜度，最好、最壞和平均時間復(fù)雜度等概念，這些概念在后續(xù)章節(jié)里會頻繁使用和出現(xiàn)。掌握算法描述和算法分析的基本方法、對典型算法要能分析出時間復(fù)雜度?；緮?shù)據(jù)結(jié)構(gòu)（第二、三、四、五章）知識點(diǎn)：線性表、樹、圖三種數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)；上述數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)；上述數(shù)據(jù)結(jié)構(gòu)上的主要算法；上述數(shù)據(jù)結(jié)構(gòu)的典型應(yīng)用；上述數(shù)據(jù)結(jié)構(gòu)的數(shù)學(xué)性質(zhì)；學(xué)習(xí)指南：本部分是《數(shù)據(jù)結(jié)構(gòu)》課程的重點(diǎn)內(nèi)容之一，需要熟練掌握。上述知識點(diǎn)僅從宏觀上概括了這一部分的內(nèi)容，以使學(xué)生能夠總體了解這一部分的知識分布。具體知識點(diǎn)可參考以下表格自行歸納，例如：線性表、樹、圖都有各自的遍歷算法，圖有拓?fù)渑判蛩惴?；?gòu)造哈夫曼樹是樹的應(yīng)用，堆棧和隊列以及數(shù)組、字符串都是線性表的應(yīng)用；在總結(jié)和分類這些知識點(diǎn)的過程中，歸納分析不同數(shù)據(jù)結(jié)構(gòu)間的區(qū)別和聯(lián)系有助于更好地掌握這一部分知識。線性表樹圖邏輯結(jié)構(gòu)存儲結(jié)構(gòu)算法應(yīng)用特性遞歸、排序、查找算法（第六、七、八章）知識點(diǎn)：遞歸算法的基本設(shè)計思想，算法執(zhí)行原理；幾類典型的排序算法的主要思想；插入排序、交換排序、選擇排序、合并排序各包含哪些典型算法；上述算法的時間復(fù)雜性和空間復(fù)雜性分析和對比；幾類典型的查找算法的主要思想；線性表查找、外查找、散列查找的典型算法；上述算法的時間復(fù)雜性和空間復(fù)雜性分析和對比；學(xué)習(xí)指南：遞歸算法在大部分章節(jié)的算法中都會使用到，需要重點(diǎn)理解遞歸算法的設(shè)計，以及遞歸與堆棧的關(guān)系，了解遞歸到非遞歸的轉(zhuǎn)換方法以及遞歸典型應(yīng)用。排序和查找是《數(shù)據(jù)結(jié)構(gòu)》課程中最中要的兩類算法，要熟練掌握。清楚掌握各個排序算法要其所屬排序類別，各個類別的排序思想。以及算法特點(diǎn)，如時間復(fù)雜性、空間復(fù)雜性、穩(wěn)定性等。學(xué)習(xí)過程中可嘗試自行完成下面的表格，更加系統(tǒng)的掌握排序算法。掌握不同類型的查找算法之間的區(qū)別和聯(lián)系、查找效率。在上機(jī)實踐中驗證并比較各個算法，并嘗試優(yōu)化算法。排序方法最好時間平均時間最壞時間輔助空間穩(wěn)定性直接插入O(n)O(n2)O(n2)O(1)穩(wěn)定直接選擇冒泡快速……內(nèi)存管理（第九章）知識點(diǎn)：均勻大小記錄內(nèi)存分配算法；均勻大小記錄內(nèi)存回收算法；不同大小記錄內(nèi)存分配算法；不同大小記錄內(nèi)存回收算法；伙伴系統(tǒng)的原理及相應(yīng)算法。學(xué)習(xí)指南：內(nèi)存管理的目的是為有效利用計算機(jī)內(nèi)存中的可用資源，學(xué)習(xí)過程中對比均勻大小和不同大小記錄的內(nèi)存管理方法的區(qū)別和聯(lián)系。在編程實踐過程中，注意理解內(nèi)存管理算法的同時注意鞏固和回憶線性表部分所學(xué)知識。文件（第十章）文件的定義、分類等基本概念；文件的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)；文件的四種存儲結(jié)構(gòu)：順序結(jié)構(gòu)，索引結(jié)構(gòu)，散列結(jié)構(gòu)和鏈結(jié)構(gòu)；四種存儲結(jié)構(gòu)的特點(diǎn)及相應(yīng)操作；學(xué)習(xí)指南：文件是是指存儲在外存中的、由大量性質(zhì)相同的記錄組成的集合，學(xué)習(xí)本章內(nèi)容要注意對比順序文件、雜湊文件、索引文件和多關(guān)鍵字文件這四種存儲結(jié)構(gòu)的特點(diǎn)，掌握不同存儲結(jié)構(gòu)上操作算法的區(qū)別。隨機(jī)數(shù)（第十一章）生成符合某概率分布的隨機(jī)數(shù)的算法；隨機(jī)數(shù)檢驗方法；隨機(jī)排列與隨機(jī)組合他的算法；隨機(jī)數(shù)的應(yīng)用；學(xué)習(xí)指南：本章的主要內(nèi)容是隨機(jī)數(shù)的產(chǎn)生和檢驗方法，要熟悉線性同余法等基本的隨機(jī)數(shù)產(chǎn)生算法的原理。了解衡量隨機(jī)序列的隨機(jī)數(shù)檢驗方法，如2檢驗、KS檢驗、等分布檢驗、序列檢驗、間隔檢驗的經(jīng)驗檢驗方法，初步了解和驗證隨機(jī)數(shù)的應(yīng)用。參考書：[1] WilliamFord,WilliamTopp,DataStructureswithC++.（中文譯名：數(shù)據(jù)結(jié)構(gòu)（C++語言描述））,Prentice-HallInternational,Inc.（影印本由清華大學(xué)出版社出版），1996.[2] MarkAllenWeiss,(FloridaInternationalUniversity),Algorithms,DataStructures,andProblemSolvingwithC++,Addison-WesleyPublishingCompany,Inc.,1996.[3] 管紀(jì)文，劉大有，《數(shù)據(jù)結(jié)構(gòu)》，高等教育出版社，1985.[4] 許卓群，張乃孝，楊冬青，唐世渭，《數(shù)據(jù)結(jié)構(gòu)》，高等教育出版社，1987.[5] 劉大有，李岳峰，《數(shù)據(jù)結(jié)構(gòu)原理》，吉林大學(xué)出版社，1994.[6] 嚴(yán)蔚敏，吳偉民，《數(shù)據(jù)結(jié)構(gòu)》（C語言版），清華大學(xué)出版社，1997.[7] 張乃孝，裘宗燕，《數(shù)據(jù)結(jié)構(gòu)－C++與面相對象的途徑》，高等教育出版社，1998.[8] 殷人昆，陶永