空間計算量

一般的な再帰は深さ優先探索であり、深さ優先探索の空間計算量は再帰の深さによって決まります。ある方向での再帰が終了すると、その時点で使用していたスタック領域が解放され、同じメモリが再利用されます。

順序リスト

静的順序リスト

typedef int SLDataType;
#define N 10
struct SeqList {
    SLDataType a[N];
    int size;
};

動的順序リスト

seqlist.h

#pragma once

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

typedef int SLDataType;
#define INIT_N 4
#define N 10

typedef struct SeqList {
    SLDataType* a;
    int size; // 現在使用している要素数
    int capacity; // 現在の最大容量
} SL;

void SeqInit(SL* s);
void SeqDestroy(SL* s);
void print(SL* ps);
void SLCheckCapacity(SL* ps);
void SLPushBack(SL* ps, SLDataType data);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType data);
void SLPopFront(SL* ps);
void SLInsert(SL* ps, int pos, SLDataType data);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);

seqlist.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "SeqList.h"

void SLInsert(SL* ps, int pos, SLDataType data) {
    assert(ps && pos >= 0 && pos <= ps->size);
    SLCheckCapacity(ps);

    int end = ps->size - 1;
    while (end >= pos) {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[pos] = data;
    ps->size++;
}

void SLCheckCapacity(SL* ps) {
    if (ps->size == ps->capacity) {
        SLDataType* temp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);
        if (temp == NULL) {
            perror("realloc");
            return;
        }
        ps->a = temp;
        ps->capacity *= 2;
    }
}

void print(SL* ps) {
    for (int i = 0; i < ps->size; i++) {
        printf("%d ", ps->a[i]);
    }
    printf("\n");
}

void SeqInit(SL* ps) {
    ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_N);
    ps->size = 0;
    ps->capacity = INIT_N;
}

void SeqDestroy(SL* ps) {
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->size = 0;
}

void SLPushBack(SL* ps, SLDataType data) {
    SLInsert(ps, ps->size, data);
}

void SLPopBack(SL* ps) {
    SLErase(ps, ps->size - 1);
}

void SLPushFront(SL* ps, SLDataType data) {
    SLInsert(ps, 0, data);
}

void SLPopFront(SL* ps) {
    SLErase(ps, 0);
}

void SLErase(SL* ps, int pos) {
    assert(ps);
    assert(pos >= 0 && pos < ps->size);
    int begin = pos + 1;
    while (begin < ps->size) {
        ps->a[begin - 1] = ps->a[begin];
        begin++;
    }
    ps->size--;
}

int SLFind(SL* ps, SLDataType x) {
    for (int i = 0; i < ps->size; i++) {
        if (ps->a[i] == x) {
            return i;
        }
    }
    return -1;
}

test.c

#include "SeqList.h"

void TestSeqList() {
    SL s;
    SeqInit(&s);

    SLPushBack(&s, 1);
    SLPushBack(&s, 2);
    SLPushBack(&s, 3);
    SLPushBack(&s, 4);
    SLPushBack(&s, 5);

    SLPopBack(&s);
    SLPopBack(&s);

    SLPushFront(&s, -1);
    SLPushFront(&s, -2);
    SLPushFront(&s, -3);

    SLPopFront(&s);
    SLPopFront(&s);

    SLInsert(&s, 0, 100);
    SLInsert(&s, 0, 100);

    SLErase(&s, 0);

    print(&s);

    SeqDestroy(&s);
}

int main() {
    TestSeqList();
    return 0;
}