线性表是n个数据特性相同的元素的组成有限序列，是最基本且常用的一种线性结构(线性表，栈，队列，串和数组都是线性结构），同时也是其他数据结构的基础。
线性表最核心的是这几种基本方法，即：
一、判断线性表是否为空
二、得到线性表的大小
三、得到线性表中的某个元素或某个元素的索引
四、插入或删除元素
五、输出线性表中的元素
这几种方法都可用数组和链表来实现，掌握了这几种基本方法，其他的变形也不在话下。数组方式看代码理解很好理解，下面解释一下链表方式实现。
链表可分为单向链表、双向链表、循环链表，这里提供的是单向链表的代码。
单链表：

文章图片

从上图可以看出，单链表的上一个结点指针指向下一个结点，最后一个结点的指针域为null。
结点的删除：

文章图片

删除一个结点，如删除上图中q结点，只需将p结点中的指针域指向a3，然后将a2释放掉（free）即可。
结点的插入：

文章图片

插入一个结点，如插入上图中s结点，首先将s的指针域指向a2（也就是把s的next赋值为p的next），然后将p结点的指针域指向x即可（p的next指向x）。

其他几种链表的实现大同小异，这里就不介绍了

两种方式的代码实现：
一、数组实现
1、基本方法头文件

#ifndef linearList_ #define linearList_#include using namespace std; template class linearList { public: virtual ~linearList() {}; virtual bool empty() const = 0; virtual int size() const = 0; virtual T get(int theIndex) const = 0; //返回索引为 theIndex 的元素 virtual void erase(int theIndex) = 0; virtual void insert(int theIndex, const T& element) = 0; virtual void output(ostream& out)const = 0; }; #endif

2、实现方法的头文件

#ifndef arrayList_ #define arrayList_#include #include #include #include"linearList.h" using namespace std; template class arrayList : public linearList { protected: int listSize; //线性表的大小 T* element; //数据域 int arraylength; //线性表的长度 public: arrayList(int length) { arraylength = length; element = new T[arraylength]; listSize = 0; } ~arrayList() { delete [] element; } bool empty() const { return listSize == 0; } int size() const { return listSize; } T get(int theIndex) const; void erase(int theIndex); void insert(int theIndex, const T& theElement); void output(ostream& out) const; void changeLength(); }; template void arrayList::changeLength() { arraylength = arraylength * 2; T* temp = new T[arraylength]; copy(element, element + listSize, temp); delete[]element; element = temp; }template T arrayList::get(int theIndex) const {//得到某个元素的索引 if (theIndex<0 || theIndex>listSize) { cout << "the Index is wrong"; return 1; } return element[theIndex]; }template void arrayList::erase(int theIndex) {//删除某个元素 if (theIndex<0 || theIndex>listSize) { cout << "the Index is wrong"; } else { copy(element + theIndex + 1, element + listSize, element + theIndex); //利用复制，把theIndex 后面的元素往前挪一个 } }template void arrayList::insert(int theIndex, const T& theElement) {//插入一个元素 if (listSize + 1 > arraylength) { changeLength(); } copy(element + theIndex, element + listSize, element + theIndex + 1); element[theIndex] = theElement; listSize++; }template void arrayList::output(ostream& out) const {//输出 copy(element, element + listSize, ostream_iterator(cout, "")); }template ostream& operator<<(ostream& out, const arrayList& x) {//输出 x.output(out); return out; }#endif

3、测试代码

#include #include"arrayList.h" #include"linearList.h" using namespace std; int main() { arrayList x(20); cout << "the size is " << x.size() << endl; cout << "after insert:" << endl; x.insert(0, 3); x.insert(0, 2); x.insert(2, 4); cout << "the size is " << x.size() << endl; cout << x << endl; system("pause"); return 0; }

二、链表实现
1、数据类型头文件

#ifndef chainNode_ #define chainNode_template struct chainNode { T element; //数据域 chainNode *next; //指针域 chainNode() {} chainNode(const T& element) { this->element = element; } chainNode(const T& element, chainNode* next) { this->element = element; this->next = next; } }; #endif

2、基本方法头文件

#ifndef linearList_ #define linearList_#include using namespace std; template class linearList { public: virtual ~linearList() {}; virtual bool empty() const = 0; virtual int size() const = 0; virtual T& get(int theIndex) const = 0; virtual int indexOf(const T& theElement) const = 0; virtual void erase(int theIndex) = 0; virtual void insert(int theIndex, const T& theElement) = 0; virtual void output(ostream& out) const = 0; }; #endif

3、实现基本方法的头文件

#ifndef chain_ #define chian_#include #include #include #include"chainNode.h" #include"linearList.h" using namespace std; template class chain : public linearList { protected: void checkIndex(int theIndex) const; chainNode* firstNode; int listSize; public: chain() { listSize = 0; firstNode = NULL; } chain(const chain& theList); ~chain(); bool empty() const; int size() const; T& get(int theIndex) const; int indexOf(const T& element) const; void erase(int theIndex); void insert(int theIndex, const T& element); void output(ostream& out) const; }; template chain::chain(const chain& theList) { listSize = theList.listSize; if (listSize == 0) { firstNode = NULL; return; } chainNode* currentNode = theList.firstNode; firstNode = new chainNode(currentNode->element); currentNode = currentNode->next; chainNode* targetNode = firstNode; while (currentNode->next != NULL) { targetNode = new chainNode(currentNode->element); targetNode = targetNode->next; currentNode = currentNode->next; } targetNode->next = NULL; }template chain::~chain() { chainNode* nextNode = firstNode; while (firstNode != NULL) { nextNode = firstNode->next; delete firstNode; firstNode = nextNode; } }template void chain::checkIndex(int theIndex) const { if (theIndex < 0 || theIndex > listSize) { ostringstream s; s << "index = " << theIndex << " size = " << listSize; throw illegalIndex(s.str()); //注意，我的异常处理和标准异常处理不同 }//复制代码后要改一下异常处理 }template bool chain::empty() const { return listSize == 0; }template int chain::size() const { return listSize; }template T& chain::get(int theIndex) const { checkIndex(theIndex); chainNode *currentNode = firstNode; for (int i = 0; i < theIndex; i++) { currentNode = currentNode->next; } return currentNode->element; }template int chain::indexOf(const T& theElement) const { chainNode *currentNode = firstNode; int index = 0; while (currentNode != NULL&¤tNode->element != theElement) { currentNode = currentNode->next; index++; } if (currentNode == NULL) { return -1; } else { return index; } }template void chain::erase(int theIndex) { chainNode *deleteNode; chainNode *currentNode = firstNode; if (theIndex == 0) { deleteNode = firstNode; firstNode = firstNode->next; } else { for (int i = 0; i < theIndex - 1; i++) { currentNode = currentNode->next; } deleteNode = currentNode->next; currentNode->next = currentNode->next->next; } listSize--; delete deleteNode; }template void chain::insert(int theIndex, const T& theElement) { checkIndex(theIndex); if (theIndex == 0) { firstNode = new chainNode(theElement, firstNode); } else { chainNode* p = firstNode; for (int i = 0; i < theIndex - 1; i++) { p = p->next; } p->next = new chainNode(theElement, p->next); } listSize++; }template void chain::output(ostream& out) const { chainNode* p = firstNode; while (p != NULL) { cout << p->element << " "; p = p->next; } }template ostream& operator<<(ostream& out, const chain& x) { x.output(out); return out; }#endif

4、测试代码

#include #include"linearList.h" #include"chain.h" using namespace std; int main() { chain x; cout << "x size is " << x.size() << endl; x.insert(0, 3); x.insert(1, 4); x.insert(2, 1); x.insert(3, 2); x.insert(4, 9); cout << "x size is " << x.size() << endl; cout << x << endl; system("pause"); return 0; }

【线性表与栈】
栈是一种特殊的线性表，即“先进后出”，会了这个，栈也就会了，这里就不累述了。

推荐阅读

• 

  教你pdffactory如何批量打印
• 

  东北地区包括哪些地方 我国东北地区包括哪几个省
• 

  好主板和差主板性能上差别区分
• 

  mysql 创建user mysql如何创建管理员并提供权限
• 

  锦心似玉在哪个台播什么时候播 锦心似玉是在哪个台播出的
• 

  泡沫多的奶粉好不好
• 

  荷包蛋烧肉怎么做 荷包蛋烧肉怎么做才好吃
• 

  win10打印机在哪（win10打印机在哪查看）
• 

  dnf周年庆是几号
• 

  班级班长申请书怎么写
• 

  on开还是off开 闹钟是on开还是off开
• 

  120长40宽的鱼缸能养龙鱼吗
• 

  星期六左眼跳代表什么
• 

  乔迁之喜送什么礼物好
• 

  遇到三菱3匹空调显示06怎么办？3个处理方法帮助你
• 

  老王教你如何夜观天象 夜观天象
• 

  尼康单反显示err 尼康单反显示clock
• 

  小编教你溜云库模型怎么导入3DMax
• 

  爱普生l1119废墨怎么更换
• 

  蚊子为什么会耳朵里

• golang学习|算法4（单链表的相关操作）
• 数据结构学习（C++实现线性表的顺序存储结构）