Lista dwukierunkowa

Question

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.

 

Comments

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.   :)

Answer 1

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...