ALDS1_3_C 双方向連結リストをC++で解いてみた[AIZU ONLINE JUDGE]

AIZU ONLINE JUDGE

こんにちは! mnbd(@mnbbbbbd)です。

プログラミング初心者なので、もっといい回答があるに違いありません。

あくまでも「動作はする」サンプルとしてご覧ください。

問題文

以下の命令を受けつける双方向連結リストを実装してください。

・insert x: 連結リストの先頭にキー x を持つ要素を継ぎ足す。
・delete x: キー x を持つ最初の要素を連結リストから削除する。そのような要素が存在しない場合は何もしない。
・deleteFirst: リストの先頭の要素を削除する。
・deleteLast: リストの末尾の要素を削除する。

入力
入力は以下の形式で与えられます。

n
command1
command2
...
commandn

最初の行に命令数 n が与えられます。続く n 行に命令が与えられる。命令は上記4つの命令のいずれかです。キーは整数とします。

出力
全ての命令が終了した後の、連結リスト内のキーを順番に出力してください。連続するキーは1つの空白文字で区切って出力してください。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/3/ALDS1_3_C

解答

#include <bits/stdc++.h>
using namespace std;

struct cell {
    cell *prev;
    cell *next;
    long value;
};

class Doubly_linked_list {
    cell *nil;

  public:
    Doubly_linked_list() {
        nil = new cell;
        nil->prev = nil;
        nil->next = nil;
    }

    cell *list_search(int x) {
        cell *c = nil->next;
        while(c != nil && c->value != x) {
            c = c->next;
        }
        return c;
    }

    void print_list() {
        cell *c = nil->next;
        bool is_flag = true;
        while(true) {
            if(c == nil) {
                break;
            }
            if(is_flag == false) {
                cout << " ";
            }
            cout << c->value;
            c = c->next;
            is_flag = false;
        }
        cout << endl;
    }

    void insert(int x) {
        cell *c = new cell;
        c->value = x;
        c->prev = nil;
        c->next = nil->next;
        nil->next->prev = c;
        nil->next = c;
    }

    void delete_cell(cell *c) {
        if(c == nil) {
            return;
        }
        c->prev->next = c->next;
        c->next->prev = c->prev;
        delete c;
    }

    void delete_first() {
        delete_cell(nil->next);
    }

    void delete_last() {
        delete_cell(nil->prev);
    }

    void delete_value(int x) { delete_cell(list_search(x)); }
};

int main() {
    long n;
    cin >> n;
    Doubly_linked_list l;
    string str;
    for(int i = 0; i < n; i++) {
        cin >> str;
        if(str[0] == 'i') {
			int x;
			cin >> x;	
            l.insert(x);
        } else if(str[6] == 'F') {
            l.delete_first();
		} else if (str[6] == 'L') {
			l.delete_last();
        } else {
			int x;
			cin >> x;
            l.delete_value(x);
        }
    }

    l.print_list();
    return 0;
}

感想

双方向連結リストの問題ですが、これまでの問題が参考にはならずに苦労しました。

リスト構造についてわからずに一般解説を見ました。

ポインタについても慣れておく必要がありましたね。

最初は実行時間オーバーで合格できませんでした。

原因はfor文の中でstring strを宣言していたこと。

できるだけスコープを狭めるクセがついていたのですが、宣言をどこでするかで実行時間に大きな差があることを知ったのは収穫でした。

まとめ

AIZU ONLINE JUDGEの「ALDS1_3_C 双方向連結リスト」を解いてみましたので、その回答と解説をご紹介いたしました。

少しずつですが、プログラミングの勉強をしています。
まだ初心者ですが、よかったらつながっていただけると嬉しいです。
Twitterアカウント(@mnbbbbbd

以上です。
読んでいただきありがとうございました!