線形リスト（linear list）は、同じ特性を持つn個のデータ要素の有限シーケンスです。線形リストは実際のアプリケーションで広く使用されているデータ構造であり、一般的な線形リストには順序リスト、連結リスト、スタック、キュー、文字列などがあります。

線形リストは論理的には線形構造であり、連続した直線状の構造を持ちます。しかし、物理的な構造としては必ずしも連続的である必要はありません。線形リストは物理的に格納される際、通常は配列や連結構造の形式で格納されます。

例えば、野菜を葉菜類、瓜類、きのこ類に分類する場合、線形リストは同じ特性を持つデータ構造の集合を指します。

順序リスト

順序リストの底層構造は配列であり、配列をカプセル化して一般的な追加、削除、変更、検索などのインターフェースを実装しています。

配列をカプセル化しているため、物理的な構造は連続的です。

静的順序リスト

概念：固定長配列を使用して要素を格納します。

静的順序リストの欠点：スペースが少なすぎると不足し、多すぎるとスペースの無駄になります。

動的順序リスト

具体的なシミュレーションと実装は以下の通りです：

DynamicList.h

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

//動的順序リスト
typedef int DataType;
typedef struct DynamicList
{
    DataType* data;
    int count;      //リスト内の有効なデータ数
    int capacity;   //リストの現在の容量
} List;

//リストの初期化と破棄
void ListInit(List* list);
void ListDestroy(List* list);

void ListCheckCapacity(List* list); //容量を確認し、不足の場合は拡張

//先頭/末尾への挿入/削除
void ListPushBack(List* list, DataType value); //末尾挿入
void ListPushFront(List* list, DataType value); //先頭挿入
void ListPopBack(List* list); //末尾削除
void ListPopFront(List* list); //先頭削除

void ListInsert(List* list, int position, DataType value); //指定位置にデータを挿入
void ListErase(List* list, int position); //指定位置のデータを削除

bool ListFind(List* list, DataType value); //リスト内の値を検索
void ListPrint(List* list); //表示
bool ListIsEmpty(List* list); //有効長が0かどうかを判断

DynamicList.c

#include"DynamicList.h"

//初期化
void ListInit(List* list) {
    assert(list);
    list->data = NULL;
    list->count = list->capacity = 0;
}

//リストの破棄
void ListDestroy(List* list) {
    assert(list);
    if(list->data)
        free(list->data);
    list->data = NULL;
    list->count = list->capacity = 0;
}

//容量を確認し、不足の場合は拡張
void ListCheckCapacity(List* list) {
    if (list->count == list->capacity) {
        //データを追加するための十分なスペースがない
        //容量を拡張
        int newCapacity = list->capacity == 0 ? 4 : 2 * list->capacity;
        DataType* temp = (DataType*)realloc(list->data, newCapacity * sizeof(DataType));
        if (temp == NULL) {
            perror("容量拡張失敗！\n");
            return;
        }
        list->data = temp;
        list->capacity = newCapacity;
    }
}

//末尾にデータを挿入
void ListPushBack(List* list, DataType value) {
    assert(list);
    ListCheckCapacity(list);
    list->data[list->count++] = value;
}

//先頭にデータを挿入
void ListPushFront(List* list, DataType value) {
    assert(list);
    ListCheckCapacity(list);
    //既存データを後方にシフト
    for (int i = list->count; i > 0; i--)
    {
        list->data[i] = list->data[i - 1];
    }
    list->data[0] = value;
    list->count++;
}

//末尾からデータを削除
void ListPopBack(List* list) {
    assert(list);
    assert(!ListIsEmpty(list));
    list->count--;
}

//先頭からデータを削除
void ListPopFront(List* list) {
    assert(list);
    assert(!ListIsEmpty(list));
    //後方のデータを前方にシフト
    for (int i = 0; i < list->count - 1; i++)
    {
        list->data[i] = list->data[i + 1];
    }
    list->count--;
}

//指定位置にデータを挿入
void ListInsert(List* list, int position, DataType value) {
    assert(list);
    assert(position >= 0 && position <= list->count);
    
    ListCheckCapacity(list);
    
    for (int i = list->count - 1; i >= position; i--)
    {
        list->data[i + 1] = list->data[i];
    }
    list->data[position] = value;
    list->count++;
}

//指定位置のデータを削除
void ListErase(List* list, int position) {
    assert(list);
    assert(!ListIsEmpty(list));
    
    assert(position >= 0 && position < list->count);

    for (int i = position; i < list->count - 1; i++)
    {
        list->data[i] = list->data[i + 1];
    }
    list->count--;
}

//リスト内の値を検索
bool ListFind(List* list, DataType value) {
    assert(list);
    for (int i = 0; i < list->count; i++)
    {
        if (list->data[i] == value) {
            return true;
        }
    }
    return false;
}

//リストを表示
void ListPrint(List* list) {
    assert(list);
    for (int i = 0; i < list->count; i++)
    {
        printf("%d ", list->data[i]);
    }
    printf("\n");
}

//有効長が0かどうかを判断
bool ListIsEmpty(List* list) {
    assert(list);
    return list->count == 0;
}

main.c

#include"DynamicList.h"

void displayMenu() {
    printf("*************************動的順序リスト*************************\n");
    printf("******1、末尾挿入          2、先頭挿入**********************\n");
    printf("******3、末尾削除          4、先頭削除**********************\n");
    printf("******5、指定位置に挿入    6、指定位置を削除********\n");
    printf("******7、値を検索          8、表示**********************\n");
    printf("******************************************************************\n");
}

int main()
{
    List myList;
    int operation;
    DataType value; 
    int position;
    ListInit(&myList);
    
    do {
        displayMenu();
        printf("操作を選択してください：\n");
        scanf("%d", &operation);
        switch (operation)
        {
        case 1:
            printf("挿入する値を入力してください\n");
            scanf("%d", &value);
            ListPushBack(&myList, value);
            break;
        case 2:
            printf("挿入する値を入力してください\n");
            scanf("%d", &value);
            ListPushFront(&myList, value);
            break;
        case 3:
            ListPopBack(&myList);
            break;
        case 4:
            ListPopFront(&myList);
            break;
        case 5:
            printf("挿入する値を入力してください\n");
            scanf("%d", &value);
            printf("挿入位置を入力してください\n");
            scanf("%d", &position);
            ListInsert(&myList, position, value);
            break;
        case 6:
            printf("削除位置を入力してください\n");
            scanf("%d", &position);
            ListErase(&myList, position);
            break;
        case 7:
            printf("検索する値を入力してください\n");
            scanf("%d", &value);
            if (ListFind(&myList, value))
                printf("見つかりました\n");
            else
                printf("見つかりませんでした\n");
            break;
        case 8:
            ListPrint(&myList);
            break;
        case 0:
            printf("終了します\n");
            break;
        default:
            printf("無効な入力です。もう一度入力してください\n");
            break;
        }
    } while (operation != 0);
    
    ListDestroy(&myList);
    return 0;
}

連絡先管理システムの実装

静的順序リストと動的順序リストを組み合わせて連絡先管理システムを実装します。

Contact.h

#pragma once

//連絡先データを保存する構造体
#define NAME_MAX 100
#define SEX_MAX 10
#define PHONE_MAX 15
#define ADDRESS_MAX 100

typedef struct ContactInfo
{
    char name[NAME_MAX];
    char sex[SEX_MAX];
    int age;
    char phone[PHONE_MAX];
    char address[ADDRESS_MAX];
} Contact;

//連絡先管理システムは順序リストを使用
typedef struct DynamicList ContactBook;

//連絡先管理システムの初期化と破棄
void ContactBookInit(ContactBook* book);
void ContactBookDestroy(ContactBook* book);

//連絡先の追加
void ContactAdd(ContactBook* book);
//連絡先の削除
void ContactDelete(ContactBook* book);
//連絡先の更新
void ContactModify(ContactBook* book);
//連絡先の一覧表示
void ContactShow(ContactBook* book);
//指定連絡先の検索
void ContactFind(ContactBook* book);

Contact.c

#include"Contact.h"
#include"DynamicList.h"
#include <string.h>

void ContactBookInit(ContactBook* book) {
    ListInit(book);
}

void ContactBookDestroy(ContactBook* book) {
    ListDestroy(book);
}

//連絡先の追加
void ContactAdd(ContactBook* book) {
    Contact info;
    printf("連絡先の名前を入力してください：\n");
    scanf("%s", info.name);
    printf("連絡先の性別を入力してください：\n");
    scanf("%s", info.sex);
    printf("連絡先の年齢を入力してください：\n");
    scanf("%d", &info.age);
    printf("連絡先の電話番号を入力してください：\n");
    scanf("%s", info.phone);
    printf("連絡先の住所を入力してください：\n");
    scanf("%s", info.address);

    //連絡先データを取得し、構造体infoに保存
    //連絡先管理システム（順序リスト）にデータを挿入
    ListPushBack(book, info);
}

//名前で連絡先を検索
int FindByName(ContactBook* book, char name[]) {
    for (int i = 0; i < book->count; i++)
    {
        if (strcmp(book->data[i].name, name) == 0) {
            return i;
        }
    }
    return -1;
}

//連絡先の削除
void ContactDelete(ContactBook* book) {
    printf("削除する連絡先の名前を入力してください：\n");
    char name[NAME_MAX];
    scanf("%s", name);
    int index = FindByName(book, name);
    if (index < 0) {
        printf("削除する連絡先が存在しません！\n");
        return;
    }
    //見つかった場合、indexを削除