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

回答編集履歴

4

移動無し判定を前に移動

2019/05/16 07:55

投稿

jimbe
jimbe

スコア13357

answer CHANGED
@@ -33,22 +33,21 @@
33
33
  if(t == NULL) return; //データが無い
34
34
 
35
35
  while(t->next != NULL) {
36
+ //ソートした最大値と比較
37
+ if(t->element <= t->next->element) { //移動の必要無し
38
+ t = t->next;
39
+ continue;
40
+ }
36
- //tまで挿入位置を探す
41
+ //挿入位置を探す(必ずある)
37
42
  cell *p = L->head;
38
- for( ; p!=t; p=p->next) {
39
- if(t->next->element < p->next->element) break;
43
+ for(; t->next->element > p->next->element; p=p->next);
40
- }
41
44
 
42
- if(p != t) { //挿入位置発見
43
- cell *next = t->next->next;
45
+ cell *next = t->next->next;
44
- //挿入
46
+ //挿入
45
- t->next->next = p->next;
47
+ t->next->next = p->next;
46
- p->next = t->next;
48
+ p->next = t->next;
47
- //移動させたcellに繋がっていた元のポインタを付け替え
49
+ //移動させたcellに繋がっていた元のポインタを付け替え
48
- t->next = next;
50
+ t->next = next;
49
- } else { //移動無し
50
- t = t->next;
51
- }
52
51
  }
53
52
  }
54
53
 

3

コメント修正

2019/05/16 07:55

投稿

jimbe
jimbe

スコア13357

answer CHANGED
@@ -44,7 +44,7 @@
44
44
  //挿入
45
45
  t->next->next = p->next;
46
46
  p->next = t->next;
47
- //元のtに繋がポインタを付け替え
47
+ //移動させたcellに繋がっていた元のポインタを付け替え
48
48
  t->next = next;
49
49
  } else { //移動無し
50
50
  t = t->next;

2

t を p と同じ動き(対象の一つ前を保持)をするようにしました

2019/05/15 16:15

投稿

jimbe
jimbe

スコア13357

answer CHANGED
@@ -32,25 +32,22 @@
32
32
  cell *t = L->head->next;
33
33
  if(t == NULL) return; //データが無い
34
34
 
35
- cell *prev = t;
36
- t = t->next;
35
+ while(t->next != NULL) {
37
- for(cell *next=NULL; t!=NULL; t=next) {
38
- next = t->next; //次のcell位置を保存しておく
39
-
40
36
  //tまで挿入位置を探す
41
37
  cell *p = L->head;
42
- for( ; p->next!=t; p=p->next) {
38
+ for( ; p!=t; p=p->next) {
43
- if(t->element < p->next->element) break;
39
+ if(t->next->element < p->next->element) break;
44
40
  }
45
41
 
46
- if(p->next != t) { //挿入位置発見
42
+ if(p != t) { //挿入位置発見
43
+ cell *next = t->next->next;
47
44
  //挿入
45
+ t->next->next = p->next;
48
- t->next = p->next;
46
+ p->next = t->next;
49
- p->next = t;
50
47
  //元のtに繋がるポインタを付け替え
51
- prev->next = next;
48
+ t->next = next;
52
- } else { //t は現在位置でOK
49
+ } else { //移動無し
53
- prev = t;
50
+ t = t->next;
54
51
  }
55
52
  }
56
53
  }

1

付け替え時のループを無くしました

2019/05/15 16:08

投稿

jimbe
jimbe

スコア13357

answer CHANGED
@@ -32,6 +32,7 @@
32
32
  cell *t = L->head->next;
33
33
  if(t == NULL) return; //データが無い
34
34
 
35
+ cell *prev = t;
35
36
  t = t->next;
36
37
  for(cell *next=NULL; t!=NULL; t=next) {
37
38
  next = t->next; //次のcell位置を保存しておく
@@ -47,8 +48,9 @@
47
48
  t->next = p->next;
48
49
  p->next = t;
49
50
  //元のtに繋がるポインタを付け替え
50
- for(p=t; p->next!=t; p=p->next);
51
- p->next = next;
51
+ prev->next = next;
52
+ } else { //t は現在位置でOK
53
+ prev = t;
52
54
  }
53
55
  }
54
56
  }