顺序表实现

动态扩容版本

• 定义顺序表数据结构

  • 为了实现类似数组的动态数组的功能，首先要定义一种新的结构类型

    typedef int data_type; // 定义元素的数据类型
    typedef struct {
        data_type* pdata;
        int capacity;
        int size;
    } vector;

  • 类型初始化

    vector* init() {
        vector* ret = (vector*)malloc(sizeof(vector));
        if (ret == NULL)
            return NULL; // C++则可以使用throw抛出异常
        ret->pdata = NULL;
        ret->size = 0;
        ret->capacity = 0;
        return ret;
    }

  注：

  • 示例代码初始化后，在堆区创建一个**vector*的指针维护这个顺序表**
  • 新初始化的类型中，元素个数、容量初始化为0，维护的内存指针新建为NULL

• 销毁函数

    void destory(vector* ptr) {
        // C++则可以使用throw抛出异常
        assert(ptr && ptr->pdata);
  
        free(ptr->pdata);
        free(ptr);
    }

  其中涉及到两种错误类型判断：

  • ptr传参非法，处理方法：使用assert()
  • ptr中记录的内存指针ptr->pdata非法，处理方法：使用assert()

• 实现接口

  • 扩容函数

    static void check_capacity(vector* ptr) {
        // 检查容量是否足够，并自动增容
        assert(ptr);
    
        if (ptr->capacity == ptr->size) {
            int newcapacity = (ptr->capacity == 0) ? 4 : ptr->capacity * 2;
            data_type* ptmp = (data_type*)realloc(ptr->pdata, newcapacity * sizeof(data_type));
            if (ptmp == NULL)
                exit(0);
            else {
                ptr->pdata = ptmp;
                ptr->capacity = newcapacity;
            }
        }
    }

    其中涉及到两种错误类型判断：

    • ptr传参非法，处理方法：使用assert()
    • realloc()开辟内存失败，处理方法：判空，错误时exit(0)

    扩容后，维护的内存空间变大了，并把capacity记录的容量增加了

  • insert()

    void insert(vector* ptr, int pos, data_type data) {
        assert(pos <= ptr->size);
        check_capacity(ptr);
    
        // 将最后一个元素至pos位置（含pos）的元素全部后移一位
        int i = 0;
        for (i = ptr->size - 1; i >= pos; --i)
            ptr->pdata[i + 1] = ptr->pdata[i];
        ptr->pdata[pos] = data;
        ptr->size++;
    }

  • erase()

    void erase(vector* ptr, int pos) {
        assert(pos < ptr->size && pos >= 0);
    
        // 将pos位置（不含pos）至最后位置的的元素全部前移一位并覆盖
        int i = 0;
        for (i = pos; i <= (ptr->size - 2); ++i)
            ptr->pdata[i] = ptr->pdata[i + 1];
        ptr->size--;
    }

  • 尾插、头插、尾删、头删

    void push_back(vector* ptr, data_type data) {
        insert(ptr, ptr->size, data);
    }
    
    void push_front(vector* ptr, data_type data) {
        insert(ptr, 0, data);
    }
    
    void pop_back(vector* ptr) {
        erase(ptr, ptr->size - 1);
    }
    
    void pop_front(vector* ptr) {
        erase(ptr, 0);
    }

  • 查找

    data_type at(vector* ptr, int pos) {
        // 按索引查找
        return ptr->pdata[pos];
    }
    
    int find(vector* ptr, data_type target) {
        // 按值查找，找不到返回-1
        int i = 0;
        for (i = 0; i < ptr->size; i++)
            if (ptr->pdata[i] == target)
                return i;
        return -1;
    }

    注：按值查找时，涉及到元素判断相等，若涉及到自定义的类型作为数据结构的元素，则需要重写这部分的代码

  • 其他接口

    bool empty(vector* ptr) {
        // 判空
        return ptr->size == 0;
    }
    
    int size(vector* ptr) {
        // 元素个数
        return ptr->size;
    }

静态数组版本

const int N = 1e5 + 10; // 数据范围
int arr[N], arr_size; // 顺序表、元素个数

void clear() {
    arr_size = 0;
}

void insert(int pos, int x) {
    // 将最后一个元素至pos位置（含pos）的元素全部后移一位
    for (int cur = arr_size; cur >= pos; --cur)
        arr[cur + 1] = arr[cur];
    arr[pos] = x;
    arr_size++;
}

void erase(int pos) {
    // 将pos位置（不含pos）至最后位置的的元素全部前移一位并覆盖
    for (int cur = pos; cur <= arr_size; cur++)
        arr[cur] = arr[cur + 1];
    arr_size--;
}

void push_back(int x) {
    insert(arr_size + 1, x);
}

void push_front(int x) {
    insert(1, x);
}

void pop_back() {
    erase(arr_size);
}

void pop_front() {
    erase(1);
}

int at(int pos) {
    return arr[pos];
}

int find(int data) {
    // 按值查找，找不到返回-1
    for (int i = 1; i <= arr_size; ++i)
        if (data == arr[i])
            return i;
    return -1;
}

void change(int pos, int data) {
    arr[pos] = data;
}