順序表の基本操作とC言語による実装

順序表（シーケンスリスト）は、メモリ上で連続したアドレス空間を使用してデータを格納する線形リストの一種です。C言語の配列を用いて、このデータ構造の基礎となる操作である位置による検索、値による検索、要素の削除、挿入、そして2つのリストの統合を実装します。

1. 指定位置による要素の取得

順序表では、物理的なメモリ配置が論理的な順序と一致しているため、特定の位置にある要素へのアクセスは計算量O(1)で行うことができます。以下では、1オリジン（1始まり）のインデックスを指定して要素を返す関数を実装します。

#include <stdio.h>
#include <stdlib.h>

#define CAPACITY 100

typedef struct {
    int data[CAPACITY];
    int length;
} LinearList;

int getElement(LinearList list, int pos) {
    if (pos < 1 || pos > list.length) {
        printf("エラー：インデックスが範囲外です。\n");
        exit(1);
    }
    return list.data[pos - 1];
}

int main() {
    LinearList myList = {{10, 20, 30, 40, 50}, 5};
    int targetIndex = 3;
    int result = getElement(myList, targetIndex);
    printf("位置 %d の要素は %d です。\n", targetIndex, result);
    return 0;
}

2. 値による要素の検索

特定の値を持つ要素がリスト内のどの位置にあるかを探索する操作です。先頭から順に比較を行い、一致する要素が見つかった時点でその位置を返します。見つからない場合は0を返します。

#include <stdio.h>

#define CAPACITY 100

typedef struct {
    int data[CAPACITY];
    int length;
} LinearList;

int findPosition(LinearList list, int key) {
    for (int i = 0; i < list.length; i++) {
        if (list.data[i] == key) {
            return i + 1; // 1始まりの位置を返す
        }
    }
    return 0; // 見つからなかった場合
}

int main() {
    LinearList myList = {{99, 88, 77, 66, 55}, 5};
    int searchVal = 77;
    int pos = findPosition(myList, searchVal);
    
    if (pos != 0) {
        printf("値 %d は %d 番目にあります。\n", searchVal, pos);
    } else {
        printf("値 %d は見つかりませんでした。\n", searchVal);
    }
    return 0;
}

3. 要素の削除

指定した値を持つ要素をリストから削除します。削除を行うには、対象の要素を見つけた後、それ以降の全ての要素を1つ前方にシフトさせる必要があります。以下の実装では、一致するすべての要素を削除するロジックを採用しています。

#include <stdio.h>

#define CAPACITY 100

typedef struct {
    int data[CAPACITY];
    int length;
} LinearList;

void removeElements(LinearList *list, int val) {
    int writeIdx = 0;
    for (int readIdx = 0; readIdx < list->length; readIdx++) {
        if (list->data[readIdx] != val) {
            list->data[writeIdx] = list->data[readIdx];
            writeIdx++;
        }
    }
    list->length = writeIdx;
}

void printList(LinearList list) {
    printf("現在のリスト: {");
    for (int i = 0; i < list.length; i++) {
        printf("%d", list.data[i]);
        if (i < list.length - 1) printf(", ");
    }
    printf("}\n");
}

int main() {
    LinearList myList = {{2, 4, 2, 6, 2, 8}, 6};
    printf("削除前: ");
    printList(myList);
    
    removeElements(&myList, 2);
    
    printf("削除後: ");
    printList(myList);
    return 0;
}

4. 要素の挿入

リストの指定した位置に新しい要素を挿入します。挿入位置以降の要素を後方にずらして空き領域を作り、そこに新しい値を書き込みます。リストが満杯である場合や、挿入位置が不正である場合はエラーとなります。

#include <stdio.h>

#define CAPACITY 100
#define SUCCESS 1
#define FAIL 0

typedef struct {
    int data[CAPACITY];
    int length;
} LinearList;

int insertAt(LinearList *list, int index, int value) {
    // インデックスの妥当性チェック（1始まり）
    if (index < 1 || index > list->length + 1) {
        printf("エラー：挿入位置が不正です。\n");
        return FAIL;
    }
    // キャパシティチェック
    if (list->length >= CAPACITY) {
        printf("エラー：リストが満杯です。\n");
        return FAIL;
    }

    // 要素を後ろへシフト
    for (int i = list->length; i >= index; i--) {
        list->data[i] = list->data[i - 1];
    }

    // 挿入実行
    list->data[index - 1] = value;
    list->length++;
    return SUCCESS;
}

void printList(LinearList list) {
    printf("リスト内容: {");
    for (int i = 0; i < list.length; i++) {
        printf("%d", list.data[i]);
        if (i < list.length - 1) printf(", ");
    }
    printf("}\n");
}

int main() {
    LinearList myList = {{1, 3, 5, 7}, 4};
    insertAt(&myList, 3, 100); // 3番目の位置に100を挿入
    printList(myList);
    return 0;
}

5. ソート済み順序表のマージ

2つのソートされた順序表を受け取り、それらをマージして新しい順序表を作成します。それぞれのリストの先頭から要素を比較し、小さい方を新しいリストに追加していくことで、マージ後のリストもソート状態を維持します。

#include <stdio.h>

#define CAPACITY 200

typedef struct {
    int data[CAPACITY];
    int length;
} LinearList;

void mergeSortedLists(LinearList a, LinearList b, LinearList *c) {
    int i = 0, j = 0, k = 0;
    
    // 両方のリストに要素がある限り比較を続ける
    while (i < a.length && j < b.length) {
        if (a.data[i] <= b.data[j]) {
            c->data[k++] = a.data[i++];
        } else {
            c->data[k++] = b.data[j++];
        }
    }

    // リストAの残り要素をコピー
    while (i < a.length) {
        c->data[k++] = a.data[i++];
    }

    // リストBの残り要素をコピー
    while (j < b.length) {
        c->data[k++] = b.data[j++];
    }
    
    c->length = k;
}

void printList(LinearList list) {
    printf("マージ結果: {");
    for (int i = 0; i < list.length; i++) {
        printf("%d", list.data[i]);
        if (i < list.length - 1) printf(", ");
    }
    printf("}\n");
}

int main() {
    LinearList listA = {{1, 4, 7, 9}, 4};
    LinearList listB = {{2, 3, 8, 10, 12}, 5};
    LinearList listC;

    mergeSortedLists(listA, listB, &listC);
    printList(listC);
    
    return 0;
}