《數據結構》是針對應用型本科教學特征和需求而編寫的,書中系統(tǒng)地介紹了常見數據結構和算法的相關理論和實現方法,主要包括線性表、棧、隊列、串、數組和廣義表、樹和二叉樹、圖等邏輯結構及其對應的存儲結構和操作。另外,該書還集中介紹了常見的排序和查找算法,并對算法的效率進行了分析。
《數據結構》以C語言為算法實現語言,以理論講解為基石,以案例講解為驅動,每個章節(jié)配備思考題和章后習題(包括理論習題和上機操作習題)。該書致力于將理論和實踐相結合,由淺入深地實現理論和實踐內容的逐級內化。
《數據結構》可作為應用型高等院校計算機科學與技術、軟件工程、數據科學與大數據技術、信息安全等相關專業(yè)的本科生專業(yè)教材或參考用書,也可作為計算機相關從業(yè)技術人員的自學和參考用書。
更多科學出版社服務,請掃碼獲取。
“數據結構”是計算機科學與技術學科中一門十分重要的專業(yè)基礎課程,也是其他工科的重要選修課之一。2022年發(fā)布的《計算機類教學質量國家標準》中將“數據結構”課程列為計算機科學與技術專業(yè)、軟件工程專業(yè)、網絡工程專業(yè)、信息安全專業(yè)、物聯網工程等5個學科的基礎課之一。另外,數據科學與大數據、人工智能等專業(yè)都要求學生具備較好的算法和數據結構相關基礎知識。
編者結合本科的教學要求和省屬學校學生的學習特點,注重理論和實踐相結合。本書中將知識內容、實踐內容有機融合,體現了程序設計方法中抽象、枚舉、歸納3個原則的運用,反復再現算法的復雜性、效率、折中、重用等重要概念。
本書在內容的選取上體現了突出應用的原則——針對應用型本科課程“教與學”的特點,在實例列舉上力求做到典型和恰當,并在各章都附有相應的習題(包括理論習題和上機操作習題);以實例介紹各種數據結構的應用。
在內容的組織上遵循“循序漸進”的原則——從數據類型、線性表、棧、隊列開講數據結構,與前導課程“高級語言程序設計”內容前后貫通,無縫銜接;內容由淺入深,按常用數據結構、簡單數據結構、樹與二叉樹、圖與網、查找和排序的次序安排主要教學內容。
在內容的敘述上符合“通俗易懂”的原則,在算法的描述上力求結構清晰、描述正確、易讀易理解,并對每一個算法都做了大量的注釋。在文字敘述上力求做到由淺入深和深入淺出,用語大眾化,增強可讀性。
全書共10章。第1章介紹數據結構和算法的基本概念,以及算法的評價方法;第2章介紹線性表的邏輯結構、存儲結構、基本操作,以及基本操作的時空復雜度分析;第3章深入淺出地介紹棧的定義、順序棧、鏈棧,以及棧的應用;第4章介紹隊列的基本概念、順序存儲結構、鏈式存儲結構,以及隊列的應用;第5章介紹串的定義、存儲結構及其操作;第6章分別介紹了一維數組、二維數組、多維數組,特殊矩陣的存儲方法,以及廣義表的定義、抽象結構及存儲結構;第7章介紹樹和二叉樹,主要包括樹和二叉樹的定義、遍歷方法、基本應用;第8章介紹圖,包括圖的基本概念、圖的存儲、圖的遍歷,以及圖的應用,并介紹相關的性能分析;第9章和第10章介紹查找和排序,并對其性能進行分析和對比。
全書側重應用性,力求教學內容與應用實際緊密結合;強調實踐性,建議讀者多動手,通過實際編程實現各種算法,并在深入分析的基礎上改進算法或提出新的算法,強調習題和上機實驗題的重要性。
本書由逯洋擔任主編,具體編寫分工如下:逯洋負責本書整體的章節(jié)設計,并編寫了第2~4章;孫宏宇編寫了第5~8章;王曉宇編寫了第9章和第10章;魯錚編寫了第1章;李穎和李闖負責全書的文字校對工作。
編者在編寫本書時,查閱和參考了眾多文獻資料,從中得到了許多教益和啟發(fā),在此向參考文獻的作者致以誠摯的謝意。
由于時間倉促和編者水平有限,書中難免有不妥和疏漏之處,敬請讀者批評指正。
第1章 數據結構和算法
1.1 數據結構的基本概念
1.2 抽象數據類型的表示與實現
1.2.1 抽象、數據抽象和過程抽象
1.2.2 封裝與信息隱蔽
1,2.3 數據類型和抽象數據類型
1.2.4 數據結構和抽象數據類型
1.3 算法
1.3.1 算法的概念
1.3 ,2算法的基本特性
1.4 算法的設計與評價
1.4.1 評價算法的標準
1.4.2 常見的算法設計方法
小結
習題
第2章 線性表
2.1 線性表的基本概念
2.1.1 線性表的定義
2.1.2 線性表的邏輯結構
2.1.3 線性表的基本運算
2.2 線性表的順序表示與實現
2.2.1 線性表的順序存儲結構
2.2.2 順序表的實現
2.2.3 順序表基本運算的實現
2.2.4 順序表的算法分析
2.3 線性表的鏈式表示與實現
2.3.1 線性表的鏈式存儲結構(鏈表)
2.3.2 鏈表的實現
2.3.3 鏈表基本運算的實現
2.3.4 鏈表的算法分析
2.4 單循環(huán)鏈表和雙鏈表
2.4.1 單循環(huán)鏈表
2.4.2 雙鏈表
2.4.3 順序表和鏈表的比較
2.5 線性表的應用
2.5.1 順序表的應用
2.5.2 鏈表的應用
小結
習題
第3章 棧
3.1 基本概念
3.1.1 棧的概念
3.1.2 棧的基本運算
3.2 棧的順序存儲結構
3.2.1 順序棧
3.2.2 順序棧的基本操作
3.3 棧的鏈式存儲結構
3.3.1 鏈棧的實現
3.3.2 鏈棧的基本操作
3.4 棧的應用
3.4.1 數制轉換
3.4.2 括號匹配
3.4.3 “迷宮”游戲
小結
習題
第4章 隊列
4.1 隊列的基本概念和基本運算
4.1.1 隊列的基本概念
4.1.2 隊列的基本運算
4.2 隊列的順序存儲結構
4.2.1 隊列的順序表示
4.2.2 順序隊列的基本運算
4.2.3 循環(huán)隊列
4.2.4 循環(huán)隊列的基本運算
……
第5章 串
第6章 數組和廣義表
第7章 樹和二叉樹
第8章 圖
第9章 查找
第10章 排序
參考文獻