【数据结构之线性表】熬夜暴肝，有亿点详细
前言
我们今天来学习线性表，线性表是数据结构中比较简单的一个数据结构了，但是它的重要性不容忽略，废话不多，直接正文。
目录
初识线性表
线性表的定义
线性表是具有相同类型的n（n>=0）个元素的有限序列，其中n为表长，当n=0时，该表为空表
线性表的特点：
1.表中元素个数有限
2.表中元素具有逻辑上的顺序性，在序列中各个元素排序有其先后次序
3.表中元素都是数据元素，每个元素都是单个元素
4.表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间
5.表中元素具有抽象性，即讨论元素间一对一的逻辑关系，而不考虑元素究竟表示的内容
6.线性表是一种逻辑结构，表示元素之间一对一相邻的关系
7.线性表在数据元素有限集中，除第一个元素无直接前驱，最后一个元素无直接后续以外，每个数据元素有且仅有一个直接前驱元素和一个直接后继元素。
线性表的基本操作
还记得之前说过运算的定义依靠数据的逻辑结构实现，运算的实现针对于数据的存储结构吗？不过不记得你可以去看看数据结构入门篇
线性表是一种逻辑结构，因此具体操作我们是无法实现的，不过我们可以定义这些操作。
我们主要从参数，返回值来说一下基本操作吧
&L指传入一个引用，这个引用指向线性表表头
InitList(&L):
初始化表。构造一个空的线性表。
DestroyList(&L):
销毁操作。销毁线性表，并释放线性表L所占用的内存空间。 LocateElem(L,e):
按值查找操作。在表中L查找具有给定关键字值得元素。
GetELem(L,i):
按位查找操作。获取表L中第i个位置的元素的值。
ListInsert(&L,i,e):
插入操作。在表L中的第i个位置上插入指定元素e。
LIstDelete(&L,i,&e):
删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
PrintList(L):
输出操作。按前后顺序输出线性表L的所有元素值。
Empty(L):
判空操作。若L为空表，则返回TRUE,否则返回FALSE。
Length(L):
求表长。返回线性表L的长度，即L中数据元素的个数。
以上就是线性表的对基本操作的定义，对这些操作的实现我们得依靠存储结构来说了。
线性表根据存储结构的不同又分为顺序表与链表，接下来我们就逐一说一下他们两个吧！
顺序表
顺序表就是线性表的顺序表示，它的主要特点是逻辑结构与存储结构相同都是连续的。
顺序表的定义
一组地址连续存放的存储单元依次存放线性表的元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻
这样一说会感觉这个和数组十分相似啊。的确十分相似，但是却有所不同，详见下文。
顺序表与数组
相同之处：数组与线性表相同都是一组地址连续存放的存储单元依次存放元素
不同之处：数组下标从0开始，而顺序表下标从1开始。数组有最大存储空间是静态的，而顺序表可以是动态的。
定义的实现
顺序表定义的实现有两种分别是静态分配和动态分配。它们的区别是使用静态分配时顺序表的容量是被规定好的，无法增加的。使用动态分配时顺序表的容量可以变大。
实现数组静态分配：
# define MaxSize 100;
typedef struct{
ElemType date[MaxSize];//ElemType是某种元素类型
int length ;//顺序表长度
}sqList;//顺序表名字
我们使用结构体实现顺序表的定义，这里使用了某种类型的数组存放某种数据，数组容量为常量MaxSize。
实现数组动态分配：
# define MaxSize 100;
typedef struct{
ElemType *date;
int length;
}sqList;
动态分配语句：
C： L.data = (Elemtype*)malloc(sizeof(ElemType)*InitSize);
C++：L.data = new ElemType[InitSize]
顺序表的基本操作
顺序表的基本操作有插入，删除，查找
顺序表的插入
这个是给顺序表L在指定位置i处，插入元素e
bool ListInsert (SqList &L,int i,ElemType e){
//除去不合法的i，保证不能空下一个位置
//length+1是因为有可能最后一个位置插入
if(i<1||i>L.length+1){
return false;
}
if(i>=MaxSize){
return false;
}
//每个元素向后移动给i-1下标位置空出来
for(int j=L.length;j>=i;j--){
L.date[j]=L.date[j-1];
}
L.date[i-1]=e;
return true;
}
顺序表的删除
传入要删除的位置和一个元素的引用来保存要删除元素的值
bool ListDelete(SqList &L,int i,ElemType &e){
if(i<1||i>L.length){
return false;
}
//保存要删除的元素
e=L.date[i-1];
//后面的元素向前逐个移动
for(int j=i;j<L.length;j++){
L.date[j-1]=L.date[j];
}
L.length--;
return true;
}
顺序表的查找
按值查找元素位置（位置从1开始）
int ListDelete(Sqlist L,ElemType e){
int i;
for(i=0;i<L.length;i++){
if(L.date[i]==e)
return i+1;
}
return 0;
}
如果是按位置查找直接L.date[i-1]即可得位置为i处的值是多少。
链表
链表我们最常见的就是单链表，除此之外还有一些特殊链表，我们重点还是说说单链表。
单链表的定义
单链表是线性表的链式存储，通过一组任意的存储单元来存储线性表中的数据元素，通过指针来实现逻辑关系
定义的实现
单链表的每一块都分为数据域和指针域，指针域用来存放逻辑上下一块内存的地址
typedef struct LNode{
ElemType date;
struct LNode *next;
}LNode,*LinkList;
链表又有两种，一种是有头结点的，一种是没有头结点的。我们为了提高效率一般使用带头结点的单链表，后面操作讲解也都是带头结点的链表。
头结点放在链表的最前面，结构与每一块结点相同，不过数据域中为空或者存放链表长度等重要元素，头结点的指针域指向链表的第一个元素。
使用头结点能帮助我们处理头部时方法与其他位置处理方法相同，操作时不需要判断是否为首元素了，大大提高了代码效率。
单链表的基本操作
单链表基本操作有：创建单链表，查找，插入和删除。
创建单链表
创建单链表我们分为头插法创建和尾插法创建，区别就是生成的链表顺序与插入时顺序是否相同。显然头插法创建单链表是顺序相同。
头插法
头插法就是每次插入元素时在链表的头结点后插入，最后生成的链表顺序与插入时顺序相反。
LinkList List_HeadInsert (LinkList &L){
LNode *s;
int x;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
scanf("%d",&x);
while(x!=99999){
s=(LNode*)malloc(sizeof(LNode));
s->date=x;
s->next=L->next;
L->next=s;
scanf("%d",&x);
}
return L;
}
尾插法
尾插法就是每次插入元素时在链表的末尾插入元素，最后生成的链表顺序与插入时顺序相同。
LinkList List_HeadInsert (LinkList &L){
LNode *s,*r;
int x;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
*r=L;
scanf("%d",&x);
while(x!=99999){
s=(LNode*)malloc(sizeof(LNode));
s->date=x;
r->next=s;
r=s;
scanf("%d",&x);
}
r->next=NULL;
return L;
}
单链表的查找
查找又根据需求分为按序查找和按值查找。
按序查找
如果查找时需要查找某个位置元素的结点，那么就是按序查找。传入的参数为一个链表和需要查找的位置。
LNode *GetElem(LinkList L,int i){
int j=1;
LNode *p=L->next;
if(i==0)
return L;
if(i<1)
return NULL;
while(p&&j<i){
p=p->next;
j++;
}
return p;
}
按值查找
如果需要在链表中查找某个值e的结点，则：
LNode *LocateElem(LinkList L,ElemType e){
LNode *p=L->next;
while(p!=NULL&&p->date!=e){
p=p->next;
}
return p;
}
单链表的插入
插入有两种，第一种是插入到指定位置，第二种是默认在链表头部插入
插入到指定位置
要求插入到i位置处时，需要先找到i-1处的结点，然后插入
p=GetElem(L,i-1);
s->next=p->next;
p->next=s;
默认插入头部
在链表头部插入元素时：
s->next=head；
head=s;
单链表的删除
删除i位置的结点：
p=GetElem(L,i-1);
q=p->next;
p->next=q->next;
free(q);
如果需要删除指定结点*q那么只需要：
q=p->next;
p->date=p->next->date;
p->next=q->next;
free(q);
特殊链表
特殊链表有：双链表，循环链表和静态链表。
双链表
双链表顾名思义就是比单链表高级了一点，一个双链表的结点在单链表的基础上又增加了一个指针，这个指针指向它的前一个结点
结点情况如下：
| 指针域 | 数据域 | 指针域 |
|---|---|---|
| prior | date | next |
定义的实现：
typedef struct DNode{
ElemType date;
struct DNode *prior,*next;
}DNode,*DLinklist;
结点发生改变了。对链表的一些操作也会发生改变
插入操作：
s->next=p->next;
p->next->prior=s;
s->prior=p;
p->next=s;
删除操作：
p->next=q->next;
q->next->prior=p;
free(q);
循环链表
之前的链表都是条状的，循环链表是头尾相连了，就是将链表的尾部与头部连接起来。有因为条状链表有单链表与双链表之分，所以循环链表也有两种分别是：循环单链表与循环双链表
对于循环单链表我们一般设置尾指针这样操作效率会更高。
对于循环双链表我们头结点的prior结点指向最后一个节点，尾结点的next指针指向头结点，以形成循环双链表。
之前的链表我们判断是否为空表都是看最后一个结点的next结点是否为空。显然，循环链表不可以这样判断，我们判断方式如下：
循环单链表判断空链表条件：
if(L->next==L)
循环双链表判断空链表条件：
if(L->next==L&&L->prior==L)
静态链表
静态链表这个名字听起来高大上，其实也是非常简单的，它和数组是非常相似的。先来看它的结构组成：
#define MaxSize 50
typedef struct DNode{
ElemType date;
int next;
}SLinkList[MaxSize];
它其实就是一个数组只不过不连续而已，结点分为两部分。date域存放数据，而next域存放下一个存放数据的数组的下标。
使用数组下标索引实现了逻辑结构。
线性表的常用操作
到此为止我们已经学过了线性表按照存储结构不同的两种分类，分别是顺序表与链表，以及他们的一些基本操作。但是在我们以后在做题时候，不会直接来考插入，删除等操作，它们都是贯穿在很多的大的操作中去的，我愿把他们称为非基本操作。。
下面我们来讲一下对于线性表的一些常考的操作分别是：最值，逆置，归并
最值
最值顾名思义就是求出线性表中的最大以及最小值，我们分别用顺序表与链表实现。
顺序表实现：
int min = L[0];
int max = L[0];
for(int i = 0; i < n; i++){
if(min > L[i])
min = L[i];
if(max < L[i])
max = L[i];
}
链表实现:
int min = p -> next ->data;
int max = p -> next ->data;
p = p -> next;
while(p != NULL){
if(min > p ->data)
min = p ->data;
if(max < p ->data)
max = p ->data;
p = p ->next;
}
逆置
逆置就是把线性表中元素顺序调反
顺寻表实现
int i = 0;
int j = n-1;
while(i < j){
temp = L[i];
L[i] = L[j];
L[j] = temp;
i++;
j--;
}
链表实现
//r为尾结点
while(p ->next != r){
temp = p -> next;
p -> next = temp -> next;
temp -> next = r -> next;
r -> next = temp;
}
归并
归并就是把两个线性表变为一个，这里其实又有两种了，一种是无序归并，还有一种是有序的归并。无序归并十分简单，这里就不说了，我们主要讲的就是有序归并。
有序归并的栗子：
L1=(1,8,6)
L2=(5,6,9)
归并后为：L3=(1,5,6,6,8,9)
顺序表实现
int i = 0, 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[j++];
链表实现归并
while(p->next!=NULL && q->next!=NULL){
if(p->next->data < q->next->data){
r->next = p->next;
p->next= p->next->next;
r = r->next;
}
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(1)(节点指针已知)；O(n)(节点指针未知)，但操作时只需修改指针
顺序表为O(n)且需要大量移动元素
查找：
按值查找中单链表和顺序表（无序）都为O(n)
按序查找中单链表为O(n)，顺序表为O(1)
内存空间
顺序存储：
无论静态分配还是非静态都需要预先分配合适的内存空间 静态分配时预分配空间太大回造成浪费，太小会造成溢出
动态分配时虽不会溢出但是扩充需要大量移动元素，操作效率低
链式存储：
在需要时分配结点空间即可，高效方便，但指针要使用额外空间
如何选择合适的线性表呢？
根据上面的比较做了以下选择总结：
| 问题情况 | 顺序表（较稳定） | 单链表（较动态） |
|---|---|---|
| 规模难以估计 | * | |
| 存储密度大 | * | |
| 按序号访问 | * | |
| 插入与删除 | * | |
| 基于数组 | * | |
| 基于指针 | * |
结言
本来打算两天就总结一篇数据结构的，但是我大意了，写起来属实很费劲，很累，甚至一度向放弃。
But我是不会放弃的，下一篇栈与队列，敬请关注！
有问题请指正，感谢支持！