c - insertBefore 链表

Question

好吧，我一直在研究我的第一个单链表项目，但遇到了困难。我试图实现的算法之一是在用户指定的节点之前插入一个节点。我遇到的问题是，当插入节点时，它被放置在正确的位置，但它也会删除它之前的所有节点。如果我的列表最初包含:1 2 3 4 5我想在4之前插入0结果是:0 4 5

struct node *insertBefore(struct node *start, int data, int x)
{
    struct node *marker = NULL;
    struct node *prev = NULL;
    struct node *temp = NULL;

    temp = (struct node*)malloc(sizeof(struct node));

    marker = start;

    while(marker != NULL && marker->info != x)
    {
        prev = marker;
        marker = marker->link;
    }
    if(!marker)
    {
        printf("*Element containing %d not found*\n", x);
        return;
    }
    if(marker == start)
    {
        temp->info = data;
        temp->link = marker;
        return;
    }
    temp->info = data;
    temp->link = prev->link;
    prev->link = temp;
    temp->link = marker;

    return; 
}

Answer 1

仔细考虑一下你在做什么。

如果您要插入一个节点，则不应创建三个!

temp = (struct node*)malloc(sizeof(struct node));
marker = (struct node*)malloc(sizeof(struct node));
prev = (struct node*)malloc(sizeof(struct node));

解决这个问题的方法是:

// Search for relevant node
while(marker != NULL && marker->info != x) {
    prev = marker;
    marker = marker->link;
}

// Verify you found somewhere to insert
if(marker == NULL) {
    // No x found
    return start;
}

// Allocate and initialize node
struct node* insert_node = (struct node*)malloc(sizeof(struct node));
insert_node->info = data;
insert_node->link = marker;

if(prev == NULL) {
    // Inserted node is the new start node
    start = insert_node;
}
else {
    // Relink chain
    prev->link = insert_node;
}

// Return the NEW start node.
// This is needed in case the new node is inserted before the original start node!
return start;

如果你的代码巧妙(这意味着思考!)，你可以写得非常简单并避免极端情况。极端情况包括:

• 输入列表为空
• 第一个元素是x
• 列表中没有x

<小时/>

再次查看您的代码，您正在做一些不寻常的事情。一是在确定要插入元素之前分配内存:

temp = (struct node*)malloc(sizeof(struct node));

此外，您连续更改 temp->link 两次。

temp->link = prev->link;
prev->link = temp;
temp->link = marker;

如果列表中的第一个元素发生更改，您没有任何机制来更新 start 节点。