(C++)再帰的構造体を使ったリストの処理

[アトラス]

学校の課題です。

あらかじめ与えられた関数をつかって、リストの中身を反転させる関数reverseを作れという問題です。

とりあえず反転には成功しているようなのですが、

その後リストに数字を追加しようとしても何も追加されていない現象が起きて困っています。（削除するのは問題なし）

どこが原因なのでしょうか？

アドバイスよろしくお願いします。

==========================

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

typedef struct list{    //再帰的構造体
    int data;
    struct list *next;
} LIST;

LIST *head,*tail;    //head:リストの先頭 tail:リストの末尾

int non=0;    //指定の数字が存在するかのフラグ


//リストの中身を表示
void display_list(LIST *p) {

    if(p == NULL)
        printf("\nからっぽ！\n\n");
    else{
        printf("\n現在のリストの中身は\n\n");

        printf("( %d ", p->data);
        p = p->next;
        while(p != NULL){
            printf(", %d ", p->data);
            p = p->next;
        }
        printf(")\n\nです\n\n");
    }
    
}

//新規リスト作成
LIST *new_list(int x, LIST *y){

    LIST *c = (LIST *)malloc(sizeof(LIST));
    c->data = x;
    c->next = y;
    return c;

}

//リストに数字を追加
void add_list(int x){
    LIST *p;
    p = new_list(x, NULL);

    if(head == NULL)
        head = tail = p;
    else{
        tail->next = p;
        tail = p;
    }
}

//リストから数字を削除
void delete_list(int x){
    LIST *p, *q;
    q = p = head;

    while(p != NULL && x != p->data){
        q = p;
        p = p->next;
    }

    if (p == NULL){
        non=1;
        return;
    }

    if (q == p) head = head->next;
    else q->next = p->next;

    free(p);
}

//２つのリストを結合
LIST *append(LIST *list1, LIST *list2){
    if (list1 == NULL){
        return list2;
    }else{
        return new_list(list1->data , append(list1->next,list2));
    }
}

//リストを反転
LIST *reverse(LIST *list){
    if(list==NULL) return list;
    else return append(reverse(list->next) , new_list(list->data,NULL));
}


void main(){
    int a,add,del;

    while(1){

        printf("\n\n    ┌--------------------┐\n");
        printf("    │                    │\n");
        printf("    │     コマンド       │\n");
        printf("    │                    │\n");
        printf("    │  0 : リストの表示  │\n");
        printf("    │  1 : リストの追加  │\n");
        printf("    │  2 : リストの削除  │\n");
        printf("    │  3 : リストの反転  │\n");
        printf("    │                    │\n");
        printf("    └--------------------┘\n\nコマンド>");

        scanf("%d",&a);

        if(a==0){
            display_list(head);

        }else if(a==1){

            printf("\n追加する数字は？\n\n");
            scanf("%d",&add);
            add_list(add);
            printf("\n%d を追加しました！",add);

        }else if(a==2){

            printf("\n削除する数字は？\n\n");
            scanf("%d",&del);
            delete_list(del);
            if(non==0){
                printf("\n%d を削除しました！\n\n",del);
            }else if(non==1){
                printf("\nその数字はリストに存在しません！");
                non=0;
            }

        }else if(a==3){
            if(head!=NULL) tail=new_list(head->data,NULL);
            head=reverse(head);
            printf("\n反転が完了しました");
        }

    }

}

[non]

あなたの逆順への考え方が、さっぱりわかりません。

まず、mainの最初でhead=NULL;はやっておきましょう。（自動的にNULLが入っているとしても）


逆順にした後、追加ができないのは、tailが最後尾を指していないからです。
とりあえず動けばいいのなら、head=reverse(head);の行の後に
for(tail=head;tail->next!=NULL;tail=tail->next){}
この1行を追加します。
しかし、これでは、mallocされた、メモリがまったく解放されてません。
このような、プログラムは作るべきではありません。

逆順にするのに、再帰呼び出しを使わなければいけないのでしょうか？
指定されていないのなら、再帰呼び出しにしない方が、いいと思います。
どこまでが、課題として指定されているのか明確にしてください。

[アトラス]

回答ありがとうございます。

逆順の作り方が根本的に違っていたみたいですね。

やり方の指定は特にありません。再帰について習った授業で出された課題なので、てっきりこれを使うのかと勘違いしていました。

tailをきちんと設定して、再起を使わずに書きなおしてみました。

今回は問題なく動きましたが、これでＯＫでしょうか。

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

typedef struct list{    //再帰的構造体
    int data;
    struct list *next;
} LIST;

LIST *head,*tail;    //head:リストの先頭 tail:リストの末尾

int non=0;    //指定の数字が存在するかのフラグ


//リストの中身を表示
void display_list(LIST *p) {

    if(p == NULL)
        printf("\nからっぽ！\n\n");
    else{
        printf("\n現在のリストの中身は\n\n");

        printf("( %d ", p->data);
        p = p->next;
        while(p != NULL){
            printf(", %d ", p->data);
            p = p->next;
        }
        printf(")\n\nです\n\n");
    }
    
}

//新規リスト作成
LIST *new_list(int x, LIST *y){

    LIST *c = (LIST *)malloc(sizeof(LIST));
    c->data = x;
    c->next = y;
    return c;

}

//リストに数字を追加
void add_list(int x){
    LIST *p;
    p = new_list(x, NULL);

    if(head == NULL)
        head = tail = p;
    else{
        tail->next = p;
        tail = p;
    }
}

//リストから数字を削除
void delete_list(int x){
    LIST *p, *q;
    q = p = head;

    while(p != NULL && x != p->data){
        q = p;
        p = p->next;
    }

    if (p == NULL){    //見つからなかった場合
        non=1;
        return;
    }

    if (q == p) head = head->next;    //先頭にあった場合
    else q->next = p->next;    //それ以外:消えた部分を連結

    free(p);
}

//リストを反転
LIST *reverse(LIST *list){
    LIST *p;
    
    if(list==NULL) return list;

    p=new_list(list->data,NULL);
    tail=p;

    while(list->next!=NULL){

        list=list->next;
        p=new_list(list->data,p);

    }

    return p;
}


void main(){
    int a,add,del;
    head=NULL;
    tail=NULL;

    while(1){

        printf("\n\n    ┌--------------------┐\n");
        printf("    │                    │\n");
        printf("    │     コマンド       │\n");
        printf("    │                    │\n");
        printf("    │  0 : リストの表示  │\n");
        printf("    │  1 : リストの追加  │\n");
        printf("    │  2 : リストの削除  │\n");
        printf("    │  3 : リストの反転  │\n");
        printf("    │                    │\n");
        printf("    └--------------------┘\n\nコマンド>");

        scanf("%d",&a);

        if(a==0){
            display_list(head);

        }else if(a==1){

            printf("\n追加する数字は？\n\n");
            scanf("%d",&add);
            add_list(add);
            printf("\n%d を追加しました！",add);

        }else if(a==2){

            printf("\n削除する数字は？\n\n");
            scanf("%d",&del);
            delete_list(del);
            if(non==0){
                printf("\n%d を削除しました！\n\n",del);
            }else if(non==1){
                printf("\nその数字はリストに存在しません！");
                non=0;
            }

        }else if(a==3){
            head=reverse(head);
            printf("\n反転が完了しました");
        }

    }

}

[non]

新しいリストを作り直したのなら、古いリストのノードを
削除しなくてはいけません。

または、新しいノードを作らずに、繋ぎ換えだけをおこなうように
作るかのどちらかです。

[アトラス]

あぁ、削除しないとどんどんたまってしまいますね、気付いていませんでした(汗)

アドバイスありがとうございました！

おかげで完成させることができました。