Использование одиночных и двойных указателей в связанных списках, реализованных в C

Я писал этот код для добавления элемента в конец связанного списка:

struct node{
    int info;
    struct node* link;
};

void append ( struct node **q, int num )  
{

struct node *temp, *r ;

if ( *q == NULL )       // if the list is empty, create first node
{
    temp = (struct node*) malloc ( sizeof ( struct node ) ) ;
    temp -> info = num ;
    temp -> link = NULL ;
    *q = temp ;        
}
else{
    temp = *q ;         

    /* go to last node */
    while ( temp -> link != NULL )
        temp = temp -> link ;

    /* add node at the end */
    r = (struct node *)malloc ( sizeof ( struct node ) ) ;
    r -> info = num ;
    r -> link = NULL ;
    temp -> link = r ;
}
}

и я вызываю функцию добавления следующим образом: append(&list, 10);, где list — указатель на связанный список

Этот код работает, но если я использую одиночный указатель в функции добавления (используя *q вместо **q) и вношу соответствующие изменения (как это делается ниже, а также когда я его вызываю), он не работает. Работа. Что не так с кодом ниже?:

void append ( struct node *q, int num )  
{

struct node *temp, *r ;

if ( q == NULL )       // if the list is empty, create first node
{
    temp = (struct node*) malloc ( sizeof ( struct node ) ) ;
    temp -> info = num ;
    temp -> link = NULL ;
    q = temp ;        
}
else{
    temp = q ;         

    /* go to last node */
    while ( temp -> link != NULL )
        temp = temp -> link ;

    /* add node at the end */
    r = (struct node *)malloc ( sizeof ( struct node ) ) ;
    r -> info = num ;
    r -> link = NULL ;
    temp -> link = r ;
}
}

c pointers linked-list double-pointer
person Jatin    schedule 06.04.2012    source источник
comment
потому что C и C++ тесно связаны, и я предполагал, что кто-то со знанием C++ сможет мне здесь помочь.   -  person Jatin    schedule 06.04.2012
comment
Между прочим, это плохой подход к добавлению элемента в список, потому что время выполнения увеличивается линейно с количеством элементов. Традиционный подход заключается в сохранении указателя на оба конца списка, что позволяет выполнять добавление в постоянное время.   -  person Oliver Charlesworth    schedule 06.04.2012

Ответы (2)


arrow_upward
3
arrow_downward

Потому что во втором примере q — это копия указателя, переданного вызывающей стороной. Исходный указатель вызывающего объекта никогда не изменяется.

person Oliver Charlesworth    schedule 06.04.2012
comment
Но list — это указатель на узел. Итак, он хранит адрес. Итак, когда я звоню append(list, 10);, я передаю адрес, поэтому не должно ли это изменить исходный связанный список. - person Jatin; 06.04.2012
comment
@Jatin: не для помеченной части кода. Если список пуст, создайте первый узел. - person Oliver Charlesworth; 06.04.2012
comment
Итак, если у меня есть хотя бы 1 элемент в списке, то второй код будет работать, верно? - person Jatin; 06.04.2012
comment
и @Oli, не могли бы вы уточнить свой последний комментарий? - person Jatin; 06.04.2012
comment
@Jatin: раздел if изменяет значение q, но это не будет отражено в значении, которое передает вызывающая сторона (потому что это копия). Однако секция else этого не делает, так что эта часть, вероятно, работает нормально. - person Oliver Charlesworth; 06.04.2012

arrow_upward
1
arrow_downward

В вашем первом фрагменте (что верно) вы делаете слишком много.

void append ( struct node **q, int num )  
{

struct node *new ;

    /* go to last node */
    for ( ; *q; q = &(*q)->link ) {;}

    /* add node at the end */
    new = malloc ( sizeof *new );
    if (!new) { barf_now(); return; }

    new->info = num ;
    new->link = NULL ;
    *q = new; ;
    }
}

Основная идея такова: вы хотите добавить в конец списка; тебе нужно:

  • найти первый указатель NULL
  • установите его значение на значение нового указателя

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

person wildplasser    schedule 06.04.2012