您好,登錄后才能下訂單哦!
本篇文章為大家展示了C語言數(shù)據(jù)結(jié)構(gòu)堆的基本操作實(shí)現(xiàn)是怎樣的,內(nèi)容簡明扼要并且容易理解,絕對能使你眼前一亮,通過這篇文章的詳細(xì)介紹希望你能有所收獲。
void AdjustDown(DateType*a, int n, int parent) { int child = parent * 2 + 1; while (child<n) { if ((child+1) < n && a[child] > a[child + 1]) { ++child; } if (a[parent] > a[child]) { Swap(&a[parent], &a[child]); parent = child; child = parent * 2 + 1; } else { break; } } }
注意:if里面的條件語句(child +1)<n是防止越界的,因?yàn)椴荒鼙WC有右孩子。
void AdjustUp(DateType*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; } } }
注意:while里面的條件語句是不能夠?qū)懗?parent<0),因?yàn)楫?dāng)child==0時,parent=(child - 1) / 2,parent==0,再次進(jìn)入循環(huán)不滿足a[child] < a[parent],恰好跳出循環(huán)。如果寫成(a[child] <= a[parent])就死循環(huán)了
void Swap(DateType*p1, DateType*p2) { DateType tmp = *p1; *p1 = *p2; *p2 = tmp; }
void CreatHeap(Heap*p,DateType*num,int n) { assert(p); p->a = (DateType*)malloc(n * sizeof(DateType)); if (p->a == NULL) { printf("malloc failed\n"); exit(-1); } memcpy(p->a, num, n * sizeof(DateType)); p->size = n; p->capacity = n; //建小堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(p->a, p->size, i); } }
void HeapPush(Heap*p, DateType x) { assert(p); if (p->size == p->capacity) { DateType*tmp = (DateType*)realloc(p->a, (p->capacity) * 2 * sizeof(DateType)); if (tmp == NULL) { printf("realloc failed\n "); exit(-1); } } (p->capacity) *= 2; p->a[p->size] = x; ++(p->size); //向上調(diào)整 AdjustUp(p->a, p->size-1); }
void HeapPop(Heap*p, DateType x) { assert(p); Swap(&p->a[0], &p->a[p->size-1]); --(p->size); AdjustDown(p->a, p->size, 0); //左右子樹還是小堆,直接調(diào)整行了 }
把堆頂?shù)臄?shù)據(jù)與最后一個數(shù)據(jù)交換,再次調(diào)整size-1個數(shù)據(jù)。
DateType HeapTop(Heap*p) { assert(p); return p->a[0]; }
int HeapSize(Heap*p) { assert(p); return p->size; }
bool HeapIsEmpty(Heap*p) { assert(p); return p->size == 0; }
void Print(Heap*p) { assert(p); for (int i = 0; i < p->size; i++) { printf("%d ", (p->a)[i]); } printf("\n"); int count = 0;//計(jì)數(shù) int levelsize = 1; for (int i = 0; i < p->size; i++) { printf("%d ", p->a[i]); ++count; if (count == levelsize) { printf("\n"); levelsize *= 2; count = 0;//重新計(jì)數(shù) } } printf("\n"); }
void HeapDestory(Heap*p) { assert(p); free(p->a); p->a = NULL; p->capacity = p->size = 0; }
int main() { int num[] = { 12,15,17,23,10,25 }; int n = sizeof(num) / sizeof(num[0]); Heap a; //創(chuàng)建小堆 CreatHeap(&a,num, n); Print(&a); printf("\n"); //插入數(shù)據(jù) HeapPush(&a, 1); Print(&a); //刪除對頂?shù)臄?shù)據(jù) HeapPop(&a); Print(&a); printf("\n"); //獲取堆頂數(shù)據(jù) int ret=HeapTop(&a); printf("The top date is %d\n",ret); //堆的數(shù)據(jù)個數(shù) int number=HeapSize(&a); printf("The number of heap is %d\n", number); //銷毀 HeapDestory(&a); return 0; }
a.代碼1
int main() { DateType num[] = { 12,15,17,23,10,25 }; int n = sizeof(num) / sizeof(num[0]); HeapSort(num, n); for (int i = 0; i < n; i++) { printf("%d ", num[i]); } printf("\n\n"); return 0; }
void HeapSort(int*num, int n) { //建小堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(num, n, i); } int end = n - 1; while (end>0) { Swap(&num[0], &num[end]); AdjustDown(num, end, 0); --end; } }
運(yùn)行結(jié)果
上述內(nèi)容就是C語言數(shù)據(jù)結(jié)構(gòu)堆的基本操作實(shí)現(xiàn)是怎樣的,你們學(xué)到知識或技能了嗎?如果還想學(xué)到更多技能或者豐富自己的知識儲備,歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。