顺序表的实现（c++）

什么是顺序表

• 一个最简单的例子就是一维数组，它的特点就是在内存中进行顺序存储
• 在一块内存中，进行顺序存储的线性表就是顺序表
• 在任意时刻，数组的长度就是顺序表的最大存储容量

准备工作

#include<iostream>

#ifdef _DEBUG		//只有在Debug（调试）模式下
#ifndef DEBUG_NEW
#define DEBUG_NEW new(_NORMAL_BLOCK,__FILE__,__LINE__)	//重新定义new运算符
//当进行对象转储时，用 DEBUG_NEW 分配的每个对象均将显示被分配到的文件和行号，使您可以查明内存泄漏源
#define new DEBUG_NEW    
#endif
#endif

using namespace std;

# pragma warning(disable : 4996)
#define InitSize 10		//动态数组的初始大小
#define IncSize 5		//当动态数组存满数据后每次扩容所能多保存的数据元素数量

---

顺序表的数据成员(两种写法)

• 静态数组

  • 建立一个一维数组，来保存顺序表的元素

  • 建立一个变量存储顺序表当前的实际长度（不是数组的长度，数组长度是已知的）

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;

---

顺序表的基本操作

• 顺序表的类的定义和设计
  • 构造函数
  • 析构函数
  • 按指定位置i插入元素
  • 按指定位置i删除元素
  • 获取第i位置的元素
  • 按元素值查找在顺序表的第一次出现的位置
  • 遍历输出顺序表的元素
  • 获取顺序表的长度
  • 反转顺序表
  • 扩容操作

---

顺序表的编程实现

类（顺序表)定义

namespace _nmsp1
{	
	template <typename T>
	class SeqList
	{
	public:
		SeqList(int length = InitSize);	//构造函数
		~SeqList();						//析构函数
	public:
		bool List_Insert(int i, const T& e);	//在第i个位置插入新元素
		bool List_Delete(int i);				//删除第i个位置的元素
		bool Get_List_Elem(int i, const T& e);	//获取第i个位置的元素
		int Locate_Elem(const T& e);		//按元素值查找在顺序表的第一次出现的位置
		void Display_List();					//输出顺序表中的元素
		int Get_List_Length();					//获取顺序表的长度
		void Reverse_List();					//反转顺序表
		void Increase_Size();					//扩容操作

	private:
		T* m_data;		//（指向存放顺序表的当中的元素
		int m_length;	//顺序表中当前实际长度（当前有几个元素）
		int m_maxsize;	//动态数组的最大容量
	};

---

构造函数（初始化）

• 首先会开辟一块内存来存储顺序表
• 为当前顺序表长度赋初值为0

//通过构造函数对顺序表进行初始化template <typename T>
	SeqList<T>::SeqList(int length)
	{
		m_data = new T[length]; //为一维数组动态分配内存
		m_length = 0;           //顺序表当前实际长度为0，表示还未向其中存入任何数据元素
		m_maxsize = length;     //顺序表最多可以存储m_maxsize个数据元素
	}

---

析构函数

• 必须对用户自己分配好的内存空间进行释放
• delete m_data 和delete []m_data的区别
  • delete m_data 释放了m_data指针指向的全部内存空间 但是只调用了m_data[0]对象的析构函数 剩下的从[1]到末尾这个用户自行分配的对应内存空间将不能释放， 从而造成内存泄漏。
  • delete []m_data /调用使用类对象的析构函数释放用户自己分配内存空间并且 释放了m_data指针指向的全部内存空间

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

---

按指定位置i插入元素

1. 先判断顺序表是否存满数据；是，进行扩容操作

2. 判断i这个位置是否合法

3. 以上都满足进行插入操作

   • 从最后一个元素遍历到下标为i的位置（也就是第i+1个元素）结束进行元素位置向后移位

   • 对第i个位置进行赋值

   • 每一次进行插入 操作，顺序表长+1

//在第i个位置（位置编号从1开始）插入指定元素e，时间复杂度：O(n)
template <typename T>
bool SeqList<T>::ListInsert(int i, const T& e)
{
	//如果顺序表已经存满了数据，则不允许再插入新数据了
	if (m_length >= m_maxsize)
	{
		//cout << "顺序表已满，不能再进行插入操作了!" << endl;			
		//return false;
		IncreaseSize();
	}

	//判断插入位置i是否合法，i的合法值应该是1到m_length+1之间
	if(i < 1 || i > (m_length+1))
	{
		cout << "元素" << e <<"插入的位置" << i << "不合法，合法的位置是1到" << 			  m_length+1 << "之间!" << 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
	cout << "成功在位置为" << i << "处插入元素" << m_data[i - 1] << "!" << 			endl;
	m_length++;        //实际表长+1
	return true;
}

---

按指定位置i删除元素

• 判断表是否为空
• 判断位置i是否合法
• 以上都满足，遍历第i+1个位置到顺序表末尾向前移位
• 每次删除操作顺序表长都必须-1

//删除第i个位置的元素
template < typename T>
bool SeqList<T>::ListDelete(int i)
{
	if (m_length < 1)
	{
		cout << "当前顺序表为空，不能删除任何数据!" << endl;
		return false;
	}
	if (i < 1 || i > m_length)
	{ 
		cout << "删除的位置" << i << "不合法，合法的位置是1到" << m_length << "之			间!" << endl;
		return false;
	}		
	cout << "成功删除位置为" << i << "的元素，该元素的值为" << m_data[i - 1] << 			"!" << endl;
	//从数组中第i+1个位置开始向后遍历所有元素，分别将这些位置中原有的元素向前移动一个位置
	for (int j = i ; j < m_length; ++j)
	{
		m_data[j-1] = m_data[j];
	}
	m_length--;       //实际表长-1
	return true;
}

---

获取第i个位置的元素值

• 判断表是否为空
• 判断位置i是否合法
• 以上都满足，成功获取值

//获得第i个位置的元素值
template<class T>
bool SeqList<T>::GetElem(int i, T& e) //参数e是引用类型参数，确保将该值带回调用者
{
	if (m_length < 1)
	{
		cout << "当前顺序表为空，不能获取任何数据!" << endl;
		return false;
	}

	if (i < 1 || i > m_length)
	{
		cout << "获取元素的位置" << i << "不合法，合法的位置是1到" << m_length <<   		"之间!" << endl;
		return false;
	}
	e = m_data[i-1];
	cout << "成功获取位置为" << i << "的元素，该元素的值为" << m_data[i - 1] << 			"!" << endl;
	return true;
}

按元素值查找在顺序表的第一次出现的位置

• 是按照元素值进行查找，则对其全部进行遍历一一对比

//按元素值查找其在顺序表中第一次出现的位置
	template<class T>
	int SeqList<T>::LocateElem(const T& e)
	{
		for (int i = 0; i < m_length; ++i)
		{
			if (m_data[i] == e)
			{ 
				cout << "值为" << e << "的元素在顺序表中第一次出现的位置为" << i+1 << 					"!" << endl;
				return i + 1;  //返回的位置应该用数组下标值+1
			}
		}
		cout << "值为" << e << "的元素在顺序表中没有找到!" << endl;
		return -1;  //返回-1表示查找失败
	}

---

遍历输出顺序表的元素

//输出顺序表中的所有元素，时间复杂度为O(n)
	template<class T>
	void SeqList<T>::DispList()
	{
		for (int i = 0; i < m_length; ++i)
		{
			cout << m_data[i] << " ";  //每个数据之间以空格分隔
		}
		cout << endl; //换行
	}

---

获取顺序表的长度

//获取顺序表的长度，时间复杂度为O(1)
	template<class T>
	int SeqList<T>::ListLength()
	{
		return m_length;
	}

---

反转顺序表

• 判断顺序是否为空
• 第一个和最后一个交换赋值，依次类推

//翻转顺序表，时间复杂度为O(n)
	template<class 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;
		}
	}

---

扩容操作

• 新建一个指针指向原来顺序表的数据的内存块
• 新开辟一个内存的同时要扩容一下大小
• 然后在遍历原来内存将其数据复制到已经新的内存（新扩容的内存）
• 释放原来的内存块

//当顺序表存满数据后可以调用此函数为顺序表扩容，时间复杂度为O(n)
	template<class 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 = m_maxsize + IncSize;     //顺序表最大长度增加IncSize
		delete[] p;                          //释放原来的内存空间
	}

主函数操作

int main()
{
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
	//程序退出时检测内存泄漏并显示到“输出”窗口

	_nmsp1::SeqList<int> seqobj(10);	
	seqobj.ListInsert(1, 15);
	seqobj.ListInsert(2, 10);
	seqobj.ListInsert(30, 8);
	
	seqobj.ListDelete(1);

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

	int findvalue = 10; //在顺序表中要找的元素值
	seqobj.LocateElem(findvalue);
	
	//-------------------------------
	seqobj.ListInsert(2, 100);
	seqobj.DispList();
	cout << seqobj.ListLength() << endl;
	seqobj.ReverseList();
	seqobj.DispList();

	//-----------------------
	cout << "-----------" << endl;
	for (int i = 3; i < 30; ++i)
	{
		seqobj.ListInsert(i, i*2);
	}
	seqobj.DispList();

	return 0;
}

---

---

总结

• 顺序表的特点

  • 通过下标访问数据元素的时间复杂度为O（1）
  • 插入和删除操作会移动大量元素时间复杂度为O（n）
  • 需要大片的连续的内存空间来存储数据
  • 扩容操作的具体数值的大小不好确定（大了导致内存浪费，小了会进行频繁的操作）

• 应用：

  • vector 大致思想原理是类似于顺序表

---

全部代码

#include <iostream>


#ifdef _DEBUG   //只在Debug（调试）模式下
#ifndef DEBUG_NEW
#define DEBUG_NEW new(_NORMAL_BLOCK,__FILE__,__LINE__) //重新定义new运算符
#define new DEBUG_NEW
#endif
#endif

//#include <boost/type_index.hpp>
using namespace std;
//#pragma warning(disable : 4996) 

namespace _nmsp1
{		

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

	template <typename T> //T代表数组中元素的类型
	class SeqList
	{
	public:
		SeqList(int length=InitSize); //构造函数，参数可以有默认值
		~SeqList();                   //析构函数

	public:
		bool ListInsert(int i, const T& e);  //在第i个位置插入指定元素e
		bool ListDelete(int i);              //删除第i个位置的元素
		bool GetElem(int i, T& e);           //获得第i个位置的元素值
		int  LocateElem(const T &e);         //按元素值查找其在顺序表中第一次出现的位置

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

		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;     //顺序表最多可以存储m_maxsize个数据元素
	}

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

	//在第i个位置（位置编号从1开始）插入指定元素e，时间复杂度：O(n)
	template <typename T>
	bool SeqList<T>::ListInsert(int i, const T& e)
	{
		
		if (m_length >= m_maxsize)
		{
			//cout << "顺序表已满，不能再进行插入操作了!" << endl;			
			//return false;
			IncreaseSize();
		}

		
		if(i < 1 || i > (m_length+1))
		{
			cout << "元素" << e <<"插入的位置" << i << "不合法，合法的位置是1到" << m_length+1 << "之间!" << endl;
			return false;
		}

		
		for (int j = m_length; j >= i; --j) 
		{
			m_data[j] = m_data[j-1];
		}
		m_data[i-1] = e;   
		cout << "成功在位置为" << i << "处插入元素" << m_data[i - 1] << "!" << endl;
		m_length++;        //实际表长+1
		return true;
	}

	//删除第i个位置的元素
	template < typename T>
	bool SeqList<T>::ListDelete(int i)
	{
		if (m_length < 1)
		{
			cout << "当前顺序表为空，不能删除任何数据!" << endl;
			return false;
		}
		if (i < 1 || i > m_length)
		{ 
			cout << "删除的位置" << i << "不合法，合法的位置是1到" << m_length << "之		间!" << endl;
			return false;
		}		
		cout << "成功删除位置为" << i << "的元素，该元素的值为" << m_data[i - 1] << 			"!" << endl;
		
		for (int j = i ; j < m_length; ++j)
		{
			m_data[j-1] = m_data[j];
		}
		m_length--;       //实际表长-1
		return true;
	}


	//获得第i个位置的元素值
	template<class T>
	bool SeqList<T>::GetElem(int i, T& e) //参数e是引用类型参数，确保将该值带回调用者
	{
		if (m_length < 1)
		{
			cout << "当前顺序表为空，不能获取任何数据!" << endl;
			return false;
		}

		if (i < 1 || i > m_length)
		{
			cout << "获取元素的位置" << i << "不合法，合法的位置是1到" << m_length << "之间!" << endl;
			return false;
		}
		e = m_data[i-1];
		cout << "成功获取位置为" << i << "的元素，该元素的值为" << m_data[i - 1] << "!" << endl;
		return true;
	}

	//按元素值查找其在顺序表中第一次出现的位置
	template<class T>
	int SeqList<T>::LocateElem(const T& e)
	{
		for (int i = 0; i < m_length; ++i)
		{
			if (m_data[i] == e)
			{ 
				cout << "值为" << e << "的元素在顺序表中第一次出现的位置为" << i+1 << "!" << endl;
				return i + 1;  //返回的位置应该用数组下标值+1
			}
		}
		cout << "值为" << e << "的元素在顺序表中没有找到!" << endl;
		return -1;  //返回-1表示查找失败
	}

	//输出顺序表中的所有元素，时间复杂度为O(n)
	template<class T>
	void SeqList<T>::DispList()
	{
		for (int i = 0; i < m_length; ++i)
		{
			cout << m_data[i] << " ";  //每个数据之间以空格分隔
		}
		cout << endl; //换行
	}

	//获取顺序表的长度，时间复杂度为O(1)
	template<class T>
	int SeqList<T>::ListLength()
	{
		return m_length;
	}
	
	//翻转顺序表，时间复杂度为O(n)
	template<class 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;
		}
	}

	//当顺序表存满数据后可以调用此函数为顺序表扩容，时间复杂度为O(n)
	template<class 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 = m_maxsize + IncSize;     //顺序表最大长度增加IncSize
		delete[] p;                          //释放原来的内存空间
	}
}

int main()
{
 //程序退出时检测内存泄漏并显示到“输出”窗口
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);

	_nmsp1::SeqList<int> seqobj(10);	
	seqobj.ListInsert(1, 15);
	seqobj.ListInsert(2, 10);
	seqobj.ListInsert(30, 8);
	
	seqobj.ListDelete(1);

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

	int findvalue = 10; //在顺序表中要找的元素值
	seqobj.LocateElem(findvalue);
	
	//-------------------------------
	seqobj.ListInsert(2, 100);
	seqobj.DispList();
	cout << seqobj.ListLength() << endl;
	seqobj.ReverseList();
	seqobj.DispList();

	//-----------------------
	cout << "-----------" << endl;
	for (int i = 3; i < 30; ++i)
	{
		seqobj.ListInsert(i, i*2);
	}
	seqobj.DispList();

	return 0;
}