大部分內(nèi)容基于中國大學(xué)MOOC的2021考研數(shù)據(jù)結(jié)構(gòu)課程所做的筆記，該課屬于付費課程（不過盜版網(wǎng)盤資源也不難找。。。）。后續(xù)又根據(jù)23年考研的大綱對內(nèi)容做了一些調(diào)整，將二叉排序樹和平衡二叉樹的內(nèi)容挪到了查找一章，并增加了并查集、平衡二叉樹的刪除、紅黑樹的內(nèi)容。

排序一章的各種算法動態(tài)過程比較難以展現(xiàn)，所以閱讀體驗可能不是特別好。

西電的校內(nèi)考試分機試和筆試。筆試占50分，機試2小時4道題占30分，做出2道滿分，多做一道總分加5分。機試盡量把老師平時發(fā)的OJ題目都過一遍。筆試內(nèi)容偏基礎(chǔ)，但考的量比較大。

?

其他各章節(jié)的鏈接如下：

數(shù)據(jù)結(jié)構(gòu)筆記（王道考研） 第一章：緒論

數(shù)據(jù)結(jié)構(gòu)筆記（王道考研） 第二章：線性表

數(shù)據(jù)結(jié)構(gòu)筆記（王道考研） 第三章：棧和隊列

數(shù)據(jù)結(jié)構(gòu)筆記（王道考研） 第四章：串

數(shù)據(jù)結(jié)構(gòu)筆記（王道考研） 第五章：樹和二叉樹

數(shù)據(jù)結(jié)構(gòu)筆記（王道考研） 第六章：圖

數(shù)據(jù)結(jié)構(gòu)筆記（王道考研） 第七章：查找

數(shù)據(jù)結(jié)構(gòu)筆記（王道考研） 第八章：排序

其他各科筆記匯總

緒論

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)如何用程序代碼把現(xiàn)實世界的問題信息化，學(xué)習(xí)如何用計算機高效地處理這些信息從而創(chuàng)造價值

數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)

數(shù)據(jù)是信息的載體，是描述客觀事物屬性的數(shù)，字符及所有能輸入計算機中并被計算機程序識別和處理的符號的集合。數(shù)據(jù)是計算機程序加工的原料。

數(shù)據(jù)元素，數(shù)據(jù)項

數(shù)據(jù)元素是數(shù)據(jù)的基本單位，通常作為一個整體進行考慮和處理

一個數(shù)據(jù)元素可由若干數(shù)據(jù)項組成，數(shù)據(jù)項是構(gòu)成數(shù)據(jù)元素的不可分割的最小單位。多個數(shù)據(jù)項可組成組合項

要根據(jù)實際的業(yè)務(wù)需求來確定什么是數(shù)據(jù)元素，什么是數(shù)據(jù)項。

數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)對象

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

數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集

數(shù)據(jù)結(jié)構(gòu)的三要素

數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)元素之間的邏輯關(guān)系是什么？

集合：各個元素同屬一個集合，別無其他關(guān)系

線性結(jié)構(gòu)：數(shù)據(jù)元素之間是一對一的關(guān)系。除了第一個元素，所有元素都有唯一前驅(qū)；除了最后一個元素，所有元素都有唯一后繼

樹形結(jié)構(gòu)：數(shù)據(jù)元素之間是一對多的關(guān)系

圖結(jié)構(gòu)：數(shù)據(jù)元素之間是多對多的關(guān)系

數(shù)據(jù)的物理結(jié)構(gòu)（存儲結(jié)構(gòu)）

探討如何用計算機表示數(shù)據(jù)元素的邏輯關(guān)系？

?

以線性結(jié)構(gòu)這種邏輯結(jié)構(gòu)為例。存儲結(jié)構(gòu)可分為順序存儲，鏈?zhǔn)酱鎯?，索引存儲，散列存儲，后三種為非順序存儲

順序存儲：把邏輯上相鄰的元素存儲在物理上也相鄰的存儲單元中，元素之間的關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)

鏈?zhǔn)酱鎯Γ哼壿嬌舷噜彽脑卦谖锢砦恢蒙峡梢圆幌噜?，借助指示元素存儲地址的指針來表示元素之間的邏輯關(guān)系，用指針表示下一個數(shù)據(jù)元素的存儲地址

索引存儲：在存儲元素信息的同時，還建立附加的索引表。索引表中的每項稱為索引項，索引項的一般形式是（關(guān)鍵字，地址）

散列存儲：根據(jù)元素的關(guān)鍵字直接計算出元素的存儲地址，又稱哈希存儲（在第六章的散列表學(xué)習(xí)）

以上內(nèi)容，現(xiàn)在只需要理解以下幾點即可

• 若采用順序存儲，則各個數(shù)據(jù)元素在物理上必須是連續(xù)的；若采用非順序存儲，則各個數(shù)據(jù)元素在物理上可以是離散的
• 數(shù)據(jù)的存儲結(jié)構(gòu)會影響存儲空間分配的方便程度
• 數(shù)據(jù)的存儲結(jié)構(gòu)會影響對數(shù)據(jù)運算的速度

數(shù)據(jù)的運算

施加在數(shù)據(jù)上的運算包括運算的定義和實現(xiàn)。運算的定義是針對邏輯結(jié)構(gòu)的，指出運算的功能；運算的實現(xiàn)是針對存儲結(jié)構(gòu)的，指出運算的具體操作步驟。

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

數(shù)據(jù)類型是一個值的集合和定義在此集合上的一組操作的總稱，又可分為

1.原子類型。其值不可再分的數(shù)據(jù)類型

2.結(jié)構(gòu)類型。其值可以再分解為若干成分（分量）的數(shù)據(jù)類型

抽象數(shù)據(jù)類型（ADT）是抽象數(shù)據(jù)組織及與之相關(guān)的操作。ADT用數(shù)學(xué)化的語言定義數(shù)據(jù)的邏輯結(jié)構(gòu)，定義運算。與具體的實現(xiàn)無關(guān)。

定義一個ADT，就是定義了數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的運算。也就是定義了一個數(shù)據(jù)結(jié)構(gòu)。而確定一種存儲結(jié)構(gòu)，就意味著在計算機中表示出數(shù)據(jù)的邏輯結(jié)構(gòu)。存儲結(jié)構(gòu)不同，也會導(dǎo)致運算的具體實現(xiàn)不同。確定了存儲結(jié)構(gòu)，才能實現(xiàn)數(shù)據(jù)結(jié)構(gòu)。

在探討一種數(shù)據(jù)結(jié)構(gòu)時：

1.定義邏輯結(jié)構(gòu)（數(shù)據(jù)元素之間的關(guān)系）

2.定義數(shù)據(jù)的運算（針對現(xiàn)實需求，應(yīng)該對這種邏輯結(jié)構(gòu)進行什么樣的運算）

3.確定某種存儲結(jié)構(gòu)，實現(xiàn)數(shù)據(jù)結(jié)構(gòu)，并實現(xiàn)一些對數(shù)據(jù)結(jié)構(gòu)的基本運算

算法的基本概念

什么是算法？

程序=數(shù)據(jù)結(jié)構(gòu)+算法，數(shù)據(jù)結(jié)構(gòu)研究如何把現(xiàn)實世界的問題信息化，將信息存進計算機。同時還要實現(xiàn)對數(shù)據(jù)結(jié)構(gòu)的基本操作。算法研究如何處理這些信息，解決實際問題

算法的五個特性

• 有窮性。一個算法必須總在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時間內(nèi)完成
• 確定性。算法中每條指令必須有確切的含義，對于相同的輸入只能得出相同的輸出
• 可行性。算法中描述的操作都可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)
• 輸入。一個算法有0個或多個輸入，這些輸入取自于某個特定的對象的集合
• 輸出。一個算法有一個或多個輸出，這些輸出是與輸入有著某種特定關(guān)系的量

算法必須是有窮的，要求用有限的步驟解決某個特定的問題。而程序可以是無窮的

“好”算法的特性

• 正確性。算法應(yīng)能夠正確地解決求解問題
• 可讀性。算法應(yīng)具有良好的可讀性，以幫助人們理解
• 健壯性。輸入非法數(shù)據(jù)時，算法能適當(dāng)?shù)刈龀龇磻?yīng)或進行處理，而不會莫名其妙的輸出結(jié)果
• 高效率（執(zhí)行速度快，時間復(fù)雜度低）與低存儲量需求（不費內(nèi)存，空間復(fù)雜度低）

算法可以用偽代碼描述，甚至用文字描述，重要的是要“無歧義”地描述出解決問題的步驟

算法的時間復(fù)雜度

如何評估算法時間開銷？

讓算法先運行，事后統(tǒng)計運行時間的方法是不科學(xué)的。因為存在如下問題

• 和機器性能有關(guān)，如超級計算機和單片機
• 和編程語言有關(guān)，越高級的語言執(zhí)行效率越低
• 和編譯程序產(chǎn)生的機器指令質(zhì)量有關(guān)
• 有些算法是不能事后再統(tǒng)計的，如：導(dǎo)彈發(fā)射算法

我們希望評估算法時能排除與算法本身無關(guān)的外界因素，且能事先估計，所以有了時間復(fù)雜度，以事前預(yù)估算法時間開銷$T(n)$與問題規(guī)模$n$的關(guān)系

時間復(fù)雜度的計算

• 時間復(fù)雜度的計算滿足乘法規(guī)則和加法規(guī)則

加法規(guī)則：$T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))$

多項相加，只保留最高階的項且系數(shù)變?yōu)?

乘法規(guī)則：$T(n)=T_1(n)+T_2(n)=O(f(n))\times O(g(n))=O(f(n)\times g(n))$

多項相乘，都保留

• 表達式只保留階數(shù)高的部分，如$T(n)=n^3+n^2+9999999$的各項只保留$n^3$

• 只關(guān)心數(shù)量級，用大$O$表示“同階”，同等數(shù)量級。即：當(dāng)$n\to \infty$時，二者之比為常數(shù)

所以常數(shù)項系數(shù)可以省略，同時時間復(fù)雜度的計算結(jié)果用$O(...)$的方式表示

• $O(1)<O(lo{g}_{2}n)<O(n)<O(nlo{g}_{2}n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$

可以結(jié)合洛必達法則和函數(shù)圖像來證明，用“常對冪指階”來記憶

• 順序執(zhí)行的代碼只會影響最終結(jié)果的表達式的常數(shù)項，可以忽略。

• 考慮循環(huán)語句時，只需挑循環(huán)中的一個基本操作分析它的執(zhí)行次數(shù)與$n$的關(guān)系即可

• 如果有多層嵌套循環(huán)，只需關(guān)注最深層循環(huán)的循環(huán)次數(shù)與$n$的關(guān)系

• 很多算法執(zhí)行時間與輸入的數(shù)據(jù)有關(guān)。這種時候就要考慮最好時間復(fù)雜度和最壞時間復(fù)雜度，平均時間復(fù)雜度

最壞時間復(fù)雜度：最壞情況下算法的時間復(fù)雜度

平均時間復(fù)雜度：所有輸入示例等概率出現(xiàn)的情況下，算法的期望運行時間

最好時間復(fù)雜度：最好情況下算法的時間復(fù)雜度

算法的空間復(fù)雜度

空間復(fù)雜度的計算

基本上可以類比時間復(fù)雜度的計算

現(xiàn)在要運行一個程序，程序運行前會先把程序代碼（這里的代碼是源代碼編譯后生成的機器指令）放到內(nèi)存中（大小固定，與問題規(guī)模無關(guān)）。接下來CPU會一行行的執(zhí)行這些代碼，內(nèi)存中開辟空間存放局部變量和參數(shù)，數(shù)組和其他信息。

• 如果無論問題規(guī)模怎么變，算法運行所需的內(nèi)存空間都是固定的常量，算法空間復(fù)雜度為$S(n)=O(1)$。此時可以說算法原地工作。
• 只需關(guān)注存儲空間大小與問題規(guī)模相關(guān)的變量。表達式中的常數(shù)項可省略
• 由于只關(guān)心數(shù)量級，計算時沒必要考慮不同類型變量所占用的內(nèi)存空間大小上的差異
• 同樣遵循加法和乘法原則，上一節(jié)用于比較數(shù)量級的不等式也適用于空間復(fù)雜度的計算

函數(shù)遞歸調(diào)用帶來的內(nèi)存開銷

遞歸過程中每加深一層的調(diào)用都需要把這一層的局部變量，參數(shù)等在內(nèi)存中開辟一塊新的空間用于存儲文章來源地址http://www.zghlxwxcb.cn/news/detail-634211.html

• 只需關(guān)注存儲空間大小與問題規(guī)模相關(guān)的變量。表達式中的常數(shù)項可省略
• 由于只關(guān)心數(shù)量級，計算時沒必要考慮不同類型變量所占用的內(nèi)存空間大小上的差異
• 同樣遵循加法和乘法原則，上一節(jié)用于比較數(shù)量級的不等式也適用于空間復(fù)雜度的計算

函數(shù)遞歸調(diào)用帶來的內(nèi)存開銷

遞歸過程中每加深一層的調(diào)用都需要把這一層的局部變量，參數(shù)等在內(nèi)存中開辟一塊新的空間用于存儲

• 絕大多數(shù)情況下空間復(fù)雜度=遞歸調(diào)用的深度，有些情況則要具體分析。

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)筆記（王道考研） 第一章：緒論的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！