数据结构和算法之线性表（C++）

线性表的顺序存储结构的特点是，用物理上的邻接关系表达逻辑上的前驱和后继，因此可以通过简单的公式获取表中的任意元素的地址，但是在插入和删除过程中需要移动大量元素，同时对存储空间的利用不是很合理。接下来我用C++的模板式编程来实现线性表的基本功能

template<typename T>
class Linearlist
{
public:
	Linearlist() {};
	virtual bool Isempty()const { return length; };
	virtual bool Find(int k, T &b)const = 0;
	virtual bool Delete(int k, T &b) = 0;
	virtual bool Insert(int k, const T&b) = 0;
	virtual void Output(ostream &out) const = 0;
	virtual ~Linearlist() {};
private:
	int length;
};

这里利用了抽象函数来实现线性表和链表的一些基本功能，其中判断是否为空不是抽象类，因为判断是否为空的实现方式比较类似，通过多态可以实现。其他的为纯虚函数，便于接下来对线性表的表达。

template<typename T>
class LinearListSqu : public Linearlist<T>
{
public:
	LinearListSqu(int Maxlistsize = 10);
	~LinearListSqu() { if (element) { delete[]element; } };
	virtual bool Isempty()const { return length == 0; };
	virtual int Length()const { return length; };
	virtual bool Find(int k, T &b)const;
	virtual bool Delete(int k, T &b);
	virtual bool Insert(int k, const T&b) ;
	virtual void Output(ostream &out) const;
protected:
	int Maxsize;
	T *element;
	int length;
};

这里是抽象类的继承，通过使用指针数组的方式来创建一个线性表，同时在结尾需要对指针的释放，防止内存泄露，其中的思路比较简单，最后还用到了输出运算符重载（<<的重载），使其可以输出对象的元素，简化了后续的步骤。

class Nomem
{
public:
	Nomem() { cout << "memory is not enough" << endl; };
	~Nomem() {};

private:

};

class OutofBound
{
public:
	OutofBound() { cout << "out of bound"; };
	~OutofBound() {};

private:

};

这里是检查函数是否出现异常进行异常处理，采用了防御式编程的思想

template<typename T>
LinearListSqu<T>::LinearListSqu(int Maxlistsize)
{
	Maxsize = Maxlistsize;
	try
	{
		element = new T[Maxsize];
	}
	catch (...)
	{
		throw Nomem();
	}
	length = 0;
}

template<typename T>
bool LinearListSqu<T>::Find(int k, T &b)const
{
	if (k<1||k>length)
	{
		return false;
	}
	else
	{
		b = element[k - 1];
		return true;
	}
}

template<typename T>
void LinearListSqu<T>::Output(ostream &out) const
{
	for (int i = 0; i < length; i++)
	{
		out << element[i] << " ";
	}
}

template<typename T>
ostream &operator << (ostream &out,LinearListSqu<T>& b)
{
	b.Output(out);
	return out;
}

template<typename T>
bool LinearListSqu<T>::Insert(int k, const T &b)
{
	if (k < 0 || k > length)
	{
		throw OutofBound();
	}
	if (length == Maxsize)
	{
		throw Nomem();
	}
	for (int i = length-1; i >=k; i--)	//第几个数字减一得到指针的序数，例如 1，2，3，4，5，6  转化为指针地址为0，1，2，3，4，5
	{
		element[i + 1] = element[i];
	}	//最后一个数字减一后从k算起
	element[k] = b;	//在移出来的空位补一个元素
	length++;	//长度加一
	return true;
}

template<typename T>
bool LinearListSqu<T>::Delete(int k, T &b)
{
	if (Find(k ,b))
	{
		for (int i = k; i < length; i++)
		{
			element[i - 1] = element[i];
			length--;
			return true;
		};
	}
	else throw OutofBound();
}

这里便是对线性表功能的基本实现，具体思路很清晰，大家理解应该没什么问题
最后便是主函数的实现，用于测试该线性表的正确性。

int main()
{
	try
	{
		LinearListSqu<int>L (5);
		cout << "length==" << L.Length() << endl;
		cout << "is empty" << L.Isempty() << endl;
		bool ok = false;
		ok = L.Insert(0, 2);
		if (!ok)cout << "ok" << endl;
		L.Insert(1, 6);
		L.Insert(2, 8);
		cout << "List = " << L << endl;
		cout << "Is Empty" << L.Isempty() << endl;
		int z;
		L.Find(1, z);
		cout << "First element is" << z << endl;
		cout << "Length = " << L << endl;
		L.Delete(1, z);
		cout << "Delete element is" << z << endl;
		cout << "List is" << L << endl;
	}
	catch (...)
	{
		cout << "An exception has occured" << endl;
	}
}

这就是该线性表的简单实现，笔者为了练习而写的，如果有不好的地方欢迎大家批评指正。

最后

以上就是强健马里奥为你收集整理的数据结构和算法之线性表（C++）的全部内容，希望文章能够帮你解决数据结构和算法之线性表（C++）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。