顺序表的实现 C++代码

使用了模板。使用的时候直接导入头文件即可。代码实现相关细节、解释都在注释里了。
那么就直接上代码了。

// MySeqList.h 文件
#ifndef __MYSEQLIST_H__
#define __MYSEQLIST_H__
#include <iostream>

#define InitSize 10									// 动态数组的初始尺寸
#define IncSize 5									// 当动态数组存满数据后每次扩容所能多保存的数据元素数量

template<typename T>
class SeqList
{
public:
	SeqList(int length = InitSize);					 // 构造函数，参数可以有默认值
	~SeqList();							// 析构函数

public:			// 接口
	bool ListInsert(int i, const T& e);				// 在第i个位置插入指定元素
	bool ListDelete(int i);						// 删除第i个位置的元素
	bool GetElem(int i, T& e);					// 获取第i个位置的元素，值通过形参引用方式返回
	int LocateElem(const T& e);					// 按元素值查找其在顺序表中第一次出现的位置

	void DispList();						// 输出顺序表中所有元素
	int ListLength();						// 获取顺序表长度
	void ReverseList();						// 反转顺序表

private:
	void IncreaseSize();						// 当顺序表满了，扩容函数

private:
	T* m_data;							// 存放顺序表中的元素
	int m_length;							// 当前长度
	int m_maxsize;							// 最大容量
};

// 通过构造函数对顺序表进行初始化
template<typename T>
SeqList<T>::SeqList(int length)
{
	m_data = new T[length];
	m_length = 0;							// 顺序表当前长度为0，表示还没有存储任何元素
	m_maxsize = length;						// 顺序表最大容量
}

// 通过析构函数对顺序表进行资源释放
template<typename T>
SeqList<T>::~SeqList()
{
	delete[] m_data;
	m_data = nullptr;
	m_length = 0;
	m_maxsize = 0;
}

// 顺序表元素插入
// 在第i个位置(位置编号从1开始)插入指定元素e
// 时间复杂度为O(n)，时间开销主要是缘于元素的移动
template<typename T>
bool SeqList<T>::ListInsert(int i, const T& e)
{ 
	// 如果数组表已经存在，则不允许再插入数据，当前先这样，后续课程再完善
	if (m_length >= m_maxsize)
	{
		IncreaseSize();		// 存满了，扩容
	}
	// 判断插入位置i是否合法，i的和法治应该时从1到m_length+1之间
	if (i < 1 || i >(m_length + 1))
	{
		std::cout << "元素" << e << "插入位置" << i << "不合法，合法的位置是[1~" << m_length + 1 << "]." << std::endl;
		return false;
	}
	// 从最后一个元素开始向前遍历到要插入新元素的第i个位置，
	// 分别将这些位置中原有的元素向后移动一个位置
	for (int j = m_length; j >= i; --j)
	{
		m_data[j] = m_data[j - 1];
	}
	m_data[i - 1] = e;			// 在指定位置i出插入元素e，因为数组下标从0开始，所以这里用i-1表示插入位置所对应的数组下标
	std::cout << "成功在位置为" << i << "处插入元素" << m_data[i - 1] << std::endl;
	++m_length;
	return true;
}

// 删除第i个位置的元素
template<typename T>
bool SeqList<T>::ListDelete(int i)
{
	if (m_length < 1)				// 空的元素表
	{
		std::cout << "空列表，无法进行删除操作!" << std::endl;
		return false;
	}
	if (i < 1 || i > m_length)
	{
		std::cout << "删除的位置" << i << "不合法，合法的位置是[1~" << m_length << "]!" << std::endl;
		return false;
	}
	// 从数组中第i+1个位置开始向后遍历所有元素，分别将这些位置中原有的元素向前移动一个位置。
	for (int j = i; j < m_length; ++j)
	{
		m_data[j - 1] = m_data[j];					// 依次往前移动
	}
	--m_length;								// 实际表长-1
	std::cout << "成功删除位置为:" << i << "的元素，该元素的值为:" << m_data[i - 1] << "!" << std::endl;
	return true;
}

// 获取第i个位置的元素值
template<typename T>
bool SeqList<T>::GetElem(int i, T& e)				// 参数e是引用类型参数，确保将该值带回调用者
{
	if (m_length < 1)					// 空的元素表
	{
		std::cout << "空列表，无法获取任何数据!" << std::endl;
		return false;
	}
	if (i < 1 || i > m_length)
	{
		std::cout << "获取元素的位置" << i << "不合法，合法的位置是[1~" << m_length << "]!" << std::endl;
		return false;
	}
	e = m_data[i - 1];
	std::cout << "成功获取位置为:" << i << "的元素，该元素的值为:" << e << "!" << std::endl;
	return true;
}

// 按元素值查找其在顺序表中第一次出现的位置
template<typename T>
int SeqList<T>::LocateElem(const T& e)				// 参数e是引用类型参数，确保将该值带回调用者
{
	for (int i = 0; i < m_length; ++i)
	{
		if (m_data[i] == e)
		{
			std::cout << "值为" << e << "的元素在顺序表中第一次出现的位置为" << i + 1 << "!" << std::endl;
			return i + 1;				// 返回位置应该用数组 下标值+1
		}
	}
	// 走到这里，在该顺序表中没有找到对应的值
	std::cout << "值为" << e << "的元素在顺序表中没有找到!" << std::endl;
	return -1;						// 返回-1表示查找失败
}

// 顺序表元素的其他常用操作
 // 输出顺序表中所有元素
template<typename T>
void SeqList<T>::DispList()  
{
	for (int i = 0; i < m_length; ++i)
	{
		std::cout << m_data[i] << "  ";
	}
	std::cout << std::endl;
}
// 获取顺序表的长度
template<typename T>
int SeqList<T>::ListLength()
{
	return m_length;
}
// 翻转顺序表reverse，时间复杂度O(n)
template<typename T>
void SeqList<T>::ReverseList()
{
	if (m_length <= 1)
	{
		// 如果顺序表中没有元素或者只有一个元素，那么就不用做任何操作
		return;
	}
	T temp;							// 中间变量
	for (int i = 0; i < m_length / 2; ++i)
	{
		temp = m_data[i];
		m_data[i] = m_data[m_length - i - 1];  
		// 第一个和最后一个交换，依次往后走 第二个和倒数第二交换...
		m_data[m_length - i - 1] = temp;
	}
	return;
}

// 顺序表的扩展操作
// 当顺序表存满数据后可以调用此函数为顺序表扩容,时间复杂度为O(n)
template<typename T>
void SeqList<T>::IncreaseSize()
{
	T* p = m_data;
	m_data = new T[m_maxsize + IncSize];
	// 重新为顺序表分配更大的内存空间
	for (int i = 0; i < m_length; ++i)
	{
		m_data[i] = p[i];				// 将数据复制到新区域
	}
	m_maxsize += IncSize;					// 顺序表最大长度郑家IncSize
	delete[] p;
}
#endif // __MYSEQLIST_H__

测试Demo

// 文件名：main.cpp
#include <iostream>
using namespace std;
#include "MySeqList.hpp"
namespace _nmsp1
{
	typedef struct
	{
		int m_data[10];  // 静态数组来保存顺序表中的元素
		 // 最多能存储10个元素
		int m_length;  // 顺序表中当前实际长度(已存在的元素个数)
	} SeqList;

	typedef struct
	{
		int* m_data; // 顺序表中的元素保存在m_data所指向的动态数组内存中
		int m_length;  // 顺序表中当前实际长度(已存在的元素个数)
		int m_maxsize;   // 动态数组最大容量，因为动态数组可以扩容，因此要记录该值
	} SeqList_Dync;
}

#include <vector>

int main()
{
	SeqList<int> seqobj(10);
	seqobj.ListInsert(1, 15);
	seqobj.ListInsert(2, 10);
	seqobj.ListInsert(30, 8);
	seqobj.ListDelete(1);
	seqobj.ListDelete(3);

	int eval = 0;
	bool get_res = seqobj.GetElem(1, eval);
	 // 如果get_res值为true，则eval中保存着获取到的元素值

	int findvalue = 10;  // 在顺序表中要找的元素值
	int find_res = seqobj.LocateElem(findvalue);
	findvalue = 22;  // 这里改为了22，表示查找值22这个元素的下标
	find_res = seqobj.LocateElem(findvalue);

	seqobj.ListInsert(2, 100);
	seqobj.DispList();
	std::cout << "当前顺序表中存在元素个数:" << seqobj.ListLength() << std::endl;
	seqobj.ReverseList();
	seqobj.DispList();

	for (int i = 3; i < 20; ++i)
	{
		seqobj.ListInsert(i, i * 2);
	}
	std::cout << "当前顺序表中存在元素个数:" << seqobj.ListLength() << std::endl;
	seqobj.DispList();
	return 0;
}

测试结果