线性表
零个或多个数据元素的有限序列。
注：1.元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其它每个元素都有且只有一个直接前驱和直接后继。
2.元素数量是有限的。
线性表的数学描述：
若将线性表记为(a1,a2,a3……,an)，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2,3,4……,n-1时，ai有且只有一个直接后继，当i=2,3,4……n时，ai有且仅有一个直接前驱。
线性表元素的个数n（n>=0）定义为线性表的长度，当n=0时，称为空表，在非空表中，每个数据元素都有一个确定的位置，如ai是第i个数据元素，称i为数据元素ai在线性表中的位序（也叫索引或下标）。
线性表的两种存储结构
顺序存储结构
线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。可用一维数组来实现顺序存储的线性表。
顺序存储线性表的代码实现：
#ifndef LISTSTOREBYORDER_H_
#define LISTSTOREBYORDER_H_
#include
/*****************************************************************************************************************/
/* 线性表中数据元素之间的逻辑关系是：线性关系（数据元素之间是一对一的关系），除首元素和尾元素外，每个元素有且只有一个直接前驱和直接后继*/
/* 本例中顺序表采用顺序存储结构来实现（顺序存储，实际上就是一维数组） */
/* 类的头文件相当于线性表的ADT */
/* 分析支持的操作 */
/****************************************************************************************************************/
template
class ListStoreByOrder
{
const int FLAG_EMPTY = 0;
public:
const int NULL_FlAG = -1;
explicit ListStoreByOrder(unsigned int iArraySize); //防止隐式类型转换
ListStoreByOrder(const ListStoreByOrder &array) = delete; //删除拷贝构造函数和赋值函数，防止因深浅拷贝导致的问题
ListStoreByOrder & operator = (const ListStoreByOrder & array) = delete;
//支持的操作
/*************************************************************************/
/* 增加元素、删除元素、修改元素、获取某位置的元素、查找某元素、求当前长度、判断是否为空*/
/* 清空线性表 */
/*************************************************************************/
//判断线性表是否为空
bool empty()
{
if (FLAG_EMPTY == m_iCurrLen)
{
return true;
}
return false;
}
//清空线性表，删除所有数据元素
void clear()
{
memset(pList, 0x00, m_iMaxSize);
m_iCurrLen = FLAG_EMPTY;
}
//获取指定下标的元素
T & at(int iPos);
//修改指定位置的值
void setValue(int iPos, const T & value);
//在尾部插入元素
void push_back(const T & value);
//在指定位置插入元素
void insert(int iPos, const T & value);
//删除表尾元素，并返回其值
T pop();
//删除指定位置的值，并返回其值
T erase(int iPos);
//获取数据长度
unsigned int size()
{
return m_iCurrLen;
}
//获取最大长度
unsigned int maxSize()
{
return m_iMaxSize;
}
//查找指定元素
int find(const T value);
~ListStoreByOrder();
private:
T *pList{ nullptr }; //用于存储线性表的地址空间的首地址
int m_iCurrLen{ 0 }; //数据长度（数组中存储的数据的数据量）
unsigned int m_iMaxSize{ 0 }; //数组的最大长度，任何时候，数据长度应该小于等于数组的最大长度
unsigned int m_iCurrPosition{ 0 }; //数据元素的当前位置
};
#endif
template
inline ListStoreByOrder::ListStoreByOrder(unsigned int iArraySize):m_iMaxSize(iArraySize)
{
pList = new T[m_iMaxSize]; //构造最大长度为m_iMaxSize的线性表
}
template
inline T & ListStoreByOrder::at(int iPos)
{
if (FLAG_EMPTY == m_iCurrLen)
{
throw runtime_error("List is empty!");
}
if (iPos< 0 || iPos >= m_iCurrLen )
{
throw runtime_error("Array bound!");
}
return pList[iPos];
// TODO: 在此处插入 return 语句
}
template
inline void ListStoreByOrder::setValue(int iPos, const T & value)
{
if (FLAG_EMPTY == m_iCurrLen)
{
throw runtime_error("List is empty!");
}
if (iPos < 0 || iPos >= m_iCurrLen)
{
throw runtime_error("Array bound!");
}
pList[iPos] = value;
}
template
inline void ListStoreByOrder::push_back(const T & value)
{
//数据长度等于最大长度，说明已经没有空余做插入操作了
if (m_iCurrLen == m_iMaxSize)
{
throw runtime_error("No space room!");
}
pList[m_iCurrLen] = value;
++m_iCurrLen;
}
template
/************************************************************************/
/* 假设在任意位置插入的概率是相同的，这个概率设为1/n */
/* 尾元素需要移动1个位置，移动次数1/n，尾元素的前驱移动次数为2/n,依次类推，可得移动 */
/* 总次数为1/n+2/n+3/n + n/n 最终移动总次数为 (n-1)/2 */
/* 所以平均时间复杂度是O(n) */
/************************************************************************/
void ListStoreByOrder::insert(int iPos, const T & value)
{
//数据长度等于线性表长度，说明已经没有空闲内存插入了
if (m_iCurrLen == m_iMaxSize)
{
throw runtime_error("No space room!");
}
//先检查这个插入位置是否是表尾部，因为索引是从0开始的
if (iPos == m_iCurrLen-1)
{
push_back(value);
return;
}
else if (0 > iPos || iPos >=m_iCurrLen) //非法插入位置
{
throw runtime_error("Invaild index");
}
//从最后一个元素开始进行移位,可避免下标越界，因为在上面的if判断中已经排除了传入位置小于0的情况,把iPos指定的位置空出来
for ( int iLoopVariable = m_iCurrLen-1; iLoopVariable >=iPos; --iLoopVariable)
{
pList[iLoopVariable + 1] = pList[iLoopVariable];
}
//移动结束，将元素value插入
pList[iPos] = value;
++m_iCurrLen;
}
template
inline T ListStoreByOrder::pop()
{
if (true == empty())
{
throw runtime_error("List is Empty!");
}
T temp = pList[m_iCurrLen - 1];
--m_iCurrLen;
return temp;
}
template
T ListStoreByOrder::erase(int iPos)
{
//如果和数据长度-1相等，那么删除表尾部元素
T tempValue;
if (iPos == m_iCurrLen -1)
{
tempValue = pop();
return tempValue;
}
else if (0> iPos || iPos >= m_iCurrLen)
{
throw runtime_error("Invaild Index!");
}
tempValue = pList[iPos];
for (int iLoopVariable = iPos;iLoopVariable < m_iCurrLen;++iLoopVariable)
{
pList[iLoopVariable] = pList[iLoopVariable+1];
}
--m_iCurrLen;
return tempValue;
}
template
//穷举法查找时间复杂度是O(n)
int ListStoreByOrder::find(const T value)
{
for (int iLoopVariable = m_iCurrLen-1; iLoopVariable >=0;--iLoopVariable)
{
if (value == pList[iLoopVariable])
{
return iLoopVariable;
}
}
return NULL_FlAG;
}
template
inline ListStoreByOrder::~ListStoreByOrder()
{
if (nullptr != pList) //销毁线性表
{
delete[] pList;
pList = nullptr;
}
}
线性表顺序存储结构的优缺点：
优点：
1. 无须为表示元素之间的逻辑关系而增加额外的存储空间
1. 可以快速的存取表中任意位置的元素
缺点：
1. 在任意位置插入和删除操作需要移动大量元素（时间复杂度为O(n)，原因是逻辑上相邻的两个元素在物理位置上也是相邻的，没有额外的空间供其插入）
1. 当线性表长度变化较大时，难以确定存储空间的容量
1. 造成存储空间碎片（new-delete）
注：对每个线性表位置的存入或者取出数据，对于计算机来说时间都是相等的，也就是一个常数，其时间复杂度为O(1)，我们把具有这一特点的存储结构称为随机存储结构。
计算顺序结构线性表的任意元素地址的公式：
LOC(ai) = LOC(a1) + (i-1)*c
其中c为数据元素的大小。
线性表的链式存储结构
线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的也可以是不连续的。这就意味着，这些数据元素可以在内存未被占用的任意位置。在这种方式下，节点除了要保存数据元素外，还有保存它的后继元素的存储地址。
为了表示每个数据元素ai与其直后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储数据元素信息外,还需要存储一个指示其直接后继数据元素的信息（即直接后继元素的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接指针后继位置的域称为指针域。指针域中存储的是信息称为指针或链。这两部分信息组成数据元素ai的存储映像，称为结点（Node）。
n个节点（ai的存储映像）链接成一个链表，即为线性表（a1,a2,a3……,an）的链式存储结构，因此链表的每个结点中只包含一个指针域，所以叫做单链表。
链表中的第一个节点的存储位置叫做头指针，整个结点的存取操作都需要从头指针进行。线性链表的最后一结点指针为NULL。
有时为了操作方便，会在单链表的第一个结点前附设一个结点，称为头结点，头结点的数据域是无意义的，当然你，也可以用来存储链表长度等附加信息。
头指针与头结点的异同：
头指针：
1. 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
1. 当线性链表为空时头指针（指向自己或者为空，这是在不带头结点的情况下）。头指针是链表的必要元素。一般用头指针来命名单链表。
头结点：
1. 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义
1. 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作就与其它结点的操作统一了
1. 头结点不一定是链表的必要元素
1. 对有头结点的线性表，若线性表为空，则头结点指针域为NULL。
首元结点：第一个有数据元素的结点，即链表中第一个实际的结点。
对不带头结点的单链表，在进行插入和删除操作时，要考虑插入和删除的是不是第一个结点，并采取不同的措施。
对单链表的结点，我们可以如下描述：
#ifndef LISTSTOREBYPTR_H_
#define LISTSTOREBYPTR_H_
//单单链表的结点
template
class Node
{
public:
T m_data; //数据域，用来保存单链中结点的元素
Node *m_next{ nullptr }; //指针域，指向单链中当前元素的后继数据元素
Node(const T info, Node *nextValue = nullptr) : m_data(info), m_next(nextValue) {};
Node() :m_next(nullptr) {};
Node(const Node & value) = delete;
Node & operator = (const Node &value) = delete;
};
#endif
头指针可以做如下描述：
Node first;
Node *head = &first; //这个head就是头指针
头指针的意义是：在访问链表是总要知道链表存储在什么位置，知道首位置，根据链表的特点我们就可以知道它接下来的元素在什么地方了。
假设结点ai
ai->m_data,就是当前结点的数据域
ai->m_next->data，就是当前结点后继结点的数据域
单链表的类定义如下，具体的算法讲解请参考注释：
//单链表的类定义
//在表达链表中的当前元素时往往是通过它的前驱元素来表示的
//单链中对结点进行操作，必须要先找到这个结点，这必须要从第一个结点开始，这个查找的时间复杂度是O(n)
//显然在中间位置进行插入或删除元素的时间复杂度为O(n)，但是它的优势在于可以在中间某位置插入n个节点，它的时间复杂度依然是O(n)，这就是单链表相比顺序表的优势
//显然，对于插入和删除数据越频繁的操作，单链表的优势就越明显
template
class LinkList
{
private:
unsigned int m_iLinkSize{ 0 };
Node *m_pHead{ nullptr }; //单链表的头指针
Node *m_pTail{ nullptr }; //单链表的尾指针
Node *setPos(const int iPosition); //第p个元素的指针
public:
LinkList(); //构造函数
LinkList(const LinkList &value) = delete;
LinkList & operator = (const LinkList &value) = delete;
~LinkList(); //析构函数
bool empty(); //判断链表是否为空
void clear(); //将链表清空，使其成为空表
int size(); //返回此链表的实际长度
bool push_back(const T value); //表尾增加元素，表长度增加1
bool insert(const int iPosition, const T value);//位置iPosition上添加一个元素
bool deleteValue(const int iPosition); //删除位置iPosition上的元素，表长度减1
bool getValue(const int iPosition, T &value); //获取位置iPosition上的元素
bool getPos(int &iPosition, const T value); //获取第一个元素值为value的结点索引
};
#endif
//查找单链表中第i个节点，返回值是
template
inline Node* LinkList::setPos(const int iPosition)
{
int count = 0;
if (-1== iPosition || nullptr == m_pHead->m_next)
{
return m_pHead; //如果i为-1则定位到头结点，输入i= -1时，定位到的是虚的头结点，此时对应于插入到数据0结点之前
}
Node *p = m_pHead->m_next;
while (p != nullptr && count m_next;
++count;
}
//通过上面的循环，我们找到的实际上是第i个元素的前驱数据元素，它的指针域中存储的就是第i个元素的存储位置，所以p最后的值就是第i个元素的存储位置
//类似于数组中定位A[i]下标的取值为0 -- n-1
return p;
}
template
LinkList::LinkList()
{
m_pHead = new Node; //令头指针指向头结点
m_pHead->m_next = nullptr; //使头结点的指针域为空
m_pTail = m_pHead;
m_pTail->m_next = nullptr;
}
//插入值为value的结点作为第iPosition个节点
//实际上就是使i位置的前驱指针域指向带插入节点，而带插入节点的指针域指针指向原来的第iPosition节点
template
bool LinkList::insert(const int iPosition, const T value)
{
Node *p(nullptr);
Node *q(nullptr);
//首先寻找目标位置的前驱节点的存储位置，所以给第setPos的参数是i-1
if (nullptr == (p =setPos(iPosition -1)))
{
std::cout << "Invaild position!" << std::endl; //加了虚头结点后，单链表中每个数据元素都有一个直接前驱，所以函数返回为nullptr，说明这个位置是非法的。
return false;
}
//如果插入位置合法，创建一个新的结点
//令新结点q的值为value,指针域指向其前驱所指位置
q = new Node(value, p->m_next);
//更改iPosition前驱的指针域，令其指向新添加的结点
p->m_next = q;
//如果iPosition位置的前驱是尾结点，那么新结点称为新的尾结点
if (m_pTail == p)
{
m_pTail = q;
}
++m_iLinkSize;
return true;
}
//单链中删除结点x
//1.用p指向结点x的前驱节点
//2.删除结点x
//3.释放结点x的占据内存
template
bool LinkList::deleteValue(const int iPosition)
{
Node *p = nullptr;
Node *q = nullptr;
//找到iPosition位置元素的前驱
//待删结点不存在，即给定i大于链表中元素的个数，if中的 p = setPos(i-1)是一定会执行的，|| p == m_pTail，说明给定位置的前驱是尾结点，这样的结点是非法的
//这里有返回为空的情况，因为在setPos中返回的是前驱节点指针域，当所指定的位置（伪）前驱是尾结点，此时返回的必然是空指针，另外，要删除元素必然是在链表中的。
if (nullptr == (p = setPos(iPosition -1)) || p == m_pTail)
{
cout << "Invaild Position!" << endl;
return false;
}
q = p->m_next; //q是真正的删除结点，我们先用q来保存下q前驱p的指针域
//如果要删除的结点是尾结点
if (m_pTail == q)
{
m_pTail = p;
p->m_next = nullptr;
}
else
p->m_next = q->m_next; //修改结点p的指针域的值，相当于 p->m_next = p->m_next->m_next;
if (q != nullptr)
{
delete q;
q = nullptr;
}
--m_iLinkSize;
return true;
}
template
bool LinkList::getValue(const int iPosition, T & value)
{
auto ret = setPos(iPosition);
//如果所返回的目标节点的指针等于头结点的指针或者返回为空，则代表索引错误
if (m_pHead == ret || nullptr == ret)
{
std::cout << "Invaild Index!" << std::endl;
return false;
}
value = ret->m_data;
return true;
}
template
bool LinkList::getPos(int & iPosition, const T value)
{
if (nullptr == m_pHead->m_next) //头结点的指针域为空，说明链表是空的
{
std::cout << "Invaild index!" << std::endl;
return false;
}
int iCount = 0;
Node *p = m_pHead->m_next; //从头结点处开始查找
while (nullptr != p)
{
if (value == p->m_data)
{
iPosition = iCount;
break;
}
++iCount;
p = p->m_next;
}
std::cout << "查找了：" << iCount << std::endl;
return true;
}
template
LinkList::~LinkList()
{
clear();
if (nullptr != m_pHead)
{
delete m_pHead;
m_pHead = nullptr;
}
}
template
inline bool LinkList::empty()
{
if (nullptr == m_pHead->m_next)
{
return true;
}
return false;
}
template
void LinkList::clear()
{
Node *p{ nullptr };
Node *q{ nullptr };
//如果是空表，直接返回
if (nullptr == m_pHead->m_next)
{
return;
}
//绝大部分的操作都要从头结点开始
p = m_pHead->m_next; //令p指向首元结点
while (p != nullptr) //没到表尾
{
q = p->m_next; //保存p下一节点的地址
if (nullptr != p)
{
delete p;
p = nullptr;
}
p = q;
--m_iLinkSize;
}
m_pTail = m_pHead;
m_pHead->m_next = nullptr; //清空链表，但是保留头结点，此时对象还没析构，原链表还能继续使用
if (nullptr == m_pHead)
{
std::cout << "头结点也没了！" << std::endl;
}
std::cout << "clear后，链表的大小是：" << m_iLinkSize << endl;
}
template
inline int LinkList::size()
{
return m_iLinkSize;
}
template
inline bool LinkList::push_back(const T value)
{
Node *newTail = new Node(value, nullptr);
m_pTail->m_next = newTail;
m_pTail = newTail;
++m_iLinkSize;
return true;
}
注：像上面这样，有一个结点分配一次内存的策略实际上并不好，因为这样做非常容易造成内存碎片。
转载请注明出处 线性表-C++实现
