【数据结构】线性表(数组实现)

前端之家收集整理的这篇文章主要介绍了【数据结构】线性表(数组实现)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。


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;
}



运行结果:

原文链接:https://www.f2er.com/datastructure/382540.html

猜你在找的数据结构相关文章