数据结构cpp实现——线性表
一、线性表定义
标准定义：线性表的数据集合为{a1,a2,…,an}，假设每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
个人理解：线性表的定义并没有规定存储结构，可以在空间上连续，也可以通过指针连串。
线性表顺序表示
顺序表基本概念：用一组地址连续的存储单元依次存储线性表的数据元素，这种存储结构的线性表称为顺序表。 本质上仍然是数组的存储形式，但是存储数据的类型可以扩展为多种形式。
顺序表的类模版实现
#include <cstdlib>
#include <iostream>
#include "assert.h"
template<class T>
class SeqList {
private:
int length;//顺序表当前所含有的元素个数
int maxLength;//顺序表最大容量，在构造函数中由用户给出的数据生成
T *elems= nullptr;//元素存储空间首地址，默认为nullptr，防止出错
public:
SeqList(){};
SeqList(T *array, int SizeOfArray, int size=10);//构造函数，第一个参数为传入的初始化数组，第二个参数为传入数组大小，第三个参数为容器最大容量，设置默认参数为10
~SeqList();//析构函数
int GetLength() const;//返回顺序表当前长度
bool IsEmpty() const;//顺序表为空返回true，非空返回false
void clear(); //清空顺序表
void traverse() const;// 遍历打印顺序表
int LocateElem(const T &e) const; //定位元素e在顺序表中的位置
bool GetElem(int i, T &e) const; //取第i个元素并赋值给e并返回true，若失败函数整体返回false
bool SetElem(int i, const T &e); //用传入的e替换第i个元素，替换成功返回true，替换失败返回false
bool DeleteElem(int i, T &e);//删除第i个元素，并把删除的元素赋值给e
bool InsertElem(const T &e);//在表尾插入元素
bool InsertElem(int i, const T &e);//在第i个位置插入元素
SeqList(const SeqList<T> &origin);//复制构造函数
SeqList<T> &operator = (const SeqList<T> &origin);//赋值语句重载
};
template<class T>
SeqList<T>::SeqList(T *array, int SizeOfArray, int size) {
if(size<SizeOfArray)
exit(1);//如果分配的最大内存空间小于初始化数组的大小，则退出程序
length=SizeOfArray;//当前顺序表长度为初始化数组大小
maxLength=size;//最大长度为size
elems=new T[size];//分配内存空间
assert(elems);//分配内存空间失败则报错并终止程序
for(int i=0;i<SizeOfArray;i++)
elems[i]=array[i];
}
template<class T>
SeqList<T>::~SeqList() {
delete [] elems;
}
template<class T>
int SeqList<T>::GetLength() const {
return length;
}
template<class T>
bool SeqList<T>::IsEmpty() const {
return length==0;
}
template<class T>
void SeqList<T>::clear() {
length=0;//这里我们只清除了length，并没有实际释放分配的内存
}
template<class T>
void SeqList<T>::traverse() const {
for(int i=0;i < length; i++)
std::cout<<elems[i]<<" "<<std::endl;
}
template<class T>
int SeqList<T>::LocateElem(const T &e) const {
int i=0;
while(i<length&&elems[i] !=e)
i++;
return i<length ? i+1:0;//i小于length，说明找到了对应元素，返回i+1，否则返回0
}
template<class T>
bool SeqList<T>::GetElem(int i, T &e) const {
if(i>length||i<1)
return false;//定位位置大于顺序表长度或给出非法值，返回false
else
{
e=elems[i-1];
return true;
}
}
template<class T>
bool SeqList<T>::SetElem(int i, const T &e) {
if(i>length||i<1)
return false;//位置错误，返回false
else
{
elems[i-1]=e;
return true;
}
}
template<class T>
bool SeqList<T>::DeleteElem(int i, T &e) {
if(i>length||i<1)
return false;//位置错误，返回false
else
{
e=elems[i-1];
for(int j=i;j<length;j++)
elems[j-1]=elems[j];//删除后，元素依次从后往前移动
length--;
return true;
}
}
template<class T>
bool SeqList<T>::InsertElem(const T &e) {
if(length==maxLength)
return false;//表尾插入元素，若超过最大存储空间，返回false
else
{
elems[length]=e;
length++;
return true;
}
}
template<class T>
bool SeqList<T>::InsertElem(int i, const T &e) {
if(length==maxLength)
return false;
else if(i<1||i>length+1)
return false;
else
{
for(int j=length;j>=i;j--)
elems[j]=elems[j-1];//元素从前往后移动，给第i个元素腾空间
elems[i-1]=e;
length++;
return true;
}
}
template<class T>
SeqList<T>::SeqList(const SeqList<T> &origin) {
if(this->elems!= nullptr)
delete [] elems;//如果元素指针被赋过值，则将其清空
elems=new T[origin.maxLength];
for(int i=0;i<origin.GetLength();i++)
elems[i]=origin.elems[i];//元素逐个赋值
this->length=origin.GetLength();//当前顺序表长度复制
this->maxLength=origin.maxLength;//当前最大长度复制
}
template<class T>
SeqList<T> &SeqList<T>::operator=(const SeqList<T> &origin) {
//=的重载其实和复制构造函数一样
if(this->elems!= nullptr)
delete [] elems;//如果元素指针被赋过值，则将其清空
this->elems=new T[origin.maxLength];
for(int i=0;i<origin.GetLength();i++)
this->elems[i]=origin.elems[i];//元素逐个赋值
this->length=origin.GetLength();//当前顺序表长度复制
this->maxLength=origin.maxLength;//当前最大长度复制
return *this;
}上面的代码因为泛化编程的原因，方法声明和实现都放在h文件里面，复制可以直接用。
顺序表是最简单的数据结构，其实就是一个特殊的数组，因为模版的原因可以存储更广泛的的类型数据。