回答編集履歴

6

ikedas さんご提案の構造のコードを追加

2022/05/11 19:20

投稿

jimbe
jimbe

スコア12472

test CHANGED
@@ -90,3 +90,79 @@
90
90
  3 1 5
91
91
  5 3 1
92
92
  ```
93
+ ---
94
+ ikedas さんご提案の構造にしてみました。テストも追加。
95
+ ```c
96
+ #include <stdio.h>
97
+ #include <stdlib.h>
98
+
99
+ typedef struct t_node {
100
+ struct t_node *next;
101
+ struct t_node *prev;
102
+ int data;
103
+ } Node;
104
+
105
+ Node *createNode(int data) {
106
+ Node *node = malloc(sizeof(Node));
107
+ if(node == NULL) return NULL; //error
108
+ node->next = NULL;
109
+ node->prev = NULL;
110
+ node->data = data;
111
+ return node;
112
+ }
113
+ //最後に追加
114
+ void addLast(Node **head, Node *node) {
115
+ if(*head == NULL) { //データ無し
116
+ *head = node;
117
+ node->next = node;
118
+ node->prev = node;
119
+ } else {
120
+ node->next = *head;
121
+ node->prev = (*head)->prev;
122
+ node->next->prev = node;
123
+ node->prev->next = node;
124
+ }
125
+ }
126
+
127
+ void print(Node *head) {
128
+ Node *p = head;
129
+ if(p != NULL) {
130
+ do {
131
+ printf("%d ", p->data);
132
+ } while((p = p->next) != head);
133
+ }
134
+ printf("\n");
135
+ }
136
+
137
+ void rotateRight(Node **head) {
138
+ if(*head != NULL) *head = (*head)->next;
139
+ }
140
+ void rotateLeft(Node **head) {
141
+ if(*head != NULL) *head = (*head)->prev;
142
+ }
143
+
144
+ int main(void) {
145
+ Node *head = NULL;
146
+
147
+ addLast(&head, createNode(3));
148
+ addLast(&head, createNode(1));
149
+ addLast(&head, createNode(5));
150
+ print(head);
151
+
152
+ rotateRight(&head); //右へ1回
153
+ print(head);
154
+
155
+ addLast(&head, createNode(7)); //7を追加して
156
+ print(head);
157
+
158
+ rotateLeft(&head); //左へ2回
159
+ rotateLeft(&head);
160
+ print(head);
161
+ }
162
+ ```
163
+ ```plain
164
+ 3 1 5
165
+ 5 3 1
166
+ 5 3 1 7
167
+ 1 7 5 3
168
+ ```

5

追記

2022/05/11 07:50

投稿

jimbe
jimbe

スコア12472

test CHANGED
@@ -1,4 +1,5 @@
1
1
  折角の双方向リストなのですから、 head->prev を使ったり、循環をノードの(先頭と最後で)移動で行ったりしては如何でしょうか。
2
+ (というより、そうしないと双方向リストを使う意味が無いのでは。)
2
3
  ```c
3
4
  #include <stdio.h>
4
5
  #include <stdlib.h>

4

remove したノードのポインタを初期化するように修正

2022/05/11 07:39

投稿

jimbe
jimbe

スコア12472

test CHANGED
@@ -9,11 +9,15 @@
9
9
  int data;
10
10
  } Node;
11
11
 
12
+ void initPointers(Node *node) {
13
+ node->next = node;
14
+ node->prev = node;
15
+ }
16
+
12
17
  Node *createNode(int data) {
13
18
  Node *node = malloc(sizeof(Node));
14
19
  if(node == NULL) return NULL; //error
15
- node->next = node;
20
+ initPointers(node);
16
- node->prev = node;
17
21
  node->data = data;
18
22
  return node;
19
23
  }
@@ -25,7 +29,7 @@
25
29
  last->next = node;
26
30
  head->prev = node;
27
31
  }
28
- //最初に追加
32
+ //先頭に追加
29
33
  void addFirst(Node *head, Node *node) {
30
34
  Node *first = head->next;
31
35
  node->prev = head;
@@ -39,6 +43,7 @@
39
43
  Node *last = head->prev;
40
44
  head->prev = last->prev;
41
45
  last->prev->next = head;
46
+ initPointers(last);
42
47
  return last;
43
48
  }
44
49
  //最初を削除
@@ -47,6 +52,7 @@
47
52
  Node *first = head->next;
48
53
  head->next = first->next;
49
54
  first->next->prev = head;
55
+ initPointers(first);
50
56
  return first;
51
57
  }
52
58
 

3

修正

2022/05/11 07:27

投稿

jimbe
jimbe

スコア12472

test CHANGED
@@ -1,4 +1,4 @@
1
- 折角の双方向リストなのですから、 head->prev を使ったり、循環をノードの(先頭最後)移動で行ったりしては如何でしょうか。
1
+ 折角の双方向リストなのですから、 head->prev を使ったり、循環をノードの(先頭最後)移動で行ったりしては如何でしょうか。
2
2
  ```c
3
3
  #include <stdio.h>
4
4
  #include <stdlib.h>
@@ -25,7 +25,7 @@
25
25
  last->next = node;
26
26
  head->prev = node;
27
27
  }
28
- //先頭に追加
28
+ //最初に追加
29
29
  void addFirst(Node *head, Node *node) {
30
30
  Node *first = head->next;
31
31
  node->prev = head;

2

コード修正(ローテートが逆だった?)

2022/05/11 07:24

投稿

jimbe
jimbe

スコア12472

test CHANGED
@@ -25,6 +25,22 @@
25
25
  last->next = node;
26
26
  head->prev = node;
27
27
  }
28
+ //先頭に追加
29
+ void addFirst(Node *head, Node *node) {
30
+ Node *first = head->next;
31
+ node->prev = head;
32
+ node->next = first;
33
+ head->next = node;
34
+ first->prev = node;
35
+ }
36
+ //最後を削除
37
+ Node *removeLast(Node *head) {
38
+ if(head->prev == head) return NULL;
39
+ Node *last = head->prev;
40
+ head->prev = last->prev;
41
+ last->prev->next = head;
42
+ return last;
43
+ }
28
44
  //最初を削除
29
45
  Node *removeFirst(Node *head) {
30
46
  if(head->next == head) return NULL;
@@ -41,6 +57,10 @@
41
57
  printf("\n");
42
58
  }
43
59
 
60
+ void rotateRight(Node *head) {
61
+ Node *last = removeLast(head);
62
+ if(last != NULL) addFirst(head, last);
63
+ }
44
64
  void rotateLeft(Node *head) {
45
65
  Node *first = removeFirst(head);
46
66
  if(first != NULL) addLast(head, first);
@@ -54,11 +74,12 @@
54
74
  addLast(head, createNode(5));
55
75
  print(head);
56
76
 
77
+ //rotateLeft(head);
57
- rotateLeft(head);
78
+ rotateRight(head);
58
79
  print(head);
59
80
  }
60
81
  ```
61
82
  ```plain
62
83
  3 1 5
63
- 1 5 3
84
+ 5 3 1
64
85
  ```

1

追加

2022/05/11 07:14

投稿

jimbe
jimbe

スコア12472

test CHANGED
@@ -58,3 +58,7 @@
58
58
  print(head);
59
59
  }
60
60
  ```
61
+ ```plain
62
+ 3 1 5
63
+ 1 5 3
64
+ ```