如何交替分割双向链表

Question

好。我对C语言编程课程作业。我需要实现一个函数原型是：

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的，免费的）。只有更新指针。不要更改节点的数据。

限制：不要使用malloc（），释放calloc（），realloc（）的，免费的（）。

我坚持，我不能产生任何算法。请帮忙！

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

这是比较容易在两个节点的团体合作，并将它们分配给新的列表。你基本上确保有列表中的两个或多个节点启动，否则返回的第一个列表是原始anfd第二列表是空的。

检查完说，建立头指针列表返回，以及巡回指针保持在每个列表中最后一个项目的跟踪：

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。

不过，这只是内置于功能额外的安全的一点点。你可以看到一个完整的程序，低于该说明如何做到这一点，首先标题，节点结构和可读形式的倾销名单（并确保它没有损坏）的辅助功能：

#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值摇身一变原来的名单。

最后的代码位，是测试工具，它只是让你在每个节点增加的整数的列表（大小是基于你给任何说法，或十，如果你给无）。

它构造列表，并输出它，然后调用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

Answer 2

我们还可以使用队列操作和布尔或INT变量 目的地列表之间切换

altsplit(L:List;var L1,L2:List)
   L1.head = NIL;
   L1.tail = NIL;
   L2.head = NIL;
   L2.tail = NIL;
   s = false
   while not isEmpty(L) do
        x = dequeue(L)
        if not s then
             enqueue(L1,x)
        else
             enqueue(L2,x);
        s := not s;

请注意，我们不需要分配新的节点内存 我们只需设置指针以相同的方式就像在队列