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”移动到位置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。输出的右侧是调用 changePos 后的列表。对于位置n = 0..3，可以看到，'picn'依次从位置0迁移到位置3。名称 pic4 永远不会插入到列表中，因此在查找它时不会发生任何变化。此外，当您尝试将任何名称移动到不存在的位置时，它会被移动到列表中的最后一个位置。小于 0 的位置被断言无效。

代码有偶然的错误检查。它断言解决了内存分配问题以及其他一些问题(例如位置小于 0)。

在 changePos() 中写入任何有值(value)的内容之前，我使用一个虚拟的无操作版本的 changePos() 让线束干净地运行。

使用我习惯的编译器警告选项，代码可以在带有 GCC 6.1.0 和 Valgrind 3.12.0.SVN 的 Mac OS X 10.11.5 上干净地编译和运行:

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