專欄引入

哈嘍大家好，我是野生的編程萌新，首先感謝大家的觀看。數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)者大多有這樣的想法：數(shù)據(jù)結(jié)構(gòu)很重要，一定要學(xué)好，但數(shù)據(jù)結(jié)構(gòu)比較抽象，有些算法理解起來很困難，學(xué)的很累。我想讓大家知道的是：數(shù)據(jù)結(jié)構(gòu)非常有趣，很多算法是智慧的結(jié)晶，我希望大家在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的過程是一種愉悅的心情感受。因此我開創(chuàng)了《數(shù)據(jù)結(jié)構(gòu)》專欄，在這里我將把數(shù)據(jù)結(jié)構(gòu)內(nèi)容以有趣易懂的方式展現(xiàn)給大家。

1.二叉樹的順序存儲(chǔ)結(jié)構(gòu)?

之前我們談過了樹的存儲(chǔ)結(jié)構(gòu)，并且談到了順序存儲(chǔ)結(jié)構(gòu)對(duì)樹這種一對(duì)多的關(guān)系結(jié)構(gòu)實(shí)現(xiàn)起來還是比較困難的。但二叉樹是一種特殊的樹，由于二叉樹的特殊性，使得它可以使用順序存儲(chǔ)結(jié)構(gòu)來實(shí)現(xiàn)，二叉樹的順序存儲(chǔ)結(jié)構(gòu)就是使用一維數(shù)組存儲(chǔ)二叉樹中的節(jié)點(diǎn)，并且節(jié)點(diǎn)的存儲(chǔ)位置，也就是數(shù)組的下標(biāo)要能體現(xiàn)出來節(jié)點(diǎn)之間的邏輯關(guān)系，比如：雙親和孩子的關(guān)系、左孩子右兄弟的關(guān)系等。先來看看完全二叉樹的順序存儲(chǔ)，就用下面這棵二叉樹為例：

將這棵二叉樹存入數(shù)組中，相應(yīng)的下標(biāo)對(duì)應(yīng)其同樣的位置，很多數(shù)據(jù)結(jié)構(gòu)相關(guān)書籍上下標(biāo)都是將0空置，從1開始存儲(chǔ)，其實(shí)下標(biāo)0的位置是否存放數(shù)據(jù)對(duì)堆的實(shí)現(xiàn)的難度沒有影響，為了節(jié)省空間我對(duì)下標(biāo)為0的位置進(jìn)行了存儲(chǔ)，如下圖：

這下我們可以看出來完全二叉樹的優(yōu)越性了吧，由于它嚴(yán)格的定義，所以用順序結(jié)構(gòu)也可以表現(xiàn)出二叉樹的結(jié)構(gòu)來，當(dāng)然對(duì)于一般的二叉樹，盡管層序編號(hào)不能反映出來邏輯關(guān)系，但是可以將其按完全二叉樹來編號(hào)，只不過，把不存在的節(jié)點(diǎn)設(shè)置為"NULL"而已，就像下面的圖中，虛線部分表示不存在：

?

?

我們?cè)倏紤]一種極端的情況：一顆深度為h的右斜樹。它只有h個(gè)節(jié)點(diǎn)，卻要分配個(gè)存儲(chǔ)單元空間，這顯然是對(duì)存儲(chǔ)空間的浪費(fèi)，如下圖所示：

?所以，二叉樹的順序存儲(chǔ)結(jié)構(gòu)一般只適用于完全二叉樹。上一篇中我們提到了堆是一個(gè)特殊的完全二叉樹，所以這篇我們就以堆為例子來實(shí)現(xiàn)二叉樹的順序存儲(chǔ)。

2.堆

2.1堆的概念

堆是具有下列性質(zhì)的完全二叉樹：每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子節(jié)點(diǎn)的值，稱為大頂堆；或者每個(gè)結(jié)點(diǎn)的值都小于等于其左右孩子結(jié)點(diǎn)的值，稱為小頂堆。如下圖所示：

從堆的定義可以知道：根節(jié)點(diǎn)一定是堆中所有結(jié)點(diǎn)的最大（小）值?。在上一篇堆二叉樹的性質(zhì)介紹時(shí)，有一個(gè)性質(zhì)還沒和大家介紹，因?yàn)檫@個(gè)性質(zhì)就仿佛是為堆量身定制的，所以我計(jì)劃在介紹堆時(shí)再介紹它：

如果一棵有n個(gè)節(jié)點(diǎn)的完全二叉樹（其深度為）的節(jié)點(diǎn)按層序編號(hào)（從第一層到第層，每層從左到右），對(duì)任一節(jié)點(diǎn)i（1≤i≤n）有：

• 如果i=1，則節(jié)點(diǎn)i是二叉樹的根，無雙親；如果i>1,則雙親是節(jié)點(diǎn)。
• 如果2i>n，則節(jié)點(diǎn)i沒有左孩子（節(jié)點(diǎn)i為葉子節(jié)點(diǎn)），否則其左孩子是節(jié)點(diǎn)2i。
• 如果2i+1>n，則節(jié)點(diǎn)i沒有右孩子；否則其右孩子是節(jié)點(diǎn)2i+1。

在這個(gè)性質(zhì)第二、三條，也就是說明下標(biāo)i與2i和2i+1的雙親子女的關(guān)系：雙親結(jié)點(diǎn)=（子節(jié)點(diǎn)-1）/2。

2.2堆的實(shí)現(xiàn)

我們先來定義一下堆的結(jié)構(gòu)：

typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;

2.2.1堆的創(chuàng)建和銷毀

堆的創(chuàng)建我們使用順序存儲(chǔ)來實(shí)現(xiàn)，所以它的創(chuàng)建和銷毀的實(shí)現(xiàn)代碼和順序表的實(shí)現(xiàn)的相同。首先是堆的創(chuàng)建函數(shù)：

void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}

接著是堆的銷毀函數(shù)：

void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

2.2.2堆的向上調(diào)整

一說到調(diào)整我們肯定會(huì)對(duì)兩個(gè)數(shù)據(jù)進(jìn)行交換，我們先來寫一個(gè)交換函數(shù)：

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}

堆的向上調(diào)整是將一個(gè)元素插入到小堆時(shí)，調(diào)整堆的結(jié)構(gòu)，使其滿足小堆的性質(zhì)過程。實(shí)現(xiàn)堆的向上調(diào)整的要先將元素插入到數(shù)組的最后一個(gè)位置（這一步我們?cè)诙训牟迦氩僮髦袑?shí)現(xiàn)）。這時(shí)候我們就要比較插入元素和其雙親結(jié)點(diǎn)的大小關(guān)系，然后做出調(diào)整。這里我們可以用循環(huán)實(shí)現(xiàn)，用循環(huán)來實(shí)現(xiàn)比用遞歸實(shí)現(xiàn)的好處有：

1. 空間開銷：循環(huán)實(shí)現(xiàn)通常比遞歸實(shí)現(xiàn)需要更少的內(nèi)存空間。遞歸函數(shù)會(huì)在每次調(diào)用時(shí)創(chuàng)建一個(gè)新的函數(shù)棧幀，而循環(huán)則只使用一個(gè)循環(huán)體內(nèi)的局部變量。
2. 性能：循環(huán)實(shí)現(xiàn)通常比遞歸實(shí)現(xiàn)具有更高的執(zhí)行效率。遞歸函數(shù)在每次調(diào)用時(shí)都需要進(jìn)行函數(shù)調(diào)用、參數(shù)傳遞和返回值處理等操作，而循環(huán)通過使用迭代變量和循環(huán)條件判斷來控制流程，避免了遞歸帶來的額外開銷。

首先我們先將這個(gè)函數(shù)里面的判斷條件先寫好：

void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

既然我們要用循環(huán)來實(shí)現(xiàn)，那么使用while()語(yǔ)句的循環(huán)條件是什么呢？最壞的情況就是將新插入的節(jié)點(diǎn)經(jīng)過調(diào)整變成根節(jié)點(diǎn)，那條件是parent≥0嗎？parent是不會(huì)小于0的，當(dāng)parent=0時(shí)，插入的數(shù)據(jù)還要接著向上調(diào)整交換，此時(shí)child變?yōu)?，parent=(0-1)/2，我們計(jì)算出來的parent時(shí)-0.5，但是要取整，所以parent還是0，此時(shí)循環(huán)還是沒結(jié)束，會(huì)再次進(jìn)入循環(huán)，此時(shí)child==parent，經(jīng)過判斷語(yǔ)句會(huì)僥幸跳出循環(huán)，這樣是不嚴(yán)謹(jǐn)?shù)?。我們將循環(huán)條件設(shè)為child大于0就可以完美解決這個(gè)問題。此時(shí)，這個(gè)向上調(diào)整的操作完整代碼為：

void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

2.3堆的插入?

?堆的插入操作和順序表的插入操作相似，其具體步驟為：

1. 首先，函數(shù)開始時(shí)先進(jìn)行一些邊界判斷，確保堆的指針有效。
2. 如果堆的當(dāng)前元素?cái)?shù)量等于堆的容量，即堆已滿，需要進(jìn)行動(dòng)態(tài)擴(kuò)容。這里使用realloc函數(shù)對(duì)堆的數(shù)組進(jìn)行擴(kuò)容，新的容量為原來容量的兩倍。
3. 將待插入的元素x放到堆數(shù)組的最后一個(gè)位置，并將堆的元素?cái)?shù)量遞增。
4. 調(diào)用AdjustUp函數(shù)對(duì)剛插入的元素進(jìn)行向上調(diào)整，保持堆的性質(zhì)。

我們來實(shí)現(xiàn)一下這個(gè)操作：

void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

2.4堆的向下調(diào)整

堆的向上調(diào)整是為了讓堆在插入數(shù)據(jù)時(shí)能夠保持堆的性質(zhì)，而堆的向下調(diào)整操作是在刪除根節(jié)點(diǎn)后，為了維護(hù)堆的性質(zhì)而進(jìn)行的操作。該操作的目的是將新的根節(jié)點(diǎn)下沉到合適的位置，使得根節(jié)點(diǎn)的值不大于它的左右子節(jié)點(diǎn)的值。堆的向下調(diào)整具體步驟為：

1. 初始化子節(jié)點(diǎn)的索引child，設(shè)為父節(jié)點(diǎn)的左孩子節(jié)點(diǎn)的索引，即parent*2+1。
2. 進(jìn)入一個(gè)循環(huán)，判斷當(dāng)前節(jié)點(diǎn)是否有左孩子節(jié)點(diǎn)，如果有則執(zhí)行循環(huán)體。
3. 在循環(huán)體內(nèi)，先假設(shè)左孩子節(jié)點(diǎn)的值最小，將child設(shè)為左孩子節(jié)點(diǎn)的索引。
4. 檢查右孩子節(jié)點(diǎn)是否存在，即child+1<size，如果存在且右孩子節(jié)點(diǎn)的值小于左孩子節(jié)點(diǎn)的值，則將child更新為右孩子節(jié)點(diǎn)的索引。
5. 檢查當(dāng)前節(jié)點(diǎn)的值是否大于最小的子節(jié)點(diǎn)的值，如果是，則交換當(dāng)前節(jié)點(diǎn)和最小子節(jié)點(diǎn)的值，將當(dāng)前節(jié)點(diǎn)的索引設(shè)為子節(jié)點(diǎn)的索引child，并更新子節(jié)點(diǎn)的索引為新的左孩子節(jié)點(diǎn)的索引child=parent*2+1。
6. 如果當(dāng)前節(jié)點(diǎn)的值不大于最小子節(jié)點(diǎn)的值，即a[child]>=a[parent]，則跳出循環(huán)。
7. 重復(fù)之前的步驟，直到當(dāng)前節(jié)點(diǎn)沒有左孩子節(jié)點(diǎn)為止。

我們來具體實(shí)現(xiàn)一下這個(gè)操作：

void AdjustDown(int* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){// 假設(shè)左孩子小，如果解設(shè)錯(cuò)了，更新一下if (child+1 < size && a[child + 1] < a[child]){++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

?2.5堆的刪除

堆的刪除具體操作步驟為：

1. 調(diào)用Swap函數(shù)來交換小堆根節(jié)點(diǎn)（php->a[0]）和最后一個(gè)節(jié)點(diǎn)（php->a[php->size - 1]）的值。這樣就將要?jiǎng)h除的根節(jié)點(diǎn)移到了最后一個(gè)位置。
2. 將小堆的大小減1，即php->size--，表示刪除了一個(gè)節(jié)點(diǎn)。
3. 最后，調(diào)用AdjustDown函數(shù)來對(duì)小堆進(jìn)行向下調(diào)整，以維護(hù)小堆的性質(zhì)。這樣就完成了小堆的刪除操作。

我們來實(shí)現(xiàn)一下這個(gè)操作：

void HeapPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}