C - Разделить односвязный список с индексами «от» и «до» - PullRequest
Новая
       12

C - Разделить односвязный список с индексами «от» и «до»

0 голосов
/ 19 апреля 2020

Недавно я столкнулся с некоторыми проблемами, связанными с разделением связанного списка с указанными c позициями. Вот мое обязательное задание:

Запись функции spitlist:

  • Разделение исходного списка на 2 подсписка.

  • splitlist (n1, n2), где n1 - начальная позиция (отсчет от 0), а n2 - количество элементов в sublist1. Остальное - подсписок 2.

Я справился с одним упражнением с разделенным списком, которое требует, чтобы sublist1 начинался только с позиции 0 Вот мой код для этого упражнения: 

void FrontBackSplit(struct Node* source, struct Node** frontRef, 
                struct Node** backRef)
{
int n; //length of node;

struct Node* current = source;

int pos; scanf("%d", &pos);
//position to split 
for (int i = 0; i < pos; i++)
    current = current->next;


*frontRef = source;
*backRef = current->next;
current->next = NULL;
}

Но я понятия не имею, как решить вышеупомянутую задачу. Как поместить все оставшиеся узлы в sublist2? Пожалуйста, помогите :(

Ответы [ 2 ]

0 голосов
/ 19 апреля 2020

Вот и вы. 

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

struct Node
{
    int value;
    struct Node *next;
};

int push_front( struct Node **head, int value )
{
    struct Node *new_node = malloc( sizeof( struct Node ) );
    int success = new_node != NULL;

    if ( success )
    {
        new_node->value = value;
        new_node->next = *head;

        *head = new_node;
    }

    return success;
}

void display( const struct Node *head )
{
    for ( ; head != NULL; head = head->next )
    {
        printf( "%d -> ", head->value );
    }

    puts( "null" );
}

struct ListPair
{
    struct Node *head1;
    struct Node *head2;
};


struct ListPair split( struct Node **head, size_t pos, size_t n )
{
    struct ListPair p = { .head1 = NULL, .head2 = NULL };

    struct Node **current1 = &p.head1;
    struct Node **current2 = &p.head2;

    for ( size_t i = 0; *head != NULL && i != pos; i++ )
    {
        *current2 = *head;
        *head = ( *head )->next;
        ( *current2 )->next = NULL;
        current2 = &( *current2 )->next;
    }

    while ( *head != NULL && n-- )
    {
        *current1 = *head;
        *head = ( *head )->next;
        ( *current1 )->next = NULL;
        current1 = &( *current1 )->next;
    }

    while ( *head != NULL )
    {
        *current2 = *head;
        *head = ( *head )->next;
        ( *current2 )->next = NULL;
        current2 = &( *current2 )->next;
    }

    return p;
}


int main(void) 
{
    const size_t N = 15;
    struct Node *head = NULL;

    srand( ( unsigned int )time( NULL ) );  

    for ( size_t i = 0; i < N; i++ )
    {
        push_front( &head, rand() % N );
    }

    display( head );
    putchar( '\n' );

    struct ListPair p = split( &head, N / 3, N / 3  );

    display( head );
    display( p.head1 );
    display( p.head2 );

    return 0;
}

Вывод программы может выглядеть как 

7 -> 13 -> 6 -> 8 -> 11 -> 1 -> 3 -> 3 -> 10 -> 8 -> 3 -> 1 -> 2 -> 14 -> 9 -> null

null
1 -> 3 -> 3 -> 10 -> 8 -> null
7 -> 13 -> 6 -> 8 -> 11 -> 3 -> 1 -> 2 -> 14 -> 9 -> null

То есть сначала существует один список, на который указывает указатель head.

Затем этот список разбивается на два списка p.head1 и p.head2. Список p.head1 получает 5 элементов исходного списка, начиная с позиции, равной 5.

Все остальные элементы перемещаются в список p.head2.

Как результат оригинальный список пуст. Теперь все его элементы разделены между двумя списками p.head1 и p.head2.

0 голосов
/ 19 апреля 2020

Попробуйте что-то вроде: 

struct Node* splitlist(struct Node* l, unsigned int n)
{
    for (int i = 0; i < n; ++i)
    {
        if (l == NULL) return NULL;
        l = l->next;
    }
    if (l == NULL) return NULL;

    // Save head of new list
    struct Node* retval = l->next;

    // Break the list apart
    l->next = NULL;

    // return the new list
    return retval;
}

и назовите это как 

struct Node* newList = splitlist(originalList, 42);
...