• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Lista dwukierunkowa - rekurencja

VPS Starter Arubacloud
0 głosów
330 wizyt
pytanie zadane 4 maja 2018 w C i C++ przez kikosiak Obywatel (1,010 p.)

Cześć

Muszę napisać podane funkcję za pomocą rekurencji. Tyle, że nie do końca wiem jak to można zrobić. Mógłby ktoś mi podpowiedzieć jak to zrobić.

Kod oryginalnego programu:

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

struct dll_node
{
    int data ;
    struct dll_node *prev, * next ;
};

struct dll_node * create_list ( int data )
{
    struct dll_node * front = ( struct dll_node *)
                              malloc ( sizeof ( struct dll_node ) ) ;
    if ( NULL != front )
    {
        front -> data = data ;
        front -> prev = front -> next = NULL ;
    }
    return front ;
}

struct dll_node * insert_front ( struct dll_node *front,
                                 struct dll_node * new_node )
{
    new_node -> next = front ;
    front -> prev = new_node ;
    return new_node ;
}

struct dll_node * find_spot ( struct dll_node *front, int data )
{
    struct dll_node * prev = NULL ;
    while (( NULL != front ) && (front -> data > data ) )
    {
        prev = front ;
        front = front -> next ;
    }
    return prev ;
}

void insert_after ( struct dll_node *node, struct dll_node * new_node )
{
    new_node -> prev = node ;
    new_node -> next = node -> next ;
    node ->next -> prev = new_node ;
    node -> next = new_node ;
}

void insert_back ( struct dll_node *back, struct dll_node * new_node )
{
    back -> next = new_node ;
    new_node -> prev = back ;
}

struct dll_node * insert_node ( struct dll_node *front, int data )
{
    if ( NULL == front )
        return NULL ;

    struct dll_node * new_node = ( struct dll_node *)
                                 malloc ( sizeof ( struct dll_node ) ) ;
    if ( NULL != new_node )
    {
        new_node -> data = data ;
        new_node -> prev = new_node -> next = NULL ;
        if (front -> data <= data )
            return insert_front (front, new_node ) ;
        else
        {
            struct dll_node * node = find_spot (front, data ) ;
            if ( NULL != node -> next )
                insert_after (node, new_node ) ;
            else
                insert_back (node, new_node ) ;
        }
    }
    return front ;
}

struct dll_node * delete_front ( struct dll_node * front )
{
    struct dll_node * next = front -> next ;
    if ( NULL != next )
        next -> prev = NULL ;
    free ( front ) ;
    return next ;
}

struct dll_node * find_node ( struct dll_node *front, int data )

{
    while (( NULL != front ) && (front -> data != data ) )
        front = front -> next ;
    return front ;
}

void delete_within ( struct dll_node * node )
{
    node ->next -> prev = node -> prev ;
    node ->prev -> next = node -> next ;
    free ( node ) ;
}

void delete_back ( struct dll_node * back )
{
    back ->prev -> next = NULL ;
    free ( back ) ;
}

struct dll_node * delete_node ( struct dll_node *front, int data )
{
    if ( NULL == front )
        return NULL ;

    if (front -> data == data )
        return delete_front ( front ) ;

    struct dll_node * node = find_node (front, data ) ;
    if ( NULL != node )
    {
        if ( NULL != node -> next )
            delete_within ( node ) ;
        else
            delete_back ( node ) ;
    }
    return front ;
}

void print_list ( struct dll_node * front )
{
    for (; NULL != front ; front = front -> next )
        printf ("%d ", front -> data ) ;
    printf ("\n") ;
}

void print_list_backwards ( struct dll_node * front )
{
    if ( NULL != front )
    {
        for (; NULL != front -> next ; front = front -> next ) ;
        for (; NULL != front ; front = front -> prev )
            printf ("%d ", front -> data ) ;
    }
    printf ("\n") ;
}

void remove_list ( struct dll_node ** front )
{
    struct dll_node * next = NULL ;
    while ( NULL != * front )
    {
        next = (* front ) ->next ;
        free (* front ) ;
        * front = next ;
    }
}

int main ()
{
    struct dll_node * front = create_list (1) ;
    int i;

    for (i=2; i <5; i++)
        front = insert_node (front, i) ;
    for (i=6; i <10; i++)
        front = insert_node (front, i) ;
    printf (" List elements :\n") ;
    print_list ( front ) ;
    printf (" List elements printed backwards :\n") ;
    print_list_backwards ( front ) ;

    front = insert_node (front, 0) ;
    printf (" List elements after insertion of 0:\n") ;
    print_list ( front ) ;
    front = insert_node (front, 5) ;
    printf (" List elements after insertion of 5:\n") ;
    print_list ( front ) ;
    front = insert_node (front, 7) ;
    printf (" List elements after insertion of 7:\n") ;
    print_list ( front ) ;
    front = insert_node (front, 10) ;
    printf (" List elements after insertion of 10:\n") ;
    print_list ( front ) ;

    front = delete_node (front, 0) ;
    printf (" List elements after deletion of 0:\n") ;
    print_list ( front ) ;
    front = delete_node (front, 1) ;
    printf (" List elements after deletion of 1:\n") ;
    print_list ( front ) ;
    front = delete_node (front, 1) ;
    printf (" List elements after deletion of 1:\n") ;
    print_list ( front ) ;
    front = delete_node (front, 5) ;
    printf (" List elements after deletion of 5:\n") ;
    print_list ( front ) ;
    front = delete_node (front, 7) ;
    printf (" List elements after deletion of 7:\n") ;
    print_list ( front ) ;
    front = delete_node (front, 10) ;
    printf (" List elements after deletion of 10:\n") ;
    print_list ( front ) ;

    remove_list (& front ) ;
    return 0;
}

 

1 odpowiedź

0 głosów
odpowiedź 4 maja 2018 przez RafalS VIP (122,820 p.)

Chodzi o to, żeby pętle for w funkcjach listy zamienić na rekurencje. Rozpisałem wypisanie listy przy pomocy rekurencji:
 

void print_list_recursive(struct dll_node * front)
{
	if (front != NULL)
	{
		printf("%d ", front->data);
		print_list_recursive(front->next);
	}
	else {
		printf("\n");
	}
}

Reszta będzie wyglądać podobnie, ale jak chcesz to mogę rozpisać.

komentarz 4 maja 2018 przez RafalS VIP (122,820 p.)
Podobnie można rozpisać wypisanie od tyłu i find spot. Wiecej petli w listach nie masz więc to tyle rekurencji.
komentarz 4 maja 2018 przez kikosiak Obywatel (1,010 p.)

A takie coś?

 int add_node(struct list_node **list_pointer, int number)
 {

 if(*list_pointer!=NULL && (*list_pointer)->data<number)
     return add_node(&(*list_pointer)->next,number);
 else
     return create_and_add_node(list_pointer,number);
 }


int create_and_add_node(struct list_node **list_pointer, int number)
 {
 struct list_node *new_node = (struct list_node *) malloc(sizeof(struct list_node));

 if(!new_node)
     return -1;
 new_node->data = number;
 new_node->next = *list_pointer;
 *list_pointer = new_node;
 return 0;
 }

 

komentarz 4 maja 2018 przez RafalS VIP (122,820 p.)
Jeśli dziala to też spoko rekurnecja. Btw rekurencja jest wolniejsza niz petla i mniej czytelna. Usywaj tylko jesli musisz :p. Akurat tutsj masz rekurnecje ogonowa, ktora zostanie zoptymalizowana przez kompilator do petli, wiec spoko

Podobne pytania

0 głosów
1 odpowiedź 203 wizyt
pytanie zadane 26 maja 2018 w C i C++ przez Roman1212 Początkujący (460 p.)
0 głosów
1 odpowiedź 443 wizyt
pytanie zadane 18 czerwca 2020 w C i C++ przez Hubertius Bywalec (2,970 p.)
0 głosów
0 odpowiedzi 135 wizyt
pytanie zadane 27 września 2018 w C i C++ przez KaRoLiNakk Nowicjusz (160 p.)

92,455 zapytań

141,263 odpowiedzi

319,100 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...