数据结构之线性表（上）

顺序表

上篇先来看顺序表，顺序表就是使用物理位置来表示逻辑位置的线性表

由于面向过程的C语言在描述数据结构时存在天然的弱势，所以还是选择一门面向对象的语言来学习数据结构比较好些，这里用C++

List.hpp

class List {
    //内部存储
    int *arr;
    //List的容量
    int size;
    //List已经存的元素数量
    int length;
    
public:
    //构造函数，size表示容量
    List(int size);
    //析构函数，用于释放申请的内存
    ~List();
    //清空线性表
    void clearList();
    //判断空表
    bool listEmpty();
    //线性表的长度
    int listLength();
    //根据下标获取值
    int getElem(int index);
    //寻找第一个等于e的元素的位序
    int locateElem(int e);
    //寻找元素e的前驱
    bool priorElem(int e,int *preElem);
    //寻找元素e的后继
    bool nextElem(int e,int *nextElem);
    //在指定i位置上插入元素e
    bool listInsert(int i,int e);
    //删除指定位置的元素，返回给e
    bool listDelete(int i,int *e);
    //遍历
    void listTraverse();
};

List.cpp

List::List(int size){
    this->size = size;
    length = 0;
    arr = new int[size];
}

List::~List(){
    delete [] arr;
    arr = nullptr;
}

void List::clearList(){
    length = 0;
}

bool List::listEmpty(){
    return length == 0;
}

int List::listLength(){
    return length;
}

int List::getElem(int index){
    return arr[index];
}

int List::locateElem(int e){
    for (int i = 0; i < length; i++) {
        if (arr[i] == e) {
            return i;
        }
    }
    return -1;
}

bool List::priorElem(int e,int *preElem){
    int index = locateElem(e);
    
    if (index!=-1 && index!=0) {
        *preElem = arr[index-1];
        return true;
    }else{
        return false;
    }
}

bool List::nextElem(int e,int *nextElem){
    int index = locateElem(e);
    if (index!=-1 && index!=length-1) {
        *nextElem = arr[index+1];
        return true;
    }else{
        return false;
    }
}

bool List::listInsert(int i,int e){
    
    if (i<0 || i>length) {
        return false;
    }
    
    for (int k = length-1; k >= i; k--) {
        arr[k+1] = arr[k];
    }
    arr[i] = e;
    length++;
    return true;
}

bool List::listDelete(int i, int *e){
    if (i<0 || i>length) {
        return false;
    }
    
    *e = arr[i];
    for (int k = i+1; i < length; k++) {
        arr[k-1] = arr[k];
    }
    length--;
    return true;
}

void List::listTraverse(){
    for (int i = 0; i < length; i++) {
        std::cout<<arr[i]<<std::endl;
    }
}