前言
1.雙親表示法
由于每個節(jié)點都 只有一個父節(jié)點 ，所以我們可通過雙親來表示一棵樹。具體方式通過數(shù)組的形式實現(xiàn)。
下標(biāo)規(guī)律
- 根節(jié)點的下標(biāo)為0
- 按照層序從上到下排序
- 每層從左向右遞增
表示形式:
存儲方式
- 二維數(shù)組
- 數(shù)據(jù)的列標(biāo)為0，只需確定行標(biāo)，即可鎖定位置
- 根節(jié)點的父節(jié)點下標(biāo)為 -1
- 列標(biāo)為1存父節(jié)點，所存數(shù)據(jù)是父節(jié)點的行標(biāo)
2.完全二叉樹結(jié)論
完全二叉樹孩子節(jié)點的計算
- 前提：節(jié)點的左右孩子均存在
- 設(shè)節(jié)點的下標(biāo)為N
- 左孩子下標(biāo) = 2*N+1
- 右孩子下標(biāo) = 2*N+2
完全二叉樹父節(jié)點的計算
- 前提：節(jié)點的父節(jié)點存在，且不為根節(jié)點
- 設(shè)節(jié)點的下標(biāo)為N
- 父節(jié)點下標(biāo) = (N-1)/2
一.順序結(jié)構(gòu)
1.理念
- 順序結(jié)構(gòu)以數(shù)組形式存儲
- 普通二叉樹存儲不便
- 堆是一種完全二叉樹。適合以一維數(shù)組進行存儲
注意：普通二叉樹可以用一維數(shù)組存儲，但空間浪費嚴(yán)重。
圖示:
說明:深度越深,空間浪費越嚴(yán)重
補充
- 邏輯結(jié)構(gòu) : 人對數(shù)據(jù)的理解,而進行抽象的模型。
- 線性結(jié)構(gòu): 計算機對數(shù)據(jù)的理解,在計算機語言中的映射。
- 因此 ：二叉樹并不一定要用指針存儲。
2.堆
概念:
如果有一個關(guān)鍵碼1的集合K = {k1 ，k2 ，k3 ，…， }，把它的所有元素按完全二叉樹的順序存儲方式存儲在一個一維數(shù)組中，并滿足： ki<=k2*i+1且 ki<=k2*i+2 ( ki>=k2*i+1 且ki >=k2*i+2 )， i = 0，1，2…，則稱為小堆(或大堆)，此處的i是節(jié)點的下標(biāo)。將根節(jié)點最大的堆叫做最大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆。
小根堆
- 一棵樹的根節(jié)點都比其孩子節(jié)點要小
-
樹可分為根和子樹
大根堆
- 一棵樹的根節(jié)點都比其孩子節(jié)點要大
3. 堆的實現(xiàn)
- 數(shù)組的形式——順序表
//大根堆
typedef int HPDateType;
typedef struct Heap
{
HPDateType* arr;
int size;
int capacity;
}Heap;
-
關(guān)鍵思路:增和刪數(shù)據(jù)
-
增數(shù)據(jù)：從棧底增，往上調(diào)
-
刪數(shù)據(jù)：出棧頂，往下調(diào)
這里我實現(xiàn)的是：大根堆
1.初始化堆
- size設(shè)為0，表示當(dāng)前數(shù)據(jù)元素的個數(shù)，也表示下一個數(shù)據(jù)的下標(biāo)
- size設(shè)為-1，表示當(dāng)前數(shù)據(jù)元素的下標(biāo)
void HeapCreate(Heap* hp)
{
HPDateType* tmp = (HPDateType*)malloc(sizeof(HPDateType) * 4);
if (tmp == NULL)
{
perror("malloc fail");
exit(-1);
}
hp->arr = tmp;
hp->size = 0;
hp->capacity = 4;
}
輔助函數(shù)——交換元素
- 切記要傳指針！
void Swap(HPDateType* arr, int child, int parent)
{
int tmp = arr[child];
arr[child] = arr[parent];
arr[parent] = tmp;
}
2.建堆——增加數(shù)據(jù)
- 從堆底進行增加，往上調(diào)數(shù)據(jù)
- 完全二叉樹的孩子節(jié)點與父節(jié)點的關(guān)系，進行比較
- 孩子節(jié)點只與祖先進行比較，直到不比祖先大或者到根節(jié)點為止。
將1,9,3,5,7依次進堆
過程圖:
向上調(diào)堆代碼:
void AdjustUp(HPDateType* arr, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (arr[parent] < arr[child])//不斷與祖先比較
{
Swap(arr, child, parent);
child = parent;
parent = (child - 1) / 2;
}
else//遇到根節(jié)點或者不大于祖先就停止
{
break;
}
}
}
向堆里增加數(shù)據(jù)
void HeapPush(Heap* hp, HPDateType x)
{
int child = hp->size;
if (hp->size == hp->capacity)//判斷是否需要擴容
{
HPDateType* tmp = (HPDateType*)realloc(hp->arr, \/*換行符*/
sizeof(HPDateType) * hp->capacity * 2);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
hp->arr = tmp;
hp->capacity *= 2;
}
hp->arr[hp->size] = x;
AdjustUp(hp->arr, hp->size);
hp->size++;
}
3.刪除數(shù)據(jù)
- 取的是堆頂?shù)臄?shù)據(jù)——一般我們需要最大的或者最小的
- 不應(yīng)該把棧頂?shù)臄?shù)據(jù)往前移，這樣會破壞堆的結(jié)構(gòu)
- 一般把堆頂?shù)臄?shù)據(jù)與堆底的數(shù)據(jù)進行互換，然后對size減一，達到刪除的效果
- 利用父節(jié)點與孩子節(jié)點的關(guān)系，表示左右孩子節(jié)點
- 從根節(jié)點開始到比其不大的左右孩子較大的或者比完數(shù)據(jù)結(jié)束
- 數(shù)據(jù)為0不能再刪！
動態(tài)圖解:
過程圖解:
向下調(diào)整
void AdjustDown(HPDateType* arr, int parent, int size)
{
//假設(shè)左孩子為較大的孩子
int child = parent * 2 + 1;
while (child < size)//這里size是刪過之后的數(shù)據(jù)個數(shù)，也是最后一個元素的下一個元素的下標(biāo)
{
//先選出較大的孩子
if (child+1<size && arr[child + 1]>arr[child])
{
child++;
}
//錯誤示例:
// if (arr[child + 1]>arr[child]&&child+1<size)
// {
// child++;
// }
//說明:&&從左到右進行判斷，這就好比：你犯錯了還要彌補有什么用？
if (arr[child] > arr[parent])
{
Swap(arr, child, parent);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
刪除堆數(shù)據(jù)
void HeapPop(Heap* hp)
{
assert(hp);
assert(hp->size > 0);
Swap(hp->arr, hp->size-1, 0);
hp->size--;
AdjustDown(hp->arr, 0, hp->size);
}
4.取堆頂元素
- 有數(shù)據(jù)才能取
- 傳入的指針不為空！
//取堆頂元素
HPDateType HeapTop(Heap* hp)
{
assert(hp);
assert(hp->size > 0);
return hp->arr[0];
}
4.堆排序
- 數(shù)組內(nèi)數(shù)據(jù)為亂序——建堆
- 對數(shù)組內(nèi)部元素進行排序——升序用大根堆/降序用小根堆
- 不使用額外的空間
向上調(diào)整(篩選法建堆)
- 從倒數(shù)第二層開始
- 每一層與其孩子節(jié)點較大的比較
- 直到不小于或到最后一層為止
動態(tài)圖:
過程圖:
時間復(fù)雜度——向上建堆
- 設(shè)高度為h
- 從最后一層開始到第一層結(jié)束——[h-1,1]
- 最后一層每個節(jié)點最多比1次，第一層每個節(jié)點最多比h-1次
| 高度 | 最多比較的次數(shù) | 節(jié)點個數(shù) |
|---|---|---|
| 1 | h-1 | 20 |
| 2 | h-2 | 21 |
| …… | …… | …… |
| h-1 | 1 | 2h-2 |
總次數(shù)
- 設(shè)總共比較T(N)次，二叉樹節(jié)點總數(shù)為N
- 所用方法:錯位相減
- 2*T(N)= ????21 *(h-1)+22 *(h-2)+……+2h-2 *2+2h-1 *1
- T(N)=?20 *(h-1)+21 *(h-2)+……+????2h-2 *1
- 第二個式子減去第一個式子。
- 得到:T(N)= -20(h-1)+21 +22+……+2h-2 +2h-1
- 整理得:T(N) = 20+21 +22+……+2h-1 +2h-1 - h
- 根據(jù)等比數(shù)列前n項和:S=a
1(1-qn)/1-q,a1為首項，q為等比 - 此處q=2，a
1=1,代入公式 - 因此:T(N)=2h -1 - h
- 又因為節(jié)點個數(shù) N =2h - 1(滿二叉樹)
- 所以T(N)=N-log2(N+1)，當(dāng)N無窮大時，后一項可忽略。
- 因此:時間復(fù)雜度為O(N),N是節(jié)點的個數(shù)
代碼實現(xiàn):
void AdjustDown(HPDateType* arr, int parent, int size)
{
//左孩子,假設(shè)左孩子為較大的孩子
int child = parent * 2 + 1;
while (child < size)
{
//先選出較大的孩子
if (child+1<size && arr[child + 1]>arr[child])
{
child++;
}
if (arr[child] > arr[parent])
{
Swap(arr, child, parent);//上文有
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapCreat(int* arr, int size)
{
//向下調(diào)整
//((size - 1) - 1) / 2 表示倒數(shù)第二層的倒數(shù)第一個節(jié)點
/*（size-1）是最后一個節(jié)點的下標(biāo)*/
for (int i = ((size - 1) - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, i, size);
}
}
向下調(diào)整(篩選法建堆)
- 從第二層開始，到倒數(shù)第一層
- 每一層與其孩子節(jié)點較大的比較
- 直到不小于或到最后一層為止
圖略~
時間復(fù)雜度——向下調(diào)整
- 設(shè)高度為h
- 從第2層開始到倒數(shù)第二層結(jié)束——[2,h-1]
- 最后一層每個節(jié)點最多比h-1次，第一層每個節(jié)點最多比1次
| 高度 | 最多比較的次數(shù) | 節(jié)點個數(shù) |
|---|---|---|
| 2 | 1 | 21 |
| 3 | 2 | 22 |
| …… | …… | …… |
| h | h-1 | 2h-1 |
- 方法:同上
- 結(jié)論：T(N)=2h *(h-2)+2
- 結(jié)合:節(jié)點個數(shù) N =2h - 1(滿二叉樹)
- 整理得:T(N)=(N+1)*(log
2(N+1)-2)+2 - N趨于無窮大時，T(N)量級趨于N*log
2N - 因此：時間復(fù)雜度——O(n*log2N)
代碼實現(xiàn):
void AdjustUp(HPDateType* arr, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (arr[parent] < arr[child])
{
Swap(arr, child, parent);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void HeapCreat(int* arr, int size)
{
//向下調(diào)整
for (int i = 1; i < size; i++)
{
AdjustUpTwo(arr, i);
}
}
排序思路
- 將堆頂?shù)臄?shù)據(jù)與堆底的數(shù)據(jù)交換位置，不刪除
- size 減去 1，減一是為了不動交換后的數(shù)據(jù)
- 調(diào)整堆的結(jié)構(gòu)
動態(tài)圖:
過程圖:
代碼實現(xiàn):
void HeapSort(int* arr, int size)
{
//第一步調(diào)堆
//建大根堆——升序
//第一種：向上調(diào)整
//for (int i = 1; i < size; i++)
//{
// AdjustUp(arr, i);
//}
//第二種：向下調(diào)整
for (int i = ((size - 1) - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, i, size);
}
int tmp = size - 1;//最后一個元素的下標(biāo)
//時間復(fù)雜度:n*logn
while (tmp)
{
Swap(arr, tmp, 0);
tmp--;
AdjustDownTwo(arr, 0, tmp+1);//tmp+1指的是當(dāng)前元素的個數(shù)
}
}
5.TopK問題
- 目的:從海量數(shù)據(jù)的取出前k大個的數(shù)/前K個小的數(shù)
- 堆大小:2GB左右
- 限制:2GB最多存大約2.5億個整形（理想狀況）
- 突破:硬盤有512GB的，大約可以存615億個整形（理想狀況），足夠所需。
- 思路:將隨機取k個數(shù)據(jù)，建立小根堆/大根堆，將硬盤里的數(shù)據(jù)不斷的取出比較。
- 說明:取出前N個大的用小根堆，前K個最小的為邊界，作為堆頂，比之大就進去，最后結(jié)果：堆頂?shù)臄?shù)據(jù)是前K個最小的。反之亦然。
我實現(xiàn)的是：從100000個數(shù)據(jù)中，取出前10個大的數(shù)。
-
在源文件的目錄下創(chuàng)建一個文本文件
-
向文本文件中輸出一百萬個數(shù)字（不大于10000）
??所用函數(shù)：
- fpoen
- 返回值：FILE*的指針
- 參數(shù)1:文件名——const char*
- 參數(shù)2:打開方式——這里是讀（“r”）
- fprintf
- 返回值：輸入的字符個數(shù)
- 參數(shù)1: 文件指針——FILE*
- 參數(shù)2：輸入的字符串——const char*
- 參數(shù)3: 可變參數(shù)列表——數(shù)據(jù)
void DatasCreat()
{
FILE* p = fopen("datas.txt", "w");
if (p == NULL)
{
perror("fopen fail");
exit(-1);
}
srand((unsigned int)time(NULL));//設(shè)置隨機數(shù)種子
int i = 0;
for (i = 0; i < 1000000; i++)
{
int ret = rand() % 10000;//產(chǎn)生1到9999的數(shù)字
fprintf(p, "%d\n", ret);
}
fclose(p);//使用完要關(guān)閉文件
}
- 修改10個文本中的數(shù)據(jù)使之大于10000
說明:使用過這個函數(shù)后要注釋掉哦！再使用又會刷新文件數(shù)據(jù),別問我怎么知道的。
- 取出文件中的前10個元素，建小根堆
這里先給出完整的函數(shù)聲明和建小根堆的函數(shù):
void DataSort(const char* fname, int k);
//小根堆
void AdjustUpTwo(HPDateType* arr, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (arr[parent] > arr[child])
{
Swap(arr, child, parent);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void HeapCreat(int* arr, int size)
{
//向下調(diào)整
for (int i = 1; i < size; i++)
{
AdjustUpTwo(arr, i);
}
}
- fscanf
- 讀取結(jié)束標(biāo)志:EOF
- 返回值:讀取的元素個數(shù)
- 參數(shù)1：文件指針——FILE*
- 參數(shù)2: 讀取的內(nèi)容——const char*
- 參數(shù)3: 讀到目標(biāo)變量的地址
FILE* fp = fopen(fname, "r");
if (fp == NULL)
{
perror("fopen:fail");
}
int i = 0;
int arr[10] = { 0 };//也可以在堆上開辟
for (i = 0; i < 10; i++)
{
fscanf(fp, "%d", &arr[i]);
}
//建小根堆
HeapCreat(arr, sizeof(arr) / sizeof(arr[0]));
- 取出文件的數(shù)據(jù)，與堆頂元素進行比較
int ret = 0;
while (fscanf(fp, "%d", &ret)!=EOF)//文件的數(shù)據(jù)讀完就結(jié)束
{
if (ret > arr[0])
{
arr[0] = ret;
AdjustDownTwo(arr, 0, sizeof(arr) / sizeof(arr[0]));
}
}
- 排升序——好看（可省略）
HeapSort(arr, 10);
- 打印數(shù)據(jù)
for (i = 0; i < 10; i++)
{
printf("arr[%d]:%d\n", i, arr[i]);
}
- 關(guān)閉文件
fclose(fp);
匯總TOPK排序的代碼:
void DataSort(const char* fname, int k)
{
FILE* fp = fopen(fname, "r");
if (fp == NULL)
{
perror("fopen:fail");
}
int i = 0;
int arr[10] = { 0 };
for (i = 0; i < 10; i++)
{
fscanf(fp, "%d", &arr[i]);
}
//建小根堆
HeapCreat(arr, sizeof(arr) / sizeof(arr[0]));
int ret = 0;
while (fscanf(fp, "%d", &ret)!=EOF)
{
if (ret > arr[0])
{
arr[0] = ret;
AdjustDownTwo(arr, 0, sizeof(arr) / sizeof(arr[0]));
}
}
HeapSort(arr, 10);
for (i = 0; i < 10; i++)
{
printf("arr[%d]:%d\n", i, arr[i]);
}
fclose(fp);
}
void DatasCreat()
{
int i = 0;
FILE* p = fopen("datas.txt", "w");
if (p == NULL)
{
perror("fopen fail");
exit(-1);
}
srand((unsigned int)time(NULL));
for (i = 0; i < 1000000; i++)
{
int ret = rand() % 10000;
fprintf(p, "%d\n", ret);
}
fclose(p);
}
總結(jié)
希望對您有所幫助！文章來源：http://www.zghlxwxcb.cn/news/detail-432165.html
-
數(shù)據(jù)元素中能起標(biāo)識作用的數(shù)據(jù)項 ??文章來源地址http://www.zghlxwxcb.cn/news/detail-432165.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】二叉樹——順序結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
