Преобразование из одного в круговой связанный список - PullRequest
Новая
       39

Преобразование из одного в круговой связанный список

0 голосов
/ 09 марта 2011

Вот ссылка на код, который я написал для кругового связанного списка.Код также вставлен ниже.

typedef struct node
{
    int value;
    struct node *next;
}mynode;

mynode *head, *tail, *temp,*sp,*fp;

void add(int value); 
void iterative_reverse();
void print_list();
void findcycle();

int main()
{
    head=(mynode *)0;
    add(1);
    add(2);
    add(3);
    //print_list();
    findcycle();
    return(0);
}

void add(int value)
{
    temp = (mynode *) malloc(sizeof(struct node));
    temp->value=value;
    temp->next=(mynode *)0;
    if(head==(mynode *)0)
    {
        head=temp;
        tail=temp;
    }
    else
    {
        tail->next=temp;
        tail=temp;
        tail->next=head;
        temp->next=head;
    }
}

void findcycle()
{
    if (head == NULL || head->next == NULL)
        printf("null");
    sp=head;
    fp=head->next;
    while (fp != NULL && fp->next != NULL)
    {
        if ((fp == sp) || (fp->next == sp))
                printf("Cycle");
        sp = sp->next;
        fp = fp->next->next;
    }
    printf("Not a Cycle");
}

void print_list()
{
    for(temp=head; temp!=tail; temp=temp->next)
        printf("[%d]->",(temp->value));
}

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

Большое спасибо.

Ответы [ 2 ]

1 голос
/ 09 марта 2011

Это выглядит неправильно: 

tail->next=temp;
tail=temp;
tail->next=head;
temp->next=head;

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

tail->next=temp;
temp->next=head;
tail=temp;

В любом случае, это небольшая ошибка: только избыточное назначение.

Здесь действительно серьезные проблемы: 

void findcycle()
{
if (head == NULL || head->next == NULL)
            printf("null");
sp=head;
fp=head->next;
while (fp != NULL && fp->next != NULL)
 {
        if ((fp == sp) || (fp->next == sp))
                printf("Cycle");
        sp = sp->next;
        fp = fp->next->next;
 }
printf("Not a Cycle");
}

Прежде всего, каковыты пытаешься сделать?Это не ясно, поэтому нелегко предложить вам, как это исправить;во всяком случае, наиболее очевидная ошибка заключается в том, что если список на самом деле является круглым, то цикл будет продолжаться вечно, поскольку не может быть никакого условия выхода (ни один из указателей никогда не будетNULL).

0 голосов
/ 09 марта 2011

Когда findcycle находит цикл, он не выходит: он просто продолжает идти. (Аналогично, когда он получает список с 0 или 1 элементом.) Я не гарантирую, что это единственная ошибка в вашем коде, но этого достаточно, чтобы он не работал.

...