好吧,我一直在研究我的第一个单链表项目,但遇到了困难。我试图实现的算法之一是在用户指定的节点之前插入一个节点。我遇到的问题是,当插入节点时,它被放置在正确的位置,但它也会删除它之前的所有节点。 如果我的列表最初包含: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;
}
最佳答案
仔细考虑一下你在做什么。
如果您要插入一个节点,则不应创建三个!
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
节点。
关于c - insertBefore 链表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46499670/