Однонаправленного Списка


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

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

Также обратите внимание, что я не оптимизировал все это; это просто первый проход, занял около часа. Я буду сопоставление этой (и других) на более позднее время, но, как я сказал, пространство и время улучшения приветствуются.

linked_list.ч

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

#include <stddef.h>

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

typedef struct _llist {
    node* head;
    node* tail;
} llist;

void init_node( node** new_node, int value );
void init_llist( llist** list );
size_t len( llist* list );
void push_back( llist* list, int value );
void push_front( llist* list, int value );
void insert( llist* list, int index, int value );
node* find( llist* list, int value );
void free_llist( llist* list );
void print_llist( llist* list );

#endif

linked_list.с

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

void init_node( node** new_node, int value ) {
    *new_node = (node*)malloc( sizeof(node) );
    (*new_node)->value = value;
    (*new_node)->next = NULL;
}

void init_llist( llist** list ) {
    *list = (llist*)malloc( sizeof(llist) );
    (*list)->head = NULL;
    (*list)->tail = NULL;
}

void push_back( llist* list, int value ) {
    node* new_node;
    init_node( &new_node, value );
    if( !list->head ) {
        /* empty list */
        list->head = new_node;
        list->tail = list->head;
    }
    else {
        list->tail->next = new_node;
        list->tail = new_node;
    }
}

void push_front( llist* list, int value ) {
    node* new_head;
    init_node( &new_head, value );
    new_head->next = list->head;
    list->head = new_head;
    if( !list->tail ) {
        /* was an empty list */
        list->tail = list->head;
    }
}

void insert( llist* list, int index, int value ) {
    int cur_idx = 0;
    node* new_node = NULL;
    node* prev_node = NULL;
    node* cur_node = list->head;    

    if( index < 0 ) return;
    if( index == 0 ) {
        push_front( list, value );
        return;
    }

    /* not sure what I should do here.
       should I hide the 'error' or force
       an assert to fail if the caller 
       tries to insert into an empty list 
       or an invalid position? */
    if( !cur_node ) {
        init_node( &cur_node, value );
        list->head = list->tail = cur_node;
        return;
    }

    while( cur_node && cur_idx < index ) {
        ++cur_idx;
        prev_node = cur_node;
        cur_node = cur_node->next;      
    }

    init_node( &new_node, value );

prev_node->next = new_node;    
    new_node->next = cur_node;
    if( !cur_node ) {
        /* new tail node, end of list */
        list->tail = new_node;
    }
}

node* find( llist* list, int value ) {
    node* tmp = list->head;
    while( tmp != NULL && tmp->value != value ) {
        tmp = tmp->next;
    }

    return tmp;
}

size_t len( llist* list ) {
    size_t len = 0;
    node* current = list->head;
    while( current ) {
        ++len;
        current = current->next;
    }

    return len;
}

void free_llist( llist* list ) {
    node* current = list->head;
    while( current ) {
        node* tmp = current->next;
        free( current );
        current = tmp;      
    }

    list->head = list->tail = NULL;
}

void print_llist( llist* list ) {
    node* cur = list->head;
    while( cur ) {
        printf( "%d\r\n", cur->value );
        cur = cur->next;
    }
}

И некоторые тривиальные модульных тестов, которые все должны пройти, наверное, должны быть более полными:

#include "linked_list.h"
#include <stdio.h>
#include <assert.h>

void test_push_back();
void test_push_front();
void test_len();
void test_insert();
void test_find();

int main( int argc, char* argv[] ) {
    test_push_back();
    test_push_front();
    test_len();
    test_insert();
    test_find();
    puts( "All Passed" );
    return 0;
}

void test_push_back() {
    llist* list;
    node* current;
    int i;
    int start = 0;
    int count = 100;
    init_llist( &list );

    for( i = start; i < count; ++i ) {
        push_back( list, i );
    }

    current = list->head;
    for( i = start; current; ++i ) {
        assert( current->value == i );
        current = current->next;
    }

    free_llist( list ); 
}

void test_push_front() {
    llist* list;
    node* current;
    int i;
    int start = 0;
    int count = 100;
    init_llist( &list );

    for( i = start; i < count; ++i ) {
        push_front( list, i );
    }

    current = list->head;
    for( i = count - 1; current; --i ) {
        assert( current->value == i );
        current = current->next;
    }

    free_llist( list ); 
}

void test_len() { 
    llist* list;
    init_llist( &list );

    assert( len( list ) == 0 );
    push_back( list, 1 );
    assert( len( list ) == 1 );

    free_llist( list );
    assert( len( list ) == 0 );
}

void test_insert() {
    llist* list;
    init_llist( &list );

    /* insert into empty list */
    insert( list, 0, 1 );
    assert( list->head->value == 1 && list->tail->value == 1 );

    /* insert at the end */
    insert( list, 1, 3 );
    assert( list->tail->value == 3 );

    /* insert in the middle */
    insert( list, 1, 2 );
    assert( list->head->next->value == 2 );

    free_llist( list );
    init_llist( &list );

    push_back( list, 1 );
    push_back( list, 2 );
    push_back( list, 3 );

    /* insert to front of already populated list */
    insert( list, 0, -1 );
    assert( list->head->value == -1 );
    assert( list->tail->value == 3 );

    /* invalid index, too large, place at end */
    insert( list, 100, 100 );
    assert( list->tail->value == 100 );

    free_llist( list );
}

void test_find() {
    llist* list;
    node* found_node;
    init_llist( &list );

    /* not present, shoudl return NULL */
    found_node = find( list, 0 );
    assert( found_node == NULL );

    push_back( list, 1 );
    push_back( list, 2 );
    push_back( list, 3 );

    found_node = find( list, 1 );
    assert( found_node == list->head && found_node->value == 1 );

    found_node = find( list, 2 );
    assert( found_node->value == 2 );

    found_node = find( list, 3 );
    assert( found_node == list->tail && found_node->value == 3 );

    free_llist( list ); 
}


921
7
задан 24 октября 2011 в 12:10 Источник Поделиться
Комментарии
2 ответа

Ваш вопрос с тегами с, и файл заканчивается .гр. Вот некоторые мысли из этого угла:


  • Не мешай литье пустоту * другой тип указателя. Это c++ вещь. В c, void*, который может быть неявно приведен к любому типу указателя.

  • Нет такой вещи, как пространства имен, так что не использовать столкновения подверженных имена, как узел или лен(). Добавить какой-то префикс.

  • Танос может потерпеть неудачу. Вы хотите пузыриться, что состояние ошибки. Все ваши функции, что в конечном итоге вызова функции malloc далее вниз по стеку понадобится средств, чтобы вернуть ошибку, а также. Как правило, способ сделать это-вернуть значение NULL (если ваша функция возвращает указатель типа) или сделать функцию возврата боол ( в C99) или Инт и некоторые конвенции, где определенное значение означает провал. (В POSIX это, как правило, инт возвращая 0 в случае успеха. Windows обычно имеют логическое, где ненулевое значение означает успех. Возврат кодов ошибок также популярен.)

Некоторые другие мысли:


  • Рассмотрим альтернативные схемы распределения для структуры коллекции. Лично я предпочел бы самой структуры (а не узлов, конечно), чтобы быть выделенный вызывающим. Стоит ли делать Танос что-то только размер двух указателей в llist_init? Я бы сказал Нет. Далее, рассмотрим способ работы с памятью, если вы хотите включить список внутри структуры: зачем иметь указатель на него, когда вы можете просто иметь структуру, перечень быть членом крупной структуры?

  • Использование пробелов кажется несовместимым. Порой вам поставить дополнительный символ новой строки между декларациями и заявлениями, а порой нет. Это конечно субъективно, какой из них вы выберете (я бы предпочел больше места лично), но важно быть последовательным.

13
ответ дан 24 октября 2011 в 02:10 Источник Поделиться

Мой первый медведь Буг идентификаторы не должны начинаться с подчеркивания:

typedef struct _node {
typedef struct _llist {

Вижу: что-правила-о-помощи-в-подчеркиваем-В-а-с-идентификатор

А не имея каких-либо выходных параметров, я думаю, это легче увидеть поведение, возвращая результаты:

node* init_node(int value )
{
node* new_node = (node*)malloc( sizeof(node) );
new_node->value = value;
new_node->next = NULL;

return new_node;
}


/* не уверен, что я должен делать здесь.
я должен скрыть 'ошибка' или силу
это утверждение с ошибкой, если абонент
пытается вставить в пустой список
или недопустимая позиция? */

Я не думаю, что это утверждение подходит как сил для выхода из программы.
Но некоторые формы индикации ошибки могут быть полезны. Или вы можете документировать поведение и решить, что он сделал. Лично я бы сказал (в документации) вставки, где индекс находится за пределами массива эквивалентно push_back() и на этом успокоиться. Вставка в пустой список и после окончания имеют одинаковое поведение.

Тогда длина как на данный момент реализовано:

size_t len( llist* list ) {

На самом деле является операцией o(n) времени. Это будет просто сделать это за O(1) и сохранить размер.

Метод, который освободит список не освобождает объект-контейнер:

void free_llist( llist* list ) // frees all the nodes.

Я хотел бы также ожидать, чтобы освободить объект, выделенный init_llist.

11
ответ дан 24 октября 2011 в 01:10 Источник Поделиться