C - Как разделить связанный список с данными типа структуры - PullRequest
Новая
       7

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

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

У меня есть проблема, которая требует разделить односвязный список на 2 части с помощью функции: Split (n1, n2), где n1 = позиция элемента, n2 - количество элементов, которые нужно разделить. Мне удалось придумать алгоритм и программу тестирования: 

#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, 6, 3  );

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

return 0;
}

Результат: 

12 -> 14 -> 3 -> 0 -> 12 -> 5 -> 4 -> 0 -> 2 -> 14 -> 1 -> 0 -> 6 -> 0 -> 5 -> null

null
5 -> 4 -> 0 -> 2 -> 14 -> null
12 -> 14 -> 3 -> 0 -> 12 -> 1 -> 0 -> 6 -> 0 -> 5 -> null

Но не знаю, как реализовать вышеизложенное в моей связанной список: 

typedef struct address_t
{
char name[30];
char storage[5];
char screen[5];
int price;
} address;


typedef address elementtype;
typedef struct node node;
typedef struct node{
elementtype element;
node *next;
};

node *root, *cur, *prev;

Пожалуйста, помогите :(

1 Ответ

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

Обзор

Насколько я понимаю вопрос, вы просто хотите удалить подсписок из единого связанного списка, например, list = el1 -> el2 -> el5 -> el6 -> el3 -> null. Когда вы звоните split(list, 2, 2), результатом будет два списка list and list1 с list = el1 -> el2 -> el3 -> null и list1 = el5 -> el6 -> null.

Но не совсем ясно, с какой реальной проблемой вы сталкиваетесь и с чем вы до сих пор пытался заставить его работать?

Ответ

Из того, как я прочитал вопрос, не очень важно, как выглядит содержимое каждого элемента списка. Так почему бы вам просто не взять свой struct Node из примера и заменить поле int value на address value следующим образом: 

typedef struct {
  char name[30];
  char storage[5];
  char screen[5];
  int price;
} address;

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

Есть несколько проблем в вашем коде, которые вы можете захотеть изменить. 1. Ваша функция разбиения устанавливает переданный в указатель head значение NULL. Это может быть нежелательное поведение 2. Вы возвращаете структуру из split(...). Поскольку все в C передается по значению, вы можете рассмотреть возможность передачи (двойного) указателя на split(...) и поместить туда полученный ListPair, потому что тогда ListPair не нужно копировать при возврате из функции 3. Обычно вы бы не использовали _t для имени структуры, но не для самой typedef. 4. Вы вводите определение структуры address_t и вводите определение типа с помощью elementtype, но никогда не используете address 5. У вас есть определение типа, у которого нет имени 

typedef struct node{
 elementtype element;
 node *next;
};

Просто удалите typedef в этой строке, потому что вы уже сделали typedef на одну строку раньше.

...