Как разделить связанный список в два список

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()
• ...

С соответствующим набором аргументов и возвращаемых значений конечно. Затем вы можете написать функцию разделения списка, используя эти основные функции работы с списком, и ваш код будет легче читать и рассуждать.

Кроме того, для обработки пустого списка вы должны иметь дополнительный тип списка, который является не только указателем на узел.

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; 
    } 
} 

может показаться, что это много работы, чтобы создать все те другие функции списка, если все, что вам нужно, - это список разделов. Но в реальных приложениях вам, скорее всего, понадобятся все эти другие функции (или у вас их уже есть). Только в домашних ситуациях это выглядит немного смешно.

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; 
}