Подтвердить что ты не робот

Интересная идиома, связанная с C

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

Скажем, у нас есть связанная запись списка, поэтому:

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?

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

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

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

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

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

Ответ 2

Я бы сказал, что идиома - это тип кода, который дал "c" плохое имя "

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

Ответ 3

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

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

Ответ 4

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

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

Ответ 5

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

Update:

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

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

Ответ 6

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

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

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

Вставка нового node y до node x становится простой:

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

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

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

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

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

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

Ответ 7

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

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

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

Ответ 8

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

Ответ 9

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

Ответ 10

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

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

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

Ответ 11

несмотря на трюки, не меняется ли переменная "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;
}

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

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