質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.48%

  • C++

    3589questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

ノードによるリスト構造

解決済

回答 3

投稿

  • 評価
  • クリップ 0
  • VIEW 412

waribashi

score 13

 質問

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

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

 該当のソースコード

#include <cstdio>
#include <iostream>
using namespace std;
#include <string>

//ノードの定義
class Node {
public:
    string name;
    int birthday;
    Node* next;
};

int main() {
    Node* head;                    // 先頭ポインタ
    Node* current;                // 現在ポインタ
    Node* dummy = new Node();    // 末尾ダミーノード
    Node* tail = dummy;            // 末尾ポインタ

                                //最初のノードの追加処理
    Node* add = new Node();    //最初に追加するノード
    head = add;                //先頭は最初の追加ノード
    cout << "名前は?" << endl;
    cin >> add->name;
    cout << "誕生日は?" << endl;
    cin >> add->birthday;
    add->next = dummy;        //追加ノードのnextはダミー
    current = add;            //現在ポインタを追加ポインタに更新

    char ch;                //入力ならy,終了ならn
    cout << "続けて追加しますか?(y / n)" << endl;
    cin >> ch;

    //2番目以降のノードの追加処理
    while (ch == 'y') {
        Node* add = new Node();    //続けて追加するノード
        current->next = add;    //現在ポインタのnextは追加ポインタ
        cout << "名前は?" << endl;
        cin >> add->name;
        cout << "誕生日は?" << endl;
        cin >> add->birthday;
        add->next = dummy;        //追加ノードのnextはダミー
        current = add;            //現在ポインタを追加ポインタに更新

        cout << "続けて追加しますか?(y / n)" << endl;
        cin >> ch;
    }

    //誕生日が偶数のノードを削除
    /*ここに適切なプログラムを書きなさい*/
    Node* Next =NULL;
    current = head;

    while (current != tail) {

        if (current->birthday % 2 == 0) {
        if (Next == tail) {
            tail = current;
        }
            Next = current->next;
            current->next = Next->next;
            current->name = Next->name;
            current->birthday = Next->birthday;

            delete Next;
        }
        current = current->next;
    }


    /*ここまで*/
    //リストの表示
    current = head;
    while (current != tail) {
        cout << "誕生日:" << current->birthday << ",氏名:" << current->name << endl;
        current = current->next;
    }

    return 0;
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

+2

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

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


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

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

Node** now = &head;
current = head;
while(current != tail){
    if(current->birthday % 2 == 0){
        *now = current->next;
        delete current;
    } else {
        now = &current->next;
    }
    current = *now;
}

なんとなく、一応解説

Node keeper;
keeper.next = head;
Node* last = &keeper;
// last は最後に調べた要素
while(last->next != tail){
    current = last->next;
    if(current->birthday % 2 == 0){
        // currentの誕生日は偶数なので飛ばす
        last->next = current->next;
        delete current;
        // last->nextを調べてないのでlastを更新しない
    }
    else
        // last->nextを調べたのでlastを更新する
        last = current;
}
head = keeper.next;

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

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/06/21 18:08

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

    キャンセル

  • 2018/06/21 18:11

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

    キャンセル

  • 2018/06/22 08:18

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

    キャンセル

  • 2018/06/22 23:25

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

    キャンセル

checkベストアンサー

0

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

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

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

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

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

    /*ここに適切なプログラムを書きなさい*/
    Node* prev = NULL;
    current = head;
    while (current != tail) {
        if (current->birthday % 2 == 0) {

            // currentの削除を行う

            if (current == head) {
                // 先頭データを消す場合
                head = current->next;
                delete current;
                current = head;
            } else {
                // 途中のデータを消す場合
                prev->next = current->next;
                delete current;
                current = prev->next;
            }
        } else {
            prev = current;
            current = current->next;
        }
    }

    /*ここまで*/

あんまりテストしていませんが、大体こんな感じで動くのではないかと思います。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/06/21 17:05

    あ、これそもそも「//誕生日が偶数のノードを削除 」部分だけを書く課題なんですかね。他にもいろいろ突っ込みどころはありますが、気にしない方がいいのかな・・・。

    キャンセル

  • 2018/06/21 17:27

    dummyとtailが同じオブジェクトを指しているというのは無駄(冗長)かもしれませんが、間違いではないのでは?
    (まあ、混乱のもとにはなるかもしれませんが)

    キャンセル

  • 2018/06/21 17:35

    あ、そうなんですか、自分なら書かないですけど、まあ間違いとまで言わなくても良いですかね。

    キャンセル

  • 2018/06/21 17:44

    /*ここに適切なプログラムを書きなさい*/
    とあるので、その上の部分は課題で与えられた部分でしょう。ならば、指摘は課題を出した先生にすべきかも(笑)

    キャンセル

  • 2018/06/21 17:56

    そうなんですよw、PineMatsuさんもおっしゃっているメモリリークの件も質問者の書いたコードではなさそうなので、突っ込むだけ無駄かなとか(^_^;)

    キャンセル

  • 2018/06/21 18:02

    後処理まで書かせようとする意図かもしれません。なのでそこはなんともですね。

    キャンセル

  • 2018/06/22 08:14

    ありがとうございます!
    takebosoftさんの仰る通り、誕生日が偶数のノードを削除部分だけ書く課題です。それ以外の部分は先生が書いたものですね……

    キャンセル

0

    while (current != tail) {
        if (current->birthday % 2 == 0) {
            if (Next == tail) {
                tail = current;
            }
            Next = current->next;
            current->next = Next->next;
            current->name = Next->name;
            current->birthday = Next->birthday;

            delete Next;
        }
        current = current->next;
    }


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

Node *prev = head;
current = head;
while(current != tail) {
    if (current->birthday % 2 == 0) {
        prev->next = current->next;
        if (current == head) {
            head = prev->next;
        }
        delete current;
        current = prev->next;
    }else{
        prev = current;
        current = current->next;
    }
}

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

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/06/22 08:17

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

    キャンセル

  • 2018/06/22 16:51

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

    キャンセル

  • 2018/06/22 18:15

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

    キャンセル

  • 2018/06/22 20:05

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

    キャンセル

  • 2018/06/22 23:27

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

    キャンセル

関連した質問

同じタグがついた質問を見る

  • C++

    3589questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。