困っている点
リスト構造を用いて挿入ソートで昇順に並び替えるプログラムに取り組んでいます。
下のプログラム内の、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}
element を直接書き換えてはリストの意味がありません.
ポインタの付け替えで行う必要があると思います.
↑なんで?
↑element(値)の書き換えでは、リンク(*next)は変えないので、ノードの位置関係は同一です。ノードがリンクの途中に「挿入」されることは無いので「挿入ソート」とはならないです。
↑配列を使って挿入ソートをした場合にもノードの位置関係は変わらず値が挿入されるので、それは別にいいんじゃないかと思います。
ただ、それなら今回も配列を使えばいいだけのことで、「リンクリストを使わなければならない」という条件があるなら、そこが破綻してしまいます。「確かにソートはできるけどリンクリストを使う意味はどこに?」と言われてしまうんじゃないでしょうか。課題だと思いますが、出題者はノードの入れ替えを期待していると思います。
理解した。「element を直接書き換えてはリストの意味がありません.」ではなく「element を直接書き換えてはリスト構造を活かした挿入ソートの意味がありません.」てことな。