如何将链表拆分为两个列表

Question

我正在编写一个代码将循环链表拆分为两个具有相同代码数的链表，以下是我的代码：

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

typedef struct node *ptr;
struct node {
    int element;
    ptr prev;
    ptr next;
};
typedef ptr list;
typedef ptr position;

int main() {
    list L=malloc(sizeof(struct node));
    list first=malloc(sizeof(struct node));
    list second=malloc(sizeof(struct node));
    splitlist(L,first,second);
    return 0;
}

void splitlist(list L, list first,list second) {
    position p,temp;
    p=malloc(sizeof(struct node));
    temp=malloc(sizeof(struct node));
    p=L;
    int count=0;

    while ((p)->next != L) {
        count++;
    }

    int c=count;
    while (c!=(count/2)-1) {
        p=(p)->next;
       temp=(p)->next;
    }

    first=L;
    (p)->next=NULL;
    second=temp;

    c=count;
    while (c!=(count/2)-1) {
       temp=(temp)->next;
    }
    (temp)->next=NULL;
}

编译我的代码时没有出现错误，但我不确定它是否正常工作。

Answer 1

为了获得更具可读性和可维护性的代码，改进代码的第一步可能是创建有助于操作列表的函数。候选函数是：

ListInitialize()
ListPushFront()
ListPushBack()
ListPopFront()
ListPopBack()
ListGetFirstNode()
ListGetNextNode()
ListGetFront()
ListGetBack()
ListEmpty()
...

当然有一组适当的参数和 return 值。然后你可以使用那些基本的列表操作函数来编写你的拆分列表函数，你的代码将更容易阅读和推理。

此外，为了处理空列表，您应该有一个额外的列表类型，它不仅仅是指向节点的指针。

typedef struct Node_tag { int value; struct Node_tag *next; struct Node_tag *prev } Node, *NodePtr;
typedef struct IntList_tag { NodePtr front; NodePtr back; } IntList;

// Creates an empty list.
void ListInitialize( IntList *pList ) { pList->front = NULL; pList->back = NULL; }
void ListPushFront( IntList *pList, int value ) 
{ NodePtr newNode = malloc(sizeof(Node)); 
  if(NULL != newNode ) 
  { newNode->next = pList->front; 
    newNode->prev = NULL; newNode->value = value; 
    pList->front = newNode; 
    if( pList->back == NULL ) pList->back = newNode; // first element...
  }
}
// ...

最终，使用这些函数，您可以以简洁无干扰的方式编写 splitlist() 函数：

void splitlist( IntList * source, IntList *target1, IntList *target2 )
{
     IntList * currentTarget = target1;
     for( NodePtr currentNode = ListGetFirstNode(source); currentNode != NULL; currentNode = ListGetNextNode(currentNode) )
     {
          ListPushBack(currentTarget, currentNode->value );
          if(currentTarget == target1 ) currentTarget = target2; 
          else currentTarget = target1;
     }
}

如果您只需要 splitlist，那么创建所有这些其他列表函数似乎需要做很多工作。但在现实世界的应用程序中，您很可能还需要所有这些其他功能（或者您已经拥有它们）。只有在作业的情况下，这看起来有点滑稽。

Answer 2

示例代码。为节点使用 typedef 以与 Microsoft C 编译器 (C89) 兼容。请注意，有时指向循环列表的指针是指向循环列表的最后一个节点的指针（其中包含指向循环列表的第一个节点的指针），允许更快的追加。此示例假定列表指针是指向第一个节点的指针，但可以修改为假定列表指针指向最后一个节点。

#include <stdlib.h>

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

node * splitlist(node * psrc, node ** ppdst1, node ** ppdst2)
{
node *ps = psrc;
node ** ppd1 = ppdst1;
node ** ppd2 = ppdst2;
    *ppd1 = *ppd2 = NULL;
    if(ps == NULL)
        return NULL;
    while(1){
        *ppd1 = ps;
        ps = *(ppd1 = &(ps->next));
        if(ps == psrc)
            break;
        *ppd2 = ps;
        ps = *(ppd2 = &(ps->next));
        if(ps == psrc)
            break;
    }
    *ppd1 = *ppdst1;
    *ppd2 = *ppdst2;
    return NULL;
}

main()
{
node a[8] = {{&a[1],0},{&a[2],1},{&a[3],2},{&a[4],3},
             {&a[5],4},{&a[6],5},{&a[7],6},{&a[0],7}};
node *pa = &a[0];
node *pb = NULL;
node *pc = NULL;
    pa = splitlist(pa, &pb, &pc);
    return 0;
}

如何将链表拆分为两个列表

How to split a linked-list into two lists

c

linked-list

data-structures