一、 概念梳理
数据结构是由某一数据对象及该对象中所有数据元素之间的关系组成的。数据结构包含数据的逻辑结构、存储结构、数据的运算三方面。
1 数据的逻辑结构：指数据元素之间的内在关系，是
面向应用问题
的，独立于计算机，分为
线性结构
、
树形结构
、
图结构
、
集合结构
四类，进一步可分为两类：线性结构与非线性结构（树形、图、集合结构统一归为非线性结构）。
2 数据的存储结构：指数据元素之间的关系在计算机内的表示形式，面向计算机，是数据的逻辑结构在计算机存储中的映像。分为：
顺序存储结构
：逻辑上相关的数据元素依次存储在地址连续的存储空间中
链式存储结构
：使用指针域存储逻辑上相关的相邻元素地址。为了存储一个元素，需要同时存放数据元素本身与该元素逻辑上相关的的相邻的元素的地址，两部分信息合称为
结点
。一个结点的存储地址通常指存放该结点的存储块的起始存储单元地址（即首地址）。
3 数据的运算：数据结构常见的运算包括：搜索运算、插入运算、删除运算、更新运算等（即增删改查）。
而此节所说明的
线性表
为零个或若干个数据元素构成的线性序列，记为（a
0
,a
1
,a
2
…a
n-1
）。其中，a
i
表示下表为i的元素，a
i-1
是a
i
的直接前驱元素，a
i+1
是a
i
的直接后继元素。线性表除第一个元素a
0
没有直接前驱元素，最后一个元素a
n-1
没有直接后继元素以外，任何其他元素都有唯一的直接前驱元素和直接后继元素。线性表中数据元素之间存在着一一对应的关系，因此，线性表的逻辑结构为线性结构。
二、 线性表的存储结构
1、 线性表的顺序存储
线性表的顺序存储指使用连续的存储空间，按照数据元素在线性表中的序号依次存储数据元素。采用顺序存储结构的线性表称为
顺序表
。顺序表中，逻辑上相邻的元素，物理存储地址也相邻。
若顺序表首个元素a
0
在内存中的存储地址为loc(a
0
)，每个元素占用k个存储单元，则线性表中任意元素a
i
在内存中的存储地址为：
loc(a
i
)=loc(a
0
)+i*k
由此可知，顺序表中只要给定loc(a
0
)和k的值，即可计算出该表中其他任何元素的存储地址，从而对其执行相关操作。因此线性表的顺序存储结构是一种
随机存取结构
(即可以直接通过特定元素下标直接访问，而无需按存储顺序存取)。
下面以C语言一维数组为例，介绍顺序表各种基本操作的算法实现：
1.1 顺序表的定义
typedef struct seqList
{
int n; //n为顺序表实际存储元素数目，即顺序表长度
int maxLength; //顺序表最大允许长度
ElemType *element; //自定义类型ElemType，*element指示顺序表的存储空间的首地址
}SeqList; //SeqList为类型名
1.2 顺序表的初始化
顺序表的初始化运算是使用动态分配数组空间方式构造一个空的线性表。动态分配数组空间可以达到有效利用存储空间的目的。
#include<stdlib.h> //添加包含malloc函数的头文件
#define ERROR 0
#define OK 1
int Init(SeqList *L,int msize)
{
L->maxLength=msize;
L->n=0;
L->element=(ElemType *)malloc(sizeof(ElemType)*mSize); //动态生成一维数组空间
if(!L->element)
return ERROR;
return OK;
}
1.3 顺序表的元素查找
由于顺序表具有随机存取的特点，因此对于元素a
i
的访问可以直接通过数组下标定位获得。
int Find(SeqList L,int i,Element *x)
{
if(i<0||i>L.n-1) //判断查找目标元素下标i是否越界
return ERROR;
*x=L.element[i] ; //取出element[i]的值通过参数x返回
return OK;
}
1.4 顺序表的元素插入
将新元素x插入顺序表L中元素a
i
的后面。若i=-1，表示新元素插入顺序表第一位。
步骤如下：
1 判断元素下标i是否越界，是则返回ERROR。
2 判断顺序表存储空间是否已满，是则返回ERROR。
3 将元素a
i+1
、a
i+2
、…a
n-1
依次后移一个单位。
4 将新元素x插入目标位置。
5 顺序表长度增加一单位。
int Insert(SeqList *L,int i,ElemType x)
{
if(i<-1||i>L->n-1)
return ERROR;
if(L->n==L->maxLength)
return ERROR;
for(int j=L->n-1;j>i;j--) //此处也可改为（int j=i+1;j<n;j++） L->element[j]=L->element[j+1];...
{
L->element[j+1]=L->element[j]; //插入位置后面元素依次后移
}
L->element[i+1]=x;
L->n=L->n +1;
return OK;
}
顺序表的元素插入过程中，时间主要消耗在移动元素上。插入一个新元素时，需移动元素的平均次数为n/2，可得顺序表插入算法的时间复杂度为O(n)。
1.5 顺序表的元素删除
与上述插入相反，完成删除顺序表中元素a
i
的操作。
步骤如下：
1 判断元素下标是否越界，是则返回ERROR.
2 判断顺序表是否为空，是则返回ERROR。
3 将元素a
i+1
,a
i+2
,…a
n-1
依次向前移动一个单位。
4 表的长度减少一单位。
int Delete(SeqList *L,int i)
{
if(i<-1||i>L->n-1)
return ERROR;
if(!L->n)
return ERROR;
for(int j=i+1;j<L->n;j++)
{
L->element[j-1]=L->element[j]; //删除位置后元素依次前移
}
L->n=L->n -1;
return OK;
}
同顺序表插入算法，删除算法的平均时间复杂度也为O(n)。
1.6 顺序表的元素输出
int Output(SeqList *L)
{
int i;
if(L->n ==0)
return ERROR;
for(int i=0;i<L->n;i++)
{
printf("%d ",L->element[i]);
}
printf("\n" );
return OK;
}
1.7 顺序表的撤销
释放初始化运算中动态分配的数据元素的存储空间，以防止内存泄漏。
void Destory(SeqList *L)
{
L->n=0;
L->maxLength=0;
free(L->element);
}
1.8 主函数运行测试
int main()
{
int i;
SeqList list;
Init(&list,10);
for(i=0;i<10;i++)
{
Insert(&list,i-1,2*i);
}
Output(&list);
Delete(&list,3);
Output(&list);
Destory(&list);
return 0;
}
(运行前需将上述代码中ElemType改为具体的基本数据类型或结构体类型)
输出结果为：
0 2 4 6 8 10 12 14 16 18
0 2 4 8 10 12 14 16 18
2、线性表的链式存储
线性表的顺序存储结构缺点明显：插入、删除元素需要进行大量元素的移动，运算效率低，且需要按照事先估计的表长申请连续的存储空间。而采用链式存储结构的线性表则不存在上述问题。
采用链式存储结构的线性表称为
链表
，包括单链表、循环链表和双向链表等多种类型。
链表中，每个结点包括两部分信息：数据元素本身及其直接后继的存储地址，对应两个域：存储数据元素信息的域称为
数据域
，存储直接后继存储地址的称为
指针域
。
2.1.1 单链表的定义
每个结点只含一个指针域的链表，称为单链表，数据域记为element，指针域记为link。线性表以单链表形式存储时，第一个元素a
0
所在的结点称为头结点，存储头结点的指针称为头指针，记为first。若链表为空，则此时first指针值为NULL。单链表最后一个结点称为尾结点，其指针域为NULL。
在对单链表进行操作时，需注意保存好后继结点的地址，避免丢失后继节点的地址，出现“
断链
”现象。
typedef struct node
{
ElemType element; //结点的数据域
struct node *link; //结点的指针域
}Node;
typedef struct singleList
{
Node *first; //单链表的头指针
int n; //单链表元素个数
}SingleList;
2.1.2 单链表的初始化
int Init(SingleList *L)
{
L->first=NULL;
L->n=0;
return OK;
}
2.1.3 单链表的元素查找
查找单链表中元素a
i
并读取该元素的值。由于链表具有非随机存取特性（即顺序存取特性），因此在查找特定元素时需沿单链表从头结点开始逐个遍历。
int Find(SingleList L,int i,ElemType *x) //思考如果将此处ElemType *x改为ElemType x，那么Find函数的定义要进行怎样的修改？
{
if(i<0||i>L.n-1) //对i的越界检查
return ERROR;
Node *p;
p=L.first;
for(int j=0;j<i;j++)
{
p=p->link; //j=m时，p存储第m个元素的指针域，即指向第m+1元素的地址
}
*x=p->element; //将第i个元素的值传给x
return OK;
}
2.1.4
单链表的元素插入
(难点）
单链表的插入运算是在a
i
之后插入新元素x。
步骤如下：
1 判断i是否越界，是则返回ERROR.
2 查找a
i
，使指针p指向该结点。
3 生成新的结点，将该结点数据域置为x，指针q指向此结点。
4 若i=-1，新结点q插在头结点之前，成为新的头结点；若i>-1，将q所指向的结点插入p所指向的结点之后。
5 单链表元素个数加一，返回OK。
int Insert(SingleList *L,int i,ElemType x)
{
Node *p,*q;
if(i<-1 || i>L->n-1)
return ERROR;
p=L->first;
for(int j=0;j<i;j++)
{
p=p->link;
}
q=(Node*)malloc(sizeof(Node)); //初始化结点q
q->element =x;
if(i>-1)
{
q->link=p->link;
p->link=q; //新结点插在p指向结点之后
}
else
{
q->link=L->first;
L->first=q; //新结点插在头结点之前，替代称为新头结点
}
L->n++;
return OK;
}
2.1.5 单链表的元素删除
单链表中的删除运算功能是删除元素a
i
。若i=0，表示删除头结点，此时需将first指针指向a
1
所在结点，使其成为新的头结点；若i>0，则需使a
i
的直接前驱a
i-1
的指针域存储a
i
的直接后继a
i+1
的地址。
int Delete(SingleList *L,int i)
{
Node *p,*q;
if(L->n==0) //对单链表是否为空的判断
return ERROR;
if(i<0||i>L->n-1) //对i是否越界的判断
return ERROR;
p=L->first;
q=L->first;
for(int j=0;j<i-1;j++)
{
q=q->link; //沿单链表遍历使q最终q存储第i-2个元素的指针域，指向a(i-1)元素
}
if(i==0)
L->first=L->first->link; //两个first：前者指链表L的头指针，后者为头结点
else{
p=q->link; //p存储第i-1个元素的指针域 ，指向a(i)
q->link=p->link; //将指向第i+1个元素的指针赋给第第i-1的元素的指针域
}
free(p); //释放第i个元素的存储空间
L->n--;
return OK;
}
2.1.6 单链表的输出
int Output(SingleList *L)
{
Node *p;
if(!L->n)
return ERROR;
p=L->first;
while(p)
{
printf("%d ",p->element); //使p依次指向各个结点，输出值
p=p->link;
}
return OK;
}
2.1.7 单链表的撤销
void Destroy(SingleList *L)
{
Node *p;
while(L->first)
{
p=L->first->link;
free(L->first);
L->first=p; //从头结点开始依次向后释放每一个元素存储空间
}
}
2.1.8 主函数运行测试
#include<stdio.h>
#include<stdlib.h>
#define ERROR 0
#define OK 1
typedef int ElemType;
int main()
{
int x;
SingleList list;
Init(&list);
for(int i=0;i<9;i++)
{
Insert(&list,i-1,7*i); //此处控制单链表个元素的数值
}
printf("The linklist is:");
Output(&list);
Delete(&list,3); //控制删除的元素下标
printf("\nThe linklist is:");
Output(&list);
Find(list,2,&x); //控制查找的元素下标
printf("\nThe value is: %d",x);
Destroy(&list);
return 0;
}
输出结果为：
The linklist is:0 7 14 21 28 35 42 49 56
The linklist is:0 7 14 28 35 42 49 56
The value is: 14
2.2.1 带表头结点单链表的定义
上述单链表中，头结点前没有直接前驱，进行插入、删除运算时，需将头结点的插入删除作为特殊情况处理。为简化算法，在单链表头结点之前增加一个表头结点，此类链表称为带表头结点的单链表。
元素a
0
所在结点为头结点，头结点之前的结点为表头结点。表头结点的数据域中不存放线性表中的数据元素，即使表为空时也需要有表头结点。
typedef struct node
{
ElemType element; //结点的数据域
struct node *link; //结点的指针域
}Node;
typedef struct headerList
{
Node *head;
int n;
}HeaderList;
2.2.2 带表头结点单链表的初始化
int Init(HeaderList *h)
{
h->head=(Node*)malloc(sizeof(Node)); //给表头结点指针域分配一个Node型存储空间，生成表头结点
if(!h->head)
return ERROR;
h->head->link=NULL;
h->n=0;
return OK;
}
注：定义指针变量需进行初始化，即必须给指针进行相应的地址分配，否则会成为野指针，会引起程序崩溃。以定义整型指针变量 int *p；为例，常见的初始化方法如下：
int x=5;
p=&x; //人为指定一个地址赋给p指针，指针类型与变量数据类型须一致
#include<stdlib.h>
p=(int*)malloc(sizeof(int)); //系统为p指针分配一个同类型存储空间适合的地址
2.2.3 带表头结点单链表的插入
int Insert(HeaderList *h,int i,ElemType x)
{
Node *p,*q;
if(i<-1 || i>h->n-1)
return ERROR;
p=h->head;
for(int j=0;j<=i;j++)
p=p->link; //使p指针指向第i个结点
q=(Node*)malloc(sizeof(Node));
q->element=x;
q->link=p->link; //使插入结点指针域指向原第i+1个结点
p->link=q; //使第i个结点指针域指向插入结点
h->n++;
return OK;
}
2.3.4 带表头结点单链表的删除
int Delete(HeaderList *h,int i)
{
Node *p,*q;
if(!h->n)
return ERROR;
if(i<0 || i>h->n-1)
return ERROR;
q=h->first;
for(int j=0;j<i;j++)
q=q->link;
p=q->link;
q->link=p->link;
free(p);
h->n--;
return OK;
}
2.4 单循环链表的定义
用单链表最后一个结点的指针域存储头结点的地址，使得整个单链表形成闭环，这样头尾相接的单链表称为
单循环链表
。
也可为单循环链表增加表头结点，构成
带表头结点的单循环链表
。
2.5.1双向链表的定义
双向链表每一个元素都是一个对象，每个对象有一个关键字key和两个指针：next和prev。对象中还可包含其他的辅助数据，(称为卫星数据)。L.head指向链表的第一个元素，若L.head=NULL，则链表为空。
若链表为有序的，则链表的线性顺序与链表元素关键字的线性顺序一致；
若链表为上述提到的循环链表，则头结点的prev指针指向尾结点，尾结点的next指针指向头结点。
typedef struct duNode
{
ElemType element;
struct duNode *prev;
struct duNode *next;
}DuNode,DuList;
2.5.2 双向链表的插入
插入运算（在
元素a
i
之前
插入x）核心代码：
q->prev=p->prev; //p指向第i个结点
q->next=p; //q指向插入结点
p->prev->next=q;
p->prev=q; //注意执行顺序，不可更改
2.5.3 双向链表的删除
删除运算核心代码：
p->prev->next=p->next;
p->next-.prev=p->prev;
free(p);
2.5.4 双向链表的哨兵
类似于上述链表中添加表头结点，在双向链表中也可添加一个对象——
哨兵元素L.nil
,该对象代表NULL，同时具备其他结点相同的各个属性。对于链表代码中出现的对于NULL的引用，都代之以对哨兵L.nil的引用，可
简化边界条件
。此类调整往往使常规的双向链表转变为一个有哨兵的双向循环链表，哨兵L.nil位于头结点和尾结点之间，属性L.nil.next指向头结点，L.nil.prev指向尾结点，从而实现忽略头结点与尾结点的边界条件的目的。（空链表即只由一个哨兵构成，类似与表头结点，此时L.nil.next和L.nil.prev同时指向L.nil）
注：哨兵基本不能降低相关操作的时间复杂度，但可以降低常数因子。循环语句中使用哨兵好处往往在于可以使代码变得整洁，而非提高速度。一些情况下，哨兵的使用让循环程序代码更紧凑，从而降低运行时间中n或n
2
的洗漱。但当设计许多较短的链表时，哨兵所占用的额外存储空间会造成内存浪费，因此须慎用。
3、 顺序表与链表的比较
时间性能方面：
1 顺序表是随机存取结构，按位置随机访问的运算的时间复杂度为O(1)；链表不具有随机存取特性，按位置访问元素只能从表头开始遍历链表，平均时间复杂度为O(n)。
2 对于链表，在确定插入或删除元素的位置后，只需修改指针即可完成相关操作，时间复杂度为O(1)；而顺序表进行插入及删除操作时，需要移动近乎表长一半元素，时间复杂度为O(n)，随着线性表中元素数目的增加，移动元素的时间开销代巨大。
——因此，若线性表需进行频繁的插入删除操作，宜采用链表的存储结构；若线性表需进行频繁查找而相对较少地执行插入和删除操作，或程序目的与数据元素在线性表中的关系密切相关，则顺序表更加适合。
空间性能方面：
顺序表需要预分配一定长度存储空间，若预分配空间过大，易导致存储空间浪费；预分配存储空间过小，将造成空间溢出问题。而链表不需要预分配存储空间，只要有足够的内存空间，链表中元素个数就没有限制。
——因此，当线性表中元素个数变化较大时或未知时，宜采用链表的存储结构；当线性表的元素个数变化不大且可较准确的预知大致长度时，宜采用顺序表的存储结构。