質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

89.06%

双方向循環リストでのバブルソート

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 155

submaru

score -6

前提・実現したいこと

双方向循環リストでのバブルソートを行い、表示したい。

発生している問題・エラーメッセージ

ソート部分のプログラムが正しいかよくわからず、またソート後の表示ができない。
おそらくソートを行う関数で不具合が起こっており、無限ループになる。

該当のソースコード

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

typedef struct node{
        struct node *prev;
        struct node *next;
        int value;
}NODE;

#define DUMMY -1
#define MAX 99
#define NUM 10

NODE* make_list(int num);
NODE* make_cell(int val);
void insert_cell_to_list(NODE *x, NODE *p);
NODE* delete_cell_from_list(NODE *x);
void print_list(NODE *link_list_head);
void free_list(NODE *link_list_head);
void bubble_sort_cell(NODE *link_list_head);

int main(void){
        NODE *list_head;

        srand((unsigned int)time(NULL));


        list_head=make_list(NUM);
        printf("ランダムで作成したリストを表示\n");
        print_list(list_head);
        bubble_sort_cell(list_head);
        printf("バブルソート後\n");
        print_list(list_head);
        printf("\n");

        free_list(list_head);

        return 0;
}

NODE* make_list(int num){
        NODE *list, *cel, *list_head;
        int i;

        list=make_cell(DUMMY);
        list->next=list;
        list->prev=list;
        list_head=list;

        for(i=0; i<num; i++){
                cel=make_cell(rand()%MAX);
                list=list->next;
                insert_cell_to_list(cel, list);
        }
        return (list_head);
}

NODE* make_cell(int val){
        NODE *p;

        p=(NODE*)malloc(sizeof(NODE));

        if (p == NULL) {
                fprintf(stderr, "Memory allocation error!\n");
                exit(-1);
        }
        p->value =val;
        p->next =NULL;
        p->prev =NULL;
        return(p);
}

void insert_cell_to_list(NODE *x, NODE *p){

  x->prev = p;
  x->next = p->next;
  p->next = x;
  p->next->prev = x;
}

NODE* delete_cell_from_list(NODE *x){

  x->prev->next = x->next;
  x->next->prev = x->prev;

  return (x);
}

void print_list(NODE *link_list_head){
        NODE *p;

        for (p = link_list_head->next; p != link_list_head; p = p->next) {
          printf("%d\n", p->value);
        }
}

void free_list(NODE *link_list_head){
        NODE *p, *q;

        p=link_list_head;
        p->prev->next = NULL;
        while (p!=NULL){
                q=p->next;
                free(p);
                p=q;
        }
}


void bubble_sort_cell(NODE *link_list_head){
        NODE *p, *q, *tmp;

        for (p = link_list_head->next; p != link_list_head->prev; p = p->next) {
          for (q = link_list_head->prev; q != p; q = q->prev) {
            if (q->value < q->prev->value) {
              tmp = delete_cell_from_list(q->prev);
              insert_cell_to_list(tmp, q);
            }
          }
        }
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

0

全体は見ていませんが、明らかにまずい個所が一つ

void insert_cell_to_list(NODE *x, NODE *p){
/*中略*/
  p->next = x;      // ここで p->next が x で上書きされるので
  p->next->prev = x;     // これは x->prev = x と自分を参照している
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/08/02 10:23

    順番を逆にしたら大丈夫ですかね?

    キャンセル

0

C言語のコードを書くなら、デバッグできる環境を整えましょう。
Eclipseや、WindowsならVisualStudioなど。
コードの任意の場所で実行を止め、変数のナカミを見ることができます。そこから1行づつ実行して、コードの流れを見れるようになります
そうすれば、アテズッポでコードを書かなくて済むようになります。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

check解決した方法

-1

考えなおしたら解決しました。
回答ありがとうございました。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/08/02 12:21

    どのようにして解決したか、書いてもらえませんか?
    bubble_sort_cell の中の delete_celll_from_list と insert_cell_to_list でリストの入れ替えが
    あるので、2つの for 文の p = p->next と q = q->prev が正しく機能しないのは分かるんですが。
    まさか、value だけを交換するようにしたとかではないでしょうね。

    キャンセル

  • 2020/08/02 15:53

    交換をした時にqの更新をしました。あとはfor文の範囲の見直しです。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 89.06%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る