【C言語】第8章第10回：データ構造を活用した実用的なプログラム

これまで学んだデータ構造（スタック、キュー、リンクリスト、ツリー、ハッシュテーブルなど）を統合して、実用的なプログラムを作成します。

0. 記事の概要

この記事を読むメリット

• 実践的なスキルの習得：複数のデータ構造を組み合わせたプログラムの設計方法を学べます。
• 効率的な問題解決：適切なデータ構造を選び、プログラムの効率を向上させる技術を習得します。
• 応用力の向上：リアルなプログラミング問題に対処する能力を養います。

この記事で学べること

• データ構造を活用したプログラムの設計方法
• 各データ構造の統合と応用例
• プログラムの実装と動作の詳細な解説

1. プロジェクト概要

1.1 プロジェクトの目的

データ構造を活用して、タスク管理アプリケーションを作成します。このアプリケーションでは、タスクの追加、削除、優先度による並び替えを行います。

1.2 使用するデータ構造

• リンクリスト：タスクの格納
• スタック：削除されたタスクの履歴管理
• ハッシュテーブル：タスクの検索
• 優先度付きキュー：タスクの優先度管理

1.3 プログラムの機能

• タスクの追加
• タスクの削除
• タスクの優先度順並び替え
• 削除済みタスクの履歴表示

2. プログラムの設計と実装

2.1 データ構造の定義

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

#define TABLE_SIZE 10

// タスクノード
typedef struct Task {
    int id;
    char description[100];
    int priority;
    struct Task* next;
} Task;

// スタックノード
typedef struct Stack {
    char taskDescription[100];
    struct Stack* next;
} Stack;

// ハッシュテーブルノード
typedef struct HashTable {
    Task* table[TABLE_SIZE];
} HashTable;

2.2 タスクの追加とリンクリスト

// タスクをリンクリストに追加
Task* addTask(Task* head, int id, const char* description, int priority) {
    Task* newTask = (Task*)malloc(sizeof(Task));
    newTask->id = id;
    strcpy(newTask->description, description);
    newTask->priority = priority;
    newTask->next = head;
    return newTask;
}

2.3 タスクの削除と履歴保存

// タスクを削除しスタックに保存
Task* deleteTask(Task* head, int id, Stack** historyStack) {
    Task* temp = head;
    Task* prev = NULL;

    while (temp != NULL && temp->id != id) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("Task with ID %d not found.\n", id);
        return head;
    }

    if (prev == NULL) {
        head = temp->next;
    } else {
        prev->next = temp->next;
    }

    // 履歴に保存
    Stack* newHistory = (Stack*)malloc(sizeof(Stack));
    strcpy(newHistory->taskDescription, temp->description);
    newHistory->next = *historyStack;
    *historyStack = newHistory;

    free(temp);
    return head;
}

2.4 タスクの優先度付き並び替え

// タスクを優先度順に並べ替え
Task* sortTasks(Task* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }

    for (Task* i = head; i->next != NULL; i = i->next) {
        for (Task* j = i->next; j != NULL; j = j->next) {
            if (i->priority < j->priority) {
                int tempId = i->id;
                char tempDesc[100];
                int tempPriority = i->priority;

                strcpy(tempDesc, i->description);
                i->id = j->id;
                i->priority = j->priority;
                strcpy(i->description, j->description);

                j->id = tempId;
                j->priority = tempPriority;
                strcpy(j->description, tempDesc);
            }
        }
    }
    return head;
}

2.5 ハッシュテーブルでのタスク検索

// ハッシュ関数
int hashFunction(int id) {
    return id % TABLE_SIZE;
}

// タスクを検索
Task* searchTask(HashTable* table, int id) {
    int index = hashFunction(id);
    Task* temp = table->table[index];
    while (temp != NULL && temp->id != id) {
        temp = temp->next;
    }
    return temp;
}

動作解説

1. 追加操作：新しいタスクをリンクリストに挿入します。
2. 削除操作：特定のタスクを削除し、その履歴をスタックに保存します。
3. 優先度並び替え：バブルソートでタスクを優先度順に並び替えます。
4. 検索操作：ハッシュテーブルでキー（ID）に基づいてタスクを検索します。

3. 練習問題

以下の課題に挑戦して、データ構造の統合理解を深めましょう。

1. 削除済みタスクの履歴を再挿入する機能を追加してください。
2. タスクの優先度を動的に変更できる機能を実装してください。
3. タスクを期限（タイムスタンプ）順に並べ替える機能を追加してください。

4. 練習問題の解答と解説

問1の解答

// 履歴からタスクを再挿入
Task* restoreTask(Stack** historyStack, Task* head) {
    if (*historyStack == NULL) {
        printf("No history to restore.\n");
        return head;
    }

    Stack* temp = *historyStack;
    head = addTask(head, rand() % 100, temp->taskDescription, rand() % 5 + 1);
    *historyStack = temp->next;
    free(temp);
    return head;
}

この関数では、削除済みタスクを履歴スタックから復元してタスクリストに再挿入します。

5. まとめ

本記事では、複数のデータ構造を統合して、実用的なタスク管理アプリケーションを構築しました。次回は、さらに高度なプロジェクトを通じて応用力を深めます。