データ構造の基本：線形リストとその応用

現代のソフトウェア開発において、データを効率的に管理するための手法は不可欠です。特に、一連の要素を順序立てて扱う必要がある場合、線形データ構造が広く利用されます。代表的な例として、配列に基づく動的配列（Dynamic Array）があり、これはC言語でのメモリ管理を活かして柔軟なデータ格納を実現します。

線形リストの特性

• 論理的連続性：要素間には前後関係があり、先頭から末尾まで一直線上に並ぶ。
• 物理的配置の自由度：メモリ上では連続している場合もあれば（配列）、非連続の場合もある（連結リスト）。

動的配列の設計思想

静的配列はサイズがコンパイル時に固定されるため、実行中にデータ量が変動するアプリケーションには不向きです。これに対し、動的配列は必要なときにヒープ領域からメモリを確保し、必要に応じて拡張することで、柔軟なデータ管理を可能にします。

主な特徴

• ポインタによるヒープメモリの動的確保（malloc, realloc）
• 現在の要素数（size）と割当容量（capacity）の分離管理
• 挿入時における自動リサイズ機構

課題点

• 先頭または中間への挿入・削除はO(n)の計算量を要する
• リサイズ時には新しい領域の確保、コピー、旧領域の解放が発生
• 倍々での容量増加により、最大で約50%の未使用領域が生じる可能性がある

動的配列の実装

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

#define DEFAULT_CAPACITY 4

typedef struct {
    char name[100];
    char gender[4];
    int age;
    char phone[11];
    char address[100];
} ContactItem;

typedef struct {
    ContactItem* data;
    int size;
    int capacity;
} DynamicArray;

void InitArray(DynamicArray* arr) {
    assert(arr);
    arr->data = NULL;
    arr->size = 0;
    arr->capacity = 0;
}

void DestroyArray(DynamicArray* arr) {
    assert(arr);
    free(arr->data);
    arr->data = NULL;
    arr->size = arr->capacity = 0;
}

static void ResizeIfNeeded(DynamicArray* arr) {
    assert(arr);
    if (arr->size == arr->capacity) {
        int new_cap = (arr->capacity == 0) ? DEFAULT_CAPACITY : arr->capacity * 2;
        ContactItem* temp = (ContactItem*)realloc(arr->data, new_cap * sizeof(ContactItem));
        if (!temp) {
            perror("Memory allocation failed");
            exit(EXIT_FAILURE);
        }
        arr->data = temp;
        arr->capacity = new_cap;
    }
}

void PushBack(DynamicArray* arr, const ContactItem* item) {
    assert(arr && item);
    ResizeIfNeeded(arr);
    arr->data[arr->size++] = *item;
}

void PopBack(DynamicArray* arr) {
    assert(arr);
    if (arr->size > 0) arr->size--;
}

int FindByName(const DynamicArray* arr, const char* name) {
    assert(arr && name);
    for (int i = 0; i < arr->size; ++i) {
        if (strcmp(arr->data[i].name, name) == 0) return i;
    }
    return -1;
}

void PrintAll(const DynamicArray* arr) {
    assert(arr);
    if (arr->size == 0) {
        printf("連絡先は空です。\n");
        return;
    }
    for (int i = 0; i < arr->size; ++i) {
        printf("【%d】名前: %s, 性別: %s, 年齢: %d, 電話: %s, 住所: %s\n",
               i + 1,
               arr->data[i].name,
               arr->data[i].gender,
               arr->data[i].age,
               arr->data[i].phone,
               arr->data[i].address);
    }
}

連絡先管理システムの構築

上記の動的配列を基盤として、ユーザーの個人情報を管理する連絡先アプリケーションを構築できます。このシステムはファイル永続化機能も備えています。

主要機能

• 新規連絡先の追加（重複チェック付き）
• 名前による検索
• 情報の編集（項目別選択式UI）
• 削除操作
• 一覧表示
• バイナリ形式での保存／読み込み

永続化処理の実装

void SaveToFile(const DynamicArray* arr, const char* filename) {
    FILE* fp = fopen(filename, "wb");
    if (!fp) {
        perror("File open error");
        return;
    }
    fwrite(&arr->size, sizeof(int), 1, fp);
    fwrite(arr->data, sizeof(ContactItem), arr->size, fp);
    fclose(fp);
    printf("データを '%s' に保存しました。\n", filename);
}

void LoadFromFile(DynamicArray* arr, const char* filename) {
    FILE* fp = fopen(filename, "rb");
    if (!fp) return;

    int count;
    fread(&count, sizeof(int), 1, fp);
    for (int i = 0; i < count; ++i) {
        ContactItem item;
        if (fread(&item, sizeof(ContactItem), 1, fp) == 1) {
            PushBack(arr, &item);
        }
    }
    fclose(fp);
    printf("'%s' からデータを読み込みました。\n", filename);
}

ユーザーインターフェース

void ShowMenu() {
    printf("\n=== 連絡先管理システム ===\n");
    printf("1. データ読み込み\n");
    printf("2. 新規追加\n");
    printf("3. 削除\n");
    printf("4. 一覧表示\n");
    printf("5. 検索\n");
    printf("6. 編集\n");
    printf("7. 保存\n");
    printf("0. 終了\n");
    printf("選択: ");
}

int main() {
    DynamicArray contacts;
    InitArray(&contacts);
    int choice;

    while (1) {
        ShowMenu();
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                LoadFromFile(&contacts, "contacts.dat");
                break;
            case 2: {
                ContactItem item;
                printf("名前: "); scanf("%s", item.name);
                if (FindByName(&contacts, item.name) != -1) {
                    printf("エラー: 同じ名前の連絡先が既に存在します。\n");
                    break;
                }
                printf("性別: "); scanf("%s", item.gender);
                printf("年齢: "); scanf("%d", &item.age);
                printf("電話: "); scanf("%s", item.phone);
                printf("住所: "); scanf("%s", item.address);
                PushBack(&contacts, &item);
                printf("追加完了。\n");
                break;
            }
            case 3: {
                char name[100];
                printf("削除対象の名前: ");
                scanf("%s", name);
                int idx = FindByName(&contacts, name);
                if (idx == -1) {
                    printf("該当なし。\n");
                } else {
                    for (int i = idx; i < contacts.size - 1; ++i) {
                        contacts.data[i] = contacts.data[i + 1];
                    }
                    contacts.size--;
                    printf("削除完了。\n");
                }
                break;
            }
            case 4:
                PrintAll(&contacts);
                break;
            case 0:
                SaveToFile(&contacts, "contacts.dat");
                DestroyArray(&contacts);
                printf("終了します。\n");
                return 0;
            default:
                printf("無効な選択です。\n");
                break;
        }
    }
}