如何建設(shè)一個電影網(wǎng)站在線播放惡意點擊軟件哪個好
前言
前邊077帶著大家學(xué)習(xí)了樹與二叉樹的相關(guān)概念，這篇文章我們來實現(xiàn)一個二叉樹的順序結(jié)構(gòu)。
二叉樹的順序結(jié)構(gòu)
普通的二叉樹是不適合用數(shù)組來存儲的，因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結(jié)構(gòu)存儲。現(xiàn)實中我們通常把堆(一種二叉樹)使用順序結(jié)構(gòu)的數(shù)組來存儲，需要注意的是這里的堆和操作系統(tǒng)虛擬進程地址空間中的堆是兩回事，一個是數(shù)據(jù)結(jié)構(gòu)，一個是操作系統(tǒng)中管理內(nèi)存的一塊區(qū)域分段。
與前邊的棧類似，數(shù)據(jù)結(jié)構(gòu)中的堆與地址空間的堆是完全不同的，是兩個學(xué)科中的名詞。?
?
堆的概念及結(jié)構(gòu)?
將根節(jié)點最大的堆叫做最大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆。
堆的性質(zhì)：堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值；堆總是一棵完全二叉樹。
?
小堆，又叫小根堆，小頂堆，顧名思義就是這個堆的根節(jié)點數(shù)據(jù)是最小的，而且每一個父節(jié)點的數(shù)據(jù)都要小于子節(jié)點的數(shù)據(jù)，有一個不滿足都不是小堆。
大堆就是根節(jié)點最大的堆，堆中每一個父節(jié)點的數(shù)據(jù)都是大于子結(jié)點的數(shù)據(jù)。
堆的實現(xiàn)
堆的接口實現(xiàn)
1.堆的結(jié)構(gòu)
typedef int hpDataType;
typedef struct heap
{hpDataType* a;int size;int capacity;
}hp;堆是順序的二叉樹，所以要定義一個順序表，在物理上就是一個順序表，在邏輯上確是一個二叉樹，也就是堆。
2.初始化
void hpInit(hp* ph)
{assert(ph);ph->a = NULL;ph->capacity = ph->size = 0;
}3.銷毀順序表
void hpDestory(hp* ph)
{assert(ph);free(ph->a);ph->a = NULL;ph->capacity = ph->size = 0;
}4.向上調(diào)整
void adjustUp(hpDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] > a[parent]){int tmp = a[child];a[child] = a[parent];a[parent] = tmp;child = parent;parent = (child - 1) / 2;}else{break;}}
}使用向上調(diào)整算法可以隨意插入數(shù)據(jù)，并且還不改變堆，還為一個小堆或者大堆，我這里實現(xiàn)的是一個大堆。
5.堆的插入
void hpPush(hp* ph, hpDataType x)
{assert(ph);if (ph->size == ph->capacity){hpDataType newCapacity = ph->capacity == 0 ? 4 : ph->capacity * 2;hpDataType* tmp = (hpDataType*)realloc(ph->a, sizeof(hpDataType)*newCapacity);if (tmp == NULL){perror("realloc fail/n");exit(-1);}ph->a = tmp;ph->capacity = newCapacity;}ph->a[ph->size] = x;ph->size++;adjustUp(ph->a, ph->size - 1);
}在堆中插入數(shù)據(jù)的前提是不改變堆的性質(zhì)，使其還是一個堆，所以我們可以在最后一個位置處插入數(shù)據(jù)，再調(diào)用向上調(diào)整函數(shù)來實現(xiàn)插入，當(dāng)然與順序表相同的是，當(dāng)容量不夠時我們要進行擴容操作。
6.向下調(diào)整算法
void adjustDown(hpDataType* a, int size, int parent)
{int child = parent * 2 + 1;//調(diào)整到?jīng)]有孩子結(jié)點while (child < size){if (child + 1 < size && a[child + 1] < a[child]){child++;}if (a[child] < a[parent]){swap(&a[parent], & a[child]);parent = child;child = parent * 2 + 1;}else{break;} }
}我們使用向下調(diào)整函數(shù)也可以實現(xiàn)大堆和小堆，當(dāng)某一節(jié)點不存在孩子結(jié)點時，向下調(diào)整結(jié)束，由于一個父節(jié)點存在左子樹和右子樹，所以我們在調(diào)整時，應(yīng)該判斷左右子樹數(shù)據(jù)的大小并且判斷右子樹是否存在，來決定child的位置，再比較與父節(jié)點的位置來交換父節(jié)點與孩子結(jié)點。
7.堆的刪除
void hpPop(hp* ph)
{assert(ph);assert(!hpEmpty(ph));swap(&ph->a[ph->size - 1], &ph->a[0]);ph->size--;adjustDown(ph->a, ph->size, 0);
}堆中數(shù)據(jù)的刪除實際上指的是將堆頂數(shù)據(jù)進行刪除，我們要進行的操作是將堆中最后一個數(shù)與堆頂元素互換，然后將堆的數(shù)據(jù)個數(shù)減一，這樣就刪除了堆頂元素，但是此時可能改變了堆的結(jié)構(gòu)，我們再使用向下調(diào)整算法，調(diào)整根節(jié)點就能恢復(fù)了。
8.判空
bool hpEmpty(hp* ph)
{assert(ph);return ph->size == 0;
}9.取堆頂數(shù)據(jù)
hpDataType hpTop(hp* ph)
{assert(ph);assert(!hpEmpty(ph));return ph->a[0];
}10.打印堆中數(shù)據(jù)
void hpPrint(hp* hp)
{for (int i = 0; i < hp->size; ++i){printf("%d ", hp->a[i]);}printf("\n");
}源碼
heap.h
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>
typedef int hpDataType;
typedef struct heap
{hpDataType* a;int size;int capacity;
}hp;
void adjustUp(hpDataType* a, int child);
void adjustDown(hpDataType* a, int size, int child);void swap(int* px, int* py);
void hpInit(hp* ph);
void hpDestory(hp* ph);
void hpPush(hp* ph, hpDataType x);
void hpPop(hp* ph);
bool hpEmpty(hp* ph);
void hpPrint(hp* ph);
hpDataType hpTop(hp* ph);heap.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"
void swap(int* px, int* py)
{int tmp = *px;*px = *py;*py = tmp;
}
void adjustUp(hpDataType* a, int child)
{int parent = (child - 1) / 2;//調(diào)整到孩子結(jié)點就是根節(jié)點結(jié)束while (child > 0){if (a[child] > a[parent]){int tmp = a[child];a[child] = a[parent];a[parent] = tmp;child = parent;parent = (child - 1) / 2;}else{break;}}
}
void adjustDown(hpDataType* a, int size, int parent)
{int child = parent * 2 + 1;//調(diào)整到?jīng)]有孩子結(jié)點while (child < size){if (child + 1 < size && a[child + 1] < a[child]){child++;}if (a[child] < a[parent]){swap(&a[parent], & a[child]);parent = child;child = parent * 2 + 1;}else{break;} }
}
void hpInit(hp* ph)
{assert(ph);ph->a = NULL;ph->capacity = ph->size = 0;
}
void hpDestory(hp* ph)
{assert(ph);free(ph->a);ph->a = NULL;ph->capacity = ph->size = 0;
}void hpPush(hp* ph, hpDataType x)
{assert(ph);if (ph->size == ph->capacity){hpDataType newCapacity = ph->capacity == 0 ? 4 : ph->capacity * 2;hpDataType* tmp = (hpDataType*)realloc(ph->a, sizeof(hpDataType)*newCapacity);if (tmp == NULL){perror("realloc fail/n");exit(-1);}ph->a = tmp;ph->capacity = newCapacity;}ph->a[ph->size] = x;ph->size++;adjustUp(ph->a, ph->size - 1);
}
void hpPop(hp* ph)
{assert(ph);assert(!hpEmpty(ph));swap(&ph->a[ph->size - 1], &ph->a[0]);ph->size--;adjustDown(ph->a, ph->size, 0);}
bool hpEmpty(hp* ph)
{assert(ph);return ph->size == 0;
}
void hpPrint(hp* hp)
{for (int i = 0; i < hp->size; ++i){printf("%d ", hp->a[i]);}printf("\n");
}
hpDataType hpTop(hp* ph)
{assert(ph);assert(!hpEmpty(ph));return ph->a[0];
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"void test()
{hp h;hpInit(&h);int a[] = { 70, 56, 30, 25, 15, 10, 1 };for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i){hpPush(&h, a[i]);}hpPrint(&h);hpDestory(&h);
}
int main()
{test();//testTopk();return;
}