1.1 什么是數(shù)據(jù)結(jié)構(gòu) ？

與其說數(shù)據(jù)結(jié)構(gòu)是一門學(xué)科，我更加希望我們可以把它看作一種藝術(shù)。更加貼近生活的話，像是一門手藝。我們掌握了這門手藝再去干活才能干得干凈利索。

當(dāng)然，要掌握這門手藝是需要付出一些代價(jià)的，這包括但不限于交大學(xué)學(xué)費(fèi)、安裝相關(guān)軟件以及依賴環(huán)境、從舒服的宿舍趕到犯困的教室上課、考試前的緊張以及掛科后的懊惱等等。因?yàn)樗且环N藝術(shù)，自然不像打掃衛(wèi)生那般簡(jiǎn)單直接。

那么這到底是一種什么藝術(shù)呢 ？我們這里先摘抄一段教材給的定義 —— 盡管我們認(rèn)為藝術(shù)不應(yīng)該被定義。

數(shù)據(jù)結(jié)構(gòu) (Data Structure) 是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。換句話說，數(shù)據(jù)結(jié)構(gòu)是帶 “結(jié)構(gòu)” 的數(shù)據(jù)元素的集合， “結(jié)構(gòu)” 就是指數(shù)據(jù)元素之間存在的關(guān)系。

這與悟道很像，我們不能急于理解它是什么，大概能夠背誦一下應(yīng)付考試、面試即可（還有就是在其他專業(yè)的人面前聊到這方面的時(shí)候，無意間來一句，數(shù)據(jù)結(jié)構(gòu)不就是 … ，以顯示咱們這種科班的人氣質(zhì)不同）。我們應(yīng)當(dāng)在實(shí)際學(xué)習(xí)過程中不斷地回顧這句話的含義，什么是結(jié)構(gòu)，什么是數(shù)據(jù)元素之間的關(guān)系等等。

1.2 數(shù)據(jù)相關(guān)術(shù)語

這是一個(gè)非常無聊的事情，但是還經(jīng)常考這種簡(jiǎn)答題或填空題，因?yàn)樗芑A(chǔ)，也很重要。

數(shù)據(jù)（Data）：對(duì)客觀事物的符號(hào)表示，指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的集合總稱。凡是存放在計(jì)算機(jī)操作系統(tǒng)內(nèi)的內(nèi)容均是數(shù)據(jù)。

數(shù)據(jù)元素（Data Element）：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。比如我們某一門的考試成績(jī)，某一條聊天記錄，或者是聊天記錄中的每一個(gè)字符，都可以被當(dāng)作數(shù)據(jù)元素，這與研究需求相關(guān)。

數(shù)據(jù)項(xiàng)（Data Item）： 是組成數(shù)據(jù)元素的、有獨(dú)立含義的、不可分割的最小單位。比如學(xué)生基本信息表中的學(xué)號(hào)、姓名、性別等都是數(shù)據(jù)項(xiàng)，我們強(qiáng)調(diào)的是如果強(qiáng)行分割則會(huì)導(dǎo)致指代不明或失去原有的意思，那么它就是不可分割的最小單位。

數(shù)據(jù)對(duì)象（Data Object）：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。例如：整數(shù)數(shù)據(jù)對(duì)象是集合 $N=\{?2,?1,0,1,2,...\}$ 等。

1.3 數(shù)據(jù)結(jié)構(gòu)的分類

1.3.1 邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩個(gè)層次，這也是我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的時(shí)候無時(shí)不刻需要明確的問題。比如有一天老師講 “線性表” 得清楚線性表是邏輯結(jié)構(gòu)的一種；而老師講到 “順序存儲(chǔ)” 與 “鏈?zhǔn)酱鎯?chǔ)” 的時(shí)候，就應(yīng)當(dāng)清楚這講的是數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。并且在實(shí)際應(yīng)用中，也應(yīng)當(dāng)思考這個(gè)問題 —— 這種情況下應(yīng)當(dāng)使用順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)更加高效。

1.3.2 邏輯結(jié)構(gòu)分類

總體而言，邏輯結(jié)構(gòu)按照以下結(jié)構(gòu)劃分：

這里個(gè)人認(rèn)為教材上的黑白兩色多少有點(diǎn)枯燥，故而特意使用xmind繪制了一下

這里我們不去細(xì)細(xì)查看到底什么結(jié)構(gòu)具有什么屬性，但一定要大致熟悉這個(gè)大坑里面有哪些小可愛，我們以后還會(huì)經(jīng)常見面。

1.3.2 存儲(chǔ)結(jié)構(gòu)分類

)
這個(gè)很容易理解，就像考試的時(shí)候一般老師發(fā)試卷的時(shí)候會(huì)從第一個(gè)傳到最后一個(gè)，有嚴(yán)格的 “先后順序”，但是老師點(diǎn)名叫同學(xué)回答問題就是 “鏈?zhǔn)健?#xff0c;大學(xué)老師一般記不住所有人的名字，就拿著花名冊(cè)進(jìn)行選擇，這類似于同學(xué)們?cè)阪湵淼奈恢么鎯?chǔ)在花名冊(cè)中。

當(dāng)然不得不說的是，當(dāng)老師點(diǎn)名沒人答到的時(shí)候，這就是一個(gè) “空指針異常”，一般可能會(huì)帶來一些或大或小的不好的后果，所以各位小伙伴們盡量不要遲到、不要缺席。

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

數(shù)據(jù)類型（Data Type）：即數(shù)據(jù)的類型，比如字符串類型、整數(shù)類型、浮點(diǎn)數(shù)類型等等；

抽象數(shù)據(jù)類型（Abstract Data Type, ADT）：可以理解為從特殊到一般的抽象結(jié)果。比如說上課的時(shí)候在課堂下聽講的一般我們可以用學(xué)生來概述，而年紀(jì)差不多，學(xué)校里撞見的我們都可以叫作同學(xué)，還有什么小姐姐小哥哥都是一種從特殊到一般的概述。抽象數(shù)據(jù)類型也是如此，我們希望能夠總結(jié)出這一類數(shù)據(jù)所具有的共同特點(diǎn)，并把這些特點(diǎn)總結(jié)為某個(gè)抽象數(shù)據(jù)類型。

一般而言，抽象數(shù)據(jù)類型可以描述為：

ADT抽象數(shù)據(jù)類型名 {數(shù)據(jù)對(duì)象:（數(shù)據(jù)對(duì)象的定義） 數(shù)據(jù)關(guān)系:（數(shù)據(jù)關(guān)系的定義）基本操作:（基本操作的定義） }

這里再舉個(gè)例子：

ADT 大學(xué)生 {數(shù)據(jù)對(duì)象：學(xué)號(hào)編號(hào)，數(shù)據(jù)關(guān)系：同專業(yè)、同班級(jí)、同學(xué)院等，基本操作：吃飯、睡覺、打豆豆、學(xué)習(xí)、考試 }

在高級(jí)開發(fā)語言中我們常常稱這種思想為 “面向?qū)ο蟆?#xff0c;這里的 “大學(xué)生” 就是 “面向?qū)ο蟆?里面的 “類” 的概念，而具體的學(xué)生，比如小明、馬超、諸葛亮就是 “大學(xué)生” 這個(gè)類的具體 “對(duì)象”。

1.4 算法基礎(chǔ)

這里主要是一些概念問題以及一個(gè)計(jì)算問題。

1.4.1 算法的定義以及特征

1.4.2 算法的優(yōu)劣

1.4.3 為什么要用 n

時(shí)間復(fù)雜度和空間復(fù)雜度一般使用 $O(n)$ 或 $O(n^2)$ 來表示，那么首先我們需要明確 $n$ 是指什么，為什么要用一個(gè)字母來表示復(fù)雜度，用具體的數(shù)值不行嗎？

原因很簡(jiǎn)單：我們要解決的問題往往是一個(gè) “看不到頭” 的問題。如果老師讓小學(xué)生求解1到10的整數(shù)的和是很容易的，1到100的和勉強(qiáng)也能算出來，但是如果1到10000呢 ？ 我們會(huì)用到常常會(huì)用到等差數(shù)列求和公式來求解，而等差序列求和公式中 $S(n)=\frac{n(n+1)}{2}$ 就是一種概括，因?yàn)?$n$ 不再是具體的某個(gè)數(shù)，它適用于所有的正整數(shù)。

1.4.4 時(shí)間復(fù)雜度

一般情況下，算法中基本語句重復(fù)執(zhí)行的次數(shù)是問題規(guī)模 $n$ 的某個(gè)函數(shù) $f(n)$，算法的時(shí)間量度記作
$$T(n)=O(f(n))$$
它表示隨問題規(guī)模 $n$ 的增大， 算法執(zhí)行時(shí)間的增長率和 $f(n)$ 的增長率相同， 稱做算法的 漸近時(shí)間復(fù)雜度， 簡(jiǎn)稱時(shí)間復(fù)雜度（Time Complexity）。

其中數(shù)字符號(hào) $O$ 的嚴(yán)格定義為：

若 $T(n)$ 和 $f(n)$ 是定義在正整數(shù)集合上的兩個(gè)函數(shù)，則 $T(n)=O(f(n))$ 表示存在正的常數(shù) $C$ 和 $n_0$，使得當(dāng) $n\ge n_0$ 時(shí)都滿足 $0\le T(n)\le Cf(n)$。

定理 1.1 ：若 $f(n)=a_m{n}^m+a_{m?1}{n}^{m?1}+...+a_{1}n+a_0$ 是一個(gè) $m$ 次多項(xiàng)式，則 $T(n)=O(n^m)$。

這里我們需要結(jié)合高等數(shù)學(xué)中的求極限的思想，也可以理解為 “抓住主要矛盾”。比如我們定義個(gè)函數(shù)，函數(shù)中有個(gè) 時(shí)間復(fù)雜度 $n^2$ 的循環(huán)以及一個(gè)時(shí)間復(fù)雜度為 $n^3$ 的循環(huán)，那么我們應(yīng)當(dāng)認(rèn)為這個(gè)函數(shù)的時(shí)間復(fù)雜度為 $O(n^3)$。因?yàn)楫?dāng) $n$ 不斷變大的時(shí)候，$n^2$ 的影響力相對(duì)越小。

1.4.5 空間復(fù)雜度

類似于時(shí)間復(fù)雜度，這里空間復(fù)雜度我們理解為算法執(zhí)行過程中需要額外申請(qǐng)的空間資源即可。比如我們將一個(gè)數(shù)組反轉(zhuǎn)，有個(gè)很簡(jiǎn)單的方法就是新建一個(gè)和它大小一樣的數(shù)組，然后反過來記錄一遍即可，這里需要申請(qǐng)的空間資源就是原數(shù)組的大小的資源，即空間復(fù)雜度為 $O(n)$。

一般而言，由于現(xiàn)在存儲(chǔ)技術(shù)的快速發(fā)展，我們?cè)絹碓皆谝獾氖菚r(shí)間復(fù)雜度問題。

1.5 本章小結(jié)

本章粗略地過了一遍數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)內(nèi)容，主要包括一些術(shù)語的介紹以及算法的基本內(nèi)容。內(nèi)容較為簡(jiǎn)單，需要計(jì)算的地方應(yīng)該在于時(shí)間復(fù)雜度的計(jì)算上，并且期末考、考研等都常常遇到這種問題，但由于篇幅問題這里不做介紹。

各位小伙伴們應(yīng)當(dāng)一直提醒一下自己是在做一件偉大的事情 —— 學(xué)習(xí)一門叫作數(shù)據(jù)結(jié)構(gòu)的藝術(shù)課，所以就不那么無聊了吧。現(xiàn)在還沒有到創(chuàng)作的時(shí)間，我們先把基本工打好。

共勉！

Smileyan
2023.04.27 01:06

總結(jié)

以上是生活随笔為你收集整理的趣说数据结构 —— 1. 绪论的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。