数据结构与算法—c++实现（刷题前必会基础）

• 线性表
• • 线性表顺序表示（SeqList）
  • • 类模板定义
  • 线性表链式表示
  • • 类模板定义

1. 增：（判断条件）是否超过最大容量；下标参数是否1~length范围内；（长度）更新增加后的长度；（操作）操作身边后操作自身；
2. 删：（判断条件）下标参数是否1~length范围内；（长度）更新删除后的长度；（操作）操作自身后操作身边；
3. 查：（根据下标查-判断条件）下标参数是否1~length范围内；（根据值查-循环条件）遍历顺序表，满足条件直接返回，未找到遍历到末尾再返回，两种完成循环的方式；
4. 改：（判断条件）下标参数是否1~length范围内；

SeqList 增删查改。

//SeqList

template 
class SeqList
{
protected:
	int length;//当前SeqList长度
	int maxlength;//SeqList最大容量
	ElemType *elems;//SeqList的元素
public:
	//增删改查
	//初始表内存、初始化表内容
	SeqList(int size=DEFAULT_SIZE);
	SeqList(ElemType v[], int n, int size=DEFAULT_SIZE);
	//析构
	virtual ~SeqList();
	//遍历
	void Traverse(void (*Visit)(const ElemType &)) const;
	//查_元素值_返回下标
	int LocateElem(const ElemType &e);
	//查_元素下标int i
	Status GetElem(int i, ElemType &e) const;
	//改_元素下标
	Status SetElem(int i, ElemType &e);
	//删_元素下标
	Status DeleteElem(int i, ElemType &e);
	//增_元素下标
	Status InsertElem(int i, const ElemType &e);//有无const???
	//增_表尾
	Status InsertElem(const ElemType &e);

	//附加
	int GetLength() const;//长度
	bool Isempty() const;//判断是否为空
	void Clear();//清空
	SeqList(const SeqList &sa);//复制构造函数
	SeqList &operator = (const SeqList &sa);//赋值语句重载
};

构造函数

template 
SeqList::SeqList(ElemType v[], int n, int size)
{
	//三个数据成员初始化赋值
	elems = new ElemType[size];
	assert(elems);
	maxlength = size;
	length = n;
	for(int i=0; i < length; i++)
		elems[i] = v[i];
}

析构函数

template 
SeqList::~SeqList()
{
	delete []elems;
}

三个数据成员都可访问
遍历

template 
void SeqList::Traverse(void (*Visit)(const ElemType &)) const
{
	for(int i=0; i 
查_元素值_返回下标（有没有）
 
template 
int SeqList::LocateElem(const ElemType &e) const
{
	int i=0;
	while(i < length && elems[i]!=e)//循环截止条件_先操作再判断是否超范围
		i++;
	return i 
查_元素下标
 
template 
Status SeqList::GetElem(int i, ElemType &e) const
{
	if(i < 1 || i > length)//边界判断条件_先判断是否超范围再操作
		return NOT_PRESENT;
	else {
		e = elems[i-1];
		return ENTRY_FOUND;
	}
}
 
改_元素下标
 
template 
Status SeqList::SetElem(int i, const ElemType &e)
{
	if(i < 1 || i > length)//边界判断条件_先判断是否超范围再操作
		return RANGE_ERROR;
	else {
		elems[i-1] = e;
		return SUCCESS;
	}
}
 
删_元素下标_自身+身边两部分
 
template 
Status SeqList::DeleteElem(int i, ElemType &e)
{
	if(i < 1 || i > length)//边界判断条件_先判断是否超范围再操作
		return RANGE_ERROR;	
	else {
		e = elems[i-1];
		for(int j=i; j 
增_元素下标
 
template 
Status SeqList::InsertElem(int i, const ElemType &e)
{
	if(length == maxlength)//边界判断条件_最大容量
		return OVER_FLOW;
	else if(i < 1 || i > length)//边界判断条件_先判断是否超范围再操作
		return RANGE_ERROR;
		else {
			for(int j=length; j >=i; j--)
				elems[j] = elems[j-1];
			elems[i-1] = e;
			length++;
			return SUCCESS;
		}		
}
 
线性表链式表示 
类模板定义