动态数组

数组是一种顺序存储的线性表，所有元素的内存地址是连续的。

int *arr = malloc(sizeof(int) * 3);
arr[0] = 11;
arr[1] = 22;
arr[2] = 33;

或者使用C++

c++

int *arr = new int[3]();
arr[0] = 11;
arr[1] = 22;
arr[2] = 33;

由上面代码创建的变量内存模型

其中，变量arr存储在栈上，但是数组中的数据是存储在堆。

数组的缺陷也很明显：

在很多编程语言中，数组都无法动态的扩展数组的容量；
如果分配空间不足，无法满足程序需要；
如果分配空间过多，造成资源浪费。

接口设计

一般情况下，动态数组应该具备以下的接口：

typedef struct dynamicArray{
    void** pAddr;   // 维护的真实存放数据的数组地址
    int m_capacity; // 动态数组的容量
    int m_size; // 动态数组的大小（或称为元素的个数，或已使用的容量）
}dynamicArray;

// 初始化动态数组
dynamicArray* initDynamicArray(int capacity);

// 向数组尾部插入数据
void insertDynamicArray(dynamicArray* array, void* data);

/**
* 按位置插入数据
* 如果提供的位置小于或等于0，将进行头插（头插性能较低）
* 如果提供的位置大于数组大小，将进行尾插
*/
void insertByPosDynamicArray(dynamicArray* array, int pos, void* data);

// 判断数组是否为空
_Bool isEmptyDynamicArray(dynamicArray* array);

// 清空数组
void clearDynamicArray(dynamicArray* array);

// 按位置获取元素
void* getElementDynamicArray(dynamicArray* array, int pos);

// 按值获取元素所在的位置，需要调用者自行定义比较值是否匹配的回调函数
int indexOfDynamicArrary(dynamicArray* array, void* data, _Bool(*compareVal)(void* data1, void* data2));

// 获取数组容量
int getCapacityDynamicArray(dynamicArray* array);

// 获取数组大小
int getSizeDynamicArray(dynamicArray* array);

// 按位置删除元素
void deleteByPosDynamicArray(dynamicArray* array, int pos);

// 按值删除元素，需要调用者自行定义比较值是否匹配的回调函数
void deleteByValDynamicArray(dynamicArray* array, void* data, _Bool(*compareVal)(void* data1, void* data2));

// 遍历数组
void forEachDynamicArray(dynamicArray* array, void(*forEachArray)(void*));

// 销毁数组
void destroyDynamicArray(dynamicArray* array);

插入、删除分析

元素的插入

元素的删除

注意:数组的容量和数组的长度是两个不同的概念

时间复杂度

动态数组的底层依然是数组，尾部插入、删除的时间复杂度是 $O (1)$ ，随机存取可以直接使用下标操作时间复杂度也是 $O (1)$ ，但是在头部进行插入、删除需要移动大量元素时间复杂度是 $O (n)$ ，另外需要考虑的是，如果插入触发了扩容操作，会额外增加 $O (n)$ 的时间。

综合平均时间复杂度为 $O (n)$ （头部操作）或为 $O (1)$ （尾部操作）。

C语言int实现

dynamicArray.hdynamicArray.ctest.c程序输出

#pragma once

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

typedef struct dynamic_array {
    int *pAddr;     // 维护的真实存放数据的数组地址
    int m_capacity; // 动态数组的容量
    int m_size;     // 动态数组的大小（或称为元素的个数，或已使用的容量）
} dynamicArray;

// 初始化动态数组
dynamicArray *initDynamicArray(int capacity);

// 向数组尾部插入数据
void insertDynamicArray(dynamicArray *array, int data);

/**
 * 按位置插入数据
 * 如果提供的位置小于或等于0，将进行头插（头插性能较低）
 * 如果提供的位置大于数组大小，将进行尾插
 */
void insertByPosDynamicArray(dynamicArray *array, int pos, int data);

// 判断数组是否为空
bool isEmptyDynamicArray(dynamicArray *array);

// 清空数组
void clearDynamicArray(dynamicArray *array);

// 按位置获取元素
int getElementDynamicArray(dynamicArray *array, int pos);

// 按值获取元素所在的位置，需要调用者自行定义比较值是否匹配的回调函数
int indexOfDynamicArrary(dynamicArray *array, int data);

// 获取数组容量
int getCapacityDynamicArray(dynamicArray *array);

// 获取数组大小
int getSizeDynamicArray(dynamicArray *array);

// 按位置删除元素
void deleteByPosDynamicArray(dynamicArray *array, int pos);

// 按值删除元素，需要调用者自行定义比较值是否匹配的回调函数
void deleteByValDynamicArray(dynamicArray *array, int data);

// 遍历数组
void forEachDynamicArray(dynamicArray *array);

// 销毁数组
void destroyDynamicArray(dynamicArray *array);

#include "dynamic-array.h"
#include <stdio.h>

dynamicArray *initDynamicArray(int capacity) {
    if (capacity < 0) {
        capacity = 10;
    }

    dynamicArray *array = malloc(sizeof(dynamicArray));
    if (array == NULL) {
        perror("初始化失败，申请空间失败");
        return array;
    }

    array->pAddr = malloc(sizeof(int) * capacity);
    if (array->pAddr == NULL) {
        perror("初始化失败，申请空间失败");
        return array;
    }

    array->m_capacity = capacity;
    array->m_size = 0;

    return array;
}

void insertDynamicArray(dynamicArray *array, int data) {
    if (array == NULL) {
        perror("插入失败，传入的数组为空");
        return;
    }

    if (array->m_capacity == array->m_size) {
        int newCapacity = array->m_capacity * 2;
        int *newAddr = malloc(sizeof(int) * newCapacity);
        if (newAddr == NULL) {
            perror("插入失败，扩容申请空间失败");
            return;
        }

        memcpy(newAddr, array->pAddr, sizeof(int) * array->m_capacity);

        free(array->pAddr);
        array->pAddr = newAddr;
        array->m_capacity = newCapacity;
    }

    array->pAddr[array->m_size] = data;
    ++array->m_size;
}

void insertByPosDynamicArray(dynamicArray *array, int pos, int data) {
    if (array == NULL) {
        perror("插入失败，传入的数组为空");
        return;
    }

    if (pos < 0) {
        pos = 0;
    } else if (pos > array->m_size) {
        insertDynamicArray(array, data);
        return;
    }

    if (array->m_capacity == array->m_size) {
        int newCapacity = array->m_capacity * 2;
        int *newAddr = malloc(sizeof(int) * newCapacity);
        if (newAddr == NULL) {
            perror("插入失败，扩容申请空间失败");
            return;
        }

        memcpy(newAddr, array->pAddr, sizeof(int) * array->m_capacity);
        free(array->pAddr);
        array->pAddr = newAddr;
        array->m_capacity = newCapacity;
    }

    for (int i = array->m_size; i >= pos; --i) {
        array->pAddr[i + 1] = array->pAddr[i];
    }
    array->pAddr[pos] = data;
    ++array->m_size;
}

bool isEmptyDynamicArray(dynamicArray *array) {
    if (array == NULL) {
        return true;
    }
    return array->m_size == 0;
}

void clearDynamicArray(dynamicArray *array) {
    if (array == NULL) {
        return;
    }

    array->m_size = 0;
}

int getElementDynamicArray(dynamicArray *array, int pos) {
    if (array == NULL) {
        perror("获取失败，传入的数组为空");
        return -1;
    }

    if (pos < 0 || pos >= array->m_size) {
        perror("获取失败，位置有误");
        return -1;
    }

    return array->pAddr[pos];
}

int indexOfDynamicArrary(dynamicArray *array, int data) {
    if (array == NULL) {
        perror("获取失败，传入的数组为空");
        return -1;
    }

    for (int i = 0; i < array->m_size; --i) {
        if (array->pAddr[i] == data) {
            return i;
        }
    }
    return -1;
}

int getCapacityDynamicArray(dynamicArray *array) {
    if (array == NULL) {
        perror("获取失败，传入的数组为空");
        return -1;
    }

    return array->m_capacity;
}

int getSizeDynamicArray(dynamicArray *array) {
    if (array == NULL) {
        perror("获取失败，传入的数组为空");
        return -1;
    }

    return array->m_size;
}

void deleteByPosDynamicArray(dynamicArray *array, int pos) {
    if (array == NULL) {
        perror("删除失败，传入的数组为空");
        return;
    }

    if (pos < 0 || pos >= array->m_size) {
        perror("删除失败，传入的位置有误");
        return;
    }

    for (int i = pos; i < array->m_size; ++i) {
        array->pAddr[i] = array->pAddr[i + 1];
    }
    --array->m_size;
}

void deleteByValDynamicArray(dynamicArray *array, int data) {
    if (array == NULL) {
        perror("删除失败，传入的数组为空");
        return;
    }

    int idx = -1;
    for (int i = 0; i < array->m_size; ++i) {
        if (array->pAddr[i] == data) {
            idx = i;
            break;
        }
    }

    if (idx != -1) {
        deleteByPosDynamicArray(array, idx);
    }
}

void forEachDynamicArray(dynamicArray *array) {
    if (array == NULL) {
        printf("array is null\n");
        return;
    }

    for (int i = 0; i < array->m_size; ++i) {
        printf("%d ", array->pAddr[i]);
    }

    putchar('\n');
}

void destroyDynamicArray(dynamicArray *array) {
    if (array == NULL) {
        return;
    }

    free(array->pAddr);
    array->pAddr = NULL;

    free(array);
    array = NULL;
}

#include "dynamic-array.h"
#include <stdio.h>

int main(void) {
    dynamicArray *array = initDynamicArray(2);
    printf("size=%d capacity=%d\n", getSizeDynamicArray(array), getCapacityDynamicArray(array));

    insertDynamicArray(array, 1);
    insertDynamicArray(array, 2);
    insertByPosDynamicArray(array, 1, 3);
    insertDynamicArray(array, 4);
    insertDynamicArray(array, 5);

    printf("size=%d capacity=%d\n", getSizeDynamicArray(array), getCapacityDynamicArray(array));

    forEachDynamicArray(array);

    deleteByPosDynamicArray(array, 1);
    deleteByValDynamicArray(array, 3);

    forEachDynamicArray(array);

    printf("size=%d capacity=%d\n", getSizeDynamicArray(array), getCapacityDynamicArray(array));

    destroyDynamicArray(array);

    return 0;
}

bash

size=0 capacity=2
size=5 capacity=8
1 3 2 4 5 
1 2 4 5 
size=4 capacity=8

C语言void*实现

dynamicArray.hdynamicArray.ctest.c程序输出

#ifndef __DYNAMICARRAY__
#define __DYNAMICARRAY__

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

typedef struct dynamicArray
{
    void** pAddr;   // 维护的真实存放数据的数组地址
    int m_capacity; // 动态数组的容量
    int m_size; // 动态数组的大小（或称为元素的个数，或已使用的容量）
}dynamicArray;

// 初始化动态数组
dynamicArray* initDynamicArray(int capacity);

// 向数组尾部插入数据
void insertDynamicArray(dynamicArray* array, void* data);

/**
* 按位置插入数据
* 如果提供的位置小于或等于0，将进行头插（头插性能较低）
* 如果提供的位置大于数组大小，将进行尾插
*/
void insertByPosDynamicArray(dynamicArray* array, int pos, void* data);

// 判断数组是否为空
_Bool isEmptyDynamicArray(dynamicArray* array);

// 清空数组
void clearDynamicArray(dynamicArray* array);

// 按位置获取元素
void* getElementDynamicArray(dynamicArray* array, int pos);

// 按值获取元素所在的位置，需要调用者自行定义比较值是否匹配的回调函数
int indexOfDynamicArrary(dynamicArray* array, void* data, _Bool(*compareVal)(void* data1, void* data2));

// 获取数组容量
int getCapacityDynamicArray(dynamicArray* array);

// 获取数组大小
int getSizeDynamicArray(dynamicArray* array);

// 按位置删除元素
void deleteByPosDynamicArray(dynamicArray* array, int pos);

// 按值删除元素，需要调用者自行定义比较值是否匹配的回调函数
void deleteByValDynamicArray(dynamicArray* array, void* data, _Bool(*compareVal)(void* data1, void* data2));

// 遍历数组
void forEachDynamicArray(dynamicArray* array, void(*forEachArray)(void*));

// 销毁数组
void destroyDynamicArray(dynamicArray* array);


#endif // !__DYNAMICARRAY__

#include "dynamicArray.h"

dynamicArray* initDynamicArray(int capacity) {
    if (capacity <= 0) { return NULL; }

    // 在堆区申请动态数组的空间
    dynamicArray* array = malloc(sizeof(dynamicArray));
    if (array == NULL) {
        puts("error：堆空间申请失败，初始化失败。");
        return NULL;
    }
    // 在堆区申请动态数组中元素的空间
    array->pAddr = malloc(sizeof(void*) * capacity);
    if (array->pAddr == NULL) {
        puts("error：堆空间申请失败，初始化失败。");
        return NULL;
    }
    // 初始化容量为传入的容量大小
    array->m_capacity = capacity;
    // 初始化大小为0
    array->m_size = 0;

    return array;
}

void insertDynamicArray(dynamicArray* array, void* data) {
    if (array == NULL || data == NULL) { return; }

    // 判断数组是否已经满了
    if (array->m_size == array->m_capacity) {
        // 记录需要申请的新空间的容量
        int newCapacity = array->m_capacity * 2;
        // 申请新的空间
        void** newpAddr = malloc(sizeof(void*) * newCapacity);
        if (newpAddr == NULL) {
            puts("error：堆空间申请失败，数组扩容失败；无法插入。");
            return NULL;
        }
        // 将旧数据拷贝到新空间
        memcpy(newpAddr, array->pAddr, sizeof(void*) * array->m_capacity);
        // 释放原有空间
        free(array->pAddr);
        // 更新指向
        array->pAddr = newpAddr;
        // 更新空间容量
        array->m_capacity = newCapacity;
    }

    // 将数据插入到尾部
    array->pAddr[array->m_size] = data;
    // 更新数组大小
    array->m_size++;
}

void insertByPosDynamicArray(dynamicArray* array, int pos, void* data) {
    if (array == NULL) { return; }
    if (pos < 0) { pos = 0; }
    else if (pos > array->m_size) {
        pos = array->m_size;
        insertDynamicArray(array, data);
        return;
    }

    // 判断数组是否已经满了
    if (array->m_size == array->m_capacity) {
        // 记录需要申请的新空间的容量
        int newCapacity = array->m_capacity * 2;
        // 申请新的空间
        void** newpAddr = malloc(sizeof(void*) * newCapacity);
        if (newpAddr == NULL) {
            puts("error：堆空间申请失败，数组扩容失败；无法插入。");
            return NULL;
        }
        // 将旧数据拷贝到新空间
        memcpy(newpAddr, array->pAddr, sizeof(void*) * array->m_capacity);
        // 释放原有空间
        free(array->pAddr);
        // 更新指向
        array->pAddr = newpAddr;
        // 更新空间容量
        array->m_capacity = newCapacity;
    }
    // 将现有数据后移
    for (int i = array->m_size; i >= pos; --i) {
        array->pAddr[i + 1] = array->pAddr[i];
    }
    array->pAddr[pos] = data;
    array->m_size++;
}

_Bool isEmptyDynamicArray(dynamicArray* array) {
    if (array == NULL) { return; }
    if (array->m_size == 0) { return 1; }
    else { return 0; }
}

void clearDynamicArray(dynamicArray* array) {
    if (array == NULL) { return; }

    array->m_size = 0;
}

void* getElementDynamicArray(dynamicArray* array, int pos) {
    if (array == NULL) { return NULL; }
    if (pos < 0 || pos >= array->m_size) { return NULL; }

    return array->pAddr[pos];
}

int indexOfDynamicArrary(dynamicArray* array, void* data, _Bool(*compareVal)(void* data1, void* data2)) {
    if (array == NULL || data == NULL || compareVal == NULL) { return; }

    for (int i = 0; i < array->m_size; ++i) {
        if (compareVal(array->pAddr[i], data)) { return i; }
    }

    return -1;
}

int getCapacityDynamicArray(dynamicArray* array) {
    if (array == NULL) { return -1; }
    return array->m_capacity;
}

int getSizeDynamicArray(dynamicArray* array) {
    if (array == NULL) { return -1; }
    return array->m_size;
}

void forEachDynamicArray(dynamicArray* array, void(*forEachArray)(void* data)) {
    if (array == NULL) { return; }
    for (int i = 0; i < array->m_size; ++i) {
        forEachArray(array->pAddr[i]);
    }
    putchar('\n');
}

void deleteByPosDynamicArray(dynamicArray* array, int pos) {
    if (array == NULL || pos < 0 || pos >= array->m_size) { return; }

    for (int i = pos; i < array->m_size; ++i) {
        array->pAddr[i] = array->pAddr[i + 1];
    }
    array->m_size--;
}

void deleteByValDynamicArray(dynamicArray* array, void* data, _Bool(*compareVal)(void* data1, void* data2)) {
    if (array == NULL || data == NULL) { return; }

    for (int i = 0; i < array->m_size; ++i) {
        if (compareVal(array->pAddr[i], data)) {
            deleteByPosDynamicArray(array, i);
        }
    }
}

void destroyDynamicArray(dynamicArray* array) {
    clearDynamicArray(array);
    if (array->pAddr) {
        free(array->pAddr);
        array->pAddr = NULL;
    }
    free(array);
    array = NULL;
}

#include "dynamicArray.h"
#include <stdio.h>

void forEachArray(void* data) {
    int* p = data;
    printf("%d ", *p);
}

_Bool CompareArrayVal(void* data1, void* data2) {
    int* p1 = data1;
    int* p2 = data2;

    return *p1 == *p2;
}

int main() {
    dynamicArray* array = initDynamicArray(2);
    printf("size=%d capacity=%d\n", getSizeDynamicArray(array), getCapacityDynamicArray(array));

    int a = 1;
    int b = 3;
    int c = 2;
    int d = 4;
    int e = 5;

    insertDynamicArray(array, &a);
    insertDynamicArray(array, &b);
    insertByPosDynamicArray(array, 1, &c);
    insertDynamicArray(array, &d);
    insertDynamicArray(array, &e);

    printf("size=%d capacity=%d\n", getSizeDynamicArray(array), getCapacityDynamicArray(array));

    forEachDynamicArray(array, forEachArray);

    deleteByPosDynamicArray(array, 1);
    deleteByValDynamicArray(array, &a, CompareArrayVal);

    forEachDynamicArray(array, forEachArray);

    printf("size=%d capacity=%d\n", getSizeDynamicArray(array), getCapacityDynamicArray(array));

    return 0;
}

bash

size=0 capacity=2
size=5 capacity=8
1 2 3 4 5
3 4 5
size=3 capacity=8

C++int类型实现

dynamicArray.hdynamicArray.cppmain.cpp运行结果

cpp

#pragma once

class DynamicArray {
public:
    // 取消默认的无参构造，给有参构造函数默认实参来代替无参构造函数
    // DynamicArray();
    DynamicArray(int capacity = 10);
    ~DynamicArray();

    // API接口
    // 添加元素到尾部
    void add(int element);
    // 插入元素到指定位置
    void insert(int pos, int element);
    // 设置指定位置的元素值
    void set(int index, int element);
    // 查看指定位置的元素值
    int get(int index) const;
    // 查看是否包含某个元素
    bool contains(int element) const;
    // 查看元素所在位置
    int indexOf(int element) const;
    // 删除元素
    void remove(int index);
    // 数组是否为空
    bool empty() const;
    // 数组元素个数
    int size() const;
    // 遍历数组
    void forEach() const;
    // 清空数组
    void clear();

    // 可以不提供的接口
    // 数组容量，使用者无需关心容量，直接使用即可
    int capacity();

private:
    // 扩容函数
    void ensureCapacity();

private:
    int *m_arr;
    int m_capacity;
    int m_size;
};

cpp

#include "dynamicArray.h"
#include <exception>
#include <iostream>

DynamicArray::DynamicArray(int capacity) : m_capacity(capacity), m_size(0) {
    if (capacity < 0) {
        capacity = 10;
    }
    try {
        m_arr = new int[capacity];
    } catch (std::bad_alloc &e) {
        throw e;
    }
}

DynamicArray::~DynamicArray() {
    delete[] m_arr;
}

void DynamicArray::add(int element) {
    if (m_size == m_capacity) {
        ensureCapacity();
    }

    m_arr[m_size] = element;
    ++m_size;
}

void DynamicArray::insert(int pos, int element) {
    // if (pos < 0) {
    //     pos = 0;
    // } else if (pos >= m_size) {
    //     add(element);
    //     return;
    // }
    if (pos < 0 || pos > m_size) {
        throw std::out_of_range("insert失败，pos范围错误");
        return;
    }

    if (m_size == m_capacity) {
        ensureCapacity();
    }

    for (int i = m_size; i >= pos; --i) {
        m_arr[i] = m_arr[i - 1];
    }

    m_arr[pos] = element;
    ++m_size;
}

void DynamicArray::set(int index, int element) {
    if (index < 0 || index >= m_size) {
        std::__throw_out_of_range("传入的索引位置有误");
        return;
    }

    m_arr[index] = element;
}

int DynamicArray::get(int index) const {
    if (index < 0 || index >= m_size) {
        std::__throw_out_of_range("传入的索引位置有误");
        return -1;
    }

    return m_arr[index];
}

bool DynamicArray::contains(int element) const {
    if (m_size == 0) {
        std::__throw_length_error("数组长度为0");
        return false;
    }

    for (int i = 0; i < m_size; ++i) {
        if (m_arr[i] == element) {
            return true;
        }
    }

    return false;
}

int DynamicArray::indexOf(int element) const {
    if (m_size == 0) {
        std::__throw_length_error("数组长度为0");
        return -1;
    }

    for (int i = 0; i < m_size; ++i) {
        if (m_arr[i] == element) {
            return i;
        }
    }
    return -1;
}

void DynamicArray::remove(int index) {
    if (index < 0 || index >= m_size) {
        std::__throw_out_of_range("索引位置错误");
        return;
    }

    for (int i = index; i < m_size; ++i) {
        m_arr[i] = m_arr[i + 1];
    }
    --m_size;
}

bool DynamicArray::empty() const {
    return m_size == 0;
}

int DynamicArray::size() const {
    return m_size;
}

void DynamicArray::forEach() const {
    if (m_size == 0) {
        return;
    }

    for (int i = 0; i < m_size; ++i) {
        std::cout << m_arr[i] << " ";
    }
    std::cout << std::endl;
}

void DynamicArray::clear() {
    m_size = 0;
}

int DynamicArray::capacity() {
    return m_capacity;
}

void DynamicArray::ensureCapacity() {
    int newCapacity = m_capacity * 2;
    int *newArr = nullptr;
    try {
        newArr = new int[newCapacity];
    } catch (std::bad_alloc &e) {
        throw e;
        return;
    }

    for (int i = 0; i < m_size; ++i) {
        newArr[i] = m_arr[i];
    }

    delete[] m_arr;
    m_arr = newArr;
    m_capacity = newCapacity;
}

cpp

#include "dynamicArray.h"
#include <iostream>
using namespace std;

void testConstructor() {
    DynamicArray arr;
    cout << "构造函数测试：";
    if (arr.size() == 0 && arr.empty()) {
        cout << "✓ 通过" << endl;
    } else {
        cout << "✗ 失败" << endl;
    }
}

void testAddAndGet() {
    DynamicArray arr(3);
    arr.add(10);
    arr.add(20);
    arr.add(30);

    cout << "\n添加/获取测试：";
    bool passed = true;
    passed &= (arr.get(0) == 10); // 验证顺序存储
    passed &= (arr.get(1) == 20);
    passed &= (arr.get(2) == 30);
    passed &= (arr.size() == 3); // 验证size更新

    // 触发扩容测试
    arr.add(40);
    passed &= (arr.get(3) == 40); // 验证扩容后数据正确
    passed &= (arr.size() == 4);  // 验证size正确

    cout << (passed ? "✓ 通过" : "✗ 失败") << endl;
}

void testInsert() {
    DynamicArray arr;
    arr.add(100);
    arr.add(300);

    // 中间插入
    arr.insert(1, 200);
    cout << "\n插入测试：";
    bool passed = true;
    passed &= (arr.get(1) == 200); // 验证插入位置
    passed &= (arr.size() == 3);   // 验证size更新

    // 边界插入
    arr.insert(0, 50);  // 头部插入
    arr.insert(4, 400); // 尾部插入
    passed &= (arr.get(0) == 50);
    passed &= (arr.get(4) == 400);
    passed &= (arr.size() == 5);

    cout << (passed ? "✓ 通过" : "✗ 失败") << endl;
}

void testRemove() {
    DynamicArray arr;
    arr.add(1);
    arr.add(2);
    arr.add(3);
    arr.add(4);

    cout << "\n删除测试：";
    bool passed = true;

    // 删除中间元素
    arr.remove(1);
    passed &= (arr.get(1) == 3);
    passed &= (arr.size() == 3);

    // 删除边界元素
    arr.remove(0); // 头部删除
    passed &= (arr.get(0) == 3);
    arr.remove(1); // 尾部删除
    passed &= (arr.size() == 1);

    // 清空测试
    arr.remove(0);
    passed &= arr.empty();

    cout << (passed ? "✓ 通过" : "✗ 失败") << endl;
}

void testBoundaryCases() {
    DynamicArray arr(2);
    arr.add(5);
    arr.add(10);

    cout << "\n边界测试：";
    bool passed = true;

    try {
        arr.insert(3, 15); // 越界插入
        passed = false;
    } catch (...) {
    }

    try {
        arr.get(-1); // 非法索引
        passed = false;
    } catch (...) {
    }

    // 容量扩展验证
    arr.add(20); // 触发扩容
    passed &= (arr.size() == 3);
    passed &= (arr.get(2) == 20);

    cout << (passed ? "✓ 通过" : "✗ 失败") << endl;
}

void testUtilityMethods() {
    DynamicArray arr;
    arr.add(100);
    arr.add(200);

    cout << "\n工具方法测试：";
    bool passed = true;

    // contains验证
    passed &= arr.contains(100);
    passed &= !arr.contains(300);

    // indexOf验证
    passed &= (arr.indexOf(200) == 1);
    passed &= (arr.indexOf(999) == -1);

    // set验证
    arr.set(0, 150);
    passed &= (arr.get(0) == 150);

    // clear验证
    arr.clear();
    passed &= arr.empty() && (arr.size() == 0);

    cout << (passed ? "✓ 通过" : "✗ 失败") << endl;
}

int main() {
    testConstructor();
    testAddAndGet();
    testInsert();
    testRemove();
    testBoundaryCases();
    testUtilityMethods();

    cout << "\n遍历测试：" << endl;
    DynamicArray arr;
    arr.add(7);
    arr.add(8);
    arr.add(9);
    arr.forEach(); // 应输出7 8 9

    return 0;
}

cpp

构造函数测试：✓ 通过

添加/获取测试：✓ 通过

插入测试：✓ 通过

删除测试：✓ 通过

边界测试：✓ 通过

工具方法测试：✓ 通过

遍历测试：
7 8 9

C++泛化实现

C++语言实现泛化编程需要借助模板技术

在使用模板的时间要注意

在类内声明类外实现的函数，需要在实现函数的时间同样使用template关键字
进行分文件编写的代码，在编译阶段会产生错误，需要将函数实现代码拷贝到头文件中并将头文件文件后缀改为.hpp
在遇到自定义数据类型无法处理的时间，需要借助模板特化技术对相应的函数实现进行重定义

dynamicArray.hdynamicArray.cppmain.cpp

cpp

#ifndef __DYNAMICARRAY__
#define __DYNAMICARRAY__

#include <iostream>
#include <string>

template <class T>
class DynamicArray {
public:
    // 无参构造
    DynamicArray();
    // 有参构造
    DynamicArray(int capacity);
    // 元素的数量
    int size();
    // 是否为空
    bool isEmpty();
    // 是否包含某个元素
    bool contains(T element);
    // 添加元素到最后面
    void add(T element);
    // 返回index位置对应的元素
    T get(int index);
    // 设置index位置对应的元素
    T set(int index, T element);
    // 往index位置添加元素
    void add(int index, T element);
    // 删除index位置对应的元素
    T remove(int index);
    // 查看元素的位置
    int indexOf(T element);
    //清除所有元素
    void clear(void);
    // 遍历数组
    void foreach(void);

private:
    void rangeForIndex(int index);
    void rangeForIndexOfadd(int index);
    void ensureCapacity(int capacity);

private:
    T* arr;
    int m_size;
    int capacity;
    int const Capacity = 10;
    int const IndexError = -1;
};

cpp

template <class T>
DynamicArray<T>::DynamicArray() {
    this->arr = new T[Capacity];
    this->m_size = 0;
    this->capacity = Capacity;
}

template <class T>
DynamicArray<T>::DynamicArray(int capacity) {
    capacity = (capacity < Capacity) ? Capacity : capacity;
    this->arr = new T[capacity];
    this->m_size = 0;
    this->capacity = capacity;
}

template <class T>
int DynamicArray<T>::size() {
    return this->m_size;
}

template <class T>
bool DynamicArray<T>::isEmpty() {
    return this->m_size == 0;
}

template <class T>
bool DynamicArray<T>::contains(T element) {
    for (int i = 0; i < this->m_size; ++i) {
        if (arr[i] == element) return true;
    }
    return false;
}

template <class T>
void DynamicArray<T>::add(T element) {
    add(this->m_size, element);
}

template <class T>
T DynamicArray<T>::get(int index) {
    rangeForIndex(index);

    return arr[index];
}

template <class T>
T DynamicArray<T>::set(int index, T element) {
    rangeForIndexOfadd(index);

    T old = arr[index];
    arr[index] = element;
    this->m_size++;
    return old;
}

template <class T>
void DynamicArray<T>::add(int index, T element) {
    rangeForIndexOfadd(index);

    ensureCapacity(this->m_size + 1);

    for (int i = this->m_size - 1; i >= index; --i) {
        arr[i + 1] = arr[i];
    }
    arr[index] = element;
    this->m_size++;
}

template <class T>
T DynamicArray<T>::remove(int index) {
    rangeForIndex(index);

    T old = arr[index];
    for (int i = index; i < this->m_size; i++) {
        arr[index] = arr[index + 1];
    }
    this->m_size--;
    return old;
}

template <class T>
int DynamicArray<T>::indexOf(T element) {
    for (int i = 0; i < this->m_size; ++i) {
        if (arr[i] == element) return i;
    }
    return IndexError;
}

template <class T>
void DynamicArray<T>::clear(void) {
    this->m_size = 0;
}

template <class T>
void DynamicArray<T>::foreach(void) {
    std::cout << "size:" << this->m_size << ", [";
    for (int i = 0; i < this->m_size; ++i) {
        if (i != 0) {
            std::cout << ", " << arr[i];
        }
        else {
            std::cout << arr[i];
        }
    }
    std::cout << "]" << std::endl;
}

template <class T>
void DynamicArray<T>::rangeForIndex(int index) {
    if (index < 0 || index >= this->m_size) {
        std::cout << "index位置错误" << std::endl;
        exit(-1);
    }
}

template <class T>
void DynamicArray<T>::rangeForIndexOfadd(int index) {
    if (index<0 || index>this->m_size) {
        std::cout << "index位置错误" << std::endl;
        exit(-1);
    }
}

template <class T>
void DynamicArray<T>::ensureCapacity(int capacity) {
    int oldCapacity = this->capacity;
    if (oldCapacity < capacity) {
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        T* array = new T[newCapacity];
        for (int i = 0; i < this->m_size; ++i) {
            array[i] = arr[i];
            array[i] = arr[i];
        }
        delete[]arr;
        arr = array;
        this->capacity = newCapacity;
        std::cout << oldCapacity << "扩容到" << newCapacity << std::endl;
    }
}

#endif // !__DYNAMICARRAY__

cpp

#include <iostream>
using namespace std;
#include "DynamicArray.hpp"

struct Person{
    string name;
    int age;
};

//使用模板特化技术重定义foreeach函数
template <>
void DynamicArray<Person>::foreach(void) {
    std::cout << "size:" << this->m_size << ", [";
    for (int i = 0; i < this->m_size; ++i) {
        if (i != 0) {
            std::cout << ", " << "name:" << arr[i].name << " age:" << arr[i].age;
        }
        else {
            std::cout << "name:"<< arr[i].name << " age:" << arr[i].age;
        }
    }
    std::cout << "]" << std::endl;
}

int main(void) {
    DynamicArray<int>array(5);
    array.add(10);
    array.add(20);
    array.add(30);
    array.set(3, 40);
    array.add(50);

    array.set(array.size(),60);

    for (int i = 0; i < 50; ++i){
        array.add(i);
    }

    array.foreach();

    std::cout << std:: endl;
    Person p1 = { "zhangsan", 18 };
    Person p2 = { "zhang", 18 };
    DynamicArray <Person>arr(5);
    arr.add(p1);
    arr.add(p2);
    arr.foreach();

    system("pause");
    return 0;
}

解决泛化以后存在的问题

cpp

#ifndef __DYNAMICARRAY__
#define __DYNAMICARRAY__

#include <iostream>
#include <string>

template<class T>
class DynamicArray {
public:
    // 无参构造
    DynamicArray();

    // 有参构造
    DynamicArray(int capacity);

    // 元素的数量
    int size();

    // 是否为空
    bool isEmpty();

    // 是否包含某个元素
    bool contains(T element, bool (*compareElement)(void *, void *));

    // 添加元素到最后面
    void add(T element);

    // 返回index位置对应的元素
    T get(int index);

    // 设置index位置对应的元素
    T set(int index, T element);

    // 往index位置添加元素
    void add(int index, T element);

    // 删除index位置对应的元素
    T remove(int index);

    // 查看元素的位置
    int indexOf(T element, bool (*compareElement)(void *, void *));

    //清除所有元素
    void clear(void);

    // 遍历数组
    void foreach (void);

private:
    void rangeForIndex(int index);
    void rangeForIndexOfadd(int index);
    void ensureCapacity(int capacity);

private:
    T *arr;
    int m_size;
    int capacity;
    int const Capacity = 10;
    int const IndexError = -1;
};

//--------------------------------------------------------

template<class T>
DynamicArray<T>::DynamicArray() {
    this->arr = new T[Capacity];
    this->m_size = 0;
    this->capacity = Capacity;
}

template<class T>
DynamicArray<T>::DynamicArray(int capacity) {
    capacity = (capacity < Capacity) ? Capacity : capacity;
    this->arr = new T[capacity];
    this->m_size = 0;
    this->capacity = capacity;
}

template<class T>
int DynamicArray<T>::size() {
    return this->m_size;
}

template<class T>
bool DynamicArray<T>::isEmpty() {
    return this->m_size == 0;
}

template<class T>
bool DynamicArray<T>::contains(T element, bool (*compareElement)(void *, void *)) {
    for (int i = 0; i < this->m_size; ++i) {
        if (compareElement(&arr[i], &element)) return true;
    }
    return false;
}

template<class T>
void DynamicArray<T>::add(T element) {
    add(this->m_size, element);
}

template<class T>
T DynamicArray<T>::get(int index) {
    rangeForIndex(index);

    return arr[index];
}

template<class T>
T DynamicArray<T>::set(int index, T element) {
    rangeForIndexOfadd(index);

    T old = arr[index];
    arr[index] = element;
    this->m_size++;
    return old;
}

template<class T>
void DynamicArray<T>::add(int index, T element) {
    rangeForIndexOfadd(index);

    ensureCapacity(this->m_size + 1);

    for (int i = this->m_size - 1; i >= index; --i) {
        arr[i + 1] = arr[i];
    }
    arr[index] = element;
    this->m_size++;
}

template<class T>
T DynamicArray<T>::remove(int index) {
    rangeForIndex(index);

    T old = arr[index];
    for (int i = index; i < this->m_size; i++) {
        arr[index] = arr[index + 1];
    }
    this->m_size--;
    return old;
}

template<class T>
int DynamicArray<T>::indexOf(T element, bool (*compareElement)(void *, void *)) {
    for (int i = 0; i < this->m_size; ++i) {
        if (compareElement(&arr[i], &element)) return i;
    }
    return IndexError;
}

template<class T>
void DynamicArray<T>::clear(void) {
    for (int i = 0; i < this->m_size; ++i) {
        arr[i] = NULL;
    }
    this->m_size = 0;
}

template<class T>
void DynamicArray<T>::foreach (void) {
    std::cout << "size:" << this->m_size << ", [";
    for (int i = 0; i < this->m_size; ++i) {
        if (i != 0) {
            std::cout << ", " << arr[i];
        } else {
            std::cout << arr[i];
        }
    }
    std::cout << "]" << std::endl;
}

template<class T>
void DynamicArray<T>::rangeForIndex(int index) {
    if (index < 0 || index >= this->m_size) {
        std::cout << "index位置错误" << std::endl;
        exit(-1);
    }
}

template<class T>
void DynamicArray<T>::rangeForIndexOfadd(int index) {
    if (index < 0 || index > this->m_size) {
        std::cout << "index位置错误" << std::endl;
        exit(-1);
    }
}

template<class T>
void DynamicArray<T>::ensureCapacity(int capacity) {
    int oldCapacity = this->capacity;
    if (oldCapacity < capacity) {
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        T *array = new T[newCapacity];
        for (int i = 0; i < this->m_size; ++i) {
            array[i] = arr[i];
            array[i] = arr[i];
        }
        delete[] arr;
        arr = array;
        this->capacity = newCapacity;
        std::cout << oldCapacity << "扩容到" << newCapacity << std::endl;
    }
}

#endif// !__DYNAMICARRAY__
#include <iostream>
using namespace std;
#include "dynamicArray.hpp"
#include <cstring>

struct Person {
    string name;
    int age;
};

//使用模板特化技术重定义foreeach函数
template<>
void DynamicArray<Person>::foreach (void) {
    std::cout << "size:" << this->m_size << ", [";
    for (int i = 0; i < this->m_size; ++i) {
        if (i != 0) {
            std::cout << ", "
                      << "name:" << arr[i].name << " age:" << arr[i].age;
        } else {
            std::cout << "name:" << arr[i].name << " age:" << arr[i].age;
        }
    }
    std::cout << "]" << std::endl;
}

bool compareInt(void *data1, void *data2) {
    int a = *(int *) data1;
    int b = *(int *) data2;
    return a == b;
}

bool comparePerson(void *data1, void *data2) {
    Person *a = (Person *) data1;
    Person *b = (Person *) data2;
    return a->name == b->name && a->age == b->age;
}

int main(void) {
    DynamicArray<int> array(5);
    array.add(10);
    array.add(20);
    array.add(30);
    array.set(3, 40);
    array.add(50);

    array.set(array.size(), 60);

    for (int i = 0; i < 50; ++i) {
        array.add(i);
    }

    array.foreach ();
    int b = array.indexOf(2, compareInt);
    std::cout << b << std::endl;

    std::cout << std::endl;
    Person p1 = {"zhangsan", 18};
    Person p2 = {"zhang", 18};
    Person p3 = {"zhan", 18};
    DynamicArray<Person> arr(5);
    arr.add(p1);
    arr.add(p2);
    arr.foreach ();

    int a = arr.indexOf(p1, comparePerson);
    std::cout << a << std::endl;

    return 0;
}

优缺点

优点：
- 无需为线性表中的逻辑关系增加额外的空间
- 可以快速的获取表中合法位置的元素
缺点：
- 插入和删除操作需要移动大量元素

动态数组 ​

接口设计 ​

插入、删除分析 ​

时间复杂度 ​

C语言int实现 ​

C语言void*实现 ​

C++int类型实现 ​

C++泛化实现 ​

解决泛化以后存在的问题 ​

优缺点 ​