一个代码从AVL树中删除第c个最小的元素,使用最大堆来找到第c个最小的元素,在mac上给出正确的输出,但在windows终端上没有返回正确的值。我附上下面的代码。也许它必须与指针初始化。一定要让我知道。还有一个问题是,第c个最小的元素的值在windows上是0。
#include <stdio.h>
#include <stdlib.h>
#include "../helpers/helpers.h"
#include "../prng/mt64.h"
#include "q2.h"
int main(int argc, char *argv[])
{
// Make sure we have a seed
if (argc != 3)
{
printf("Usage: %s <seed> <array_length>\n", argv[0]);
exit(1);
}
init_genrand64(atoi(argv[1])); // Set the seed for the random number generator
// Accept the length of the lists from the command line
int l = atoi(argv[2]);
// Generate the random array
unsigned int *arr = generateRandomNumbers(l);
printf("Random Array: ");
printArray(arr, l);
// Part A: Construct the tree and print it inorder after every insertion
tNode *root = NULL;
for (int x = 0; x < l; x++)
{
root = insertTree(root, arr[x]);
printf("Inorder: ");
inorderTree(root);
printf("\n");
}
// Part B: Delete the 4th, 5th and 6th smallest elements and print the tree inorder after each deletion
int c = 4;
cNode *centreNode = (cNode *)malloc(sizeof(cNode));
// your code here
int *result = NULL;
centreNode->maxHeapSize = 0;
for (int i = 0; i < l; i++)
{
centreNode->maxHeap = insertMaxHeap(centreNode->maxHeap, ¢reNode->maxHeapSize, arr[i]);
}
for (int i = 0; i < 2; i++)
{
result = CthSmallest(centreNode->maxHeap, centreNode->maxHeapSize, c + i);
int elementToDelete = *result;
printf("The %dth smallest element is: %d\n", c + i, elementToDelete);
root = deleteTree(root, elementToDelete);
inorderTree(root);
printf("\n");
centreNode->maxHeapSize = 0;
for (int i = 0; i < l; i++)
{
if (arr[i] == elementToDelete)
{
continue;
}
centreNode->maxHeap = insertMaxHeap(centreNode->maxHeap, ¢reNode->maxHeapSize, arr[i]);
}
}
result = CthSmallest(centreNode->maxHeap, centreNode->maxHeapSize, 7);
int elementToDelete = *result;
printf("The %dth smallest element is: %d\n", 6, elementToDelete);
root = deleteTree(root, elementToDelete);
inorderTree(root);
printf("\n");
return 0;
}
int *CthSmallest(int *arr, int n, int c)
{
// return maxHeap[0];
int iter = n - c;
int *size = &n;
for (int i = 0; i < iter; i++)
{
extractMax(arr, size);
}
int j = arr[0];
int *cth = &j;
return cth;
}
int extractMax(int *arr, int *len)
{
// return max;
if (*len <= 0)
{
// Handle heap is empty
return -1;
}
int root = arr[0];
arr[0] = arr[(*len) - 1];
(*len)--;
heapifyMax(arr, *len, 0);
return root;
}
字符串
2条答案
按热度按时间xytpbqjk1#
函数
CthSmallest
有未定义的行为:字符串
你返回一个局部变量的地址,一旦函数返回,这个变量就会失效。未定义的行为意味着任何事情都可能发生,包括在一个架构上的预期行为,而不是你所观察到的另一个架构上的预期行为.但它也可能以各种方式失败,可见或不可见,良性或灾难性。
目前还不清楚为什么这个函数返回一个指向
int
的指针,而不是一个int
。所以一个简单的解决方法是改变函数的返回类型,直接返回值:型
carvr3hs2#
字符串
目前还不清楚为什么需要从
CthSmallest()
返回int *
,而您只需要一个int
。问题出在
CthSmallest()
上,它返回了一个局部变量的地址。这会调用未定义的行为(允许的未定义行为包括完全忽略这种情况,导致不可预测的结果,让恶魔从你的鼻子里飞出来。这应该可以解释为什么它在mac上工作,而不是在Windows上,因为任何事情都可以发生)。考虑将
CthSmallest()
的声明更改为:型
并将代码更改为:
型
在调用者中,将返回值直接赋给
elementToDelete
。