线性表（linear list）
定义：
线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，其中n为表长，当n=0时线性表示一个空表。若用L来命名线性表，则其一般表示为：L=（a1,a2,a3，…,an)
例如：英文字母表就是一个线性表
注意：
a1是线性表中的“第i个”元素线性表的位序
a1是表头元素；an是表尾元素
除了第一个元素外，每一个元素有且仅有一个直接前驱；
除最后一个元素，外每个元素有且仅有一个直接后继；
位序从一开始，数组下标从零开始
同一线性表中的元素必定具有相同的特性，即属于同一数据对象，相邻数据元素间序偶关系
线性表的基本操作
- 从无到有，从有到无：
- InitList(&L):初始化表。构造一个空的线性表L，分配内存空间。
- DestroyList(&L):销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
- 增、删：
- ListInsert(&L)插入操作。在表L中的第i个位置上插入指定的e元素
- ListDelete（&L）删除操作，删除表L中的第i个位置的元素，并用e返回删除的元素的值
- 查：
- LocateElem（L，e）按值查找操作，在表L中查找具有给定关键字值的元素
- GetElem（L，i）按位置查找操作，获取表中第i个位置的元素值
- 其他常用操作：
- Length（L）求表长，返回线性表L的长度，即L中元素个数
- PrintList（L）输出表中所有元素
- Empty（L）判断表是否为空
注意：
- 对数据的操作（记忆思路）–创销，增删改查
- 对c语言的定义————<返回值类型> 函数名(<参数1类型> 参数一 <参数二> 参数二 ……)
- 实际开发中，根据实际需求定义其他基本操作
- 函数名和参数形式、命名都可改变
- 什么时候传入引用，及修改原值，传值和传地址参数的区别
顺序表（顺序存储）：
定义：用顺序存储的方式实现线性表。
顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系
· 由存储单元的邻接关系来体现
sizeof（Elem Type）函数计算数据元素大小
静态分配实现：
利用数组这种方式实现静态顺序表
|
int类型的静态顺序表实现：
|
查看是否有脏数据：
可以看到存在脏数据
静态顺序表由于是刚开始就要定义存储空间是静态的，当静态顺序表满了我们直接放弃治疗不扩充
静态顺序表的缺点是浪费存储空间
基本操作：
插入数据元素：
void ListInsert(SqList &L,int i,int e){ //基本操作在L的位序为i的位置插入元素e
for (int j = L.length; j >= i;j--){ //将第i个元素之后的元素向后移动
L.data[j] = L.data[j - 1]; //注意位序、数组下标的关系，并从后面的元素依次移动
}
L.data[i - 1] = e; //在i处放置元素e
L.length++; //长度增加
}由于这样的做法无法给用其他人调用的体验有反馈值，加上当数据元素满了时没有错误反馈所以改进为以下代码：
bool ListInsert(SqList &L,int i,int e){ //基本操作在L的位序为i的位置插入元素e
if(i<1||i>L.length+1) //判断i的范围是否有效
return false;
if(L.length>=Maxsize) //当存储空间满了不能插入
return false;
for (int j = L.length; j >= i;j--){ //将第i个元素之后的元素向后移动
L.data[j] = L.data[j - 1]; //注意位序、数组下标的关系，并从后面的元素依次移动
}
L.data[i - 1] = e; //在i处放置元素e
L.length++; //长度增加
return true;
}插入操作的时间复杂度计算：
最好情况：新插入的元素插入到表尾，不需要移动元素吗，i=n+1,循环0次，最好时间复杂度为O(1)
最坏情况：新插入元素在表头，将原有的n个元素全向后移动，i=1，循环n次最坏时间复杂度O(n)
平均情况：
新元素插入有(n+1)种选择,即插入每个位置的概率都是 p= 1/(n+1)
i =1 ,循环n次
i =2 ,循环n-1次
…
i =n+1, 循环 0次
平均循环次数: = np+(n-1)p+…+1*p = n/2
即 平均时间复杂度 = O(n)顺序表的删除：
bool ListDelete(SqList &L,int i,int &e){ //此处e不加引用法将第i个元素的值传出去
if(i<1||i>L.length) //判断i的范围是否合法
return false;
e = L.data[i - 1]; //将第ige位置的元素值赋给e
for (int j = i; j < L.length;j++){ //将第i个位置后的元素向前移
gailuxiangt L.data[j - 1] = L.data[j]; //注意位序、数组下标的关系并从前面的元素以次移动
} //要与插入是分辨开
L.length--; //线性表长度减一
return true;
}删除操作的时间复杂度：
最好情况：删除表尾元素不需要移动其他元素 i=n,循环0次；最好时间复杂度O(1)
最坏情况：删除表头元素,需要将后续的n-1个元素全部向前移动,i=1，循环n-1次最坏时间复杂度O(n)
平均情况：
删除操作有n种选择,即删除每个位置的概率都是 p= 1/n
i =1 ,循环n-1次
i =2 ,循环n-2次
…
i =n, 循环 0次
平均循环次数: = (n-1)p+…+1*p = (n-1)/2
即 平均时间复杂度 = O(n)插入和删除结果：
顺序表的查找：
顺序表的按位查找：时间复杂度：O(1),由于存放是连续的所以可以实现随机存取
Elemtype Getelemtype(SqList L,int i){
return L.data[i - 1];//数组元素下标从零开始所以i-1
}
//加入判断i的值是否合法
bool Getelem(SqList L,int i,Elemtype e){
if(i<0||i>L.length)
return false;
else{
e = L.data[i];
return true;
}
}顺序表的按值查找：
int LocateElem(SqList L,ElemType e){
for (int i = 0; i < L.length;i++){
if(L.data[i]==e)
return i + 1;
}
return 0;
}
//以int类型为例则为
int LocateElem(SqList L,int e){
for (int i = 0; i < L.length;i++){
if(L.data[i]==e)
return i + 1;
}
return 0;
}在进行元素对比时两个结构体不能直接用“==”比较，必须分别比较结构体内的每一个分量是否相等，也可以实现一个相等判断的方法来调用。
时间复杂度：（问题规模n=L.length)
- 最好情况：目标元素在表头，循环一次，最好时间复杂度=O(1)
- 最坏情况：目标元素在表尾，循环n次，最好时间复杂度=O(n)
- 平均情况：
假设目标元素出现在每个位置的概率都是 p= 1/n
目标元素在第1位 ,循环1次
目标元素在第2位,循环2次
…
目标元素在第n位, 循环n次
平均循环次数: = 1*(1/n)+2*(1/n)+...+n*(1/n)=(n+1)/2
即 平均时间复杂度 = O(n)
两种查找的测试结果：
还有一些简单的基本操作：
|
动态分配实现
|
关键点：动态分配和释放空间
c语言中利用malloc、free函数来动态申请和释放空间，使用malloc、free函数需要使用这个库文件#include<stdlib.h>
c++则使用new、delete来动态申请和释放空间
int类型动态顺序表的实现：
|
基本操作：
插入操作、删除操作、查找操作：
由于动态分配创建的顺序表可以用类似访问数组的方式访问所以其插入操作、删除操作、查找操作与静态方法相同其访问过程是通过定义的指针指向申请空间的首地址，然后通过计算类型空间大小，指出数组下标对应的空间地址，在使用malloc函数申请空间时已经 强制定义了类型，不同类型用的空间大小不同。
顺序表的特点：
优点：
- 随机访问，即可以在O（1）时间内找到第i个元素的值（数组下标访问）
- 存储密度高，每个节点只存储数据元素
缺点:
- 拓展容量不方便（即使使用动态分配的方式实现，拓展的时间复杂度比较高）
- 插入删除操作不方便，需要移动大量元素
链表（链式存储）：
链表是物理存储单元上非连续、非顺序的存储结构。与我们之前学习过的数组同为存储结构，区别是数组是连续的、顺序的存储结构。
链式存储结构的特点是：
用一组任意的存储单元存储线性表的数据元素（可连续可不连续）。
结点：
数据元素的存储映像：数据元素的本身信息和后继元素的逻辑关系。
单链表：
是链表中最简单的单向链表，每一个结点除了存放数据元素外，还要存储指向下一个结点的指针
信息域：存储数据元素信息
指针域：存储直接后继存储位置的域，其中存储的信息位指针或链
从上图可知：
- 单链表的每一个节点里面有一个信息域（element）和一个指向下一个节点的指针（next）。
- 查找一个节点是从第一个节点（head）找起。
优点：
- 不要求大片连续空间
- 改变容量方便
缺点：
- 不可随机存取
- 要耗费一定空间存放指针
代码定义：
|
LNode*这中强调的时返回一个结点
LinkList这是强调定义的是一个单链表
初始化：
|
首元结点：是指链表中存储第一个数据元素的结点
头结点：是在首结点之前附设的一个结点，其指针域指向首结点，其数据域可不存储任何信息，也 可存储与数据元素类型相同的其他附加信息,在理解时可以将头结点看作时第0个结点。
头指针：是指向链表中第一个节点的指针，有头结点，则头指针所指结点为线性表的头结点，若无 头结点则头指针所指结点为线性表的首元结点
带头结点写代码方便，不带头结点对于第一个数据节点的后续节点的处理需要用不同的代码逻辑，对空表和非空表的处理需要用不同的代码逻辑
单链表的插入和删除：
插入操作：
按位序插入:(在表L中的第i个位置插入指点元素e，首先找到第i-1个结点，将新结点插入其后)
带头结点:(在i=1的位置插入，可以把头结点看成是第0个结点用基本逻辑就可实现)
//带头结点插入
bool Listsert(LinkList &L,int i,Elemtype e){
if(i<1)
return false;
Lnode *p; //指针p指向当前扫描到的结点
int j = 0; //当前p指向第几个结点
p=L; //L指向头结点，头结点是第0个结点（不存放数据）
while(p!=NULL&&j<i-1) //循环找到第i-1个结点推出循环
{
p = p->next;
j++;
}
//return InsertNextNode(p, e); //用后插代替下面的代码调用函数
if(p==NULL) //i值不合法超过当前链长
return false;
Lnode *s = (Lnode *)malloc(sizeof(Lnode));
s->data = e;
s->next = p->next;//顺序不能反，否则会使链断
p->next = s;//将结点s连到p之后
return true; //插入成功
}分析：
当i=1（插在表头），首先查找到头结点然后申请一个新的结点，新结点的数据域赋值为e，然后将新结点的next指针指向头结点中的next所指的位置；然后头结点的next指针指向新申请的结点，这样就可以将链连起来。若顺序颠倒在断链后续结点无法找到。因为只在头结点后插入，所以循环跳过时间复杂度为O(1).
当i=3（插在表中）,首先在循环中查找到第i-1个结点，在第i-1个结点插入新结点
当i等于表尾，在循环中当p指向要插入位置的前一个结点时由于j++后不满足即推出循环找到插入位置的前一个结点，p不为空然后将新结点连入链表中，时间复杂度为O(n)n为表长
当i大于链表的最大长度+1则会由于p!=NULL这个条件跳出循环和p=NULL返回false
不带头结点
//不带头结点的插入：
bool ListSertD(LinkList &L,int i,Elemtype e){
if(i<1)
return false;
if(i==1){ //由于不带头结点其逻辑和一般插入逻辑不同所以单独操作
Lnode *s = (Lnode *)malloc(sizeof(Lnode));
s->data = e;
s->next = L;
L=s; //头指针指向新结点
return true;
}
Lnode *p = L;//指针p指向当前扫描的结点，指向第1个结点，不是头结点无头结点
int j = 1; //当前p指向第几个结点
while(p!=NULL&&j<i-1) //循环找到第i-1个结点
{
p = p->next;
j++;
}
//return InsertNextNode(p, e);//调用后插函数代替下面的代码
if(p==NULL) //i值不合法超过当前链长
return false;
Lnode *s = (Lnode *)malloc(sizeof(Lnode));
s->data = e;
s->next = p->next;//顺序不能反，否则会使链断
p->next = s;//将结点s连到p之后
return true; //插入成功
}分析：
当i=1(无头结点插在表头)，不带头结点则插入删除第1个元素时只需要更改头指针L，后续更改插入与带头结点的逻辑相同
结论：
推荐使用带头结点的写代码方便，不带头结点不方便（考试两种都要考察）
指定结点的后插：
//指定结点的后插操作：
bool InsertNextNode(Lnode *p,Elemtype e){
if(p==NULL)
return false;
Lnode *s = (Lnode *)malloc(sizeof(Lnode));
if(s==NULL) //内存分配失败（某些情况可能发生）
return false;
s->data = e; //用结点s保存数据元素e
s->next = p->next;
p->next = s; //将结点s连到p之后
return true;
}所以前面找到第i-1个结点后就可以调用后插函数了
指定节点的前插：
//指定结点的前插操作：
bool InsertPriorNode(LinkList L, Lnode *p, Elemtype e) {
Lnode *q=L;//q指针查找p的前驱结点
while(q->next!=p){
q = q->next;
}
InsertNextNode(q, e);
return true;
}
//传入头指针即可利用循环查找到所有结点信息找到指定结点的前一个结点新结点插到其后连起来
//其时间复杂度为O(n)
//偷天换日法实现前插其时间复杂度为O（n）：
bool InsertPriorNodeT(Lnode *p,Elemtype e){
if(p==NULL)
return false;
Lnode *s = (Lnode *)malloc(sizeof(Lnode));
s->next = p->next;
p->next = s;
s->data = p->data;
p->data = e;
return true;
}
删除操作(针对与带头结点的删除):删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值
找到第i-1个结点，将其指针指向第i+1个结点
按位序删除：
//按位序删除结点（带头结点）
bool ListDelete(LinkList &L,int i,Elemtype &e){
if(i<1)
return false;
Lnode *p;//指针p指向当前扫描到的结点
int j = 0;//当前p指向第几个结点
p = L;//指向头结点
while(p!=NULL&&j<i-1)
{
p = p->next;
j++;
}
if(p==NULL)
return false;//当前传入的i值不合法
if(p->next->next==NULL)
return false;//第i-1个节点之后以无其他结点
Lnode *q = p->next;
e = q->data;
p->next = q->next;
free(q);
return true;
}//最好时间复杂度O(1) 最坏、平均时间复杂度：O（n）指定结点删除：
//删除指定结点(两种：1、传入头指针查找删除 2、偷天换日法)
bool DeleteNode(Lnode *p){
if(p==NULL)
return false;
Lnode *q = p->next;//q指向*p的后继结点
p->data = p->next->data;//和后继结点交换数据
p->next = q->next; //将*q结点从链中断开
free(q); //释放后继结点的存储空间
return true;
} //时间复杂度为O(1);
//传入头指针
bool DeleteNodeT(LinkList &L,Lnode *p)
{
if(L==NULL||p==NULL)
return false;
Lnode * q = L;
while(q->next!=p)
q = q->next;
if(q->next->next==NULL)
{
free(p);
q->next = NULL;
}
q->next = p->next;
free(p);
return true;
}这段代码存在一个问题：当p是最后一个节点q则为空指针，就只能用从表头开始一次寻找p的前驱的方法删除时间复杂度为O(n),这也是单链表的局限性，无法逆向检索，有时不太方便。
查找操作（带头结点）：
按位查找操作：获取表L中第i个位置的元素的值
//按位查找（带头结点）
Lnode * GetElem(LinkList L,int i){
if(i<0)
return NULL;
Lnode *p;
int j = 0;
p = L;
while ( p!=NULL && j < i){
p = p->next;
j++;
}
return p;
}
/*当i=0时直接返回头结点
当i大于链表的实际长度返回一个空指针NULL
平均时间复杂度为O（n）
上节课的找到第i-1个结点更加方便
将常用代码封装成函数可以避免重复代码，简介易维护
*/按值查找操作：在表中查找具有给定关键字值的元素
//按值查找(带头结点）：
Lnode * LocateElem(LinkList L,Elemtype e){
Lnode *p = L->next;
while(p!=NULL&&p->data!=e){
p = p->next;
}
return p;
}
/*
平均时间复杂度O（n）
判断的时候Elemtype是结构体，结构体判断不能直接用等于号，写函数判断
*/求表长:函数代码与查找类似故加在此处
//求表长
int Length(LinkList L){
int len = 0;
Lnode *p=L;
while(p->next!=NULL){
p = p->next;
len++;
}
return len;
}
由于单链表不具备随机访问的特性，只能一次扫描，所以三种基本操作的时间复杂度为O(n),在编写代码时要注意边界值的处理。
单链表的建立方法：
尾插法：（含有一个尾指针）
第一步初始化一个单链表、第二步每一次取一个数据元素，插入到表尾、表头
尾插法建立单链表：初始化单链表，设置变量记录链表长度，利用while循环每次取一个数据元素插入到length+1个位置然后length++；这种插入方式每次都从开头开始遍历，其时间复杂度就为O（n的平方）
我们可以设置一个尾指针来减小时间复杂度，每一次将新的数据元素插在尾指针后边
//尾插法建立单链表
LinkList List_Tailnsert(LinkList &L){//正向建立单链表
int x;//设置elemtype为整形
L = (LinkList)malloc(sizeof(Lnode));//建立头结点 ----->初始化一个空表
Lnode *s, *r = L;//r为尾指针
scanf("%d", &x);
while(x!=9999) //9999只是一个结束的标志
{ //在r结点之后插入元素x
s = (Lnode *)malloc(sizeof(Lnode));
s->data = x;
r->next = s;
r = s; //r指向新表结尾 --------->保证r永远指向最后一个结点
scanf("%d", &x);
}
r->next = NULL; //尾指针制空
return L;
}
//时间复杂度为O(n)头插法：
第一步初始化一个单链表，第二部在while循环中获取一个数据元素，插入到头结点之后
时间复杂度仍然为O（n）
//头插法建立单链表
LinkList List_Headinsert(LinkList &L){//逆向建立单链表（输入的是逆向排序
Lnode *s;
int x;
L = (LinkList)malloc(sizeof(Lnode));//创建头结点
L->next = NULL; //初始为空链表
scanf("%d", &x); //输入结点的值
while(x!=9999){ //结束标志
s = (Lnode *)malloc(sizzeof(Lnode));//创建新结点
s->data = x;
s->next = L->next;
L->next = s; //将新节点插入表中，L为头指针
scanf("%d", &x);
}
return L;
}
//养成良好的编程习惯只要初始化单链表，都先把头指针指向NULL，若不指向空指针则会指向内存中遗留的脏数据影响代码的运行头插法可以运用与链表的逆置
双链表：
单链表无法逆向检索,有时候不太方便,于是乎产生了双链表,它可进可退,但存储密度更低一些
只需要在单链表的基础上在增加一个指针域来指向前驱结点,prior(先前的),双链表中的一个结点叫 Dnode.
|
初始化双链表(带头结点):
|
是否为空(带头结点):
|
双链表的插入:
|
在进行前插操作时我们可以找到给定结点的前前驱结点然后在后插实现
双链表的删除操作:
|
销毁一个双链表：
|
双链表的遍历：
|
循环链表
只需要在单链表和双链表的基础上做一些小改动即可
循环单链表：
只需将单链表尾结点的next指针指回头结点即可，在初始化时也要将头结点的next指针指向自己，判断循环单链表是否为空只需要判断（L->next==L)即可,若成立则为空的循环单链表，在判断一个结点是否为循环单链表的尾结点时只需要判断这个结点的next指针指向是否为头结点。
特点：
从一个结点出发可以找到其他任何一个结点，由于尾结点的next指针指向头结点，而单链表就没有这种特性。
普通的循环单链表从头结点找到尾部结点的时间复杂度为为O(n)要遍历整个链表，但是如果我们将循环单链表的指针一开始就指向尾部结点查找时其时间复杂度就为O(1)，由于可循环这样也是可以访问整个循环单链表的。当循环单链表指针指向尾结点时在对表尾进行插入删除操作时需要修改循环单链表的指针指向。
|
循环双链表
只需要将普通双链表头结点的prior指针指向表尾结点，表尾结点的next指针指向头结点即可。
|
循环双链表的基本操作：
插入操作：
//插入操作：在p结点之后插入s结点
bool InsertNextDnodex(Dnode *p,Dnode *s){
s->next = p->next; //将结点*s插入到结点*p之后
p->next->prior = s;
s->prior = p;
p->next = s;
return true;
}删除操作：
//双链表的删除
bool DeleteDnodex(Dnode *p,Dnode *q){ //删除p的后继结点q
p->next = q->next;
q->next->prior = p;
free(q);
return true;
}
在操作循环单（双）链表时注意的地方：
- 如何判断表空
- 如何判断结点p是否尾头结点
- 如何在表头、表尾、表中插入或删除一个结点
静态链表：
分配一整个连续的内存空间，各个结点集中安置。每一个结点中有一个数据域和一个下标域。用数组方式实现的链表，先申请一片连续的空间，空间内部每一个结点的逻辑关系并不是和数组的位序关系确定而是由每一个结点中的游标来确定相互间的关系。位序为0的数组结点为头结点，而游标对应的就是数组下标。（数组内部混乱）
特点：
优点：增删操作不许要移动大量元素
缺点：不能随机存取，只能从头结点开始一次往后找，容量固定不变。
顺序表和链表的比较：
逻辑结构：
- 顺序表和链表都时线性结构
物理结构/存储结构：
顺序表采用顺序存储，链表采取链式存储
顺序表支持随机存取，存取密度高，但大片连续空间分配不方便，改变容量不方便
链表离散小空间分配，改变容量方便，但不支持随机读取，只能从表头开始查找，由于每个结点要存储指针所以存取密度低
数据的运算/基本操作：
创销增删改查在上文已经详细记录
如何选择这两种方式：
- 当需要的线性表表长难以估计、经常需要增减删除元素时选择链表
- 表长可预估、查询搜索操作较多时选择顺序表
