课程设计--基于模板的顺序表的使用

• 顺序表功能
• • 正文
  • • 顺序表创建
    • 顺序表尾插
    • 顺序表插入
    • 顺序表删除
    • 顺序表逆序
    • 顺序表读取
  • 结尾

数据结构顺序表课设，附带功能：尾插、定点插入、按照内容单插多插、定点删除、按照内容单删多删、元素逆置等。

作为顺序表，创建时需要带有一个默认的数组大小，这里的大小就用define定义了。

#define defaultSize 200

之后开始创建顺序表的基础部分：

template 
class Seq
{
protected:
	T* data;        //存放数组
	int maxSize = 0;//最大可容纳表项的项数
	int last = 0;   //当前已存表项的最后位置(从0开始)
public:
	Seq(int sz = defaultSize) {//构造函数
	    if (sz > 0) {
		maxSize = sz; last = 0;
		data = new T[maxSize];//创建顺序表存储数组
		if (data == NULL) {   //动态分配失败
		    cout << "动态分配失败" << endl;
			return false；
		}
	}
	~Seq() {
		delete[] data;
	}
	int Size() {
		return maxSize;
	}
	int Length() {
		return last;
	}
};

有了顺序表的主体，那就开始一点点的铺设功能。首先给它创建一个尾插，把输入的数据依次插入顺序表中，组成顺序表中的数据。

template
bool Seq::Push_back(T x)
{
	if (last == maxSize) { //表满
		cout << "表满,不可插入!" << endl;
		return false;
	}
	data[last] = x;  //插入(新表项在data[last]处)
	last++;//已用空间+1
	return true;  //插入成功
}

数据输入时，难免存在漏输的问题，这就需要有一个插入函数，总不能删了重输或者迭代查找吧。

template 
bool Seq::Insertn(int& i, T x) //顺序表位插算法
{
	if (last == maxSize) {//表满
		cout << "表满,不可插入!" << endl;
		return false;
	}
	if (i<1 || i>last) {//参数i不合理
		cout << "参数输入错误!" << endl;
		return false;
	}
	for (int j = last; j >= i; j--) //依次后移
		data[j] = data[j - 1];
	data[i - 1] = x;//插入(第i表项在data[i-1]处)
	last++;
	return true;  //插入成功
}
template 
bool Seq::Insertd(int& n, T& x, T y) //顺序表值插算法，n为单多插提示数据
{
	if (last == maxSize) {//表满
		cout << "表满,不可插入!" << endl;
		return false;
	}
	for (int i = 2; i <= last + 1; i++) {
		if (data[i - 2] == x && n == 0) {//单插部分
			if (i != last + 1) {
				for (int j = last; j >= i; j--) //依次后移
					data[j] = data[j - 1];
			}
			data[i - 1] = y;//插入(第i表项在data[i-1]处)
			last++;
			break;
		}
		if (data[i - 2] == x && n == 1) {//多插部分
			if (i != last + 1) {
				for (int j = last; j >= i; j--) //依次后移
					data[j] = data[j - 1];      //这里有好几种多插方法，不过最简单的还是写这种，不过就是O（）有点大。
			}
			data[i - 1] = y;//插入(第i表项在data[i-1]处)
			last++;
			i++;
		}
	}
	return true;  //插入成功
}

输入多了的删除。

template 
bool Seq::Removen(int& i) //按位删
{
	if (last == -1) { //表空,不能删除
		cout << "表空,不可删除!" << endl;
		return false;
	}
	else if (i<1 || i>last) {//参数i不合法
		cout << "参数输入错误!" << endl;
		return false;
	}
	for (int j = i; j <= last; j++) {
		data[j - 1] = data[j];//依次前移
	}
	last--;//最后位置减1
	return true;//删除成功
}
template 
bool Seq::Removed(int& i, T& x)//按值删，i为单删多删的识别符
{
	if (last == -1) { //表空,不能删除
		cout << "表空,不可删除!" << endl;
		return false;
	}
	int i0 = 0, n = 0;
	for (int j = 0; j < last; j++) {//同一个for循环
		if (data[j] == x && i == 0) {//识别到就打断
			break;
		}
		if (data[j] != x) {//识别不到就执行数据迁移
			data[i0] = data[j];
		    i0++;
		}
	}
	if (i == 0) {//处理单插被打断部分
		for (int j = i0 + 1; j < last; j++) {
			data[j - 1] = data[j];//依次前移
		}
		last--;//只删除了一个，-1
	}
	else if (i == 1) {
		last = i0;//删除多个，可用空间就是删除后的序号值
	}
	return true;
}

二分交换数据，没什么好说的。

template 
bool Seq::Reverse()
{
	if (last == 0) { //表空,不能执行
		cout << "表空,不可执行!" << endl;
		return false;
	}
	for (int i = 0; i < last / 2; i++) {
		T tmp = data[i];
		data[i] = data[last - 1 - i];
		data[last - 1 - i] = tmp;
	}
	return true;
}

能往外读取的顺序表才是好顺序表。

template 
T Seq::Read(int i)
{
	if (i<1 || i>last) {//参数i不合理
		cout << "参数输入错误!" << endl;
		return false;
	}
	return data[i - 1];
}

这里的顺序表只是些比较常用的功能，而且代码也就这些量，就不上传文件了。
另外这个是从我作业的mfc封装好的头文件里拆的，可能会有些许地方报错；至于头文件的补全，应该差个iostream了。
Ps：由于本人才疏学浅，错误纰漏之处在所难免，如果您在阅读的过程中发现了文章的错误和不足，欢迎交流学习与指正。