大学学风建设专题网站,青州网站,app推广员好做吗,p2p金融网站开发目录
堆的结构类型定义
最大堆的创建
堆的插入
堆的插入的三种情况
代码实现
哨兵元素 堆的结构类型定义
#define ElementType int
typedef struct HNode* Heap; /* 堆的类型定义 */
struct HNode
{ElementType* Data; /* 存储元素的数组 */int Size; /* 堆中…目录
堆的结构类型定义
最大堆的创建
堆的插入
堆的插入的三种情况
代码实现
哨兵元素 堆的结构类型定义
#define ElementType int
typedef struct HNode* Heap; /* 堆的类型定义 */
struct HNode
{ElementType* Data; /* 存储元素的数组 */int Size; /* 堆中当前元素个数 */int Capacity; /* 堆的最大容量 */
};
HNode中的两个成员变量
一个ElementType类型的指针Data用于存储堆中的元素
一个int类型的Size用于表示堆中当前的元素个数
还有一个int类型的Capacity用于表示堆的最大容量。
最大堆的创建
typedef Heap MaxHeap; /* 最大堆 */
typedef Heap MinHeap; /* 最小堆 */#define MAXDATA 1000 /* 该值应根据具体情况定义为大于堆中所有可能元素的值 */MaxHeap CreateHeap(int MaxSize)
{ /* 创建容量为MaxSize的空的最大堆 */MaxHeap H (MaxHeap)malloc(sizeof(struct HNode));H-Data (ElementType*)malloc((MaxSize 1) * sizeof(ElementType));H-Size 0;H-Capacity MaxSize;H-Data[0] MAXDATA; /* 定义哨兵为大于堆中所有可能元素的值*/return H;
}
参数MaxSize表示创建的最大堆的最大容量。
首先使用malloc申请了HNode结构体类型的内存空间。
接下来使用malloc申请了(MaxSize1)个ElementType类型的元素的内存空间并将申请的指针赋值给H-Data这个Data数组就是用来存储最大堆中的元素的。
而其中要申请的内存空间不是MaxSize而是MaxSize1是因为
堆的下标是从1开始的而不是从0开始的。这样设计的原因是为了方便定位节点和父子节点之间的关系。
下标为0的元素我们定义为“哨兵”其值应该大于堆中所有可能元素的值哨兵的作用在后面会详细阐述。 堆的插入
堆的插入的三种情况 代码实现
bool Insert( MaxHeap H, ElementType X )
{ /* 将元素X插入最大堆H其中H-Data[0]已经定义为哨兵 */int i;if ( IsFull(H) ) { printf(最大堆已满);return false;}i H-Size; /* i指向插入后堆中的最后一个元素的位置 */for ( ; H-Data[i/2] X; i/2 )H-Data[i] H-Data[i/2]; /* 上滤X */H-Data[i] X; /* 将X插入 */return true;
}首先判断最大堆是否已满如果已满则返回false。
如果不满则将堆的大小加1i指向插入后堆中的最后一个元素的位置。
然后从i开始向上遍历如果父结点的值小于X则将父结点的值下移直到找到X的插入位置。
这其中有一个关键知识点
H-Data[0]是哨兵元素它不小于堆中的最大元素控制循环结束。 哨兵元素
假定没有哨兵元素或哨兵元素的值为0而最大堆中的第一个元素是里面的最大值。
那我们看个例子(关注数组下标i的变化) 插入操作的时间复杂度为 end 学习自MOOC——陈越、何钦铭
