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

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

新規登録して質問してみよう
ただいま回答率
86.02%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

プログラミング言語

プログラミング言語はパソコン上で実行することができるソースコードを記述する為に扱う言語の総称です。

連結リスト

連結リストとは、データ構造のひとつであるリストの中で、要素が前後の要素の情報を持つことで、要素が連結(リンク)しているリストの事を呼びます。

Q&A

受付中

連結リスト(単方向リスト)を用いたクイックソートのプログラムの作成

Shota08
4431

総合スコア2

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

プログラミング言語

プログラミング言語はパソコン上で実行することができるソースコードを記述する為に扱う言語の総称です。

連結リスト

連結リストとは、データ構造のひとつであるリストの中で、要素が前後の要素の情報を持つことで、要素が連結(リンク)しているリストの事を呼びます。

2回答

0グッド

0クリップ

541閲覧

投稿2022/11/22 02:11

編集2022/11/22 08:23

前提

C言語で連結リストを用いたクイックソートのプログラムを作成しています。
リストの要素数はプログラムの引数で指定するようにしています。
リストの要素 Node の値 value は 1 から 10000 までの整数をランダムで入れるようにします。
まだまだプログラミング初学者なため出来るだけ簡単に分かりやすくご教授いただければ幸いです。
よろしくお願いします。(c言語)

実現したいこと

以下のような実行をイメージしています。

>./qsort 10
generated list
7019, 7431, 4192, 3673, 6593, 1236, 9108, 5213, 5460, 8572
sorted list
1236, 3673, 4192, 5460, 5213, 6593, 7019, 7431, 8572, 9108

そのためにquick_sort_list にある
pivotの値より小さい要素をl_pivotに集め、
pivotの値と同じ大きさの要素をe_pivotに集め、
pivotの値より大きい要素をr_pivotに集める部分を修正して
所望の動作が出来るようにしたいです。

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

エラーなくコンパイルすることが出来るのですが、ソートをしたはずのリストが表示されずに以下のような実行になってしまいます。これを修正して上記のような実行になる様にしたいです。

>./qsort 10
generated list
9604 7228 8288 2305 8323 9013 7967 3979 7798 1795
sorted list

該当のソースコード

C

1//qsort.c 2#include <stdio.h> 3#include <stdlib.h> 4#include <time.h> 5#include <math.h> 6 7typedef struct node Node; 8 9struct node { 10 int value; 11 Node *next; 12}; 13 14Node *prepare_head(int); 15Node *generate_node(); 16int gen_random_num(int); 17void print_list(Node *); 18Node *quick_sort_list (Node *); 19Node *concatante (Node *, Node *); 20 21int main(int argc, char *argv[]) 22{ 23 Node *head; 24 int n; 25 26 n = atoi(argv[1]); 27 28 srand((unsigned int)time(NULL)); // 現在時刻の情報で初期化 29 30 head = prepare_head(n); 31 printf("generated list\n"); 32 print_list(head); 33 head = quick_sort_list(head); 34 printf("sorted list\n"); 35 print_list(head); 36 37} 38Node *concatante (Node *a, Node *b) 39{ 40 Node *p; 41 if (a == NULL) 42 return b; 43 else if (b == NULL) 44 return a; 45 for (p = a; p->next != NULL; p = p->next) 46 p->next = b; 47 return a; 48} 49Node *quick_sort_list (Node *c) 50{ 51 int pivot; 52 Node *t; 53 Node *l_pivot = NULL; 54 Node *e_pivot = NULL; 55 Node *r_pivot = NULL; 56 57 if (c == NULL || c->next == NULL) 58 return c; 59 60 pivot = c->value; 61 62 while(c->next != NULL) { 63 t = c->next; 64 if (c->value < pivot) { 65 c->next = l_pivot; 66 l_pivot = c; 67 } 68 else if (c->value == pivot) { 69 c->next = e_pivot; 70 e_pivot = c; 71 } 72 else if (c->value > pivot) { 73 c->next = r_pivot; 74 r_pivot = c; 75 } 76 } 77 78 l_pivot = quick_sort_list (l_pivot); 79 r_pivot = quick_sort_list (r_pivot); 80 81 return concatante (l_pivot, concatante (e_pivot, r_pivot)); 82} 83Node *prepare_head(int n) 84{ 85 int i; 86 Node *p, *q, *head; 87 head = generate_node(); 88 p = head; 89 for(i = 0;i < n;i++) { 90 q = generate_node(); 91 q->value = gen_random_num(10000); 92 p->next = q; 93 p = q; 94 } 95 return head; 96} 97void print_list(Node *head) 98{ 99 Node *p = head; 100 while(p->next != NULL) { 101 p = p->next; 102 printf(" %d",p->value); 103 } 104 printf("\n"); 105} 106Node *generate_node() 107{ 108 Node *p = (Node *)malloc(sizeof(Node)); 109 p->next = NULL; 110 return p; 111} 112int gen_random_num(int max) 113{ 114 return (int)(rand()*(max + 1.0)/(1.0+RAND_MAX)); 115}

以下のような質問にはグッドを送りましょう

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

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

気になる質問をクリップする

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

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

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

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

適切な質問に修正を依頼しましょう。

2022/11/22 08:17依頼された後にこの質問は修正されています

こちらの質問が複数のユーザーから「やってほしいことだけを記載した丸投げの質問」という指摘を受けました。

Shota08

2022/11/22 03:26

concatante、quick_sort_list以外は想定通りの動作をしていると思われます。
jimbe

2022/11/22 12:06 編集

>想定通りの動作をしていると思われます。 思われます、は確認しているとは言えません。 二つの関数が怪しいと考えているのであれば、それらを優先的に確認するべきと思います。 prepare_head で作ったリストは head はデータを入れない形になっているようです ( print_list も head の value は表示していません ) が、 concatante や quick_sort_list はそのようにしていますでしょうか。

回答2

1

問題は 3 つです。

1. prepare_head 関数が生成し print_list 関数のパラメータが前提としているリストの構造と、quick_sort_list, concatante 関数のパラメータが前提としているリストの構造が違っている。

前者は head ノードは value を設定せず next の先が実際のデータであるのに対し、後者は head からデータであることになっています。
main 関数での head の使い方も恐らく後者です。前者だとしたらメモリリークがあります。

2. quick_sort_list 関数の while 内で、ループしても変数 c が正しく次のノードを指していない。

変数 t に c->next を保存した上で c->next を更新しているのに、 t が使われていません。

3. concatante 関数が a の後ろに b を正しく連結出来ていない

pig_vba さんがご自身の回答のコメントで指摘されています。

投稿2022/11/22 19:55

編集2022/11/22 20:06
jimbe

総合スコア10817

spoofy_dragon👍を押しています

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

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

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

このような回答には修正を依頼しましょう。

1

※普通に誤回答なので折りたたみます。無視してください

while(c->next != NULL) { t = c->next; if (c->value < pivot) { c->next = l_pivot; l_pivot = c; } else if (c->value == pivot) { c->next = e_pivot; e_pivot = c; } else if (c->value > pivot) { c->next = r_pivot; r_pivot = c; } 処理が逆じゃないですかね…?流れを見るに前と次の要素を入れ替える処理と判断しましたが、l_pivotの初期値はNULLなのでこれ全部c->nextにNULLが挿入されているように見えます。 if (t->value < pivot) { //入れ替え処理 } 私はこうだと思ったんですけど、間違えてたらすみません

投稿2022/11/22 04:39

編集2022/11/22 13:21
pig_vba

総合スコア668

spoofy_dragon👍を押しています

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

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

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

このような回答には修正を依頼しましょう。

回答へのコメント

Shota08

2022/11/22 04:51

申し訳ございません。修正してみましたが、正しく動作しませんでした。ご回答ありがとうございます。
pig_vba

2022/11/22 05:37

お力に添えられず申し訳ございません。 あと別の項目になりますが、*concatante関数はnode aの後ろにnode bを結合する関数でしょうか?そうであるならばaの末尾に結合だと思うので for (p = a; p->next != NULL; p = p->next); p->next = b; こうではないでしょうか?
jimbe

2022/11/22 11:54 編集

該当 while は 大小関係に合わせて各 pivot リストの先頭に追加しているので、追加の処理自体は間違っておりません。 ただ…最後に重要な処理が足りないです。( t は何の為にあるのでしょう。) >//c->valueとt->valueを入れ替える処理 少なくとも、 リストを使用しているのは value を直接入れ替えるのでは無く Node のポインタの繋ぎ変えで入れ替えるということですので、この部分は合わないと思います。
pig_vba

2022/11/22 13:22

やっぱりそうでしたか。余計混乱させるだけなので自分は静観しておきます
jimbe

2022/11/22 19:25

concatante の指摘は合っていると思います。

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

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

ただいまの回答率
86.02%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

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

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

プログラミング言語

プログラミング言語はパソコン上で実行することができるソースコードを記述する為に扱う言語の総称です。

連結リスト

連結リストとは、データ構造のひとつであるリストの中で、要素が前後の要素の情報を持つことで、要素が連結(リンク)しているリストの事を呼びます。