基础数据结构与算法

第一章：线性结构

顺序表

对于一个顺序表，我们可以不需要因为结点逻辑关系额外增加开销做到随机访问与修改，但是只能在实现删除与插入，平均移动约一半的元素，并且预先分配空间过小容易溢出，过大容易浪费；

#pragma once
using namespace std;
template<typename T> class SeqList{//动态顺序表
private:
    #define _OVERFLOW 3
    #define _ERROR -1
    #define _OUT_OF_RANGE -1
    #define _MAXSIZE 1024
    #define _FAIL -1
    T *elem;
    int size;
    int capacity;

public:
    SeqList(){//初始化
        elem=new T[_MAXSIZE];
        if(!elem){
            std::cout<<"OVERFLOW"<<std::align_val_t;
            exit(_OVERFLOW);
        }
        size=0;
        capacity=_MAXSIZE;
    }

    ~SeqList(){//销毁
        if(elem){
            delete elem;
            elem=NULL;
            size=0;
            capacity=0;
        }
    }

    clear(){//清空，保持头部指针和容量不变
        size=0;
    }

    T size(){//返回容器的大小
        return size;
    }

    bool empty(){
        return size==0;
    }

    const T& at(int index){
        if(index<0||index>size){
            std::cout<<"ERROR:ArrayIndexOutOfBoundsException"<<std::endl;
            exit(_OUT_OF_RANGE);
        }
        return *(elem+index);
    }
    const *T& begin(){//第一个元素的指针，并没有整个iterator
        return elem;
    }
    const *T& end(){//末尾元素的下一个位置
        return elem+size;
    }
    const T& front(){//头部元素的引用
        return *elem;
    }
    const T& back(){//末尾元素的引用
        return *(elem+size-1);
    }
    T& operator[] (int index){//重载[]访问与修改元素，不给出越界提示
        return *(elem+index);
    }
    const T& operator[](int index){//允许对const对象的访问
        return *(elem+index);
    }
    const *T& find(*T beg,*T end,T value){
        for(*T tmp=beg;tmp!=end;tmp++){
            if(*tmp==value) return tmp;
        }
        return this.end();//找不到返回表尾
    }
    //在顺序表L中第i个数据元素之前插入数据元素e 
    insert(int pos,T value){
        if(pos>=_MAXSIZE) {
            std::cout<<"OVERFLOW"<<std::endl;
            exit(_OVERFLOW);
        }
        else if(pos<=0||pos>size+1) {
            std::cout<<"ERROR:ArrayIndexOutOfBoundsException"<<std::endl;
            exit(_OUT_OF_RANGE);
        }
        for(int i=size;i>pos;i--){
            elem[i]=elem[i-1];
        }//增加数据应该从后面开始移动
        elem[pos]=value;
        size++;
        if(size==capacity) {//size变化可能会触发扩容机制
            capacity*=2;
            upd_elem=new T[capacity];
            for(int i=0;i<size;i++){
                upd_elem[i]=elem[i];
            }
            delete elem;
        }
    }

    //删除指定位置pos的数据
    erase(int pos){
        if(pos>=_MAXSIZE) {
            std::cout<<"OVERFLOW"<<std::endl;
            exit(_OVERFLOW);
        }
        else if(pos<0||pos>=size) {
            std::cout<<"ERROR:ArrayIndexOutOfBoundsException"<<std::endl;
            exit(_OUT_OF_RANGE);
        }
        for(int i=pos;i<size;i++){
            pos[i]=pos[i+1];
        }
        size--;
    }
};

第二章：递归与分治

第三章：树与图

第四章：线性规划