teratail header banner
teratail header banner
質問するログイン新規登録

回答編集履歴

2

説明の追加

2021/05/17 10:24

投稿

kazuma-s
kazuma-s

スコア8222

answer CHANGED
@@ -119,4 +119,66 @@
119
119
  aaa bbb ccc ddd
120
120
  1.追加入力 2.ソート 3.表示 0.終了: 0
121
121
  ```
122
- バグがあるかもしれません。どうでしょうか?
122
+ バグがあるかもしれません。どうでしょうか?
123
+
124
+ **追記**
125
+ コードの説明です。
126
+ 変数名{変数の値}。値がポインタの時は * で -> の先のオブジェクトを指す。
127
+ ->{構造体の値} は一つ前の * で指されるオブジェクト。
128
+
129
+ head{*}->{1,"ccc",*}->{2,"aaa",*}->{3,"ddd",*}->{4,"bbb",NULL}
130
+ というリストができたとする。
131
+
132
+ quick_sort に入ると、
133
+ a{*}->{1,"ccc",*}->{2,"aaa",*}->{3,"ddd",*}->{4,"bbb",NULL}
134
+
135
+ pivot = a, a = a->next, pivot->next = NULL; を実行すると、
136
+ pivot{*}->{1,"ccc",NULL}
137
+ a{*}->{2,"aaa",*}->{3,"ddd",*}->{4,"bbb",NULL}
138
+
139
+ a のリストの先頭から順番に取り外し、
140
+ pivot の "ccc" より小さい name のものを less リストに追加し、
141
+ pivot の "ccc" より大きい name のものを greater リストに追加する
142
+ ということを繰り返す。
143
+
144
+ int diff = strcmp(a->name, pivot->name); を実行すると、
145
+ "aaa" < "ccc" だから diff は負の値で、a の先頭を less に追加する。
146
+ add(less) は、 p = a, a = a->next, p->next = less, less = p なので、
147
+ p{*}->{2,"aaa",NULL}  (less は NULL だったので)
148
+ a{*}->{3,"ddd",*}->{4,"bbb",NULL}
149
+ less{*}->{2,"aaa",NULL}
150
+
151
+ int diff = strcmp(a->name, pivot->name); を実行すると、
152
+ "ddd" > "ccc" だから diff は正の値で、a の先頭を greater に追加する。
153
+ add(greater) は、 p = a, a = a->next, p->next = greater, greater = p なので、
154
+ p{*}->{3,"ddd",NULL}  (greater は NULL だったので)
155
+ a{*}->{4,"bbb",NULL}
156
+ greater{*}->{3,"ddd",NULL}
157
+
158
+ int diff = strcmp(a->name, pivot->name); を実行すると、
159
+ "bbb" < "ccc" だから diff は負の値で、a の先頭を less に追加する。
160
+ add(less) は、 p = a, a = a->next, p->next = less, less = p なので、
161
+ p{*}->{4,"bbb",*}->{2,"aaa",NULL}  (less の先頭に追加)
162
+ a{NULL}
163
+ less{*}->{4,"bbb",*}->{2,"aaa",NULL}
164
+
165
+ a が NULL なので、while (a) のループを終了
166
+
167
+ less = quick_sort(less) で less をソート
168
+ less{*}->{2,"aaa",*}->{4,"bbb",NULL}
169
+
170
+ greater = quick_sort(greater) で greater をソート
171
+ greater{*}->{3,"ddd",NULL}
172
+
173
+
174
+ less が NULL なら、a は pivot + greater となるが、
175
+ less が NULL でないので、a = less とし、
176
+ less と pivot と greater を結合して a を作る。
177
+ for (p = less; p->next; p = p->next) ; で、
178
+ p が less の最後の要素を指すようにする。
179
+ p->next = pivot で less の最後に pivot を連結する。
180
+ for (p = pivot; p->next; p = p->next) ; で、
181
+ p が pivot の最後の要素を指すようにする。
182
+ p->next = greater で pivot の最後に greater を連結する。
183
+
184
+ return a; でソートと連結が完了したリストを返す。

1

コードの修正

2021/05/17 10:24

投稿

kazuma-s
kazuma-s

スコア8222

answer CHANGED
@@ -60,7 +60,7 @@
60
60
  greater = quick_sort(greater);
61
61
  if (less == NULL) a = pivot;
62
62
  else {
63
- for (a = p = less; p && p->next; p = p->next) ;
63
+ for (a = p = less; p->next; p = p->next) ;
64
64
  p->next = pivot;
65
65
  }
66
66
  for (p = pivot; p->next; p = p->next) ;