第二章线性表

graph TD; 线性表-->顺序存储; 线性表-->链式存储; 链式存储-->单链表; 链式存储-->双链表; 链式存储-->循环链表; 链式存储-->静态链表; 单链表-->指针实现; 双链表-->指针实现; 循环链表-->指针实现;

线性表是算法题命题的重点。实现容易代码量少，但是同时也要求有最优的性能（时间复杂度和空间复杂度），才能拿满分。
考试中不要求代码有实际的可执行性，只要表达出算法的思想即可，不要死抠语法细节。
在考场上实在想不出来最优解可以采用暴力解也能拿至少一半分数。

线性表的类型定义

线性结构特点：

存在唯一的一个被称作“第一个”的数据元素；
除第一个之外，集合中的每一个数据元素都只有一个前驱；
除了最后一个之外，集合中的每个数据元素都只有一个后继。

线性表是最常用且最简单的一种数据结构。
线性表是有n个数据元素的有限序列，这里的数据元素可以是简单的int型整数，也可以是一个结构体，由若干个数据项组成，比如说链表，含有数据域以及指针域。
在这种情况下，数据元素可以叫做记录，含有大量记录的线性表叫做文件。
线性表特点

元素个数有限
表中元素具有先后次序
元素数据类型都相同
元素具有抽象性，仅讨论元素间的逻辑关系，不考虑元素究竟表示什么内容

线性表的顺序表示和实现

顺序表定义

线性表的顺序存储又称顺序表，它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得在逻辑上相邻的两个元素在物理上也相邻。
顺序表的特点就是表中元素的逻辑顺序和物理顺序相同。
位序：数组下标加一，即表示实际第几个元素（从一开始计数）
线性表顺序存储实现

静态分配（长度不可变）

#define MaxSize 50
typedef struct{
  Elemtype data[MaxSize];	//顺序表元素
  int length;
}Sqlist;										//把struct换个名字

动态分配（长度可以变）

#define InitSize 50
typedef struct{
  Elemtype *data;
  int length, MaxSize;	//length：当前元素个数，MaxSize：数组最大长度（随着需要可以改变）
}Sqlist;
L.data=(Elemtype*)malloc(sizeof(Elemtype));//C语言分配内存空间
L.data=new Elemtype[InitSize];

注意C语言调用malloc函数要包含 #include<stdlib.h>

顺序表特点

最大特点是随机访问
存储密度高
插入删除要移动大量元素

顺序表基本操作实现

插入操作

bool ListInsert(Sqlist &L, int i, Elemtype e){
  if(i<1||i>L.length+1)return false;
  if(L.length>=MaxSize)return false;
  /*注意这里判断插入位置i可以到length+1因为可以在这个位置插入（位序）
  	而下面的移动元素数组的下标最多到length，此时数组里最后一个元素的下标是length-1
  	因为要往后移动元素，所以要用到第length个数组位置
  */
  for(int j=L.length;j>=i;j++){
    L.data[j]=L.data[j-1];//从第i个元素开始往后移动，这样数组里面L.data[i-1]就会空出来
  }
  L.data[i-1]=e;
  L.length++;
  return true;
}

考虑时间复杂度为 $O(N)$。注意计算移动节点的平均次数。

删除操作

bool ListInsert(Sqlist &L, int i, Elemtype &e){
  if(i<1||i>L.length)return false;
  e=L.data[i-1];
  for(int j=i-1;j<L.length-1;j++){
    L.data[j]=L.data[j+1];//将第i个元素之后的元素前移
  }
  L.length--;
  return true;
}

时间复杂度为$O(N)$，注意计算移动节点的平均次数。

按值查找

int LocateElem(Sqlist L, Elemtype e){
	for(int i=0;i<L.length;i++){
		if(L.data[i]==e)return i+1;
	}
	return 0;
}

时间复杂度为$O(N)$，注意查找的平均比较次数。

线性表的链式表示和实现

显然，顺序表在插入删除方面有不可避免的缺点，所以链式存储应运而生，解决这个问题，但也失去了顺序存储的随机访问的优点。

线性表的链式存储也叫链表。

单链表的定义

typedef struct LNode{
  Elemtype data;
  struct LNode *next;
}LNode, *LinkList;
/*
	*LinkList -> LNode*
	LinkList L;
	LNode* L;
*/

注意这里的重命名，我们声明了一个叫做LNode的结构体，然后我们给他换个名字叫LNode，以及声明一个它的指针类型。

头指针与头结点

头指针：指向链表第一个结点的指针，跟有没有头结点没有关系
头结点：有些定义为了方便操作，在第一个结点之前定义了一个叫做头结点的东西，该节点的指针指向第一个结点，头结点的数据域可以不存储东西，也可以存储比如说链表长度之类的东西

头结点的好处

第一个节点不用特殊处理（因为第一个节点跟其他节点一样，他的位置存放在上一个节点的next指针里，如果不使用头结点，那么第一个节点就要特殊处理，做题的时候注意审题），比如说在第一个结点前插入新节点或者说删除第一个结点我们都需要更改头指针的指向，非常麻烦。
非空表和空表的处理得到统一（因为无论是不是空表，头指针都是非空的），比如说一个不带头结点的空链表要插入一个结点，不带头结点的链表在第一个位置插入新节点，虽然都是在同一个位置插入，但是操作是不一样的，非常麻烦，容易出bug
总的来说就是没有头结点的时候，对于第一个结点的操作跟其他节点都是不一样的，每个操作都要考虑特殊情况，有头结点就没这么多鸟事

头插法建立单链表

带头结点

LinkList List_HeadInsert(LinkList &L){
  LNode *s;
  int x;
  L=(LinkList)malloc(sizeof(LNode));	//创建头结点
  L->next=NULL;
  scanf("%d", &x);
  while(x!=9999){	//这里设置的终止条件是输入9999
    s=(LNode*)malloc(sizeof(LNode));
    s->data=x;
    s->next=L->next;	//两步指针插入
    L->next=s;
    scanf("%d", &x);
  }
  return L;
}

不带头结点

LinkList List_HeadInsert(LinkList &L){
  LNode *s;
  int x;
  scanf("%d", &x);
  while(x!=9999){	//这里设置的终止条件是输入9999
    s=(LNode*)malloc(sizeof(LNode));
    s->data=x;
    s->next=L;	//两步指针插入
    L=s;
    scanf("%d", &x);
  }
  return L;
}

不需要创建头结点以及插入的时候先指向头指针所指向的节点（第一个结点），然后再将头指针指向新节点。

需要注意的是，头插法输入数据的顺序跟在链表中的顺序是相反的，可以用来将元素逆序。

尾插法

带头结点

LinkList List_TailInsert(LinkList &L){
  int x;
  L=(LinkList)malloc(sizeof(LNode));	//创建头结点
  LNode *s, *r=L;	//r为表尾指针
  scanf("%d", &x);
  while(x!=9999){	//这里设置的终止条件是输入9999
    s=(LNode*)malloc(sizeof(LNode));
    s->data=x;
    r->next=s;	//两步指针插入
    r=s;
    scanf("%d", &x);
  }
  r->next=NULL;
  return L;
}

不带头结点

思考

按位查找
按值查找
插入结点
删除结点
求表长

双链表

单链表有个缺点就是要找一个结点的前驱非常麻烦，要从头遍历，所以有了双链表，在结构体的指针域中增加一个指向前一个结点的指针，注意头结点的前驱指针指向空。

插入
删除

循环链表

循环单链表

与单链表唯一的不同就是尾结点的next指针指向了头结点，变成了一个环。

第二章 线性表