云南省網(wǎng)站建設(shè)收費(fèi)調(diào)查報告論文專業(yè)seo排名優(yōu)化費(fèi)用
目錄
一、樹概念及結(jié)構(gòu)
二、二叉樹樹概念及結(jié)構(gòu)
?特殊的二叉樹
三、堆的概念及結(jié)構(gòu)
四、堆的創(chuàng)建
1、聲明結(jié)構(gòu)體
2、初始化?
3、銷毀
4、添加新元素
5、交換元素?
6、向上調(diào)整
7、判斷堆是否為空
8、移除堆頂元素
9、向下調(diào)整
10、獲取堆元素個數(shù)?
五、使用堆排序
?排降序建小堆
?完整版:
Heap.h聲明部分
Heap.c函數(shù)部分
text.c使用及測試部分
一、樹概念及結(jié)構(gòu)
樹是一種非線性的數(shù)據(jù)結(jié)構(gòu),它是由n(n>=0)個有限結(jié)點(diǎn)組成一個具有層次關(guān)系的集合。把它叫做樹是因 為它看起來像一棵倒掛的樹,也就是說它是根朝上,而葉朝下的。
- 有一個特殊的結(jié)點(diǎn),稱為根結(jié)點(diǎn),根節(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)。
- 除根節(jié)點(diǎn)外,其余結(jié)點(diǎn)被分成M(M>0)個互不相交的集合T1、T2、……、Tm,其中每一個集合Ti(1 <= i <= m)又是一棵結(jié)構(gòu)與樹類似的子樹。每棵子樹的根結(jié)點(diǎn)有且只有一個前驅(qū),可以有0個或多個后繼。
- 因此,樹是遞歸定義的
- 注意:樹形結(jié)構(gòu)中,子樹之間不能有交集,否則就不是樹形結(jié)構(gòu)
- 節(jié)點(diǎn)的度:一個節(jié)點(diǎn)含有的子樹的個數(shù)稱為該節(jié)點(diǎn)的度; 如上圖:A的為6
- 葉節(jié)點(diǎn)或終端節(jié)點(diǎn):度為0的節(jié)點(diǎn)稱為葉節(jié)點(diǎn); 如上圖:B、C、H、I...等節(jié)點(diǎn)為葉節(jié)點(diǎn)
- 非終端節(jié)點(diǎn)或分支節(jié)點(diǎn):度不為0的節(jié)點(diǎn); 如上圖:D、E、F、G...等節(jié)點(diǎn)為分支節(jié)點(diǎn)
- 雙親節(jié)點(diǎn)或父節(jié)點(diǎn):若一個節(jié)點(diǎn)含有子節(jié)點(diǎn),則這個節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn); 如上圖:A是B的父節(jié)點(diǎn)
- 孩子節(jié)點(diǎn)或子節(jié)點(diǎn):一個節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn); 如上圖:B是A的孩子節(jié)點(diǎn)
- 兄弟節(jié)點(diǎn):具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn); 如上圖:B、C是兄弟節(jié)點(diǎn)
- 樹的度:一棵樹中,最大的節(jié)點(diǎn)的度稱為樹的度; 如上圖:樹的度為6
- 節(jié)點(diǎn)的層次:從根開始定義起,根為第1層,根的子節(jié)點(diǎn)為第2層,以此類推;
- 樹的高度或深度:樹中節(jié)點(diǎn)的最大層次; 如上圖:樹的高度為4
- 堂兄弟節(jié)點(diǎn):雙親在同一層的節(jié)點(diǎn)互為堂兄弟;如上圖:H、I互為兄弟節(jié)點(diǎn)
- 節(jié)點(diǎn)的祖先:從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn);如上圖:A是所有節(jié)點(diǎn)的祖先
- 子孫:以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。如上圖:所有節(jié)點(diǎn)都是A的子孫
- 森林:由m(m>0)棵互不相交的樹的集合稱為森林;
二、二叉樹樹概念及結(jié)構(gòu)
二叉樹是一個由n(n>=0)個結(jié)點(diǎn)構(gòu)成的有限集合,其中該集合可以為空,這時稱其為空二叉樹;或者由一個根結(jié)點(diǎn)以及兩個互不相交的左子樹和右子樹組成,且左右子樹均為二叉樹。在二叉樹中,子樹被明確區(qū)分為左子樹和右子樹,且它們的順序不可顛倒。
- 值得注意的是,二叉樹的定義具有遞歸性質(zhì),因?yàn)槎鏄浔旧砜梢詾榭?#xff0c;根結(jié)點(diǎn)可以有空的左子樹或空的右子樹。
- 這使得二叉樹與普通樹有明顯的區(qū)別,即使只有一棵子樹存在,也需要明確指定它是左子樹還是右子樹。這是二叉樹與樹最主要的區(qū)別之一。
- 請注意,二叉樹不同于一般的樹,因?yàn)樗淖訕渚哂凶笥抑?#xff0c;并且順序不能顛倒。因此,“二叉樹是結(jié)點(diǎn)度為2的樹”的說法是不正確的。
二叉樹的基本形態(tài)包括以下五種:
?特殊的二叉樹
當(dāng)涉及到二叉樹的特殊類型時,有兩個主要概念需要了解:滿二叉樹和完全二叉樹。
- 滿二叉樹:滿二叉樹是一種特殊的二叉樹,其特點(diǎn)是每個層級的結(jié)點(diǎn)數(shù)都達(dá)到最大值。具體來說,如果一個二叉樹的深度為K,且結(jié)點(diǎn)總數(shù)為2^K - 1,那么它就是一個滿二叉樹。滿二叉樹的每一層都包含最大數(shù)量的結(jié)點(diǎn),使得它具有很特殊的結(jié)構(gòu)。
- 完全二叉樹:完全二叉樹是一種高效的數(shù)據(jù)結(jié)構(gòu),與滿二叉樹相關(guān)。一個二叉樹如果在深度為K的情況下,其結(jié)點(diǎn)都與深度為K的滿二叉樹中的編號從1到n的結(jié)點(diǎn)一一對應(yīng),那么它就被稱為完全二叉樹。需要注意的是,滿二叉樹是完全二叉樹的一個特殊情況。
- 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1,則一棵非空二叉樹的第i層上最多有
個結(jié)點(diǎn)。
- 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1,則深度為h的二叉樹的最大結(jié)點(diǎn)數(shù)是
。
- 對任何一棵二叉樹, 如果度為0其葉結(jié)點(diǎn)個數(shù)為 n0?, 度為2的分支結(jié)點(diǎn)個數(shù)為 n2?,則有 n0 =n2?+1。
- 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1,具有n個結(jié)點(diǎn)的滿二叉樹的深度,h=log以2為底,n+1的對數(shù)。
- 對于具有n個結(jié)點(diǎn)的完全二叉樹,如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點(diǎn)從0開始編號,則對于序號為i的結(jié)點(diǎn)有:
- 若i>0,i位置節(jié)點(diǎn)的雙親序號:(i-1)/2;i=0,i為根節(jié)點(diǎn)編號,無雙親節(jié)點(diǎn)
- 若2i+1<n,左孩子序號:2i+1,2i+1>=n否則無左孩子
- 若2i+2<n,右孩子序號:2i+2,2i+2>=n否則無右孩子
?
三、堆的概念及結(jié)構(gòu)
堆(Heap)是一種特殊的樹狀數(shù)據(jù)結(jié)構(gòu),通常用于實(shí)現(xiàn)優(yōu)先隊列和對數(shù)據(jù)進(jìn)行排序。堆的主要特點(diǎn)是它是一棵樹,其中每個節(jié)點(diǎn)的值滿足特定的堆屬性。在堆中,通常有兩種主要類型:最大堆和最小堆。
最大堆(Max Heap):在最大堆中,每個節(jié)點(diǎn)的值都不小于其子節(jié)點(diǎn)的值,即根節(jié)點(diǎn)的值最大。這意味著最大堆的最大元素總是位于根節(jié)點(diǎn),而子樹中的值遞減。
最小堆(Min Heap):在最小堆中,每個節(jié)點(diǎn)的值都不大于其子節(jié)點(diǎn)的值,即根節(jié)點(diǎn)的值最小。這意味著最小堆的最小元素總是位于根節(jié)點(diǎn),而子樹中的值遞增。
堆的常見用途包括:
優(yōu)先隊列:堆可以用來實(shí)現(xiàn)高效的優(yōu)先隊列,使得可以快速訪問和刪除具有最高或最低優(yōu)先級的元素。
堆排序:堆排序是一種高效的排序算法,它利用堆的性質(zhì)來進(jìn)行排序。它的時間復(fù)雜度為O(n log n)。
堆通常是以數(shù)組的形式來表示,其中父節(jié)點(diǎn)和子節(jié)點(diǎn)之間的關(guān)系通過數(shù)組索引來建立。具體來說,對于一個具有n個元素的堆,節(jié)點(diǎn)的索引從1到n編號,其中:
- 父節(jié)點(diǎn)的索引為i,則它的左子節(jié)點(diǎn)的索引為2i,右子節(jié)點(diǎn)的索引為2i + 1。
- 子節(jié)點(diǎn)的索引為i,則其父節(jié)點(diǎn)的索引為i/2。
這種數(shù)組表示方法使得堆的操作更加高效,因?yàn)樗恍枰褂妙~外的指針來表示樹的結(jié)構(gòu)。
四、堆的創(chuàng)建
本次以小堆舉例進(jìn)行講解?
1、聲明結(jié)構(gòu)體
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;
HPDataType
?被定義為?int
?類型,表示堆中存儲的數(shù)據(jù)類型。- 創(chuàng)建堆的結(jié)構(gòu)體Heap,定義別名為HP。
- 指針a指向堆的數(shù)組
- size為堆的當(dāng)前大小
- capacity為堆的容量
2、初始化?
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}
- assert 判斷指針是否合法。
- 指向數(shù)組的指針 a 初始化為 NULL。
- size 和 capacity 初始化為0。
3、銷毀
void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}
- assert 判斷指針是否合法。
- 釋放數(shù)組空間,將 a 指針置空,同時將 capacity 和 size 設(shè)置為0。
4、添加新元素
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");return;}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}
- assert 判斷指針是否合法。
- 判斷當(dāng)前是否需要擴(kuò)容,初始堆的容量為0,則為堆開辟四個HPDataType類型大小的空間,如果當(dāng)前堆的大小size等于容量capacity,則將堆擴(kuò)容為兩倍原來大小的空間。
- 擴(kuò)容失敗,打印錯誤信息,結(jié)束函數(shù)
- 將擴(kuò)容的空間賦值給指針a,更新容量capacity的大小。
- 將要增加的元素插入數(shù)組a中,更新size大小。
- 每次在堆中添加新元素時,小堆可能會被破壞,所以我們再添加新元素后,要在AdjustUp函數(shù)中判斷是否需要進(jìn)行向上調(diào)整。
5、交換元素?
后續(xù)函數(shù)會經(jīng)常用到,同一串代碼放到函數(shù)里供其使用者調(diào)用比較好。?
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}
6、向上調(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;}}
}
- 首先通過當(dāng)前的孩子節(jié)點(diǎn)child找到父節(jié)點(diǎn)parent。
- 當(dāng)child大于0時,進(jìn)行判斷當(dāng)前chilid是否需要調(diào)整
- 如果child位置元素小于parent位置元素,則通過Swap進(jìn)行交換,然后新的孩子節(jié)點(diǎn)更新為parent位置,通過孩子節(jié)點(diǎn)更新新的父節(jié)點(diǎn)位置,然后繼續(xù)比較和交換,直到不再需要交換為止。
- 如果當(dāng)前孩子節(jié)點(diǎn)不小于當(dāng)前的父節(jié)點(diǎn),則結(jié)束循環(huán),當(dāng)前節(jié)點(diǎn)不需要向上調(diào)整。
7、判斷堆是否為空
bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}
8、移除堆頂元素
?一般來說,堆的移除操作通常是移除堆頂元素,這樣大堆小堆的性質(zhì)保持不變,如果移除堆底會破壞堆的性質(zhì)。
void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}
- assert 判斷指針是否合法。
- 檢查堆是否為空,為空則報錯。
- 移除堆頂元素有兩種方法,首選第二種方法,不需要重新建堆,節(jié)約時間。
- 首先交換堆頂堆尾,然后size減一完成刪除,后續(xù)不會訪問刪除位置的元素,所以不釋放內(nèi)存空間也可以。
- 然后進(jìn)行向下調(diào)整。
9、向下調(diào)整
向下調(diào)整是從第一個節(jié)點(diǎn)(父節(jié)點(diǎn))開始向下調(diào)整,傳入?yún)?shù)命名為parent?
void AdjustDown(HPDataType* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size) {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;}}
}
- 通過傳入?yún)?shù)獲取到當(dāng)前的左子節(jié)點(diǎn)的位置。
- 當(dāng)child位置小于數(shù)組元素個數(shù)時進(jìn)行判斷。
- 進(jìn)入循環(huán),首先判斷檢查右子節(jié)點(diǎn)是否存在并且比左子節(jié)點(diǎn)的值小,如果是,將?
child
?更新為右子節(jié)點(diǎn)的索引,以確保選擇更小的子節(jié)點(diǎn)進(jìn)行比較。 - 比較選定的子節(jié)點(diǎn)的值與父節(jié)點(diǎn)的值,如果子節(jié)點(diǎn)的值小于父節(jié)點(diǎn)的值,就交換它們。
- 更新parent為新的子節(jié)點(diǎn)位置,更新child為新的左子節(jié)點(diǎn)位置,然后繼續(xù)比較和交換,直到不再需要交換為止。
- 如果當(dāng)前子節(jié)點(diǎn)不小于當(dāng)前父節(jié)點(diǎn)則停止循環(huán)。
10、獲取堆元素個數(shù)?
int HeapSize(HP* php)
{assert(php);return php->size;
}
五、使用堆排序
void HeapSort(int* a, int n)
{HP hp;HeapInit(&hp);// 時間復(fù)雜度:N*logNfor (int i = 0; i < n; ++i){HeapPush(&hp, a[i]);}// 時間復(fù)雜度:N*logNint i = 0;while (!HeapEmpty(&hp)){int top = HeapTop(&hp);a[i++] = top;HeapPop(&hp);}HeapDestroy(&hp);
}
可以使用這種方式,但有諸多弊端:?
- 要先有一個堆,太麻煩。
- 空間復(fù)雜度+拷貝數(shù)據(jù)
?排降序建小堆
所以我們要在傳入的原數(shù)組上排降序,需要使用建小堆的方式向上調(diào)整。
void HeapSort(int* a, int n)
{// 建堆--向上調(diào)整建堆for (int i = 1; i < n; i++){AdjustUp(a, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);// 再調(diào)整,選出次小的數(shù)AdjustDown(a, end, 0);--end;}
}
- 從根節(jié)點(diǎn)的子節(jié)點(diǎn)開始向上建堆,除了根節(jié)點(diǎn)以外,每個節(jié)點(diǎn)都進(jìn)行向上調(diào)整。
- 定義堆的最后一個節(jié)點(diǎn)end為n-1
- 我們將堆的根節(jié)點(diǎn)(也就是最小值)與堆的最后一個元素交換,即將最小值放到排序尾部即為好的部分。接下來,通過調(diào)用
AdjustDown
函數(shù),將堆的大小減一,再次將堆調(diào)整為最小堆。 - 重復(fù)while循環(huán)內(nèi)部操作,直到整個數(shù)組排序完成。每次交換和堆的調(diào)整都會將最小的元素添加到已排序的部分,直到整個數(shù)組都有序。
HeapSort的時間復(fù)雜度為O(nlog(n)),它不需要額外的空間來存儲數(shù)據(jù),所以是一種原地排序算法。它在最壞情況下的性能仍然是O(nlog(n)),因此相對穩(wěn)定,適用于大規(guī)模數(shù)據(jù)的排序。?
我們也可以向下建堆:
倒著調(diào)整葉子節(jié)點(diǎn)不需要處理,從倒樹第一個非葉子節(jié)點(diǎn)開始,即最后一個節(jié)點(diǎn)的父節(jié)點(diǎn)開始調(diào)整。
void HeapSort(int* a, int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; --i){ AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);// 再調(diào)整,選出次小的數(shù)AdjustDown(a, end, 0);--end;}
}
?完整版:
Heap.h聲明部分
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;void HeapInit(HP* php);
void HeapDestroy(HP* php);void AdjustUp(HPDataType* a, int child);
void HeapPush(HP* php, HPDataType x);
bool HeapEmpty(HP* php);
void AdjustDown(int* a, int n, int parent);
void HeapPop(HP* php);HPDataType HeapTop(HP* php);
int HeapSize(HP* php);
Heap.c函數(shù)部分
#include "Heap.h"void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}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;}}
}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");return;}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}bool HeapEmpty(HP* php)
{assert(php);return php->size==0;
}
void AdjustDown(HPDataType* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size) {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;}}
}void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}HPDataType HeapTop(HP* php)
{assert(php);assert(!HeapEmpty(php));return php->a[0];
}int HeapSize(HP* php)
{assert(php);return php->size;
}
text.c使用及測試部分
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"void HeapSort(int* a, int n)
{// 建堆--向上調(diào)整建堆for (int i = 1; i < n; i++){AdjustUp(a, i);}// 建堆--向下調(diào)整建堆//for (int i = (n - 1 - 1) / 2; i >= 0; --i)//{// AdjustDown(a, n, i);//}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);// 再調(diào)整,選出次小的數(shù)AdjustDown(a, end, 0);--end;}
}int main()
{int a[] = { 7,8,3,5,1,9,5,4 };HeapSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < 8; i++) {printf("%d ", a[i]);}return 0;
}//---測試堆函數(shù)功能---
//int main()
//{
// HP hp;
// HeapInit(&hp);
// int a[] = { 65,100,70,32,50,60 };
// for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
// {
// HeapPush(&hp, a[i]);
// }
//
// while (!HeapEmpty(&hp))
// {
// int top = HeapTop(&hp);
// printf("%d\n", top);
// HeapPop(&hp);
// }
//
// return 0;
//}