Связанные списки/linked lists

Рейтинг: 0Ответов: 1Опубликовано: 27.11.2014

Изучаю сейчас самостоятельно связанные списки С. Кто-нибудь может сказать, почему, несмотря на то, что в последнем цикле while я вывожу лишь l1, l2 каким-то образом тоже выводится?

  #include <stdio.h>
#include <stdlib.h>
//dummy=head
struct node {
    int value;
    struct node *next;
    };

struct node *head;
struct node *tail;

struct node *init(void) {
    head=(struct node *) malloc(sizeof *head);
    tail=(struct node *) malloc(sizeof *head);
    head->next = tail; tail->next = tail;
    return head;
}

struct node *append(int v) {
    struct node *ptr;
    struct node *t;
    ptr=head;
    while (ptr->next != tail) ptr = ptr->next;
    t=(struct node *) malloc(sizeof *t);

    t->value=v;
    t->next = tail;
    ptr->next = t;
    return ptr;
}

struct node *insert(int v, struct node *ptr) {
    struct node *t;
    t=(struct node *) malloc(sizeof *t);
    ptr->value=v;
    t->value=v;
    t->next = tail;
    ptr->next = t;
    return ptr;
    }

void delete(struct node *ptr) {
    struct node *t;
    t = ptr->next;
    ptr->next = ptr->next->next;
    free(t);
    }

int main () {
struct node *l1, *l2;

int n, v;
scanf("%d", &n);
l1=init();
l2=init();
int i=0;
while(i<n){
        scanf("%d", &v);
l1=append(v);
i++;}

l1=l1->next;
scanf("%d", &v);
l1=insert(v, l1);
delete(l1);
i=0;
while(i<n){
        scanf("%d", &v);
l2=append(v);
i++;
}

l2=l2->next;
scanf("%d", &v);
l2=insert(v, l2);
delete(l2);

l1=head->next;
while (l1 != tail) {
    printf("%d\n",l1->value);
    l1 = l1->next;
    }

return 0;
}

Ответы

▲ 1

Потому что после второго вызова init() переменные head и tail отражают список l2 (даже когда Вы вызываете append(l1) и т.п.).


Кстати, после delete у Вас идет обращение к данным в уже освобожденной памяти. Это неправильно и поведение (упадет или нет программа) зависит от версии аллокатора памяти.


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

Обновление

@dropitlikeitshot, при чем тут какие-то dummy node?

Насколько я вижу код, Вы пытаетесь делать 2 списка (в main) l1 и l2, но для обеих оперируете в своих функциях одними и теми же глобальными head и tail.

Вот тут то у Вас все и перемешивается. Выбросьте их.

Сделайте структуру, содержащую для каждого списка его head и tail. И вот указатель на такую структуру (у Вас это будут 2 списка l1 и l2) и передавайте в функции, которые манипулируют списками.


Сейчас Вы просто сами хотите изобрести общие алгоритмы для работы со списками? Увлекательное занятие.