1、线性表
2、线性表的抽象数据类型描述
3、线性表的数组描述
按照上述抽象描述，定义一个模板类来描述上述的抽象描述。
template<class T>
class LinearList
{
public:
LinearList(int MaxListSize = 10); //构造函数
~LinearList() //析构函数
{
delete []element; //删除堆空间
}
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所在的位置
LinearList<T>& Delete(int k,T& x); //删除第k个元素并将它返回到x中
LinearList<T>& Insert(int k,const T& x); //在第k个元素之后的位置插入x
void Output(ostream& out) const; //输出线性表内容
private:
int MaxSize; //线性表可容纳最大长度
int length; //线性表中非空的长度
T *element; //线性表数组头指针
};
下面依次分析各种操作。
3.1 Create()操作
Create()创建一个空线性表，对应的就是类的构造函数操作。构造函数里面首先要的就是对空间的分配，当然要确定类成员变量的值。
/* 构造函数 */ template<class T> LinearList<T>::LinearList(int MaxListSize) { MaxSize = MaxListSize; element = new T[MaxSize]; length = 0; }
3.2 Destory()操作
Destory()操作主要就是对线性表对象分配的堆空间进行回收。
~LinearList() //析构函数 { delete []element; //删除堆空间 }
3.3 isEmpty()操作
isEmpty()操作很简单，就是判断线性表是否为空。检查是否为空只需检查类length的值是否为零。
bool isEmpty() const //判断线性表是否为空
{
return (length == 0);
}
3.4 Length()操作
Length()操作就是要返回线性表的所含元素的个数。
int Length() const //线性表长度
{
return length;
}
3.5 Find()操作
bool Find(int k,T& x) const;操作是将线性表中的第k个元素返回到x中，这里操作里面要注意的就是判断标号k是否是在线性表的范围内，若不在范围内，则返回false。
/*
返回第k个元素到x中
*/
template<class T>
bool LinearList<T>::Find(int k,T& x) const
{
if(k > length || k < 0)
return false;
x = element[k];
return true;
}
3.6 Search()
Search()函数就是查找传入的参数是否在线性表中，如果不在返回-1，如果在线性表中则返回该元素在线性表中的索引。
/*
遍历整个数组，发现被查找元素和数组中元素匹配则返回该元素位置
如果在数组中没有发现被查找元素，则返回-1
*/
template<class T>
int LinearList<T>::Search(const T& x) const
{
for(int i=0; i<length; ++i)
{
if(x == element[i])
return i;
}
return -1;
}
3.7 Delete()操作
Delete()操作要从线性表中删除一个元素，如果有该元素就删除，并返回到x；如果不存在该元素则抛出异常。要注意长度的变化。
/* 从线性表中删除一个元素 */ template<class T> LinearList<T>& LinearList<T>::Delete(int k,T& x) { if(!Find(k,x)) //如果序列中没有该元素则抛出异常 { throw "Out of Bounds"; } //将第k个元素后的元素依次往前移动一个位置，覆盖掉第k个元素 for(int i = k+1; i<length; ++i) { element[i-1] = element[i]; } length -= 1; //线性表长度减少一个长度 return *this; }
3.8 Insert()操作
Insert()是在索引k的后面插入一个元素，返回当前线性表；需要检查k是否在可插入的范围内。重要的是要检查当前线性表分配的空间是否已经存储满了。要注意长度的变化。
/*
在第k个元素的后面插入一个元素
*/
template<class T>
LinearList<T>& LinearList<T>::Insert(int k,const T& x)
{
if(k > length || k < 0)
{
//抛出异常
throw "插入元素位置不正确！";
}
if(length == MaxSize)
{
//抛出异常，空间不足
throw "空间不足";
}
//将第k个元素后面的元素都往后移动一个单位
for(int i=length; i>k; --i)
{
element[i] = element[i-1];
}
element[k] = x;
length += 1;
return *this;
}
3.9 Output()操作
为了使线性表数据可视化。
/* 输出线性表内容 */ template<class T> void LinearList<T>::Output(ostream& out) const { out << endl <<"print list element: " << endl; for (int i = 0; i < length; i++) { out << element[i] << " "; } out << endl; }
4、实现源码
tips：模板类的定义和实现要放在一个文件里面，不然会报错！！
.h文件
#ifndef __LINEARLIST_H__
#define __LINEARLIST_H__
#include <iostream>
using namespace std;
template<class T>
class LinearList
{
public:
LinearList(int MaxListSize = 10); //构造函数
~LinearList() //析构函数
{
delete []element; //删除堆空间
}
bool isEmpty() const //判断线性表是否为空
{
return (length == 0);
}
int Length() const //线性表长度
{
return length;
}
bool Find(int k,const T& x); //在第k个元素之后的位置插入x
void Output(ostream& out) const; //输出线性表内容
private:
int MaxSize; //线性表可容纳最大长度
int length; //线性表中非空的长度
T *element; //线性表数组头指针
};
/*
构造函数
*/
template<class T>
LinearList<T>::LinearList(int MaxListSize)
{
MaxSize = MaxListSize;
element = new T[MaxSize];
length = 0;
}
/*
返回第k个元素到x中
*/
template<class T>
bool LinearList<T>::Find(int k,T& x) const
{
if(k > length || k < 0)
return false;
x = element[k];
return true;
}
/*
遍历整个数组，发现被查找元素和数组中元素匹配则返回该元素位置
如果在数组中没有发现被查找元素，则返回-1
*/
template<class T>
int LinearList<T>::Search(const T& x) const
{
for(int i=0; i<length; ++i)
{
if(x == element[i])
return i;
}
return -1;
}
/*
从线性表中删除一个元素
*/
template<class T>
LinearList<T>& LinearList<T>::Delete(int k,x)) //如果序列中没有该元素则抛出异常
{
throw "Out of Bounds";
}
//将第k个元素后的元素依次往前移动一个位置，覆盖掉第k个元素
for(int i = k+1; i<length; ++i)
{
element[i-1] = element[i];
}
length -= 1; //线性表长度减少一个长度
return *this;
}
/*
在第k个元素的后面插入一个元素
*/
template<class T>
LinearList<T>& LinearList<T>::Insert(int k,const T& x)
{
if(k > length || k < 0)
{
//抛出异常
throw "插入元素位置不正确！";
}
if(length == MaxSize)
{
//抛出异常，空间不足
throw "空间不足";
}
//将第k个元素后面的元素都往后移动一个单位
for(int i=length; i>k; --i)
{
element[i] = element[i-1];
}
element[k] = x;
length += 1;
return *this;
}
/*
输出线性表内容
*/
template<class T>
void LinearList<T>::Output(ostream& out) const
{
out << endl <<"print list element: " << endl;
for (int i = 0; i < length; i++)
{
out << element[i] << " ";
}
out << endl;
}
/*
重载<<运算符
*/
template <class T>
ostream& operator<<(ostream& out,const LinearList<T>& x)
{
x.Output(out);
return out;
}
#endif // !__LINEARLIST_H__
.c文件
#include <iostream>
#include "LinearList.h"
using namespace std;
int main()
{
LinearList<int> list(10);
cout << "Length = " << list.Length() << endl;
cout << "IsEmpty = " << list.isEmpty() << endl;
list.Insert(0,2);
list.Insert(1,6);
list.Insert(2,8);
list.Insert(0,4);
list.Output(cout);
int x;
list.Delete(2,x);
list.Output(cout);
cout << "IsEmpty = " << list.isEmpty() << endl;
return 0;
}
运行结果：
