[C++知识库]C实现 顺序表 的主要接口

顺序表Sequence List

C语言的数组就是一种顺序表，在内存中用一段连续的空间存储数据。

顺序表是一种数据结构，不同的数据结构对数据有不同的存储规则，体现出不同的特性，但总归是数据组织形式的一种抽象。基本的操作应该具有：增 删 查 改。下面我们用C来实现一个顺序表，让它能够添加数据、删除数据、查找数据、改数据。

结构

顺序表的主体数组。

为了实现增删查改，需要有个size来记录已经存储的元素个数；

为了让顺序表可以扩容，需要有个capacity来记录当前数组的容量，且数组应该是malloc出来的而非静态的。

那么整体的结构应该用struct来实现。

typedef struct SeqList{
    int * array;
    int size;
    int capacity;
}SeqList;

为了数据的可扩展性，改进一下

/* SequenceList的结构 */
typedef int SLDataType; //若想存储double或其他类型的数据，在这里改

typedef struct SeqList {
    SLDataType* array;//存储数据
    int size;//有效数据个数
    int capacity;//array的容量
}SeqList;

初始化与销毁

众所周知，变量在使用时是要初始化的 比如int n = 0;//经常就顺便初始化为0了 ，所以我们也要把上面的结构体初始化一波。

对assert(ps);说明一下：函数中任何指针参数，都有必要防止它传入空指针，因此多数情况下，会把所涉及到的指针都assert一下。

void SeqListInit(SeqList* ps){
    assert(ps);
    
    ps->array = NULL;
    ps->size = 0;
    ps->capacity = 0;
}

因为要实现的顺序表能扩容，array的空间是malloc出来的，所以在用完顺序表之后必须销毁，我们必须提供销毁空间的接口。

void SeqListDestroy(SeqList* ps){
    assert(ps);
    
    if(ps->array){
        free(ps->array);
    	ps->array = NULL;
        ps->size = 0;
        ps->capacity = 0;
    }
}

尾插PushBack和尾删PopBack

顺序表的尾插尾删效率很高，因为有个size记录元素个数。（尾插：尾部插入数据）

写尾插之前，必须考虑容量问题，事实上，只要需要添加数据，就需要检查容量。

检查容量

void static CheckCapacity(SeqList* ps) {
    assert(ps);

    //根据size和capacity的关系决定是否扩容
    if (ps->size == ps->capacity) {
        /*	若size==capacity==0(即顺序表刚开始用),则默认给4个空间,若是用完空间了,则扩容2倍	*/
        int newCapacity = ps->size ==0 ? 4 : 2 * ps->capacity;

        SLDataType* tmp = (SLDataType*)realloc(ps->array, newCapacity * sizeof(SLDataType));
        if (tmp == NULL) {
            perror("CheckCapacity :: Reallocation Failed");
            exit(-1);
        }
        ps->array = tmp;
        ps->capacity = newCapacity;
    }
}

关于函数的命名：

以下函数的命名均是参考了C++STL库的命名习惯，建议使用。当然，命名没有绝对的标准，比如把尾插写成Append也未尝不可。

但是就不要用拼音了，会被嘲笑的！

尾插数据

void PushBack(SeqList* ps , SLDataType element){
    assert(ps);
    
    //首先检查容量
    CheckCapacity(ps);
    //添加数据
    ps->array[ps->size] = element;
    ps->size ++;
}

尾删数据（删除最后1个元素）

void PopBack(SeqList* ps){
    assert(ps);
    
    //避免非法删除
    assert(ps->size > 0);
    
    ps->size --;
}

说明一下，尾删只需要直接把size – 就行了，因为size本身就意味着数组的有效长度，也就是说，用户在使用这个数组时，必须认为size就是数组的长度（即遍历数组时共遍历size次for(i=0;i<size;i++){}）。

头插PushFront和头删PopFront

头插

void PushFront(SeqList* ps, SLDataType element){
    assert(ps);
    //检查容量
    CheckCapacity(ps);
    
    //数组整体往后挪动1个单位 ——从后往前挪动
    for(int i = ps->size-1; i >= 0; i--){
        ps->array[i+1] = ps->array[i];
    }
    //插入element
    ps->array[0] = element;
    ps->size++;
}

头删

【2022_10_30更新：增加了assert(ps->size>0);，防止没有元素之后还去pop，导致size变成-1，如果size==-1，到时候再去Push数据时，会越界访问！】

void PopFront(SeqList* ps){
    assert(ps);
    
    //当数组里没有元素时不能删！
    assert(ps->size>0);
    
    //数组整体往前覆盖1个单位 ——从前往后覆盖
    for(int i = 0; i < ps->size-1; i++){
        ps->array[i] = ps->array[i+1];
    }
    ps->size--;
}

可以看到，顺序表的头插、头删 时间复杂度为O(N)，后面可以学习到 有链表来弥补这个缺点。

任意位置插入Insert

void SeqListInsert(SeqList* ps, size_t position ,SLDataType element){
    assert(ps);
    assert(position >= 0 && position <= ps->size); //在有效范围内插入数据
    
    //检查容量
    CheckCapacity(ps);
    
    if(position == 0){ //头插
        PushFront(ps,element);
        
    }else if(position == ps->size){ //尾插
        PushBack(ps,element);
        
    }else{ //其他位置
        //挪动
        for(int i = ps->size; i > position; i--){
            ps->array[i] = ps->array[i-1];
        }
        ps->array[position] = element;
    }
    
    ps->size++;
}

【2022_10_30更新：改进插入，只实现Insert，PushBack、PushFront都能复用Insert】

/*所有位置插入Insert*/
void SeqListInsert(SeqList* ps, int position, SLDataType element) {
    assert(ps);
    assert(position >= 0 && position <= ps->size);

    //检查容量
    CheckCapacity(ps);

    //挪动数据——从后往前挪动
    if (position != ps->size) {
        for (int i = ps->size - 1; i >= position; i--) {
            ps->array[i + 1] = ps->array[i];
        }
    }

    //插入element到position位置
    ps->array[position] = element;
    ps->size++;
}

/* SequenceList的尾插PushBack*/
void PushBack(SeqList* ps, SLDataType element) {
    SeqListInsert(ps, ps->size, element);
}

/*头插PushFront*/
void PushFront(SeqList* ps, SLDataType element) {
    SeqListInsert(ps, 0, element);
}

任意位置删除Erase

void SeqListErase(SeqList* ps, size_t position){
    assert(ps);
    assert(position >= 0 && position <= ps->size); //在有效范围内删除数据
    
    if(position == 0){ //头删
        PopFront(ps,element);
        
    }else if(position == ps->size){ //尾删
        PopBack(ps,element);
        
    }else{ //其他位置
        //覆盖
        for(int i = position; i < ps->size-1; i++){
            ps->array[i] = ps->array[i+1];
        }
    }
    
    ps->size--;
}

【2022_10_30更新：改进删除，只实现Erase，PopBack、PopFront都能复用Erase】

/*任意位置删除Erase*/
void SeqListErase(SeqList* ps, int position) {
    assert(ps);
    assert(position >= 0);
    assert(position < ps->size);

    //覆盖数据
    if (position != ps->size - 1) {
        for (int i = position; i < ps->size - 1; i++) {
            ps->array[i] = ps->array[i + 1];
        }
    }
    
    ps->size--;
}

/*SequenceList的尾删PopBack*/
void PopBack(SeqList* ps) {
    SeqListErase(ps, ps->size - 1);
}

/*头删PopFront*/
void PopFront(SeqList* ps) {
    SeqListErase(ps, 0);
}

查找Search

/*
	根据'值'查找，返回所查找的元素'第一次出现时'的下标
	若找不到，则返回-1
*/
void SeqListSearch(SeqList* ps, SLDataType element){
    assert(ps);
    
    //遍历数组
    for(int i = 0; i < ps->size; i++){
        if(ps->array[i] == element){
            return i;
        }
    }
    
    return -1;
}