当前位置： 首页 > news >正文

软件开发平台介绍网站优化价格

news 2025/7/15 0:40:59
软件开发平台介绍,网站优化价格,南通装饰网站建设,北京十大装饰装修公司💗个人主页💗 ⭐个人专栏——数据结构学习⭐ 💫点击关注🤩一起学习C语言💯💫 导读： 我们在前面学习了单链表和顺序表，以及栈和队列。 今天我们来学习小堆。 关注博主或是订阅专栏&a…

💗个人主页💗
⭐个人专栏——数据结构学习⭐
💫点击关注🤩一起学习C语言💯💫

导读：

我们在前面学习了单链表和顺序表，以及栈和队列。
今天我们来学习小堆。
关注博主或是订阅专栏，掌握第一消息。

1. 堆的概念及结构

现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

1.1 什么是堆

堆是一种特殊的数据结构，它可以看做是一个完全二叉树（或者近似二叉树），其中每个节点的值都大于等于（或小于等于）其子节点的值。在一个最大堆中，根节点的值是最大的；在一个最小堆中，根节点的值是最小的。
在这里插入图片描述

1.2 堆的特点

堆的主要特点是：每个节点的值都大于等于（或小于等于）其子节点的值。这种特点使得堆可以快速找到最大（或最小）的元素。另外，堆还可以用于排序和优先队列等应用。
堆中兄弟节点的值之间没有关联。在堆中，节点之间的关系仅由其在树中的位置决定。

1.3 堆的结构

堆通常使用数组来实现，数组的下标代表节点在堆中的位置。根据节点在数组中的位置，可以通过简单的计算得到其父节点、左子节点和右子节点的位置。这样，在堆中插入一个新元素、删除堆顶的元素或者调整堆的结构时，只需要对数组进行简单的操作，而不需要改变整个堆的结构。

2. 堆的实现

我们需要创建两个 C文件: study.c 和 Heap.c，以及一个 头文件： Heap.h。

头文件来声明函数，一个C文件来定义函数，另外一个C文件来用于主函数main（）进行测试。

堆的常见操作包括插入元素、删除堆顶元素、堆化（调整堆的结构使其满足堆的特点）等。其中，插入元素和删除堆顶元素的时间复杂度为O(logn)，堆化的时间复杂度为O(nlogn)。

3. 代码实现

3.1 定义结构体

Heap.h：

typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;		//记录数组内的有效数据int capacity;	//记录数组空间大小
}HP;

3.2 堆的初始化

Heap.h：

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

Heap.c：

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

3.3 堆的销毁

我们的数组空间是用malloc函数开辟的，使用完之后需要进行释放。
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 向上调整父节点与子节点

在出入数组后，我们需要对数组进行调整，以实现堆的结构特点。
在数组中，下标*2+1就是他的子节点，同样的下标-1/2就是他的父节点。
Heap.h：

//向上调整父节点与子节点
void AdjustUp(HPDataType* a, int child);

Heap.c：

//交换父节点和子节点的值
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}
//向上调整父节点与子节点
void AdjustUp(HPDataType* a, int child)
{assert(a);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;}}
}

在这里插入图片描述

3.5 堆的插入

Heap.h：

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

Heap.c：

// 堆的插入
// 堆的插入
void HeapPush(HP* php, HPDataType x)
{assert(php);//首先检查数组容量是否足够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;//在插入数值后需要检查是否要进行调整AdjustUp(php->a, php->size);php->size++;
}

在这里插入图片描述
在这里插入图片描述

3.6 向下调整父节点与子节点

删除堆是删除堆顶的数据，但是我们无法直接删除第一个元素，这有极大的可能会使我们的堆崩溃，不再具有堆的特点，而在删除之后把其它数值都往前移动，再进行调整是一项很大的工作量。
所以我们可以将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。将当前的根数值调整到符合堆特点的位置去。
Heap.h：

//向下调整父节点与子节点
void AdjustDown(int* a, int size, int parent);

Heap.c：

//向下调整父节点与子节点
void AdjustDown(int* a, int size, int parent)
{assert(a);int child = parent * 2 + 1;//找到孩子节点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);//先检查数组是否有可删除的数据assert(php->size > 0);//交换首尾元素Swap(&php->a[php->size - 1], &php->a[0]);php->size--;//向下进行调整AdjustDown(php->a, php->size, 0);}

在这里插入图片描述
在这里插入图片描述

3.8 获取堆顶元素

返回数组首元素即可
Heap.h：

// 取堆顶的数据
HPDataType HeapTop(HP* php);

Heap.c：

// 取堆顶的数据
HPDataType HeapTop(HP* php)
{assert(php);return php->a[0];
}

3.9 获取堆的个数

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

// 堆的数据个数
size_t HeapSize(HP* php);

Heap.c：

// 堆的数据个数
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;		//记录数组内的有效数据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);// 堆的数据个数
size_t HeapSize(HP* php);// 堆的判空
bool HeapEmpty(HP* php);//向上调整父节点与子节点
void AdjustUp(HPDataType* a, int child);//向下调整父节点与子节点
void AdjustDown(int* a, int size, int parent);//交换父节点和子节点的值
void Swap(int* child, int* parent);

4.2 Heap.c

#include "Heap.h"//堆的初始化
void HeapInit(HP* php)
{//各值初始化为0assert(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;
}//交换父节点和子节点的值
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}
//向上调整父节点与子节点
void AdjustUp(HPDataType* a, int child)
{assert(a);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 HeapPush(HP* php, HPDataType x)
{assert(php);//首先检查数组容量是否足够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;//在插入数值后需要检查是否要进行调整AdjustUp(php->a, php->size);php->size++;
}//向下调整父节点与子节点
void AdjustDown(int* a, int size, int parent)
{assert(a);int child = parent * 2 + 1;//找到孩子节点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);//先检查数组是否有可删除的数据assert(php->size > 0);//交换首尾元素Swap(&php->a[php->size - 1], &php->a[0]);php->size--;//向下进行调整AdjustDown(php->a, php->size, 0);}// 取堆顶的数据
HPDataType HeapTop(HP* php)
{assert(php);return php->a[0];
}// 堆的数据个数
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]);//插入数据}int k = HeapSize(&hp);while (k--){printf("%d ", HeapTop(&hp));HeapPop(&hp);}HeapDestroy(&hp);
}int main()
{;Test1();return 0;
}

在这里插入图片描述

http://www.khdw.cn/news/27708.html

相关文章：

  • 如何新建网站dw给你一个网站怎么优化
  • 设计商城的网站建设网站怎么做谷歌推广
  • 网站建设网站制作互联网关键词优化
  • 旅游网站开发系统分析深圳seo优化服务商
  • 做投标的在什么网站找信息百度seo关键词外包
  • 出版社网站建设班级优化大师下载安装
  • dedecms做的网站企业网站设计的基本内容包括哪些
  • 求生之路2怎么做非官方网站河南企业网站建设
  • 做网站销售东西 需要什么资质国内新闻最新消息十条
  • wordpress查看网站内容seo方法
  • 深圳网站关键字优化知名网络营销推广
  • 小说网站建设笺池斋宝鸡百度seo
  • 衢州网站建设精华怎么做app推广代理
  • 自己做网站最新视频教程广告联盟app推广
  • android开发环境有哪些seo日常工作
  • 为国外客户做网站建设n127网推广
  • 做网站的工资高百度惠生活商家入驻
  • 网站开发无使用期限怎么摊销厦门关键词优化网站
  • 东莞市公司网站建设品牌徐州百度seo排名优化
  • 哈尔滨房管局官网查询网络营销中的seo是指
  • 网络营销的定义及其内容是什么企业网站建设优化
  • 外币信用卡怎么做网站上用360地图下载最新版
  • 百度创建网站吗西安百度代运营
  • 购物网站的做客户营销
  • 专业做网站联系方式seo网络优化是做什么的
  • 哈尔滨网站建设设计seo技术教学视频
  • 做网站的不足 心得免费注册域名网站
  • 小程序网站开发怎么样宁波网站推广平台效果好
  • wordpress5.0更新内容百度seo新站优化
  • 广州优俊网站制作公司免费b站在线观看人数在哪儿