C++数据结构----顺序表

线性结构：

• 除了外，每个元素都有它的前趋和后继
• 每个元素,它的前驱是,它的后继是
• 只有后继，没有前驱；只有前驱，没有后继

• 创建一个空的线性表create()----C++中一般用构造函数解决
• 清除一个线性表clear()----删除线性表的所有数据元素
• 求线性表的长度Length()----也就是求目前线性表中的元素个数

增加insert(i,x)

• 在线性表第i个位置插入元素x----

删除remove(i)

• 删除线性表第i个位置的元素

查

• 查索引search(x)-----给定元素x，查找是否存在，存在返回x的位置
• 访问元素visit(i)-----给定索引，访问该位置的元素
• 遍历元素traverse()-----顺序访问元素的所有位置

template
class list{
    public:
    //少了create函数，因为在具体实现时，构造函数可以满足该功能
    virtual void clear()=0;
    virtual int Length() const=0;
    virtual void insert(int i,const elemType& x)=0;
    virtual void remove(int i)=0;
    virtual int search(const elemType& x) const=0;
    virtual elemType visit(int i) const=0;
    virtual void traverse() const=0;
    virtual ~list(){};//析构函数，delete指针，防止内存泄露
};

注意，这里基本操作加上virtual原因，是希望其继承类必须实现该函数功能

有关查的操作，如果不希望改变或者不能改变传参的值，要加上const关键字

 用动态数组去实现

数据成员----

• 线性表第一个元素的起始地址的指针----data
• 数组规模maxsize----也就是目前的数组容量上限
• 数组中当前的元素个数----curLength

template
class seqList:public list{
    private:
    elemType* data;
    int maxsize;
    int curLength;
    public:
    seqList(int initSize=10);//构造函数，默认初始化长度为10
    void clear(){ curLength=0;}
    int Length() const{ return curLength;}
    void insert(int i,const elemType& x);
    void remove(int i);
    int search(const elemType& x) const;
    elemType visit(int i) const{
        if(i 
 
 
为了解决插入元素的容量不足问题，即---curLength==maxsize
 
 
需要做一个隐式扩容操作，即容量满后，私有函数去进行扩容，用户无需知道，给用户造成数组永远不会满的假象
 
 
private  void doublespace();
 
 
具体实现---保存在seqList.h文件
 
#ifndef MY_seqlist
#define MY_seqlist
#include"list.h"
template
class seqList:public list{
    private:
    elemType* data;
    int maxsize;
    int curLength;
    void doublespace();
    public:
    seqList(int initSize=10);//构造函数，默认初始化长度为10
    void clear(){ curLength=0;}
    int Length() const{ return curLength;}
    void insert(int i,const elemType& x);
    void remove(int i);
    int search(const elemType& x) const;
    elemType visit(int i) const{
        return data[i];
    }
    void traverse() const;
    ~seqList(){delete[] data;}
};
//私有扩容操作
template
void seqList::doublespace(){
       elemType* tmp=data;
       maxsize*=2;
       data=new elemType[maxsize];
       for(int i=0;i
seqList::seqList(int initSize){
    data =new elemType[initSize];
    maxsize=initSize;
    curLength=0;
}
//查元素
template
int seqList::search(const elemType& x) const{
    int i;
    for(i=0;i
void seqList::insert(int i,const elemType& x){
    //是否需要扩容？
    if(curLength==maxsize){
        doublespace();
    }
    //当前第i个位置直到最后的元素右移一位，把第i个位置空出来
       for(int j=curLength;j>i;j--){
             data[j]=data[j-1];
       }
    //x放到当前索引位置i，然后表长+1
       data[i]=x;
       ++curLength;
}
//删除
template
void seqList::remove(int i){
     for(int j=i;j
using namespace std;
template
void seqList::traverse() const{
    for(int i=0;i 
 插入函数也可以这样写
 
template
int seqList::search(const elemType& x) const{
    int i;
   
    for(int i=0;i 
主程序的测试用例程序---maintest.cpp
 
#include"list.h"
#include
using namespace std;
int main(){
    seqList seq;
    seq.insert(0,19);
    seq.insert(1,18);
    seq.insert(2,88);
    seq.insert(3,6);
    seq.traverse();
    cout< 
最初的list.h文件
 
#ifndef MY_list
#define MY_list
template
class list{
    public:
    //少了create函数，因为在具体实现时，构造函数可以满足该功能
    virtual void clear()=0;
    virtual int Length() const=0;
    virtual void insert(int i,const elemType& x)=0;
    virtual void remove(int i)=0;
    virtual int search(const elemType& x) const=0;
    virtual elemType visit(int i) const=0;
    virtual void traverse() const=0;
    virtual ~list(){};//析构函数，delete指针，防止内存泄露
};
#include"seqList.h"
#endif