C++顺序表的实现

xiaoxiao2021-02-28  11

顺序表是在计算机内存中以数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构。

顺序表的存储特点是:只要确定了起始位置,表中任一元素的地址都通过下列公式得到:LOC(ai)=LOC(a1)+(i-1)*L  1≤i≤n 其中,L是元素占用存储单元的长度。

 

#ifndef LIST_H #define LIST_H template <typename T> class List{ public:  virtual void InitList()=0;    //表初始化  virtual void DestoryList()=0;   //销毁表  virtual int Length()=0;     //求表长度  virtual const T & Get(int i)=0;   //取表中元素  virtual int Locate(T & x)=0;   //元素查找  virtual void Insert(int i,T & x)=0;  //插入新元素  virtual T Delete(int i)=0;    //删除元素  virtual bool Empty()=0;     //判断表是否为空  virtual bool Full()=0;     //判表是否满 }; #endif

 

 

#ifndef SEQLIST_H #define SEQLIST_H #include"List.h" #include<iostream> using namespace std;

template <typename T> class SeqList : public List<T>{  template <typename T>  friend ostream & operator<<(ostream & os,const SeqList<T> & sl); public:  SeqList(int m=20);  SeqList(T ary[],int n,int max);  ~SeqList(){   DestoryList();   delete [] ptr;  }  virtual void InitList(){curLen=0;}  virtual void DestoryList(){curLen=-1;max=0;}  virtual int Length(){return curLen;}  virtual T Get(int i);     //取表中元素  virtual int Locate(T & x);   //元素查找  virtual void Insert(int i,T & x);  //插入新元素  virtual T Delete(int i);    //删除元素  virtual bool Empty(){return curLen==0;}     //判断表是否为空  virtual bool Full(){return curLen==max;}     //判表是否满 private:  T * ptr;  int curLen;  int max; }; template <typename T> SeqList<T>::SeqList(int m){  max=m  curLen=0;  ptr=new T[max]; } template <typename T> SeqList<T>::SeqList(T ary[],int n,int max){  this->max=max;  curLen=0;  ptr=new T[max];  while(curLen<n){   ptr[curLen]=ary[curLen];   curLen++;  } } template <typename T> T SeqList<T>::Get(int i){  if (i>=1 && i<=curLen)   return ptr[i-1];  else   throw "元素位置错误!"; } template <typename T> int SeqList<T>::Locate(T & x){  for (int i=0;i<curLen; i++)   if (ptr[i]==x)    return i+1;     return 0;          } template <typename T> void SeqList<T>::Insert(int i,T & x){  if(Full())   throw "顺序表已满!";  if(i<1 || i>=curLen+1)   throw "插入位置错误!";  for(int j=curLen;j>=i;j--)   ptr[j]=ptr[j-1];  ptr[i-1]=x;  curLen++; } template <typename T> T SeqList<T>::Delete(int i){  T tmp;  if(Empty())   throw "顺序表空!";  if(i<1 || i>=curLen)   throw "删除位置错误!";  tmp=ptr[i-1];  for(int j=i-1;j<curLen-1;j++)   ptr[j]=ptr[j+1];  curLen--;  return tmp; } template <typename T> ostream & operator<<(ostream & os,const SeqList<T> & sl){  for(int i=0;i<sl.curLen;i++)   os<<sl.ptr[i]<<", ";  return os; } #endif

 

 

#include<iostream> #include"SeqList.h" using namespace std; int main(){  int ary[]={4,7,2,9,10,43,6},x=10,l;  SeqList<int> myList(ary,7,10);  cout<<myList<<endl;  try{   myList.Insert(7,x);   cout<<myList<<endl;  }catch(char * s){   cout<<s<<endl;  }  try{   myList.Delete(40);   cout<<myList<<endl;  }catch(char * s){   cout<<s<<endl;  }  cout<<"请依次输入插入元素的位置和值:";cin>>l>>x;  while(1){   try{    myList.Insert(l,x);    cout<<myList<<endl;    cout<<"请依次输入插入元素的位置和值:";cin>>l>>x;   }catch(char * s){    cout<<s<<endl;    break;   }  }  cout<<myList<<endl;

 return 0;

}

 

转载请注明原文地址: https://www.6miu.com/read-1950200.html

最新回复(0)