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

Question

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

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

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, и у меня довольно хорошо разобрались указатели и косвенные указания, но на это у меня ушло некоторое время, чтобы полностью понять.

Answer 1

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

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

Answer 2

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

Таким образом, чтобы вставить, у вас есть 3 варианта,

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

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

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

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

Answer 3

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

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

Answer 4

Это хорошо известная вещь - итерация двойного указателя (это мое имя, я не знаю официального имени). Цель состоит в том, чтобы иметь возможность найти позицию в одном связанном списке, а затем вставить до этой позиции (вставка после нее тривиальна). Реализованный наивно, для этого требуется два указателя (текущий и предыдущий) и специальный код для начала списка (когда 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;
}

Answer 5

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

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

Answer 6

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

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

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

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

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

Answer 7

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

Answer 8

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

Answer 9

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

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

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

Answer 10

несмотря на хитрости, разве роль переменной "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;
    }