1

我将如何创建一个允许我在链表中​​的任何索引处插入新节点的函数？这是结构：

struct node {
    int data;
    struct node* next;
};

这是函数，注意只有一个双指针、索引和数据参数。

void insertN(struct node** headRef, int index, int data);

以下是调用 insertN 后的结果：

[ HEAD ] -> [ 0 ] -> [ 15 ] -> [ 10 ] -> [ 5 ] -> [ NULL ]
insertN( &head, 3, -44);
[ HEAD ] -> [ 0 ] -> [ 15 ] -> [ 10 ] -> [ -44 ] -> [ 5 ] -> [ NULL ]
insertN( &head, 4, -55);
[ HEAD ] -> [ 0 ] -> [ 15 ] -> [ 10 ] -> [ -44 ] -> [-55 ] -> [ 5 ] -> [ NULL ]
insertN( &head, 0, -66);
[ HEAD ] -> [ -66 ] -> [ 0 ] -> [ 15 ] -> [ 10 ] -> [ 5 ] -> [ NULL ]

我知道如何向头部添加一个新节点，但在任何时候都不知道。我的想法是

void insertN(struct node** headRef, int index, int data) {
    struct node* new;
    int i;
    for (i = 0; i <= index; i++) {
        if (i == index) {
            /* move what was here to next node and put in new node */
        }
    }

    return;
}

我只是不确定如何去做这一切，因为如果节点中有东西，我也必须移动所有后续节点。

4

2 回答 2

1

如下图所示，您需要在两个节点之间插入节点。

其他3例是

  • 在列表开头插入
  • 在列表中间插入
  • 在列表末尾插入。

保持计数并循环遍历列表中的所有元素。此计数将帮助您跟踪索引。

到达节点后，您必须在其中插入新节点

  • 创建新节点
  • 将前一个节点的下一个指针指向新节点。
  • 将新节点的下一个指针指向当前节点。

完整的源代码在这里

在此处输入图像描述

于 2013-11-12T03:17:37.820 回答
0

当 index == 0 时，您必须处理一种特殊情况，headRef 将需要更新。或者如果 index 大于列表中的元素数。插入将失败。否则请查看下面的示例代码。

int insertN(struct node** headRef, int index, int data) {
    /* invalid headRef */
    if (!headRef) {
        return 0;
    }
    /* insert node at index */
    int i;
    struct node* new = (struct node *)malloc(sizeof(*node));
    struct node *scan = *headRef;
    new->data = data;
    new->next = 0;
    /* new head of list */
    if (scan == NULL && index == 0) {
         /* new head node */
         new->next = *headRef;
         *headRef = new;
         return 0;
    }
    /* while not at end of list and not at index */
    for (i = 0; scan != NULL && i <= index; i++) {
        if (i == index) {
            /* move what was here to next node and put in new node */
            new->next = scan->next;
            scan->next = new;
        } else {
            /* advance to next entry in list */
            scan = scan->next;
        }
    }
    /* scan == NULL indicates reached end of list before index */
    return (scan != NULL);
}
于 2013-11-12T03:12:01.563 回答