1.定义

template<typename T>
struct SequenList
{
    int capacity;
    int size;
    T* element;
};

定义顺序表的结构,size是已有元素的数量,capacity是总共的容量,T* element是存放数据,不知道template<typename T>的含义的同学可以搜一搜c++泛型编程.(此部分也可以用class,创建类的方式来实现)

2.顺序表的创建与删除(构造与析构)

template<typename T>
void initSequenList(SequenList<T>* ptr,int cap){
    ptr->element = new T[cap];
    ptr->capacity = cap;
    ptr->size = 0;
    cout << "已成功初始化顺序表" <<endl;
}

template<typename T>
void deleteSequenList(SequenList<T>* ptr){
   delete[] ptr;
   ptr->element = nullptr;
   cout << "已成功删除顺序表" <<endl;
}

构造这个顺序表时,用new开辟空间,然后再依次定义各种变量的初值.析构时,使用delete[]表示删除此指针指向的一片内存而不是此顺序表的首地址的元素.

3.插入操作

template<typename T>
void insertElement(SequenList<T>*ptr,int index,T element){
    if(ptr->size == ptr->capacity){
        ptr->capacity = ptr->size*2;
        T* ptr1 = new T[ptr->capacity];
        for(int i=0;i<ptr->size;i++){
            ptr1[i] = ptr->element[i];
        }
        delete[] ptr;
        ptr->element = ptr1;
        ptr1 = nullptr;
    }
    if(index < 0 || index > ptr->capacity){
        throw std::invalid_argument("Invalid index");
    }
    for(int i = ((ptr->size)+1);i>index;i--){
        ptr->element[i] = ptr->element[i-1];
    }
    ptr->element[index] = element;
    ptr->size+=1; 
}
/*
插入,容量不够扩容,*2,转移数据,再插;index超出边界抛出异常;把index后面的元素往后移动一格,在index插入;
*/

当原始的顺序表的容量不足时要进行扩容,姑且定义为原来的两倍:用一个新的指针开辟一个新空间,此时新指针指向新空间,然后遍历一遍将原空间的元素拷贝到新空间.(其实此时需要一个个拷贝的时间复杂度为O(n),非常麻烦, 所以可以将ptr1[i] = ptr->element[i]改为ptr1[i] = move(ptr->element[i]),这里涉及到c++的移动语义,详细解释请见下文)

操作完成后删除原空间,将新指针指向的新空间的首地址赋给原指针,将新指针指控避免悬挂.

4.删除操作

/*
删除,把index位置的元素删掉,后面的元素往前挪一格;index超出范围报错
*/
template<typename T>
void deleteElement(SequenList<T>* ptr,int index){
    if(index < 0 || index > ptr->size){
        throw std::invalid_argument("Invalid index");
    }
    for(int i = index;i<ptr->size;i++){
        ptr->element[i] = ptr->element[i+1];
    }
    ptr->size-=1;
}

将索引index位置的元素删除后将后面的元素一个一个往前挪,又是一个时间复杂度为O(n)的操作,所以后面要引入链表

5.改和查

/*
改
*/
template<typename T>
void editElement(SequenList<T>* ptr,int index,T element){
    if(index < 0 || index > ptr->size){
        throw std::invalid_argument("Invalid index");
    }
    ptr->element[index] = element;
}

/*
查
*/
template<typename T>
T searchElement(SequenList<T>* ptr,int index){
    if(index < 0 || index > ptr->size){
        throw std::invalid_argument("Invalid index");
    }
    return ptr->element[index];
}
template<typename T>
int findElment(SequenList<T>* ptr,T element){
    for(int i=0;i<(ptr->size+1);i++){
        if(element == ptr->element[i])
        return i;
    }
    return -1;
}

此处较为简单,将指针指向处的元素进行修改和返回即可

6.其它操作

//打印所有元素
template<typename T>
void printAllElement(SequenList<T>* ptr){
    for(int i = 0;i<ptr->size;i++){
        cout << ptr->element[i] << " ";
        
    }
    cout << endl;
}
template<typename T>
bool isEmpty(SequenList<T>* ptr){
    if(ptr->size){
        return false;
    }
    return true;//空则为0,不空则为1
}
template<typename T>
int listSize(SequenList<T>* ptr){
    return ptr->size;
}