-1

[/////////]コメント部のリストを昇順にソートするプログラムなのですが、coutでデバッグすると文字が無限に出てしまうので無限ループしてると思われるのですが。どこが原因なのかわかりません。初学者のため紙に変数の動きなど書きましたがやはりループは抜けるとしか思われないため
解決に困っています。何が原因か教えてくれますでしょうか?(書き写したコードです。)

        #include <iostream>
        #include <string>
        #include "conio.h"
        using namespace std;


        typedef struct list {
            list *next;
            list *prev;

            int weight;
            int height;
            string name;
        }st_list;

        enum mood{
            e_add = 1,
            e_delete,
        };
        enum select {
            e_yes = 1,
            e_no,
        };

        int select_mood()//Add deleteを選択する関数
        {
             int no = 0;
            do {
                cout << "モード選択 [Add 1 / Delete 0 / sort 2 ]: ";
                cin >> no;
                if (no != 1 && no != 0 && no != 2) {
                    cout << "1,0,2を入力してください。\n";
                }
            } while (no != 1 && no != 0 && no != 2);

            return no;
        }

        int select_try()//続けるかどうかを選択する関数
        {
            int no = 0;
            do {
                cout << "続けますか?[YES 1 / NO 0]: ";
                cin >> no;
                if (no != 1 && no != 0) {
                    cout << "1,0を入力してください。\n";
                }
            } while (no != 1 && no != 0);

            return no;
        }

        void view(list *start) {/*リストを一挙に表示する関数*/

            if (start != NULL)
            {
                while (start != NULL)
                {
                    cout << "weight: " << start->weight << "\n";
                    cout << "height: " << start->height << "\n";
                    cout << "name: " << start->name << "\n";

                    start = start->next;
                }
            }
            else {
                cout << "リストがりません\n";
            }

        }

        int main() {
            st_list *data = NULL, *start = NULL, *t = NULL, *p = NULL;
            st_list *end = NULL;
            st_list *front = NULL;

            int no;

        do {
            do {
                cout << "モード選択 [Add 1 / Delete 0 / sort 2]: ";
                cin >> no;
                if (no != 1 && no != 0 && no != 2) {
                    cout << "1,0を入力してください。\n";
                }
            } while (no != 1 && no != 0 && no != 2);

            /*追加する*/
            if (no == 1)
            {
                data = new list;
                cout << "体重:";
                cin >> data->weight;
                cout << "身長:";
                cin >> data->height;
                cout << "名前:";
                cin >> data->name;
                data->next = NULL;
                data->prev = NULL;

                if (start == NULL) {
                    data->prev = NULL;
                    start = data;               
                    p = data;
                }
                else {
                    data->prev = p;
                    p->next = data;
                    p = data;
                }
                end = p;
            }

            /*削除する*/
            if (no == 0)
            {
                if (start == NULL)
                {
                    cout << "データがありません。\n";
                }
                else {

                p = NULL;
                view(start);
                cout << "削除するリストの名前を入力してください:";
                string name;
                cin >> name;
                data = start;

                    do {
                        if (strcmp(name.c_str(), data->name.c_str()) == 0)
                        {
                            if (p == NULL)
                            {

                                cout << "<debug 先頭の時>\n";
                                start = data->next;

                                if (start != NULL)
                                {
                                    cout << "<リストが一個で前と次がNULLの時>\n";
                                    start->prev = NULL;

                                }                           
                                cout << "選択したデータを削除しました。\n";
                                delete data;

                            }
                            else {                          
                                cout << "<debug 二回目以降>\n";  
                                if (data->next != NULL)
                                {
                                    t = data->next;
                                    p->next = t;
                                    t->prev = p;

                                    cout << "選択したリストを削除しました\n";
                                    delete data;
                                }
                                else
                                {
                                    p->next = NULL;
                                    end = p;

                                    cout << "選択してリストを削除しました\n";
                                    delete data;
                                }
                            }

                            break;
                        }
                        else 
                        {
                            p = data;
                            data = data->next;
                        }

                        if (data == NULL) /*一致するデータがないとき*/
                        {
                                cout << "一致するリスト名がありません。" << "[ " << name << " ]\n";
                        }
                    } while (data != NULL);

                    p = start;
                    if (p != NULL) {
                        while (p->next != NULL)
                        {
                            p = p->next;
                        }
                    }
                    end = p;
                }
            }

            ///////////////////////////////////////////////////////////////////////
            if (no == 2)//昇順にソートして表示(上から1,2,3)
            {

                if (p == NULL || start == NULL) {
                    cout << "リストがありません.\n";
                }
                    cout << "ソート部\n";
                    list *t,*n;
                    list *pprev, *nnext;
                    p = start;

                do{
                    //cout << "aaa\n";
                    n = p->next;            
                    if (p->height > n->height)
                    {
                        pprev = p->prev;
                        nnext = p->next;

                        if (pprev != NULL)
                        {
                            pprev->next = n;

                        }
                        n->prev = pprev;
                        n->next = p;




                        if (nnext != NULL) {
                            n->next = p;
                        }
                        else {
                            //nnext->prev = p;
                        }


                        p->next = nnext;
                        p->prev = n;


                        //if (n->prev == NULL) { start = n; }
                        if (!n->prev) { start = n; }

                        if (!p->next) { end = p; }
                        //if (p->next == NULL) { end = p; }

                        if (n->prev) { p = n->prev; }
                        else { p = n; }
                    }
                    else {
                        p = p->next;
                    }

                    //p = p->next;

                } while (p != NULL);

            }
        ///////////////////////////////////////////////////////////////////

            view(start);
        } while (select_try() == 1);
        cout << "終了します。\n";


            _getch();
            return 0;
        }

1 件の回答 1

0

双方向リストをソートするのが難題すぎると思います。それはプロでもやりません。私も自分好みのスタイルに直してみましたが、ソート処理のところでセグメンテーションフォールトがかかります。時間をかければ解けますが解かなくていい問題だと思います(興味のある人は解いてみてください)。

参考までに、私が自分好みに書き直したバージョンを上げておきますね。多分ユニットテストをがっつりかけて2,3か所直せば動くようになるのでしょうが、面倒になってしまったので。

#include <iostream>
#include <string>

using namespace std;

#define CHK(EXP) if (!(EXP)) cerr << "Failed at line: " << __LINE__ << endl;

/*
 * リストの項目を保持する構造体
 */
typedef struct Item {
    struct Item *next;
    struct Item *prev;
    int weight;
    int height;
    string name;
} *PITEM;


/*
 * リスト(扱うリストは1個なのでグローバル変数とする)
 */
PITEM head = NULL;
PITEM tail = NULL;


/*
 * コンソールに選択肢を表示し、ユーザーのモード選択を受け取る関数
 */
int select_mode()
{
    int num = 0;
    while (1) {
        cout << "モード選択 [Add 1 / Delete 2 / sort 3 ]: ";
        cin >> num;
        if (num >= 1 && num <= 3) {
            break;
        }
        cout << "1, 2または3を入力してください。\n";
    }
    return num;
}

/*
 * 続けるかどうかをユーザーに問う関数
 */
int select_continue() {
    int num = 0;
    while (1) {
        cout << "続けますか?[YES 1 / NO 2]: ";
        cin >> num;
        if (num == 1 || num == 2) {
            break;
        }
        cout << "1または2を入力してください。\n";
    }
    return num;
}

/*
 * リストの項目を表示する関数
 */
void view_item(PITEM item) {
    cout << "weight: " << item->weight << endl;
    cout << "height: " << item->height << endl;
    cout << "name: " << item->name << endl;
}

/*
 * リストを全て表示する関数
 */
void view() {
    PITEM iter = head;
    if (iter == NULL) {
        cout << "リストがありません\n";
    }
    while (iter != NULL) {
        view_item(iter);
        iter = iter->next;
    }
}

/*
 * ユーザー入力によってリスト項目を取得する関数
 */
PITEM input_item() {
    PITEM item = new Item;
    cout << "体重:";
    cin >> item->weight;
    cout << "身長:";
    cin >> item->height;
    cout << "名前:";
    cin >> item->name;
    return item;
}

/*
 * リストの末尾にリスト項目を追加する関数
 */
void add(PITEM item) {
    if (head == NULL) {
        CHK(tail == NULL)
        item->prev = item->next = NULL;
        head = tail = item;
    } else {
        CHK(tail != NULL)
        item->prev = tail;
        item->next = NULL;
        tail->next = item;
        tail = item;
    }
}

/*
 * 属性nameからリストの項目を見つける関数(無ければNULL)
 */
PITEM find_by_name(string name) {
    PITEM iter = head;
    while (iter != NULL) {
        if (iter->name == name) {
            return iter;
        }
        iter = iter->next;
    }
    return NULL;
}

/*
 * リストの項目を削除する関数
 */
void del(PITEM item) {
    // prevの再結合
    if (item->prev == NULL) {
        head = item->next;
    } else {
        item->prev->next = item->next;
    }
    // nextの再結合
    if (item->next == NULL) {
        tail = item->prev;
    } else {
        item->next->prev = item->prev;
    }
    delete item;
}

/*
 * 2つの項目を比較する関数(マイナスだと昇順)
 */
int compare(PITEM a, PITEM b) {
    if (a->height != b->height) {
        return a->height - b->height;
    }
    return 0;
}

/*
 * 項目のポインタをスワップさせる関数
 */
void swap(PITEM &p1, PITEM &p2) {
    PITEM tmp = p2;
    p2 = p1;
    p1 = tmp;
}

/*
 * 2つの項目を入れ替える関数(ただしitem1はitem2の前にあるものとする)
 */
void replace(PITEM item1, PITEM item2) {
    // A: item1 -> item2, B: item2 -> item1とする

    // prevの再結合
    if (item1->prev == NULL) {
        CHK(head == item1)
        head = item2;
        item2->prev->next = item1;
    } else {
        CHK(head != item1)
        swap(item1->prev->next, item2->prev->next);
    }
    swap(item1->prev, item2->prev);

    // nextの再結合
    if (item2->next == NULL) {
        CHK(tail == item2)
        tail = item1;
        item1->next->prev = item2;
    } else {
        CHK(tail != item2)
        swap(item1->next->prev, item2->next->prev);
    }
    swap(item1->next, item2->next);
}

/*
 * バブルソートを実行する関数
 */
void sort() {
    if (head == NULL || head->next == NULL) {
        return;
    }
    CHK(tail != NULL && tail->prev != NULL)
    PITEM i = head;
    while (i != tail) {
        PITEM j = i->next;
        while (j != NULL) {
            if (compare(i, j) > 0) {
                replace(i, j);
            }
            j = j->next;
        }
        i = i->next;
    }
}

/*
 * ユーザー入力によって項目を追加する関数
 */
void run_add() {
    add(input_item());
}

/*
 * ユーザーが入力した名前の項目を削除する関数
 */
void run_delete() {
    if (head == NULL) {
        cout << "データがありません。\n";
        return;
    }
    string name;
    cout << "削除するリストの名前を入力してください:";
    cin >> name;
    PITEM item = find_by_name(name);
    if (item == NULL) {
        cout << "一致するリスト名がありません。"
                     << "[ " << name << " ]\n";
        return;
    }
    cout << "選択したデータを削除しました。\n";
    del(item);
}

/*
 * リストをソートしてから表示する関数
 */
void run_print() {
    if (head == NULL) {
        cout << "リストがありません.\n";
        return;
    }
    sort();
    view();
}

/*
 * メイン関数
 */
int main () {
    int mode = 0;

    do {
        mode = select_mode(); // モードを選択する

        if (mode == 1) { // 追加する
            run_add();
        }
        if (mode == 2) { // 削除する
            run_delete();
        }
        if (mode == 3) { //昇順にソートして表示(上から1,2,3)
            run_print();
        }
    } while (select_continue() == 1);

    cout << "終了します。\n";
    return 0; // デバッグするときはここにデバッグポイントを置いてください(ポーズできなかった時)
}

この質問に回答するには、ログインする必要があります。