一、前言1.1、什么是數(shù)據(jù)結(jié)構(gòu)？N. Wirth早在20世紀(jì)70年代就指出“程序=數(shù)據(jù)結(jié)構(gòu)+算法”。數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)在計算機(jī)中存儲、組織、傳遞和轉(zhuǎn)換的過程以及方法，這些也是構(gòu)成與支撐算法的基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)主要討論數(shù)據(jù)的邏輯結(jié)構(gòu)、在計算機(jī)中的存儲結(jié)構(gòu)以及對其進(jìn)行的各種處理運算的方法和算法。 1.2、為什么要學(xué)數(shù)據(jù)結(jié)構(gòu)？如何有效地組織數(shù)據(jù)和處理數(shù)據(jù)是軟件設(shè)計的基本內(nèi)容，直接關(guān)系軟件的運行效率和工程化程度。數(shù)據(jù)結(jié)構(gòu)是軟件設(shè)計的重要理論和實踐基礎(chǔ)。 早期計算機(jī)處理的對象多為簡單的數(shù)值數(shù)據(jù)，而現(xiàn)在，隨著計算機(jī)和信息技術(shù)的飛速發(fā)展，計算機(jī)應(yīng)用遠(yuǎn)遠(yuǎn)超出了單純進(jìn)行數(shù)值計算的范疇。處理非數(shù)值計算性問題占用了90%以上的機(jī)器時間，設(shè)計了更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)元素間的互相關(guān)系。 主要有以下3個步驟：
二、基本概念2.1、數(shù)據(jù)數(shù)據(jù)是信息的載體，是計算機(jī)程序處理對象的集合，也是計算機(jī)處理信息的某種特定符號化表示形式，除了整數(shù)、實數(shù)等數(shù)值數(shù)據(jù)外，還包括字符串等非數(shù)值數(shù)據(jù)以及圖形、圖像、音頻和視頻等媒體數(shù)據(jù)。
2.2、數(shù)據(jù)項數(shù)據(jù)項是具有獨立含義、數(shù)據(jù)不可分割的最小標(biāo)識單位，是數(shù)據(jù)元素的組成部分，也可稱之為字段和域。 下面是小說類書籍，其中“書名”和“出版社”就是數(shù)據(jù)項（字段或域）。
2.3、數(shù)據(jù)元素數(shù)據(jù)元素是數(shù)據(jù)的基本單位，又可稱之為元素、節(jié)點，是一個數(shù)據(jù)整體中可以表示和訪問的數(shù)據(jù)單元。 "小說類書籍"就是數(shù)據(jù)元素，是數(shù)據(jù)項的集合。 2.4、數(shù)據(jù)對象數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，也叫數(shù)據(jù)元素類。 比如生活類書籍、科技類書籍、小說類書籍，每一種類型的書籍的總和都是性質(zhì)相同的數(shù)據(jù)元素的集合（數(shù)據(jù)對象）。 三、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是相互之間存在著一種或者多種關(guān)系的數(shù)據(jù)元素的集合，數(shù)據(jù)結(jié)構(gòu)概念包含3個方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的操作。 3.1、邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間存在的邏輯關(guān)系。數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)，獨立于計算機(jī)，是從具體問題抽象出來的數(shù)學(xué)模型。 集合集合中數(shù)據(jù)元素的關(guān)系極為松散，關(guān)系為“屬于同一個集合”。 比如下圖中有三個數(shù)據(jù)元素：databseTheory（數(shù)據(jù)庫原理）、databaseStructure（數(shù)據(jù)結(jié)構(gòu)）和wxApplets（微信小程序開發(fā)），它們的性質(zhì)都是教育類的書籍，而它們之間的關(guān)系極為松散，因此屬于集合類型的邏輯結(jié)構(gòu)。
線性結(jié)構(gòu)線性結(jié)構(gòu)是數(shù)據(jù)元素中具有線性關(guān)系的數(shù)據(jù)結(jié)構(gòu)，線性結(jié)構(gòu)中的節(jié)點存在“一對一”的關(guān)系。開始節(jié)點和終端節(jié)點都是唯一的，除開始和終端結(jié)點外，每個節(jié)點有且僅有一個前驅(qū)節(jié)點和一個后繼節(jié)點。 比如下圖的字母表，a是開始節(jié)點，e是終端節(jié)點，而a與e兩個節(jié)點之間都有一個前驅(qū)節(jié)點和后驅(qū)節(jié)點。對于c節(jié)點來說，b是c的前驅(qū)節(jié)點，d是c的后驅(qū)節(jié)點。并且，b與c是一對一的關(guān)系，d與c也是一對一的關(guān)系。
樹形結(jié)構(gòu)樹形結(jié)構(gòu)是數(shù)據(jù)元素之間具有層次關(guān)系的一種非線性結(jié)構(gòu)，樹形結(jié)構(gòu)中的節(jié)點存在“一對多”的關(guān)系。除根節(jié)點外，每個節(jié)點有且僅有一個前驅(qū)節(jié)點，所有節(jié)點可以有零個或多個后驅(qū)節(jié)點。 比如下圖的文件系統(tǒng)的組織方式，C盤是該結(jié)構(gòu)的根節(jié)點，有且僅有一個根節(jié)點。文件夾1有3個后驅(qū)節(jié)點，而文件夾3沒有后驅(qū)節(jié)點。
圖形結(jié)構(gòu)圖形結(jié)構(gòu)是一種非線性結(jié)構(gòu)，圖形結(jié)構(gòu)中的節(jié)點存在“多對多”的關(guān)系，所有的節(jié)點都可以有多個前驅(qū)結(jié)點和后驅(qū)節(jié)點。
數(shù)據(jù)的邏輯結(jié)構(gòu)涉及兩個方面的內(nèi)容，一是數(shù)據(jù)元素，二是數(shù)據(jù)元素之間的邏輯關(guān)系。 以二元組來定義數(shù)據(jù)的邏輯結(jié)構(gòu)：logica structure = (D, R)，D表示數(shù)據(jù)元素，R表示數(shù)據(jù)元素之間的關(guān)系 比如D={1,2,3,4,5,6,7}，R={[1,2], [1,3], [3,4], [2,5], [3,6], [2,7]} 用圖來表示數(shù)據(jù)元素之間的邏輯關(guān)系：
1是2的前驅(qū)元素，2是1的后繼(驅(qū))元素。 3.2、存儲結(jié)構(gòu)邏輯結(jié)構(gòu)在計算機(jī)中的存儲表示或?qū)崿F(xiàn)叫數(shù)據(jù)的存儲結(jié)構(gòu)，也叫物理結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系角度觀察數(shù)據(jù)，與數(shù)據(jù)的存儲無關(guān)系，是獨立于計算機(jī)的；而數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)在計算機(jī)中的實現(xiàn)，依賴于計算機(jī)。 例子一：所有年級的所有班如何用表示班與班之間的關(guān)系，如：一年級一班、一年級二班、一年級三班屬于一年級；二年級一班、二年級二班屬于二年級。這是以邏輯層面（角度）去觀察數(shù)據(jù)元素之間的關(guān)系。 例子二：分別設(shè)計班級表和學(xué)生表，兩張表的邏輯結(jié)構(gòu)是學(xué)生表屬于班級表。數(shù)據(jù)存儲在各自的表中就是存儲結(jié)構(gòu)。 順序存儲結(jié)構(gòu)物理位置相鄰的元素在邏輯上也相鄰，每個元素（數(shù)據(jù)元素）與其前驅(qū)元素和后繼元素的存儲位置相鄰，數(shù)組就是順序存儲結(jié)構(gòu)。
鏈?zhǔn)酱鎯Y(jié)構(gòu)索引存儲結(jié)構(gòu)散列存儲結(jié)構(gòu)3.3、數(shù)據(jù)操作數(shù)據(jù)操作是指對數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素進(jìn)行運算或處理，每種邏輯結(jié)構(gòu)都需要一組對其數(shù)據(jù)元素進(jìn)行處理一實現(xiàn)特定功能的操作，如插入、刪除、更新等。數(shù)據(jù)操作的實現(xiàn)依賴于數(shù)據(jù)的存儲結(jié)構(gòu)。 |
|
|
