乾貨 | 數據結構的基本概念介紹
- 2020 年 2 月 25 日
- 筆記
文案 向柯瑋 排版 鄧發珩
疫情尚未結束，大家繼續堅守在家呀！響應鐘爺爺的號召，祝大家健健康康！
前言
各位看客老爺們，宅在家裡快樂！
對於數據結構，這個熟悉而又陌生的名詞，我相信很多人都不能很準確地說出它的定義，它包含哪些內容，它有什麼用，它應該怎麼學……
對於演算法，這個熟悉而又陌生的名詞，我相信很多人也都不能很準確地說出它的定義，它包含哪些內容，它有什麼用，它應該怎麼學……
不用著急，在接下來的一段時間裡，小瑋會陪著大家一起探究數據結構與演算法的魅力！
有一句在程式猿中流傳很久的話：'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。
今天是數據結構與演算法系列的第一篇，數據結構的相關概念介紹。
本篇文章中，小瑋會陪著大家了解數據結構的起源，一些基本概念和術語，一些結構……那麼我們開始吧。
起源
在很久以前，人們只是單純地把電腦理解為數值計算的工具，就感覺它只能用來計算。
所以才很早的時候，人們要使用電腦解決問題，一般都是從某個具體問題中抽象出一個適當的數據模型，然後再設計一個演算法來解這個模型，然後再編寫程式，得到一個軟體。
但是實際上，我們很多時候都並不是為了解決一個數值的問題，而是需要一種些更科學有效的手段（表，樹和圖等數據結構）的幫助，才可以更好地處理問題。
所以數據結構是一門研究非數值計算的程式設計問題中的操作對象，以及它們之間的關係和操作等相關問題的學科。
大約是在上世紀七十年代，各種各樣的大型程式出來了，軟體也開始相對獨立，結構程式設計成為程式設計方法學的主要內容。
其實一個程式設計的實質是對確定的問題選擇一種好的結構，加上設計一種好的演算法。
總的來說，程式設計=數據結構+演算法。
基本概念和術語
》數據
是描述客觀事物的符號，是電腦中可以操作的對象，是能被電腦識別，並輸入給電腦處理的符號集合。數據不僅僅包括整型、實型等數值類型，還包括字元，聲音，影像，影片等非數值類型。
舉個簡單的例子來說，在搜索引擎中，一般會有網頁、音頻、圖片等分類。就包括了上述的各種數據。
在這個位置，我們所說的數據，其實就是符號，而這些符號必須要滿足以下兩個條件：
1. 可以輸入到電腦中。
2. 能被電腦程式處理。
如果是數值類型數據，我們可以直接進行計算，如果是非數據類型，就可以通過編碼的方式變成字元數據來處理。
》數據元素
是組成數據的、有一定意義的基本單位，在電腦中通常作為整體處理。也被稱為記錄。
舉個例子來說，在一個人群裡面，它的數據元素是什麼？沒錯，當然是人啊。
》數據項
一個數據可以由多個數據項組成，而數據項就是一個數據的最小組成單位，打個比方來說一個人的最小組成單位是什麼？是手，耳，口……吧？
》數據對象
是性質相同的數據元素的集合，是數據的子集。
什麼叫做性質相同？就是數據元素具有相同數量和類型的數據項。打個比方說，人擁有姓名，生日，性別等相同的數據項。
》數據結構
說了這麼多，我們的主角終於登場了。結構，其實就是關係的意思，打個比方說一輛車的結構，就是內部各種配件的組裝關係。
在現實生活中，不同的數據元素之間是存在某些特定的關係的。我們把這些關係成為結構。
那麼數據結構呢？就是相互之間存在一種或者多種關係的數據元素的集合。
為了編寫出一個優質的程式，我們必須處理好不同數據之間的關係。而這就是我們研究數據結構的意義所在。
結構
》邏輯結構
是指數據對象中數據元素之間抽象的相互關係。這也是以後我們最需要考慮的東西。它主要分為四類。集合結構，線性結構，樹形結構，圖形結構。
1. 集合結構
在這個結構中的元素，除了在同一個集合裡面，沒有任何別的關係。如圖所示。
2. 線性結構
在這個結構中的元素之間都是一對一的關係，像一條線一樣。如圖所示。
3. 樹形結構
在這個結構中的元素之間存在一種一對多的關係層次關係，有一點需要注意，他們的父母只有一個，但是後代可以有多個。
但是電腦的樹和現實中的樹是有區別的：
(現實中的樹 VS 電腦科學中的樹)
4. 圖形結構
在這個結構中的元素是多對多的關係。分為有向和無向圖。在這裡給出無向圖的圖示。
不同的邏輯結構對應不同的具體問題，為了解決具體的問題，我們在對問題充分理解的基礎上會選擇合適的邏輯結構去表示其中元素的關係。
》物理結構
大家不用多想，覺得這是什麼高大上的東西。物理結構簡單的來說，其實就是數據的邏輯結構在電腦中的儲存方式。它主要分為順序儲存和鏈式儲存。
1. 順序儲存
就是把數據元素存放在地址連續的存儲單元中，其數據間的邏輯關係和物理關係一致，如圖所示。
其實這種儲存結構很容易理解，就和排隊佔位一樣的，大家都按一定的順序排好，誰也不要插別人的隊。舉一個例子，我們在學習c++的時候，數組就是這樣的儲存方式。
2. 鏈式儲存
首先，我們思考一個問題，在排隊的時候，如果有人突然離開了，或者是說有人情況很緊急，需要插隊，就會涉及到整個隊伍的變化。
如果是順序儲存的話，是不是非常不方便？你需要讓後面的全部發生變化，這是一種非常不科學的儲存。那麼科學的是什麼呢？就是我們的鏈式儲存。
鏈式儲存結構就是把各種數據元素存放到任意的儲存單元中，這組儲存單元可以是連續的也可以是不連續的。他們之間的聯繫是通過指針來實現的。
這種結構我們用生活中例子來說。去銀行辦理業務，我們需要取號，我們關注的不是別的號碼有沒有被叫到，我們只會關心我們前面的一個號碼有沒有被叫到，叫到了你就知道下一個是你了。
說到這個鏈式結構，我想到了小時候看的電影裡面的間諜，他們都是一對一的聯繫，如果其中某一個人不見了，那麼整條鏈都斷了。大家可以根據這個例子去理解一下這種結構。
抽象數據類型
說到這個，我想通過兩個方面來介紹，數據類型和抽象數據類型。
》數據類型
它是指一組性質相同的值的集合及定義在此集合上的一些操作的總稱。
這樣說其實並不是很容易理解，我們通俗地來講其實就是int，float……等等這樣的類型，它規定了這個數據的範圍，同時也規定了這個數據能夠進行的操作。
那麼數據類型有什麼用作用呢？舉一個例子來講，不同經濟條件的人會買不同價位的服飾，有的人會買幾萬的衣服，而有的會買幾十的衣服，而商家會按照不同的需求提供不同的衣服。
有的人可能覺得這個和咱們int，float這些不一樣。那麼我們再舉一個例子。你的電腦的記憶體不是無限大的吧？如果你的數據全是int範圍內的，但是你卻分配了float的記憶體給它們，後果是什麼？白白浪費了很多空間吧？
》抽象數據類型
當我們對數據類型進行抽象以後，就有了抽象數據類型。它具體是指一個數學模型及定義在該模型上的一組操作。
舉一個例子來說，同樣是整型的數據，在手機上，在電腦上，在計算器中，可能實現的方式就不一樣。但是不可否認的是，它們都是整型數據。在我們這些設計程式的人眼中，它們其實都是一樣的。這就是因為我們把它抽象了出來。
所以抽象數據類型就在於在這種數據類型的數學特徵。當然，它不僅僅是指這種數學模型，它同時也定義了相關的操作。
比如，對於拳皇這款遊戲，我們用整型浮點型等表示玩家的身高體重，並對裡面的人物定義了相關的攻擊防禦方法等一系列招式。
一個抽象數據類型定義了一個數據對象、數據對象中各數據元素之間的關係及對數據元素的操作。
其實在我看來，抽象數據類型其實就是對整個程式中的問題進行分解，把它們分解成多個規模小且容易處理的問題。
為了便於我們在之後的推文中對抽象數據類型進行規範化的描述，下面給出標準格式。
ADT 抽象數據結構類型名 Data 數據元素之間邏輯關係的定義 Operation 操作1 操作條件 結果描述 操作2 操作條件 結果描述 …… endADT
到這個位置，其實我們已經大致的了解了數據結構一些基本的方面。這個時候大家肯定仍然對於這一門學科充滿困惑，沒關係。後面還有很多內容，小瑋會慢慢陪大家進行學習！
大家在剛開始學習的時候肯定會覺得難學，這是很正常的，但是萬事開頭難，對吧？加油！
下期推文中，我們會一起了解演算法的相關內容。讓我們一起期待吧！
