c-如何删除数组中任何特定位置的任何元素

Question

我遇到了一个编程问题，我必须将数组的前两个索引相加，然后它们的和必须在第一个位置(删除添加的两个节点)，这肯定会导致数组的其余部分向前移动一个索引位置。但问题是，它的变化非常奇怪。请仔细看，我只需要使用数组，没有其他数据结构这是我想要的清晰图片。参见示例：

arr[5]= {1,2,3,4,5}
First execution:
{3,3,4,5} //here we added first two elements (1+2=3)
second execution:
(6,4,5) //again added first two elements
third execution:
{10,5}
finally:
{15}

我的代码是：

Node *temp;
Node *array[5]; //actually this array is declared like this {1,2,3,4,5}
int i;
for (i=0;i<5;i++)
{
array[i] = malloc(sizeof(Node));
array[i]->value = freq[i+1];//this contains {1,2,3,4,5}
array[i]->sym = arry[i];
array[i]->left = NULL;
array[i]->right = NULL;
printf("%d  ",array[i]->value );
}
int j=0,d,t=5;
while (t>1 )
{
temp = array[j];
printf(" ncheckOne %d  ",array[j]->value);
printf("checkTwo %d  n",array[j+1]->value );
array[j]->value= temp->value + array[j+1]->value; //
printf(" checkSumOfOneAndTwo %d  n",temp->value);
array[j]=array[j+1];
array[j]->left=array[j+1];
array[j]->right=temp;
array[j]=temp;
for(d=0;d < t;d++)
printf(" %d  ",array[d]->value);
t--; 
j++;
}

它的输出是：

The Frequencies corresponding to alphabets in Input.txt  files are as follows 
: a  b  c  d  e  
1  2  3  4  5   
checkOne 1  checkTwo 2  
checkSumOfOneAndTwo 3  
3   2   3   4   5   
checkOne 2  checkTwo 3  
checkSumOfOneAndTwo 5  
3   5   3   4   
checkOne 3  checkTwo 4  
checkSumOfOneAndTwo 7  
3   5   7   
checkOne 4  checkTwo 5  
checkSumOfOneAndTwo 9  
3   5  

我是编程初学者。有谁能告诉我这个错误是什么以及如何解决吗？(我不得不使用数组来实现它，所以没有链表、堆等)

Answer 1

这小段代码本身就是一个问题：

array[j]=array[j+1];
array[j]->left=array[j+1];

在执行上述代码后，您将得到一个节点，其"left"指针指向自身。

我会先解决这个问题。

更新：

为了有效地构建Huffman树，应该使用二进制堆(顶部最小值)而不是数组。在每次迭代中，应该提取两次根，将两个节点相加为一，然后将结果推回到堆中。

更新#2：

如果你坚持使用数组而不是二进制堆，那么你的代码中有一个基本的概念错误：

在整个执行过程中，您的数组必须从最小到最大排序。

您从一个已排序的数组开始，但没有确保它在每次迭代结束时保持排序。

简而言之，在对前两个元素求和之后，不能简单地将结果作为数组中的第一个节点。相反，您必须将该节点"传播"到数组中的正确位置，以使其按最小到最大排序。

如果不这样做，可能会导致代码工作，但霍夫曼编码/解码的实现不正确。

更新#3：

如果你坚持使用数组而不是二进制堆，下面的代码只是你应该如何构建霍夫曼树的一般框架。我还没有验证。

// Create a new node, whose children are the first two nodes in the array
temp = malloc(sizeof(Node));
temp->value = array[0]->value + array[1]->value;
temp->left  = array[0];
temp->right = array[1];
array_size--;
// Push the new node into the array, and move all elements 1 entry backwards
array[0] = temp;
for (int k=1; k<array_size; k++)
{
array[k] = array[k+1];
}
// Move the new node forward, until the array is properly sorted (min-to-max)
for (int k=1; k<array_size; k++)
{
if (array[k-1]->value < array[k]->value)
break;
temp = array[k-1];
array[k-1] = array[k];
array[k] = temp;
}

Answer 2

#include <stdio.h>
#include <stdlib.h>
int main(){
int stack_size = 5;
int sp = stack_size;
int *stack = malloc(stack_size * sizeof(int));//int stack[5];
int i;
for(i=stack_size; i>0 ;--i){
stack[--sp] = i;//push
}
//print stack
printf("{ " );
for(i = sp;i<stack_size;++i)
printf("%d ", stack[i]);
printf("}n");
int t = stack_size;
for(t=stack_size;t > 1;--t){
int first, second;
first = stack[sp++];//pop
second = stack[sp++];//pop
stack[--sp] = first + second;//push
printf("{ " );//now stack print 
for(i = sp;i<stack_size;++i)
printf("%d ", stack[i]);
printf("}n");
}
free(stack);
return 0;
}
/* result
{ 1 2 3 4 5 }
{ 3 3 4 5 }
{ 6 4 5 }
{ 10 5 }
{ 15 }
*/