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

Я сказал бы, что идиома является "видом кода, который дал 'c' дурную славу"

• Неоправданно умный
• Неоправданно компактный
• Удивительные побочные эффекты на вызывающей стороне
• Никакая обработка ошибок на malloc
• Только работы для американских английских строк

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

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

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

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

Вы пропускаете обработку ошибок для malloc/strdup провальный случай btw.

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

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

Это - известная вещь - двойное повторение указателя (это - мое имя его, я не знаю официальное название). Цель состоит в том, чтобы смочь определить положение в единственном связанном списке и затем вставить перед тем положением (вставка после того, как это будет тривиально). Реализованный наивно, это требует двух указателей (текущий и предыдущий) и специальный код для начала списка (когда предыдущий == ПУСТОЙ УКАЗАТЕЛЬ).

Код путем, который я обычно пишу этому, является чем-то вроде

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;
}

Обновление:

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

// 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;
}

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

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

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

Вставка нового узла 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

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

Для ответа на исходный вопрос это известно как указатель центральный подход вместо наивного узла центральный подход. Глава 3 "Усовершенствованных Методов программирования" Rex Barzee, доступным по amazon.com, включает намного лучшую реализацию в качестве примера указателя центральный подход.