c - 如何在保留旧内容的同时将动态数组的大小加倍

Question

对于我的 C 数据结构作业的一部分，我的任务是获取指向 2 个双向链表节点的指针数组(一个表示主服务队列，另一个表示准备好重复使用的蜂鸣器“桶”或在队列中第一次使用)，将大小加倍，同时保持原始内容不变。这个想法是每个节点都有一个关联的 ID，它对应于指针数组映射的数字索引。因此，例如，索引 3 中的指针将始终指向 ID 为 3 的节点。 bool 值 inQ 用于与此问题无关的内容。

我已经写了大部分代码，但它似乎运行不正确(它在调整数组大小之前将所有原始指针更改为列表中的最后一个节点)所以，由于数组的起始大小是 10 个元素, 当我打印出函数后的内容时，它显示 9 9 9 9 9 9 9 9 9 9.

这是我使用的结构:

typedef struct node {
int id;
int inQ;
struct node *next;
struct node *prev;
}NODE;

typedef struct list
{
NODE *front;
NODE *back;
int size;
} LIST;

//referred to as SQ in the separate header file
struct service_queue
{
LIST *queue;
LIST *bucket;
NODE **arr;
int arrSize;
int maxID;
};

这里是有问题的函数:

SQ  sq_double_array(SQ *q)
{
NODE **arr2 = malloc(q->arrSize * 2 * sizeof(NODE*));
int i;

//fill the first half of the new array with the node pointers of the first array
for (i = 0; i < q->arrSize; i++)
{
    arr2[i] = malloc(sizeof(NODE));
    if (i > 0)
    {
        arr2[i - 1]->next = arr2[i];
        arr2[i]->prev = arr2[i - 1];
    }
    arr2[i]->id = q->arr[i]->id;
    arr2[i]->inQ = q->arr[i]->inQ;
    arr2[i]->next = q->arr[i]->next;
    arr2[i]->prev = q->arr[i]->prev;
}

//fill the second half with node pointers to the new nodes and place them into the bucket
for (i = q->arrSize; i < q->arrSize * 2; i++)
{
    //Point the array elements equal to empty nodes, corresponding to the inidicies
    arr2[i] = malloc(sizeof(NODE));
    arr2[i]->id = i;
    arr2[i]->inQ = 0;

    //If the bucket is empty (first pass)
    if (q->bucket->front == NULL)
    {
        q->bucket->front = arr2[i];
        arr2[i]->prev = NULL;
        arr2[i]->next = NULL;
        q->bucket->back = arr2[i];
    }

    //If the bucket has at least 1 buzzer in it
    else
    {
        q->bucket->back = malloc(sizeof(NODE));
        q->bucket->back->next = arr2[i];
        q->bucket->back = arr2[i];
        q->bucket->back->next = NULL;
    }
}
q->arrSize *= 2;
q->arr = arr2;
return *q;
}

请记住，这只能在 c 中完成，这就是我不使用“new”的原因

Answer 1

您可以使用 realloc 函数:

void *realloc(void *ptr, size_t size);

引自手册页:

The realloc() function changes the size of the memory block pointed to by ptr to size bytes. The contents will be unchanged in the range from the start of the region up to the minimum of the old and new sizes. If the new size is larger than the old size, the added memory will not be initial‐ ized. If ptr is NULL, then the call is equivalent to malloc(size), for all values of size; if size is equal to zero, and ptr is not NULL, then the call is equivalent to free(ptr). Unless ptr is NULL, it must have been returned by an earlier call to malloc(), calloc() or realloc(). If the area pointed to was moved, a free(ptr) is done.