隨著計算機技術的飛速發展,計算機在各個學科和領域得到廣泛應用,而這些應用所面臨的首要問題就是對於信息量大、種類繁多、結構復雜的數據和數據關繫的處理,因此必須設計好數據結構和數據組織方式,以便有效地實現數據存儲、數據傳輸和數據處理等操作。數據結構主要研究數據的邏輯結構,數據在計算機中的存儲實現,以及處理不同結構數據的算法。我們研究數據結構的目的是編寫更高效的程序,而高效、簡捷的程序取決於數據結構和算法的設計。
“數據結構”是計算機程序設計的重要理論基礎,是計算機專業最為核心的一門專業基礎課程,也是非計算機專業的主要選修課程,同時還是一門考研課程。數據結構前承高級語言程序設計和離散數學,後接操作繫統、編譯原理、數據庫原理等專業課程,為研制開發各種繫統和應用軟件奠定理論和實踐基礎。該課程的學習效果不僅關繫到後續課程的學習,而且直接關繫到軟件設計水平的提高和專業素質的培養,在計算機學科教育中有非常重要的作用。
考慮到初學者普遍對算法設計問題感到比較困難且思路不明確,本書不僅注重基本概念的引入和闡述,更加注重算法的設計、分析與實現,強調實踐環節的重要性。本書具有如下特點。
(1)將C++語言作為數據結構的算法描述語言,讓數據結構與面向對像技術有機結合。在設置例題時,充分考慮應用型人纔培養的需求,更加側重於算法的程序實現。書中的算法講解都有風格優美而完整的C++代碼實現,並在Visual Studio 2010環境下編譯通過,這將有利於讀者掌握算法的程序實現及對算法進行分析與比較。
(2)按照“全國碩士研究生招生考試計算機科學與技術學科聯考計算機學科專業基礎綜合考試大綱”的要求編寫,基本涵蓋該考試大綱所有的知識點,並在重要知識點之後附加部分高校及全國統一考試真題作為自測題。讀者在完成相應問題的同時,既能鞏固知識點,又能有選擇地提高能力,還能有效地檢驗階段學習效果。
(3)繫統、全面地介紹各種傳統的數據結構,按照“線性結構、樹結構、圖結構、集合結構”四大模塊順序安排內容。部分章節還設有算法設計舉例,意在提高初學者的算法分析和設計的能力。
全書分為12章。
第1章介紹基礎知識,討論什麼是數據結構,給出數據結構和算法的相關概念與描述方法,介紹算法分析的基本方法。
線性結構包括第2~5章。第2章介紹線性表的有關概念及其基本操作,是後續章節的基礎。第3章在第2章的基礎上討論操作受限的線性表——棧與隊列。第4章討素為字符的特殊的線性表——串。第5章介紹程序設計中常用的數據類型——數組。
樹結構包括第6、7章。第6章介紹樹和二叉樹的有關概念及基本操作。第7章討論樹和二叉樹的應用。
圖結構包括第8、9章。第8章介紹圖的基本概念、存儲結構及遍歷運算。第9章討論圖的應用。
集合結構包括第10~12章。第10章以集合作為數據模型,討論查找的方法和技術,包括靜態查找表和動態查找表。第11章介紹一種專用於集合的存儲和檢索的數據結構——散列表。第12章介紹一些常用的排序算法,包括內部排序和外部排序。
本書由教學一線的教師主筆,結合作者多年的教學經驗和教學素材,針對數據結構這門課程的特點撰寫而成,目的是使學生在扎實的編程能力基礎上,掌握如何合理地組織數據、有效地存儲和處理數據,並學會在時間復雜度和空間復雜度之間進行平衡與取舍。本書滿足多樣化的人纔培養模式的需求,既可作為普通高等院校計算機及相關專業的數據結構課程教材,也可作為考研參考書,還可作為工程技術人員的工具書。在本書目錄中加“*”的章節可以酌情處理。
在本書的編寫和出版過程中得到電子工業出版社冉哲編輯和《算法與數據結構考研試題精析》的編者陳守孔教授的諸多幫助,得到吉林大學珠海學院領導的大力支持,在此深表感謝。
由於作者水平所限,加上計算機學科的發展十分迅速,書中難免有不妥之處,懇請讀者批評指正。
作者