C++ 数据结构学习一(顺序表)

//SequentialList.h 顺序表模板类

#ifndef SEQUENTIAL_LIST_HXX
#define SEQUENTIAL_LIST_HXX

using std::cout;

using std::endl;

const int MaxSize=100;   //顺序表数组最大值

template<class T>
class SeqList    //定义模板类SeqList(顺序表)
{
  public:

    SeqList() { length=0; }    //无参构造函数,建立一个空的顺序表
    SeqList(T a[],int n);      //有参构造函数,建立一个长度为n的顺序表 n不大于MaxSize
    ~SeqList() {}         //析构函数

    int Length() { return length; } //求线性表长度

    T Get(int i);          //按位查找,在线性表中查找第i个元素

    int Locate(T x);        //按值查找,在线性表中找值为x的元素序号

    void Insert(int i,T x);     //插入操作,在线性表中的第i个位置插入值为x的元素

    T Delete(int i);        //删除操作,删除线性表的第i个元素

    void PrintList();        //遍历操作,按序号依次输出各元素

  private:
    T data[MaxSize];      //存放数据元素的数组
    int length;         //线性表的长度
};

template<class T>
SeqList<T>::SeqList(T a[],int n)
{
  if(n>MaxSize) throw "参数非法";
  for(int i=0;i<n;i++)
    data[i]=a[i];
  length=n;
}

template<class T>
T SeqList<T>::Get(int i)
{
  if(i<1||i>length) throw "参数非法";
  return data[i-1];
}

template<class T>
int SeqList<T>::Locate(T x)
{
  for(int i=0;i<length;i++)
  if(data[i]==x) return i+1;  //下标为i的元素等于x,返回其序号i+1
  return 0;           //退出循环,说明查找失败
}

template<class T>
void SeqList<T>::Insert(int i,T x)
{
  if(length>=MaxSize) throw "上溢";
  if(i<1||(i>length+1)) throw "位置溢出";
  for(int j=length;j>=i;j--)
    data[j]=data[j-1];       //注意第j个元素存在于数组小标为j-1处
  data[i-1]=x;
  length++;
}

template<class T>
T SeqList<T>::Delete(int i)
{
  if(length==0) throw "下溢";
  if(i<1||i>length) throw "位置";
  T x=data[i];          //取出位置i的元素
  for(int j=i;j<length;j++)
    data[j-1]=data[j];      //此处j已经是元素所在的数组下表
  length--;
  return x;
}

template<class T>
void SeqList<T>::PrintList()
{
  for(int i=0;i<length;i++)
    cout<<data[i];        //依次输出线性表的元素值
}

#endif

//seqlisttest.cpp
#include <iostream>
#include "SequentialList.h"
using std::cout;
using std::endl;

int main()
{
  int m[10]={1,2,3,4,28,50,7,8,9,10};
  SeqList<int> seqList(m,10);

  cout<<"顺序表原始状态"<<endl;
  seqList.PrintList();
  cout<<"顺序表第5个元素值"<<seqList.Get(5)<<endl;
  cout<<"顺序表长度"<<seqList.Length()<<endl;

  cout<<"顺序表删除一个元素后的状态"<<endl;
  seqList.Delete(5);
  seqList.PrintList();
  cout<<"顺序表第5个元素值"<<seqList.Get(5)<<endl;
  cout<<"顺序表长度"<<seqList.Length()<<endl;

  cout<<"顺序表增加一个元素后的状态"<<endl;
  seqList.Insert(5,108);

  seqList.PrintList();

  cout<<"顺序表第5个元素值"<<seqList.Get(5)<<endl;
  cout<<"顺序表长度"<<seqList.Length()<<endl;

  cout<<"顺序表中数值=108在表中第"<<seqList.Locate(108)<<"位"<<endl;

  return 0;

}

上一篇:Oracle 数据库简单操作


下一篇:Vue生命周期简介和钩子函数