数据结构

绪论

​ 数据表示的本质是数据结构设计，数据处理的本质是算法设计。

​ 算法+数据结构=程序 ——Niklaus Wirth

• 数值计算问题：如概率统计，求极限等，用数学建模、公式推导来解决
• 非数值计算问题：对弈问题等，用数据结构和算法来解决

​ 数据结构解决数据如何存储的问题，算法解决如何操作数据的问题。

数据结构的基本概念

​ 数据元素是数据的基本单位。

​ 数据项是构成数据元素的不可分割的最小单位，每个数据元素可以包含多个不同的数据项，每个数据项具有独立的含义。

​ 数据类型是具有相同性质的数据的集合以及在这个数据集合上的一组操作。

​ 数据类型分为简单类型（原子类型）和构造类型（结构类型）。

​ 数据结构是指按照某种逻辑关系组织起来的一组数据，按照一定的存储方法存储在存储器中，并在这些数据上定义一组运算的集合。通常认为数据结构包含以下3方面的内容。

• 数据元素之间的逻辑关系，称为数据的逻辑结构。
• 数据元素及其关系在计算机存储器内的存储形式，称为数据的存储类型，物理结构。
• 对数据的操作或运算。

​ 逻辑结构描述了数据相互间的关联形式或邻接形式，反映了数据内部的构成方式，定义了数据的本质特点，因此人们常常将数据的逻辑结构称为数据结构。

​ 常见的逻辑结构共有4种：

• 集合，共同属于一个集合的关系，通常要求集合中的元素不可重复；
• 线性结构，其数据元素之间的逻辑特点是有且仅有一个起始结点和一个终端结点，并且其他结点的前面有且只有一个结点（称为直接前驱），每个结点的后面有且只有一个结点（称为直接后继）。
• 树结构，其数据元素之间存在着一对多的层次关系。
• 图结构，数据元素之间存在多对多的关系。

​ 数据的存储结构考虑的是如何在计算机的存储器中存储各个数据元素，并同时反映数据元素间的逻辑关系。基本的存储结构通常有两大类：

• 顺序存储结构：用一组连续的存储单元一次存储各个数据元素，数据元素之间的逻辑关系由存储单位的邻接关系体现。顺序存储通常借助于数组来体现。

• 链式存储结构：即用一组任意的存储单位来存储各个数据元素，数据元素之间的关系通常用指针来表示，例如后一个元素的地址存储在前一个元素的某个特定数据项中。

  

​ 学习一种数据结构，首先分析其逻辑结构及其相关操作，掌握了各种数据结构的逻辑特点，当分析待处理数据时可以根据数据特点来确定数据结构类型。分析了逻辑结构后，再学习其各种常见存储方式。

算法与算法分析

​ 数据的运算是通过算法描述的。

算法描述

​ 每个算法必须满足以下5个准则：

• 输入：具有0或多个输入参数
• 输出
• 有穷性：每条指令的执行次数必须是有限的，即执行了有穷步后能结束
• 确定性：每条指令必须有确切的含义，无二义性
• 可行性：每条指令的执行时间都是有限的

​ 在用面向对象的思想设计算法时，往往将算法看作某个类的某种运算方法，例如每个自然数都可以与其他自然数求解两者的最大公约数，因此这个求解运算可认为是自然数类的一种操作方法。

算法分析

时间复杂度

​ 将问题规模设为n，作为参数进行分析，运行算法的时间T可看成问题规模n的函数，记为T(n)

​ 假定每条语句执行一次所需是时间是单位时间，则每条语句执行的时间正比于该语句执行的次数。

​ 通常将语句执行的次数称为该语句的频度，算法运行的时间可认为是算法中所有语句的频度之和。

​ 时间复杂度O：如果存在两个正常数c和n₀，对于任意\(n\geq n_0\)，都有\(T(n)\leq c\times f(n)\)，则称T(n)=O(f(n))

​ 一般来说，只要算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也只是一个常数，此时算法的复杂度为O(1)

​ 常见的时间复杂度有：常数阶O(1)、对数阶O(log n)、线性阶O(n)、线性对数阶O(nlog n)等。解决同一问题的不同算法，算法的时间复杂度越低越好。当问题的规模较大时，通常认为具有指数阶的算法是不可以计算的。

空间复杂度

​ 算法执行过程中所耗费的存储空间。通常可以以空间换时间。

NP问题

​ P问题：若存在以问题规模n为变量的多项式函数p(n)，解决该问题的算法的时间复杂度为O(p(n))，则称该问题为多项式时间问题，即P问题。其解决算法为多项式时间算法

​ 还有另一类算法，其时间复杂度不能用多项式函数去界定，称为指数时间算法，例如O(2ⁿ),O(n!)等

​ 如果问题规模n较大，显然多项式时间算法优于指数时间算法。

​ 对于很多问题，可能不清楚是否存在一个能在多项式时间里解决它的算法，但是可以在多项式的时间里验证一个解，这种问题称为非确定性多项式时间问题，简称NP问题，显然\(P\subseteq NP\)

​ 例如，大的合数分解质因数，没有同一个公式可以直接得到因子，无法直接计算得到，只能通过间接的猜算得到结果，这就是非确定性问题。

​ 这些问题通常有个算法，它不能直接告知答案是什么，但可以告知某个可能的结果是正确的还是错误的，这个可以告知猜算结果正确与否的算法，假如可以在多项式时间内算出来，就称为NP问题。

​ 如果这个问题的所有可能答案都是可以在多项式时间内进行正确与否的验算的话，就称为NP完全问题，即NPC问题。

​ NP问题通俗来说就是其解的正确性能够被“很容易检查”的问题，即存在一个多项式检查算法。若NP中所有问题到某一个问题是图灵可归约的，则该问题为NP-hard问题。

​ NP-hard问题不一定是一个NP问题，但所有的NP问题都可以约化到该问题，例如，售货员旅行问题即TSP，是最具有代表性的NP问题之一。

STL与数据结构

​ STL（Standard Template Library，标准模板类）是C++语言提供的一个基础模板类型，包含了各种常用的存储数据的模板类及相应的操作函数，为开发者提供了一种快速有效的访问机制。

​ 从根本上来说，STL是一些容器、算法合其他一些组件的集合，这些容器有list，vector，set，map等。基本达到了各种存储方法合相关算法的高度优化。STL已经是C++的一部分，不用额外安装。

​ 在C++标准中，STL被组织为以下13个头文件：<algorithm>,<deque>,<functional>,<iterator>,<vector>,<list>,<map>,<memory>,<numeric>,<queue>,<set>,<set>,<stack>和<utility>。通常认为STL由空间管理器、迭代器、泛函、适配器、容器和算法6部分构成，其中前面4部分用于服务后面两部分。

​ 空间管理器：为容器类模板提供用户自定义的内存申请和释放功能。默认情况下，STL仍然使用C++的内存管理函数或操作符来完成动态内存申请和释放。

​ 迭代器：类似于指针，存储某个对象的地址或者说指向某个对象，有时也被称为广义指针。迭代器可以为STL中的算法提供数据的输入，也可以用来遍历容器类或流中的对象。指针本身也可以认为是一个迭代器，用户也可以自定义迭代器。

​ 泛函：在STL中，如果某个类重载了函数调用运算符“()”，则称该类为泛函类，称其对象为泛函。通过引入泛函，可以为算法提供某个策略。例如，同一个排序算法，可以利用泛函完成对不同关键字进行升序或降序等各种排列策略。

​ 适配器：适配器对象将自己与另外一个对象进行绑定，使对适配器对象的操作转换为被绑定对象的操作。STL中适配器应用较广，有容器适配器，如栈(stack)、队列(queue)、优先队列(priority_queue)，以及迭代器适配器和泛函适配器。

​ 容器：包含若干对象的数据结构，并提供少量操作接口。STL提供3类标准容器：顺序容器、排序容器和哈希容器，后两类容器有时也统称为关联容器。

• 顺序容器：包括向量(vector)、列表(list)、双端队列(deque)。顺序容器将单一类型元素聚集起来称为容器，然后根据位置来存储和访问这些元素。
• 排序容器：包括集合(set)、多重集合(multiset)、映射(map)以及多重映射(multimap)。排序容器的元素位置一般通过元素键值的大小关系来确定，可以通过键值高效地查找和读取元素。
• 哈希容器：包括哈希集合(hash_set)、哈希多重集合(hash_multiset)、哈希映射(hash-map)以及哈希多重映射(hash_multimap)。哈希容器中的元素位置直接通过元素的键值确定，通过键值将会更加高效地查找和读取元素。

​ 算法可以认为是STL的精髓，所有算法都是采用函数模板的形式提供的。STL提供的算法大致分为4类：日常事务算法、查找类算法、排序类算法、工作类算法。

线性表

​ 线性表的逻辑结构简单，相邻元素之间只有单一的前驱和后继的关系，便于实现和操作。

定义

​ 线性表简称表，是由具有零个或多个相同类型的数据元素构成的有限序列。元素的个数称为线性表的长度。长度为零的线性表称为空表。对于非空表，通常记为： \[ L=(a_1,a_2,\cdots,a_n) \] ​ 其中，n为线性表的长度，\(a_i(1\leq i \leq n)\)称为数据元素或结点，i表示该元素在线性表中的位置或序号，称a_i是线性表的L的第i个数据元素。a_i称为第一个元素或开始结点，a_n称为最后一个元素或终端结点。对于中间任意一个元素\(a_i(1< i < n)\)，称a_i-1为a_i的直接前驱，称a_i+1为a_i的直接后继。线性表的实例如图

对于非空的线性表L，具有如下性质：

• 有且仅有一个开始结点a₁，a₁没有直接前驱，有且仅有一个直接后继a₂；
• 有且仅有一个终端结点a_n，a_n没有直接后继，有且仅有一个直接前驱a_n-1；
• 其余的任意内部结点a_i(1<i<n)有且仅有一个直接前驱结点a_i-1，有且仅有一个直接后继结点a_i+1；

​ 对于一个含有相同类型元素的有限数据集合，如果满足上述性质，则认为该数据集合是线性表结构。例如一周的7天，英文字母表。

线性表的运算

​ 线性表的运算是指对线性表的基本操作，这里所说的运算是在逻辑结构上的定义，只是确定这些功能是什么，而不去考虑其具体实现。

1. 求长度GetLength(L)，求线性表L的长度；
2. 置空表SetNull(L)，将线性表置成空表；
3. 按位置找Get(L,i)，查找线性表的第i个元素，i应满足\(1\leq i\leq GetLength(L)\)；
4. 修改Set(L,i,x)，修改线性表中第i个元素的值为x；
5. 删除Delete(L,I)，删除线性表L中的第i个元素；
6. 插入Insert(L,i,x)，在线性表L的第i个位置插入一个值为x的新元素；
7. 按值查找Locate(L,x)，查找线性表L中值为x的元素；
8. 排序sort(L)，按某种要求重新将线性表L中各元素进行排列；

各种常用的存储结构

顺序表

​ 把线性表中的数据元素按逻辑次序一次存放在一组地址连续的存储空间。通常认为线性表中的所有数据元素具有相同的数据类型，占用相同的存储空间。

​ 假定顺序表长度为n，每个元素占用c个存储单位，其中第一个存储单元的地址就是该元素的存储地址，第i个数据元素a_i的地址记为LOC(a_i)，则有如下计算公式： \[ LOC(a_i)=LOC(a_1)+(i-1)\times c\space \space 1\leq i \leq n \] ​ 也就是说，顺序表中的每个元素的存储地址是该元素在表位置的线性函数，只要知道第一个元素的存储地址以及每个元素占用的存储空间，就可以直接计算得到任意元素的存储地址。

​ 因此顺序表是一种随机存储结构。

​ 显然，在C++中，可以用数组来顺序存储顺序表中的所有元素。

顺序表的优点

1. 不需要为表示元素之间的逻辑关系而增加额外的存储空间；
2. 可以方便的随机访问顺序表中的任一位置的元素；

顺序表的缺点

1. 插入和删除操作需移动大量的数据元素，效率较低。在等概率条件下，两种操作平均需要移动顺序表中约一半的元素；
2. 顺序表难以选择合适的存储容量。

链式存储结构

​ 链表用一组任意的存储单元存放线性表中的各个元素，这组存储单元可以是连续的，也可以是分散的。因此，链表中数据元素的逻辑次序和物理次序不一定相同。为了正确地表示结点的逻辑关系，在存储每个元素值的同时，还要存储该元素的直接后继元素的位置信息，这个信息称为指针(pointer)或链(link)，这个两部分信息构成了实际的存储结构，称为结点(node)，然后各个结点通过指针链接起来形成一个完整的链式结构，称为链表，示例如下图：

​ 通常人们关心的是单链表中各个结点的逻辑次序，而不关心其实际存储的位置。

​ 指向第一个结点的指针，我们称为头指针；指向最后一个结点的指针，由于其没有后继结点，我们设置为NULL

​ 根据链表结构或者节点结构的不同，可以把链表分为：单链表，循环链表和双链表三种。。

单链表

​ 链表中的每个结点只包含一个指向直接后继的指针即为单链表。若链表为空，则头指针为NULL，若链表不为空，头指针存储第一个结点的地址。有时，单链表的第一个结点不存放数据，仅作为表头使用，则称其为带头节点的单链表；否则称其为不带头结点的单链表

、

循环链表

​ 如果将单链表的最后一个结点的指针指向头节点，则整个链表构成一个环，这种首尾相接的单链表被称为单循环链表。

​ 这种循环链表查找第一个元素很方便，但查找最后一个元素很慢，因此常常使用尾指针rear来表示单循环链表，如下图所示，即设指针rear指向单循环链表的最后一个结点，这样就可以很方便地访问首尾两端的元素了。

双链表

​ 对于单链表，由于前一个结点已经存储了直接后继结点的地址，因此可以直接得到直接后继结点。而如果查找当前结点的直接前驱结点，则需要从第一个元素开始遍历，操作比较繁琐，为此，可以在每个结点中再加入一个指针域，用于存储前一个元素的地址，这样便可以方便地得到直接前驱元素，这种链表中有两条方向相反的链，因此称为双向链表，简称双链表。

顺序表的实现

顺序表的存储结构

​ 由于顺序表中的数据元素可以是任意类型，因此在定义顺序表时可采用C++模板的机制。

template<class T,int N>
class SeqList
{
    public:
    	SeqList(){length=0;}
    	SeqList(T a[],int n);
        int GetLength(){return length;}
    	void PrintList();
    	void Insert(int i,T x);
    	T Delete(int i);
    	T Get(int i);
    	int Locate(T x);
    private:
    	T data[N];
    	int length;
}

​ 该类含有两个私有变量，数组data存储顺序表的所有数据元素，length表示顺序表当前的长度。

顺序表的基本运算

#### 构造函数

​ 模板类中含有两个构造函数，无参构造用于建立空顺序表，有参构造函数SeqList(T a[],int n)创建一个长度为n的顺序表，其数据元素依次来自参数数组a的各个元素，其长度为传入的参数n。如果n超出了顺序表的最大长度，则应该抛出异常，终止操作。

template<class T,int N>
SeqList<T,N>::SeqList(T a[],int n)
{
    if(n>N)throw"数组超出顺序表的最大长度";
    for(int i=0;i<n;i++)
    {
        data[i]=a[i];
    }
    length=n;
}

遍历顺序表

​ 遍历顺序表是指按序号依次访问顺序表中的各个数据元素。为简单起见，“访问”在这里表示为将元素的值显示。需要注意的是，由于数据类型不确定，显示操作可能有多种不同处理方式。

​ 简单数据类型的遍历操作如下：

template<class T,int N>
void SeqList<T,N>::PrintList()
{
	for(int i=0;i<length;i++)
	{
		cout<<data[i]<<" ";
	}
	cout<<endl;
}

​ 若元素为构造类型，则需要使用对应的显示函数。

插入操作

​ 在顺序表的第i个位置上插入值为x的新元素。若在表尾追加，则不涉及表中已有元素的移动；若在表头或中间某个位置i插入，则顺序表中原来序号从i到n的元素都要后移一个位置，最终顺序表的长度由n变为n+1。

​ 需要注意的是，数据元素在后移时，必须从最后一个元素开始移动，即先移动a_n到n+1的位置，再移动a_n-1到n位置，依次类推，知道将a_i移动到i+1的位置。对于一些操作不成功的情况，需要抛出异常

template<class T,int N>
void SeqList<T,N>::Insert(int i,T x)
{
    if(length>=N)throw"上溢异常";
    if(i<1||i>length+1)throw"位置异常";
    for(int j=length;j>=i;j--)
        data[j]=data[j-1];
    data[i-1]=x;
    length++;
}

​ 下面对算法的时间复杂度进行分析，该算法的问题规模是顺序表的长度n，基本语句是for循环中元素后移的语句。

​ 当插入的位置在表尾，即i=n+1时，不执行元素后移操作，这是最好的情况，时间复杂度为O(1)；

​ 当插入的位置在表头，即i=1时，所有元素都要后移，这是最坏的情况，时间复杂度为O(n)；

​ 当插入的位置在表的中间某一位置时，则要分析算法的平均时间复杂度。设T(n)表示元素移动过的平均次数，插入位置为i\((1\leq i\leq n+1)\)，元素的移动次数为n-i+1，因此有 \[ T(n)=\sum_{i=1}^{n+1}p_i(n-i+1) \] ​ 其中，pi表示在表中第i个位置插入新元素的概率，假定在任意位置进行插入操作的概率都相同，则对于任意的i，有： \[ p=\frac{1}{n+1} \] ​ 因此， \[ T(n)=\sum^{n+1}_{i=1}p_i(n-i+1)=\frac{1}{n+1}\sum_{i=1}^{n+1}(n-i+1)=\frac{n}{2}=O(n) \] ​ 也就是说，对顺序表进行插入操作，在等概率的情况下，平均要移动表中一半的元素，算法的平均复杂度为O(n)。

删除操作

​ 把第i个位置的元素删除并返回删除的元素。若要删除表头或中间某个位置i上的元素，则顺序表中原来序号从i+1到n的元素都要向前移动一个位置。

​ 与插入操作相反，数据元素在位移时，必须从第n+1个元素开始移动，即先移动a_i+1到i位置，再移动a_i+2到i+1的位置，以此类推，对于操作不成功的的特殊情况需要抛出异常或返回错误号。例如，如果在删除操作之前顺序表已经为空表，则抛出下溢异常；如果删除的位置不合理，则抛出位置异常。

​ 伪代码描述：

[1]如果表空，则抛出下溢异常；

[2]如果删除位置不合理，则抛出位置异常；

[3]取出将被删除的元素；

[4]依次从第i+1个元素开始到第n个元素分别前移1个位置；

[5]表长减1，并返回被删除元素的值。

template<class T,int N>
T SeqList<T,N>::Delete(int i)
{
    if(0==length)throw"下溢错误";
    if(i<1||i>length)throw"位置错误";
    T x=data[i-1];//将待删除元素暂存
    for(int j=i;j<length;j++)
    {
        data[j-1]=data[j];//从第i+1个元素开始(下标为i)开始顺序前移，直到最后一个元素
    }
    length--;
    return x;
}

​ 算法时间复杂度：

​ 类似于插入运算，表头的为O(n)，表尾的为O(1)，中间某个位置时： \[ T(n)=\sum _{i=1}^n p_i(n-1) \] ​ 其中p_i表示删除表中第i个位置上元素的概率。假定在任意位置进行删除操作的概率都相同，则对于任意的i，有 \[ p_i=\frac{1}{n} \] ​ 因此 \[ T(n)=\sum^n_{i=1}p_i(n-1)=\frac{1}{n}\sum^n_{i=1}p_i(n-1)=\frac{n-1}{2}=O(n) \]

​ 也就是说，算法的平均时间复杂度为O(n)

​

查找操作

按位查找

​ 查找顺序表中指定位置的数据元素

template<class T,int N>
T SeqList<T,N>::Get(int i)//获取线性表第i个位置的元素
{
    if(i<1||i>length)throw"查找位置非法";
    return data[i-1];
}

​ 显然，时间复杂度为O(1)

按值查找

​ 查找顺序表中指定数值的数据元素。需要依次比较顺序表中的每个数据元素，直到找到指定数值的数据元素或遍历完整数据表为止。

template<class T,int N>
int SeqList<T,N>::Locate(T x)//查找线性表中值为x的元素，找到后返回其位置
{
    for(int i=0;i<length;i++)
    {
        if(data[i]==x)return i+1;
    }
    return 0;//查找失败
}

​ 进行值比较的语句，对于复杂类型，如自定义类，需要在自定义类中对“==”进行运算符重载。

​ 算法的平均时间复杂度为O(n)

​ 如果data数组从data[1]开始存储顺序表数据元素，data[0]不存储顺序表数据元素，能否设计更高效的方法

​ 可以采用“哨兵”

template<class T,int N>
int SeqList<T,N>::Locate(T x)//查找线性表中值为x的元素，找到后返回其位置
{
    data[0]=x;
    int i=length-1;
    while(x!=data[i])i--;
    return i+1;
}

顺序表的应用

​ 模板类SeqList中的形式化参数T，在实例化时可以用任何的数据类型来替换。

SeqList.h

#include<iostream>
template <class T, int N>
class SeqList
{
public:
    SeqList() { length = 0; }
    SeqList(T a[], int n);
    int GetLength() { return length; }
    void PrintList();
    void Insert(int i, T x);
    T Delete(int i);
    T Get(int i);
    int Locate(T x);

private:
    T data[N];
    int length;
};
template <class T, int N>
SeqList<T, N>::SeqList(T a[], int n)
{
    if (n > N)
        std::cout << "数组超出顺序表最大长度";
    for (int i = 0; i < n; i++)
    {
        data[i] = a[i];
    }
    length = n;
};
template <class T, int N>
void SeqList<T, N>::PrintList()
{
    for (int i = 0; i < length; i++)
    {
        data[i].print();
    }
    std::cout << std::endl;
};
template <class T, int N>
void SeqList<T, N>::Insert(int i, T x)
{
    if (length >= N)
        std::cout << "上溢异常";
    if (i < 1 || i > length + 1)
        std::cout << "位置异常";
    for (int j = length; j >= i; j--)
        data[j] = data[j - 1];
    data[i - 1] = x;
    length++;
};
template <class T, int N>
T SeqList<T,N>::Delete(int i)
{
    if (length == 0)
        std::cout << "下溢错误";
    if (i < 1 || i > length)
        std::cout << "位置错误";
    T x = data[i - 1];
    for (int j = i; j < length; j++)
    {
        data[j - 1] = data[j];
    }
    length--;
    return x;
};
template <class T, int N>
T SeqList<T, N>::Get(int i) // 获取线性表第i个位置的元素
{
    if (i < 1 || i > length)
        std::cout << "查找位置非法";
    return data[i - 1];
};
template <class T, int N>
int SeqList<T, N>::Locate(T x) // 查找线性表中值为x的元素，找到后返回其位置
{
    for (int i = 0; i < length; i++)
    {
        if (data[i] == x)
            return i + 1;
    }
    return 0; // 查找失败
};

PHONEBOOK.h

#include <iostream>
class PHONEBOOK
{
private:
    int m_ID;
    std::string m_name;

public:
    PHONEBOOK() {}
    PHONEBOOK(int id, char *name)
    {
        m_ID = id;
        m_name = name;
    }
    void print()
    {
        std::cout << m_ID << '\t' << m_name << std::endl;
    }
    bool operator==(PHONEBOOK &p)
    {
        if (p.m_ID == m_ID)
            return true;
        return false;
    }
};

主程序

#include <iostream>
#include "PHONEBOOK.h"
#include "Seqlist.h"
using namespace std;
int main()
{
    PHONEBOOK pbook[2] = {{20181208, "Mary"}, {20181127, "Tom"}};
    PHONEBOOK record(20181209, "Phoenix");
    SeqList<PHONEBOOK, 100> list(pbook, 2);
    list.PrintList();
    list.Insert(1, record);
    list.PrintList();
    PHONEBOOK x = list.Delete(3);
    x.print();
    list.PrintList();
    int p = list.Locate(record);
    cout << p << endl;
}

STL中的顺序表

​ 向量(vector)就是使用顺序结构存储实现的模板类，即内部使用数组来实现的模板类，因此vector具有顺序表的所有特点

方法名	方法描述
back()	返回最后一个向量的值
begin()	返回指向第一个元素的迭代器
capacity()	返回容量
clear()	将容器清空
empty()	若大小为0，则返回true；否则返回false
end()	返回指向最后一个容器的迭代器
erase()	在向量的任意位置删除元素
insert()	在向量的任意位置插入元素
pop_back()	删除最后一个元素
push_back()	在向量的尾部添加元素
resize()	改变容量
size()	返回向量中的元素个数

​ 在使用vector之前，需要包含相应的头文件：

#include<vectore>
using namespace std;
vector<int>ivec;//定义向量对象ivec，向量中每一个元素都是int类型
vector<PHONEBOOK>vec;//定义向量对象vec，向量中每一个元素都是PHONEBOOK类型

​ vector在实例化时不需要声明长度。标准库负责管理与存储元素相关的内存，用户不用担心内存不够。

​ 为了防止访问时地址越界，一般使用迭代器

​ 定义迭代器：

vector<PHONEBOOK>::iterator it;

​ 迭代器类似于指针，可以使用*it 来访问相应元素。如it=vec.begin()表示迭代器it指向vec的第一个元素；it=vec.end()表示迭代器指向vec的最后一个元素。

​ vector容器是自动增长的，随着数据元素的增多，vector能自动申请内存（自动扩容）

单链表的实现

​ 动画理解链表

​ 顺序表利用物理位置上的相邻关系来表示数据元素之间的逻辑关系，这一特点使得存储结构具有以下优缺点：

优点：

• 不需要为表示元素之间的逻辑关系而增加额外的存储空间
• 可以方便地随机访问顺序表中任一位置的元素

缺点：

• 插入和删除操作需移动大量的数据元素，效率较低；在等概率的情况下，两种操作平均需要移动顺序表中约一半的元素
• 顺序表难以选择合适的存储容量。顺序表要求占用连续的存储空间，存储分配只能预先进行，因此属于静态存储分配方式，若开始时分配的空间过小，则插入操作很容易引起顺序表的溢出，若开始时分配的空间过大，则可能造成一部分的空间长期空置，不能被充分利用。

​ 为了克服顺序表的缺点，可以采用链式存储方式存储线性表，最简单的链式存储方式就是单链表，这种方法采用动态存储分配方式，即根据实际需要随时申请内存，在不需要时将内存释放。

单链表的存储结构

​ 单链表由一个一个结点通过结点的指针(pointer)或链(link)按照元素逻辑顺序链接而成，因此，单链表的每一个结点都由数据域(data)和指针域(next)两部分构成，data域用来存储元素的值，next域用来存储直接后继的地址或位置。

​

​ 由于结点的数据类型不确定，因此可以采用模板机制，使用结构类型或类来描述单链表的结点。

template<class T>
struct Node
{
    T data;
    struct Node<T> * next;
}

​ 单链表除第一个结点外，其他每个结点的地址都存储在前一个结点的next域中，因此，只要取得第一个结点的地址，就能顺序遍历单链表的所有结点，因此头指针具有标识一个单链表的功能。

​ 对于不带头节点的单链表，若表为空则头指针值为NULL；若表不为空，头指针存储第一个结点的地址。实际操作下，由于不能确定表是否为空，因此处理头指针时往往需要按两种情况分开讨论。

​ 需要修改头指针和不需要修改头指针。使用头指针时，插入删除首结点与修改其他结点的操作不同。

​ so，为了统一处理上述情况，通常在单链表的开始结点之前附设一个类型相同的结点，称为头结点(head node)。头节点虽然增加了一点内存开销，却使得单链表的很多操作实现起来更加方便。头节点的地址保存在头指针中。

​

​

​ 下面给出C++描述的单链表模板类

template<class T>
class LinkList
{
    public:
    	LinkList(){front =new Node<T>;front->next=NULL;}//无参构造函数
    	LinkList(T a[],int n);//有参构造函数
    	~LinkList();//析构函数
    	void PrintList();
    	int GetLength();
    	Node<T> * Get(int i);//获取线性表第i个位置上的元素结点地址
    	int Locate(T x);
    	void Insert(int i,T x);//在线性表的第i个位置插入值为x的新元素
    	T Delete(int i);//删除线性表的第i个元素，并将该元素返回
    private：
        Node<T> * front;//头指针
};

​ 在单链表模板类中，结点类型Node已经在前面给出，私有成员front为头指针，用于存储头结点的地址。

单链表的基本运算

构造函数

​ 如果建立空单链表，只需要建立头结点，在单链表模板类中已经给出了无参构造函数的实现，

​ 建立单链表的方法有两种，分别为头插法和尾插法

头插法：

​ 每次插入元素都从单链表的第一个结点位置插入，先前插入的结点随着新节点的插入而不断后移，因此，若希望数组a中各个元素插入后在单链表后的次序依然为a[0],a[1],...,a[n-1]，则插入时应先插入a[n-1]，再插入a[n-2]，依次类推，最后插入a[0]。

​ 头插法的执行过程如图所示，无论是插入第一个结点还是插入第k个结点，操作都分为4个步骤，3和4不能互换

1. 在堆中建立新结点

   Node<T> * s=new Node<T>;

2. 将a[i]写入新结点的数据域：

   s->data=a[i];

3. 修改新结点的指针域

   s->next=front->next;

4. 修改头结点的指针域，将新结点加入链表中

   front->next=s;

​ 带头结点的单链表对于所有的结点的操作都是相同的，而不带头结点的单链表则需要判断。

​ 算法如下：

template<class T>
LinkList<T>::LinkList(T a[],int n)
{
    front=new Node<T>;
    front->next=NULL;
    for(int i=n-1;i>=0;i++)
    {
        Node<T> * s=new Node<T>;//建立新结点
        s->data=a[i];//将a[i]写入新结点的数据域
        s->next=front->next;//修改新结点的的指针域
        front->next=s;//修改头结点的指针域，将新结点加入到链表当中
    }
}

​ 显然，时间复杂度为O(n)

尾插法：

​ 通常尾插法需要一个指针变量保存终端结点的地址，称为尾指针，设为r，每插入一个新结点后，r指向新插入的终端结点。

​ 步骤如下

1. 在堆中建立新结点；

   Node<T> *s=new Node<T>;

2. 将a[i]写入新结点的数据域；

   s->data=a[i];

3. 将新结点加入链表中；

   r->next=s;

4. 修改尾指针；

   r=s;

​ 需要注意的是，全部结点插入后，需要将终端结点的指针域设为空。

​ 算法如下：

template<class T>
LinkList<T>::LinkList(T a[],int n)//尾插法建立链表
{
    front = new Node <T>;
    Node <T> *r =front;
    for(int i=0;i<n;i++)
    {
        Node <T> *s =new Node <T>;
        s->data=a[i];
        r->next=s;
        r=s;
    }
    r->next=NULL;
}

​ 显然算法的时间复杂度为O(n)

析构函数

​ 各个结点都是采用操作符new动态申请的，因此在单链表对象生命周期结束时，需要将这些结点释放。

template<class T>
LinkList<T>::~LinkList()
{
    Node <T> * p=front;//初始化工作指针p
    while(p)//要释放的结点存在
    {
        front=p;//暂存要释放的结点
        p=p->next;//移动工作指针
        delete front;//释放结点
    }
}

​ 若链表长度为n，则包括头结点在内需要进行n+1次循环释放结点空间，所以析构函数的时间复杂度为O(n);

查找算法

按位查找

​ 链表是一种顺序存储结构，只能从链表的表头出发，顺着每个结点的指针域往后依次访问每个结点。

​ 设单链表的长度为n，要查找表中的第i个元素，则i应满足\(1\leq i\leq n\)。设工作指针为p，当开始查找时，p指向第一个结点，用整型变量j作计数器，初始时j=1。p每指向下一个结点，j进行加1操作，直到j等于i，此时p的结点（有时简称p结点）就是要找的结点；或者j不等于i但p已经为空，此时说明i是不合法的，算法可抛出异常或返回错误标识。在实现时，可直接返回p，因为若p为空，说明第i个元素不存在，返回空地址；否则，p指向的元素就是要找到，返回元素地址。

伪代码

[1]初始化工作指针p和计数器j，p指向第一个结点，j=1；

[2]循环以下操作；

​ [2.1]p指向下一个结点；

​ [2.2]j+1；

[3]返回p

实现代码

template<class T>
Node <T> * LinkList<T>::Get(int i)//获取线性表第i个位置的元素
{
    Node <T> *p=front->next;
    int j=1;
    while(p&&j!=i)
    {
        p=p—>next;
        j++;
    }
    return p;
}

​ 算法中p=p->next；是其中一条基本语句，该语句的执行次数玉被查找结点在单链表中的位置有关。在查找超过的情况下，查找位置i满足\(1\leq i \leq n\)，则基本语句的执行次数为i-1，假定查找每个结点的概率相同(p_i=1/n)，则查找成功的平均时间复杂度为 \[ T(n)=\sum_{i=1}^np_i\times (i-1)=\frac1n \sum_{i=1}^n(i-1)=\frac{n-1}{2}=O(n) \] ​ 查找不成功的时间复杂度为O(n);

按值查找

​ 按值查找是在单链表中查找给定值的结点，找到后返回元素地址或序号。

​ 返回序号：

template<class T>
int LinkList<T>::Locate(T x)
{
    Node <T> *p=front->next;
    int j=1;
    while(p)
    {
        if(p->data==x)return j;
        p=p->next;
        j++;
    }
    return -1;
}

​ 返回元素地址：

template<class T>
Node <T> * LinkList<T>::Locate(T x)
{
    Node <T> *p=front->next;
    int j=1;
    while(p)
    {
        if(p->data==x)return p;
        p=p->next;
        j++;
    }
    return -1;
}

插入操作

​ 在链表的第i个位置插入值为x的元素，共分为两步：

1. 查找到位置为i-1的元素
2. 在该元素后插入新元素

​ 算法实现：

template<class T>
void LinkList<T>::Insert(int i,T x)
{
    Node <T> *p=front;
    if(i!=1)p=Get(i-1);
    if(p)
    {
        Node <T> *s=new Node<T>;
        s->data=x;
        s->next=p->next;
        p->next=s;
    }
    else throw"插入位置错误";
}

​ 平均时间复杂度与按位查找的时间复杂度相同为O(n);

​ 还有一类插入操作是在给定元素的前或后进行插入。

​ 如果插入位置的前一个元素的地址已知，设为p，则只需要在p所指元素后插入一个新结点，时间复杂度为O(1)，这种操作称为后插操作。

​ 如果p指向待插入的元素，则新元素实际插入p所指元素的前一个元素，这种操作称为前插。

​ 如果为了找到p所指结点的前一个结点，需要从第一个元素开始遍历，时间复杂度为O(n)，实际可以改造算法，使其时间复杂度为O(1)

​ 改进方法的思想是：在p结点后插入新结点，让新结点的数据域存储原来p结点的数据域，而p结点的数据域存储新插入的值。

template<class T>
void LinkList<T>::Insertup(T *p,T x)
{
    Node<T> *s=new Node<T>;
    s->data=p->data;
    s->next=p->next;
    p->next=s;
    p->data=x;
}

删除操作

​ 操作过程可分为5个步骤：

1. 从第一个结点开始，查找第i-1个结点，设为p指向该结点；
2. 设q指向第i个元素；
3. 摘链，即将q元素从链表中摘除；
4. 保存q元素的数据；
5. 释放q元素；

​

​ 下面给出代码实现:

template<class T>
T LinkList<T>::Delete(int i)
{
    Node<T> *p=front;
    if(i!=1)p=Get(i-1);//若不是在第一个位置删除，得到第i-1个个元素的地址
    Node<T> *q=p->next;
    p-next=q->next;
    T x=q->data;
    delete q;
    return x;
}

​ 如果要删除单链表中p所指的某个结点：

template<class T>
T LinkList<T>::Delete(T *p)
{
    T x=p->data;
    Node<T> *q=p->next;
    p->data=q->data;
    p->next=q->next;
    delete q;
}

单链表的应用——通信录

​ 下面给出实现代码

​ LinkList.h

template<class T>
struct Node
{
    T data;
    struct Node<T> *next;
};
template<class T>
class LinkList
{
    private:
        Node<T> *front;
        int length;

    public:
        LinkList() { front = new Node<T>;
            front->next = NULL;
            length = 0;
        }
        LinkList(T a[], int n);
        ~LinkList();
        void PrintList();
        void GetLength();
        Node<T> * Get(int i);
        int Locate(T x);
        void Insert(int i, T x);
        void Insertbh(Node<T> *p,T x);
        T Delete(int i);
};
//前插法
/*
template<class T>
LinkList<T>::LinkList(T a[],int n)
{
    front = new Node<T>;
    front->next = NULL;
    for (int i = n - 1; i >= 0;i--)
    {
         Node<T> *s = new Node<T>;
         s->data = a[i];
         s->next = front->next;
         fornt->next = s;
    }
    length=n;
};
*/
// 尾插法
template <class T>
LinkList<T>::LinkList(T a[], int n)
{
    front = new Node<T>;
    front->next = NULL;
    Node<T> *r = front;
    for (int i = 0; i <n;i++)
    {
        Node<T> *s = new Node<T>;
        s->data = a[i];
        r->next = s;
        r = s;
    }
    r->next = NULL;
    length = n;
};
template <class T>
LinkList<T>::~LinkList()
{
    Node<T> *p = front;
    while(p)
    {
        front = p;
        p = p->next;
        delete front;
    }
};
template <class T>
void LinkList<T>::PrintList()
{
    Node<T> *p = front->next;
    while(p)
    {
        p->data.print();
        p = p->next;
    }
    std::cout << std::endl;
};
template <class T>
void LinkList<T>::GetLength()
{
    std::cout << length;
};
template <class T>
Node<T> * LinkList<T>::Get(int i)
{
    Node<T> *p = front->next;
    int j = 1;
    while(p&&j!=i)
    {
        p = p->next;
        j++;
    }
    return p;
};
template <class T>
int LinkList<T>::Locate(T x)
{
    Node<T> *p = front->next;
    int j = 1;
    while(p)
    {
        if(p->data==x)
            return j;
        p = p->next;
        j++;
    }
    return -1;
};
//插入操作
template <class T>
void LinkList<T>::Insert(int i, T x)
{
    Node<T> *p = front;
    if (i != 1)
        p = Get(i-1);
    if(p)
    {
        Node<T> *s = new Node<T>;
        s->data = x;
        s->next = p->next;
        p->next = s;
        length++;
    } 
    else
        std::cout << "wrong";
};
//前插操作
template <class T>
void LinkList<T>::Insertbh(Node<T> *p,T x)
{
    Node<T> *s = new Node<T>;
    s->data = p->data;
    s->naxt = p->next;
    p->next = s;
    p->data = x;
};
template <class T>
T LinkList<T>::Delete(int i)
{
    Node<T> *p = front;
    if(i!=1)
        p = Get(i - 1);
    Node<T> *q = p->next;
    T x = q->data;
    p->next = q->next;
    delete q;
    return x;
};
// 删除单链表中p所指的某个结点
/*
template <class T>
T LinkList<T>::Delete(T *p)
{
    T x=p->data;
    Node<T> *q=p->next;
    p->data=q->data;
    p->next=q->next;
    delete q;
};
*/

PHONEBOOK.h

#include <iostream>
class PHONEBOOK
{
private:
    int m_ID;
    std::string m_name;

public:
    PHONEBOOK() {}
    PHONEBOOK(int id, std::string name)
    {
        m_ID = id;
        m_name = name;
    }
    void print()
    {
        std::cout << m_ID << '\t' << m_name << std::endl;
    }
    bool operator==(PHONEBOOK &p)
    {
        if (p.m_ID == m_ID)
            return true;
        return false;
    }
};

​ 主程序

#include <iostream>
#include "PHONEBOOK.h"
#include "LinkList.h"
using namespace std;
int main()
{
    PHONEBOOK pbook[2] = {{20181208, "Mary"}, {20181127, "Tom"}};
    PHONEBOOK record(20181209, "Phoenix");
    LinkList<PHONEBOOK> list(pbook, 2);
    list.PrintList();
    list.Insert(1, record);
    list.PrintList();
    PHONEBOOK x = list.Delete(3);
    x.print();
    cout << endl;
    list.PrintList();
    int p = list.Locate(record);
    cout << p << endl;
}

循环链表的实现

​ 循环链表即链表首尾相接的链表

​

​ 带尾指针的单循环链表相对于单链表，只是改用指向终端结点的尾指针，并且尾结点的指针域指向头结点；

• 头指针的表示：单链表使用front标识头指针，单循环链表使用rear->next标识头指针；
• 判断p指向的某结点是否为尾结点的方法：单链表中若p->next=NULL，单循环链表中p==rear；

​ 带尾结点的单循环链表的C++语言描述(还能实现带头结点的单循环链表，在此不做展开)

​ CLinkList.h

template <class T>
struct Node
{
    T data;
    struct Node<T> *next;
};
template <class T>
class CLinkList
{
private:
    Node<T> *rear;
    int length;

public:
    CLinkList()
    {
        rear = new Node<T>;
        rear->next = rear;
        length = 0;
    }
    CLinkList(T a[], int n);
    ~CLinkList();
    void PrintList();
    void GetLength();
    Node<T> *Get(int i);
    int Locate(T x);
    void Insert(int i, T x);
    void Insertbh(Node<T> *p, T x);
    T Delete(int i);
};
// 头插法
/*
template <class T>
CLinkList<T>::CLinkList(T a[], int n)
{
    rear = new Node<T>;
    rear->next = rear;
    for (int i = n - 1; i >= 0; i++)
    {
        Node<T> *s = new Node<T>;
        s->data = a[i];
        s->next = rear->next;
        rear->next = s;
    }
    length = n;
};
*/
// 尾插法
template <class T>
CLinkList<T>::CLinkList(T a[], int n)
{
    rear = new Node<T>;
    rear->next = rear;
    for (int i = 0; i < n; i++)
    {
        Node<T> *s = new Node<T>;
        rear->data = a[i];
        s->next = rear->next;
        rear->next = s;
        rear = s;
    }
    length = n;
};
template <class T>
CLinkList<T>::~CLinkList()
{
    Node<T> *p = rear->next;
    while (p!=rear)
    {
        rear->next = p;
        p = p->next;
        delete rear->next;
    }
}
template <class T>
void CLinkList<T>::PrintList()
{
    Node<T> *p = rear->next;
    while (p != rear)
    {
        p->data.print();
        p = p->next;
    }
    std::cout << std::endl;
}
template <class T>
void CLinkList<T>::GetLength()
{
    std::cout << length;
};
template <class T>
Node<T> *CLinkList<T>::Get(int i)
{
    Node<T> *p = rear->next;
    int j = 1;
    while (p == rear && j != i)
    {
        p = p->next;
        j++;
    }
    return p;
};
template <class T>
int CLinkList<T>::Locate(T x)
{
    Node<T> *p = rear->next;
    int j = 1;
    while (p != rear)
    {
        if (p->data == x)
            return j;
        p = p->next;
        j++;
    }
    return -1;
};
// 插入操作
template <class T>
void CLinkList<T>::Insert(int i, T x)
{
    Node<T> *p = rear;
    if (i != 1)
        p = Get(i - 1);
    if (p != rear->next)
    {
        Node<T> *s = new Node<T>;
        s->data = x;
        s->next = p->next;
        p->next = s;
    }
    else
        std::cout << "wrong";
};
// 前插操作
template <class T>
void CLinkList<T>::Insertbh(Node<T> *p, T x)
{
    Node<T> *s = new Node<T>;
    s->data = p->data;
    s->naxt = p->next;
    p->next = s;
    p->data = x;
};
template <class T>
T CLinkList<T>::Delete(int i)
{
    Node<T> *p = rear->next;
    if (i != 1)
        p = Get(i - 1);
    Node<T> *q = p->next;
    T x = q->data;
    p->next = q->next;
    delete q;
    return x;
};
// 删除单链表中p所指的某个结点
/*
template <class T>
T LinkList<T>::Delete(T *p)
{
    T x=p->data;
    Node<T> *q=p->next;
    p->data=q->data;
    p->next=q->next;
    delete q;
};
*/

​ PHONEBOOK.h

#include <iostream>
class PHONEBOOK
{
private:
    int m_ID;
    std::string m_name;

public:
    PHONEBOOK() {}
    PHONEBOOK(int id, std::string name)
    {
        m_ID = id;
        m_name = name;
    }
    void print()
    {
        std::cout << m_ID << '\t' << m_name << std::endl;
    }
    bool operator==(PHONEBOOK &p)
    {
        if (p.m_ID == m_ID)
            return true;
        return false;
    }
};

​ main.cpp

#include <iostream>
#include "PHONEBOOK.h"
#include "LinkList.h"
using namespace std;
int main()
{
    PHONEBOOK pbook[2] = {{20181208, "Mary"}, {20181127, "Tom"}};
    PHONEBOOK record(20181209, "Phoenix");
    LinkList<PHONEBOOK> list(pbook, 2);
    list.PrintList();
    list.Insert(1, record);
    list.PrintList();
    PHONEBOOK x = list.Delete(3);
    x.print();
    cout << endl;
    list.PrintList();
    int p = list.Locate(record);
    cout << p << endl;
}

实现链表的链接

​ 对于只带有头结点的单链表，需要遍历找到链表的尾结点，再进行链表的链接

​ 而对于带有尾结点的循环链表，只需要链接即可，故时间复杂度为O(1)

​

​ 教材中给出的为带头结点的单循环链表的链接实现代码。

​ 下面给出带尾结点单循环链表链接的实现代码

template<class T>
void CLinkList<T>::Connect(CLinkList<T> &b)//b为链接的链表
{
    Node<T> *q=b.rear->next;//保存b链表的表头
    b.rear->next=rear->next;//b链表的表尾指向当前链表的表头
    rear->next=q->next;//当前链表的表尾指向b链表的起始元素
    rear->data=q->data;
    rear=b.rear;
    delete q;
}

双链表

​ 有一个直接前驱结点和一个直接后继结点，表中有两条方向相反的链

​ 双链表的实现：

STL中的双链表——list

​ list容器使用不连续的空间区域，允许向前或向后遍历元素，但是不支持随机访问，查找某个元素时往往需要遍历相邻的若干元素，优点在于任何位置都可以高效地插入或删除，并不需要移动其他元素。

​

树

​ 非线性，结点之间有分支，并具有层次关系。

​