C -移动链表中的一个节点

Question

我正在处理一个链表，我想把列表中的一个节点从一个位置移动到另一个位置，而不把东西弄乱。

链表的结构体是:

 struct Frame
{
    char* name; // Name and path are just pointers to strings
    unsigned int duration;
    char* path;
};
typedef struct Frame frame_t;

:

struct Link
{
    frame_t *frame;
    struct Link *next;
};

(这是我被要求做的，不是我的选择)

现在我需要的是一个函数，它接收链表和字符串(其中一个节点的名称)和一个整数，然后将具有该名称的节点移动到该位置(接收到的整数)第一个位置是1，而不是0(这是请求的)

例如:如果列表包含如下节点:[pic1, pic2, pic3, pi4]并且用户请求将"pic1"移动到pos 3，那么新的列表将是:[pic2, pic3, pic1, pic4](其中pic2为新的头部)

我试过一些版本，但他们总是只有80%的工作(要么切断列表或不移动到正确的位置)。什么好主意吗?

下面是我尝试过的函数:

 void changePos(link_t** anchor_link, char* name1, int pos)
{
    link_t* currLink = *anchor_link;
    link_t* temp = NULL;
    link_t* temp2 = NULL;
    int i;
    if (strcmp(name1, currLink->frame->name) == 0 && currLink->next)
    {
        *anchor_link = (*anchor_link)->next;
        temp = currLink;
    }
    else
    {
        while (strcmp(name1, currLink->next->frame->name) != 0 && currLink->next)
        {
            currLink = currLink->next;
        }
        temp = currLink->next;
    }
    currLink = *anchor_link;
    for (i = 1; i < pos - 1; i++) // Go up until the node before the pos (meaning if pos is 4 then node 3)
    {
            currLink = currLink->next;
    }
    // Now we insert the temp node at the pos
    temp2 = currLink->next->next;
    currLink->next->next = temp;
    temp->next = temp2;
}

Answer 1

这是我想到的代码- changePos()函数和我创建的测试代码，以适度确信它是正确的。

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Frame
{
    char *name;
    unsigned int duration;    // Effectively unused
//  char *path;               // Actually unused
};
typedef struct Frame Frame;
struct Link
{
    Frame *frame;
    struct Link *next;
};
typedef struct Link Link;
static void print_list(Link *root);
static void changePos(Link **anchor_link, const char *name, int pos)
{
    assert(anchor_link != 0 && name != 0 && pos >= 0);
    Link *root = *anchor_link;
    Link *link = root;
    Link *prev = 0;
    int count = 0;
    while (link != 0 && strcmp(link->frame->name, name) != 0)
    {
        prev = link;
        link = link->next;
        count++;
    }
    if (link == 0)      // Name not found - no swap!
        return;
    if (count == pos)   // Already in target position - no swap
        return;
    if (count == 0)     // Moving first item; update root
    {
        assert(link == root);
        *anchor_link = root->next;
        root = *anchor_link;
    }
    else
    {
        assert(prev != 0);
        prev->next = link->next;
    }
    // link is detached; now where does it go?
    if (pos == 0)       // Move to start; update root
    {
        link->next = root;
        *anchor_link = link;
        return;
    }
    Link *node = root;
    for (int i = 0; i < pos - 1 && node->next != 0; i++)
        node = node->next;
    link->next = node->next;
    node->next = link;
}
static void print_list(Link *root)
{
    const char *pad = "";
    while (root != 0)
    {
        printf("%s[%s]", pad, root->frame->name);
        root = root->next;
        pad = "->";
    }
}
static void free_frame(Frame *frame)
{
    if (frame != 0)
    {
        free(frame->name);
        free(frame);
    }
}
static void free_link(Link *link)
{
    while (link != 0)
    {
        Link *next = link->next;
        free_frame(link->frame);
        free(link);
        link = next;
    }
}
static Frame *make_frame(const char *name, unsigned int number)
{
    Frame *frame = malloc(sizeof(*frame));
    if (frame != 0)
    {
        frame->name = strdup(name);
        frame->duration = number;
    }
    return frame;
}
static Link *make_link(const char *name, unsigned int number)
{
    Link *link = malloc(sizeof(*link));
    if (link != 0)
    {
        link->frame = make_frame(name, number);
        link->next = 0;
    }
    return link;
}
static Link *make_list(int num, Frame *frames)
{
    Link *head = 0;
    Link *tail = 0;
    for (int k = 0; k < num; k++)
    {
        Link *link = make_link(frames[k].name, frames[k].duration);
        assert(link != 0 && link->frame != 0);  // Lazy!
        if (head == 0)
            head = link;
        if (tail != 0)
            tail->next = link;
        tail = link;
    }
    return head;
}
int main(void)
{
    Frame frames[] =
    {
        { "pic0", 0 },
        { "pic1", 1 },
        { "pic2", 2 },
        { "pic3", 3 },
        { "pic4", 4 },      // Never in the list, but searched for
    };
    enum { NUM_FRAMES = sizeof(frames) / sizeof(frames[0]) };
    for (int i = 0; i < NUM_FRAMES; i++)
    {
        for (int j = 0; j < NUM_FRAMES; j++)
        {
            Link *head = make_list(NUM_FRAMES - 1, frames);
            print_list(head);
            printf(" == %s to %u == ", frames[i].name, j);
            changePos(&head, frames[i].name, j);
            print_list(head);
            putchar('n');
            free_link(head);
        }
    }
    return 0;
}

我怀疑changePos()中的代码仍然可以简化一点，但我还没有发现如何。这是一个带有数字位置和列表的丑陋界面—使用另一个名称来标识节点应该移动到哪里会更自然。对于数字位置，您可能会尝试使用数组而不是列表。

样本输出:

[pic0]->[pic1]->[pic2]->[pic3] == pic0 to 0 == [pic0]->[pic1]->[pic2]->[pic3]
[pic0]->[pic1]->[pic2]->[pic3] == pic0 to 1 == [pic1]->[pic0]->[pic2]->[pic3]
[pic0]->[pic1]->[pic2]->[pic3] == pic0 to 2 == [pic1]->[pic2]->[pic0]->[pic3]
[pic0]->[pic1]->[pic2]->[pic3] == pic0 to 3 == [pic1]->[pic2]->[pic3]->[pic0]
[pic0]->[pic1]->[pic2]->[pic3] == pic0 to 4 == [pic1]->[pic2]->[pic3]->[pic0]
[pic0]->[pic1]->[pic2]->[pic3] == pic1 to 0 == [pic1]->[pic0]->[pic2]->[pic3]
[pic0]->[pic1]->[pic2]->[pic3] == pic1 to 1 == [pic0]->[pic1]->[pic2]->[pic3]
[pic0]->[pic1]->[pic2]->[pic3] == pic1 to 2 == [pic0]->[pic2]->[pic1]->[pic3]
[pic0]->[pic1]->[pic2]->[pic3] == pic1 to 3 == [pic0]->[pic2]->[pic3]->[pic1]
[pic0]->[pic1]->[pic2]->[pic3] == pic1 to 4 == [pic0]->[pic2]->[pic3]->[pic1]
[pic0]->[pic1]->[pic2]->[pic3] == pic2 to 0 == [pic2]->[pic0]->[pic1]->[pic3]
[pic0]->[pic1]->[pic2]->[pic3] == pic2 to 1 == [pic0]->[pic2]->[pic1]->[pic3]
[pic0]->[pic1]->[pic2]->[pic3] == pic2 to 2 == [pic0]->[pic1]->[pic2]->[pic3]
[pic0]->[pic1]->[pic2]->[pic3] == pic2 to 3 == [pic0]->[pic1]->[pic3]->[pic2]
[pic0]->[pic1]->[pic2]->[pic3] == pic2 to 4 == [pic0]->[pic1]->[pic3]->[pic2]
[pic0]->[pic1]->[pic2]->[pic3] == pic3 to 0 == [pic3]->[pic0]->[pic1]->[pic2]
[pic0]->[pic1]->[pic2]->[pic3] == pic3 to 1 == [pic0]->[pic3]->[pic1]->[pic2]
[pic0]->[pic1]->[pic2]->[pic3] == pic3 to 2 == [pic0]->[pic1]->[pic3]->[pic2]
[pic0]->[pic1]->[pic2]->[pic3] == pic3 to 3 == [pic0]->[pic1]->[pic2]->[pic3]
[pic0]->[pic1]->[pic2]->[pic3] == pic3 to 4 == [pic0]->[pic1]->[pic2]->[pic3]
[pic0]->[pic1]->[pic2]->[pic3] == pic4 to 0 == [pic0]->[pic1]->[pic2]->[pic3]
[pic0]->[pic1]->[pic2]->[pic3] == pic4 to 1 == [pic0]->[pic1]->[pic2]->[pic3]
[pic0]->[pic1]->[pic2]->[pic3] == pic4 to 2 == [pic0]->[pic1]->[pic2]->[pic3]
[pic0]->[pic1]->[pic2]->[pic3] == pic4 to 3 == [pic0]->[pic1]->[pic2]->[pic3]
[pic0]->[pic1]->[pic2]->[pic3] == pic4 to 4 == [pic0]->[pic1]->[pic2]->[pic3]

输出的LHS是之前的列表-始终相同，顺序为pic0到pic3。输出的RHS为调用changePos后的列表。对于位置n = 0..3，你可以看到，'picn'依次从位置0迁移到位置3。名称pic4从未插入到列表中，因此在查找它时没有任何变化。此外，当您尝试将任何名称移动到不存在的位置时，它将移动到列表中的最后一个位置。

代码有临时错误检查。它断言自己的方式来解决内存分配问题，以及其他一些问题(如位置小于0)。

在changePos()中写入任何有价值的东西之前，我用changePos()的一个虚拟的无操作版本干净地运行了这个harness。

该代码在Mac OS X 10.11.5与GCC 6.1.0和Valgrind 3.12.0上编译和运行干净。SVN，使用我习惯的编译器警告选项:

$ gcc -O3 -g -std=c11 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes 
>     -Wold-style-definition -Werror so.3807-9550.c -o so.3807-9550
$

Answer 2

我认为您的一般方法是好的:找到目标节点，将其从列表中删除，然后将其重新插入指定位置。但是，您的代码有几个问题。

首先，考虑while()循环的条件:

    while (strcmp(name1, currLink->next->frame->name) != 0 && currLink->next)

如果您不确定currLink->next是否为NULL(您应该是)，那么您必须在解引用它之前执行空检查，这是您在表达式currLink->next->frame->name中所做的。实际上，如果您的代码到达列表末尾而没有找到指定的名称，则会显示未定义的行为。

第二，您的变量命名留下了一些需要改进的地方。temp是什么?temp2是什么?如果看不到name2, name1中的1表示什么?以一种清晰地传达其目的的方式命名变量有助于编写和分析代码。例如，"target_node"有什么问题?

第三，你的插入代码是错误的:

temp2 = currLink->next->next;
currLink->next->next = temp;
temp->next = temp2;

您打算在*currLink和*currLink->next之间插入*temp，但实际上您将其放在 *currLink->next之后，然后关闭双元素循环。另外，我怀疑使用temp2只是混淆了这段代码。我会这样写:

temp->next = currLink->next->next;
currLink->next = temp;

第四，你没有准备在列表的位置1插入。你这样做需要一个特殊的情况