Понимание рекурсивной функции в связанном списке C - PullRequest
Новая
       26

Понимание рекурсивной функции в связанном списке C

0 голосов
/ 03 декабря 2018

Давайте предположим, что я пишу программу, которая имитирует игру Dominoes, поэтому я хотел бы определить структуру следующим образом: 

typedef struct nodo { 
    int casella1;
    int casella2;
    struct nodo *next;
} Tessera;
typedef Tessera *Lista;

И затем после некоторого ввода в случайном порядке, который заканчивается, когда числоза пределами диапазона 0 <= x <= 6, я хотел бы удалить возможные дубликаты, которые не соответствуют правилам домино.Число <code>casella2 всегда должно следовать за тем же номером в ->next->casella1, используя рекурсивную функцию, которая выглядит так: 

void legale(Lista *head) {

    Lista aux,aus = *head;

    if(aus->next == NULL) {
      return;
    }

    else if(aus->casella2 == aus->next->casella1)   {
      legale(&(aus->next));
    }
    else {
      aux = aus->next;
      aus->next = aus->next->next;  
      free(aux);
    }
}

Но, например, последовательность "1 2, 2 3, 34, 4 5, 5 4, 6 2, 7 "дает" 1 2, 2 3, 3 4, 4 5,6 2 ", поэтому не удаляет 6,2, как следует.

Iдумаю, что способ, которым я удалил указатель, является правильным, так почему же эта функция неверна?

Код выглядит так: 

#include<stdio.h>
#include<stdlib.h>
typedef struct nodo { 
    int casella1;
    int casella2;
    struct nodo *next;
    }Tessera;
typedef Tessera *Lista;

void stampa(Lista *head) {

    Lista ausil = *head;

    while(ausil != NULL) {
    printf("%d\t%d\n",ausil->casella1,ausil->casella2);
    ausil = ausil->next;
    }
}

void legale(Lista *head) {

    Lista aux,aus = *head;

    if(aus->next == NULL) {
    return;
}

    else if(aus->casella2 == aus->next->casella1)   {
    legale(&(aus->next));
}
    else {
    aux = aus->next;
    aus->next = aus->next->next;    
    free(aux);
}


}

void write (Lista *head) {
    Lista corr,aux,aus;
    int x,y;
    scanf("%d%d",&x,&y);
    aus = *head;

    while((x >= 0 && x <= 6) && (y >= 0 && y <= 6)) {

    if(aus == NULL) {

    aus = malloc(sizeof(Tessera));
    aus->casella1 = x;  
    aus->casella2 = y;
    aus->next = NULL;
    *head = aus;
}
    else {
    aux = *head;

    corr = malloc(sizeof(Tessera));
    corr->casella1 = x;
    corr->casella2 = y;
    corr->next = aux;
    *head = corr;
}
    scanf("%d%d",&x,&y);
    }

}

int main() {
    Lista Lista1 = NULL;
    write(&Lista1);
    legale(&Lista1);
    stampa(&Lista1);
return 0;
}

1 Ответ

0 голосов
/ 04 декабря 2018

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

else {
  aux = aus->next;
  aus->next = aus->next->next;  
  free(aux);
}

Если вы не выполняете рекурсию, вы останавливаетесь после первого удаления.

Также по предосторожности, перед проверкой aus->next == NULL следует проверить, aus == NULL, чтобы он не ломался, если вы передали ему пустой список.

РЕДАКТИРОВАТЬ

Вы создаете свой связанный список в обратном порядке, когда читаете его.

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

...