欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言 深入解讀數(shù)據(jù)結(jié)構(gòu)之堆的實現(xiàn)

 更新時間：2021年11月09日 15:47:11   作者：loveandsharef  
堆就是用數(shù)組實現(xiàn)的二叉樹，所以它沒有使用父指針或者子指針。堆根據(jù)“堆屬性”來排序，“堆屬性”決定了樹中節(jié)點的位置

堆的概念與結(jié)構(gòu)

概念：如果有一個關(guān)鍵碼的集合K={ k0，k1 ，k2 ，…，kn-1 },把它的所有元素按完全二叉樹的順序存儲方式存儲 在一個一維數(shù)組中，并滿足K i<=K 2*i+1且Ki<=K 2*i+2(K i>=K 2*i+1且Ki>=K 2*i+2) i = 0，1，2...，則稱為小堆(或大堆)。將根節(jié)點最大的堆叫做最大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆。

性質(zhì)：

  • 堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值；
  • 堆總是一棵完全二叉樹。

結(jié)構(gòu)：

1.大堆

2.小堆

堆(大根堆)的實現(xiàn)：

堆的接口：

#pragma once
#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;
 
//堆的創(chuàng)建
void HeapInit(HP*hp);
//堆的銷毀
void HeapDestroy(HP*hp);
//交換數(shù)值
void Swap(HPDataType *px, HPDataType *py);
//向上調(diào)整
void AdjustUp(int *a,int child);
//向下調(diào)整
void AdjustDown(int *a, int n, int parent);
//堆的插入
void HeapPush(HP*hp,HPDataType x);
//堆的刪除
void HeapPop(HP*hp);
//取堆頂?shù)臄?shù)據(jù)
HPDataType HeapTop(HP*hp);
//打印堆
void HeapPrint(HP*hp);
//堆的判空
bool HeapEmpty(HP*hp);
//堆的數(shù)據(jù)個數(shù)
int HeapSize(HP*hp);

堆的創(chuàng)建：

void HeapInit(HP*hp)
{
    assert(hp);
    hp->a=NULL;
    hp->capacity=hp->size=0;
}

堆的銷毀：

void HeapDestroy(HP*hp)
{
    assert(hp);
    free(hp->a);
    hp->capacity=hp->size=0;
}

交換數(shù)值：

void Swap(HPDataType*px, HPDataType*py)
{
    HPDataType tmp = *px;
    *px=*py;
    *py=tmp;
}

向上調(diào)整：

void AdjustUp(int*a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
            //交換數(shù)值
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

堆得插入：

void HeapPush(HP*hp,HPDataType x)
{
    assert(hp);
    if(hp->capacity==hp->size)
    {
        size_t newCapacity=hp->capacity==0?4:hp->capacity*2;
        HPDataType * tmp=(HPDataType*)realloc(hp->a,newCapacity*sizeof(HPDataType));
        if(tmp==NULL)
        {
            printf("realloc is fail\n");
        }
        hp->a=tmp;
        hp->capacity=newCapacity;
        
    }
    hp->a[hp->size-1]=x;
    hp->size++;
    //向上調(diào)整
    AdjusiUp(hp->a,hp->size-1);
}

向下調(diào)整：

void AdjustDown(int *a,int n,int parent)
{
    int child=parent*2+1;
    while(child<n)
    {
        //比較左孩子還是右孩子大
        if(child+1<n && a[child+1]>a[child])
        {
            child++;
        }
        if(a[child]>a[parent])
        {
            Swap(&a[child],&a[parent]);
            parent=child;
            child=parent*2+1;
        }
        else
        {
            break;
        }
    }
}

堆的判空：

bool HeapEmpty(HP*hp)
{
    assert(hp);
    return hp->size==0;
}

堆的刪除：

void HeapPop(HP*hp)
{
	assert(hp);
    //堆的判空
	assert(!HeapEmpty(hp));
    //交換數(shù)值
	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
    //向下調(diào)整
	AdjustDown(hp->a, hp->size, 0);
}

取堆頂?shù)臄?shù)據(jù)：

HPDataType HeapTop(HP*hp)
{
    assert(hp);
    assert(!HeapEmpty(hp));
    return hp->a[0];
}

打印堆：

void HeapPrint(HP*hp)
{
    assert(hp);
    assert(!HeapEmpty(hp));
    for(int i=0; i<hp->size;i++)
    {
        printf("%d",hp->a[i]);
    }
    printf("\n");
}

堆的數(shù)據(jù)個數(shù)：

int HeapSize(HP*hp)
{
    assert(hp);
    return hp->size;
}

以上就是對堆的講解與操作實現(xiàn)。

感謝老鐵看到這里，如果文章對你有用的話請給我一個贊支持一下，感激不盡！

在下才疏學淺,一點淺薄之見，歡迎各位大佬指點。

以上就是C語言 深入解讀數(shù)據(jù)結(jié)構(gòu)之堆的實現(xiàn)的詳細內(nèi)容，更多關(guān)于C語言 數(shù)據(jù)結(jié)構(gòu)的資料請關(guān)注腳本之家其它相關(guān)文章！

相關(guān)文章

  • 一文詳解C++中運算符的使用

    一文詳解C++中運算符的使用

    這篇文章主要為大家詳細介紹了C++中運算符的使用方法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助
    2022-05-05
  • C語言volatile關(guān)鍵字的作用與示例

    C語言volatile關(guān)鍵字的作用與示例

    這篇文章主要介紹了C語言volatile關(guān)鍵字的作用，volatile提醒編譯器它后面所定義的變量隨時都有可能改變，因此編譯后的程序每次需要存儲或讀取這個變量的時候，都會直接從變量地址中讀取數(shù)據(jù)
    2023-04-04
  • C語言中的常量詳解

    C語言中的常量詳解

    本文主要講解C語言 常量,這里整理了 C語言常量的基礎(chǔ)知識，并附代碼示例和示例詳細講解，希望能幫助開始學習C 語言的同學
    2021-09-09
  • C++存儲方案和動態(tài)分配

    C++存儲方案和動態(tài)分配

    這篇文章主要介紹了C++存儲方案和動態(tài)分配，
    2021-12-12
  • C++編程中隊內(nèi)聯(lián)函數(shù)的理解和使用

    C++編程中隊內(nèi)聯(lián)函數(shù)的理解和使用

    這篇文章主要介紹了C++編程中隊內(nèi)聯(lián)函數(shù)的理解和使用,簡單舉例講解了inline關(guān)鍵字引出的內(nèi)聯(lián)函數(shù)的相關(guān)知識,需要的朋友可以參考下
    2016-01-01
  • C語言實現(xiàn)歌手比賽系統(tǒng)

    C語言實現(xiàn)歌手比賽系統(tǒng)

    這篇文章主要為大家詳細介紹了C語言實現(xiàn)歌手比賽系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2022-05-05
  • C++取得當前時間的方法

    C++取得當前時間的方法

    這篇文章主要介紹了C++取得當前時間的方法,實例展示了通過系統(tǒng)函數(shù)獲取當前時間的實現(xiàn)方法,非常簡單易懂,需要的朋友可以參考下
    2014-10-10
  • Linux網(wǎng)絡(luò)編程之socket文件傳輸示例

    Linux網(wǎng)絡(luò)編程之socket文件傳輸示例

    這篇文章主要介紹了Linux網(wǎng)絡(luò)編程之socket文件傳輸示例,對于基于Linux平臺的C程序員來說有一定的借鑒價值,需要的朋友可以參考下
    2014-08-08
  • 統(tǒng)計C語言二叉樹中葉子結(jié)點個數(shù)

    統(tǒng)計C語言二叉樹中葉子結(jié)點個數(shù)

    這篇文章主要介紹的是統(tǒng)計C語言二叉樹中葉子結(jié)點個數(shù)，文章以C語言二叉樹中葉子結(jié)點為基礎(chǔ)分享一個簡單小栗子講解，具有一定的知識參考價值，需要的小伙伴可以參考一下
    2022-02-02
  • C++編程之?std::forward使用例子

    C++編程之?std::forward使用例子

    std::forward?是一個?C++11?中的模板函數(shù)，其主要作用是在模板函數(shù)或模板類中，將一個參數(shù)以“原樣”（forward）的方式轉(zhuǎn)發(fā)給另一個函數(shù)，這篇文章主要介紹了C++編程之?std::forward,需要的朋友可以參考下
    2023-03-03

最新評論