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

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

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

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

ソート

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

連結リスト

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

Q&A

解決済

4回答

4753閲覧

C言語 連結リストのソーティングプログラム

Kassy11

総合スコア26

C

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

ソート

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

連結リスト

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

0グッド

1クリップ

投稿2019/06/18 08:25

編集2019/06/19 08:55

現在C言語を用いて、コマンドライン引数で受け取ったファイルを読み取り、連結リストとして出力ファイルに書き込むプログラムを実装しました。
これに加えて、このファイル要素を昇順にソートしたいと考えています。

入出力のプログラム

#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct school_record SRec; struct school_record{ float gpa;/*累積GPA*/ int credit;/*累積単位数*/ char name[200];/*名前(アルファベット)*/ SRec *next; /*次のセルへのポインタ*/ }; SRec *p;/*連結リストをたどるためのポインタ*/ SRec *input_file(char *input_name); void output_file(char *output_name,SRec *front); int main(int argc,char *argv[]) {/*agrv[1]はソートを行うフィールド名(メンバ名)※この課題では必要なし、[2]は入力ファイル名:データ件数は記録しない、[3]は出力ファイル名*/ // int n,i; SRec *front; if(argc != 4){/*ファイルは3つ(プログラム名を含めて4つ)*/ printf("ソートを行いたいフィールド名、入力ファイル、出力ファイルの3つをコマンドライン引数で指定してください.\n"); return 1; } front = input_file(argv[2]);/*入力処理を行う*/ output_file(argv[3],front); return 0; } SRec *input_file(char *input_name){/*入力ファイル名を受け取りファイルをオープンして、データ領域を確保し、一件分のデータ入力と挿入を繰り返す、先頭要素へのポインタを返す*/ int credit_temp; float gpa_temp; char name_temp[200];/*ファイル読み込みのための一時変数*/ SRec header;/*連結リスト自身を表すためのダミー*/ SRec *p;/*連結リストをたどるためのポインタ*/ SRec *tail = &header;/*初期化、連結リストの最後の要素*/ header.next = NULL; FILE *fp; if((fp = fopen(input_name,"r")) == NULL){/*ファイルをオープン*/ printf("入力ファイルをオープンできませんでした。\n"); } while(fscanf(fp,"%f %d %s ",&gpa_temp,&credit_temp,name_temp)==3){/*ファイルの内容を読み込んで一時変数に格納する*/ /*連結リストに関するif文*/ if((p=malloc(sizeof(SRec)))==NULL){ printf("メモリが足りません。"); exit(1); } p->gpa = gpa_temp; p->credit = credit_temp; strcpy(p->name,name_temp);/*連結リストに値を入れる*/ printf("%f %d %s\n",p->gpa,p->credit,p->name);/*デバッグ用*/ p->next = NULL; tail->next = p; tail = p; /*セルを進める*/ } fclose(fp); printf("入力ファイルの処理完了。\n"); return header.next; } void output_file(char *output_name, SRec *front){/*出力ファイル名と連結リストの先頭へのポインタを受け取り、書き込む*/ FILE *fp; if((fp = fopen(output_name,"w")) == NULL){ printf("出力ファイルをオープンできませんでした。\n"); } while(front != NULL){ fprintf(fp,"%f %d %s\n",front->gpa,front->credit,front->name); front = front->next; } printf("書き込みに成功しました。\n"); fclose(fp); free(p); }

これに以下のようなプログラムを加えて昇順のソートをしたいと考えています。
・dummyはリストが空にならないために定義する
・最初、qはdummyを指しpはその次のfront(引数で受け取ったリストの最初の要素)を指す
・比較関数にqとpを送り比較してもらい、昇順になっていなければソートを行う←このソートの部分の実装方法がわかりません
・qとpをがNULLを指すまで順次ひとつずつずらしていく(探索していく)
・戻り値としてリストの先頭を返し、output_file関数で出力ファイルに書き込めるようにする

SRec *list_sort(SRec *front,int (*comp)(const void*,const void*)){ SRec dummy; SRec *p,*q; dummy.next = front; q = &dummy; p = q->next; while(p != NULL){ if( comp(q,p)>=0 ){ /*q->nextに挿入する*/ p->next = q->next; break; } q = p; p = p->next; /*リストを進める*/ } return front;/*pでもいいのか??*/ }

ソートプログラムを実現したいのですが、if文中でのソートの実装方法がわからないため、ご教授いただきたいです。

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

y_waiwai

2019/06/18 09:04

うまく動かないとはどうなるんでしょう。 エラーメッセージが出るなら、コピペでそのまま提示しましょう
episteme

2019/06/18 10:36

質問ヘタクソ。やりなおし。
guest

回答4

0

ベストアンサー

list_sort を書いてみましたが、テストのため結局全部書いてしまいました。
呼び出し方にも注意してください。

C

1#include <stdio.h> 2#include <stdlib.h> 3#include <string.h> 4 5typedef struct school_record SRec; 6struct school_record{ 7 float gpa; /* 累積GPA */ 8 int credit; /* 累積単位数 */ 9 char name[200]; /* 名前(アルファベット)*/ 10 SRec *next; /* 次のセルへのポインタ */ 11}; 12 13SRec *input_file(const char *input_name); 14void output_file(const char *output_name, SRec *front); 15SRec *list_sort(SRec *front, int (*comp)(const void *, const void *)); 16 17void list_free(SRec *p) { for (SRec *q; p; p = q) q = p->next, free(p); } 18 19int comp_gpa(const void *a, const void *b) 20{ 21 float x = ((SRec *)a)->gpa, y = ((SRec *)b)->gpa; 22 return x < y ? -1 : x > y; 23} 24 25int comp_credit(const void *a, const void *b) 26{ 27 int x = ((SRec *)a)->credit, y = ((SRec *)b)->credit; 28 return x < y ? -1 : x > y; 29} 30 31int comp_name(const void *a, const void *b) 32{ 33 return strcmp(((SRec *)a)->name, ((SRec *)b)->name); 34} 35 36int main(int argc, char *argv[]) 37{ 38 if (argc != 4) { 39 puts("引数 3: [1]ソートキー(gpa|credit|name) [2]入力ファイル名 [3]出力ファイル名"); 40 return 1; 41 } 42 SRec *front = input_file(argv[2]); 43 if (!front) return 1; 44 45 if (strcmp(argv[1], "gpa") == 0) 46 front = list_sort(front, comp_gpa); 47 else if (strcmp(argv[1], "credit") == 0) 48 front = list_sort(front, comp_credit); 49 else if (strcmp(argv[1], "name") == 0) 50 front = list_sort(front, comp_name); 51 else { puts("specify one of gpa, credit, or name"); return 1; } 52 53 output_file(argv[3], front); 54 55 list_free(front); 56 return 0; 57} 58 59SRec *input_file(const char *input_name) 60{ 61 int credit_temp; 62 float gpa_temp; 63 char name_temp[200]; /* ファイル読み込みのための一時変数 */ 64 65 SRec header; /* 連結リスト自身を表すためのダミー */ 66 SRec *tail = &header; /* 初期化、連結リストの最後の要素*/ 67 header.next = NULL; 68 69 FILE *fp = fopen(input_name,"r"); 70 if (fp == NULL) { 71 puts("入力ファイルをオープンできませんでした。"); return NULL; 72 } 73 74 while (fscanf(fp,"%f%d%199s", &gpa_temp, &credit_temp, name_temp) == 3) { 75 SRec *p = malloc(sizeof(SRec)); 76 if (p == NULL) { puts("メモリが足りません。"); return NULL; } 77 78 p->gpa = gpa_temp; 79 p->credit = credit_temp; 80 strcpy(p->name,name_temp); 81 82 printf("%f %d %s\n", p->gpa, p->credit, p->name); /* デバッグ用 */ 83 84 p->next = NULL; 85 tail->next = p; 86 tail = p; 87 } 88 fclose(fp); 89 puts("入力ファイルの処理完了。"); 90 return header.next; 91} 92 93void output_file(const char *output_name, SRec *front) 94{ 95 FILE *fp = fopen(output_name,"w"); 96 if (fp == NULL) { 97 puts("出力ファイルをオープンできませんでした。"); return; 98 } 99 for (; front != NULL; front = front->next) 100 fprintf(fp, "%f %d %s\n", front->gpa, front->credit, front->name); 101 puts("書き込みに成功しました。"); 102 fclose(fp); 103} 104 105SRec *list_sort(SRec *front, int (*comp)(const void *, const void *)) 106{ 107 SRec dummy, *p, *q, *next; 108 dummy.next = NULL; 109 for (p = front; p; p = next) { 110 next = p->next; 111 for (q = &dummy; q->next && comp(p, q->next) > 0; q = q->next) ; 112 p->next = q->next; 113 q->next = p; 114 } 115 return dummy.next; 116} 117

投稿2019/06/19 09:06

kazuma-s

総合スコア8224

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Kassy11

2019/07/12 01:47

ありがとうございました!助かりました
guest

0

list_sortのどこかでエラーが起きているのか、eclipceがうまく動きません

eclipseを持ってないけど手元で試してみました。list_sort()が「ソート」した結果、ある要素の次の要素が自分自身であるというリスト構造になります。
それをoutput_file()が出力しようとして無限ループする(ある要素を無限に出力する、おそらく巨大な出力ファイルが作られている)、その結果プログラムは動作終了せず、eclipseに制御が戻らない、それを「eclipceがうまく動きません」と表現したのでしょうが、eclipseのせいではありません。

要するに、list_sort()がダメダメです。見るからに、ソートになっていません(後述)。
eclipseならlist_sort()関数をトレースできるのではありませんか?誤ったリスト構造を返すことを、ご自分で確かめてみましょう。

ソートプログラムを実現したいのですが、if文中でのソートの実装方法がわからないため、ご教授いただきたい

質問者のイメージと違うかもしれませんが、リスト構造のソートは大まかに次のような手順になると思います。

  1. ソートしたいリスト(frontから始まるリスト)がある
  2. 結果となる空のリスト(dummy?)がある
  3. front から要素を一つ取出し、結果となるリストdummyの、しかるべき位置に挿入する
  4. front に要素が無くなるまで 3. の処理を繰り返す。

これだけだと一重のループに思えるかもしれませんが、

  • しかるべき挿入位置を決める
  • 取り出す要素を決める

の、どちらかがループになるので、ソート処理は2重ループで実現されるはずです。こう考えれば、一重のループでしかない list_sort()ではソートできないだろうと予想できます。

「取り出す要素を決める」方式の具体例を示します。

front -> B -> F -> A -> D -> C -> E -> NULL dummy -> NULL

このリストで最小(最奥)になるべき要素は、リストを先頭から見ていき F が見つかりますので、F を取出し、dummy に挿入します。

front -> B -> A -> D -> C -> E -> NULL dummy -> F -> NULL

次は E を取出し dummy に挿入する、その次は D ・・・と進めて

front -> B -> A -> C -> NULL dummy -> D -> E -> F -> NULL

となっていく。最終的に dummy にソートされた結果ができるという次第。

front -> NULL dummy -> A -> B -> C -> D -> E -> F -> NULL

P.S.1
公開するプログラムにしては、インデントが杜撰で、無駄な空行が多い。

P.S.2

C

1 SRec *p;/*連結リストをたどるためのポインタ*/

ポインタ変数「p」が、グローバル変数としてある他に、input_file()関数のローカル変数としてもある。2つのpは(名前は同じでも)異なる変数だということを理解していますか?
英小文字一字のグローバル変数なんて、周囲の人から袋叩きにあう(笑)ほどマナーの悪い書き方です。

P.S.3
output_file()の最後で free(p); しています。この p は、上記2つの p のどちらなのか、わかって書いてますか?
もうひとつ、入力ファイルの行数回だけ malloc() して獲得したメモリを、そこの一回の free() で返却できるでしょうか?

P.S.4
少しだけ違うソートプログラム(「いちいち書いた」同等のコード)
を作ったことがあります。この中の sort_list() は、

  • 今の場所(ap ポインタが指している要素)から先を見て
  • 最小の要素を探して
  • それを取出し
  • 今見ている場所に挿入する(挿入し直す)

という感じで、head から始まる一本のリストだけでソートしています。双方向リストなので、そのままコピペできませんが(むしろ、できないからこそw)ご紹介します。リスト操作の雰囲気を感じてください。
加えて、リストの図を描かずにリスト操作はできません。図も描いてあるので描き方を参考にしていただきたく。

投稿2019/06/19 08:07

編集2019/06/21 04:30
rubato6809

総合スコア1380

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

rubato6809

2019/06/21 04:32

P.S.4に書いたソートの手順を、回答の2番目の柱として抜き出し、具体例を追加するなど変更しました。
guest

0

line_sort の先頭で q は dummy を指し、p はリストの先頭要素を指しています。
dummy はデータを持っていません。comp(q, p) なんか無意味です。
紙にリストや変数の図を書いて、どのようにソートすればいいか考えてコーディングしてください。

投稿2019/06/19 04:29

kazuma-s

総合スコア8224

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

C

1 if( comp(q,p)>=0 ){ 2 /*q->nextに挿入する*/ 3 p->next = q->next; 4 break; 5 }

この部分、問題無い?
p->nextp を指すだけになってませんか?
また、break で while()ループを抜けます。

投稿2019/06/18 15:14

pepperleaf

総合スコア6383

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問