配列とリスト

配列はメモリ上で連続しているので
array[0]やarray[5]のようなアクセスできる。
ただし、当然サイズを超えてアクセスするとエラーになる。

と思いきや手元のC++ではエラーにならなかった。
ここにある通り、

"It is left undefined what happens if you go out of bounds"

ということか。そういうもんなのか、意外。しかし

"there is no guarantee that it'll still work the next time you run the program."

とあるので意識して書く方が良い（当然）。

それは置いといて、今日も遊ぶ。
配列が一杯になったら2倍のサイズの配列を生成して中身を入れ替える。

int main() {
    int input, size, cnt;
    int *temp, *array;
    cnt = 0;
    size = 10;
    array = (int *)malloc(sizeof(int) * size);
    do {
        cout << "Input number you like (0 for finsh) ";
        cin >> input;
        array[cnt] = input;
        cnt++;
        if (cnt == size) {
            temp = (int *)malloc(sizeof(int) * size * 2);
            memcpy(temp, array, sizeof(int) * size);
            free(array);
            array = temp;
            size *= 2;
        }
    } while (input != 0);
    for (int i = 0; i < size; i++) {
        cout << array[i] << " ";
    }
    cout << endl;
}

これを頻繁にやる場合には効率あまり良くない。ということでリストを考える。
リストはノードを連結したものということでノードはこんな構造体。

typedef struct tagListNode {
    struct tagListNode *prev;
    struct tagListNode *next;
    int data;
} ListNode;

prevは前ノードへのポインタ、nextは次ノードへのポインタ、dataはデータ。
次のコードは入力値を元にノードを作成し、リストへどんどん追加する。

   do {
        cout << "input new data (0 for end) : ";
        cin >> buf;
        if (buf) {
            newNode = (ListNode *)malloc(sizeof(ListNode));
            newNode->data = buf;
            newNode->next = NULL;

            if (lastNode != NULL) {
                lastNode->next = newNode;
                newNode->prev = lastNode;
                lastNode = newNode;
            } else {
                firstNode = lastNode = newNode;
                newNode->prev = NULL;
            }
        }
    } while (buf != 0);

そして、リストに入力値が含まれるか探索する。

    do {
        cout << "input search number (0 for end) : ";
        cin >> buf;
        if (buf) {
            for (thisNode = firstNode; thisNode != NULL; thisNode = thisNode->next) {
                if (thisNode->data == buf) {
                    cout << buf << " is found." << endl;
                }
            }
        }
    } while (buf != 0);

結局何が嬉しいのかという話。ポインタの付け替えを行えば良いだけなので値の追加や削除が簡単。厳密にはメモリーの解放が必要だけど。例えば、検索した値がリストに含まれる場合、最初のノードとする為のコード。例えば配列の自己組織化探索の例だと一番先頭に持ってくることは効率を悪くするが、リストだと効率を損なうこと無く実現できる。

    do {
        cout << "--- current sequence ---" << endl;
        for (thisNode = firstNode; thisNode != NULL; thisNode = thisNode->next) {
            cout << thisNode->data << " ";
            sum += thisNode->data;
        }
        cout << endl;

        cout << "input search number (0 for end) : ";
        cin >> buf;
        if (buf) {
            for (thisNode = firstNode; thisNode != NULL; prevNode = thisNode, thisNode = thisNode->next) {
                if (thisNode->data == buf) {
                    cout << buf << " is found." << endl;
                    if (thisNode != firstNode) {
                        prevNode->next = thisNode->next;
                        if (lastNode == thisNode)
                            lastNode = prevNode;
                        thisNode->next = firstNode;
                        firstNode = thisNode;
                    }
                    break;
                }
            }
            if (thisNode == NULL) 
                cout << buf << " is not found in list." << endl;
        }
    } while (buf != 0);

以上。

でもまさかこれ↓がコンパイルできて実行できるとは思わなかったな

#include 

using namespace std;

int main() {
    int *array = new int[3];
    array[0] = 0;
    array[1] = 1;
    array[2] = 2;
    array[3] = 3;
    array[4] = 4;
    array[5] = 5;
    for (int i = 0; i < 6; i++)
        cout << array[i] << endl;
    return 1;
}