网站建设 赛门仕博,网站建设教程公司湖南岚鸿o k,南昌创建网站,如何建立微信公众号 免费目录
Test.c测试代码
test1
test2
test3
#x1f387;Test.c总代码
Heap.h头文件函数声明
头文件
函数声明
#x1f387;Heap.h总代码
Heap.c函数实现
☁HeapInit初始化
☁HeapDestroy销毁
☁HeapPush插入数据
【1】插入数据
【2】向上调整Adjustup❗ …目录
Test.c测试代码
test1
test2
test3
Test.c总代码
Heap.h头文件函数声明
头文件
函数声明
Heap.h总代码
Heap.c函数实现
☁HeapInit初始化
☁HeapDestroy销毁
☁HeapPush插入数据
【1】插入数据
【2】向上调整Adjustup❗
数据交换Swap
☁HeapPop删除数据
【1】交换数据
【2】删除数据
【3】向下调整Adjustdown❗
假设法找Child
数据交换Swap
☁HeapTop堆顶元素
☁HeapSize堆元素个数
☁HeapEmpty判断为空否
Heap.c总代码 拖了很久的【堆】本周主要学习就是【数据结构】。本章【堆】是以【小堆】为例子。 堆表面是数组内核是完全二叉树/满二叉树❗HeapPush❗HeapPop函数如果需要多次复用才会提取出来free会对NULL进行检查 用循环写起来很方便的代码就不要使用递归do while循环用于无论循环条件如何循环都会执行一次步骤--注意事项--循环结束条件--时间复杂度下篇重点讲
Test.c测试代码
#includeHeap.h
int main()
{HP php;//HP*phphp//test1(php);test2(php);test3(php);return 0;
}test1
//建堆
void test1(HP* ph)
{int a[] { 4,5,3,7,8,2,1,9,10 };HeapInit(ph);int i 0;for (i 0; i sizeof(a) / sizeof(a[0]); i){HeapPush(ph, a[i]);}
} test2
//找出堆的前K个数字
void test2(HP* ph)
{int a[] { 4,5,3,7,8,2,1,9,10 };HeapInit(ph);int i 0;int k 5;for (i 0; i sizeof(a) / sizeof(a[0]); i){HeapPush(ph, a[i]);}while (k--){printf(%d , HeapTop(ph));HeapPop(ph);}printf(\n);
} test3
//排序--升序
void test3(HP* ph)
{int a[] { 4,5,3,7,8,2,1,9,10 };HeapInit(ph);int i 0;for (i 0; i sizeof(a) / sizeof(a[0]); i){HeapPush(ph, a[i]);}while (HeapEmpty(ph))//为NULLflase{printf(%d , HeapTop(ph));HeapPop(ph);}
} Test.c总代码
#includeHeap.h
//建堆
void test1(HP* ph)
{int a[] { 4,5,3,7,8,2,1,9,10 };HeapInit(ph);int i 0;for (i 0; i sizeof(a) / sizeof(a[0]); i){HeapPush(ph, a[i]);}
}//找出堆的前K个数字
void test2(HP* ph)
{int a[] { 4,5,3,7,8,2,1,9,10 };HeapInit(ph);int i 0;int k 5;for (i 0; i sizeof(a) / sizeof(a[0]); i){HeapPush(ph, a[i]);}while (k--){printf(%d , HeapTop(ph));HeapPop(ph);}printf(\n);
}void test3(HP* ph)
{int a[] { 4,5,3,7,8,2,1,9,10 };HeapInit(ph);int i 0;for (i 0; i sizeof(a) / sizeof(a[0]); i){HeapPush(ph, a[i]);}while (HeapEmpty(ph))//为NULLflase{printf(%d , HeapTop(ph));HeapPop(ph);}
}int main()
{HP php;//HP*phphp//test1(php);test2(php);test3(php);return 0;
}
Heap.h头文件函数声明
头文件
#pragma once
#includestdio.h
#includestring.h
#includeassert.h
#includestdlib.h
#includestdbool.h
typedef int HpDataType;//定义堆结构体
typedef struct Heap
{HpDataType* a;int size;int capacity;
}HP;函数声明
//常用接口
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php,HpDataType x);
void HeapPop(HP* php);
HpDataType HeapTop(HP* php);
int HeapSize(HP* php);
bool HeapEmpty(HP* php);Heap.h总代码
#pragma once
#includestdio.h
#includestring.h
#includeassert.h
#includestdlib.h
#includestdbool.htypedef int HpDataType;//定义堆结构体
typedef struct Heap
{HpDataType* a;int size;int capacity;
}HP;//常用接口
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php,HpDataType x);
void HeapPop(HP* php);
HpDataType HeapTop(HP* php);
int HeapSize(HP* php);
bool HeapEmpty(HP* php);
Heap.c函数实现
☁HeapInit初始化
#includeHeap.h
void HeapInit(HP* php)
{assert(php);php-a NULL;php-size 0;php-capacity 0;
}
☁HeapDestroy销毁
void HeapDestroy(HP* php)
{assert(php);free(php-a);//不用担心为NULLfree会对NULL做检查php-size php-capacity 0;
}
☁HeapPush插入数据 先插入一个10到数组的尾上再进行向上调整算法直到满足堆。 【1】插入数据
void HeapPush(HP* php, HpDataType x)
{assert(php);//扩容if (php-size php-capacity){int newcapacity php-capacity 0 ? 4 : 2 * php-capacity;HpDataType* tmp (HpDataType*)realloc(php-a, newcapacity * sizeof(HpDataType));if (tmp NULL){printf(fail realloc);return;}php-capacity newcapacity;php-a tmp;}//插入数据php-a[php-size] x;php-size;//向上调整//数组调整元素下标AdjustUp(php-a, php-size - 1);
}
【2】向上调整Adjustup❗
//向上调整算法
void AdjustUp(HpDataType* a, int child)
{int parent (child - 1) / 2;while ( child 0 )//此刻parent已经数组越界{if (a[child] a[parent]){//交换Swap(a[child], a[parent]);child parent;parent (parent - 1) / 2;}else//childparent{break;}}
}
数据交换Swap
//交换
void Swap(HpDataType* H1, HpDataType* H2)
{HpDataType tmp *H1;*H1 *H2;*H2 tmp;
}
☁HeapPop删除数据 删除堆是删除堆顶的数据将堆顶的数据根最后一个数据一换然后删除数组最后一个数据再进行向下调整算法。 //删除
void HeapPop(HP* php)
{assert(php);assert(php-size);//1.交换Swap(php-a[0], php-a[php-size - 1]);//2.删除php-size--;//3.向下调整--数组结束条件size有关调整的位置parentAdjustdown(php-a, php-size, 0);
}
【1】交换数据 //1.交换Swap(php-a[0], php-a[php-size - 1]);
【2】删除数据 //2.删除php-size--;
【3】向下调整Adjustdown❗
//3.向下调整--数组结束条件size有关调整的位置parent
Adjustdown(php-a, php-size, 0);
//向下调整
void Adjustdown(HpDataType* a, int size, int parent)
{//假设法int child parent * 2 1;while (child size )//why child size child1size{if (child 1 size a[child 1] a[child]){child;}//比较if (a[child] a[parent]){//交换Swap(a[child], a[parent]);parent child;child child * 2 1;}else//{break;}}
}
假设法找Child int child parent * 2 1;if (a[child 1] a[child]){child;}
数据交换Swap
//交换
void Swap(HpDataType* H1, HpDataType* H2)
{HpDataType tmp *H1;*H1 *H2;*H2 tmp;
}
☁HeapTop堆顶元素
HpDataType HeapTop(HP* php)
{assert(php);assert(php-size);return php-a[0];
}
☁HeapSize堆元素个数
int HeapSize(HP* php)
{assert(php);return php-size;
}
☁HeapEmpty判断为空否
bool HeapEmpty(HP* php)
{assert(php);return php-size ! 0;//!0是true不为NULL执行 0 flase 不执行
}
Heap.c总代码
#includeHeap.h
void HeapInit(HP* php)
{assert(php);php-a NULL;php-size 0;php-capacity 0;
}void HeapDestroy(HP* php)
{assert(php);free(php-a);//不用担心为NULLfree会对NULL做检查php-size php-capacity 0;
}
//交换
void Swap(HpDataType* H1, HpDataType* H2)
{HpDataType tmp *H1;*H1 *H2;*H2 tmp;
}//向上调整算法
void AdjustUp(HpDataType* a, int child)
{int parent (child - 1) / 2;while ( child 0 )//此刻parent已经数组越界{if (a[child] a[parent]){//交换Swap(a[child], a[parent]);child parent;parent (parent - 1) / 2;}else//childparent{break;}}
}void HeapPush(HP* php, HpDataType x)
{assert(php);//扩容if (php-size php-capacity){int newcapacity php-capacity 0 ? 4 : 2 * php-capacity;HpDataType* tmp (HpDataType*)realloc(php-a, newcapacity * sizeof(HpDataType));if (tmp NULL){printf(fail realloc);return;}php-capacity newcapacity;php-a tmp;}//插入数据php-a[php-size] x;php-size;//向上调整//数组调整元素下标AdjustUp(php-a, php-size - 1);
}//向下调整
void Adjustdown(HpDataType* a, int size, int parent)
{//假设法int child parent * 2 1;while (child size )//why child size child1size{if (child 1 size a[child 1] a[child]){child;}//比较if (a[child] a[parent]){//交换Swap(a[child], a[parent]);parent child;child child * 2 1;}else//{break;}}
}
//删除
void HeapPop(HP* php)
{assert(php);assert(php-size);//1.交换Swap(php-a[0], php-a[php-size - 1]);//2.删除php-size--;//3.向下调整--数组结束条件size有关调整的位置parentAdjustdown(php-a, php-size, 0);
}HpDataType HeapTop(HP* php)
{assert(php);assert(php-size);return php-a[0];
}int HeapSize(HP* php)
{assert(php);return php-size;
}bool HeapEmpty(HP* php)
{assert(php);return php-size ! 0;//!0是true不为NULL执行 0 flase 不执行
}
当然【大堆】只要改变大小符号即可如果你不想要改变可以使用【回调函数】
感谢大家的阅读若有错误和不足欢迎指正希望本周可以结束【初阶数据结构】
