データ構造入門

データ構造は効率的なアルゴリズム設計の基盤となる概念です。プログラミングにおける問題解決能力は反復練習によって向上します。

基本概念

データ構造は情報の論理的関係と記憶領域内での配置方法を扱います。主な構成要素：

• データ：計算機で処理可能な情報の表現
• データ要素：データの基本単位（レコード）

データ構造の三側面

1. データ操作：検索、整列、追加、削除、更新
2. 論理構造：要素間の抽象的な関係性
3. 記憶構造：論理構造の物理的実装方法

記憶構造の種類

線形リストの実装

順序リスト

typedef int ElementType;
#define MAX_SIZE 128

typedef struct {
    ElementType elements[MAX_SIZE];
    int last_index;
} SequentialList;

SequentialList* create_list() {
    SequentialList* list = malloc(sizeof(SequentialList));
    memset(list, 0, sizeof(SequentialList));
    list->last_index = -1;
    return list;
}

連結リスト

typedef struct Node {
    int value;
    struct Node* next;
} ListNode;

ListNode* create_node(int val) {
    ListNode* node = malloc(sizeof(ListNode));
    node->value = val;
    node->next = NULL;
    return node;
}

スタックとキューの実装

スタック操作

typedef struct {
    int* items;
    int capacity;
    int top_index;
} ArrayStack;

void push(ArrayStack* s, int item) {
    if (s->top_index < s->capacity - 1) {
        s->items[++s->top_index] = item;
    }
}

キュー操作

typedef struct {
    int items[QUEUE_SIZE];
    int front_idx;
    int rear_idx;
} CircularQueue;

void enqueue(CircularQueue* q, int item) {
    if ((q->rear_idx + 1) % QUEUE_SIZE != q->front_idx) {
        q->items[q->rear_idx] = item;
        q->rear_idx = (q->rear_idx + 1) % QUEUE_SIZE;
    }
}

木構造の操作

二分木走査

typedef struct TreeNode {
    char data;
    struct TreeNode* left_child;
    struct TreeNode* right_child;
} BinaryTree;

void inorder_traversal(BinaryTree* root) {
    if (root) {
        inorder_traversal(root->left_child);
        printf("%c ", root->data);
        inorder_traversal(root->right_child);
    }
}

探索アルゴリズム

ハッシュ表の実装

#define HASH_SIZE 15

typedef struct HashNode {
    int key;
    struct HashNode* next;
} HashEntry;

typedef struct {
    HashEntry* entries[HASH_SIZE];
} HashTable;

void hash_insert(HashTable* table, int key) {
    int slot = key % HASH_SIZE;
    HashEntry* new_entry = malloc(sizeof(HashEntry));
    new_entry->key = key;
    new_entry->next = table->entries[slot];
    table->entries[slot] = new_entry;
}

整列アルゴリズム

クイックソート実装

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
    
    int tmp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = tmp;
    return i+1;
}

void quick_sort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quick_sort(arr, low, pi-1);
        quick_sort(arr, pi+1, high);
    }
}