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

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

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

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

Q&A

2回答

3951閲覧

リスト構造を用いた挿入ソート

slushii

総合スコア19

C

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

1グッド

2クリップ

投稿2019/05/13 15:05

困っている点

リスト構造を用いて挿入ソートで昇順に並び替えるプログラムに取り組んでいます。
下のプログラム内の、sort関数内の処理に誤りがあり、昇順にソートされません。
誤りを指摘していただけませんでしょうか。
宜しくお願い致します。

c

1#include <stdio.h> 2#include <stdlib.h> 3 4typedef struct _cell { 5 int element; 6 struct _cell *next; 7}cell; 8 9typedef struct _list{ 10 cell *head; 11}list; 12 13list* create() { 14 list *L = (list *)malloc(sizeof(list)); 15 L->head = (cell *)malloc(sizeof(cell)); 16 L->head->next = NULL; 17 L->head->element = -1; 18 return L; 19} 20 21void addFirst(list *L, int element) { 22 cell *add = (cell *)malloc(sizeof(cell)); 23 add->element = element; 24 add->next = L->head->next; 25 L->head->next = add; 26} 27 28void del(list *L, int element) { 29 cell *ptr = L->head->next; 30 cell *prev = L->head; 31 while(ptr != NULL){ 32 if(ptr->element == element) { 33 prev->next = ptr->next; 34 } else { 35 prev = ptr; 36 } 37 ptr = ptr->next; 38 } 39} 40 41void search(list *L, int element) { 42 cell *ptr = L->head->next; 43 while(ptr != NULL) { 44 if(ptr->element == element) { 45 printf("Found! : %d\n", ptr->element); 46 } 47 ptr = ptr->next; 48 49 } 50} 51 52 53void print(list *L) { 54 cell *ptr = L->head->next; 55 while(ptr != NULL) { 56 printf("%d\n", ptr->element); 57 ptr = ptr->next; 58 } 59} 60 61void sort(list *L) { 62 cell *ptr = L->head->next; 63 cell *prev = L->head; 64 int temp; 65 while(ptr != NULL){ 66 temp = ptr->element; 67 while(prev->element > temp){ 68 prev->element = ptr->element; 69 } 70 ptr->element = temp; 71 printf("\n%d", ptr->element); 72 printf("\n%d\n", prev->element); 73 ptr = ptr->next; 74 prev = prev->next; 75 } 76 printf("\n"); 77 78} 79 80int main(void){ 81 list *L = create(); 82 addFirst(L,1); 83 addFirst(L,2); 84 addFirst(L,3); 85 addFirst(L,4); 86 addFirst(L,5); 87 print(L); 88 sort(L); 89 print(L); 90 91 return 0; 92}
DrqYuto👍を押しています

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

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

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

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

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

jimbe

2019/05/13 17:54

element を直接書き換えてはリストの意味がありません. ポインタの付け替えで行う必要があると思います.
coco_bauer

2019/05/14 04:24

↑element(値)の書き換えでは、リンク(*next)は変えないので、ノードの位置関係は同一です。ノードがリンクの途中に「挿入」されることは無いので「挿入ソート」とはならないです。
Zuishin

2019/05/14 13:30

↑配列を使って挿入ソートをした場合にもノードの位置関係は変わらず値が挿入されるので、それは別にいいんじゃないかと思います。 ただ、それなら今回も配列を使えばいいだけのことで、「リンクリストを使わなければならない」という条件があるなら、そこが破綻してしまいます。「確かにソートはできるけどリンクリストを使う意味はどこに?」と言われてしまうんじゃないでしょうか。課題だと思いますが、出題者はノードの入れ替えを期待していると思います。
episteme

2019/05/14 13:52 編集

理解した。「element を直接書き換えてはリストの意味がありません.」ではなく「element を直接書き換えてはリスト構造を活かした挿入ソートの意味がありません.」てことな。
guest

回答2

0

こんな感じでどうでしょう.

c

1#include <stdio.h> 2#include <stdlib.h> 3 4typedef struct _cell { 5 int element; 6 struct _cell *next; 7} cell; 8 9typedef struct _list { 10 cell *head; 11} list; 12 13list* create() { 14 list *L = (list *)malloc(sizeof(list)); 15 L->head = (cell *)malloc(sizeof(cell)); 16 L->head->next = NULL; 17 L->head->element = -1; 18 return L; 19} 20 21void addFirst(list *L, int element) { 22 cell *add = (cell *)malloc(sizeof(cell)); 23 add->element = element; 24 add->next = L->head->next; 25 L->head->next = add; 26} 27 28void sort(list *L) { 29 cell *t = L->head->next; 30 if(t == NULL) return; //データが無い 31 32 while(t->next != NULL) { 33 //ソートした最大値と比較 34 if(t->element <= t->next->element) { //移動の必要無し 35 t = t->next; 36 continue; 37 } 38 //挿入位置を探す(必ずある) 39 cell *p = L->head; 40 for(; t->next->element > p->next->element; p=p->next); 41 42 cell *next = t->next->next; 43 //挿入 44 t->next->next = p->next; 45 p->next = t->next; 46 //移動させたcellに繋がっていた元のポインタを付け替え 47 t->next = next; 48 } 49} 50 51void print(list *L) { 52 cell *ptr = L->head->next; 53 while(ptr != NULL) { 54 printf("%d\n", ptr->element); 55 ptr = ptr->next; 56 } 57} 58 59int main(void){ 60 list *L = create(); 61 addFirst(L, 1); 62 addFirst(L, 2); 63 addFirst(L, 3); 64 addFirst(L, 4); 65 addFirst(L, 5); 66 print(L); 67 sort(L); 68 print(L); 69 70 return 0; 71}

投稿2019/05/15 15:33

編集2019/05/16 07:55
jimbe

総合スコア12543

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

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

0

以前の回答にも書きましたが、連結リストのソートは結構やっかいです。
新規のリストに常に昇順になるようにノードを挿入していけば、ソート済みのリストが出来ますが、これを挿入ソートと呼んでいいものかどうか分りません。

質問のソースのsrot 関数を差し替えて、insert関数を追加するとソートができます。ご希望のものとは違うかもしれませんが、参考までに。

c

1// リストに追加する 2void insert(cell **root, cell *data) 3{ 4 cell **p; 5 6 for (p = root; *p; p = &(*p)->next) { //リストの最初から挿入位置を検索 7 if ((*p)->element > data->element) { 8 cell *t = *p; // 現在のノードを保存 9 *p = data; // dataを挿入する 10 data->next = t; // リンクを付け替える 11 return; 12 } 13 } 14 15 *p = data; // リストの最後に追加 16 data->next = NULL; 17} 18 19// リストをソートする 20void sort(list *L) 21{ 22 cell *new_list = NULL; // ここにソート済みのリストを追加する 23 24 cell *curr; 25 cell *next; 26 27 for (curr = L->head->next; curr; curr = next) { // リストの最初から最後まで 28 next = curr->next; // 次のノード 29 insert(&new_list, curr); // ソート済みのリストに追加 30 } 31 32 L->head->next = new_list; // ソート済みのリスト 33}

質問の答えになってなかったので、補足します。

何故ソートできないか?
配列の場合を考えてみれば分りますが、挿入ソートにするにはリストを順方向と逆方向に走査する必要があります。ご提示のプログラムではそれが出来ていません。単方向リストを逆方向に辿るのは出来なくはないですが、かなり手間のかかる作業になります。
なので、効率も悪いので挿入ソートはやめた方がいいかもしれません。

余談ですがバブルソートや選択ソートでしたら順方向だけでもできます。
更に余談、以前にお遊びで単方向リストを逆方向に辿る処理を実装したことがあります。その時は再帰関数で実装したので、ノードの個数分再帰が深くなります。速度も遅いしあまり実用的ではないですね。


度々追加ですいません。
逆順にこだわって実装してみました。
あまり実用的ではないですし、再帰呼び出ししているので要素数が多いとダメですけど。

c

1#include <stdio.h> 2#include <stdlib.h> 3 4typedef struct _cell { 5 int element; 6 struct _cell *next; 7}cell; 8 9typedef struct _list { 10 cell *head; 11}list; 12 13list* create() { 14 list *L = (list *)malloc(sizeof(list)); 15 L->head = (cell *)malloc(sizeof(cell)); 16 L->head->next = NULL; 17 L->head->element = -1; 18 return L; 19} 20 21void addFirst(list *L, int element) { 22 cell *add = (cell *)malloc(sizeof(cell)); 23 add->element = element; 24 add->next = L->head->next; 25 L->head->next = add; 26} 27 28void del(list *L, int element) { 29 cell *ptr = L->head->next; 30 cell *prev = L->head; 31 while (ptr != NULL) { 32 if (ptr->element == element) { 33 prev->next = ptr->next; 34 } else { 35 prev = ptr; 36 } 37 ptr = ptr->next; 38 } 39} 40 41void search(list *L, int element) { 42 cell *ptr = L->head->next; 43 while (ptr != NULL) { 44 if (ptr->element == element) { 45 printf("Found! : %d\n", ptr->element); 46 } 47 ptr = ptr->next; 48 49 } 50} 51 52 53void print(list *L) { 54 cell *ptr = L->head->next; 55 while (ptr != NULL) { 56 printf("%d\n", ptr->element); 57 ptr = ptr->next; 58 } 59} 60 61void sort_sub(cell *p) 62{ 63 if (p) { 64 sort_sub(p->next); //再帰呼び出しでリストを逆順に辿る 65 66 int temp = p->element; //データを保存 67 while (p->next) { 68 if (temp > p->next->element) { //挿入位置を探す 69 p->element = p->next->element; //データをずらす 70 } else { 71 break; 72 } 73 74 p = p->next; //次の要素 75 } 76 77 p->element = temp; //挿入する 78 } 79} 80 81void sort(list *L) 82{ 83 sort_sub(L->head->next); 84} 85 86int main(void) { 87 list *L = create(); 88 addFirst(L, 1); 89 addFirst(L, 2); 90 addFirst(L, 3); 91 addFirst(L, 4); 92 addFirst(L, 5); 93 print(L); 94 sort(L); 95 print(L); 96 97 return 0; 98}

投稿2019/05/14 03:36

編集2019/05/16 13:09
Bull

総合スコア986

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

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

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

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

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問