ノードによるリスト構造

質問

「名前と誕生日」のデータベースを作ります．
ユーザが，順番に名前(string型)と誕生日(int型8桁：1998年1月5日なら19980105)を入力します．
その後，誕生日（末尾）が偶数のノードを削除します．
最後に，残った（誕生日が奇数の）データを表示します．
指定の位置に，誕生日が偶数のノードを削除する適切なプログラムを書きなさい

という問題で、回答してデバッグすると
例外がスローされました:読み取りアクセス違反。
current が nullptr でした。
というメッセージが出るのですが、どこをどう修正したらいいのか分かりません。どうすればいいのでしょうか

該当のソースコード

C++
1#include <cstdio>
2#include <iostream>
3using namespace std;
4#include <string>
5
6//ノードの定義
7class Node {
8public:
9	string name;
10	int birthday;
11	Node* next;
12};
13
14int main() {
15	Node* head;					// 先頭ポインタ
16	Node* current;				// 現在ポインタ
17	Node* dummy = new Node();	// 末尾ダミーノード
18	Node* tail = dummy;			// 末尾ポインタ
19
20								//最初のノードの追加処理
21	Node* add = new Node();	//最初に追加するノード
22	head = add;				//先頭は最初の追加ノード
23	cout << "名前は？" << endl;
24	cin >> add->name;
25	cout << "誕生日は？" << endl;
26	cin >> add->birthday;
27	add->next = dummy;		//追加ノードのnextはダミー
28	current = add;			//現在ポインタを追加ポインタに更新
29
30	char ch;				//入力ならy，終了ならn
31	cout << "続けて追加しますか？(y / n)" << endl;
32	cin >> ch;
33
34	//2番目以降のノードの追加処理
35	while (ch == 'y') {
36		Node* add = new Node();	//続けて追加するノード
37		current->next = add;	//現在ポインタのnextは追加ポインタ
38		cout << "名前は？" << endl;
39		cin >> add->name;
40		cout << "誕生日は？" << endl;
41		cin >> add->birthday;
42		add->next = dummy;		//追加ノードのnextはダミー
43		current = add;			//現在ポインタを追加ポインタに更新
44
45		cout << "続けて追加しますか？(y / n)" << endl;
46		cin >> ch;
47	}
48
49	//誕生日が偶数のノードを削除
50	/*ここに適切なプログラムを書きなさい*/
51	Node* Next =NULL;
52	current = head;
53
54	while (current != tail) {
55
56		if (current->birthday % 2 == 0) {
57		if (Next == tail) {
58			tail = current;
59		}
60			Next = current->next;
61			current->next = Next->next;
62			current->name = Next->name;
63			current->birthday = Next->birthday;
64		
65			delete Next;
66		}
67		current = current->next;
68	}
69
70
71	/*ここまで*/
72	//リストの表示
73	current = head;
74	while (current != tail) {
75		cout << "誕生日:" << current->birthday << "，氏名:" << current->name << endl;
76		current = current->next;
77	}
78
79	return 0;
80}
81

行動規範の内容に同意します

回答3件

これでは、末尾要素が%2で割り切れる場合に失敗しますね。

c
1            if (Next == tail){
2                tail = current;
3                delete Next;
4                break;
5            }

をdelete Next;の直前に移動でしょうか

もうひとつ問題として、削除のたびに要素を移動していてはリストのメリットが潰れてしまいます。

c
1Node** now = &head;
2current = head;
3while(current != tail){
4    if(current->birthday % 2 == 0){
5        *now = current->next;
6        delete current;
7    } else {
8        now = &current->next;
9    }
10    current = *now;
11}

なんとなく、一応解説

c
1Node keeper;
2keeper.next = head;
3Node* last = &keeper;
4// last は最後に調べた要素
5while(last->next != tail){
6    current = last->next;
7    if(current->birthday % 2 == 0){
8        // currentの誕生日は偶数なので飛ばす
9        last->next = current->next;
10        delete current;
11        // last->nextを調べてないのでlastを更新しない
12    }
13    else
14        // last->nextを調べたのでlastを更新する
15        last = current;
16}
17head = keeper.next;

片方向リストは先頭要素を指すダミーを作ってしまうと↑のようになります。

よくみると、lastはlast->nextにしか使ってないのでポインタでどうにかなるってのが提示したソースです。

投稿2018/06/21 08:41

編集2018/06/21 23:57

asm

総合スコア15147

takabosoft

2018/06/21 09:08

こんな書き方あるんですね、勉強になります。

asm

2018/06/21 09:11

head番兵作ってしまうか悩んで、結局欲しいのはheadのアドレスだと気づいた感じですね

waribashi

2018/06/21 23:18

ありがとうございます！初めて見た書き方です。勉強になります

waribashi

2018/06/22 14:25

解説ありがとうございます、分かりやすいです

行動規範の内容に同意します

C++
1    while (current != tail) {
2        if (current->birthday % 2 == 0) {
3            if (Next == tail) {
4                tail = current;
5            }
6            Next = current->next;
7            current->next = Next->next;
8            current->name = Next->name;
9            current->birthday = Next->birthday;
10
11            delete Next;
12        }
13        current = current->next;
14    }

このwhileループの中の処理がおかしいです。
current->birthdayが偶数ならcurrentを削除してポインターを付け替える必要がありますが、これではcurrent->nextを削除してしまっています。
また、ポインターを付け替えるだけでいいので、名前や誕生日をコピーする必要はありません。

C++
1Node *prev = head;
2current = head;
3while(current != tail) {
4    if (current->birthday % 2 == 0) {
5        prev->next = current->next;
6        if (current == head) {
7            head = prev->next;
8        }
9        delete current;
10        current = prev->next;
11    }else{
12        prev = current;
13        current = current->next;
14    }
15}

最後にプログラム終了するときには残っているNodeをすべて削除するようにしないと、メモリーリークしてしまいます。、

※一部間違いがあったので修正しました。
※さらに修正。(headが消去対象の場合に落ちてしまう)

投稿2018/06/21 08:23

編集2018/06/25 08:30

PineMatsu

総合スコア3579

waribashi

2018/06/21 23:17

ありがとうございますすみません、一つ質問なのですが、最後に残っているNodeを全て削除するには「delete ノード名;」を残っているノード分すればいいでしょうか？

PineMatsu

2018/06/22 07:51

headからtail、まで検索しながら1つずつ削除すればOKかと。 nextがnullになればそこで終わり。

asm

2018/06/22 09:15

headが消えた時に死にますよ

PineMatsu

2018/06/22 11:05

確かに(-_-;) 消すやつがheadだったらnextをheadにも入れてやらんとイカンですね。

waribashi

2018/06/22 14:27

なるほど、ありがとうございます

行動規範の内容に同意します

ベストアンサー

2018/06/21 17:19 回答を修正します（課題の細かい部分は突っ込まないようにします）。

この課題は、「片方向連結リスト」で末尾に番兵ノード（ダミーノード）が居る事が特徴です。
また、headという先頭ノードがありますが、これは番兵ではなく実データを指しているというところもポイントです。

    if (Next == tail) {
        tail = current;
    }

↑ここですが、tail（末尾の番兵ノード）はリストの終りを示す存在なので、
tailそのものを差し替えることは無いはずです。
差し替える可能性があるのはheadです。

この「片方向連結リスト」で「現在」を削除したい場合は、
「前のデータのnextを現在のnextに繋ぎ変える」という事をします。
ただし、削除対象が先頭データの場合は「前のデータ」は無いので別の処理を行います。

c
1    /*ここに適切なプログラムを書きなさい*/
2    Node* prev = NULL;
3    current = head;
4    while (current != tail) {
5        if (current->birthday % 2 == 0) {
6
7			// currentの削除を行う
8
9			if (current == head) {
10				// 先頭データを消す場合
11				head = current->next;
12				delete current;
13				current = head;
14			} else {
15				// 途中のデータを消す場合
16				prev->next = current->next;
17				delete current;
18				current = prev->next;
19			}
20        } else {
21			prev = current;
22			current = current->next;
23		}
24    }
25
26    /*ここまで*/