用c++模板实现数据结构的静态线性表

 

//——————-Sqlist.h———————–

#ifndef SQ_H
#define SQ_H

template <class Elemtype>
class Sqlist{
public:
 Sqlist();
 ~Sqlist();
public:
 Elemtype *GetE();
 int GetLength();
 int GetListSize();
private:
 Elemtype *elem;
 int length;
 int listsize;
public:
 int InitSlist();//构造一个空的线性表
 int DestorySlist();//销毁线性表
 int ClearSlist();
 bool IsEmpty();
 int SlistLength();
 int GetElem(int i,Elemtype &e);//找的第i个元素
 int SlistInsert(int i,Elemtype e);//在i之前插入元素
 int SlistDelete(int i,Elemtype &e);//删除第i个元素
};

#endif

//———————–Common.h———————–

#ifndef COMMON_H
#define COMMON_H

＃i nclude <stdio.h>
＃i nclude <malloc.h>
＃i nclude <string.h>
＃i nclude <stdlib.h>
＃i nclude <iostream>
using namespace std;

#define LIST_INIT_SIZE 100
#define LIST_ADD 10

#define OK 1
#define EOR 0

typedef struct {
 char *name;
 char *number;
 char *sex;
}Elemtype;

#endif

//————————-Sqlist.cpp—————————-

＃i nclude “Sqlist.h”

template <class Elemtype>
Sqlist<Elemtype>::Sqlist()
{
 InitSlist();
}

template <class Elemtype>
Sqlist<Elemtype>::~Sqlist()
{
 free(elem);
}

template <class Elemtype>
Elemtype *Sqlist<Elemtype>::GetE()
{
  return elem;
}

template <class Elemtype>
int Sqlist<Elemtype>::GetLength()
{
 return length;
}

template <class Elemtype>
int Sqlist<Elemtype>::GetListSize()
{
 return listsize;
}

template <class Elemtype>
int Sqlist<Elemtype>::DestorySlist()
{
 if(elem)
 {
  free(elem);//free空间后，还要把那些length和size都给初始化了。
  elem=NULL;
  length=0;
  listsize=0;
  return OK;
 }
 return EOR;
}

template <class Elemtype>
int Sqlist<Elemtype>::ClearSlist()
{
 if(elem)
 {
  length=0;//长度设置为0。就是所谓的空了。
  return OK;
 }
 return EOR;
}

template <class Elemtype>
bool Sqlist<Elemtype>::IsEmpty()
{
 if(length!=0)
  return false;//不是空的
 return true;//是空的
}

template <class Elemtype>
int Sqlist<Elemtype>::SlistLength()
{
 return length;
}

template <class Elemtype>
int Sqlist<Elemtype>::GetElem(int i,Elemtype &e)
{
 if( (i>=1) && (i<=length) )
 {
  e=elem[i-1];
  return OK;
 }
 return EOR;
}
//下面三个主要程序,不深入Elemtype里面，所以可以看做一个单元处理，让整个程序变成通用的静态

template <class Elemtype>
int Sqlist<Elemtype>::InitSlist()
{
 elem=(Elemtype *)malloc(LIST_INIT_SIZE*sizeof(Elemtype));
 //Elemtype *elem=new Elemtype(LIST_INIT_SIZE*sizeof(Elemtype));
 if(!elem)
  exit(EOR);
 length=0;
 listsize=LIST_INIT_SIZE;
 return OK;
}

template <class Elemtype>
int Sqlist<Elemtype>::SlistInsert(int i,Elemtype e)
{
 Elemtype *q,*p;
 if( (i<1) || (i>length+1) )
  return EOR;
 if(length>=listsize)
 {
  elem=(Elemtype *)realloc(elem,(listsize+LIST_ADD)*sizeof(Elemtype));
  if(!elem) exit(EOR);
  listsize=listsize+LIST_ADD;
 }
 q=&elem[i-1];// 得到第i位置的指针，接着就是后移动元素了
 for(p=&(elem[length-1]);p>=q;p–) *(p+1)=*p;
 *q=e;
 ++length;
 return OK;
}

template <class Elemtype>
int Sqlist<Elemtype>::SlistDelete(int i,Elemtype &e)
{
 Elemtype *q,*p;
 if( (i<1) || (i>length) )
  return EOR;
 q=&elem[i-1];
 e=*q;
 for(p=q+1;p<=&elem[length-1];p++)*(p-1)=*p;
 length–;
 return OK;
}

//————main.cpp——————-

＃i nclude “Common.h”
＃i nclude “Sqlist.h”
＃i nclude “Sqlist.cpp”

int main()
{
 //Sqlist<Elemtype> *stu=new Sqlist<Elemtype>;
 Sqlist<Elemtype> stu;
 Elemtype e;
 for(int i=1;i<=5;i++)
 {
  e.name=(char *)malloc(sizeof(char));
  e.number=(char *)malloc(sizeof(char));
  e.sex=(char *)malloc(sizeof(char));
  if((!e.name) || (!e.number) || (!e.sex))
   return EOR;
  cout<<”Please input the Student Name:”<<endl;
  cin>>e.name;
  cout<<”Input the number”<<endl;
  cin>>e.number;
  cout<<”Input your sex”<<endl;
  cin>>e.sex;
  stu.SlistInsert(i,e);
 }
 for(i=0;i<5;i++)
 {
  cout<<”—————————”<<endl;
  cout<<stu.GetE()[i].name<<ends<<stu.GetE()[i].number<<ends<<stu.GetE()[i].sex<<endl;
  cout<<”—————————”<<endl;
 }
 //delete stu;
 return OK;
}