Указатели на указатели: разбиение связанного списка

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

void partitionList(lnode<int> *& head, int val) {
lnode<int> * front = nullptr;
lnode<int> * back = nullptr;
lnode<int> * curr = head;

while (curr) {
lnode<int> * next = curr->next;
if (curr->data < val) {
curr->next = front;
front = curr;
} else {
curr->next = back;
back = curr;
}
curr = next;
}

curr = front;
while (curr->next) {
curr = curr->next;
}
curr->next = back;
head = front;
}

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

void partitionList(lnode<int> ** head, int val) {
lnode<int> * front = nullptr;
lnode<int> * back = nullptr;
lnode<int> ** curr = head;

while (*curr) {
lnode<int> * entry = *curr;

std::cout << (*curr)->data << std::endl; // On second loop, prints 2
std::cout << entry->data << std::endl; // On second loop, prints 2

lnode<int> * next = entry->next; // This assignment does something

std::cout << entry->data << std::endl; // On second loop, prints 2
std::cout << (*curr)->data << std::endl; // On second loop, prints 3!

if ((*curr)->data < val) {
(*curr)->next = front;
front = *curr;
} else {
(*curr)->next = back;
back = *curr;
}
curr = &next;
}

*curr = front;
while ((*curr)->next) {
(*curr) = (*curr)->next;
}
(*curr)->next = back;
head = &front;
}

int main() {
lnode<int> * tail = new lnode<int>(8, nullptr);
lnode<int> * seven = new lnode<int>(7, tail);
lnode<int> * six = new lnode<int>(6, seven);
lnode<int> * five = new lnode<int>(5, six);
lnode<int> * four = new lnode<int>(4, five);
lnode<int> * three = new lnode<int>(3, four);
lnode<int> * two = new lnode<int>(2, three);
lnode<int> * head = new lnode<int>(1, two);

partitionList(&head, 6);
}

В первом цикле все четыре строки отладочной печати располагаются в верхней части цикла while с печатью «1». Однако, во втором цикле они печатают «2», «2», «2», «3»?

Кто-нибудь может объяснить, что происходит? Как правильно использовать двойной указатель вместо ссылки на указатель?

Спасибо!

1

Решение

void partitionList(lnode<int> *& head, int val) {
...
head = front; // <= head is modified
}

но здесь нет

void partitionList(lnode<int> ** head, int val) {
...
head = &front; // try it with *head = front
}

и если вы хотите быструю замену для этого

void partitionList(lnode<int> *& head, int val) {
...
lnode<int> * curr = head;

просто напишите это:

void partitionList(lnode<int> ** head, int val) {
...
lnode<int> * curr = *head;

Почему вы изменили *cur в **cur?

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]