线性表-数组实现（C++）

专栏说明：

该专栏为学习笔记，内容是c++实现的数据结构与算法，代码主要copy自大黑书《数据结构与算法分析——c++语言描述》。阅读需要c++基础（包括模板类的使用）

原文发布于个人网站www.gislxz.com，欢迎各位交流。

线性表是最简单的数据结构（各种数据结构的基础概念我就不写了，网上一搜一大把图文并茂的，我只分享一下代码实现），一般有数组实现和链式描述两种（正如所有数据结构的底层都是数组或链表），数组实现可以用基础数组，也可以用vector等结构来实现。 

c++数组本身限制是很多的，必须提前设置好数据类型和长度。

这样的静态数组显然功能局限，因而在实现数据结构时往往使用动态数组。

接着我们需要实现一个更改数组长度的函数

changeLength1D这个函数首先是一个模板函数，需要注意第一个参数类型是T*&，即引用一个T指针。如果不加引用，那我们相当于复制了外部调入的指针，可以正常修改该指针指向的对象，但没法改变这个外部指针的指向（只是把函数内这个指针指向了新数组，函数运行结束这个指针就释放了）。

通过指针的指针也可以达到类似效果

有了变长函数我们就可以来实现线性表了

构造函数和拷贝构造函数的具体实现

构造函数的赋值有一个细节，像上面这么写就是先创建arraylength这个变量，等执行到arrayLength = initialCapacity;这行代码在进行赋值，如果写成arrayList<T>::arrayList(int initialCapacity):arrayLength(initialCapacity)那就是创建变量时直接赋值，这样节省一点效率，另外如果arraylength是const修饰的话，那么只能这样在初始化时就赋值。

查找和获取指定位置的元素都很简单，删除和插入稍微复杂一些。删除需要把删除后的元素向左移，插入不仅要平移，还得提前判断一下长度够不够了。