1.线性表
1.1线性表是一种逻辑关系（见绪论）。
1.2定义：是具有相同类型的n个元素的有限序列，其中n为表长，n=0时为空表（关键词：相同类型，一般处理的数据元素都是相同类型，比如一个人那么都是人，而不会把人与车放在一起。关键词：有限序列，必须有限长度，因为计算机无法处理无限个数据。有序，线性表中的每一个元素都是有序号的排列）
1.3表示方法：L = （a1,a2,a3……an） a1为表头元素，an为表尾元素。除表头表尾外所有元素都有前驱结点和后继结点
1.4线性表的特点：
1> 表中元素个数有限
2> 表中元素具有逻辑上的顺序性，在序列中各个元素序列具有先后次序
3> 表中元素都是数据元素，每个元素都是单个元素
4> 表中元素的数据类型都相同，所以每个元素占有相同大小的存储空间
5> 表中元素具有抽象性，即讨论元素间一对一的逻辑关系相邻的关系，而不考虑元素究竟表示内容（可以理解为数据结构只管数据的逻辑结构、物理结构、数据运算，数据的逻辑结构只看数据间关系的描述）
1.5线性表是一种逻辑结构，表示元素之间一对一相邻的关系。
1.6线性表逻辑上的九种基本操作（重点）
1> InitList(&L)：初始化表。构造一个空的线性表。（&L引用，L线性表）
2> DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
3> LocateElem(L,e)：按值查找操作。在表中L查找具有给定值e的元素。（e为值，即找到元素值为e的元素,若有多个则只取第一个）
4> GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。（i在0与表长之间，包括0和表长）
5> ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。（前插，即在第i个元素的前一个位置插入，i在0与表长之间，包括0和表长）
6> ListDelete（&L,i,&e）：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。（i在0与表长之间，包括0和表长）
7> PrintList(L)：输出操作。按前后顺序输出线性表L的有元素值。
8> Empty（L）：判空操作。若L为空表，则返回TRUE，否则返回FLASE。
9> Length（L）：求表长。返回线性表L的长度，即L中数据元素的个数。
1.7补充几个关系：
1> 线性表是逻辑概念，是在计算机内存中以数组的形式保存的线性表。，与之对应的还有树（堆:一种特殊的树）、图。
2> 顺序表、链表都是一种线性表，是线性表以不同的方式实现的。比如顺序表就是顺序存储方式 ，内存中开辟的地址是连续的，而链表采用链式存储的方式，地址是可以不连续的。
3> 顺序存储结构存在的问题：存储空间分配不灵活，运算的空间复杂度高。
二.顺序表
1.基本概念
1> 顺序存储：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
2> 顺序表就是使用顺序存储方式的线性表。
3> 线性表第一个元素的存储位置称为起始位置或者基地址。
4> 优点：由上面的一些概念可知，顺序表一定是占用连续的存储空间。所以一旦知道某个元素的存储位置，我们就可以立刻算出其他元素的存储地址。也就是说顺序表的任一元素都可以随机存取。
例如：当我们知道a1的地址LOC(a1),an的地址为LOC(a1)+(n-1)sizeof(ElemType)
5> 顺序表的实现
顺序表的特点：地址连续、依次存放、随机存取、类型相同。所以可以使用数组来实现，但是顺序表的长度可以改变，而数组的长度一旦确定不可更改。所以可以在加上一个变量用来表示顺序表的长度属性。
#define LIST_INIT_SIZE 100
typedef struct
{
ElemType elem[LIST_INIT_SIZE];
int length;
}SqList;
比如对于多项式加减之类的，那么ElemType就是一个结构体类型，里面有指数与系数。
上面一种属于数组的静态分配，还有一种方式，数组动态分配。
typedef struct
{
ElemType *data;
int length;
}SqList;
SqList L;
L.data = (ElemType *)malloc(sizeof(ElemType)*MaxSize);
这里使用的malloc函数，当然我们用的C++，可以使用new函数。而且传参时可以用引用等。
三.顺序表的基本操作
1. 插入操作
bool ListInsert(SqList &L, int i, ElemType e)
{
if(i<1||i>L.length+1) //输入合法
return false;
if(L.length>=MaxSize) //顺序表未满
return false;
int j;
for(j=L.length; j>=i; j--)
L.data[j]=L.data[j-1]; //length是长度，在数组中对应下标为length-1.
L.data[i-1] = e;
L.length++;
return true;
}
时间复杂度：O（n）
2.删除操作
bool ListDelete(SqList &L, int i, ElemType &e)
{
if(i<1||i>L.length+1) //输入合法
return false;
if(L.length==0) //顺序表为空
return false;
e=L.data[i-1];
int j;
for(j=i; j<=L.length; j++)
L.data[j-1]=L.data[j];
L.length--;
return true;
}
时间复杂度：O（n）
3.按值操作
int LocateElem(SqList L, Elemtype e)
{
int i;
for(i=0; i<=L.length-1; i++)
{
if(e==L.data[i]);
return i+1;
}
return -1;
}
时间复杂度：O（n）
四.单链表
1.定义：线性表的链式存储
2.单链表是通过指针实现线性关系
3.特点：
1>只能实现顺序存取，不可实现随机存取
2>逻辑上是顺序的，存储方式是随机的
4.结点由数据域和指针域组成，用结构体实现
typedef struct LNode
{
ElemtType data;
struct LNode *next;
}LNode,*LinkList;
五.单链表的基本操作
1.头插法建立单链表
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(sizeof(LNode))
s->data=x;
s->next=L-next;
L->next=s;
scanf("%d",&x);
}
return L;
}
时间复杂度：O（n）
2.尾插法建立单链表
LinkList List_TailInsert (LinkList &L)
{
int x; //结点的值
L=(LinkList)malloc(sizeof(LNode)); //申请结点空间
LNode *s; //插入结点
*r=L; //r为尾指针
scanf("%d",&x); //头插法建立单链表
while(x!=9999)
{
s=(LNode*)malloc(sizeof(LNode))
s->data=x;
r->next=s;
r=r->next;
scanf("%d",&x);
}
r->next=NULL;
return L;
}
时间复杂度：O（n）
3.按序号查找
LNode *GetElem(LinkList L,int i) //返回结点指针
{
int j=i;
LNode *p=L->next;
if(i == 0)
return L;
if(i<1)
return NULL;
while(p&&j<i) //p非空
{
p=p->next;
j++;
}
return p;
}
时间复杂度：O（n）
4.按值查找
LNode *LocateElem(LinkList L, Elemtype e)
{
LNode *p=L->next;
while(p!=NULL&&p->data!=e)
p=p->next;
return p;
}
时间复杂度：O（n）
5.插入操作
分为前插法和后插法
一般情况下后插法直接队i位置的结点进行如下操作：s->next=ai->next;ai->next=s
而前插法则要先遍历找到i-1结点，在进行上面操作。
不过后插法和前插法的区别就在s结点和ai结点的顺序，所以前插法可以通过使用后插法在改变两者顺序实现。
时间复杂度：O（1）
6.删除操作
一般先遍历到i-1位置在让ai-1->next = ai->next即可
不过可以先改变ai与ai+1位置在删掉i+1位置即可实现
q=p->next;
p->data=p->next->data 交换位置
p->next=q->next 删除
free(q)
q为要删结点
时间复杂度：O（1）
7.求表长
int count = 0;
p=head
while(p->next!=NULL)
{
count++;
p=p->next;
}
时间复杂度：O（n）
引入头结点可以使得操作统一。
六.几种特殊链表
1.双向链表
结点实现
typedef struct DNode
{
ElemType data;
struct DNode *prior;
struct DNode *next;
}DNode, *DLinklist;
插入实现
双链表表尾的插入与表头表中不同，即插入过程不一致。
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;
时间复杂度：O（1）
删除实现
p->next = q->next;
q->next->prior=p;
free(q)
时间复杂度：O（1）
2.循环链表
判空：循环单链表L->next == L;
循环双链表L->next == L;L->prior = L;
3.静态链表
目的：便于在没有指针类型的高级程序设计语言中使用链表结构。
实现：相比单链表把地址改成数组下标，把单链表中指向下一个结点的指针改成下一个结点的下标（称为游标）。
next域存储下一个结点的下标，最后一个结点的next域为-1。用数组描述链表，会预分配一个较大空间，
插入删除都不用移动元素，只需修改游标
#define MaxSize 50
typedef struct DNode
{
ElemType data;
int next;
}SLinkList[MaxSize];
七.顺序表与链表对比
1.存储方式
链表只能顺序存取
顺序表可以实现顺序存取和随机存取
2.逻辑结构和物理结构
链表：逻辑相邻物理上不一定相邻，通过指针实现逻辑关系
顺序表：逻辑相邻物理上也相邻，通过相邻表示逻辑关系
3.基本操作
插入&删除：单链表为O（1）（结点指针已知）；O（n）（结点指针未知），操作时只需修改指针
顺序表为O（n）修改时需要移动元素
查找：按值查找中单链表和顺序表都为O（n）
按序查找中单链表为O（n）,顺序表为O（1）
4.内存空间
顺序存储：无论静态分配还是非静态分配都需要预先分配合适的内存空间（静态分配时预分配空间太大会浪费，太小会溢出；动态分配不会溢出但扩充要大量移动元素）
链式存储：在需要时分配结点空间即可，高效方便，但指针要使用额外空间。
5.怎样选择线性表的存储结构
存储：规模难以估计 单链表
存储密度大 顺序表
效率：频繁按序号访问 顺序表
插入和删除 单链表（因为顺序表需要大量元素移动）
环境：基于数组 顺序表
基于指针 单链表
线性表稳定选顺序表、动态选单链表
八.三种常用操作
最值、逆置、归并
1.最值—顺序表：
int min=L[0];
int max=L[0];
for(int i=0;i<n;i++)
{
if(L[i]>max)
max=L[i];
if(L[i]<min)
min=L[i];
}
时间复杂度O（n）
最值—单链表：
int min=p->next->data;//p初始化为头结点
int max=p->next->data;
for(;p!=NULL;p=p->next)
{
if(p->data>max)
max=p->data;
if(p->data<min)
min=p->data;
}
时间复杂度O（n）
逆置—顺序表
int i=0;
int j=n-1;
while(i<j)
{
int temp;
temp=L[i];
L[i]=L[j];
L[j]=temp;
}
时间复杂度O（n）
逆置—单链表
//p为头结点、r为尾结点
while(p->next!=r)
{
temp = p->next;
p->next = temp->next; //将第一个结点拿出，赋值给temp
temp->next = r->next;
r->next = temp; //将temp放在r的后面
}
时间复杂度O（n）
合并—顺序表
int i=0;//将L1、L2合并到L中
int j=0;
int k=0;
for(;i<L1_Size&&j<L2_Size;k++)
{
if(L1[i]<L2[j])
L[k]=L1[i++];
else
L[k]=L2[j++];
}
while(i<L1_Size)
L[k++]=L1[i++];
while(j<L2_Size)
L[k++]=L2[i++];
时间复杂度O（n）
需要额外空间
合并—单链表
while（p->next!=NULL&&q->next!=NULL）
{
if(p->next->data<q->next->data)
{
r->next=p->next; //把P的后继放在r的后继上
p->next=p->next->next;//指针域，移除p的后继
r=r->next; //r后移
}
else
{
r->next=q->next;
q->next=q->next->next;
r=r->next;
}
}
if(p->next!=NULL)
r->next = p->next;
if(q->next!=NULL)
r->next = q->next;
free(p);
free(q);
时间复杂度O（n）
不需要额外空间
