Проблема создания односвязного списка без использования функции - PullRequest
Новая
       26

Проблема создания односвязного списка без использования функции

1 голос
/ 25 мая 2020 
//linked_list_1

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

struct list
{
    int data;
    struct list *link;
};

int main()
{
    struct list *ll=NULL, *tp=NULL;
    int n=3, i;

    ll=(struct list *)malloc(sizeof(struct list));

    scanf("%d",&ll->data);

    for(i=1; i<n; i++)
    {
        tp=(struct list *)malloc(sizeof(struct list));
        scanf("%d",&tp->data);
        ll->link=tp;
        ll=ll->link;
    }

    ll->link=NULL;

    while(ll)
    {
        printf("\n%d",ll->data);
        ll=ll->link;
    }
}

//linked_list_2

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

struct list
{
    int data;
    struct list *link;
};

void linked_list(struct list *,int);

int main()
{
    struct list *ll=NULL;
    int n=3;

    ll=(struct list *)malloc(sizeof(struct list));

    linked_list(ll,n);


    while(ll)
    {
        printf("\n%d",ll->data);
        ll=ll->link;
    }
}

void linked_list(struct list *kk, int n)
{
    struct list *tp=NULL;
    int i;
    scanf("%d",&kk->data);
    for(i=1; i<n; i++)
    {
        tp=(struct list *)malloc(sizeof(struct list));
        scanf("%d",&tp->data);
        kk->link=tp;
        kk=kk->link;
    }
    kk->link=NULL;
}

Обе программы одинаковы, вторая программа - это создание связанного списка с использованием функции: void linked_list(struct list *kk, int n) Первая программа также создает связанный список, но без какой-либо функции. Вторая программа работает правильно, но первая программа работает некорректно.

Если входы 2 5 4 для обеих программ, выход второй программы - 2 5 4, но выход первой программы - только 4.

Почему первая программа работает некорректно? В чем причина?

1 Ответ

1 голос
/ 25 мая 2020

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

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

ll=ll->link; //Wrong!

, пока это не станет абсолютно необходимым. Это приведет к усеченному связанному списку, и вы потеряете свои узлы.

В идеале ваш код должен быть примерно таким: 

ll=(struct list *)malloc(sizeof(struct list));
tp = ll; //Align the temporary pointer with the head of the linked list.
scanf("%d",&tp->data);

for(i=1; i<n; i++)
{
    //Allocate memory to the link of the temporary pointer since it is also a type of struct list.
    tp->link=(struct list *)malloc(sizeof(struct list)); 
    scanf("%d",&tp->link->data);
    tp = tp->link; //Move only the temporary pointer.
}

tp->link=NULL; //Finally assign NULL when done taking inputs.

Обратите внимание, я использую только временный указатель для выполнения все.

Причина, по которой работает вторая программа, заключается в том, что вы передаете адрес указателя заголовка функции, которую вы используете для построения связанного списка. Теперь эта функция получает копию адреса в kk, который является начальным адресом связанного списка, и строит связанный список, используя его. Но вернемся к main() указатель ll по-прежнему сохраняет исходный адрес, по которому вы изначально выделили память. Следовательно, после создания связанного списка, когда вы вернетесь в main() для его печати, вы начнете с фактического заголовка связанного списка, который все еще будет удерживаться ll, и вы сможете распечатать весь связанный список.

Но здесь все еще есть тот же недостаток, о котором я упоминал ранее. Вы перемещаете заголовок связанного списка во время его печати (например, ll). 

while(ll)
{
    printf("\n%d",ll->data);
    ll=ll->link; //This is wrong!
}

Итак, после того, как вы закончите печать связанного списка, ваша голова связанного списка теперь имеет значение NULL. Поэтому, если вы хотите что-то сделать с фактическим связанным списком после его печати, это невозможно, поскольку вы сделали заголовок NULL. Итак, снова решение - использовать временный указатель, выровнять его с заголовком связанного списка, а затем использовать его для печати связанного списка. Примерно так: 

struct list *tp = ll;
while(tp)
{
    printf("\n%d",tp->data);
    tp=tp->link;
}
...