C语言 将节点移动到链表中的新索引

Question

我正在尝试更改链表中的索引.... 像这样： 我有链表：1->2->3->4->END，用户插入第二个节点(2(和索引4。

该函数将给我们结果：1->3->4->2->END。

我知道算法是：

1. 查找节点
2. 剪掉它
3. 查找要插入的位置
4. 插入它

但我不能让它工作... 到目前为止，我的函数代码是：

void changeIndex(FrameNode** head, char* name, int index)
{
FrameNode* temp = NULL;
FrameNode* curr = *head;
FrameNode* node = *head;
int counter = 1;
int flag = 0;

while (node && flag == 0)
{
if (strcmp(node->frame->name, name) == 0)
{
flag = 1;

}
else
{
node = node->next;
}
}

while (counter != index)
{
counter++;
temp = curr;
curr = curr->next;
}

temp->next = node;
curr->next = node->next;
node->next = curr;
}

我找不到有什么问题... 我搜索并找到了这个- 在 c 中更改链表中的索引 但它只给出了算法，我无法编码。 请帮忙...

Answer 1

对于初学者，我建议使用 0 索引而不是 1 索引，因此我在整个示例中进行了逻辑修改。

我建议将问题分解为几个步骤：

1. 编写一个函数来删除并返回给定name字符串的节点。
2. 编写一个函数以在索引处添加节点。

这样，每个函数都更容易编写和验证。

删除节点的逻辑涉及遍历列表以使用strcmp查找节点(就像您正在执行的操作一样(并跟踪上一个节点。循环终止后，如果存在上一个节点，则将其next设置为下一个下一个节点。如果不存在prev节点，那么我们有一个空列表，或者我们试图删除头部，这涉及不执行任何操作或分别*head设置为下一个节点。

在索引处添加节点的逻辑类似：将列表与prev节点遍历到索引或运行器节点为空(不清楚要对索引超出范围的错误采取什么操作(。当循环终止时，我们再次根据我们是否有prev来移动指针，如果没有，如果我们有*head。

下面是如何处理此问题的完整示例：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Node {
char *name;
struct Node *next;
};
void print_list(struct Node *head) {
for (; head; head = head->next) {
printf("%s->", head->name);
}
puts("");
}
struct Node *remove_node_by_name(struct Node **head, char *name) {
struct Node *prev = NULL;
struct Node *curr = *head;
for (; curr && strcmp(curr->name, name); prev = curr, curr = curr->next);
if (curr && prev) {
prev->next = curr->next;
}
else if (curr) {
*head = (*head)->next;
}
return curr;
}
void add_node_at_index(struct Node **head, struct Node *to_add, int index) {
struct Node *prev = NULL;
struct Node *curr = *head;
for (; curr && index--; prev = curr, curr = curr->next);
if (prev) {
prev->next = to_add;
to_add->next = curr;
}
else if (*head) {
to_add->next = *head;
*head = to_add;
}
}
void change_index(struct Node **head, char *name, int index) {
struct Node *removed = remove_node_by_name(head, name);
if (removed && *head) {
add_node_at_index(head, removed, index);
}
else if (removed) {
*head = removed;
}
}
int main(int argc, char **argv) {
if (argc != 4) {
puts("usage: ./llswap [nodelist] [node name] [new index]"
"nex: ./llswap abc b 2");
return 0;
}
struct Node *head = NULL;
struct Node *curr = NULL;
for (int i = 0; i < strlen(argv[1]); i++) {
struct Node *node = malloc(sizeof(*node));
if (!node) {
fprintf(stdout, "%s:%d malloc failedn", __FILE__, __LINE__);
exit(1);
}
node->next = NULL;
node->name = malloc(2);
if (!node->name) {
fprintf(stdout, "%s:%d malloc failedn", __FILE__, __LINE__);
exit(1);
}
node->name[1] = '';
strncpy(node->name, &argv[1][i], 1);
if (!head) {
head = node;
}
else {
curr->next = node;
}
curr = node;
}

printf("before: ");
print_list(head);
change_index(&head, argv[2], atoi(argv[3]));
printf("after:  ");
print_list(head);

while (head) {
struct Node *tmp = head;
head = head->next;
free(tmp->name);
free(tmp);
}
return 0;
}

一些示例运行：

$ ./llswap abc b 2
before: a->b->c->
after:  a->c->b->
$ ./llswap abc a 2
before: a->b->c->
after:  b->c->a->
$ ./llswap abc a 3
before: a->b->c->
after:  b->c->a->
$ ./llswap abcd d 0
before: a->b->c->d->
after:  d->a->b->c->
$ ./llswap a d 0
before: a->
after:  a->
$ ./llswap a a 0
before: a->
after:  a->
$ ./llswap a a 2
before: a->
after:  a->
$ ./llswap ab a 2
before: a->b->
after:  b->a->
$ ./llswap ab a 1
before: a->b->
after:  b->a->
$ ./llswap ab b 1
before: a->b->
after:  a->b->

Answer 2

我没有运行这个，但我认为这是你需要做的......(另外，我建议使用对您正在执行的操作更有意义的变量名称。

您需要在要移动的节点之前维护一个指向节点的临时指针，以便可以将其连接到要移动的节点之后的节点。

完成该拼接后，使用beforeIndex将节点插入正确的索引处，并将最初位于索引处的节点重新连接为刚刚移动的节点之后的下一个节点

void changeIndex(FrameNode** head, char* name, int index)
{
FrameNode* beforeMoved = NULL;
FrameNode* beforeIndex = NULL;
FrameNode* atIndex = *head;
FrameNode* toMove = *head;
int counter = 0;
int flag = 0;

while (toMove && flag == 0)
{
if (strcmp(toMove->frame->name, name) == 0)
{
flag = 1;

}
else
{
beforeMoved = toMove;
toMove = toMove->next;
}
}

while (atIndex && (counter != index))
{
counter++;
beforeIndex = atIndex;
atIndex = atIndex->next;
}
if(toMove && (atIndex || index+1 == counter) && (toMove != atIndex))
{
if(beforeMoved == NULL)
*head = (*head)->next;
else
beforeMoved->next = toMove->next;   // splice moving node out of linked list

if(beforeIndex == NULL)
*head = toMove;
else
beforeIndex->next = toMove;         // add moving node to correct location
toMove->next = atIndex;             // reconnect node previously at index
}
}