如何建設一個電影網站在線播放惡意點擊軟件哪個好
前言
前邊077帶著大家學習了樹與二叉樹的相關概念，這篇文章我們來實現(xiàn)一個二叉樹的順序結構。
二叉樹的順序結構
普通的二叉樹是不適合用數組來存儲的，因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結構存儲。現(xiàn)實中我們通常把堆(一種二叉樹)使用順序結構的數組來存儲，需要注意的是這里的堆和操作系統(tǒng)虛擬進程地址空間中的堆是兩回事，一個是數據結構，一個是操作系統(tǒng)中管理內存的一塊區(qū)域分段。
與前邊的棧類似，數據結構中的堆與地址空間的堆是完全不同的，是兩個學科中的名詞。?
?
堆的概念及結構?
將根節(jié)點最大的堆叫做最大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆。
堆的性質：堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值；堆總是一棵完全二叉樹。
?
小堆，又叫小根堆，小頂堆，顧名思義就是這個堆的根節(jié)點數據是最小的，而且每一個父節(jié)點的數據都要小于子節(jié)點的數據，有一個不滿足都不是小堆。
大堆就是根節(jié)點最大的堆，堆中每一個父節(jié)點的數據都是大于子結點的數據。
堆的實現(xiàn)
堆的接口實現(xiàn)
1.堆的結構
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.向上調整
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;}}
}使用向上調整算法可以隨意插入數據，并且還不改變堆，還為一個小堆或者大堆，我這里實現(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);
}在堆中插入數據的前提是不改變堆的性質，使其還是一個堆，所以我們可以在最后一個位置處插入數據，再調用向上調整函數來實現(xiàn)插入，當然與順序表相同的是，當容量不夠時我們要進行擴容操作。
6.向下調整算法
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[parent], & a[child]);parent = child;child = parent * 2 + 1;}else{break;} }
}我們使用向下調整函數也可以實現(xiàn)大堆和小堆，當某一節(jié)點不存在孩子結點時，向下調整結束，由于一個父節(jié)點存在左子樹和右子樹，所以我們在調整時，應該判斷左右子樹數據的大小并且判斷右子樹是否存在，來決定child的位置，再比較與父節(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);
}堆中數據的刪除實際上指的是將堆頂數據進行刪除，我們要進行的操作是將堆中最后一個數與堆頂元素互換，然后將堆的數據個數減一，這樣就刪除了堆頂元素，但是此時可能改變了堆的結構，我們再使用向下調整算法，調整根節(jié)點就能恢復了。
8.判空
bool hpEmpty(hp* ph)
{assert(ph);return ph->size == 0;
}9.取堆頂數據
hpDataType hpTop(hp* ph)
{assert(ph);assert(!hpEmpty(ph));return ph->a[0];
}10.打印堆中數據
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;//調整到孩子結點就是根節(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;//調整到沒有孩子結點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;
}