Q&A
詳しい説明ありがとうございます。
先に末尾のノードを探索した方が条件処理をするのに楽にできるということを知れてよかったです。
しかし、このリストについて自分の理解不足がありまして、一つ質問したいのですが、
どうしてt->prev->nextとはどこを指しているのでしょうか。私の解釈としては末尾の前のノードの次のノードと読み取れますので結局自分自身という解釈に至るのですがそれでよろしいのでしょうか。
こちらのソースコードは単方向連結リストです。このソースコードを双方向連結リストに拡張してノードを末尾に挿入する方法が分かりません。どなたか説明込みで教えていただけませんか。
/*
- list2.c: 片方向連結リストの例プログラム
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
/* 連結リスト中のノードの構造体 /
struct node {
int val; / 値 */
struct node next; / 次ノード */
struct node *prev;/前ノード/
};
/* セルとそのポインタの型 */
typedef struct node Node;
typedef Node *NodePtr;
/* セルを一つ生成 */
NodePtr create_node(int v) {
NodePtr n = NULL;
n = malloc(sizeof(Node)); n->val = v; n->next = NULL; return n;
}
/* セルを表示 */
void print_node(NodePtr n) {
if (n != NULL) {
printf("<%d>", n->val);
}
else {
printf("(null)");
}
}
/* 連結リストの構造体 /
struct list {
/ 先頭セルへのポインタ */
NodePtr head;
};
/* 連結リストとそのポインタの型 */
typedef struct list List;
typedef List *ListPtr;
/* 空の連結リストを生成 */
ListPtr create_list(void) {
ListPtr l = NULL;
l = malloc(sizeof(List));
l->head = NULL;
return l;
}
/* 連結リスト l が空かどうか判定 */
int is_empty(ListPtr l) {
return (l->head == NULL);
}
/* リスト l の内容を表示 */
void print_list(ListPtr l) {
NodePtr n = NULL;
if (is_empty(l)) { printf("(empty)\n"); return; } n = l->head; while (n != NULL) { print_node(n); n = n->next; } printf("\n");
}
/* リスト l の先頭にセルを挿入 */
void add_first(ListPtr l, int val) {
NodePtr n = NULL;
n = create_node(val);
n->next = l->head;
l->head = n;
}
/* リスト l の先頭セルを削除 */
int delete_first(ListPtr l) {
NodePtr n = NULL;
int v;
/* リストが空なら -1 を返す（負の値はリストに含まれないと仮定）*/ if (is_empty(l)) return -1; v = l->head->val; n = l->head; l->head = l->head->next; free(n); n = NULL; return v;
}
/* 連結リスト l のサイズを取得 */
int get_list_size(ListPtr l) {
NodePtr n = NULL;
int size;
size = 0; n = l->head; while (n != NULL) { size++; n = n->next; } return size;
}
/*
- 連結リスト l における index 番目のセルの値を取得
- （そのようなセルが存在しなければ -1 を返す）
*/
int get_value(ListPtr l, int index) {
NodePtr n = NULL;
if (index < 0) return -1;
n = l->head; while (index > 0 && n != NULL) { n = n->next; index--; } return (n == NULL) ? -1 : n->val;
}
/* リスト l 中の全セルを削除（ループ版）*/
void delete_all(ListPtr l) {
NodePtr n = NULL, m = NULL;
n = l->head; while (n != NULL) { m = n; n = n->next; free(m); } l->head = NULL;
}
/* セル n 以降を全て削除（内部処理用の再帰関数）*/
void delete_rest(NodePtr n) {
if (n->next != NULL) delete_rest(n->next);
free(n);
}
/* リスト l 中の全セルを削除（再帰版）*/
void delete_all_recursively(ListPtr l) {
if (l->head == NULL) return;
delete_rest(l->head);
l->head = NULL;
}
/* リスト l 全体を削除 */
#define delete_list(l) (delete_list0(l),l=NULL)
void delete_list0(ListPtr l) {
delete_all(l);
free(l);
}
/* リスト l の末尾にセルを挿入 /
void add_last(ListPtr l, int val) {
/ 課題3:ここに正しい実行内容を書く! */
}
/* リスト l の末尾セルを削除 /
int delete_last(ListPtr l) {
/ 課題3:ここに正しい実行内容を書く! */
return -1;
}
/* 連結リストの使用例 */
int main(void) {
FILE *fp = NULL;
char buf[10];
int age;
ListPtr l = NULL;
l = create_list(); add_last(l, 28); add_last(l, 40); add_last(l, 33); add_last(l, 15); print_list(l); delete_last(l); print_list(l); delete_last(l); print_list(l); delete_last(l); print_list(l); delete_last(l); print_list(l); return 0;
}
回答2件
0
末尾に追加する場合、
ListPtr *allow; こいつを作り
TOPからnextポインタを参照してどんどこ下っていきnext=NULLの場所へ追加する
allow = ListPtr; このソースの場合mainのlがtopですね。
//末尾を探す
if( allow->next != NULL )
allow = allow->next;
else
末尾なので、
allow->next = &newList;
newList->bifor = &allow;
newList->next = NULL;
て感じですね。
もっと解りやすくするのでしたら、あらかじめtopとtailをつないでおくのも手です。
ListPtr top;
ListPtr tail;
top->bifor = NULL;
top->next = tail;
tail->bifor = top;
tail->next = NULL;
topとtailを繋いでおけば、次から新しいListPtrを作って挿入する場合
必ずtop+tailの間になると考えられるので、色々と処理が楽になります。
投稿2015/06/20 13:04
総合スコア1021
0
ベストアンサー
こんなんいかがでしょう。
lang
1#include <stdio.h> 2#include <stdlib.h> 3#include <assert.h> 4 5/* 連結リスト中のノードの構造体 */ 6struct node { 7 int val; /* 値 */ 8 struct node *next; /* 次ノード */ 9 struct node *prev; /* 前ノード */ 10}; 11 12/* セルとそのポインタの型 */ 13typedef struct node Node; 14typedef Node *NodePtr; 15 16/* セルを一つ生成 */ 17NodePtr create_node(int v) { 18 NodePtr n = NULL; 19 20 n = malloc(sizeof(Node)); 21 n->val = v; 22 n->next = NULL; 23 n->prev = NULL; 24 25 return n; 26} 27 28/* セルを表示 */ 29void print_node(NodePtr n) { 30 if(n != NULL) { 31 printf("<%d>", n->val); 32 } 33 else { 34 printf("(null)"); 35 } 36} 37 38/* 連結リストの構造体 */ 39struct list { 40 /* 先頭セルへのポインタ */ 41 NodePtr head; 42}; 43 44/* 連結リストとそのポインタの型 */ 45typedef struct list List; 46typedef List *ListPtr; 47 48/* 空の連結リストを生成 */ 49ListPtr create_list(void) { 50 ListPtr l = NULL; 51 l = malloc(sizeof(List)); 52 l->head = NULL; 53 return l; 54} 55 56/* 連結リスト l が空かどうか判定 */ 57int is_empty(ListPtr l) { 58 return (l->head == NULL); 59} 60 61/* リスト l の内容を表示 */ 62void print_list(ListPtr l) { 63 NodePtr n = NULL; 64 65 if (is_empty(l)) { 66 printf("(empty)\n"); 67 return; 68 } 69 70 n = l->head; 71 while (n != NULL) { 72 print_node(n); 73 n = n->next; 74 } 75 printf("\n"); 76} 77 78/* リスト l の先頭にセルを挿入 */ 79void add_first(ListPtr l, int val) { 80 NodePtr n = NULL; 81 n = create_node(val); 82 n->next = l->head; 83 84 if(l->head != NULL) { 85 l->head->prev = n; 86 } 87 l->head = n; 88} 89 90/* リスト l の先頭セルを削除 */ 91int delete_first(ListPtr l) { 92 NodePtr n = NULL; 93 int v; 94 95 /* リストが空なら -1 を返す（負の値はリストに含まれないと仮定）*/ 96 if (is_empty(l)) return -1; 97 98 v = l->head->val; 99 n = l->head; 100 l->head = l->head->next; 101 free(n); 102 n = NULL; 103 104 if(l->head != NULL) { 105 l->head->prev = NULL; 106 } 107 return v; 108} 109 110/* 連結リスト l のサイズを取得 */ 111int get_list_size(ListPtr l) { 112 NodePtr n = NULL; 113 int size; 114 115 size = 0; 116 n = l->head; 117 while (n != NULL) { 118 size++; 119 n = n->next; 120 } 121 return size; 122} 123 124/* 125 * 連結リスト l における index 番目のセルの値を取得 126 * （そのようなセルが存在しなければ -1 を返す） 127 */ 128int get_value(ListPtr l, int index) { 129 NodePtr n = NULL; 130 if (index < 0) return -1; 131 132 n = l->head; 133 while (index > 0 && n != NULL) { 134 n = n->next; 135 index--; 136 } 137 138 return (n == NULL) ? -1 : n->val; 139} 140 141/* リスト l 中の全セルを削除（ループ版）*/ 142void delete_all(ListPtr l) { 143 NodePtr n = NULL, m = NULL; 144 145 n = l->head; 146 while (n != NULL) { 147 m = n; 148 n = n->next; 149 free(m); 150 } 151 152 l->head = NULL; 153} 154 155/* セル n 以降を全て削除（内部処理用の再帰関数）*/ 156void delete_rest(NodePtr n) { 157 if (n->next != NULL) delete_rest(n->next); 158 free(n); 159} 160 161/* リスト l 中の全セルを削除（再帰版）*/ 162void delete_all_recursively(ListPtr l) { 163 if (l->head == NULL) return; 164 delete_rest(l->head); 165 l->head = NULL; 166} 167 168/* リスト l 全体を削除 */ 169#define delete_list(l) (delete_list0(l),l=NULL) 170void delete_list0(ListPtr l) { 171 delete_all(l); 172 free(l); 173} 174 175/* 末尾のセルを取得 */ 176NodePtr getTail(ListPtr l) { 177 NodePtr n = l->head; 178 179 if(n == NULL) { 180 return NULL; 181 } 182 while(n->next != NULL) { 183 n = n->next; 184 } 185 return n; 186} 187 188/* リスト l の末尾にセルを挿入 */ 189void add_last(ListPtr l, int val) { 190 NodePtr t = getTail(l); 191 NodePtr n = NULL; 192 193 /* リストが空なら先頭に追加と同じ */ 194 if(t == NULL) { 195 add_first(l, val); 196 return; 197 } 198 n = create_node(val); 199 t->next = n; 200 n->prev = t; 201} 202 203/* リスト l の末尾セルを削除 */ 204int delete_last(ListPtr l) { 205 NodePtr t = getTail(l); 206 int v; 207 208 /* リストが空なら -1 を返す（負の値はリストに含まれないと仮定）*/ 209 if(t == NULL) return -1; 210 211 /* リストが要素数1なら先頭を削除と同じ */ 212 if(t->prev == NULL) { 213 return delete_first(l); 214 } 215 v = t->val; 216 t->prev->next = NULL; 217 free(t); 218 219 return v; 220} 221 222/* 連結リストの使用例 */ 223int main(void) { 224 ListPtr l = NULL; 225 l = create_list(); 226 227 print_list(l); 228 229 add_last(l, 28); print_list(l); 230 add_last(l, 40); print_list(l); 231 add_last(l, 33); print_list(l); 232 add_last(l, 15); print_list(l); 233 234 delete_last(l); print_list(l); 235 delete_last(l); print_list(l); 236 delete_last(l); print_list(l); 237 delete_last(l); print_list(l); 238 239 return 0; 240}
投稿2015/06/20 13:07
総合スコア159
はい、そのとおりです。
蛇足になりますが、t->prev->next は、tの1つ前のノード（つまり新しい最後のノード）の自分自身へのポインタになります。これを NULL にしておかないと、最後のノードの次のノードへのポインタが t のままになってしまいます。最後のノードの next は NULL でなければなりません。
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。