（数组描述）采用模板
#ifndef CLinearList_
#define CLinearList_
#include<iostream.h>
template<class T>
class CLinearList
{
public:
CLinearList(int MaxListSize=10); //构造函数
virtual ~CLinearList();
bool IsEmpty() const {return length== 0;}
int Length() const {return length;} //返回当前元素个数
bool Find(int k, T& x) const; //返回第k个元素保存至x中
int Search(const T& x) const; // 返回x所在位置
CLinearList<T>& Insert(int k, const T& x); // 在第k个位置插入x，从零开始算
CLinearList<T>& Delete(int k, T& x);
void Output(ostream& out) const;
private:
int length;
int MaxSize;
T *element; // 一维动态数组
};
template<class T>
CLinearList<T>::CLinearList(int MaxListSize)// 基于公式的线性表的构造函数
{
MaxSize = MaxListSize;
element = new T[MaxSize];
length =0;
}
template<class T>
bool CLinearList<T>::Find(int k, T& x) const
{ //把第k个元素取至x中
//如果不存在第k个元素则返回false，否则返回true
if (k<0 || k>length-1) // 不存在第k个元素
return false;
x=element[k];
return true;
}
template<class T>
int CLinearList<T>::Search(const T& x) const // 查找x，如果找到，则返回x所在的位置
{
// 如果x不在表中，则返回0
for (int i = 0; i < length; i++)
if (element[i] == x) return i;
return 0;
}
template<class T>
CLinearList<T>& CLinearList<T>::Delete(int k, T& x)
{// 把第k个元素放入x中，然后删除第k个元素
if (Find(k, x))
{
for (int i=k; i <length; i++)
element[i] = element[i+1]; // 把元素k+l, ...向前移动一个位置
length-- ;
return *this;
}
}
template<class T>
CLinearList<T>& CLinearList<T>::Insert(int k, const T& x)
{// 在第k个位置插入x
if (k < 0 || k >MaxSize-1)
cout<<"位置不对！"<<endl;
else if (length == MaxSize)
cout<<"超出数组最大长度！"<<endl;
else
{
if(length!=0)
{
for (int i=length-1;i>=k; i--)
element[i] = element[i-1];
}
element[k] = x;
length++ ;
}
return *this;
}
template<class T>
void CLinearList<T>::Output(ostream& out) const //把表输送至输出流 辅助函数，只要是为了重载<<，也可以用友元函数重载
{
for (int i = 0; i <length; i++)
out <<element[i] << " ";
}
// 重载<<
template <class T>
ostream& operator<<(ostream& out, const CLinearList<T>& x)
{
x.Output(out);
return out;
}
template<class T>
CLinearList<T>::~CLinearList()
{
delete [] element;
}
#endif
在主函数下调用：
#include "LinearList.h"
void main(void)
{
CLinearList<int> myList(5);
cout<<"线性表长度为："<<myList.Length()<<endl;
cout << "IsEmpty =" << myList.IsEmpty()<<endl;
cout << "Length = " << myList.Length() << endl;
myList.Insert(0,2).Insert(1,10).Insert(2,49);
cout << "IsEmpty =" << myList.IsEmpty() << endl;
cout << "List is" <<myList<<endl;
cout << "Length = " << myList.Length() << endl;
int z;
myList.Find(1,z);
cout << "位置为1的元素为：" << z << endl;
myList.Delete(2,z);
cout << "Deleted element is"<< z << endl;
cout << "List is " << myList << endl;
cout << "Length = " << myList.Length() << endl;
}
运行结果：
注：在VC6.0中，模板类不支持分离编译，需要把模板类的定义与声明放同一个文件中才可以。
采用链表描述：
/* *******************************链表描述**************************************/
template<class T> class Chain; //加上Chain模板声明，不加出错
template <class T>
class ChainNode{
friend class Chain<T>;//保证了Chain<T>可以访问ChainNode<T>的所有成员,尤其是私有成员。
private:
T data;
ChainNode<T> *link;
};
/*
创建空的整型线性表Chain<int> L;
*/
template<class T>
class Chain {
public:
Chain() {first = 0;}
~Chain() ;
bool IsEmpty() const {return first == 0;}
int Length() const;
bool Find(int k, T& x) const;
int Search(const T& x) const;
Chain<T>& Delete(int k, T& x);
Chain<T>& Insert(int k, const T& x);
void Output(ostream& out) const;
void Erase();
Chain<T> & Append(const T& x);
private:
ChainNode<T> *first; // 指向第一个节点的指针
ChainNode<T> *last;
};
template<class T>
Chain<T>::~Chain() //删除链表中的所有节点
{
// 链表的析构函数，用于删除链表中的所有节点
ChainNode<T> *next; // 下一个节点
while (first)
{
next = first->link;
delete first;
first = next;
}
}
template<class T>
int Chain<T>::Length() const //返回链表中的元素总数
{
ChainNode<T> *current = first;
int len = 0;
while (current) {
len++;
current = current->link;
}
return len;
}
template<class T>
bool Chain<T>::Find(int k, T& x) const
{// 寻找链表中的第k个元素，并将其传送至x
//如果不存在第k个元素，则返回f a l s e，否则返回t r u e
if (k < 1) return false;
ChainNode<T> *current = first;
int index = 1; // current的索引
while (index<k && current)
{
current = current->link;
index++;
}
if (current) {x=current->data; return true;}
return false; //不存在第k个元素
}
template<class T>
int Chain<T>::Search(const T& x) const
{// 寻找x，如果发现x，则返回x的地址
//如果x不在链表中，则返回0
ChainNode<T> *current = first;
int index = 1; // current的索引
while (current && current->data!= x) {
current=current->link;
index++ ;
}
if (current) return index;
return 0;
}
template<class T>
void Chain<T>::Output(ostream& out) const
{// 将链表元素送至输出流
ChainNode<T> *current;
for (current=first; current; current = current->link)
out<<current->data<<" ";
}
//重载<<
template <class T>
ostream& operator<<(ostream& out, const Chain<T>& x)
{
x.Output(out);
return out;
}
/*从链表中删除一个元素*/
template<class T>
Chain<T>& Chain<T>::Delete(int k, T& x)
{// 把第k个元素取至x，然后从链表中删除第k个元素
//如果不存在第k个元素，则引发异常OutOfBounds
if (k < 1 || !first)
cout<<"不存在第K个元素"<<endl; // 不存在第k个元素
// p最终将指向第k个节点
ChainNode<T> *p = first;
// 将p移动至第k个元素，并从链表中删除该元素
if (k == 1) // p已经指向第k个元素
first = first->link; // 删除之
else ( // 用q指向第k - 1个元素
ChainNode<T> *q = first;
for (int index = 1; index<k-1&&q; index++)
q = q->link;
if (!q || !q->link)
cout<<"不存在第K个元素！"<<endl; //不存在第k个元素
p = q->link; // 存在第k个元素
if (p == last)
last =q ;
q->link = p->link;) // 从链表中删除该元素
//保存第k个元素并释放节点p
x = p->data;
delete p;
return *this;
}
/*在链表中插入元素*/
template<class T>
Chain<T>& Chain<T>::Insert(int k, const T& x)
{//在第k个元素之后插入x
if (k < 0) cout<<"超出范围";
// p最终将指向第k个节点
ChainNode<T> *p = first;
//将p移动至第k个元素
for (int index = 1; index < k && p; index++)
p = p->link;
if (k > 0 && !p) tcout<<"不存在第K个元素"; //不存在第k个元素
// 插入
ChainNode<T> *y=new ChainNode<T>;
y->data = x;
if (k) {// 在p之后插入
y->link = p->link;
p->link = y;}
else {// 作为第一个元素插入
y->link = first;
first = y;}
if (!y->link)
last = y;
return *this;
}
template<class T>
void Chain<T>::Erase()
{ //删除链表中的所有节点
ChainNode<T> *next;
while (first)
{
next = first->link;
delete first;
first = next;
}
}
template <class T>
Chain<T> & Chain<T>::Append(const T& x)
{ //在链表尾部添加x
ChainNode<T> *y;
y = new ChainNode<T>;
y->data = x; y->link = 0;
if (first)
{//链表非空
last->link = y;
last= y;
}
else // 链表为空
first = last = y;
return *this;
}
在主函数中调用如下：
#include "LinearList.h"
void main(void)
{
cout<<"采用链表描述："<<endl;
Chain<int> myChain;
myChain.Append(3).Append(10);
cout<<"链表元素为："<<myChain<<endl;
}