В чем разница между двойным указателем и функцией с возвратом при использовании односвязных списков?

Question

У меня есть это объявление:

struct node {
      int value;
      struct node * next;
  };
 

Тогда я бы сравнил эти две функции:

struct node* function1(struct node *p) {
       p = p->next;
       return p;
}

void function2(struct node **p) {
    (*p) = (*p)->next;
}

В основной функции мы имеем соответственно:

head = funcion1(head);
function2(&head);

Кто-то сказал мне, что «вы должны использовать двойной указатель, когда вам нужно обновить заголовок вашего списка», но в обоих случаях я обновляю его. Можете ли вы помочь мне понять различия?

Answer 1

В чем разница между двойным указателем и функцией с возвратом при использовании односвязных списков?

Вы хотите, чтобы функция обновляла head или вызывающий код? Выбор за вами.

Кто-то сказал мне, что «вы должны использовать двойной указатель, когда вам нужно обновить заголовок вашего списка», но в обоих случаях я обновляю его.

Это больше похоже на «у вас есть использовать двойной указатель, когда вам нужно иметь функцию обновить заголовок вашего списка ».

function2(&head);

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

head = funcion1(head);

Answer 2

Это разные. В function1 изменения, внесенные в struct node* p, являются локальными для блока function1, т.е. изменение является временным. Но в function2 изменения, внесенные в struct node* p НЕ локальные для блока function2, т. Е. Являются постоянными (до тех пор, пока не будут изменены снова).

Это связано с концепцией Call-by-value и Call-by-reference. Чтобы быть точным, следует отметить следующие моменты:

• В Call-by-value изменения, внесенные в параметры, являются локальными для функционального блока, но в Call-by-reference изменения, внесенные в параметры, являются постоянными
• Чтобы передать значение как Call-by-value, мы определяем параметр функции как этот конкретный тип, например, если мы хотим передать int в f1 функцию, то его замедление будет как void f1(int val);. Чтобы передать значение как Call-by-reference, мы определяем параметр функции как указатель определенного типа , например, если мы хотим передать int в f1 функцию, то его замедление будет как void f1(int* val); и вызов будет иметь вид int a= 0; f1(&a);.
• Чтобы передать указатель в качестве ссылки, функция должна иметь one-more-level-of-indirection. например, для передачи int *a; функция должна быть объявлена ​​как void f1(int** val);; для передачи int **a; функция должна быть объявлена ​​как void f1(int*** val); и так далее

Попробуйте следующий код. См. , здесь работает этот код :

struct node * p1 = (struct node*)calloc(1, sizeof(struct node));
struct node * p2 = (struct node*)calloc(1, sizeof(struct node));

p1->next = NULL;
p2->next = NULL;

printf("p1 = %p; and p2 = %p\n", p1, p2);

function1(p1);
function2(&p2);

printf("p1 = %p; and p2 = %p", p1, p2);

ВЫВОД ОБРАЗЦА:

p1 = 0x5604536cf260; and p2 = 0x5604536cf280
p1 = 0x5604536cf260; and p2 = (nil)

В выходных данных выше вы можете увидеть этот адрес p1 не обновляется, но обновляется адрес p2.

Answer 3

В следующем примере вы должны использовать двойной указатель:

int main()
{
    struct node *head= NULL;
    createList (&head);
    //...
}

void createList(struct node **head)
{
    *head= malloc(sizeof(struct node));
}

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

Answer 4

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

К сожалению, хотя язык, описанный в K & R2, позволяет функции, которая принимает struct ANYTHING **ref, использовать его напрямую для обновления указателя на любой вид структура [поскольку указатели структур могут быть преобразованы в void* и обратно в единицах компиляции, которые не содержат определений для этих структур, все указатели на типы структур должны иметь одинаковое представление], и хотя все версии стандарта C будут разрешить компиляторам поддерживать такие конструкции, никакие версии Стандарта не запрещают компиляторам требовать, чтобы программисты перепрыгивали через обруч для выполнения sh таких вещей; авторы clang и g cc рассматривают отсутствие запрета как приглашение.

Следовательно, если кто-то хочет использовать такие конструкции способом, совместимым с -fstrict-aliasing диалектом, обработанным clang и g cc необходимо использовать memcpy для обновления указателей вместо использования присваиваний. В зависимости от используемой реализации это может дать или не дать код, который будет столь же эффективным, как простое присвоение. Если идти по этому маршруту, Я бы предложил:

#ifdef JUMP_THROUGH_SILLY_HURDLES_FOR_CLANG_AND_GCC
memcpy(origRef, &newPointerValue, sizeof newPointerValue);
#else
*((STRUCT ANYTHING**)origRef) = newPointerValue;
#endif

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