c - 如何交替分割双向链表

Question

好的。我有一个 C 编程类(class)的作业。 我需要实现一个函数原型(prototype):

void split(node* head, node **first, node **second)   

该函数将head指向的双向链表拆分为两个列表first和second。

假设head包含元素F0,S0,F1,S1,F2,S2,...

然后:

• first 应按以下顺序包含元素:F0,F1,F2,...
• second 应按以下顺序包含元素:S0,S1,S2,...

不要进行任何分配或释放(malloc、calloc、realloc、free)。仅更新指针。不要更改节点数据。

限制:不要使用 malloc()、calloc()、realloc()、free()。

我被卡住了，我无法生成任何算法。请帮忙!

typedef struct node
{
    int data;
    struct node *prev;
    struct node *next;
} node;

编辑解决方案:

    #define DATA(p) ((p)->data)
    #define NEXT(p) ((p)->next)
    #define PREV(p) ((p)->prev)



    void split ( node* head, node **first, node **second )
    {
        node* firstCurrent = head;
        node* secondCurrent = NULL;
        node* dummyforbprev = NULL;

        if ( firstCurrent )
        {
            secondCurrent = NEXT(firstCurrent);
            if(secondCurrent)
                PREV(secondCurrent)=NULL;
        }

        *first = firstCurrent;
        *second = secondCurrent;

        while ( firstCurrent && secondCurrent )
        {
            NEXT(firstCurrent) = NEXT(secondCurrent);
            dummyforbprev = PREV(firstCurrent);
            firstCurrent = NEXT(firstCurrent);
            if(firstCurrent)
                PREV(firstCurrent) = PREV(secondCurrent);

            if ( firstCurrent )
                NEXT(secondCurrent) = NEXT(firstCurrent);
            PREV(secondCurrent) = dummyforbprev;
            secondCurrent = NEXT(secondCurrent);
        }

        if ( firstCurrent )
            NEXT(firstCurrent) = NULL;

        if ( secondCurrent )
            NEXT(secondCurrent) = NULL;
    }

Answer 1

无需为新列表分配任何新节点，只需调整指针即可形成新列表，请记住，这必然会修改您传入的列表。

从如下列表开始:

head -> 1 -> 2 -> 3 -> 4 -> 6 -> null

以两个节点为一组进行工作并将它们分配到新列表相对容易。基本上，您首先要确保列表中有两个或多个节点，否则返回的第一个列表是原始列表，第二个列表为空。

检查完毕后，为要返回的列表设置头指针，并设置移动指针来跟踪每个列表中的最后一项:

second ------|
first --|    |
head -> 1 -> 2 -> 3 -> 4 -> 6 -> null
fEnd ---|    |
sEnd --------|

然后，简单地说，您执行以下步骤:

• 将 fEnd 下一个值设置为 sEnd 下一个值(因此 1 现在指向 3)然后将 fEnd 指针前进到 3。
• 将 sEnd 下一个值设置为 fEnd 下一个值(因此 2 现在指向 4)然后将 sEnd 指针前进到 4。

现在你遇到这样的情况:

sEnd --------------------|
fEnd ---------------|    |
           ________ |    |
          /        \     |
first/ -> 1    2    3 -> 4 -> 6 -> null
 head          |\        /
               | \______/
second --------|

您可以看到列表的前部已被分割，并且指针已前进到列表的其余部分。

您只需继续执行此操作，直到到达列表末尾。

现在你会注意到上面提到的“简单化”这个词。虽然此处解释的概念很简单，但存在一些复杂的因素。

第一个事实是，您可能无法能够处理两个节点的组，仅仅是因为列表中可能有奇数个节点。其次，处理链表末端时会遇到一些常见问题，您必须小心处理以下问题:

node->next->prev = node;

其中 node 可能位于末尾，当您取消引用 node->next 时，可能会导致崩溃。

不过，这只是函数中内置的一点额外安全性。您可以在下面看到一个完整的程序，它说明了如何执行此操作，首先是 header 、节点结构和用于以可读形式转储列表的辅助函数(并确保其未损坏):

#include <stdio.h>
#include <stdlib.h>

typedef struct sNode {
    int value;
    struct sNode *next;
    struct sNode *prev;
} tNode;

static void dump (char *desc, tNode *head) {
    printf ("Dumping %s: ", desc);
    tNode *p = head;
    while (p != NULL) {
        if ((p != head) && (p->prev->next != p)) {
            printf ("double-link error\n");
            exit (1);
        }
        printf ("%d -> ", p->value);
        p = p->next;
    }
    puts ("NULL");
}

其次，解决方案的“核心”是一个根据您的要求的 split() 函数，它接受一个列表并返回两个列表，每个列表都具有与原始值不同的交替值:

void split (tNode* head, tNode **pFirst, tNode **pSecond) {
    // Must have two elements or more to split.

    if ((head == NULL) || (head->next == NULL)) {
        *pFirst = head;
        *pSecond = NULL;
        return;
    }

    // Set up list heads and roving pointers.

    tNode *first = head, *second = head->next;
    tNode *fEnd = first, *sEnd = second;

    // Do whole list in groups of two, but check to ensure
    //   no crashes due to invalid pointer dereferences.

    while (fEnd != NULL) {
        // First in group of two.

        if (sEnd != NULL) {
            fEnd->next = sEnd->next;
            if (fEnd->next != NULL)
                fEnd->next->prev = fEnd;
        }
        if (fEnd != NULL)
            fEnd = fEnd->next;

        // Second in group of two.

        if (fEnd != NULL) {
            sEnd->next = fEnd->next;
            if (sEnd->next != NULL)
                sEnd->next->prev = sEnd;
        }
        if (sEnd != NULL)
            sEnd = sEnd->next;
    }

    // Return lists to caller.

    *pFirst = first;
    *pSecond = second;
}

如前所述，该函数也会影响原始列表，因为它必须使用原始节点，并且更改这些节点中的 next/prev 值也会改变原始列表。

代码的最后一部分是测试工具，它只是为您提供每个节点中递增整数的列表(大小基于您提供的任何参数，如果您没有提供，则为 10)。

它构造列表并输出它，然后调用 split() 函数并向您显示结果:

int main (int argc, char *argv[]) {
    int quant = (argc > 1) ? atoi (argv[1]) : 10;
    tNode *head = NULL, *first, *second;

    for (int i = quant - 1; i >= 0; i--) {
        tNode *add = malloc (sizeof (*add));
        add->value = i + 1;
        add->next = head;
        add->prev = NULL;
        if (head != NULL) head->prev = add;
        head = add;
    }

    dump ("before", head);
    split (head, &first, &second);
    dump ("after (first) ", first);
    dump ("after (second)", second);

    return 0;
}

该程序的输出可以在以下记录中看到:

$ ./testprog 0
Dumping before: NULL
Dumping after (first) : NULL
Dumping after (second): NULL

$ ./testprog 1
Dumping before: 1 -> NULL
Dumping after (first) : 1 -> NULL
Dumping after (second): NULL

$ ./testprog 2
Dumping before: 1 -> 2 -> NULL
Dumping after (first) : 1 -> NULL
Dumping after (second): 2 -> NULL

$ ./testprog 3
Dumping before: 1 -> 2 -> 3 -> NULL
Dumping after (first) : 1 -> 3 -> NULL
Dumping after (second): 2 -> NULL

$ ./testprog
Dumping before: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> NULL
Dumping after (first) : 1 -> 3 -> 5 -> 7 -> 9 -> NULL
Dumping after (second): 2 -> 4 -> 6 -> 8 -> 10 -> NULL

$ ./testprog 9
Dumping before: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> NULL
Dumping after (first) : 1 -> 3 -> 5 -> 7 -> 9 -> NULL
Dumping after (second): 2 -> 4 -> 6 -> 8 -> NULL