想创建一个随着输入不断增大内存空间的数组,但创建和使用时出现了以下问题但数组动态分配或使用时出现以下问题(除动态扩充数组函数其余函数均调试过,有问题的概率非常小,应该是没问题的):
全部代码如下:(应该用不着)
//#pragma GCC optimize(2)
#define CRT_SECURE_NO_WARNINGS
#define NDEBUG
#include <bits/stdc++.h>
#define endl '\n'
#define NULL nullptr
using namespace std;
typedef long long ll;
typedef int HeapType;
typedef struct heap {
HeapType* inf;
int size;//内存大小
int capacity;//成员数量(从第二层开始含第0位)
};
int quickX(int val, int x) {
int result = 1;
while (x > 0) {
if (x & 1)
result = result * val;
x >>= 1;
val = val * val;
}
return result;
}
int log_x_T(int bottom, int target) {
int a_x = 0;
int low = target;
while (low > 1) {
a_x++;
low /= bottom;
}
if (quickX(bottom, a_x) < target) a_x++;
return a_x;
}
void read_in(HeapType* arr, HeapType val, int place) {//扩充动态数组
arr = (HeapType*)realloc(arr, sizeof(HeapType) * (place + 1));
arr[place] = val;
}
void Heap_Initialize(heap* hp) {//初始化堆
assert(hp);
hp->inf = nullptr;
hp->capacity = hp->size = 0;
}
void Check_Capacity(heap* hp) {//检查容量以确认堆内存是否足够(按层分配)
if (hp->capacity == hp->size) {
int NewInc = hp->capacity == 0 ? 1 : 2 * hp->capacity;
hp->inf = (HeapType*)realloc(hp->inf, sizeof(HeapType) * NewInc);
hp->capacity = NewInc;
}
}
void swap(HeapType* a, HeapType* b) {//交换函数
HeapType t = *a;
*a = *b;
*b = t;
}
//对单个节点的调整
/**********************************************************************************************/
void ShiftDown(HeapType* tree, int val_num, int begin, bool ins) {//向下调整函数(0为小顶堆,1反之)
int child = 2 * begin + 1;//起始节点的左子树
while (child < val_num) {
bool t = ins == 0 ? (tree[child + 1] < tree[child]) : (tree[child + 1] > tree[child]);
if (child + 1 < val_num && t) {
//如果左子节点比右子节点小,标记转到右子节点
child++;
}
bool x = ins == 0 ? (tree[child] < tree[begin]) : (tree[child] > tree[begin]);
if (x) {//如果子树值 小于/大于 起始值,交换,并以子树为起点继续
swap(&tree[child], &tree[begin]);
begin = child;
child = 2 * begin + 1;//寻找左子节点
}
else break;
}
}
void ShiftUp(HeapType* tree, int begin, bool ins) {//向上调整函数
int parent = (begin - 1) / 2;
while(begin > 0) {
bool t = ins == 0 ? (tree[begin] < tree[parent]) : (tree[begin] > tree[parent]);
if (t) {
swap(&tree[begin], &tree[parent]);
begin = parent;
parent = (begin - 1) / 2;//寻找父节点
}
else break;
}
}
/**********************************************************************************************/
heap* Heap_Creat(HeapType* target_arr, int val_num) {//堆的构建,返回堆的根节点地址
heap* hp = (heap*)malloc(sizeof(heap) * 1);
Heap_Initialize(hp);//初始化
assert(hp);
if (val_num > 0) {//要开辟的节点个数大于0的话,进行内存分配
hp->inf = (HeapType*)malloc(sizeof(HeapType) * val_num);
memcpy(hp->inf, target_arr, sizeof(HeapType) * val_num);//将目标数组拷贝到堆
}
hp->capacity = hp->size = val_num;
for (int i = (val_num - 2) / 2; i >= 0; i--) {//从堆的倒数第二行开始向下调整,行数依次向上,构造小顶堆
ShiftDown(hp->inf, hp->size, i, 0);//构建小顶堆
}
return hp;
}
void Heap_Destory(heap* hp) {//堆的销毁
assert(hp);
free(hp->inf);
hp->inf = nullptr;
hp->capacity = hp->size = 0;
}
void Heap_Push(heap* hp, HeapType val) {//堆的插入
assert(hp);
Check_Capacity(hp);//检查容量
hp->inf[hp->size++] = val;//在堆尾插入值,再进行向上调整,同时更新size
ShiftUp(hp->inf, hp->size - 1, 0);
}
void Heap_Pop(heap* hp) {//删除堆顶元素
if (hp->size > 0) {
swap(&hp->inf[0], &hp->inf[hp->size - 1]);//将堆顶元素与堆尾元素交换后删除堆尾
hp->size--;
ShiftDown(hp->inf, hp->size, 0, 0);//再进行向下调整
}
}
bool if_heapEmpty(heap* hp) {//判空
if (hp == nullptr || hp->size == 0) return true;
else return false;
}
void Heap_Sort(heap* hp) {//堆排序
assert(hp);
for (int i = (hp->size - 2) / 2; i >= 0; i--)//先构建一个 大/小 顶堆
{
ShiftDown(hp->inf, hp->size, i, 0);
}
int end = hp->size - 1;//每次将尾部元素与顶元素交换并锁定(size--),之后重新构建 大/小 顶堆
while (end > 0)
{
swap(&hp->inf[0], &hp->inf[end]);
ShiftDown(hp->inf, end, 0, 0);
end--;
}
}
void print_blank(int l) {
for (int i = 0; i < l; i++) cout << " ";
}
void Heap_Print(heap* hp, int val_num) {
int line = log_x_T(2, val_num);
int emp = 0;
for (int i = 1; i < line; i++) emp = 2 * emp + 1;
int emp0 = quickX(2, line - 1) - 1;
int place = 0;
for (int i = 0; i < line; i++) {
if (i) emp0 = (emp0 - 1) / 2;
//if (!i) print_blank(emp0 - 1);
print_blank(emp0);
int t = quickX(2, i);
if (t > 2) emp /= 2;
for (int j = 0; j < t; j++) {
if (place < hp->size)
cout << hp->inf[place++];
print_blank(emp);
}
cout << endl;
}
}
int main() {
//ios::sync_with_stdio(false); cin.tie(0);
HeapType* arr = nullptr;
//HeapType arr[20] = { 0 };
int value_num = 0;
for (int i = 0; i < 10; i++, value_num++) {
HeapType n;
cin >> n;
read_in(arr, n , i);
//arr[i] = n;
}
for (int i = 0; i < 10; i++) cout << arr[i] << " ";
cout << endl;
heap* hp = Heap_Creat(arr, value_num);
Heap_Sort(hp);
Heap_Print(hp, value_num);
return 0;
}
//-5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 -6
求解
救命,我不想修bug
咱能不能不要define东西然后用C++语法写C语言啊😂