线性表之顺序表和链表

父类的线性表ADT

template <class T> 
class List  {
      void clear(); 				 	// 置空线性表
      bool isEmpty();				 	// 线性表为空时，返回True
      bool append(T value);		 		// 在表尾添加一个元素value，表的长度增1
      bool insert(int p, T value);	 		// 在位置p上插入一个元素value，表的长度增1
      bool del(int p); 			 	// 删除位置p上的元素，表的长度减 1
      T getValue(int p);			 	// 返回位置p的元素值 
      T setValue(int p, T value);	 		// 用value修改位置p的元素值
}; 

顺序表的ADT

template <class T> // 假定顺序表的元素类型为T
class arrList : public List<T>
{							   // 顺序表，向量
private:					   // 线性表的取值类型和取值空间
	int maxSize;			   // 私有变量，顺序表实例的最大长度
	int curLen;				   // 私有变量，顺序表实例的当前长度
	int position;			   // 私有变量，当前处理位置
	T *aList;				   // 私有变量，存储顺序表的实例
public:						   // 顺序表的运算集
	arrList(const int size);   // 创建一个新的顺序表，参数为表实例的最大长度
	~arrList();				   // 析构函数，用于消除该表实例
	int getPos(const T value); // 在线性表中查找值为value的元素，并返回第1次出现的位置
	void print();

	void clear();				 // 将顺序表存储的内容清除，成为空表
	bool isEmpty();				 // 线性表为空时，返回True
	bool append(T value);		 // 在表尾添加一个元素value，表的长度增1
	bool insert(int p, T value); // 在位置p上插入一个元素value，表的长度增1
	bool del(int p);			 // 删除位置p上的元素，表的长度减 1
	int length();				 // 返回此顺序表的当前实际长度
	T getValue(int p);			 // 返回位置p的元素值
	T setValue(int p, T value);	 // 用value修改位置p的元素值
								 // 打印线性表
};

链表的ADT

链表节点ADT

template <class T>
class Link{
public:
	T data; // 用于保存节点的元素
	Link<T> *next; // 只向后记节点的指针
	Link(const T info, const Link<T>* nextValue=NULL);
	Link( Link<T>* nextValue=NULL);
};

链表ADT

template <class T>
class lnkList : public List<T>
{
private:
	Link<T> *head, *tail; //单链表的指针
public:
	lnkList();
	lnkList(int s);
	~lnkList();
	void clear();
	bool isEmpty();
	bool append(const T value);
	bool insert(const int p, const T value);
	bool del(const int i);
	T getValue(int p);			// 返回位置p的元素值
	T setValue(int p, T value); // 用value修改位置p的元素值

	Link<T> *getPos(const int p); //第p个元素指针
	int length();
	void print();
};