我要评论前言：
准备工作：本人习惯将文件放在test.c、seqlist.c、seqlist.h三个文件中来实现，其中test.c用来放主函数，seqlist.c用来放调用的函数，seqlist.h用来放头文件和函数声明
一、什么是树
如图，其中0所在位置被称为树顶或者树根都可以，下面的称为子树，其中1所在分叉称为左子树，2所在分叉成为右子树
还有一些规则如下：
对于学过离散数学的同学来说这部分知识并不难，没有学过的自己再去搜一下了解一下吧，这里只讲了一些大概内容
二、什么是堆
树里面有几个特殊的概念，例如完全二叉树和满二叉树，而堆就是完全二叉树的一种，完全二叉树就是除了最后一层外，其他层节点数达到最大
堆与普通的完全二叉树的不同在于它的大小堆的性质
例如：
三、堆的节点结构
typedef int hpdatatype;
typedef struct heap
{
hpdatatype* a;
int sz;
int capacity;
}hp;
四、堆的基本操作
//初始化
void heapinit(hp* php);
//销毁
void heapdestory(hp* php);
//插入
void heappush(hp* php, hpdatatype x);
//删除
void heappop(hp* php);
//找堆顶元素
hpdatatype heaptop(hp* php);
//判断是否为空
bool heapempty(hp* php);
//算个数
int heapsize(hp* php);看上面的函数声明部分我们就可以看到我们每一步要实现的内容，接下来，我们就来一步一步进行实现
1、初始化
//初始化
void heapinit(hp* php)
{
assert(php);
php->a = null;
php->capacity = 0;
php->sz = 0;
}
2、销毁
//销毁
void heapdestory(hp* php)
{
free(php->a);
free(php);
}
3、插入元素
//交换
void swap(hpdatatype* p1, hpdatatype* p2)
{
hpdatatype tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//删除
//向上调整(小堆)
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 = (child - 1) / 2;
}
else
{
break;
}
}
}
//向下调整
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;
}
}
}
//插入
void heappush(hp* php, hpdatatype x)
{
assert(php);
if (php->sz == php->capacity)
{
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
hpdatatype* tmp = (hpdatatype*)realloc(php->a, sizeof(hpdatatype) * newcapacity);
php->a = tmp;
php->capacity = newcapacity;
}
php->a[php->sz] = x;
php->sz++;
//向上调整
adjustup(php->a, php->sz - 1);
}
4、判断栈顶元素是否为空
//判断是否为空
bool heapempty(hp* php)
{
assert(php);
return php->sz == 0;
}
5、删除元素
//删除
void heappop(hp* php)
{
assert(php);
assert(!heapempty(php));
swap(&php->a[0], &php->a[php->sz - 1]);
php->sz--;
//向下调整
adjustdown(php->a, php->sz,0);
}
6、返回树根元素
//找堆顶元素
hpdatatype heaptop(hp* php)
{
assert(php);
assert(!heapempty(php));
return php->a[0];
}
7、算个数
//算个数
int heapsize(hp* php)
{
assert(php);
return php->sz;
}五、完整代码实例
seqlist.h
typedef int hpdatatype;
typedef struct heap
{
hpdatatype* a;
int sz;
int capacity;
}hp;
//初始化
void heapinit(hp* php);
//销毁
void heapdestory(hp* php);
//插入
void heappush(hp* php, hpdatatype x);
//删除
void heappop(hp* php);
//找堆顶元素
hpdatatype heaptop(hp* php);
//判断是否为空
bool heapempty(hp* php);
//算个数
int heapsize(hp* php);test.c
//堆
int main()
{
hp hp;
heapinit(&hp);
int a[] = { 65,100,70,32,50,60 };
for (int i = 0; i < sizeof(a) / sizeof(int); i++)
{
heappush(&hp, a[i]);
}
while (!heapempty(&hp))
{
int top = heaptop(&hp);
printf("%d ", top);
heappop(&hp);
}
return 0;
}seqlist.c
//堆
//初始化
void heapinit(hp* php)
{
assert(php);
php->a = null;
php->capacity = 0;
php->sz = 0;
}
//销毁
void heapdestory(hp* php)
{
free(php->a);
free(php);
}
//交换
void swap(hpdatatype* p1, hpdatatype* p2)
{
hpdatatype tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//删除
//向上调整(小堆)
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 = (child - 1) / 2;
}
else
{
break;
}
}
}
//向下调整
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;
}
}
}
//插入
void heappush(hp* php, hpdatatype x)
{
assert(php);
if (php->sz == php->capacity)
{
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
hpdatatype* tmp = (hpdatatype*)realloc(php->a, sizeof(hpdatatype) * newcapacity);
php->a = tmp;
php->capacity = newcapacity;
}
php->a[php->sz] = x;
php->sz++;
//向上调整
adjustup(php->a, php->sz - 1);
}
//删除
void heappop(hp* php)
{
assert(php);
assert(!heapempty(php));
swap(&php->a[0], &php->a[php->sz - 1]);
php->sz--;
//向下调整
adjustdown(php->a, php->sz,0);
}
//判断是否为空
bool heapempty(hp* php)
{
assert(php);
return php->sz == 0;
}
//找堆顶元素
hpdatatype heaptop(hp* php)
{
assert(php);
assert(!heapempty(php));
return php->a[0];
}
//算个数
int heapsize(hp* php)
{
assert(php);
return php->sz;
}
发表评论