Реализация с однонаправленного списка


Я понимаю, что мой код довольно длинный, так что хотелось бы отзывов, в основном на пару вещей, если времени мало:

1) возвращение INT_MIN, чтобы указать, что он был пуст.

2) в removeHead и removeTail функции.

Не стесняйтесь добавлять больше критики.

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

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

typedef struct
{
    Node* head;
    Node* tail;
}LinkedList;

void printListRec(Node* node);
void printHeadAndTail(LinkedList* list);
int printList(LinkedList* list);
int linkedListSize( LinkedList* list );
int searchForElement( LinkedList* list , int value );
int isEmpty( LinkedList* list );
int removeElement( LinkedList* list , int value);
int removeTail( LinkedList* list );
int removeHead( LinkedList* list );
void addTail( LinkedList* list , int value);
void addHead( LinkedList* list , int value);
LinkedList* initialize() ;

//implement a clear list function

int main()
{
    LinkedList* linkedlist = initialize();

    addHead(linkedlist , 1);
    printHeadAndTail(linkedlist);
    printList(linkedlist);

    addHead(linkedlist , 2);
    printHeadAndTail(linkedlist);
    printList(linkedlist);

    removeTail(linkedlist);
    printHeadAndTail(linkedlist);
    printList(linkedlist);

    removeTail(linkedlist);
    printHeadAndTail(linkedlist);
    printList(linkedlist);

    addTail(linkedlist , 3);
    printHeadAndTail(linkedlist);
    printList(linkedlist);



    return 0;
}

LinkedList* initialize() //creates linked list with no nodes, initializes head & tail to 0
{
    LinkedList* list = malloc(sizeof(LinkedList));
    list->head = NULL;
    list->tail = NULL;
    return list;
}

void addHead( LinkedList* list , int value)
{
    Node* newNode = malloc( sizeof(Node) );
    newNode->value = value;

    if( isEmpty(list) )
    {
        newNode->next = NULL;
        list->head = list->tail = newNode;
    }

    else
    {
        newNode->next = list->head;
        list->head = newNode;
    }
    puts("Add head");
}

void addTail( LinkedList* list , int value)
{
    Node* newNode = malloc( sizeof(Node) );
    newNode->value = value;
    newNode->next = NULL;

    if( isEmpty(list) )
    {
        newNode->next = NULL;
        list->head = list->tail = newNode;
    }

    else
    {
        list->tail->next = newNode;
        list->tail = newNode;
    }
    puts("Add tail");
}

int removeHead( LinkedList* list )
{
    if(isEmpty(list))
        return INT_MIN;

    Node* nodeToDelete = list->head;
    int value = nodeToDelete->value;


    if(list->head == list->tail) //if node is the only node present
        list->head = list->tail = NULL;
    else
        list->head = list->head->next;

    free(nodeToDelete);
    puts("Remove head");
    return value;
}

int removeTail( LinkedList* list )
{
    if( isEmpty(list) )
        return INT_MIN;

    int value ;
    if(list->head == list->tail)
    {
        value = list->tail->value;
        free(list->tail);
        list->head = list->tail = NULL;
        return value;
    }

    Node* nodeToDelete = list->tail;
    value = nodeToDelete->value;

    Node* nodeBeforeTail = list->head;
    while( nodeBeforeTail->next != nodeToDelete )
        nodeBeforeTail = nodeBeforeTail->next;

    nodeBeforeTail->next = NULL;
    list->tail = nodeBeforeTail;

    free(nodeToDelete);
    puts("Remove tail");
    return value;
}

int removeElement( LinkedList* list , int value)
{
    if( list->head->value == value )
    {
        removeHead(list);
        return 0; //element found
    }

    if(list->tail->value == value)
    {
        removeTail(list);
        return 0;
    }

    Node* node = list->head;
    while( (node->next) != list->tail )
    {
        if( node->next->value == value)
        {
            Node* nodeToDelete = node->next;
            node->next = node->next->next;
            free(nodeToDelete);
            return 0;
        }
        node = node->next;
    }
    return 1;
}

int isEmpty( LinkedList* list )
{
    return !list->head && !list->tail;
}

int searchForElement( LinkedList* list , int value )
{
    if(isEmpty(list))
        return -1;

    Node* node = list->head;

    do
    {
        if(node->value == value) return 0;
    }while( (node = node->next) );

    return 1;
}

int linkedListSize( LinkedList* list )
{
    int counter = 0;
    Node* node = list->head;
    while( node )
    {
        counter++;
        node = node->next;
    }
    return counter;
}

void printHeadAndTail(LinkedList* list)
{
    if(isEmpty(list))
    {
        printf("\nHead pointer : %d , tail pointer : %d\n" , list->head , list->tail);
        return;
    }
    printf("Head pointer: %d , Head's pointer to next : %d\n" , list->head, list->head->next );
    printf("Tail pointer: %d , tail's pointer to next : %d\n" , list->tail, list->tail->next );
}

void printListRec(Node* node)
{
    if( !node )
        return;
    printf("%d " , node->value);
    printListRec(node->next);
}

int printList(LinkedList* list)
{
    if( isEmpty(list) )
    {
        puts("List is empty");
        return 1;
    }

    puts("\nPrint Linked List: ");
    Node* node = list->head;
    while( node )
    {
        printf("%d " , node->value);
        node = node->next;
    }

    puts("\n*******************\n");

    return 0;
}


240
2
задан 20 марта 2018 в 07:03 Источник Поделиться
Комментарии
2 ответа

    LinkedList* list = malloc(sizeof(LinkedList));

Всегда убедитесь, что распределение функций malloc и друзей удастся. Эти функции возвращают null указатель, когда они не в состоянии выделить память. Если среда не настроена на охрану/аварии, когда malloc не удается, то у вас есть куча null указатель разыменовывает, приводящих к неопределенному поведению.


    puts("Add head");

Эти сообщения ничего не делать, но производить шум. Вы должны либо использовать директиву прекомпилятором, чтобы переключить вызов функции трассировки отладки сборки или перемещение отслеживания вашего водителя-испытателя. Еще лучше, использовать отладчик.


int removeHead( LinkedList* list )
{
if(isEmpty(list))
return INT_MIN;
// ...
}

Не пытайтесь возвращать коды ошибок и фактических данных представимы через одну и ту же переменную отдачу. Библиотека может использоваться пользователем INT_MIN в их набор данных и Вызов removeXXXX() может привести в некоторых пользователей-код полагать, некоторые данные были удалены. Решите, хотите ли вы информировать абонента об успехе или неудаче, а не заморачиваться с возвратом данных из списка. Если собеседник действительно хочет данные, они могут скопировать его себе перед удалением.


Сохранить функции короткие и простые. Когда функции становится больше, чем несколько строк, искать возможности реструктурировать в более высокие уровни абстракции. Например, removeTail функция имеет один большой блок, который по существу removeHead а другой блок, который, по существу, находит предыдущий узел.


int isEmpty( LinkedList* list )
{
return !list->head && !list->tail;
}

Есть ли такая ситуация, когда либо list->head или list->tail существует, а другой нет? Что произойдет, если абонент передает list это null?


        if(node->value == value) return 0;
}while( (node = node->next) );

if(isEmpty(list))
if( !node )

Будьте последовательны с вашим форматирования.

    if( isEmpty(list) )
if( !node )

Быть безопасным и всегда свяжите ваши однострочные областей тела. Они не могут быть неправильно истолкованы сопровождающими (как человека, так и машины).

    if( node->value == value) 
{
return 0;
}
}
while( (node = node->next) );

Что-то рассмотреть: дифференцировать структуры управления с функцией звонков, чтобы помочь с читаемость и понимание кода. Больше времени будет потрачено на чтение кода, чем писать код. например

    if (node->value == value) 
{
return 0;
}
}
while (node = node->next);


int linkedListSize( LinkedList* list )
{
int counter = 0;
Node* node = list->head;
while( node )
{
counter++;
node = node->next;
}
return counter;
}

Расчет размеров является линейной операцией. Рассматривали ли вы просто хранить текущий размер в LinkedList структура и обновление значение, как вы действуете в списке? Что бы называть размер постоянной времени операции за счет размера int.


Где-функция свободного списке? printList() вперед объявлены. Нет реализации?

5
ответ дан 20 марта 2018 в 11:03 Источник Поделиться

Матч printf преобразования типов

ССЗ предупреждает меня:

190060.c:220:35: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘Node *’ {aka ‘struct node *’} [-Wformat=]
printf("\nHead pointer : %d , tail pointer : %d\n" , list->head , list->tail);
~^ ~~~~~~~~~~
190060.c:220:55: warning: format ‘%d’ expects argument of type ‘int’, but argument 3 has type ‘Node *’ {aka ‘struct node *’} [-Wformat=]
printf("\nHead pointer : %d , tail pointer : %d\n" , list->head , list->tail);
~^ ~~~~~~~~~~

(и более). Мы хотим *p для указателей:

void printHeadAndTail(LinkedList* list)
{
if(isEmpty(list))
{
printf("\nHead pointer : %p , tail pointer : %p\n" , (void*)list->head , (void*)list->tail);
return;
}
printf("Head pointer: %p , Head's pointer to next : %p\n" , (void*)list->head, (void*)list->head->next );
printf("Tail pointer: %p , tail's pointer to next : %p\n" , (void*)list->tail, (void*)list->tail->next );
}

Использовать const для немодифицируемые операций

Это достаточно легко:

void printListRec(const Node *node);
void printHeadAndTail(const LinkedList *list);
int printList(const LinkedList *list);
int linkedListSize(const LinkedList *list);
int searchForElement(const LinkedList *list, int value);
int isEmpty(const LinkedList *list);

Реализации clearList функция

Есть общее, что упоминает о нем отсутствует; без этого, это труднее, чтобы проверить для утечек памяти.

void clearList(LinkedList *list)
{
Node *n = list->head;
while (n) {
Node *n2 = n->next;
free(n);
n = n2;
}
list->head = list->tail = NULL;
}

Рассмотрим "манекен голова" реализация

Если мы сделаем head элемент, который никогда не используется для значение, но только для своих next член, мы уменьшаем сложность многих функций. Это пример нулевой шаблон проектирования объекта.

Например:

// allocation error-checking omitted - please add some!

void addHead(LinkedList* list, int value)
{
Node* newNode = malloc(sizeof *newNode);
newNode->value = value;
newNode->next = NULL;

if (!list->head.next) {
list->tail = newNode;
}
newNode->next = list->head.next;
list->head.next = newNode;
puts("Add head");
}

void addTail(LinkedList* list , int value)
{
Node* newNode = malloc(sizeof *newNode);
newNode->value = value;
newNode->next = NULL;

list->tail->next = newNode;
list->tail = newNode;
puts("Add tail");
}

int removeHead(LinkedList* list)
{
Node* nodeToDelete = list->head.next;
int value = INT_MIN;
if (nodeToDelete) {
value = nodeToDelete->value;
list->head.next = nodeToDelete->next;
free(nodeToDelete);
if (!list->head.next) {
list->tail = &list->head;
}
}
puts("Remove head");
return value;
}

int removeTail(LinkedList* list)
{
if (!list->head.next)
return INT_MIN;

Node *n = &list->head;
while (n->next->next) n = n->next;

Node* nodeToDelete = n->next;
int value = nodeToDelete->value;

n->next = NULL;
list->tail = n;

free(nodeToDelete);
puts("Remove tail");
return value;
}

int removeElement(LinkedList* list , int value)
{
Node *n = &list->head;
while (n->next && n->next->value != value)
n = n->next;

if (!n->next)
/* not found */
return 0;

if (list->tail == n->next)
return removeTail(list), 1;

Node *newNext = n->next->next;
free(n->next);
n->next = newNext;
return 1;
}

int searchForElement(const LinkedList* list , int value)
{
const Node *n = &list->head;
while ((n=n->next)) {
if (n->value == value) return 0;
}
return 1;
}

Я не уверен, так ли это на самом деле гораздо проще и понятнее, но это техника, чтобы быть в курсе и иметь в наличии, когда вам это нужно. Он имеет тенденцию быть более полезным в двусвязный списки.

Рассмотрим также, можно ли имея tail указатель стоит стоимость его постоянное обновление. Это может быть для длинных списков, которые добавляются к, но если вы можете вместо этого добавить, тогда, может быть, лучше опустить.

2
ответ дан 23 марта 2018 в 11:03 Источник Поделиться