线性表的定义
线性表的概念
线性表是处理线性结构的数据结构。
线性表包含N个具有相同特征的结点A0, A1, …, AN-1构成的集合。在这个集合中，除了A0 和AN-1外，每个元素都有唯一的前趋和后继。对于每个Ai，它的前驱是Ai-1，它的后继是Ai+1。A0只有后继没有前驱，AN-1只有前驱没有后继。
N称为表的大小，A0称为首结点，AN-1称为尾结点，元素个数为零的表称为空表，元素Ai在表中的位置为i。
线性表的基本操作
create():创建一个空的线性表；
clear():清空线性表中的所有数据元素；
length():返回线性表的长度；
visit(i):返回线性表中第i个数据元素的值；
insert(i, x):在第i个位置插入一个元素x，即在i-1和i个元素之间插入；
remove(i):删除第i个位置的元素；
search(i):在线性表中搜索x是否出现，并返回x的位置；
traverse():按序访问线性表的每一数据元素；
线性表的抽象类(ADT)
// list.h
#ifndef list_
#define list_
#include <iostream>
using namespace std;
template <class elemType>
class list
{
public:
virtual void clear() = 0;
virtual int length() const = 0;
virtual void insert(int i, const elemType &x) = 0;
virtual void remove(int i) = 0;
virtual int search(const elemType &x) const = 0 ;
virtual elemType visit(int i) const = 0;
virtual void traverse() const = 0;
virtual ~list() {};
};
#endif
线性表的实现
顺序实现
存储结构
线性表中结点存放在存储器上一块连续的空间中，借助存储空间的连续性，结点可以按照其逻辑顺序依次存放，因此结点存放的物理位置和逻辑位置是一致的。线性表的顺序实现通常称为顺序表。
在C++中，一块连续的存储空间可以用一个数组实现。由于线性表中的元素个数是动态的，因此采用了动态数组。线性表必须支持插入或删除，在申请空间时要留有余地。一般要比实际元素个数多一点。
保存一个动态数组，需要两个变量：指向线性表元素类型的指针，数组规模（容量），数组中的元素个数（表长）。
顺序表类的定义
// seqList.h
#ifndef seqList_
#define seqList_
#include<iostream>
#include"list.h"
class OutOfBound{};
class IllegalSize{};
template <class elemType>
class seqList: public list<elemType>
{
private:
elemType *data;
int currentLength;
int maxSize;
void doubleSpace();
public:
seqList(int initSize = 10);
~seqList() {delete [] data;}
void clear() {currentLength = 0;}
int length() const {return currentLength;}
void insert(int i, const elemType &x);
void remove(int i);
int search(const elemType &x) const;
elemType visit(int i) const {return data[i];}
void traverse() const;
};
// 构造函数
template <class elemType>
seqList<elemType>::seqList(int initSize)
{
if (initSize <= 0) throw IllegalSize();
data = new elemType[initSize];
maxSize = initSize;
currentLength = 0;
}
template <class elemType>
int seqList<elemType>::search(const elemType &x) const
{
int i;
for (i = 0; i < currentLength && data[i] != x; ++i);
if (i == currentLength) return -1; else return i;
}
template <class elemType>
void seqList<elemType>::traverse() const
{
for (int i = 0; i < currentLength; ++i)
cout << data[i] << ' ';
cout << endl;
}
template <class elemType>
void seqList<elemType>::doubleSpace()
{
elemType *tmp = data;
maxSize *= 2;
data = new elemType[maxSize];
for (int i = 0; i < currentLength; ++i)
data[i] = tmp[i];
delete [] tmp;
}
template <class elemType>
void seqList<elemType>::insert(int i, const elemType &x)
{
if (i < 0 || i > currentLength) throw OutOfBound();
if (currentLength == maxSize) doubleSpace();
for (int j = currentLength; j > i; --j) data[j] = data[j-1];
data[i] = x;
++currentLength;
}
template <class elemType>
void seqList<elemType>::remove(int i)
{
if (i < 0 || i > currentLength-1)
throw OutOfBound();
for (int j = i; j < currentLength - 1; j++)
data[j] = data[j+1] ;
--currentLength;
}
#endif
由代码实现可以分析各个操作的时间复杂度：
length, visit和clear的实现与表中的元素个数无关，时间复杂度是O(1)。
traverse()操作遍历整个表中的所有元素，因此时间复杂度为O(n)。
create操作需要申请一块动态数组的空间，并设表为空。因此也是O(1)的时间复杂度。
插入操作，需要移动结点。当i等于n时，移动次数为0。当i等于0时，移动次数为n。
最好情况下的时间复杂度为O(1)；
最坏情况下的时间复杂度为O(n)；
平均的时间复杂度：如果在每个位置上的插入都是等概率的，则插入算法的平均时间复杂度为n/2；
因此时间复杂度为O(n)。
顺序实现总结
由于要保持逻辑次序和物理次序的一致性，顺序表在插入删除时需要移动大量的数据，性能不太理想。
由于逻辑次序和物理次序的一致性使得定位访问的性能很好。
顺序表比较适合静态的、经常做定位访问的线性表。
链接实现
存储结构
将每个结点放在一个独立的存储单元中，结点间的逻辑关系依靠存储单元中附加的指针来给出。 结点的存储单元在物理位置上可以相邻，也可以不相邻。
单链表
每个结点附加了一个指针字段，如next，该指针指向它的直接后继结点，最后一个结点的next字段为空。
为了消除特殊情况，通常在表头额外增加一个相同类型的特殊结点，称之为头结点。它们不是线性表中的组成部分。
头结点的出现，使得在表头位置上进行插入和删除和在其它结点位置上是完全一致的，从而使得插入和删除算法得到简化。
结点及其组成
链表中的结点包含两部分：数据字段和后继指针字段。 数据字段可以是任何类型的数据；指针字段用于存放其他相关结点的地址值。由于结点类型是链表专用的，因此可设为内嵌类。
由于链表的操作是通过对结点的操作实现的，于是把结点类定义成struct，以方便链表类访问。
双链表
每个结点附加了两个指针字段，prior字段给出直接前驱结点的地址，next给出直接后继结点的地址。
为了消除在表头、表尾插入删除的特殊情况，通常双链表设一头结点，设一尾节点。头结点中prior字段为空，它的next字段给出线性表中的首结点的地址；尾结点中next字段为空，它的prior字段给出线性表中最后一个节点的地址。
