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

Lista dwukierunkowa

VPS Starter Arubacloud
0 głosów
443 wizyt
pytanie zadane 18 czerwca 2020 w C i C++ przez Hubertius Bywalec (2,970 p.)

Hej :)

Rozpisuję obecnie funkcje wymagane do zadanka z związanego z konstrukcją listy dwukierunkowej:

Oto treść wymagana do rozpisania funkcji:

Napisz program pozwalający użytkownikowi na wykonywanie dowolnej operacji na liście dwukierunkowej z poziomu konsoli (menu tekstowe).

W tym celu zaimplementuj listę wiązaną dwukierunkową, opartą o następujące struktury oraz API:

struct doubly_linked_list_t
{
  struct node_t *head;
  struct node_t *tail;
};

struct node_t
{
  int data;
  struct node_t *next;
  struct node_t *prev;
};

gdzie:

head - wskaźnik na pierwszy element listy, jeżeli lista jest pusta powinien być ustawiony na NULL,
tail - wskaźnik na ostatni element listy, jeżeli lista jest pusta powinien być ustawiony na NULL.
next - wskaźnik na następny element listy, jeżeli nie ma następnego elementu to NULL
prev - wskaźnik na poprzedni element listy, jeżeli nie ma poprzedniego elementu to NULL,
data - wartość przechowywana w elemencie listy
Przygotuj następujące funkcje, umożliwiające obsługę listy:

struct doubly_linked_list_t* dll_create();

int dll_push_back(struct doubly_linked_list_t* dll, int value);
int dll_push_front(struct doubly_linked_list_t* dll, int value);
int dll_pop_front(struct doubly_linked_list_t* dll, int *err_code);
int dll_pop_back(struct doubly_linked_list_t* dll, int *err_code);

int dll_back(const struct doubly_linked_list_t* dll, int *err_code);
int dll_front(const struct doubly_linked_list_t* dll, int *err_code);

struct node_t* dll_begin(struct doubly_linked_list_t* dll);
struct node_t* dll_end(struct doubly_linked_list_t* dll);

int dll_size(const struct doubly_linked_list_t* dll);
int dll_is_empty(const struct doubly_linked_list_t* dll);

int dll_at(const struct doubly_linked_list_t* dll, unsigned int index, int *err_code);

int dll_insert(struct doubly_linked_list_t* dll, unsigned int index, int value);
int dll_remove(struct doubly_linked_list_t* dll, unsigned int index, int *err_code);

void dll_clear(struct doubly_linked_list_t* dll);

void dll_display(const struct doubly_linked_list_t* dll);
void dll_display_reverse(const struct doubly_linked_list_t* dll);
Deklaracje wszystkich funkcji oraz struktur umieść w pliku nagłówkowym doubly_linked_list.h, a definicje w pliku doubly_linked_list.c.

struct doubly_linked_list_t* dll_create();
Funkcja przydziela pamięć na strukturę doubly_linked_list_t, inicjuje ją na pustą listę dwukierunkową i zwraca adres przydzielonej struktury. Jeżeli operacja się nie powiedzie to zwraca NULL.

int dll_push_back(struct doubly_linked_list_t* dll, int value);
int dll_push_front(struct doubly_linked_list_t* dll, int value);
Funkcje dodają element o wartości value na koniec (push_back) lub początek (push_front) listy dll. Funkcje zwracają:

0 w przypadku sukcesu,
1 w przypadku błędnych danych wejściowych lub
2 jeżeli nie uda się przydzielić pamięci.
int dll_pop_front(struct doubly_linked_list_t* dll, int *err_code);
int dll_pop_back(struct doubly_linked_list_t* dll, int *err_code);
Funkcje usuwają pierwszy (pop_front) lub ostatni (pop_back) element z listy dll zwracając jego wartość. Do zmiennej err_code, o ile to możliwe, zapisany powinien zostać kod błędu:

0 w przypadku sukcesu,
1 w przypadku błędnych danych wejściowych.
int dll_front(const struct doubly_linked_list_t* dll, int *err_code);
int dll_back(const struct doubly_linked_list_t* dll, int *err_code);
Funkcje zwracają wartość pierwszego (front) lub ostatniego (back) elementu z listy dll bez usuwania tego elementu. Do zmiennej err_code, o ile to możliwe, zapisany powinien zostać kod błędu:

0 w przypadku sukcesu,
1 w przypadku błędnych danych wejściowych.
struct node_t* dll_begin(struct doubly_linked_list_t* dll);
struct node_t* dll_end(struct doubly_linked_list_t* dll);
Funkcje zwracają:

wskaźnik na pierwszy (begin) lub ostatni (end) elementu listy dll lub
NULL jeżeli nie będzie to możliwe.
int dll_size(const struct doubly_linked_list_t* dll);
Funkcja zwraca:

liczbę elementów w liście dll lub
-1 w przypadku błędnych danych wejściowych.
int dll_is_empty(const struct doubly_linked_list_t* dll);
Funkcja sprawdza czy lista dll jest pusta. Funkcja zwraca:

1 jeżeli lista jest pusta,
0 jeżeli w liście znajdują się jakieś elementy lub
-1 w przypadku błędnych danych wejściowych.
int dll_at(const struct doubly_linked_list_t* dll, unsigned int index, int *err_code);
Funkcja zwraca wartość elementu spod indeksu index listy dll. Indeks elementu liczony jest względem pierwszego elementu (head). Do zmiennej err_code, o ile to możliwe, zapisany powinien zostać kod błędu:

0 w przypadku sukcesu,
1 w przypadku błędnych danych wejściowych.
int dll_insert(struct doubly_linked_list_t* dll, unsigned int index, int value);
Funkcja dodają element o wartości value na pozycję index listy dll. Funkcja zwraca:

0 w przypadku sukcesu,
1 w przypadku błędnych danych wejściowych lub
2 jeżeli nie uda się przydzielić pamięci.
Przykład:

Dana jest lista sześciu elementów ll = ABCDEF.
Element x jest wstawiany na pozycję 3.
Lista ll po zmianie: ABCxDEFG.
int dll_remove(struct doubly_linked_list_t* dll, unsigned int index, int *err_code);
Funkcja usuwa element spod indeksu index z listy dll i zwraca jego wartość. Do zmiennej err_code, o ile to możliwe, zapisany powinien zostać kod błędu:

0 w przypadku sukcesu,
1 w przypadku błędnych danych wejściowych.
void dll_clear(struct doubly_linked_list_t* dll);
Funkcja usuwa wszystkie elementy z listy dll (zwalnia również pamięć).

void dll_display(const struct doubly_linked_list_t* dll);
Funkcja wyświetla wszystkie elementy z listy dll, w jednym wierszu, oddzielone spacjami. Jeżeli lista jest pusta to funkcja nie podejmuje żadnej akcji.


void dll_display_reverse(const struct doubly_linked_list_t* dll);

Funkcja wyświetla wszystkie elementy z listy dll, w jednym wierszu, oddzielone spacjami. Elementy należy wyświetlać od ostatniego (tail).

Jeżeli lista jest pusta to funkcja nie podejmuje żadnej akcji.

 

komentarz 18 czerwca 2020 przez Hubertius Bywalec (2,970 p.)

Na tą chwilę rozpisałem swój kod do funkcji:

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

struct doubly_linked_list_t* dll_create()
{
    struct doubly_linked_list_t * pointer = malloc( sizeof(struct doubly_linked_list_t) * 1  );
    if( pointer == NULL )
    {
        return NULL;
    }
    pointer->head = NULL;
    pointer->tail = NULL;
    return pointer;
}

int dll_push_back(struct doubly_linked_list_t* dll, int value) // dodanie elementu na koniec
{
    if( dll == NULL )
    {
        return 1;
    }
    if( dll->tail == NULL && dll->head == NULL ) //gdy lista jest pusta
    {
        struct node_t * first_in_list = (struct node_t *) malloc (sizeof(struct node_t) * 1);
        if( first_in_list == NULL )
        {
            return 2;
        }
        dll->head = first_in_list;
        dll->tail = first_in_list;
        first_in_list->prev = NULL;
        first_in_list->next = NULL;
        first_in_list->data = value;
    }
    else // gdy lista nie jest pusta
    {
        struct  node_t * pointer_on_tail = dll->tail;
        struct  node_t * pointer_on_next = pointer_on_tail->next;
        pointer_on_next = (struct node_t *) malloc (sizeof( struct node_t) * 1);
        if( pointer_on_next == NULL )
        {
            return 2;
        }
        pointer_on_next->data = value;
        pointer_on_next->next = NULL;
        pointer_on_next->prev = dll->tail;
        dll->tail = pointer_on_next; //wskaznik na ostatni element
        pointer_on_tail->next = pointer_on_next;
    }

    return 0;
}

int dll_push_front(struct doubly_linked_list_t* dll, int value) // dodanie elementu na pocz.
{
    if( dll == NULL  )
    {
        return 1;
    }
    if( dll->tail == NULL && dll->head == NULL ) //gdy lista jest pusta
    {
        struct node_t * first_in_list = (struct node_t *) malloc (sizeof(struct node_t) * 1);
        if( first_in_list == NULL )
        {
            return 2;
        }
        dll->head = first_in_list;
        dll->tail = first_in_list;
        first_in_list->prev = NULL;
        first_in_list->next = NULL;
        first_in_list->data = value;
    }
    else
    {
        struct  node_t * pointer_on_head = dll->head;
        struct  node_t * pointer_on_prev = pointer_on_head->prev;
        pointer_on_prev = (struct node_t *) malloc (sizeof( struct node_t) * 1);
        if( pointer_on_prev == NULL )
        {
            return 2;
        }
        pointer_on_prev->data = value;
        pointer_on_prev->prev = NULL;
        pointer_on_prev->next = dll->head;
        dll->head = pointer_on_prev;
        pointer_on_head->prev = pointer_on_prev;
    }
    return 0;
}

int dll_pop_front(struct doubly_linked_list_t* dll, int *err_code)
{
    if( dll == NULL )
    {
        if( err_code != NULL )
        {
            *err_code = 1;
        }
    }
    struct node_t * pointer_on_head = dll->head;
    int value;
    if( pointer_on_head == dll->tail )
    {
        value = pointer_on_head->data;
        free(pointer_on_head);
        dll->head = NULL;
        dll->tail = NULL;
        if( err_code != NULL )
        {
            *err_code = 0;
        }
    }
    else
    {
        struct node_t * pointer_on_next = pointer_on_head->next;
        pointer_on_next->prev = NULL;
        value = pointer_on_head->data;
        dll->head = pointer_on_next;
        free(pointer_on_head);
        if( err_code != NULL )
        {
            *err_code = 0;
        }
    }
    return value;
}
int dll_pop_back(struct doubly_linked_list_t* dll, int *err_code)
{
    if( dll == NULL || dll->tail == NULL || dll->head == NULL )
    {
        if( err_code != NULL )
        {
            *err_code = 1;
            return 0;
        }
    }
    struct node_t * pointer_on_tail = dll->tail;
    int value;
    if( pointer_on_tail == dll->head )
    {
        value = pointer_on_tail->data;
        free(pointer_on_tail);
        dll->tail = NULL;
        dll->head = NULL;
        if( err_code != NULL )
        {
            *err_code = 0;
        }
    }
    else
    {
        struct node_t * pointer_on_before = pointer_on_tail->prev;
        value = pointer_on_tail->data;
        pointer_on_before->next = NULL;
        dll->tail = pointer_on_before;
        free(pointer_on_tail);
        if( err_code != NULL )
        {
            *err_code = 0;
        }
    }
    return value;
}

int dll_back(const struct doubly_linked_list_t* dll, int *err_code)
{
    if( dll == NULL || dll->tail == NULL)
    {
        if( err_code != NULL )
        {
            *err_code = 1;
        }
    }
    struct node_t * pointer_on_tail = dll->tail;
    int value = pointer_on_tail->data;
    if( err_code != NULL )
    {
        *err_code = 0;
    }
    return value;
}
int dll_front(const struct doubly_linked_list_t* dll, int *err_code)
{
    if( dll == NULL || dll->head == NULL )
    {
        if( err_code != NULL )
        {
            *err_code = 1;
        }
    }
    struct node_t * pointer_on_head = dll->head;
    int value = pointer_on_head->data;
    if( err_code != NULL )
    {
        *err_code = 0;
    }
    return value;
}

struct node_t* dll_begin(struct doubly_linked_list_t* dll)
{
    if( dll == NULL || dll->head == NULL)
    {
        return NULL;
    }
    return dll->head;
}

struct node_t* dll_end(struct doubly_linked_list_t* dll)
{
    if( dll == NULL || dll->tail == NULL)
    {
        return NULL;
    }
    return dll->tail;
}

int dll_size(const struct doubly_linked_list_t* dll)
{
    if( dll == NULL || dll->head == NULL || dll->tail == NULL)
    {
        return 1;
    }
    struct node_t * pointer_on_ending = dll->tail;
    struct node_t * pointer_on_beginning = dll->head;
    struct node_t * temp = pointer_on_beginning;
    struct node_t * temp_on_next;
    int count = 0;
    do
    {
        temp_on_next = temp->next;
        count++;
        if( temp_on_next == pointer_on_ending )
        {
            count++;
            break;
        }
        temp = temp_on_next;
    }while(1);
    return count;
}

int dll_is_empty(const struct doubly_linked_list_t* dll)
{
    if( dll == NULL )
    {
        return -1;
    }
    if( dll->head == NULL && dll->tail == NULL )
    {
        return 1;
    }
    return 0;
}

int dll_at(const struct doubly_linked_list_t* dll, unsigned int index, int *err_code)
{
     int score_from_dll_is_empty = dll_is_empty(dll);
     if( (score_from_dll_is_empty == -1 || score_from_dll_is_empty == 1) || index == 0 )
     {
         if( err_code != NULL )
         {
             *err_code = 1;
         }
     }
     unsigned int count = 0;
     struct node_t * pointer = dll->head;
     int value;
     do
     {
         if( pointer == dll->tail )
         {
             break;
         }
         if( count == index )
         {
             value = pointer->data;
             break;
         }
         pointer = pointer->next;
         count++;
     }while( count <= index);
     return value;
}



int dll_insert(struct doubly_linked_list_t* dll, unsigned int index, int value)
{
    int score_from_dll_is_empty = dll_is_empty(dll);
    if( (score_from_dll_is_empty == -1 || score_from_dll_is_empty == 1)  )
    {
         return 1;
    }
    struct node_t * pointer = dll->head;
    unsigned int count = 0;
    if( index > 0 )
    {
        do
        {
            if( count == index )
            {
                break;
            }
            if( pointer == dll->tail )
            {
                break;
            }
            pointer = pointer->next;
            count++;
        }while(1);
    }
    if( count < index )
    {
        return 1;
    }
    struct node_t * new_structure = (struct node_t *) malloc( sizeof(struct node_t) * 1 );
    if( new_structure == NULL )
    {
        return 2;
    }
    if( count == 0 )
    {
        new_structure->data = value;
        new_structure->prev = NULL;
        new_structure->next = dll->head;
        pointer->prev = new_structure;
        dll->head = new_structure;
    }
    if( count != 0 && pointer != dll->tail )
    {
        struct node_t * next = pointer->next;
        struct node_t * before = pointer->prev;
        next->prev = new_structure;
        before->next = new_structure;
        new_structure->data = value;
        new_structure->next = next;
        new_structure->prev = before;
    }
    if( pointer ==  dll-> tail)
    {
        new_structure->data = value;
        new_structure->prev = dll->tail;
        new_structure->next = NULL;
        pointer->next = new_structure;
        dll->tail = new_structure;
    }
    return 0;
}

int dll_remove(struct doubly_linked_list_t* dll, unsigned int index, int *err_code)
{
    int score_from_dll_is_empty = dll_is_empty(dll);
    if( (score_from_dll_is_empty == -1 || score_from_dll_is_empty == 1)  )
    {
         if( err_code != NULL )
         {
             *err_code = 1;
         }
    }
    struct node_t * pointer = dll->head;
    unsigned int count = 0;
    if( index > 0 )
    {
        do
        {
            if( count == index )
            {
                break;
            }
            if( pointer == dll->tail )
            {
                break;
            }
            pointer = pointer->next;
            count++;
        }while(1);
    }
    if( count < index )
    {
        return 1;
    }
    int value;
    if( pointer == dll->head )
    {
        value = pointer->data;
        struct node_t * next = pointer->next;
        next->prev = NULL;
        dll->head = next;
        free(pointer);
    }
    else if( pointer == dll->tail )
    {
        value = pointer->data;
        struct node_t * previously = pointer->prev;
        previously->next = NULL;
        dll->tail = previously;
        free(pointer);
    }
    else
    {
        value = pointer->data;
        struct node_t * next = pointer->next;
        struct node_t * previously = pointer->prev;
        next->prev = previously;
        previously->next = next;
        free(pointer);
    }
    return value;
}

void dll_clear(struct doubly_linked_list_t* dll)
{
    if( dll == NULL )
    {
        return;
    }
    else
    {
        struct node_t * pointer = dll->head;
        struct node_t * temp ;
        do
        {
            if( pointer == NULL )
            {
                break;
            }
            if( pointer == dll->tail )
            {
                break;
            }
            temp = pointer->next;
            free(pointer);
            pointer = temp;
        }while(1);
    }
    if( dll->tail != NULL )
    {
        free(dll->tail);
    }
}

void dll_display(const struct doubly_linked_list_t* dll)
{

}
void dll_display_reverse(const struct doubly_linked_list_t* dll)
{

}

Wiem, że na pewno dobrze są funkcje push_front i push_back. Jednak co z innymi? Czy czegoś im brakuje? Co powinienem w nich poprawić? Z góry dziękuję za odpowiedzi.   :)

1 odpowiedź

0 głosów
odpowiedź 18 czerwca 2020 przez j23 Mędrzec (194,920 p.)
if( dll->tail == NULL && dll->head == NULL )

To nie błąd, ale... Skoro tail jest NULL, to siłą rzeczy head też musi być. Nie ma sensu testować obu wskaźników - wystarczy jeden.

struct  node_t * pointer_on_next = pointer_on_tail->next;
pointer_on_next = (struct node_t *) malloc (sizeof( struct node_t) * 1);

Po co w pierwszej linii przypisujesz wskaźnik, skoro w następnej go nadpisujesz innym?

W dll_pop_front nie sprawdzasz, czy lista ma jakieś elementy.

    struct node_t * pointer_on_tail = dll->tail;
    int value = pointer_on_tail->data;

Po co takie akrobacje? Nie wystarczy samo dll->tail->data?

    if( dll == NULL || dll->head == NULL)
    {
        return NULL;
    }
    return dll->head;
return (dll == NULL) ? NULL : dll->head;
    struct node_t * pointer_on_ending = dll->tail;
    struct node_t * pointer_on_beginning = dll->head;
    struct node_t * temp = pointer_on_beginning;
    struct node_t * temp_on_next;
   int count = 0;
    do
    {
        temp_on_next = temp->next;
        count++;
        if( temp_on_next == pointer_on_ending )
        {
            count++;
            break;
        }
        temp = temp_on_next;
    }while(1);

Co Ty masz z tym tworzeniem zbędnych wskaźników? Efekt jest taki, że kodu jest więcej niż trzeba.

int count = 0;
struct node_t * temp = dll->head;

while (temp) { 
	++count; 
	temp = temp->next;
}
   if( pointer == dll->head )
    {
        struct node_t * next = pointer->next;
        next->prev = NULL; // zakładasz, że next nie jest NULL, a może
        ...
    }
    else if( pointer == dll->tail )
    {
        struct node_t * previously = pointer->prev;
        previously->next = NULL; // zakładasz, że previously nie jest NULL, a może
        ...
    }

Tu masz uproszczoną wersję funkcji dll_clear:

void dll_clear(struct doubly_linked_list_t* dll)
{
    if( dll == NULL ) return;
	while (dll->head) {
		struct node_t * p = dll->head->next;
		free(dll->head);
		dll->head = p;
	}

	free(dll);
}

 

Tyle...

Podobne pytania

0 głosów
1 odpowiedź 330 wizyt
pytanie zadane 4 maja 2018 w C i C++ przez kikosiak Obywatel (1,010 p.)
0 głosów
0 odpowiedzi 135 wizyt
pytanie zadane 27 września 2018 w C i C++ przez KaRoLiNakk Nowicjusz (160 p.)
0 głosów
1 odpowiedź 203 wizyt
pytanie zadane 26 maja 2018 w C i C++ przez Roman1212 Początkujący (460 p.)

92,454 zapytań

141,262 odpowiedzi

319,089 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!

...