Связанный список имеет другое поведение для аналогичного назначения указателя - PullRequest
Новая
       65

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

0 голосов
/ 06 апреля 2020

Я пишу код для удаления узла из связанного списка, когда дается только указатель на узел, а головной узел не дается 

/*
struct Node {
  int data;
  struct Node *next;
  Node(int x) {
    data = x;
    next = NULL;
  }
}*head;
*/

// This function should delete node from linked list. The function
// may assume that node exists in linked list and is not last node
// node: reference to the node which is to be deleted
void deleteNode(Node *node)
{
        node=(node->next);
}

не удаляет существующий указатель в списке , но, 

/*
struct Node {
  int data;
  struct Node *next;
  Node(int x) {
    data = x;
    next = NULL;
  }
}*head;
*/

// This function should delete node from linked list. The function
// may assume that node exists in linked list and is not last node
// node: reference to the node which is to be deleted
void deleteNode(Node *node)
{
        *node=*(node->next);
}

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

Почему? В чем разница между подходами?

Ответы [ 3 ]

0 голосов
/ 06 апреля 2020

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

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

0 голосов
/ 06 апреля 2020

давайте рассмотрим более простой пример с целыми числами вместо узлов: 

void Modify_1 (int *piVal, int *piNewVal)
 {  
    //piVal has adresse of i passed as argument 

     // similar to  node = (node->next);    
     piVal = piNewVal;  // This change just the VALUE of the pointer passed as argument !  


    //piVal has adresse of j now
 }

void Modify_2 (int *piVal)
{
    // similar to *node=*(node->next);
    *piVal = 0; // This change de content of pointer 
}

int main ()
{
    int i = 3;
    int j = 5;

    Modify_1 (&i, &j);
    cout << i << endl; // This print 3 !

    Modify_2 (&i);
    cout << i << endl; // This print 0

    return 0;
}

piVal - это pointer, который содержит i адрес VALUE. Пример: 0x00bcfdb4
Этот адрес передается как значение (0x00bcfdb4), если вы хотите функционировать.
Пока вы не пишете *piVal, вы не собираетесь изменять указанный контент, а только ЗНАЧЕНИЕ адреса.

Если вы хотите изменить указатель, вам нужно **int (в вашем случае **node) 

void Modify_3 (int **piVal, int *piNewVal)
{
   *piVal = piNewVal;   // this change de pointer adresse
}  

int main ()
{
    int x = 5;
    int *pi = &x;
    Modify_3 (&pi, &x);

    cout << *pi << endl; // This print 5  
}
0 голосов
/ 06 апреля 2020

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

Это так же, как 

void f(int x) { x = 1000; }

int main()
{
    int x = 0;
    f(x);
    std::cout << x << std::endl;
}

будет печатать 0, а не 1000.

Таким образом, ваша первая попытка ничего не меняет и не имеет видимого эффекта.

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

Вам нужно что-то вроде этого: 

void deleteNode(Node *node)
{
    Node* old = node->next;
    *node = *(node->next);
    delete old;
}

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

...