日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

C語言堆與二叉樹的順序結構與實現_C 語言

作者：Hiland. ? 更新時間： 2022-07-09 編程語言

一. 二叉樹的順序結構

普通的二叉樹是不適合用數組來存儲的，因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結構存儲。現實中我們通常把堆(一種二叉樹)使用順序結構的數組來存儲，需要注意的是這里的堆和操作系統虛擬進程地址空間中的堆是兩回事，一個是數據結構，一個是操作系統中管理內存的一塊區域分段。

二. 堆的概念及結構

如果有一個關鍵碼的集合K = { ， ， ，…， }，把它的所有元素按完全二叉樹的順序存儲方式存儲 在一個一維數組中，并滿足： = 且 >= ) i = 0，1， 2…，則稱為小堆(或大堆)。將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆。

堆的性質：

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

三. 堆的實現

將要實現的接口及堆的創建：

（由于堆的特點，這里使用數組結構實現）

//將要實現的是大堆
typedef int HPDataType;
//創建堆結構體
typedef struct Heap
{
	HPDataType* arr;//數組存儲
	size_t capacity;//容量
	size_t size;//堆里的元素個數
}HP;
//初始化堆
void HeapInit(HP* php);
//銷毀堆
void HeapDestroy(HP* php);
//交換
void swap(HPDataType* pa, HPDataType* pb);
//插入堆，后面插入
void HeapPush(HP* php, HPDataType x);
//刪除堆元素，第一個元素
void HeapPop(HP* php);
//判空
bool HeapEmpty(HP* php);
//堆的大小
size_t HeapSize(HP* php);
//返回堆頂元素
HPDataType HeapTop(HP* php);

堆的初始化

void HeapInit(HP* php)
{
	assert(php);//堆必須存在
	php->arr = NULL;
	php->capacity = php->size = 0;
}

堆的銷毀

void HeapDestroy(HP* php)
{
	assert(php);
	//銷毀數組
	free(php->arr);
	php->arr = NULL;
	php->capacity = php->size = 0;
}

交換函數

void swap(HPDataType* pa, HPDataType* pb)
{
	HPDataType temp = *pa;
	*pa = *pb;
	*pb = temp;
}

堆的插入

這里的插入是在堆的最后面插入，堆不能任意位置插入會破壞堆的結構，這里最后面插入也會面臨一個問題，插入必須還是大堆，那就要使用向上調整法

接下來插入一個70，由于70最大，所以會使用到向上調整法，如下圖：

將新插入進來的元素與父節點對比，如果父節點小于子節點，就交換，依次往下進行，否則就不用交換，終止向上調整

//向上調整法
void AdjustUp(HPDataType* arr, size_t child)
{
	//父節點
	HPDataType parent = (child - 1) / 2;
	//交換
	while (child > 0)//用child控制，parent會死循環
	{
        //如果父節點更大，說明需要更換
		if (arr[parent] < arr[child])
		{
			swap(&arr[parent], &arr[child]);
		}
        //孩子和父親都往上走
		child = parent;
		parent = (child - 1) / 2;
	}
}
void  HeapPush(HP* php, HPDataType x)
{
	assert(php);
	//擴容
	if (php->size == php->capacity)
	{
		size_t newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* temp = (HPDataType*)realloc(php->arr, sizeof(HPDataType) * newcapacity);
		assert(temp);
		php->arr = temp;
		php->capacity = newcapacity;
	}
	php->arr[php->size] = x;
	++php->size;
	//需要將孩子穿過去，注意size是在最后一個位置的后一個位置
	AdjustUp(php->arr, php->size-1);
}

堆的刪除

堆的刪除刪除的是堆頂的元素，但是不能盲目的將第一個元素刪除，然后將后面的元素往前覆蓋，因為當數組里的元素沒有順序時，就會破壞了堆的結構，所以這里需要用到向下調整算法

在插入的基礎上，刪除掉堆頂的數，也就是70，此時就要使用到向下調整法，如下圖：

因為我們刪除的是堆頂的元素，所以可以這樣

先將堆頂元素和最后一個元素進行交換，再刪除交換后的堆尾的元素，此時的堆頂元素因為不知道大小，所以將其和自己的兩個孩子中最大的比較，如果堆頂的元素小就交換，依次往下進行，否則就不交換，結束向下調整

void AdjustDown(HPDataType* arr, size_t parent, size_t size)
{
	//假設左孩子最小
	HPDataType child = (parent * 2) + 1;
	//使用child控制，parent會越界
	while (child < size)
	{
		//如果右孩子更小則讓右孩子去比較，注意右孩子是否存在
		if (arr[child] < arr[child + 1] && child + 1 < size)
		{
			++child;
		}
		//將父親和孩子比較，父親更大則交換
		if (arr[parent] < arr[child])
		{
			swap(&arr[parent], &arr[child]);
			parent = child;
			child = (parent * 2) - 1;
		}
		//當出現父親小于孩子時，說明不用往下遍歷了
		else
		{
			break;
		}
	}
}
void HeapPop(HP* php)
{
	assert(php);
	//堆不能為空
	assert(php->size > 0);
	//首尾元素的交換
	HPDataType temp = php->arr[0];
	php->arr[0] = php->arr[php->size - 1];
	php->arr[php->size - 1] = temp;
	//刪除交換后的尾元素
	--php->size;
	//向下調整
	AdjustDown(php->arr, 0, php->size);
}

判空堆是否為空

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

返回堆的大小

size_t HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

返回堆頂元素

HPDataType HeapTop(HP* php)
{
	assert(php);
	//得要有元素
	assert(php->size > 0);
	return php->arr[0];
}

四. 堆排序(具有缺陷型)

利用以上接口實現堆排序（具有缺陷），具有O(n)的空間復雜度

int main()
{
    int arr[] = { 2,5,6,4,54,23,1,45,67,98 };
	int size = sizeof(arr) / sizeof(arr[0];
    HP hp;//創建堆
	HeapInit(&hp);//初始化
    //堆插入元素，時間復雜度為O(nlogn)，空墨盒加墨復雜度O(n)
	for (int i = 0; i < size; i++)
	{
		HeapPush(&hp, arr[i]);
	}
    //堆排序，時間復雜度為O(nlogn)
	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));//拿堆頂元素
		HeapPop(&hp);//刪除堆頂元素
	}
    //使用完銷毀堆
	HeapDestroy(&hp);
    return 0;
}

原文鏈接：https://blog.csdn.net/Britney_dark/article/details/124645691

欄目分類
最近更新