書(shū)本是來(lái)自 程杰 老師的《大話數(shù)據(jù)結(jié)構(gòu)》，老師在書(shū)中自稱(chēng) 封清揚(yáng)

第一章 數(shù)據(jù)結(jié)構(gòu)緒論

1.3 數(shù)據(jù)結(jié)構(gòu)起源

??數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中的操作對(duì)象，一級(jí)它們之間的關(guān)系和操作等相關(guān)問(wèn)題的學(xué)科。

??1968年高德納《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》第一卷《基本算法》中，比較系統(tǒng)地闡述了數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及其操作，開(kāi)創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的課程體系。同年，數(shù)據(jù)結(jié)構(gòu)作為一門(mén)獨(dú)立的課程，在計(jì)算機(jī)科學(xué)的學(xué)位課程中開(kāi)始出現(xiàn)。 程序設(shè)計(jì)=數(shù)據(jù)結(jié)構(gòu)+算法

1.4基本概念和術(shù)語(yǔ)

1.4.1數(shù)據(jù)

??數(shù)據(jù)是描述客觀事物的符號(hào)，是計(jì)算機(jī)中可以操作的對(duì)象，是能被計(jì)算機(jī)識(shí)別，并輸入給計(jì)算機(jī)處理的符號(hào)集合。數(shù)據(jù)不僅僅包括整型，實(shí)型等數(shù)值類(lèi)型，還包括，字符及聲音，圖像，視頻等非數(shù)值類(lèi)型。

??我們這里說(shuō)的數(shù)據(jù)，其實(shí)就是符號(hào)，而且這些符號(hào)必須就別兩個(gè)前提：

可以輸入到計(jì)算機(jī)中

能被計(jì)算機(jī)程序處理

1.4.2 數(shù)據(jù)元素

??數(shù)據(jù)元素：是組成數(shù)據(jù)的，有一定意義的基本單位，在計(jì)算機(jī)中通常作為整體處理，也被稱(chēng)為記錄。

比如人類(lèi)的數(shù)據(jù)元素就是人。

畜類(lèi)的數(shù)據(jù)元素就是，牛，馬，羊，雞，豬，狗等。

1.4.3 數(shù)據(jù)項(xiàng)

??數(shù)據(jù)項(xiàng)：一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)做成。

??比如人這樣的數(shù)據(jù)元素，可以有眼，耳，鼻，口，手，腳這些數(shù)據(jù)項(xiàng)，也可以由姓名，年齡，性別，出生地址，聯(lián)系電話等數(shù)據(jù)項(xiàng)，具體哪些數(shù)據(jù)項(xiàng)，要視你做的系統(tǒng)來(lái)決定。

??數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位。在數(shù)據(jù)結(jié)構(gòu)這門(mén)課程中，我們把數(shù)據(jù)項(xiàng)定義為最小單位，有助于我們更好的解決問(wèn)題。真正討論問(wèn)題時(shí)，數(shù)據(jù)元素（記錄）才是數(shù)據(jù)結(jié)構(gòu)中建立數(shù)據(jù)模型的著眼點(diǎn)。就像我們討論一部電影時(shí)，是討論這部電影角色這樣的“數(shù)據(jù)元素”，而不是針對(duì)這個(gè)角色的姓名或者年齡這樣的“數(shù)據(jù)項(xiàng)”去研究分析。

1.4.4 數(shù)據(jù)對(duì)象

??數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。 ??什么叫性質(zhì)相同呢？是指數(shù)據(jù)元素具有相同數(shù)量和類(lèi)型的數(shù)據(jù)項(xiàng)，比如人都有姓名，生日，性別等相同的數(shù)據(jù)項(xiàng)。

1.4.5 數(shù)據(jù)結(jié)構(gòu)

??結(jié)構(gòu)，簡(jiǎn)單的理解就是關(guān)系，比如分子結(jié)構(gòu)，就是說(shuō)組成分子的原子之間的排列方式。嚴(yán)格點(diǎn)說(shuō)，結(jié)構(gòu)是指各個(gè)組成部分相互搭配和排列的方式。在現(xiàn)實(shí)世界中，不同數(shù)據(jù)元素之間不是獨(dú)立的，而是存在特定的關(guān)系，我們將這些關(guān)系稱(chēng)為結(jié)構(gòu)。那數(shù)據(jù)結(jié)構(gòu)是什么？

??數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

??在計(jì)算機(jī)中，數(shù)據(jù)元素并不是孤立、雜亂無(wú)序的，而是具有內(nèi)在聯(lián)系的數(shù)據(jù)集合。數(shù)據(jù)元素之間存在的一種或多種特定關(guān)系，也就是數(shù)據(jù)的組織形式。

??為編寫(xiě)出一個(gè)“好”的程序，必須分析待處理對(duì)象的特性及各處理對(duì)象之間存在的關(guān)系。這也就是研究數(shù)據(jù)結(jié)構(gòu)的意義所在。

??定義中提到了一種或多種特定關(guān)系，具體是什么樣的關(guān)系，這正是我們下面要討論的問(wèn)題。

1.5 邏輯結(jié)構(gòu)與物理結(jié)構(gòu)

??按照視點(diǎn)的不同，我們把數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。

1.5.1 邏輯結(jié)構(gòu)

??邏輯結(jié)構(gòu)：是指數(shù)據(jù)對(duì)象中數(shù)據(jù)元素之間的相互關(guān)系。其實(shí)這也是我們今后需要關(guān)注的問(wèn)題。邏輯結(jié)構(gòu)分為以下四種：

1.集合結(jié)構(gòu)

??集合結(jié)構(gòu)：集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一個(gè)集合外，它們之間沒(méi)有其他關(guān)系。各個(gè)數(shù)據(jù)元素是“平等”的，它們的共同屬性是“同屬于一個(gè)集合”。數(shù)據(jù)結(jié)構(gòu)中的集合關(guān)系就類(lèi)似于數(shù)學(xué)中的集合。

2.線性結(jié)構(gòu)

????????線性結(jié)構(gòu)：線性結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對(duì)一的關(guān)系

3.樹(shù)形結(jié)構(gòu)

????????樹(shù)形結(jié)構(gòu)：樹(shù)形結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一種一對(duì)多的層次關(guān)系

4.圖形結(jié)構(gòu)

????????圖形結(jié)構(gòu)：圖形結(jié)構(gòu)的數(shù)據(jù)元素是多對(duì)多的關(guān)系。

????????我們?cè)谟檬疽鈭D表示數(shù)據(jù)的邏輯結(jié)構(gòu)時(shí)，要注意兩點(diǎn)：

????????將每一個(gè)數(shù)據(jù)元素看做一個(gè)結(jié)點(diǎn)，用圓圈表示

????????元素之間的邏輯關(guān)系用結(jié)點(diǎn)之間的連線表示，如果這個(gè)關(guān)系是有方向的，那么用帶箭頭的連線表示。

????????從之前的例子也可以看出，邏輯結(jié)構(gòu)是針對(duì)具體問(wèn)題，是味蕾解決某個(gè)問(wèn)題在堆問(wèn)題理解的基礎(chǔ)上，選擇一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)表示數(shù)據(jù)元素之間的邏輯關(guān)系。

1.5.2 物理結(jié)構(gòu)

????????物理結(jié)構(gòu)；是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)形式。

????????很多書(shū)中也叫做存儲(chǔ)結(jié)構(gòu)，你要在理解上把他們當(dāng)做一回事。

????????數(shù)據(jù)是數(shù)據(jù)元素的集合，那么根據(jù)物理結(jié)構(gòu)的定義，世界上也就是如何把數(shù)據(jù)元素存儲(chǔ)到計(jì)算機(jī)的存儲(chǔ)器中。存儲(chǔ)器主要是針對(duì)內(nèi)存而言的，像硬盤(pán)，軟皮，光盤(pán)等外部存儲(chǔ)器的數(shù)據(jù)組織通常用文件結(jié)構(gòu)來(lái)描述。

????????數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)贏正確反映數(shù)據(jù)元素之間的邏輯關(guān)系，這才是最為關(guān)鍵的，如何存儲(chǔ)數(shù)據(jù)元素之間的邏輯關(guān)系，是實(shí)現(xiàn)物理結(jié)構(gòu)的重點(diǎn)和難點(diǎn)。

????????數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)形式有兩種：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。

1.順序存儲(chǔ)結(jié)構(gòu)

????????順序存儲(chǔ)結(jié)構(gòu)：是把數(shù)據(jù)元素存放在地址連續(xù)的存儲(chǔ)單元里，其數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系是一致的

2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

????????數(shù)據(jù)項(xiàng)存儲(chǔ)簡(jiǎn)單又規(guī)律，但總會(huì)有刪除，添加的情況，整個(gè)結(jié)構(gòu)時(shí)刻都處于變化中。顯然，面對(duì)這樣時(shí)常要變化的結(jié)構(gòu)，順序存儲(chǔ)是不科學(xué)的。那怎么辦呢？

????????鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：是把數(shù)據(jù)元素存放在任意的存儲(chǔ)單元里面，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。數(shù)據(jù)元素的存儲(chǔ)關(guān)系并不能反映其邏輯關(guān)系，因此需要用一個(gè)指針存放數(shù)據(jù)元素的地址，這樣通過(guò)地址就可以找到相關(guān)聯(lián)數(shù)據(jù)元素的位置。

????????顯然鏈?zhǔn)酱鎯?chǔ)就靈活很多，數(shù)據(jù)存在哪里不重要，只要有一個(gè)指針存放了響應(yīng)的地址就能找到了。

????????邏輯結(jié)構(gòu)面向問(wèn)題，物理結(jié)構(gòu)面向計(jì)算機(jī)，基本的目標(biāo)就是將數(shù)據(jù)及其邏輯關(guān)系存儲(chǔ)到計(jì)算機(jī)的內(nèi)存中。

1.6 抽象數(shù)據(jù)類(lèi)型

1.6.1 數(shù)據(jù)類(lèi)型

????????數(shù)據(jù)類(lèi)型：是指一組性質(zhì)相同的值的集合及定義在此集合上的一些操作的總稱(chēng)。

????????數(shù)據(jù)類(lèi)型是按照值的不同進(jìn)行劃分的。在高級(jí)語(yǔ)言中，每個(gè)變量，常量和表達(dá)式都有各自的取值范圍。類(lèi)型就用來(lái)說(shuō)明變量或表達(dá)式的取值范圍和所能進(jìn)行的操作。

????????在計(jì)算機(jī)中，內(nèi)存也不是無(wú)限大的，要計(jì)算一個(gè)如1+1=2,3+5=8這樣的整型數(shù)字的加減乘除運(yùn)算，顯然不需要要開(kāi)辟很大的適合小數(shù)深圳字符運(yùn)算的內(nèi)存空間。于是計(jì)算機(jī)的研究者們就考慮，要對(duì)數(shù)據(jù)進(jìn)行分類(lèi)，分出來(lái)多種數(shù)據(jù)類(lèi)型。

????????在C語(yǔ)言中，按照取值的不同，數(shù)據(jù)類(lèi)型可以分為兩類(lèi):

????????原子類(lèi)型：是不可以在分解的基本類(lèi)型，包括整型，實(shí)型，字符型等。

????????結(jié)構(gòu)類(lèi)型：由若干個(gè)類(lèi)型組合而成，是可以再分解的。例如整型數(shù)組是有若干個(gè)整型數(shù)據(jù)組成的。

????????比如，在C語(yǔ)言中變量聲明int a,b, 這就意味著，在變量a和b賦值時(shí)不能超出int的取值范圍，變量a和b之間的運(yùn)算只能是int類(lèi)型所允許的運(yùn)算。

????????抽象是指抽取出事物具有的普遍的性質(zhì)。它是抽出問(wèn)題的特征而忽略非本質(zhì)的細(xì)節(jié)，是對(duì)具體事物的一個(gè)概括。抽象是一種思考問(wèn)題的方式，它隱藏了繁雜的細(xì)節(jié)，值保留實(shí)現(xiàn)目標(biāo)所必須的信息。

1.6.2 抽象數(shù)據(jù)類(lèi)型

????????抽象數(shù)據(jù)類(lèi)型（Abstract Data Type,ADT）：是指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作。

????????抽象數(shù)據(jù)類(lèi)型的定義僅取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無(wú)關(guān)。

????????比如各個(gè)計(jì)算機(jī)，不管是大型機(jī)，小型機(jī)，PC，平板電腦，PDA，甚至是只能手機(jī)都有“整數(shù)”類(lèi)型，也需要整數(shù)間的運(yùn)算，那么整型其實(shí)就是一個(gè)抽象數(shù)據(jù)類(lèi)型，盡管他在上面提到的這些在不同計(jì)算機(jī)中實(shí)現(xiàn)方法上可能不一樣，但由于其定義的數(shù)學(xué)特性相同，在計(jì)算機(jī)編程者看來(lái)，它們都是相同的。因此“抽象”的意義在數(shù)據(jù)類(lèi)型的數(shù)學(xué)抽象特性。

????????抽象數(shù)據(jù)類(lèi)型體現(xiàn)了程序設(shè)計(jì)中問(wèn)題分解，抽象和信息隱藏的特性。

????????抽象數(shù)據(jù)類(lèi)型把實(shí)際生活中的問(wèn)題分解為多個(gè)規(guī)模小且容易處理的問(wèn)題，然后建立一個(gè)計(jì)算機(jī)能處理的數(shù)據(jù)模型，并把每個(gè)功能模塊的實(shí)現(xiàn)細(xì)節(jié)作為一個(gè)獨(dú)立的單元，從而使具體實(shí)現(xiàn)過(guò)程隱藏起來(lái)。

????????為了在之后的講解中對(duì)抽象數(shù)據(jù)類(lèi)型進(jìn)行規(guī)范的描述，我們給出了描述抽象數(shù)據(jù)類(lèi)型的標(biāo)準(zhǔn)格式：

????????ADT 抽象數(shù)據(jù)類(lèi)型名稱(chēng)

????????Data

????????????數(shù)據(jù)元素之間邏輯關(guān)系的定義

????????Operation

????????????操作1

????????????初始條件

????????????操作結(jié)果描述

????????????操作2

????????????。。。

????????????操作n

????????????。。。

????????endADT

1.7 總結(jié)回顧

????????數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

????????同樣的結(jié)構(gòu)，從不同的角度來(lái)討論，會(huì)有不同的分類(lèi)

????????邏輯結(jié)構(gòu)???? 物理結(jié)構(gòu)

????????集合結(jié)構(gòu)???? 順序存儲(chǔ)結(jié)構(gòu)

????????線性結(jié)構(gòu)???? 鏈接存儲(chǔ)結(jié)構(gòu)

????????樹(shù)形結(jié)構(gòu)

????????圖形結(jié)構(gòu)

1.8 結(jié)尾語(yǔ)

????????如果中途放棄了，之前所有的努力和付出都會(huì)變得沒(méi)有價(jià)值。