Data Structure1

Before：JaneZ决定早点开始DS的学习（虽然可能已经不算早了呜呜呜），所以：DS , 启动！

Data Structure 1 线性表List

线性表的定义

• 线性结构的定义：所有结点按一对一的邻接关系构成的整体就是线性结构
• 线性表是处理线性结构的数据结构
• 线性表中数据元素的个数称为线性表的长度

线性表的基本运算：

• 创建空线性表 create
• 删除线性表中所有数据元素 clear
• 求长度 length
• 插入元素 insert
• 删除元素 remove
• 搜索元素 search
• 返回特定位置元素值 visit
• 按序访问每一数据元素 traverse

线性表的抽象类

template<class elemType>
class list{
    public:
        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(){};
};

线性表的顺序实现

• 将线性表的数据元素存储在一块连续的空间里，用存储位置反映数据元素间的关系
  

顺序表的定义

• 从线性表的抽象类list公有派生

  template<class elemType>
  class seqList: public list <elemType>{
  
      private:
  
          elemType *data;
          int currentLength;
          int maxSize;
          void doubleSpace();
  
      public:
  
          seqList(int initSize = 10);
          ~seqList();
          void clear();
          int length() const;
          void insert(int i,const elemType& x);
          void remove(int i);
          int search(const elemType& x) const;
          elemType visit(int i)const;
          void traverse()const;
  };

顺序表实现

template<class elemType>
seqList<elemType>::seqList(int initsize){
    data = new elemType[initsize];
    maxsize = initsize;
    currentLength = 0;
}

template<class elemType>
seqList<elemType>::~seqList(){
    delete []data;
}

template<class elemType>
void seqList<elemType>::clear(){
    currentLength = 0;
}
(是个伪清除)

template<class elemType>
int seqList<elemType>::length(){
    return currentLength;
}

template<class elemType>
int seqList<elemType>::search(const elemType&x)const{
    int i;
    for(i = 0;i < currentLength && data[i] != x; i ++);
    if(i == currentLength){
        return -1;
    }else{
        return i; 
    }
}

template<class elemType>
elemType seqList<elemType>::visit(int i)const{
    return data[i];
}

template<class elemType>
void seqList<elemType>::traverse()const{
    cout << endl;
    for(int i = 0;i < currentLength; i ++){
        cout << data[i]<< ' ';
    }
}

单独讨论插入删除函数

template<class elemType>
void seqList<elemType>::doubleSpace(){
    elemType *tmp = data;
    maxSize *= 2;
    data = new elemType[maxSize];
    for(int i = 0;i < currentLength; i ++){
        data[i] = tmp[i];
    }
    delete []tmp;
}

template<class elemType>
void seqList<elemType>::insert(int i,const elemType& x){
    if(currentLength == maxSize){
        doubleSpace();
    }
    for(int j = currentLength; j > i ; j --){
        data[j] = data[j - 1];
    }
    data[i] = x;
    ++ currentLength;
}

template<class elemType>
void seqList<elemType>::remove(int i){
    for(int j = i;j < currentLength - 1; j ++){
        data[j] = data[j + 1];
    }
    -- currentLength;
}