干貨 | 數(shù)據(jù)結(jié)構(gòu)的基本概念介紹

文案?向柯瑋
排版 鄧發(fā)珩

疫情尚未結(jié)束，大家繼續(xù)堅守在家呀！響應(yīng)鐘爺爺?shù)奶栒伲４蠹医〗】悼担?/span>

前言

各位看客老爺們，宅在家里快樂！

對于數(shù)據(jù)結(jié)構(gòu)，這個熟悉而又陌生的名詞，我相信很多人都不能很準(zhǔn)確地說出它的定義，它包含哪些內(nèi)容，它有什么用，它應(yīng)該怎么學(xué)……

對于算法，這個熟悉而又陌生的名詞，我相信很多人也都不能很準(zhǔn)確地說出它的定義，它包含哪些內(nèi)容，它有什么用，它應(yīng)該怎么學(xué)……

不用著急，在接下來的一段時間里，小瑋會陪著大家一起探究數(shù)據(jù)結(jié)構(gòu)與算法的魅力！

有一句在程序猿中流傳很久的話：'If you?give?someone a?program, you will?frustrate them?for a day;?if you?teach?them?how to program, you will?frustrate?them for a lifetime'.?????

翻譯過來的意思：如果你交給某人一個程序，你會折磨他一天；如果你教會某人如何寫程序，你將會折磨他一輩子。

而我可能就是那一位會折磨大家一輩子的人，hhhh。

今天是數(shù)據(jù)結(jié)構(gòu)與算法系列的第一篇，數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念介紹。

本篇文章中，小瑋會陪著大家了解數(shù)據(jù)結(jié)構(gòu)的起源，一些基本概念和術(shù)語，一些結(jié)構(gòu)……那么我們開始吧。

起源

在很久以前，人們只是單純地把計算機(jī)理解為數(shù)值計算的工具，就感覺它只能用來計算。

所以才很早的時候，人們要使用計算機(jī)解決問題，一般都是從某個具體問題中抽象出一個適當(dāng)?shù)臄?shù)據(jù)模型，然后再設(shè)計一個算法來解這個模型，然后再編寫程序，得到一個軟件。

但是實際上，我們很多時候都并不是為了解決一個數(shù)值的問題，而是需要一種些更科學(xué)有效的手段（表，樹和圖等數(shù)據(jù)結(jié)構(gòu)）的幫助，才可以更好地處理問題。

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

大約是在上世紀(jì)七十年代，各種各樣的大型程序出來了，軟件也開始相對獨立，結(jié)構(gòu)程序設(shè)計成為程序設(shè)計方法學(xué)的主要內(nèi)容。

其實一個程序設(shè)計的實質(zhì)是對確定的問題選擇一種好的結(jié)構(gòu)，加上設(shè)計一種好的算法。

總的來說，程序設(shè)計=數(shù)據(jù)結(jié)構(gòu)+算法。

基本概念和術(shù)語

》數(shù)據(jù)

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

舉個簡單的例子來說，在搜索引擎中，一般會有網(wǎng)頁、音頻、圖片等分類。就包括了上述的各種數(shù)據(jù)。

在這個位置，我們所說的數(shù)據(jù)，其實就是符號，而這些符號必須要滿足以下兩個條件：

1. 可以輸入到計算機(jī)中。

2. 能被計算機(jī)程序處理。

如果是數(shù)值類型數(shù)據(jù)，我們可以直接進(jìn)行計算，如果是非數(shù)據(jù)類型，就可以通過編碼的方式變成字符數(shù)據(jù)來處理。

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

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

舉個例子來說，在一個人群里面，它的數(shù)據(jù)元素是什么？沒錯，當(dāng)然是人啊。

》數(shù)據(jù)項

一個數(shù)據(jù)可以由多個數(shù)據(jù)項組成，而數(shù)據(jù)項就是一個數(shù)據(jù)的最小組成單位，打個比方來說一個人的最小組成單位是什么？是手，耳，口……吧？

》數(shù)據(jù)對象

是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。

什么叫做性質(zhì)相同？就是數(shù)據(jù)元素具有相同數(shù)量和類型的數(shù)據(jù)項。打個比方說，人擁有姓名，生日，性別等相同的數(shù)據(jù)項。

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

說了這么多，我們的主角終于登場了。結(jié)構(gòu)，其實就是關(guān)系的意思，打個比方說一輛車的結(jié)構(gòu)，就是內(nèi)部各種配件的組裝關(guān)系。

在現(xiàn)實生活中，不同的數(shù)據(jù)元素之間是存在某些特定的關(guān)系的。我們把這些關(guān)系成為結(jié)構(gòu)。

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

為了編寫出一個優(yōu)質(zhì)的程序，我們必須處理好不同數(shù)據(jù)之間的關(guān)系。而這就是我們研究數(shù)據(jù)結(jié)構(gòu)的意義所在。

結(jié)構(gòu)

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

是指數(shù)據(jù)對象中數(shù)據(jù)元素之間抽象的相互關(guān)系。這也是以后我們最需要考慮的東西。它主要分為四類。集合結(jié)構(gòu)，線性結(jié)構(gòu)，樹形結(jié)構(gòu)，圖形結(jié)構(gòu)。

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

在這個結(jié)構(gòu)中的元素，除了在同一個集合里面，沒有任何別的關(guān)系。如圖所示。

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

在這個結(jié)構(gòu)中的元素之間都是一對一的關(guān)系，像一條線一樣。如圖所示。

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

在這個結(jié)構(gòu)中的元素之間存在一種一對多的關(guān)系層次關(guān)系，有一點需要注意，他們的父母只有一個，但是后代可以有多個。

但是計算機(jī)的樹和現(xiàn)實中的樹是有區(qū)別的：

(現(xiàn)實中的樹 VS 計算機(jī)科學(xué)中的樹)

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

在這個結(jié)構(gòu)中的元素是多對多的關(guān)系。分為有向和無向圖。在這里給出無向圖的圖示。

不同的邏輯結(jié)構(gòu)對應(yīng)不同的具體問題，為了解決具體的問題，我們在對問題充分理解的基礎(chǔ)上會選擇合適的邏輯結(jié)構(gòu)去表示其中元素的關(guān)系。

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

大家不用多想，覺得這是什么高大上的東西。物理結(jié)構(gòu)簡單的來說，其實就是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的儲存方式。它主要分為順序儲存和鏈?zhǔn)絻Υ?/span>。

1. 順序儲存

就是把數(shù)據(jù)元素存放在地址連續(xù)的存儲單元中，其數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系一致，如圖所示。

其實這種儲存結(jié)構(gòu)很容易理解，就和排隊占位一樣的，大家都按一定的順序排好，誰也不要插別人的隊。舉一個例子，我們在學(xué)習(xí)c++的時候，數(shù)組就是這樣的儲存方式。

2. 鏈?zhǔn)絻Υ?/strong>

首先，我們思考一個問題，在排隊的時候，如果有人突然離開了，或者是說有人情況很緊急，需要插隊，就會涉及到整個隊伍的變化。

如果是順序儲存的話，是不是非常不方便？你需要讓后面的全部發(fā)生變化，這是一種非常不科學(xué)的儲存。那么科學(xué)的是什么呢？就是我們的鏈?zhǔn)絻Υ妗?strong>

鏈?zhǔn)絻Υ娼Y(jié)構(gòu)就是把各種數(shù)據(jù)元素存放到任意的儲存單元中，這組儲存單元可以是連續(xù)的也可以是不連續(xù)的。他們之間的聯(lián)系是通過指針來實現(xiàn)的。

這種結(jié)構(gòu)我們用生活中例子來說。去銀行辦理業(yè)務(wù)，我們需要取號，我們關(guān)注的不是別的號碼有沒有被叫到，我們只會關(guān)心我們前面的一個號碼有沒有被叫到，叫到了你就知道下一個是你了。

說到這個鏈?zhǔn)浇Y(jié)構(gòu)，我想到了小時候看的電影里面的間諜，他們都是一對一的聯(lián)系，如果其中某一個人不見了，那么整條鏈都斷了。大家可以根據(jù)這個例子去理解一下這種結(jié)構(gòu)。

抽象數(shù)據(jù)類型

說到這個，我想通過兩個方面來介紹，數(shù)據(jù)類型和抽象數(shù)據(jù)類型。

》數(shù)據(jù)類型

它是指一組性質(zhì)相同的值的集合及定義在此集合上的一些操作的總稱。

這樣說其實并不是很容易理解，我們通俗地來講其實就是int，float……等等這樣的類型，它規(guī)定了這個數(shù)據(jù)的范圍，同時也規(guī)定了這個數(shù)據(jù)能夠進(jìn)行的操作。

那么數(shù)據(jù)類型有什么用作用呢？舉一個例子來講，不同經(jīng)濟(jì)條件的人會買不同價位的服飾，有的人會買幾萬的衣服，而有的會買幾十的衣服，而商家會按照不同的需求提供不同的衣服。

有的人可能覺得這個和咱們int，float這些不一樣。那么我們再舉一個例子。你的電腦的內(nèi)存不是無限大的吧？如果你的數(shù)據(jù)全是int范圍內(nèi)的，但是你卻分配了float的內(nèi)存給它們，后果是什么？白白浪費了很多空間吧？

》抽象數(shù)據(jù)類型

當(dāng)我們對數(shù)據(jù)類型進(jìn)行抽象以后，就有了抽象數(shù)據(jù)類型。它具體是指一個數(shù)學(xué)模型及定義在該模型上的一組操作。

舉一個例子來說，同樣是整型的數(shù)據(jù)，在手機(jī)上，在電腦上，在計算器中，可能實現(xiàn)的方式就不一樣。但是不可否認(rèn)的是，它們都是整型數(shù)據(jù)。在我們這些設(shè)計程序的人眼中，它們其實都是一樣的。這就是因為我們把它抽象了出來。

所以抽象數(shù)據(jù)類型就在于在這種數(shù)據(jù)類型的數(shù)學(xué)特征。當(dāng)然，它不僅僅是指這種數(shù)學(xué)模型，它同時也定義了相關(guān)的操作。

比如，對于拳皇這款游戲，我們用整型浮點型等表示玩家的身高體重，并對里面的人物定義了相關(guān)的攻擊防御方法等一系列招式。

一個抽象數(shù)據(jù)類型定義了一個數(shù)據(jù)對象、數(shù)據(jù)對象中各數(shù)據(jù)元素之間的關(guān)系及對數(shù)據(jù)元素的操作。

其實在我看來，抽象數(shù)據(jù)類型其實就是對整個程序中的問題進(jìn)行分解，把它們分解成多個規(guī)模小且容易處理的問題。

為了便于我們在之后的推文中對抽象數(shù)據(jù)類型進(jìn)行規(guī)范化的描述，下面給出標(biāo)準(zhǔn)格式。

ADT?抽象數(shù)據(jù)結(jié)構(gòu)類型名Data ????數(shù)據(jù)元素之間邏輯關(guān)系的定義Operation    操作1        操作條件        結(jié)果描述????操作2        操作條件        結(jié)果描述????????……endADT

到這個位置，其實我們已經(jīng)大致的了解了數(shù)據(jù)結(jié)構(gòu)一些基本的方面。這個時候大家肯定仍然對于這一門學(xué)科充滿困惑，沒關(guān)系。后面還有很多內(nèi)容，小瑋會慢慢陪大家進(jìn)行學(xué)習(xí)！

大家在剛開始學(xué)習(xí)的時候肯定會覺得難學(xué)，這是很正常的，但是萬事開頭難，對吧？加油！

下期推文中，我們會一起了解算法的相關(guān)內(nèi)容。讓我們一起期待吧！