простой связанный список не распечатывается - PullRequest
Новая
       4

простой связанный список не распечатывается

0 голосов
/ 29 мая 2018

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

#include <stdio.h>
#include <stdlib.h>

// typedef is used to give a data type a new name
typedef struct node * link ;// link is now type struct node pointer

/*
    typedef allows us to say "link ptr"
    instead of "struct node * ptr"
*/

struct node{
    int item ;// this is the data
    link next ;//same as struct node * next, next is a pointer
};

void printAll(link head); // print a linked list , starting at link head
void addFirst(link ptr, int val ); // add a node with given value to a list
link removeLast(link ptr); // removes and returns the last element in the link

//prints the link
void printAll(link head){
    link ptr = head;
    printf("\nPrinting Linked List:\n");
    while(ptr != NULL){
        printf(" %d ", (*ptr).item);
        ptr = (*ptr).next;// same as ptr->next
    }
    printf("\n");
}

//adds to the head of the link
void addFirst(link ptr, int val ){
    link tmp = malloc(sizeof(struct node));// allocates memory for the node
    tmp->item = val;
    tmp->next = ptr;
    ptr = tmp;
}

// testing
int main(void) {
    link head = NULL;// same as struct node * head, head is a pointer type

    //populating list
    for(int i = 0; i<3; i++){
        addFirst(head, i);
    }

    printAll(head);

    return 0;
}

вывод:

Печать связанного списка:

Процесс вернул 0(0x0) время выполнения: 0,059 с

Нажмите любую клавишу для продолжения

Ответы [ 2 ]

0 голосов
/ 29 мая 2018

В цикле for 

for(int i = 0; i<3; i++){
    addFirst(head, i);
}

вы создаете группу указателей, которые все указывают на NULL.head никогда не меняется, так как сам указатель передается "по значению".Например, head копируется, и все модификации самого указателя в addFirst не видны снаружи.

Это то же самое, что, скажем, int.Представь себе void foo(int x);.Что бы эта функция ни делала с x, снаружи не видно.

Однако изменения в памяти, на которые link ptr указывает, конечно, видны.

Например, эта строка ничего не делает: 

   tmp->next = ptr;
   ptr = tmp;      <=== this line
}

Вы можете исправить это несколькими способами.Один - вернуть новый узел из addFirst, а другой - сделать link ptr указателем на указатель: link *ptr.Так как в этом случае вы хотите изменить значение указателя (не значение pointee): 

//link *ptr here a pointer to pointer
void addFirst(link * ptr, int val ){
    link tmp = malloc(sizeof(struct node));// allocates memory for the node
    tmp->item = val;
    tmp->next = *ptr; //<<changed
    *ptr = tmp;    //<<changed
}

Не забудьте также обновить объявление выше.И вызов: 

void addFirst(link * ptr, int val ); // add a node with given value to a list

...
for(int i = 0; i<3; i++){
    addFirst(&head, i);
}

Затем этот код выдает: 

Printing Linked List:
 2  1  0

Добавлено: Важно понимать, что работа со связанным списком требует работы с двумя различными типамиданных.

Первый - struct node, и вы передаете данные этого типа, используя link s.

Второй - head.Это указатель на самый первый узел.Когда вы хотите изменить голову, вы обнаружите, что это не «узел».Это что-то еще.Это «имя» для первого узла в списке.Это имя само по себе является указателем на узел.Посмотрите, как расположение памяти для head отличается от самого списка. Кстати, 

head[8 bytes]->node1[16 bytes]->node2[16 bytes]->...->nodek[16 bytes]->NULL;

- единственное, что здесь имеет лексическое имя - head.Все узлы не имеют имен и доступны через синтаксис node->next.

Здесь вы также можете представить еще один указатель, link last, который будет указывать на nodek.Опять же, это будет иметь разную структуру памяти от самих узловИ если вы хотите изменить это в функции, вам нужно будет перейти к указателю на функцию (например, от указателя к указателю).

Указатель и данные, на которые он указывает, - разные вещи.В вашем уме вы должны разделить их.Указатель похож на int или float.Передается «по значению» в функции.Да link ptr уже указатель, и это позволяет вам обновлять данные, на которые он указывает.Однако сам указатель передается по значению, и обновления указателя (в вашем случае ptr=tmp) не видны снаружи.

(*ptr).next=xxx будет видно, конечно, потому что данные обновляются (не указатель).Это означает, что вам нужно сделать один дополнительный шаг - сделать изменения в вашем указателе видимыми вне функции, например, преобразовать сам указатель (head) в данные для другого указателя, например, использовать struct node **ptr (первая звездочка здесь говорит, что это указатель наузел, а вторая звезда преобразует этот указатель в данные для другого указателя.

0 голосов
/ 29 мая 2018

Это потому, что вы передаете нулевой указатель на вашу функцию, и условие выхода из цикла состоит в том, чтобы этот указатель был нулевым, поэтому ничего не происходит.Ваша addFirst функция принимает значение указателя, но она не может изменить head, который вы объявили внутри main ().Чтобы изменить head, вам нужно передать указатель на ссылку, затем вы можете разыменовать этот указатель для доступа к вашему head и затем изменить его. 

void addFirst(link *ptr, int val ){
    link tmp = malloc(sizeof(struct node));// allocates memory for the node
    tmp->item = val;
    tmp->next = *ptr;
    *ptr = tmp;
}

Теперь вы можете изменить указатель головы.Просто не забудьте передать адрес при вызове функции.addFirst(&head,i)

...