順序表

上篇先來(lái)看順序表，順序表就是使用物理位置來(lái)表示邏輯位置的線性表

由于面向過(guò)程的C語(yǔ)言在描述數(shù)據(jù)結(jié)構(gòu)時(shí)存在天然的弱勢(shì)，所以還是選擇一門面向?qū)ο蟮恼Z(yǔ)言來(lái)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)比較好些，這里用C++

List.hpp

class List {
    //內(nèi)部存儲(chǔ)
    int *arr;
    //List的容量
    int size;
    //List已經(jīng)存的元素?cái)?shù)量
    int length;
    
public:
    //構(gòu)造函數(shù)，size表示容量
    List(int size);
    //析構(gòu)函數(shù)，用于釋放申請(qǐng)的內(nèi)存
    ~List();
    //清空線性表
    void clearList();
    //判斷空表
    bool listEmpty();
    //線性表的長(zhǎng)度
    int listLength();
    //根據(jù)下標(biāo)獲取值
    int getElem(int index);
    //尋找第一個(gè)等于e的元素的位序
    int locateElem(int e);
    //尋找元素e的前驅(qū)
    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;
    }
}