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

Я не вижу ничего, что я бы назвал идиомой как таковой. Это похоже на стандартное кодирование, когда вы имеете дело со структурами данных на C.

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

Какая здесь идиома? Уж точно не реализация связного списка. Использование указателя на конструкцию указателя? Компактная петля?

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

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

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

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

Вставка нового узла y перед узлом x становится простой задачей:

x -> prev -> next = y
y -> next = x
y -> prev = x -> prev
x -> prev = y

Удаление узла x выполняется просто:

x -> prev -> next = x -> next
x -> next -> prev = x -> prev
free x

Обход настроен так, чтобы игнорировать посторонние голова и хвост:

n = head -> next
while n != tail
    process n
    n = n -> next

Все это упрощает понимание кода без особой обработки крайних случаев за счет пары узлов памяти.

Я бы сказал, что эта идиома - это «такой код, который дал« c »плохую репутацию»

• Неоправданно умный
• Неоправданно компактный
• Неожиданные побочные эффекты у звонящего
• Нет обработки ошибок на malloc
• Работает только для строк на английском языке (США)

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

record* insert_sorted(const record* head, const char* value)

Вам не хватает обработки ошибок для случая сбоя malloc / strdup, кстати.

Это хорошо известная штука - итерация с двойным указателем (так я ее называю, официального названия не знаю). Цель состоит в том, чтобы иметь возможность найти позицию в односвязном списке, а затем вставить до этой позиции (вставка после тривиальной). Наивно реализовано, для этого требуются два указателя (текущий и предыдущий) и специальный код для начала списка (когда prev == NULL).

Код, который я обычно пишу, похож на

void insertIntoSorted(Element *&head, Element *newOne)
{
  Element **pp = &head;
  Element *curr;
  while ((curr = *pp) != NULL && less(curr, newOne)) {
    pp = &(pp->next);
  }
  newOne->next = *pp;
  *pp = newOne;
}

Обновлять:

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

// returns deleted element or NULL when key not found
Element *deleteFromList(Element *&head, const ElementKey &key)
{
  Element **pp = &head;
  Element *curr;
  while ((curr = *pp) != NULL && !keyMatches(curr, key)) {
    pp = &(pp->next);
  }
  if (curr == NULL) return NULL;
  *pp = (*pp)->next; // here is the actual delete
  return curr;
}

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

Итак, чтобы вставить, у вас есть 3 варианта:

1: используйте переменную, которая отслеживает предыдущее значение вашего итерационного указателя.

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

3: или более элегантное решение - просто использовать указатель на указатель, так что вы можете просто сделать: *it = new_node();, и он добавит его туда, где раньше был NULL в вашем дереве.

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

Чтобы ответить на исходный вопрос, это известен как подход, ориентированный на указатель, а не на наивный подход, ориентированный на узлы. Глава 3 «Продвинутых методов программирования» Рекса Барзи, доступная по адресу amazon.com, включает гораздо лучший пример реализации подхода, ориентированного на указатель.

Эта идиома приводится в главе 12 «Указатели на C». Она используется для вставки узла в связанный список без заголовка списка.

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

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

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

несмотря на уловки, не изменилась ли роль переменной «r»? как вызывающий абонент узнает, что означает «* r» после звонка? или после выполнения, каков заголовок списка?

Я не мог поверить, что это можно проиллюстрировать (даже в какой-нибудь книге ?!). Я что-нибудь пропустил?

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

void insert_sorted(record** head, const char* value)
{
    record** r = head;
    bool isSameHead = false;
    record* newrec = NULL;
    while(*r && strcmp(value, (*r)->value) > 0) {
        r = &((*r)->next); isSameHead = true; }
    newrec = malloc(sizeof(record));
    newrec->value = strdup(value);
    newrec->next = *r;
    *r = newrec;
    if (!isSameHead) *head = newrec;
}

на самом деле, вероятно, еще один лучший способ сделать это - использовать «фиктивный головной узел», который связывает его рядом с началом списка.

    void insert_sorted(record** head, const char* value)
    {
        record dummyHead;
        dummyHead.next = *head;
        record* r = &dummyHead;
        while(r->next) {
           if (strcmp(value, r->next->value) < 0) 
              break;
           r = r->next;}
        newrec = malloc(sizeof(record));
        newrec->value = strdup(value);
        newrec->next = r->next;
        r->next = newrec;
        *head = dummyHead.next;
    }