第2章线性表

2.1 线性表的定义和基本操作

2.1.1 线性表的定义

线性表占据数据结构三元素其中之二（逻辑结构、数据的运算），所以算是抽象数据类型ADT（Abstract Data Type)，而不算一个完整的数据结构。

存储结构不同，运算的实现方式不同（在物理上用不同的方式来实现运算）

线性表定义：

具有相同数据类型的n（n ≥ 0）个数据元素的有限序列，其中n为表长，当n = 0 时线性表是一个空表。若用L命名线性表，则其一般表示为 L = (a₁ , a₂ , a_i , a_i+1 , … , a_n)

tips:

相同：代表每个数据元素所占空间一样大；

有限：代表线性表内数据元素的个数是有限的（有具体个数的）

序列：代表数据元素是有次序，按照某一规则排序（例如按从大到小或从小到大排序）

线性表的几个概念：

a_i 是线性表中的 “第i个” 元素线性表中的位序

（当我们用数组存数据元素，这时数组下标是从0开始的，而位序是从1开始的，一定要注意这点，在取值时下标不要搞错了）

a₁ 是表头元素；a_n 是表尾元素

除第一个元素外，每个元素都有且仅有一个直接前驱；除了最后一个元素外，每个元素有且仅有一个直接后继

2.1.2 线性表的基本操作

线性表的基本操作：

概括为：新建、销毁，增删查改

新建表：InitList(&L) ------> 初始化操作，构造一个空的线性表L，分配内存空间

销毁表：DestroyList(&L) ------> 销毁操作，销毁线性表，并释放 线性表L所占用的内存空间

插入：ListInsert(&L, i, e) ------> 插入操作，在表L中的第i个位置上插入指定元素e

删除：ListDelete(&L, i, &e) ------> 删除操作，删除表中的第i个位置的元素，并用e返回删除元素的值

查找有两种：

按值查找： LocateElem(L, e) ------> 在表L中查找具有给定关键字值的元素

按位查找： GetElem(L, i) ------> 获取表L中第i个位置的元素的值

改：就是先查找到元素，再进行上述插入或删除的操作

其他常用操作：

Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数

PrintList(L)：输出表。按前后顺序输出线性表L的所有元素值。

Empty(L)：判空操作。若线性表L为空表，则返回true，否则返回false。

引用&：C++语言符号，在传参时直接把被调函数中的运算结果带回，而不需要像C语言一样传地址，再解引用带回被调函数运算结果，举例如下：

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
void test(int &a)  //c语言：void test(int* a)
{
	a = 10;       //c语言：*a = 10;
    printf("被调函数内 a = %d\n", a);
}

int main()
{
	int a = 5;
    printf("调用test函数前 a = %d\n", a);
	test(a);    //c语言：test(&a);
	printf("调用test函数后 a = %d\n", a);
	return 0;
}

本小节思维导图：

2.2 线性表的顺序表示

2.2.1 顺序表的定义

顺序表（是一个完整的数据结构） ------> 线性表(逻辑结构) + 顺序存储(存储结构) +运算：用顺序存储的方式实现 线性表顺序存储。即把逻辑上相邻的数据元素存储再物理位置上也相邻的存储单元上，元素之间的关系有存储单元的邻接关系来体现。

ps：由于顺序表每一个元素类型相同，占据存储空间相等，且在物理上连续，所以能推导出每一个元素的地址

例如：顺序表K的首地址为Loc_first，用sizeof（ElemType)算得一个元素所占空间大小，则第二个元素的地址为 Loc_first + sizeof(ElemType)，依此类推第n个元素的地址为 Loc_first + (n - 1)*sizeof(ElemType)

顺序表的实现：一维数组可以静态分配，也可以动态分配（都是连续的空间）

静态分配

所谓静态分配就是一旦定义，就不能改变定义时所规定的长度和大小。例如，使用数组来建顺序表，这个数组的大小和长度一旦确定，在空间已占满，还要插入新数据时，就会出现溢出错误。

动态分配

#define InitSize 10      //顺序表的初始长度
typedef struct{
    ElemType *data;      //指向动态分配数组的指针
    int MaxSize;		//顺序表最大容量
    int length;			//顺序表的当前长度
}SqList;				//动态分配数组顺序表的类型定义

malloc与free函数：malloc用来动态申请内存空间，free用来释放内存空间

L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);
//malloc返回一个空类型指针，为了匹配定义的数据类型，要进行强制转换，转成对应数据类型的指针

具体实现代码：

#include<stdib.h>
#include<iostream>
#define InitSize 10     //默认最大长度
typedef struct{
  int *data;           //指示动态分配数组的指针
  int MaxSize;         //顺序表最大容量
  int length;          //顺序表当前长度
}SeqList;

void InitList(SeqList &L){
  //用malloc申请一片连续的存储空间
  L.data = (int*)malloc(InitSize * sizeof(int));
  L.MaxSize = InitSize;
  L.length  = 0;
}

//增加动态数组的长度
void IncreaseSize(SeqList &L, int len)
{
  int *p = L.data;
  L.data = (int*)malloc((L.MaxSize+len) * sizeof(int));
  for(int i = 0; i < L.length; i++)
  {
    L.data[i] = p[i];
  }
  L.MaxSize = L.MaxSize + len;
  free(p);
}

int main()
{
    SeqList L;
    InitList(L);
    //... 往顺序表中随便插入几个元素
    IncreaseSize(L,5);
    return 0;
}

顺序表的特点：
1. 随机访问，即可以在O(1)时间内找到第i个元素。
2. 存储密度高，每个节点只存储数据元素(不像链式存储还要存储指针)
3. 拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）
4. 插入、删除操作不方便，需要移动大量元素

本小节思维导图：

2.2.2 顺序表上基本操作的实现`用存储位置的相邻来体现数据元素之间的逻辑关系`

插入

在逻辑结构上，数据元素“有头有尾”依次按序排列，当我们要在原本的序列中插入一个新的元素时，只需将要插入的第i个位置 (位序）及其后续的位置上的元素一起往后移一位，新数据元素就被插入到了第i个位置。

代码实现：(以静态分配实现，动态分配同理)

#define MaxSize 10    		//定义最大长度
typedef  struct
{
    int data[MaxSize];   	//用“静态数组”存放数据元素
    int length;				//顺序表的当前长度
}SqList;					//顺序表的类型定义

void ListInsert(SqList &L, int i, int e)   //将第i个元素及之后的元素后移
{
    for(int j = L.length; j >= i, j--)    //从数组内元素最后一个开始依次往后移一位
    	L.data[j] = L.data[j - 1];
    L.data[i - 1] = e;					 //在位置i处放入e（此时数组下标为i-1）
    L.length++;							 //长度加1
}

int main()
{
    SqList L;					//声明一个顺序表
    InitList L;					//初始顺序表
    // ...此处省略插入元素的代码
    InitInsert(L, 3, 3);       //在顺序表L的第3个位置插入数据元素3
    return 0;
}

要考虑代码的健壮性：在输入有误时，要有一个反馈

针对上述代码改进：

bool ListInsert(SqList &L, int i, int e)   //将第i个元素及之后的元素后移
{
    if(i < 1 && i > L.length + 1)          //判断i是否有效
    	return false;
    if(L.length >= MaxSize)               //当前存储已满，不能插入。关注这里的大于号，看下图
        return false;
    for(int j = L.length; j >= i, j--)    //从数组内元素最后一个开始依次往后移一位
    	L.data[j] = L.data[j - 1];
    L.data[i - 1] = e;					 //在位置i处放入e（此时数组下标为i-1）
    L.length++;							 //长度加1
	return ture;
}

if(L.length >= MaxSize) //关注这里的大于号，看下图

插入操作的时间复杂度（问题规模n = L.length 表长）

bool ListInsert(SqList &L, int i, int e)   //将第i个元素及之后的元素后移
{
    if(i < 1 && i > L.length + 1)          //判断i是否有效
    	return false;
    if(L.length >= MaxSize)               //当前存储已满，不能插入。关注这里的大于号，看下图
        return false;
    for(int j = L.length; j >= i, j--)    //从数组内元素最后一个开始依次往后移一位
    	L.data[j] = L.data[j - 1];
    L.data[i - 1] = e;					 //在位置i处放入e（此时数组下标为i-1）
    L.length++;							 //长度加1
	return ture;
}

L.data[j] = L.data[j - 1];      //关注这句代码运行的次数来求时间复杂度

有三种时间复杂度：

最好时间复杂度：当要插入元素插入位置恰好是表尾时，其他元素不需要移动位置，i = n + 1，循环0次，此时时间复杂度是O(1)。
最坏时间复杂度：当要插入元素插入位置恰好是表头时，表内原有的所有元素都要向后移一位， i = i，循环n次，此时时间复杂度是O(n)。
平均时间复杂度：假设新元素插入到任何一个位置的概率相同，即 i = 1, 2, 3, … , length + 1 的概率都是 p = $\frac{1}{n+1}$ ，

当 i = 1时，循环n次；当 i = 2时，循环n - 1次；当 i = 3时，循环n - 2次 … 当 i = n + 1时，循环0次。

平均循环次数 = np + (n -1)p +(n -2)p + … + 1·p = $\frac{n(n+1)}{2}$ $\frac{1}{n+1}$ = $\frac{n}{2}$ ，平均时间复杂度 = O( $\frac{n}{2}$ )，化简得O(n)。

删除

同理，插入时是插入的指定位置及指定位置之后的原有元素向后移一位，删除时是删除指定位置的原有元素并使指定位置位置之后的原有元素向前移一位，length的值减1。

代码实现：

bool ListDelete(SqList &L, int i, int &e)
{
    if(i < 1 || i > L.length)
        return false;
    e = L.data[i - 1];
    for(int j = i; j < L.length; j++)     //这里的判断条件没有取等于号是因为，删除的如果是最后一个元素，那么
    {									  //就不用使删除元素后的原有元素向前移一位。会造成将数组外的数据添加
        L.data[j - 1] = L.data[j];		  //到数组最后一位（应该算数据溢出吧？）
    }
    L.length--;
    return true;
}

int main()
{
    SqList(L);
    InitList(L);
    //...此处省略一些代码，插入几个元素
    int e = -1;
    if(ListDelete(L, 3, e))
        printf("已删除第3个元素，删除元素的值为=%d\n", e);
    else
        printf("位序i不合法，删除失败\n");
    return 0;
}

总结：在for循环内，当插入时，把元素依次往后移一位，是先移动后面的元素再移动前面的元素；当删除时，把元素依次往前移一位，是先移动前面的元素再移动后面的元素

删除操作的时间复杂度

有三种时间复杂度：
1. 最好时间复杂度：删除表尾元素，不需要移动其他元素，i = n，循环0次；此时时间复杂度为O(1)。
2. 最坏时间复杂度：删除表头元素，需要将后续的n - 1个元素全部向前移动，i = 1，循环n - 1次；此时时间复杂度为O(n)。
3. 平均时间复杂度：假设删除任何一个元素的概率相同，即1，2，3，…，length的概率都是p = $\frac{1}{n}$ 。i = 1，循环n - 1次；i = 2，循环n -2次；… i = n，循环0次，平均循环次数 = (n -1)p + (n-2)p +…+ 1·p = $\frac{n(n -1)}{2}$ $\frac{1}{n}$ = $\frac{n-1}{2}$ 。

本小节思维导图：

顺序表的查找

按位查找

GetElem(L, i)：获取表L中第i个位置的元素的值。

#define MaxSize 10
typedef struct
{
    ElemType data[MaxSize];					//静态分配
    int length;
}SqList;

ElemType GetElem(Sqlist L, int i)
{
    if(i < 1 || i > L.length)
        printf("位序有误，请重新输入\n");
    else
        return L.data[i - 1];
}

按位查找时间复杂度
ElemType GetElem(Sqlist L, int i)
{
return L.data[i - 1]; //无循环，无递归调用
}
时间复杂度为O(1)。

特性：随机存取----> 由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素的大小立即找到第 i 个元素。

按值查找

LocateElem(L, e)：在表L中查找具有给定关键字值的元素。

代码实现：

#define MaxSize 10
typedef struct
{
	ElemType *data;
    int MaxSize;
    int length;
}SeqList;

//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SeqList L, ElemType e)
{
    for(int i = 0; i < L.length; i++)
        if(L.data[i] == e)
            return i + 1;     //数组下标为i的元素值等于e, 返回其位序i+1
    return 0;				  //退出循环，说明查找失败
}

==：当两个结构体比较是否相等时，要比较结构体内各分量是否相等（例如：L.num == K.num)。

按值查找的时间复杂度

最好时间复杂度：目标元素在表头时，循环1次，为O(1)。

最坏时间复杂度：目标元素在表尾时，循环n次，为O(n)。

平均时间复杂度：假设目标元素在表内任意位置的概率相等为p = $\frac{1}{n}$ ，目标元素在第1位，循环1次；在第2位，循环两次；…；在第n位，循环n次；所以平均时间复杂度 = 1·p + 2·p + 3·p + 4·p + … + np = $\frac{n(n+1)}{2}$ $\frac{1}{n}$ =O( $\frac{n+1}{2}$ )，化简得O(n)。

本小节思维导图：

2.3 线性表的链式表示

2.3.1 单链表的定义

线性表的链式存储实现方式之一又称单链表。
单链表为了建立数据元素之间的线性关系，每个结点除了存放数据元素外，还要存储指向下一个结点的指针（单链表结点内只包含一个指针）
单链表在查找目标元素时，需要从头至尾依次遍历直到找到目标元素（为什么要依次遍历而不是直接存取？因为单链表只有知道指向目标元素的指针才能找到目标元素，所以无法查找任意位序的元素，只能从头至尾遍历，像玩游戏一样，打通一关才能到下一关）

顺序表和单链表的优劣对比
用代码定义一个单链表

struct LNode{						//定义单链表结点类型，LNode是结点
	ElemType data;				//每个结点存放一个数据元素，data是数据域
	struct LNode *next;			//指针指向下一个结点，*next是指针域
};

struct LNode *p = (struct LNode *)malloc(sizeof(struct LNode));  //增加一个新的结点：在内存中用malloc申请一个结点所需的空间
											                           //并用指针p指向这个结点

typedef关键字——数据类型重命名
typedef <数据类型> <别名>
例如：typedef int zhengxing，就是将整型变量int重新命名为zhengxing，如果定义一个整型变量就可以用“zhengxing a；”这行代码代替。

注意：写代码要在见名知义的前提下，对命名所代表的东西有所强调，强调指代对象。

初始化单链表

不带头结点的单链表

typedef struct LNode{			//定义单链表结点类型
	ElemType data;				//每个结点存放一个数据元素
	struct LNode *next;			//指针指向下一个结点
}LNode, *LinkList;

//初始化一个空的单链表
bool InitList(LinkList &L){			//这里的“&”不是c的取地址，而是c++的引用
	L = NULL;				//空表，暂时还没有任何结点，防止脏数据
	return true;
}
/*  //判断链表是否为空
	bool Empty(LinkList L){
		if(L == NULL)
			return turn;
		else
			return false;
	}
或者：bool Empty(LinkList L){
		 return(L == NULL);
	 }
*/
void test(){
	LinkList L;  //声明一个指向单链表的指针,此处并没有创建一个结点
	//初始化一个空表
	InitList(L);
	//......后续代码......
}

带头结点的单链表

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode, *LinkList;
//初始化一个单链表（带头结点）
bool InitList(LinkList &L){
	L = (LNode *)malloc(sizeof(LNode));   //分配一个头结点
	if(L == NULL)							    //内存不足，分配失败
		return false;
	L->next = NULL;						    //头结点之后暂时还没有结点
	return true；
}
/* //判断单链表是否为空（带头结点）
	bool Empty(LinkList L){
		if(L->next == NULL)
			return true;
		else
			return false;
	}
*/

void test(){
	LinkList L;    //声明一个指向单链表的指针
	//初始化一个空表
	InitList(L);
	//.....后续代码......
}

本小节思维导图：

2.3.2 单链表上基本操作的实现

单链表的插入删除

插入

按位序插入（带头结点）

a. 思路

ListInsert(&L, i, e)：插入操作。在表L中的第i个位置（找到第i-1个结点，将新结点插入其后）上插入指定元素e。

i代表==位序==，我们假设出了一个所谓的“==第0个结点==”的==头结点==，而实际单链表存放的是后面a₁到a_n的结点，这些结点的位序编号是从1开始的，所以当我们插入结点时要保证插入位置的位序是1至n+1，即表头、表中、表尾。

b. 具体代码实现

插在表头：

==注：==如果绿色箭头与黄色箭头所指代码颠倒顺序，会造成s的next指针指向结点本身（即图中的绿色箭头指向结点本身），从而使链表断链。

插在表中：

插在表尾（假如表长为4，插入到位序5）：

插在超出表长的位置（假如表长为4，插入到位序6，此时会反馈i值非法的信息）：
按位序插入（不带头结点）：

a. 思路

不存在头结点时，在插入第一位序结点的代码实现与带头结点时不同，要让新结点指向==原第一位序==结点，再让头指针指向新的结点。（即头指针的指向发生了改变，而带头结点的链表的头指针指向是不改变的）

b. 具体代码实现

插入表头：

插入表中、表尾（即 1< i < n+2）：

指定结点的后插操作

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

//后插操作：在p结点之后插入元素e
bool InserNextNode(LNode *p, ElemType e){
    if(p==NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if(s == NULL)					//有些情况下内存可能分配失败（如内存不足）
        return false;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

对于单链表给定的一个结点来说，知道了这个结点的指针，那后续元素的地址就是可知的了，而之前的元素是不知道的。

指定结点的前插操作

当前插操作时，由于不知道给定结点前一个元素的地址，所以没办法插入。

一共有两种思路：
1. 传入头指针，然后遍历找到给定结点前一个元素，再在这个元素后面后插要插入的元素
1. 先申请一个新结点，然后将这个结点作为给定结点的后继结点插入进去，然后将给定结点所存储的信息给申请的新结点，然后将要插入的元素的信息给到给定结点（本版本申请的新结点是内容是空的，王道版本是直接在要插入元素的结点上进行操作）
  
  王道版：

删除
- 按位序删除（带头结点）
  
  listDelete(&L, i, &e): 删除操作。删除表L中第i个位置(找到第i-1个结点，将其指针指向i+1个结点，并释放第i个结点)的元素，并用e返回删除元素的值。
- 指定结点的删除
  
  极限情况：单链表当要删除的结点是最后的一个结点，只能从表头开始依次寻找p的前驱

本小节思维导图：

单链表的查找（只讨论“带头结点”的情况）
- 按位查找
  
  GetElem(L,i): 按位查找操作。获取表L中第i个位置的元素的值。
  
  注：i=0，把头结点看作是第0个结点；只要判断p返回值是否是NULL，就可以知道本次按位查找是否执行成功了；按位查找的平均时间复杂度是O(n)
  
  体会下图两种代码写法的不同：
- 按值查找
  
  LocateElem(L,e): 按值查找操作。在表L中查找具有给定关键字值的元素。
求表的长度

本小节思维导图：

单链表的建立（带头结点的情况）

尾插法

定义一个单链表并初始化：

typedef struct LNode{				//定义单链表结点类型
    ElemType data;					//每个结点存放一个数据元素
    struct LNode *next;				//指针指向的下一个结点
}LNode, *LinkList;

//初始化一个单链表（带头结点）
bool InitList(LinkList &L){
    L = (LNode *)malloc(sizeof(LNode));		//分配一个头结点
    if(L == NULL)							//内存不足，分配失败
        return false;
    L->next = NULL;							//头结点之后暂时还没有结点
    return true;
}
void test(){
    LinkList L;				//声明一个指向单链表的指针
    //初始化一个空表
    InitList(L);
    //......后续代码......
}

用这种每插入一个元素都要重新遍历到表尾再插新元素的方式时间复杂度较高：

通过设置一个表尾指针，直接在表尾插入新元素降低时间复杂度：

回忆后插操作：

王道书上的尾插法(使用表尾指针)：

头插法

思路：

具体实现：

链表的逆置（重要）：

头插法表现出来的顺序是元素输入顺序的逆序：如果给定一个链表L，让求这个链表的逆置可以用头插法解决。
1. 用一个指针按顺序扫描原来的链表取得各个元素，然后建立一个新链表用头插法将这些元素存进去就可完成链表L的逆置。
2. 可以直接依次取原链表L的各个元素，再将各个元素用头插法再插回链表L的头结点之后（这种方法不用建立新链表，原地逆置链表L）

本小节总结：

2.3.3 双链表

双链表和单链表的比较
双链表的初始化（带头结点）
双链表的插入

但是当p结点刚好是双链表的最后一个结点，p–>next–>prior = s是错误的，因为p–>next = NULL，无法再指向prior。

对于上述问题可以写更严谨的代码如下图：
双链表的删除和销毁

**红色错号解读：**但是当p结点刚好是双链表的最后一个结点，q–>next–>prior = p是错误的，因为q–>next = NULL，无法再指向prior。
双链表的遍历