Интересная идиома связанного списка C - PullRequest
Новая
       34

Интересная идиома связанного списка C

11 голосов
/ 02 декабря 2008

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

Скажем, у нас есть запись связанного списка, определенная так: 

typedef struct _record
{
    char* value;
    struct _record* next;
} record;

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

void insert_sorted(record** r, const char* value)
{
    record* newrec = NULL;
    while(*r && strcmp(value, (*r)->value) > 0)
        r = &((*r)->next); /* move r to point to the next field of the record */
    newrec = malloc(sizeof(record));
    newrec->value = strdup(value);
    newrec->next = *r;
    *r = newrec;
}

Когда вызывается функция, r указывает на указатель заголовка списка. Во время цикла while значение r обновляется, чтобы указывать на поле next записи, которая находится непосредственно перед точкой, в которую мы хотим поместить новую запись. Последняя строка функции либо обновляет указатель заголовка списка ( если вставка происходит в начале) или next поле предыдущей записи, что довольно круто.

Пара вопросов:

  • У этой идиомы есть имя или она упоминается в какой-либо литературе?

  • Есть ли другие подобные слова на языке Си?

Мне показалось, что я довольно хорошо знаю C, и у меня довольно хорошо разобрались указатели и косвенные указания, но на это у меня ушло некоторое время, чтобы полностью понять.

Ответы [ 11 ]

0 голосов
/ 01 сентября 2013

Я также придумал использование двойного указателя, я использовал его, но мне это не очень нравится. Код, который я придумал, имеет это ядро ​​для поиска определенных объектов и удаления их из списка: 

Element** previous = &firstElement, *current;
while((current = *previous)) {
    if(shouldRemove(current)) {
        *previous = current->next;  //delete
    } else {
        previous = &current->next;  //point to next
    }
}

Причина, по которой мне не нравится мой код, заключается в тонкой разнице между двумя предложениями if: синтаксис почти идентичен, но эффект совершенно другой. Я не думаю, что мы должны писать такой тонкий код, но, делая это иначе, код становится действительно длинным. Так что в любом случае это плохо - вы можете пойти на краткость или на удобочитаемость, это ваш выбор.

Страница:
...