国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁
  2. >Toy博客

【C語言】數(shù)據(jù)結(jié)構(gòu)——小堆實例探究

2年前作者：流浪者與猴分類：Toy博客閱讀(19)違法舉報

這篇具有很好參考價值的文章主要介紹了【C語言】數(shù)據(jù)結(jié)構(gòu)——小堆實例探究。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

??個人主頁??
?個人專欄——數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)?
??點擊關(guān)注??一起學(xué)習(xí)C語言????

導(dǎo)讀：

我們在前面學(xué)習(xí)了單鏈表和順序表，以及棧和隊列。
今天我們來學(xué)習(xí)小堆。
關(guān)注博主或是訂閱專欄，掌握第一消息。

1. 堆的概念及結(jié)構(gòu)

現(xiàn)實中我們通常把堆(一種二叉樹)使用順序結(jié)構(gòu)的數(shù)組來存儲，需要注意的是這里的堆和操作系統(tǒng)虛擬進程地址空間中的堆是兩回事，一個是數(shù)據(jù)結(jié)構(gòu)，一個是操作系統(tǒng)中管理內(nèi)存的一塊區(qū)域分段。

1.1 什么是堆

堆是一種特殊的數(shù)據(jù)結(jié)構(gòu)，它可以看做是一個完全二叉樹（或者近似二叉樹），其中每個節(jié)點的值都大于等于（或小于等于）其子節(jié)點的值。在一個最大堆中，根節(jié)點的值是最大的；在一個最小堆中，根節(jié)點的值是最小的。
【C語言】數(shù)據(jù)結(jié)構(gòu)——小堆實例探究,數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí),c語言,開發(fā)語言,數(shù)據(jù)結(jié)構(gòu)

1.2 堆的特點

堆的主要特點是：每個節(jié)點的值都大于等于（或小于等于）其子節(jié)點的值。這種特點使得堆可以快速找到最大（或最小）的元素。另外，堆還可以用于排序和優(yōu)先隊列等應(yīng)用。
堆中兄弟節(jié)點的值之間沒有關(guān)聯(lián)。在堆中，節(jié)點之間的關(guān)系僅由其在樹中的位置決定。

1.3 堆的結(jié)構(gòu)

堆通常使用數(shù)組來實現(xiàn)，數(shù)組的下標(biāo)代表節(jié)點在堆中的位置。根據(jù)節(jié)點在數(shù)組中的位置，可以通過簡單的計算得到其父節(jié)點、左子節(jié)點和右子節(jié)點的位置。這樣，在堆中插入一個新元素、刪除堆頂?shù)脑鼗蛘哒{(diào)整堆的結(jié)構(gòu)時，只需要對數(shù)組進行簡單的操作，而不需要改變整個堆的結(jié)構(gòu)。

2. 堆的實現(xiàn)

我們需要創(chuàng)建兩個 C文件: study.c 和 Heap.c，以及一個 頭文件： Heap.h。

頭文件來聲明函數(shù)，一個C文件來定義函數(shù)，另外一個C文件來用于主函數(shù)main（）進行測試。

堆的常見操作包括插入元素、刪除堆頂元素、堆化（調(diào)整堆的結(jié)構(gòu)使其滿足堆的特點）等。其中，插入元素和刪除堆頂元素的時間復(fù)雜度為O(logn)，堆化的時間復(fù)雜度為O(nlogn)。

3. 代碼實現(xiàn)

3.1 定義結(jié)構(gòu)體

Heap.h：

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;		//記錄數(shù)組內(nèi)的有效數(shù)據(jù)
	int capacity;	//記錄數(shù)組空間大小
}HP;

3.2 堆的初始化

Heap.h：

//堆的初始化
void HeapInit(HP* php);

Heap.c：

//堆的初始化
void HeapInit(HP* php)
{
	//各值初始化為0
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

3.3 堆的銷毀

我們的數(shù)組空間是用malloc函數(shù)開辟的，使用完之后需要進行釋放。
Heap.h：

// 堆的銷毀
void HeapDestroy(HP* php);

Heap.c：

// 堆的銷毀
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

3.4 向上調(diào)整父節(jié)點與子節(jié)點

在出入數(shù)組后，我們需要對數(shù)組進行調(diào)整，以實現(xiàn)堆的結(jié)構(gòu)特點。
在數(shù)組中，下標(biāo)*2+1就是他的子節(jié)點，同樣的下標(biāo)-1/2就是他的父節(jié)點。
Heap.h：

//向上調(diào)整父節(jié)點與子節(jié)點
void AdjustUp(HPDataType* a, int child);

Heap.c：

//交換父節(jié)點和子節(jié)點的值
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//向上調(diào)整父節(jié)點與子節(jié)點
void AdjustUp(HPDataType* a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;//找到父節(jié)點
	while (child > 0)
	{
		//查看父親節(jié)點與孩子節(jié)點的值
		//若小則替換，否則就結(jié)束循環(huán)
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

【C語言】數(shù)據(jù)結(jié)構(gòu)——小堆實例探究,數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí),c語言,開發(fā)語言,數(shù)據(jù)結(jié)構(gòu)

3.5 堆的插入

Heap.h：

// 堆的插入
void HeapPush(HP* php, HPDataType x);

Heap.c：

// 堆的插入
// 堆的插入
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	//首先檢查數(shù)組容量是否足夠
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	//在插入數(shù)值后需要檢查是否要進行調(diào)整
	AdjustUp(php->a, php->size);
	php->size++;
}

【C語言】數(shù)據(jù)結(jié)構(gòu)——小堆實例探究,數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí),c語言,開發(fā)語言,數(shù)據(jù)結(jié)構(gòu)
【C語言】數(shù)據(jù)結(jié)構(gòu)——小堆實例探究,數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí),c語言,開發(fā)語言,數(shù)據(jù)結(jié)構(gòu)

3.6 向下調(diào)整父節(jié)點與子節(jié)點

刪除堆是刪除堆頂?shù)臄?shù)據(jù)，但是我們無法直接刪除第一個元素，這有極大的可能會使我們的堆崩潰，不再具有堆的特點，而在刪除之后把其它數(shù)值都往前移動，再進行調(diào)整是一項很大的工作量。
所以我們可以將堆頂?shù)臄?shù)據(jù)根最后一個數(shù)據(jù)一換，然后刪除數(shù)組最后一個數(shù)據(jù)，再進行向下調(diào)整算法。將當(dāng)前的根數(shù)值調(diào)整到符合堆特點的位置去。
Heap.h：

//向下調(diào)整父節(jié)點與子節(jié)點
void AdjustDown(int* a, int size, int parent);

Heap.c：

//向下調(diào)整父節(jié)點與子節(jié)點
void AdjustDown(int* a, int size, int parent)
{
	assert(a);
	int child = parent * 2 + 1;//找到孩子節(jié)點
	while (child < size)
	{
		//找孩子中較小的一個
		if ((a[child] > a[child + 1]) && (child + 1) < size)
		{
			child += 1;
		}
		//判斷兩個大小進行交換
		if (a[parent] > a[child])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

3.7 堆的刪除

Heap.h：

// 堆的刪除
void HeapPop(HP* php);

Heap.c：

// 堆的刪除
void HeapPop(HP* php)
{
	assert(php);
	//先檢查數(shù)組是否有可刪除的數(shù)據(jù)
	assert(php->size > 0);
	//交換首尾元素
	Swap(&php->a[php->size - 1], &php->a[0]);
	php->size--;
	//向下進行調(diào)整
	AdjustDown(php->a, php->size, 0);

}

【C語言】數(shù)據(jù)結(jié)構(gòu)——小堆實例探究,數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí),c語言,開發(fā)語言,數(shù)據(jù)結(jié)構(gòu)
【C語言】數(shù)據(jù)結(jié)構(gòu)——小堆實例探究,數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí),c語言,開發(fā)語言,數(shù)據(jù)結(jié)構(gòu)

3.8 獲取堆頂元素

返回數(shù)組首元素即可
Heap.h：

// 取堆頂?shù)臄?shù)據(jù)
HPDataType HeapTop(HP* php);

Heap.c：

// 取堆頂?shù)臄?shù)據(jù)
HPDataType HeapTop(HP* php)
{
	assert(php);
	return php->a[0];
}

3.9 獲取堆的個數(shù)

直接返回size的值即可
Heap.h：

// 堆的數(shù)據(jù)個數(shù)
size_t HeapSize(HP* php);

Heap.c：

// 堆的數(shù)據(jù)個數(shù)
size_t HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

3.10 堆的判空

只需判斷size的值是否為0，如果是，返回true，反之返回false。
Heap.h：

// 堆的判空
bool HeapEmpty(HP* php);

Heap.c：

// 堆的判空
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

4. 代碼整理

4.1 Heap.h

#define _CRT_SECURE_NO_WARNINGS 
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	int size;		//記錄數(shù)組內(nèi)的有效數(shù)據(jù)
	int capacity;	//記錄數(shù)組空間大小
}HP;

//堆的初始化
void HeapInit(HP* php);

// 堆的銷毀
void HeapDestroy(HP* php);

// 堆的插入
void HeapPush(HP* php, HPDataType x);

// 堆的刪除
void HeapPop(HP* php);

// 取堆頂?shù)臄?shù)據(jù)
HPDataType HeapTop(HP* php);

// 堆的數(shù)據(jù)個數(shù)
size_t HeapSize(HP* php);

// 堆的判空
bool HeapEmpty(HP* php);

//向上調(diào)整父節(jié)點與子節(jié)點
void AdjustUp(HPDataType* a, int child);

//向下調(diào)整父節(jié)點與子節(jié)點
void AdjustDown(int* a, int size, int parent);

//交換父節(jié)點和子節(jié)點的值
void Swap(int* child, int* parent);

4.2 Heap.c

#include "Heap.h"

//堆的初始化
void HeapInit(HP* php)
{
	//各值初始化為0
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

// 堆的銷毀
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

//交換父節(jié)點和子節(jié)點的值
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//向上調(diào)整父節(jié)點與子節(jié)點
void AdjustUp(HPDataType* a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;//找到父節(jié)點
	while (child > 0)
	{
		//查看父親節(jié)點與孩子節(jié)點的值
		//若小則替換，否則就結(jié)束循環(huán)
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
// 堆的插入
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	//首先檢查數(shù)組容量是否足夠
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	//在插入數(shù)值后需要檢查是否要進行調(diào)整
	AdjustUp(php->a, php->size);
	php->size++;
}


//向下調(diào)整父節(jié)點與子節(jié)點
void AdjustDown(int* a, int size, int parent)
{
	assert(a);
	int child = parent * 2 + 1;//找到孩子節(jié)點
	while (child < size)
	{
		//找孩子中較小的一個
		if ((a[child] > a[child + 1]) && (child + 1) < size)
		{
			child += 1;
		}
		//判斷兩個大小進行交換
		if (a[parent] > a[child])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

// 堆的刪除
void HeapPop(HP* php)
{
	assert(php);
	//先檢查數(shù)組是否有可刪除的數(shù)據(jù)
	assert(php->size > 0);
	//交換首尾元素
	Swap(&php->a[php->size - 1], &php->a[0]);
	php->size--;
	//向下進行調(diào)整
	AdjustDown(php->a, php->size, 0);

}

// 取堆頂?shù)臄?shù)據(jù)
HPDataType HeapTop(HP* php)
{
	assert(php);
	return php->a[0];
}

// 堆的數(shù)據(jù)個數(shù)
size_t HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

// 堆的判空
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

4.3 study.c

void Test1()
{
	int array[] = { 27,15,19,18,28,34,65,49,25,37 };
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < sizeof(array) / sizeof(int); i++)
	{
		HeapPush(&hp, array[i]);//插入數(shù)據(jù)
	}
	int k = HeapSize(&hp);
	while (k--)
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	HeapDestroy(&hp);
}


int main()
{;
	Test1();
	return 0;
}

【C語言】數(shù)據(jù)結(jié)構(gòu)——小堆實例探究,數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí),c語言,開發(fā)語言,數(shù)據(jù)結(jié)構(gòu)文章來源地址http://www.zghlxwxcb.cn/news/detail-762343.html

到了這里，關(guān)于【C語言】數(shù)據(jù)結(jié)構(gòu)——小堆實例探究的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實不符，請點擊違法舉報進行投訴反饋，一經(jīng)查實，立即刪除！

領(lǐng)支付寶紅包贊助服務(wù)器費用

相關(guān)文章

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包