目录
1 线性表的定义
2 线性表的逻辑特性
3 线性表的存储结构
4 顺序表
4.1 顺序表的定义
4.2 顺序表的存储
4.3 顺序表的特点
4.4 顺序表的基本操作
（1）初始化顺序表
（2）查找操作
（3）插入操作
（4）删除操作
（5）顺序表的逆置
（6）顺序表的排序
5 链表
5.1 链表的定义
5.2 链表的分类
5.2.1 单链表
5.2.2 双链表
5.2.3 静态链表
6. 顺序表和链表的比较
总结
1 线性表的定义
线性表是具有相同特性数据元素的一个有限序列。该序列中所含元素的个数叫作线性表的长度，用 n（n≥0）表示。注意，n可以等于零，表示线性表是一个空表。
线性表是一种简单的数据结构，可以把它想象成一队人在超市排队买东西。排队人数对应线性表的长度，队伍长度是有限的，大白不会让队伍无限长下去，这里体现了线性表是一个有限序列;队中所有人的身份都是居民，这里体现了线性表中的数据元素具有相同的特性;线性表可以是有序的，也可以是无序的，如果按照年龄来排队，老人在前， 年轻人在后，则体现了线性表的有序性。
2 线性表的逻辑特性
继续拿定义中的例子来进行说明。在一队学生排队买东西做中，只有一个学生在队头，同样只有一个学生在队尾。 在队头的学生的前面没有其他学生，在队尾的学生的后边也没有其他学生。除了队头和队尾的学生以外，对于其他的每一个学生，紧换着站在其前面和后面的学生都只有一个，这是很显然的事情。线性表也是 这样，只有一个表头元素，只有一个表尾元囊，表头元聚没有前驱，表尾元素没有后继，除表头和表尾 元素之外，其他元素只有一个直接前驱，也只有一个直接后继，以上就是线性表的逻辑特性。
3 线性表的存储结构
线性表的存储结构有顺序存髓结构和链式存储结构两种。前者称为顺序表，后着称为链表、下面通 过对比来介绍这两种存储结构。
4 顺序表
4.1 顺序表的定义
线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第1个元素存储在线性表的起始位，第i个儿素的存储位置后面i紧接着存储的是第i+1个元素，称i为元素α,在线性表中的位序。对此，顺i序表的特点是表中元素的逻辑顺序与其物理顺序相同。
假设线性表最大为Maxsize，起始位置为LOC(A)，sizeof(ElemType)为单个元素所占用的内存大小，则线性表的存储结构如下图所示：
每个数据元素的存储位置都和线性表的起始位置相差一个和该数据元素的位序成正比的常数，因此，线性表中的任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。通常用高级程序设计语言中的数组来描述线性表的顺序存储结构。
4.2 顺序表的存储
假定线性表的元素类型为ElemType，则线性表的顺序存储类型描述如下
#define Maxsize 50 //线性表最大长度
typedef struct{
ElemType data[Maxsize]; //顺序表的元素
int len; //顺序表当前长度
}SqList; //顺序表的定义类型 数组可以是静态分配的，也可以是动态分配的。在静态分配时，由于数组的大小和空间事先已经固定．一旦空间古满，再加入新的数据就会产生溢出，进而导致程序崩溃。
而在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空画的目的，而不需要为线性表一次性地划分所有空间。
#define InitSize 100 //线性表的初始长度
typedef struct{
ElemType *data; //顺序表的元素
int MaxSize,len; //顺序表当前最大容量和长度
}SqList; //顺序表的定义 C语言的动态分配内存
L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
C++动态分配内存
L.data = new ElemType(InitSize);
注意:动态分配并不是链式存储、它同样居于顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时动态决定。
4.3 顺序表的特点
（1）顺序表最主要的特点是随机访问，即通过首地址和元素序号可在时间O(1)内找到指定的元索。
（2）顺序表的存储密度高、每个结点只存储数据元素。
（3）顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。
从该实验平台中，我们可以很清晰的看到顺序表的物理存储和逻辑存储结构。因为int 类型在电脑中占4个字节，所以在存储顺序表中，每个元素存储位置相差4个字节（就比如第1个数据和第2个数据相差4个字节），而逻辑存储也都是连续的。
4.4 顺序表的基本操作
（1）初始化顺序表
只需将len设置为0，代码如下∶
void InitList(SqList &L){ //L本身要发生改变，所以用引用型
L.len=0;
} （2）查找操作
在顺序表中查找第一个值等于e的元素，并返回 其下标，代码如下∶
int findElem(SqList L, int e){
for(int i=0;i 最好情况：查找的元素就在表头，仅需比较一次，时间复杂度为O(1)。
最坏情况：查找的元素在表尾（或不存在）时，需要比较n次，时间复杂度为O(n)。
平均情况：假设
(= 1/n）是查找的元素在第i (1<=i<=L.length）个位置上的概率，则在长度为n的线性表中查找值为e的元素所需比较的平均次数为（n+1）/2，因此，线性表按值查找算法的平均时间复杂度为O(n)。
（3）插入操作
在顺序表L的第i ( 1<=i<=L.length + 1)个位置插入新元素e。若i的输入不合法，则返问false，表示插入失败；否则，将第i个元素及其后的所有元素依次往后移动一个位置，腾出一个空位置插入新元素e，顺序表长度增加 1，插入成功，返回true 。
bool ListInsert(SqList &L,int i,int e){
if(i<1||i>L.len+1) //判断插入位置是否合法
return false;
if(L.len>=MaxSize) //判断插入后是否溢出
return false;
for(int j=L.len;j>=i;j--) //将i后面元素往后移
L.data[j]=L.data[j-1];
L.data[i-1]=e; //插入
L.len++; //线性表插入加1
return true;
} 最好情况:在表尾插入(即 i= n+1)，元素后移语句将不执行，时间复杂度为O(1) 。
最坏情况:在表头插入（即i= 1)，元素后移语句将执行n次，时间复杂度为O(n)。
平均情况:假设( = 1/(n1+ 1)）是在第个位置上插入一个结点的概率，则在长度为n的线性表中插入一个结点时，所需移动结点的平均次数为n/2。因此，线性表插入算法的平均时间复杂度为O(n)。
以下是插入的步骤：
1）找到需要插入的位置
2）将步骤 1）中找出的位置上以及其后的元素往后移动一个位置，然后将其放至腾出的位置上。
注意：从实验平台中，我们可以看出元素9所占的物理地址是之前元素2所在的物理地址，而元素2后面的元素（包括2）都往后移动4个字节，所以在物理存储上依据连续，逻辑上也连续。这也与上述所写特性吻合。
（4）删除操作
删除顺序表L中下标为p（0≤p≤length-1）的元素，成功返回true，否则返回false，并将被删除元素的值赋给 e。
分析：要删除表中下标为p的元素，只需将其后边的元素逐个往前移动一个位置，将p位置上的元素覆盖 掉，就达到了删除的目的。明白了上述元素插入的算法，本算法写起来就相对容易了，只需将插入操作 中的元素右移改成元素左移即可。插入操作中右移时需要从最右边的元素开始移动，这里很自然想到在 删除操作中左移时需要从最左边的元素开始移动。
bool ListDelete(SqList &L,int i,int &e){
if(i<1||i>L.len) //判断i是否在合法范围
return false;
e=L.data[i-1]; //将删除元素赋值给e
for(int j=i;j 最好情况：删除表尾元素（即 i=n)，无须移动元素，时间复杂度为O(1)。
最坏情况：删除表头元素（即 i = 1)，需移动除表头元素外的所有元素，时间夏杂度为O(n)。
平均情况：假设 ( = 1/n）是删除第i个位置上结点的概率，则在长度为n的线性表中删除一个结点时，所需移动结点的平均次数为(n-1)/2，因此，线性表删除算法的平均时间复杂度为O(n)。
以下是删除的步骤：
1）先判断数据是否合法
2）从要删除的元素位置开始，依次从前往后进行移动数据
注意：从实验平台中，我们可以看出删除之后依旧是每个元素相隔4个字节，所以在物理存储上依据连续，逻辑上也连续。这也与上述所写特性吻合。
（5）顺序表的逆置
将顺序表L的元素进行逆置，使其与原顺序表的元素是相反的。
分析：要将顺序表L进行逆置，只需要将第一个元素和最后一个元素、第二个元素和倒数第二个元素...依次调换位置即可。不用考虑顺序表元素个数的奇偶，因为如果如果是奇数，完全可以不用管中间的元素，其余元素进行调换；如果是偶数，只需两两调换就行。
void Inversion(SqList *L)
{
int i,a;
for(i=0;ilen/2;i++) //左右两边边调换位置
{
a = L->data[i];
L->data[i] = L->data[L->length-i-1];
L->data[L->length-i-1] = a;
}
} 最好情况、最坏情况、平均情况：时间复杂度均为O(n)。
（6）顺序表的排序
将顺序表L的元素进行排序，使其成为一个非递增或者非递减的序列。
排序大家可以看小编之前发的文章：八大排序算法 ，这里讲述了大部分数据结构中的排序。
注意：从实验平台中可以看出，排序完成之后，顺序表的内存占用没有发生改变，只是元素的值发生了变化；由此可以得出，在将顺序表排序之后，不会改变顺序表的物理地址，只会改变顺序表的逻辑地址。
5 链表
5.1 链表的定义
在链表存储中，每个结点不仅包含所存元素的信息，还包含元素之间逻辑关系的信息，如单链表中前驱结点包含了后能结点的地址信息。这样就可以通过前驱结点中的地址信息找到后继结点的位置。
顺序表可以随时存取表中的任意一个元素，它的存储位置可以用一个简单直观的公式表示，但插入和删除操作需要移动大量元素。链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理位置上也相邻，它通过“链”建立起数据元素之间的逻辑关系，因此插入和朋除操作不需要移动元素，而只需修改指针，但也会失去顺序表可随机存取的优点。
5.2 链表的分类
5.2.1 单链表
在每个结点中除了包含数据域外，还包含一个指针域，用以指向其后继结点。图所示为带头结 点的单链表。这里要区分一下带头结点的单链表和不带头结点的单链表。
（1） 单链表的数据描述
typedef struct LNode{ //定义单链表的类型
int data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList; （2）单链表的特点
利用单链表可以解决顺序表需要大量连续存储单元的缺点，但单链表附加指针域，也存在浪费存储空间的缺点。由于单链表的元素离散地分布在存储空间中，所以单链表是非随机存取的存储结构，即不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历，依次查找。
由实验平台我们可以看出链表中的每个元素物理地址都是随机无序的，而其逻辑地址是连续的，所以要让其保持逻辑上连续，就需要记录下一个地址的指针，于是引出next指针。这也印证了上述说的特点，单链表可以解决顺序表需要大量连续存储单元的缺点，但单链表附加指针域，也存在浪费存储空间的缺点。
头结点 ：
通常用头指针来标识一个单链表，如单链表L，头指针为NULL时表示一个空表。此外，为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点，如上图就是带头结点的链表。
头结点和头指针的区分：不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，结点内通常不存储信息。
引入头结点后，可以带来两个优点:
1、由于第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理。
2、无论链表是否为空，其头指针都指向头结点的非空指针（空表中头结点的指针域为空)，因此空表和非空表的处理也就得到了统一。
（3）单链表的基本操作
①采用头插法建立单链表
该方法从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。
头插法建立单链表的代码如下：
LinkList HeadInsertList(LinkList &L){
LNode *s;
int x;
L=(LinkList)malloc(sizeof(LNode)); //创建头结点
L->next=NULL; //初始为空链表
scanf("%d",&x);
while(x!=-1){ //输入-1结束
s=(LNode*)malloc(sizeof(LNode)); //创建结点
s->data=x;
s->next=L->next;
L->next=s;
scanf("%d",&x);
}
return L;
} 采用头插法建立单链表时，读入数据的顺序与生成的链表中的元素的顺序是相反的。每个结点插入的时间为O(1)，设单链表长为n，则总时间复杂度为O(n)。
②采用尾接法建立单链表
头插法建立单链表的算法虽然简单，但生成的链表中结点的次序和输入数据的顺序不一致。若希望两者次序一致，则可采用尾插法。该方法将新结点插入到当前链表的表尾，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。
尾接法建立单链表的代码如下：
LinkList TailInsertList(LinkList &L){
int x;
L=(LinkList)malloc(sizeof(LNode));
LNode *s,*r=L; //r是最后一个结点的位置
scanf("%d",&x);
while(x!=-1){ //输入-1结束
s->next=r->next;
r->next=s;
r=s; //加入s后,s变成了最后一个结点，把r换成最后一个结点
scanf("%d",&s);
}
r->next=NULL; //尾结点指向空
return L;
} 因为附设了一个指向表尾结点的指针，故时间复杂度和头插法的相同。
③按序号查找结点值
在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第三个结点为止，否则返回最后一个结点指针域NULL。
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&&jnext;
j++;
}
return p;
} 时间复杂度：O(n)
④按值查找表结点
从单链表的第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针:若整个单链表中没有这样的结点，则返回 NULL。
LNode *LocateElem(LinkList L,ElemType e){
LNode *p=L->next;
while(p!=NULL&&p->data!=e)
p=p->next;
return p;
} 时间复杂度：O(n)
⑤插入结点操作
插入结点操作将值x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点﹑即第i-1个结点，再在其后插入新结点。
算法思路：算法首先调用按序号查找算法CetElem( L,i-1)，查找第i-1个结点。假设返回的第i-1个结点为*p，然后令新结点* s 的指针域指向*p 的后继结点，再令结点i*p 的指针域指向新插入的结点*s。（就类似于上述的头插法）
在插入时候，这里和上面顺序表不同，插入元素所放的位置，是在计算机中找到空余内存进行随机存储，然后记录他的next指针即可。
方法一：
p=GetElem(L,i-1);
s->next=p->next;
p->next=s;
算法中，语句②和③的顺序不能颠倒，否则，当先执行 p->next=s后，指向其原后继的指针就不存在，再执行s->next=p->next时，相当于执行了s->next=s，显然是错误的。本算法主要的时间开销在于查找第i-1个元素,时间复杂度为O(n)。若在给定的结点后面插入新结点，则时间复杂度仅为O(1)。
方法二：
s->next=p->next;
p->next=s;
temp=p->data;
p->data=s->data;
s->data=temp;
⑥删除结点操作
删除结点操作是将单链表的第 i个结点删除。先检查删除位置的合法性，后查找表中第 i -1个结点，即被删结点的前驱结点，再将其删除。其操作过程如图所示。
假设结点p为找到的被删结点的前驱结点，为实现这一操作后的逻辑关系的变化．仅需修改* p的指针域。即将*p的指针域next指向q的下一结点。
p=GetElem(L,i-1);
q=p->next;
p->next=p->next;
free(q);
⑦ 链表逆置
将链表的位置进行前后互换。
void Inversion(list *head){
list *p,*q;
p=head->next;
head->next=NULL;
while(p!=NULL){
q=p;
p=p->next;
q->next=head->next;
head->next=q;
}
} 读者可以接着这个循环一直遍历下去，就能知道整个逆置过程了
从实验平台来看，每个元素的物理地址都没发生改变，而它所指的Next地址发生了改变，这也是链表特性所造成的。
5.2.2 双链表
单链表只能由开始结点走到终端结点，而不能由终端结点反向走到开始结点。如果要求输出从终端 结点到开始结点的数据序列，则对于单链表来说操作就非常麻烦。为了解决这类问题，构造了双链表。 图所示为带头结点的双链表。双链表就是在单链表结点上增添了一个指针域，指向当前结点的前驱。 这样就可以方便地由其后继来找到其前驱，从而实现输出从终端结点到开始结点的数据序列。
同样，双链表也分为带头结点的双链表和不带头结点的双链表，情况类似于单链表。带头结点的双 链表，当head->next为NULL时，链表为空;不带头结点的双链表，当 head为 NULL时，链表为空。
双链表中结点类型的描述如下：
typedef struct DNode{
ElemType data;
struct DNode *prior,*next;
}DNode,*DLinklist; ①双链表的插入操作
在双链表中p所指的结点之后插入结点*s，其指针的变化i过程如图所示。
s->next=p->next; //将结点*s插入到结点*p之后 (1)
p->next->prior=s; //（2）
s->prior=p; //(3)
p->mext=s; //(4)
上述代码的语句顺序不是唯一的，但也不是任意的，①和②两步必须在④步之前，否则*p的后继结点的指针就会丢掉，导致插入失败。为了加深理解，读者可以在纸上画出示意图。若问题改成要求在结点p之前插入结点*s，请读者思考具体的操作步骤。
②双链表的删除操作
删除双链表中结点*p的后继结点*q，其指针的变化过程如图所示。
p->next=q->next; //(1)
q->next->prior=p; //(2)
free(q);
若问题改成要求删除结点*q的前驱结点*p，清读者思考具体的操作步骤。
在建立双链表的操作中，也可采用如同单链表的头插法和尾插法，但在操作上需要注意指针的变化和单链表有所不同。
③循环单链表
知道了单链表的结构之后，循环单链表就显得比较简单了，只要将单链表的最后一个指针域（空指针）指向链表中的第一个结点即可（这里之所以说第一个结点而不说是头结点是因为∶如果循环单链表 是带头结点的，则最后一个结点的指针域要指向头结点;如果循环单链表不带头结点，则最后一个指针 域要指向开始结点）。图2-4所示为带头结点的循环单链表。循环单链表可以实现从任一个结点出发访问 链表中的任何结点，而单链表从任一结点出发后只能访问这个结点本身及其后边的所有结点。带头结点 的循环单链表，当 head等于head->next时，链表为空;不带头结点的循环单链表，当 head等于NULL 时，链表为空。
④循环双链表
和循环单链表类似，循环双链表的构造源自双链表，即将终端结点的 next指针指向链表中的第一个 结点，将链表中第一个结点的 prior指针指向终端结点，如图所示。循环双链表同样有带头结点和不 带头结点之分。当 head 等于NULL时，不带头结点的循环双链表为空。带头结点的循环双链表中是没有 空指针的，其空状态下，head->next 和 head->prior必然都等于head。所以判断其是否为空，只需要检查 head->next和 head->prior两个指针中的任意一个是否等于head指针即可。因此，以下四句代码中的任意 一句为真，都可以判断循环双链表为空。
head->next==head;
head->prior==head;
head->next==head&&head->prior==head;
head->next==head||head||head->prior==head;
单链表就像单行车道，只允许车辆往一个方向行驶;双链表就像双向车道，车辆既可以从左往右行驶，也可以从右向左行驶;循环单链表就像单向环形车道，车辆可沿着一个方向行驶在这条车道上;循环双链表就像双向环形车道，车辆可以沿着两个方向行驶在这条车道上。
5.2.3 静态链表
静态链表借助一维数组来表示，如图所示
左图是静态链表，右图是其对应的一般链表。一般链表结点空间来自于整个内存，静态链表则来自于一个结构体数组。数组中的每一个结点含有两个分量∶一个是数据元素分量 data;另一个 是指针分量，指示了当前结点的直接后继结点在数组中的位置（这和一般链表中next指针的地位是同等的）。
静态链表结构类型的描述如下:
#define MaxSize 50 //静态链表的最大长度
typedef struct{ //静态链表结构类型的定义
ElemType data; //存储类型元素
int next; //下一个元素的数组下标
}SLinkList[MaxSize]; 静态链表以next=-1作为其结束的标志。
注意∶静态链表中的指针不是我们通常所说的C语言中用来存储内存地址的指针型变量，而是一个 存储数组下标的整型变量，通过它可以找到后继结点在数组中的位置，其功能类似于真实的指针，因此 称其为指针。
说明∶在考研中经常要考到顺序表和链表的比较，这里给出一个较为全面的答案。
6. 顺序表和链表的比较
1. 读写方式
顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。例如在第i个位置上执行存或取的操作，顺序表仅需一次访间，而链表则需从表头开始依次访问i次。
2. 逻辑结构和物理结构
采用唢序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻。而采用链式存储时，逻辑上l邻的几素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来表示的。
3. 查找、插入和删除操作
对于按值查找，顺序表无序时，两者的时间复杂度均为O(n)：顺序表有序时，可采用折半查找．此时的时间复杂度为O(
)。
对于按序号查找，顺序表支持随机访问，时间复杂度仅为O(1)，而链表的平均时间复杂度为O)。顺表的插入、删除操作，平均需要移动半个表长的元素。链表的插入、删除操作，只需修改相关结点的指针域即可。由于链表的每个结点都带有指针域，故而存储密度不够大。
4.空间分配
顺序存储在静态存储分配情形下，一旦存储空间装满就不能扩充，若再加入新元素，则会出现内溢出．国此需要预先分配足够大的存储空间。预先分配过大，可能会导致顺序表后部大量闲Y';预先分配过小，又会造成溢出。动态存储分配虽然存储室间可 以扩充，但雷要移动大量元索，导致操作效率降低，而且若内存中没有更大块的连续存储空间，则会导致分配失败。链式存储的结点室间只在需要时中请分配，只要内存有空问就可以分配，操作灵活、高效。
总结
以上就是今天要讲的内容，本文详细介绍了线性表的基本操作以及其不同存储的特性。
线性表是我们学习数据结构的基础，也是每个在开始学习数据结构小白的噩梦，尤其是在C语言程序设计中链表和结构体的使用。希望这篇文章能为大家有所帮助，也希望大家对不同的排序算法有更深一步的理解。
参考文献：
[1] 苏小红，孙志刚，陈惠鹏等编著. C语言大学实用教程（第四版）[M]. 北京：电子工业出版社，2017.
[2] 严蔚敏，吴伟民. 数据结构[M]. 北京：清华大学出版社.
[3] 罗勇君， 郭卫斌.算法竞赛_入门到进阶[M].北京：清华大学出版社.
作者：
江西师范大学_姜嘉鑫； 江西师范大学_龚俊