本博文使用簡單易懂的方式講解數(shù)據(jù)結(jié)構(gòu)，并用C語言進(jìn)行了實(shí)現(xiàn)，即使你是零基礎(chǔ)，本博文也會為你鋪平學(xué)習(xí)之路，相信讀完本博客你會對數(shù)據(jù)結(jié)構(gòu)有更深一步的了解和認(rèn)識。

本博文中提到的所有數(shù)據(jù)結(jié)構(gòu)都使用C語言進(jìn)行了實(shí)現(xiàn)，限于篇幅原因，博主將所有實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的代碼放在了Github上，讀者可自行查閱。

為了避免篇幅過長，本博文中所有數(shù)據(jù)結(jié)構(gòu)的具體操作細(xì)節(jié)會在《數(shù)據(jù)結(jié)構(gòu)》專欄 的具體文章中講解。每種數(shù)據(jù)結(jié)構(gòu)下都附有該數(shù)據(jù)結(jié)構(gòu)詳解的鏈接，以及使用C語言實(shí)現(xiàn)的Github地址，希望可以方便大家學(xué)習(xí)。

目錄

• 先驗(yàn)知識——C語言
• 鏈表
• • 單鏈表
  • 雙鏈表
  • 循環(huán)單鏈表
  • 循環(huán)雙鏈表
  • 小結(jié)
• 堆棧
• • 堆棧的數(shù)組實(shí)現(xiàn)
  • 堆棧的鏈表實(shí)現(xiàn)
• 隊(duì)列
• • 隊(duì)列的數(shù)組實(shí)現(xiàn)
  • 隊(duì)列的鏈表實(shí)現(xiàn)
  • 循環(huán)隊(duì)列
• 樹
• • 二叉樹
  • 二叉搜索樹
  • 平衡搜索樹（AVL）
  • B樹
  • B+樹
• 圖
• • 廣度優(yōu)先搜索（BFS）
  • 深度優(yōu)先搜索（DFS）
  • 生成樹

先驗(yàn)知識——C語言

為了更好地使用C語言學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，本節(jié)我們介紹實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)我們應(yīng)該掌握的一些基礎(chǔ)知識。

對于很多C語言基礎(chǔ)不夠好，又不想再系統(tǒng)地去學(xué)習(xí)的童鞋，建議一看博主推出的數(shù)據(jù)結(jié)構(gòu)第一課，相信對C語言基礎(chǔ)不夠好又想快速學(xué)習(xí)數(shù)據(jù)接結(jié)構(gòu)的童鞋大有幫助。

C語言0基礎(chǔ)的童鞋，建議先學(xué)習(xí)C語言，博主推薦譚浩強(qiáng)的《C語言程序設(shè)計(jì)》（博主這里有電子版，給大家上傳的時候遇到了問題，有需要的童鞋可以留言或郵件聯(lián)系，文章結(jié)尾有郵箱），不過很多人可能會說這本教程并不是很好，作為0基礎(chǔ)的我們而言，學(xué)會C語言的一些基本知識已經(jīng)夠了，而且該書作為很多學(xué)校的教材，因此可以一讀以了解C語言。

當(dāng)然這里還推薦菜鳥教程，相信過一遍之后相信你會對C語言有一些基本的了解。

鏈表

鏈表是一種邏輯上連續(xù)，而存儲結(jié)構(gòu)上非連續(xù)的一種存儲結(jié)構(gòu)，即：鏈表是由一些在存儲位置上不連續(xù)的數(shù)據(jù)組成的。因此，鏈表的每個結(jié)點(diǎn)應(yīng)包含兩個部分：一個是數(shù)據(jù)域，用于存儲數(shù)據(jù)，另一個是指針域，用于存儲其相鄰結(jié)點(diǎn)的地址。

PS: 每個單元都會存儲數(shù)據(jù)，為了把每個存儲單元的數(shù)據(jù)串起來，每個單元會存儲相鄰單元的地址（指針域的作用）

優(yōu)點(diǎn)：

• 鏈表不需要初始化容量，可以任意加減元素；
• 添加或者刪除元素時只需要改變前后兩個元素結(jié)點(diǎn)的指針域的指向地址即可，所以添加，刪除很快

缺點(diǎn)：

• 因?yàn)楹写罅康闹羔樣?#xff0c;占用空間較大
• 查找元素需要遍歷鏈表來查找，非常耗時

適用場景：

• 數(shù)據(jù)量較小，需要頻繁增加，刪除操作的場景

單鏈表

單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu)，由每個結(jié)點(diǎn)單元連接而成。

每個結(jié)點(diǎn)單元由兩部分組成：數(shù)據(jù)域和指針域，其中數(shù)據(jù)域用來存儲數(shù)據(jù)，指針域用來存儲下一結(jié)點(diǎn)的地址。

因此，每個結(jié)點(diǎn)的結(jié)構(gòu)體可以表示為：

struct node { 數(shù)據(jù)域;struct node *next;//指針域 }

單鏈表的示意圖如下：

為避免博文篇幅過長，博主將單鏈表的插入、刪除、查找、遍歷等操作的細(xì)節(jié)及C語言實(shí)現(xiàn)整理到了《數(shù)據(jù)結(jié)構(gòu)》專欄中，鏈接如下：

單鏈表的詳解及實(shí)現(xiàn)見單鏈表及C語言實(shí)現(xiàn)

單鏈表所有相關(guān)操作實(shí)現(xiàn)的代碼見Github

雙鏈表

雙鏈表也叫雙向鏈表，如下圖所示，不同于單鏈表，對于任意一個結(jié)點(diǎn)，鏈表是“雙向”的：每一個結(jié)點(diǎn)都包含指針pre（用于指向當(dāng)前結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)），數(shù)據(jù)域（用于存儲數(shù)據(jù)元素）和指針next（用于指向當(dāng)前結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)）。

雙鏈表中結(jié)點(diǎn)的結(jié)構(gòu)體如下所示：

struct node { struct node *pre; 數(shù)據(jù)域; struct node *next; }

為避免博文篇幅過長，博主將雙鏈表的插入、刪除、查找、遍歷等操作的細(xì)節(jié)及C語言實(shí)現(xiàn)整理到了《數(shù)據(jù)結(jié)構(gòu)》專欄中，鏈接如下：

雙鏈表的詳解及實(shí)現(xiàn)見雙鏈表及C語言實(shí)現(xiàn)

雙鏈表所有相關(guān)操作實(shí)現(xiàn)的代碼見Github

循環(huán)單鏈表

單鏈表中，鏈表的最后一個結(jié)點(diǎn)的指針為NULL，每次遍歷單鏈表都需要從頭結(jié)點(diǎn)開始訪問。

不同于單鏈表，循環(huán)單鏈表的示意圖如下所示，循環(huán)單鏈表的尾結(jié)點(diǎn)的指針不為空，其指向了頭結(jié)點(diǎn)，這樣一來每次遍歷單鏈表就不一定非得從頭結(jié)點(diǎn)開始，從任意結(jié)點(diǎn)都可以遍歷整個循環(huán)單鏈表。

循環(huán)單鏈表的結(jié)構(gòu)體和單鏈表的結(jié)構(gòu)體一樣：

struct node { 數(shù)據(jù)域;struct node *next; }

為避免博文篇幅過長，博主將循環(huán)單鏈表的插入、刪除、查找、遍歷等操作的細(xì)節(jié)及C語言實(shí)現(xiàn)整理到了《數(shù)據(jù)結(jié)構(gòu)》專欄中，鏈接如下：

循環(huán)單鏈表的詳解及實(shí)現(xiàn)見循環(huán)單鏈表及C語言實(shí)現(xiàn)

循環(huán)單鏈表所有相關(guān)操作實(shí)現(xiàn)的代碼見Github

循環(huán)雙鏈表

雙鏈表中，每個結(jié)點(diǎn)單元都有一個數(shù)據(jù)域和兩個指針域，每個結(jié)點(diǎn)的pre指針指向上一個結(jié)點(diǎn)（若為頭結(jié)點(diǎn)則指向NULL），每個結(jié)點(diǎn)的next指針指向下一個結(jié)點(diǎn)（若為尾節(jié)點(diǎn)則指向NULL）。

循環(huán)雙鏈表與雙鏈表大體差不多，只是在頭結(jié)點(diǎn)和尾節(jié)點(diǎn)有所區(qū)別：

頭結(jié)點(diǎn)的pre指針指向尾結(jié)點(diǎn)

尾結(jié)點(diǎn)的next指針指向頭結(jié)點(diǎn)

因此，循環(huán)雙鏈表的任何結(jié)點(diǎn)都不包含NULL

循環(huán)雙鏈表的示意圖如下：

循環(huán)雙鏈表的結(jié)構(gòu)體與雙鏈表一樣：

struct node { struct node *pre; 數(shù)據(jù)域; struct node *next; }

為避免博文篇幅過長，博主將循環(huán)雙鏈表的插入、刪除、查找、遍歷等操作的細(xì)節(jié)及C語言實(shí)現(xiàn)整理到了《數(shù)據(jù)結(jié)構(gòu)》專欄中，鏈接如下：

循環(huán)雙鏈表的詳解及實(shí)現(xiàn)見循環(huán)雙鏈表及C語言實(shí)現(xiàn)

循環(huán)雙鏈表所有相關(guān)操作實(shí)現(xiàn)的代碼見Github

小結(jié)

對以上鏈表所有操作做一總結(jié)我們可以發(fā)現(xiàn)：鏈表里所有定義的指針都應(yīng)該被用到（要么指向NULL，要么指向某一結(jié)點(diǎn)），只要記住這一點(diǎn)我們對鏈表的操作就游刃有余了：
1. 單鏈表尾結(jié)點(diǎn)的next指向NULL
2. 雙鏈表頭結(jié)點(diǎn)pre指向NULL，尾結(jié)點(diǎn)的next指向NULL
3. 循環(huán)單鏈表尾結(jié)點(diǎn)的next指向head
4. 循環(huán)雙鏈表尾結(jié)點(diǎn)的next指向head，頭結(jié)點(diǎn)的pre指向尾結(jié)點(diǎn)

堆棧

堆棧，也稱為棧，是一種只能在一端（稱為棧頂）對數(shù)據(jù)項(xiàng)進(jìn)行操作的一種數(shù)據(jù)結(jié)構(gòu)。

數(shù)據(jù)的操作有兩種：

插入，稱為入棧

刪除，稱為出棧

堆棧的示意圖如下：

由于只能在頂端執(zhí)行插入和刪除，因此最先插入堆棧的元素將最后從堆棧中刪除，因此，有時堆棧被稱為后進(jìn)先出（Last In First Out，LIFO）列表。

堆棧的數(shù)組實(shí)現(xiàn)

為避免博文篇幅過長，博主將堆棧的C語言數(shù)組實(shí)現(xiàn)的細(xì)節(jié)及C語言實(shí)現(xiàn)整理到了《數(shù)據(jù)結(jié)構(gòu)》專欄中，鏈接如下：

堆棧數(shù)組實(shí)現(xiàn)的詳解見堆棧的數(shù)組實(shí)現(xiàn)（C語言）

堆棧所有相關(guān)操作數(shù)組實(shí)現(xiàn)的代碼見Github

堆棧的鏈表實(shí)現(xiàn)

為避免博文篇幅過長，博主將堆棧的C語言鏈表實(shí)現(xiàn)的細(xì)節(jié)及C語言實(shí)現(xiàn)整理到了《數(shù)據(jù)結(jié)構(gòu)》專欄中，鏈接如下：

堆棧鏈表實(shí)現(xiàn)的詳解見堆棧的鏈表實(shí)現(xiàn)（C語言）

堆棧所有相關(guān)操作鏈表實(shí)現(xiàn)的代碼見Github

隊(duì)列

隊(duì)列是一種允許在一端（隊(duì)尾，rear）進(jìn)行插入操作，另一端（隊(duì)頭，front）進(jìn)行刪除操作的數(shù)據(jù)結(jié)構(gòu)。

插入：在隊(duì)尾進(jìn)行，也稱為入隊(duì)

刪除：在隊(duì)頭進(jìn)行，也稱為出隊(duì)

隊(duì)列的示意圖如下：

隊(duì)列只能在一端進(jìn)行插入，另一端進(jìn)行刪除，從示意圖可以看出，隊(duì)列里的元素是按照入隊(duì)的順序出隊(duì)的（因此隊(duì)列經(jīng)常被用在排隊(duì)等候類的應(yīng)用中）。

根據(jù)隊(duì)列的特征，隊(duì)列也被稱為先進(jìn)先出（First In First Out，FIFO）列表。

隊(duì)列的數(shù)組實(shí)現(xiàn)

為避免博文篇幅過長，博主將隊(duì)列的C語言數(shù)組實(shí)現(xiàn)的細(xì)節(jié)及C語言實(shí)現(xiàn)整理到了《數(shù)據(jù)結(jié)構(gòu)》專欄中，鏈接如下：

隊(duì)列數(shù)組實(shí)現(xiàn)的詳解見隊(duì)列的數(shù)組實(shí)現(xiàn)（C語言）

隊(duì)列所有相關(guān)操作數(shù)組實(shí)現(xiàn)的代碼見Github

隊(duì)列的鏈表實(shí)現(xiàn)

為避免博文篇幅過長，博主將隊(duì)列的C語言鏈表實(shí)現(xiàn)的細(xì)節(jié)及C語言實(shí)現(xiàn)整理到了《數(shù)據(jù)結(jié)構(gòu)》專欄中，鏈接如下：

隊(duì)列鏈表實(shí)現(xiàn)的詳解見隊(duì)列的鏈表實(shí)現(xiàn)（C語言）

隊(duì)列所有相關(guān)操作鏈表實(shí)現(xiàn)的代碼見Github

循環(huán)隊(duì)列

循環(huán)隊(duì)列是為了解決數(shù)組隊(duì)列的“假溢出”現(xiàn)象以提高空間利用率而提出的。

為避免博文篇幅過長，博主將隊(duì)列的C語言鏈表實(shí)現(xiàn)的細(xì)節(jié)及C語言實(shí)現(xiàn)整理到了《數(shù)據(jù)結(jié)構(gòu)》專欄中，鏈接如下：

循環(huán)隊(duì)列的詳解及實(shí)現(xiàn)見循環(huán)隊(duì)列及C語言實(shí)現(xiàn)

循環(huán)隊(duì)列所有相關(guān)操作實(shí)現(xiàn)的代碼見Github

樹

樹是由有限個結(jié)點(diǎn)組成的具有層次關(guān)系的集合，在邏輯關(guān)系上看起來像一顆倒掛的樹而得名，包括無序樹，有序樹，二叉樹，哈夫曼樹等

二叉樹

二叉樹是一種樹型結(jié)構(gòu)，其特點(diǎn)是每個結(jié)點(diǎn)至多有兩顆子樹，這兩顆子樹有左右之分，順序不能顛倒。如圖就是一個二叉樹的例子：

• 除最后一層外，其他層的結(jié)點(diǎn)均有2個結(jié)點(diǎn)的二叉樹稱為滿二叉樹
• 對滿二叉樹按照從上到下，從左到右的順序編號，如果有一個二叉樹不是滿二叉樹，該樹的編號又與滿二叉樹的編號對應(yīng)，則稱為完全二叉樹

二叉樹的性質(zhì)

二叉樹每個結(jié)點(diǎn)至多有兩棵子樹，因此如果二叉樹的每個節(jié)點(diǎn)都都包含至多即2個結(jié)點(diǎn)，即滿二叉樹，則

• 第$i$層上有$2^{i?1}$個結(jié)點(diǎn)（$i\ge 1$）
• 深度為$k$的二叉樹有$2^k?1$個結(jié)點(diǎn)

任何一顆二叉樹，如果其終端結(jié)點(diǎn)（沒有子樹的結(jié)點(diǎn)）數(shù)為$n_e$，度為2的結(jié)點(diǎn)數(shù)為$n_2$，則

• $n_e=n_2+1$

具有n個結(jié)點(diǎn)的完全二叉樹的深度為

• $?lo{g}_{2}n+1?$

為避免博文篇幅過長，博主將二叉樹的操作細(xì)節(jié)及C語言實(shí)現(xiàn)整理到了《數(shù)據(jù)結(jié)構(gòu)》專欄中，鏈接如下：

二叉樹的詳解及實(shí)現(xiàn)見二叉樹及C語言實(shí)現(xiàn)

二叉樹所有相關(guān)操作實(shí)現(xiàn)的代碼見Github

二叉搜索樹

為避免博文篇幅過長，博主將二叉搜索樹的操作細(xì)節(jié)及C語言實(shí)現(xiàn)整理到了《數(shù)據(jù)結(jié)構(gòu)》專欄中，鏈接如下：

二叉搜索樹的詳解及實(shí)現(xiàn)見二叉搜索樹及C語言實(shí)現(xiàn)

二叉搜索樹所有相關(guān)操作實(shí)現(xiàn)的代碼見Github

平衡搜索樹（AVL）

為避免博文篇幅過長，博主將平衡搜索樹的操作細(xì)節(jié)及C語言實(shí)現(xiàn)整理到了《數(shù)據(jù)結(jié)構(gòu)》專欄中，鏈接如下：

平衡搜索樹（AVL）的詳解及實(shí)現(xiàn)見平衡搜索樹（AVL）及C語言實(shí)現(xiàn)

平衡搜索樹所有相關(guān)操作實(shí)現(xiàn)的代碼見Github

B樹

為避免博文篇幅過長，博主將B樹的操作細(xì)節(jié)及C語言實(shí)現(xiàn)整理到了《數(shù)據(jù)結(jié)構(gòu)》專欄中，鏈接如下：

B樹的詳解及實(shí)現(xiàn)見B樹及C語言實(shí)現(xiàn)

B樹所有相關(guān)操作實(shí)現(xiàn)的代碼見Github

B+樹

為避免博文篇幅過長，博主將B+樹的操作細(xì)節(jié)及C語言實(shí)現(xiàn)整理到了《數(shù)據(jù)結(jié)構(gòu)》專欄中，鏈接如下：

B+樹的詳解及實(shí)現(xiàn)見及C語言實(shí)現(xiàn)

B+樹所有相關(guān)操作實(shí)現(xiàn)的代碼見Github

圖

廣度優(yōu)先搜索（BFS）

為避免博文篇幅過長，博主將廣度優(yōu)先搜索的操作細(xì)節(jié)及C語言實(shí)現(xiàn)整理到了《數(shù)據(jù)結(jié)構(gòu)》專欄中，鏈接如下：

廣度優(yōu)先搜索（BFS）的詳解及實(shí)現(xiàn)見廣度優(yōu)先搜索（BFS）及C語言實(shí)現(xiàn)

BFS所有相關(guān)操作實(shí)現(xiàn)的代碼見Github

深度優(yōu)先搜索（DFS）

為避免博文篇幅過長，博主將深度優(yōu)先搜索的操作細(xì)節(jié)及C語言實(shí)現(xiàn)整理到了《數(shù)據(jù)結(jié)構(gòu)》專欄中，鏈接如下：

深度優(yōu)先搜索（DFS）的詳解及實(shí)現(xiàn)見深度優(yōu)先搜索（DFS）及C語言實(shí)現(xiàn)

DFS所有相關(guān)操作實(shí)現(xiàn)的代碼見Github

生成樹

為避免博文篇幅過長，博主將生成樹的操作細(xì)節(jié)及C語言實(shí)現(xiàn)整理到了《數(shù)據(jù)結(jié)構(gòu)》專欄中，鏈接如下：

生成樹的詳解及實(shí)現(xiàn)見生成樹及C語言實(shí)現(xiàn)

生成樹所有相關(guān)操作實(shí)現(xiàn)的代碼見Github

博主正在完善中......

才疏學(xué)淺，難免有錯誤和不當(dāng)之處，歡迎交流批評指正!
同時有問題的話歡迎留言或郵箱聯(lián)系（ljt_IT@163.com）。

創(chuàng)作不易，覺得寫得不錯就微信掃碼獎勵一下吧！

總結(jié)

以上是生活随笔為你收集整理的数据结构教程（详细又简单——C语言实现）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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