Зачем использовать двойной указатель при вставке узла в отсортированном порядке в списке ссылок?

Question

typedef struct node node;
struct node {
    int data;
    node *next; 
};

int insert_asc(node **phead, int data) {
    node **traser;
    node *newnode = malloc(sizeof(node));
    if (newnode == 0)
        return 0;
    newnode->data = data;

    for (traser = phead; *traser != 0; traser = &(*traser)->next)
        if (data <= (*traser)->data)
            break;

    newnode->next = *traser;
    *traser = newnode;
    return 1;
}

Запутанная часть для меня, когда вы разыменовываете двойной указатель traser. почему (*traser)->next содержит адрес следующего узла? и что именно здесь *traser?

Answer 1

Двойные указатели используются в размещенном коде для двух отдельных целей:

• node **phead: заголовок списка передается по ссылке, поэтому его можно обновить с помощью insert_ascесли новый узел должен быть вставлен в начало списка.Передача по ссылке невозможна в C, идиоматический способ ее достижения - передать указатель на значение, которое будет обновлено функцией, следовательно, двойной указатель phead.

• node **traser: Чтобы избежать особого случая пустого списка и вставки в начало списка, программист использует указатель, чтобы отслеживать место для вставки нового узла.traser сначала указывает на заголовок списка, который в данном случае является значением phead и обновляется, чтобы указывать на связь между узлами, членом next текущего узла, когда определяется, что новыйузел должен быть вставлен после текущего.Это элегантный способ осуществить вставку без особого случая.C позволяет благодаря указателям, это не возможно ни в java, ни в javascript, потому что эти языки не имеют обобщенных указателей.

Обратите внимание, однако, что код можно сделать более читабельным при использовании NULLвместо 0 при сравнении указателей:

typedef struct node node;
struct node {
    int data;
    node *next; 
};

int insert_asc(node **phead, int data) {
    node **traser;
    node *newnode = malloc(sizeof(node));
    if (newnode == NULL)
        return 0;
    newnode->data = data;

    for (traser = phead; *traser != NULL; traser = &(*traser)->next) {
        if (data <= (*traser)->data)
            break;
    }
    newnode->next = *traser;
    *traser = newnode;
    return 1;
}

Обратите также внимание, что новые узлы с заданным значением data вставляются перед узлами с таким же значением data.Это не имеет значения в этом случае и может быть немного быстрее для списков с большим количеством дубликатов, но если бы полезная нагрузка была более сложной, этот метод вставки реализовал бы нестабильную сортировку, тогда как использование < вместо <=сделало бы сортировку стабильной.

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

int insert_asc(node **phead, int data) {
    node *cur;
    node *newnode = malloc(sizeof(node));
    if (newnode == NULL)
        return 0;
    newnode->data = data;

    cur = *phead;
    if (cur == NULL || cur->next == NULL) {
       newnode->next = cur;
       *phead = newnode;
    } else {
        while (cur->next != NULL && data < cur->next->data)
            cur = cur->next;
        newnode->next = cur->next;
        cur->next = newnode;
    }
    return 1;
}

Answer 2

Вы используете двойной указатель для отслеживания заголовка вашего списка.

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

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

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