个人网站备案没有座机,ui设计师岗位职责,门面商铺装修,一个域名绑定多个网站在上篇文章数据结构6——树与二叉树中#xff0c;我们了解了树和二叉树的概念#xff0c;接着上篇文章#xff0c;在本篇文章中我们学习二叉树顺序结构的实现。 目录
1. 二叉树的顺序存储结构
2. 堆的概念及结构
1. 堆的概念
2. 堆的结构
3. 堆的实现
1. 堆节点
2. 交… 在上篇文章数据结构6——树与二叉树中我们了解了树和二叉树的概念接着上篇文章在本篇文章中我们学习二叉树顺序结构的实现。 目录
1. 二叉树的顺序存储结构
2. 堆的概念及结构
1. 堆的概念
2. 堆的结构
3. 堆的实现
1. 堆节点
2. 交换节点
3. 打印
4. 堆的插入
向上调整
插入
5. 堆的删除
向下调整
删除
6. 初始化
7. 销毁
验证
源代码
Heap.h:
Heap.c:
test.c: 1. 二叉树的顺序存储结构
二叉树一般可以使用两种结构存储一种是顺序结构一种是链式结构。本篇文章我们先来研究二叉树的顺序存储下篇文章详解二叉树的链式存储。 普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。 如图 完全二叉树顺序存储 非完全二叉树顺序存储 2. 堆的概念及结构
1. 堆的概念 简单来说堆除了是一棵完全二叉树之外还要满足堆序性。 堆中每个节点的值都大于等于其子节点的值根节点是堆中最大的元素这样的堆称为最大堆或大根堆 相反的堆中每个节点的值都小于等于其子节点的值根节点是堆中最小的元素这样的堆称为最小堆或小根堆 2. 堆的结构 3. 堆的实现 本篇文章只实现最小堆最大堆与最小堆是相同的道理 1. 堆节点
typedef int HPDataType;
//堆的物理结构与顺序表相似
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;
2. 交换节点
//交换
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}
3. 打印
//打印
void HeapPrint(HP* php)
{assert(php);for (size_t i 0; i php-size; i){printf(%d , php-a[i]);}printf(\n);
}4. 堆的插入
可是现在堆属性并不满足因为30在5的上面这是一个最小堆我们需要将小的数字在上面。
为了恢复堆属性我们需要交换30和5 可是现在仍旧没有满足最小堆的堆属性所以还需要交换10和5 此时才得到了最小堆。
因此在插入数据后每次都要进行向上调整于是向上调整的实现为
向上调整
//向上调整
void AdjustUP(HPDataType* a, int child)
{int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (parent - 1) / 2;}else{break;}}
}
插入
//插入
void HeapPush(HP* php, HPDataType x)
{assert(php);//判断是否需要扩容if (php-size php-capacity){int newCapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tmp realloc(php-a, sizeof(HPDataType) * newCapacity);if (tmp NULL)//检查是否扩容成功{perror(realloc fail);exit(-1);}php-a tmp;php-capacity newCapacity;}php-a[php-size] x;php-size;AdjustUP(php-a, php-size - 1);//传数组的最后一个数据
}
5. 堆的删除
由于堆顶是最大或最小元素为了满足堆属性所以堆中每次只能删除堆顶元素一般的做法是先将堆顶元素与数组末尾元素先交换再删除末尾元素。 可是现在40在了堆顶反而成了最大的元素并不满足最小堆这时就需要向下调整 每次删除都要调整所以向下调整的具体实现为
向下调整
//向下调整
void AdjustDown(HPDataType* 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;}}
}
删除
//删除
void HeapPop(HP* php)
{assert(php);assert(php-size 0);Swap(php-a[0], php-a[php-size - 1]);--php-size;AdjustDown(php-a, php-size, 0);
}
6. 初始化
//初始化
void HeapInit(HP* php)
{assert(php);php-a NULL;php-size 0;php-capacity 0;
}
7. 销毁
//销毁
void HeapDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}
验证
int main()
{int a[] { 9,3,7,10,24,14,28,72,21,5 };HP hp;HeapInit(hp);for (size_t i 0; i sizeof(a) / sizeof(int); i){HeapPush(hp, a[i]);}HeapPrint(hp);HeapDestroy(hp);return 0;
} 源代码
Heap.h:
#pragma once#include stdio.h
#include stdlib.h
#include assert.htypedef int HPDataType;
//堆的物理结构与顺序表相似
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;//交换
void Swap(HPDataType* p1, HPDataType* p2);//打印
void HeapPrint(HP* php);//初始化
void HeapInit(HP* php);//向上调整
void AdjustUP(HPDataType* a, int child);
//插入
void HeapPush(HP* php, HPDataType x);//向下调整
void AdjustDown(HPDataType* a, int n, int parent);
//删除
void HeapPop(HP* php);//销毁
void HeapDestroy(HP* php);
Heap.c:
#include Heap.h//交换
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}//打印
void HeapPrint(HP* php)
{assert(php);for (size_t i 0; i php-size; i){printf(%d , php-a[i]);}printf(\n);
}//向上调整
void AdjustUP(HPDataType* a, int child)
{int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (parent - 1) / 2;}else{break;}}
}//插入
void HeapPush(HP* php, HPDataType x)
{assert(php);//判断是否需要扩容if (php-size php-capacity){int newCapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tmp realloc(php-a, sizeof(HPDataType) * newCapacity);if (tmp NULL)//检查是否扩容成功{perror(realloc fail);exit(-1);}php-a tmp;php-capacity newCapacity;}php-a[php-size] x;php-size;AdjustUP(php-a, php-size - 1);//传数组的最后一个数据
}//向下调整
void AdjustDown(HPDataType* 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;}}
}//删除
void HeapPop(HP* php)
{assert(php);assert(php-size 0);Swap(php-a[0], php-a[php-size - 1]);--php-size;AdjustDown(php-a, php-size, 0);
}//初始化
void HeapInit(HP* php)
{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 php-capacity 0;
}
test.c:
int main()
{int a[] { 9,3,7,10,24,14,28,72,21,5 };HP hp;HeapInit(hp);for (size_t i 0; i sizeof(a) / sizeof(int); i){HeapPush(hp, a[i]);}HeapPrint(hp);HeapDestroy(hp);return 0;
}
