零个或者有限个元素组成的序列，包括顺序表和链表。不同的应用问题，需要线性表有不同的操作。
（1）、顺序表（数组描述）：有一个（可变）数组来存储线性表里边的元素，有一些方法来操作这些元素。元素是连续存储的，只要知道首元素指针便可以获得其他元素的指针。
（2）、线性表的vector描述基于数组的，比起顺序表有更多功能。
封装顺序表需要三个属性：存储起点，线性表最大存储大小（数组大小），线性表当前存储大小
注意：线性表的长度是可变的，数组的长度一般在初始化后不变，也可以设置可变数组功能。
C++实现顺序表：
//头文件 //arrayList.h #include <iostream> #include <sstream> using namespace std; / template<class T> class arrayList { public: //arrayList(); arrayList(int initialcapacity = 10); arrayList(const arrayList<T>&); ~arrayList() { delete[] element; } // int size() const//获得线性表大小，元素个数 { return listSize; } bool empty() const//判断是否为空表 { return listSize == 0; } T& get(int theIndex) const//获得某个位置元素 { return element[theIndex]; } int indexOf(const T& theElement) const;//某个元素的位置 void erase(int theIndex);//删除某个位置元素 void insert(int theIndex, T& thelement);//在线性表某一个位置插入元素 void output(ostream& out) const;//输出线性表元素 void add(T&); void reverse();//将线性表逆序 int capacity() const//获得数组容量 { return arrayLength; } public://protected: void initialarrayList(int initialcapacity);//初始化 void checkIndex(int theIndex) const;//判断索引是否有效 T* element;//存储线性表元素的一维数组 int arrayLength;//一维数组容量 int listSize;//线性表元素个数 //vector<T>* veclist; }; //线性表中的函数 template<class T> arrayList<T>::arrayList(int initialcapacity) { initialarrayList(initialcapacity); } template<class T> void arrayList<T>::initialarrayList(int initialcapacity) { if (initialcapacity < 1) { ostringstream s; s << "intialapacity = " << initialcapacity << " must be >0"; //throw illegalParameterValue(s.str()); } listSize = 0; arrayLength = initialcapacity; element = new T[arrayLength]; } template<class T> arrayList<T>::arrayList(const arrayList<T>& theList) { arrayLength = theList.arrayLength; listSize = theList.listSize; element = new T[arrayLength]; copy(theList.element, theList.element+listSize, element); } template<class T> void arrayList<T>::checkIndex(int theIndex) const { if (theIndex < 0 || theIndex >= listSize) { ostringstream s; s << "index = " << theIndex << "size = "<<listSize; throw illegalParameterValue(s.str()); } } template<class T> void arrayList<T>::erase(int theIndex) { checkIndex(theIndex); copy(element + theIndex + 1, element + listSize, element + theIndex); element[--listSize].~T();//调用析构函数//删除一个元素之后数组大小不会变？ } template<class T> void arrayList<T>::insert(int theIndex, T& theElement) { checkIndex(theIndex); if (listSize == arrayLength) {//数组空间已经满 T* temp = new T[2 * arrayLength]; copy(element, element + arrayLength, temp); delete []element; element = temp; arrayLength *= 2; } copy_backward(element + theIndex, element + listSize, element + theIndex + 1); element[theIndex] = theElement; listSize++; } template<class T> int arrayList<T>::indexOf(const T& theElement) const { int theIndex = (int)(find(element, element + listSize, theElement) - element); if (theIndex == listSize) return -1; else return theIndex; } template<class T> void arrayList<T>::output(ostream& out) const { int i = 0; while (listSize != 0) { out << element[i]; ++i; listSize--; } } template<class T> void arrayList<T>::add(T& theElement) { } template<class T> void arrayList<T>::reverse() { T* temp = new T[arrayLength]; for (int i = arrayLength-1, j = 0; i >= 0; i--, j++) { temp[j] = element[i]; } delete element; element = temp; } / int main() { arrayList<int> a(20); for (int i = 0; i < 20; i++) { a.element[i] = i; } a.reverse(); for (int j = 0; j < 20; j++) cout << a.element[j] << endl; cout << endl; a.reverse(); cout<<a.get(2)<<endl; return 0; }顺序表优缺点：
优点：操作时间短，相邻元素有物理关系和逻辑关系，没有必要为这种逻辑关系占用存储空间。
缺点：插入删除要移动大量元素，容易造成存储空间碎片。
（2）、链表：链表中的元素不是顺序排列的。（这里只介绍单项链表）
顺序存储结构每个数据元素只需要存储一个位置就可以了，而链式存储结构中，除了要存储数据信息外，还要存储它的后继元素的存储地址。
重要概念：头指针、头结点、首节点，数据节点。
带头结点的链表模型：
空链表（带头结点）
C++链表描述：
//头文件 //chain.h #include <iostream> #include <sstream> using namespace std; template<class T> struct chainNode { // T element; chainNode<T>* next; // chainNode(){} chainNode(const T& element, chainNode<T>* next) { this->element = element; this->next = next; } }; / template<class T> class chain { public: chain(int initialcapacity = 10); chain(const chain<T>&); ~chain(); // bool empty() const { return listSize == 0; } int size() const { return listSize; } T& get(int theIndex) const; int indexOf(const T&) const; void insert(int, const T&); void erase(int); void output(ostream& out) const; protected: void checkIndex(int theIndex) const; chainNode<T>* firstNode; int listSize; }; /// template<class T> chain<T>::chain(int initialCapacity) { if (initialCapacity < 1) { ostringstream s; s << "initial capacity=" << initialCapacity << "Must be > 0"; throw ilegalParameterValue(s.str()); } firstNode = NULL; listSize = 0; } template<class T> chain<T>::chain(const chain<T>& theList) { listSize = theList.listSize; if (listSize == 0) { firstNode = NULL; return; } chainNode<T>* Node = new chainNode<T>(theList.firstNode); firstNode = new chainNode<T>(Node->element); Node = Node->next; chainNode<T>* targetNode = firstNode; while (Node != NULL) { targetNode->next = new chainNode<T>(Node->element); targetNode = targetNode->next; Node = Node->next; } targetNode->next = NULL; } template<class T> chain<T>::~chain() { while (firstNode != NULL) { chainNode<T>* nextNode = firstNode->next; delete firstNode; firstNode = nextNode; } } template<class T> T& chain<T>::get(int theIndex) const { checkIndex(theIndex); chainNode<T>* currentNode = firstNode; for (int i = 0; i < theIndex; i++) { currentNode = currentNode->next; } return currentNode->element; } template<class T> int chain<T>::indexOf(const T& theElement) const { chainNode<T>* currentNode = firstNode; int theIndex = 0; while (currentNode->element != theElement&¤tNode !=NULL) { currentNode = currentNode->next; theIndex++; } if (currentNode == NULL) return -1; else return theIndex; } template<class T> void chain<T>::insert(int theIndex, const T& theList) { } template<class T> void chain<T>::erase(int theIndex) { } template<class T> void chain<T>::output(ostream& out) const { } int main() { return 0; }链表优缺点：
优点：
删除插入等操作不需要移动节点，只需要改变指针
空间利用率高；
缺点：
查找需要遍历整个链表。
