數(shù)據(jù)結構

前言

“數(shù)據(jù)結構”是計算機專業(yè)非常重要的一門主課，是計算機程序設計的理論基礎。學好“數(shù)據(jù)結構”課，將為后續(xù)的“數(shù)據(jù)庫原理”、“操作系統(tǒng)”、“編譯原理”等專業(yè)課程打下良好的專業(yè)知識基礎，為程序設計人員提供良好的技能訓練。  本書共分8章。我們根據(jù)多年從事高職高?！皵?shù)據(jù)結構”課程教學工作的經驗，我們在教材內容的組織上力求做到“以應用為主體”，對相對較為抽象的概念和一部分難度較大又不常用的數(shù)據(jù)結構相關知識進行了刪減，強調基礎理論知識的理解和應用，突出對高職高專類學生應用能力和實際動手能力的培養(yǎng)。本教材有以下幾個特點：1.本教材內容豐富，條理清晰，算法簡潔，便于學生理解和掌握。2.每章起始均有本章要點和本章難點，使學生在每章學習的起始階段對該章內容有個基本認識。3.理論知識的介紹由淺入深，通俗易懂，內容組織以應用為教學目標，略去了一部分理論推導和數(shù)學證明，對算法的設計分析和時空分析沒有提出過高的要求。4.書中所有的算法實現(xiàn)均用c語言編寫，并可直接調試運行，使學生便于上機驗證各個算法的實現(xiàn)。本書由宋宏圖任主編，盧敏和吳林華擔任副主編，陳千、陳樹祥、劉魯楣、范淵、張定俊、董淑華、潘修強參加了編寫工作。由于作者水平有限，書中不足與錯誤之處在所難免，敬請讀者和專家批評指正。

內容概要

《數(shù)據(jù)結構》可作為高職高專計算機專業(yè)學生學習“數(shù)據(jù)結構”課程的選用教材，也可以作為大學非計算機類專業(yè)學生的選修課教材和計算機應用技術從業(yè)人員的參考書?！皵?shù)據(jù)結構”是計算機專業(yè)的核心課程，《數(shù)據(jù)結構》對數(shù)據(jù)結構的有關知識作了系統(tǒng)全面的介紹，在內容組織上力求概念清晰，注重數(shù)據(jù)結構的實際應用。主要內容包括：數(shù)據(jù)結構基本概念、線性表、棧和隊列、樹、圖、排序和查找。各章節(jié)給出的算法均用C語言編寫，并可順利地在計算機上調試運行，以便于讀者理解。

書籍目錄

第1章 緒論1.1 數(shù)據(jù)結構的基本概念和術語1.1.1 引言1.1.2 數(shù)據(jù)結構的有關概念和術語1.1.3 數(shù)據(jù)結構的分類1.1.4 數(shù)據(jù)結構和抽象數(shù)據(jù)類型1.2 算法分析1.2.1 算法的定義和要求1.2.2 算法分析技術基礎知識習題第2章 線性表2.1 線性表的定義2.2 線性表的基本操作2.3 線性表的順序存儲結構2.3.1 線性表的順序存儲結構2.3.2 順序表上基本運算的實現(xiàn)2.4 線性表的鏈式存儲結構2.4.1 單鏈表上的基本運算2.4.2 循環(huán)鏈表2.4.3 雙向鏈表2.5 順序表和鏈表的比較2.6 應用舉例習題第3章 棧和隊列3.1 棧3.1.1 棧的定義和基本操作3.1.2 棧的順序存儲結構3.1.3 棧的鏈式存儲結構3.2 隊列3.2.1 隊列的定義和基本操作3.2.2 隊列的順序存儲結構3.2.3 隊列的鏈式存儲結構3.3 應用舉例習題第4章 其他線性數(shù)據(jù)結構4.1 串4.1.1 串的定義和基本操作4.1.2 串的存儲結構4.1.3 串的操作實現(xiàn)4.1.4 串的應用——文本編輯基本原理4.2 數(shù)組4.2.1 數(shù)組的概念4.2.2 數(shù)組的順序表示4.2.3 特殊矩陣的壓縮存儲4.3 稀疏矩陣4.3.1 稀疏矩陣的壓縮存儲4.3.2 稀疏矩陣的運算4.3.3 應用舉例——稀疏矩陣運算器習題第5章 樹5.1 樹的定義和基本操作5.1.1 樹的定義5.1.2 樹的表示方法5.1.3 樹的基本操作5.2 二叉樹5.2.1 二叉樹的定義和基本操作5.2.2 二叉樹的性質5.2.3 二叉樹的存儲結構5.2.4 遍歷二叉樹5.3 樹和森林5.3.1 樹的存儲結構5.3.2 樹、森林與二叉樹的轉換5.3.3 樹和森林的遍歷5.4 樹的應用5.4.1 二叉排序樹5.4.2 哈夫曼樹及其應用習題第6章 圖6.1 圖的基本概念和術語6.2 圖的存儲結構6.2.1 鄰接矩陣表示法6.2.2 鄰接鏈表表示法6.3 圖的遍歷和求圖的連通分量6.3.1 深度優(yōu)先搜索遍歷6.3.2 廣度優(yōu)先搜索遍歷6.3.3 求圖的連通分量6.4 圖的應用6.4.1 生成樹和最小生成樹6.4.2 拓撲排序6.4.3 最短路徑習題第7章 查找7.1 基本概念7.2 靜態(tài)查找表7.2.1 順序表上順序查找7.2.2 有序表查找7.2.3 索引順序表查找7.3 動態(tài)查找表7.3.1 二叉樹排序樹的生成和插入7.3.2 二叉排序樹上的查找7.3.3 二叉排序樹的刪除7.4 散列表7.4.1 散列表與散列函數(shù)7.4.2 散列函數(shù)的構造7.4.3 解決沖突的主要方法7.4.4 散列表的查找及分析7.5 應用舉例及分析習題第8章 內部排序8.1 基本概念8.2 插入排序8.2.1 直接插入排序8.2.2 折半插入排序8.2.3 希爾排序8.3 交換排序8.3.1 冒泡排序8.3.2 快速排序8.4 選擇排序8.5 歸并排序8.6 基數(shù)排序8.7 各種內部排序方法的比較習題主要參考文獻

章節(jié)摘錄

插圖：在本章中介紹了線性表的邏輯結構及其兩種存儲結構：順序表和鏈表。通過討論可知它們各有優(yōu)缺點，順序存儲有三個優(yōu)點：（1）方法簡單，各種高級語言中都有數(shù)組，容易實現(xiàn)。（2）不用為表示結點間的邏輯關系而增加額外的存儲開銷。（3）順序表具有按元素序號隨機訪問的特點。但它也有兩個缺點：（1）在順序表中作插入刪除操作時，平均移動表中一半的元素，因此對較大的順序表效率低。（2）需要預先分配足夠大的存儲空間，若分配的空間過大，可能會導致順序表后部大量閑置；若預先分配過小，又會造成溢出。鏈表的優(yōu)缺點恰好與順序表相反。在實際選取存儲結構時通常要考慮以下幾點：（1）基于存儲的考慮。順序表的存儲空間是靜態(tài)分配的，在程序執(zhí)行之前必須明確規(guī)定它的存儲規(guī)模，也就是說，事先對“MAXSIZE”要有合適的設定，過大造成浪費，過小造成溢出?？梢妼€性表的長度或存儲規(guī)模難以估計時，不宜采用順序表；鏈表不用事先估計存儲規(guī)模，但鏈表的存儲密度較低，存儲密度是指一個結點中數(shù)據(jù)元素所占的存儲單元和整個結點所占的存儲單元之比。顯然鏈式存儲結構的存儲密度是小于l的。（2）基于運算的考慮。在順序表中按序號訪問的時間性能是O（1），而鏈表中按序號訪問的時間性能是O（n），所以如果經常作的運算是按序號訪問數(shù)據(jù)元素，顯然順序表優(yōu)于鏈表；而在順序表中作插入、刪除時，需平均移動表中一半的元素，在鏈表中作插入、刪除，雖然也要找插入位置，但操作主要是比較操作，從這個角度考慮顯然后者優(yōu)于前者。（3）基于環(huán)境的考慮。順序表容易實現(xiàn)，任何高級語言中都有數(shù)組類型，鏈表的操作是基于指針的，相對來講前者簡單些，這也是用戶考慮的一個因素?？傊?，兩種存儲結構各有長短，選擇哪一種由實際問題中的主要因素決定。通?！拜^穩(wěn)定”的線性表選擇順序存儲，而頻繁作插入、刪除的即動態(tài)性較強的線性表宜選擇鏈式存儲。

編輯推薦

《數(shù)據(jù)結構》由宋宏圖任主編，盧敏和吳林華擔任副主編，陳千、陳樹祥、劉魯楣、范淵、張定俊、董淑華、潘修強參加了編寫工作。

圖書封面

評論、評分、閱讀與下載

---

    數(shù)據(jù)結構 PDF格式下載

---