数据结构（二）----线性表（顺序表，链表）

目录

1.线性表的概念

2.线性表的基本操作

3.存储线性表的方式

（1）顺序表

•顺序表的概念

•顺序表的实现

静态分配：

动态分配：

顺序表的插入：

顺序表的删除：

顺序表的按位查找：

顺序表的按值查找：

顺序表的特点：

（2）单链表

•单链表的实现

不带头结点的单链表：

带头结点的单链表：

单链表的插入：

▴按位序插入（带头结点）

▴按位序插入（不带头结点）

▴指定结点的后插操作

▴指定结点的前插操作

单链表的删除：

▴按位序删除（带头结点）

▴按位序删除（不带头结点）

▴指定结点的删除

单链表的查找：

▴按位查找

▴按值查找

单链表的长度：

单链表的两种建立方法：

▴尾插法建立单链表

▴头插法建立单链表

（3）双链表

• 双链表的实现

双链表的初始化：

双链表的插入：

双链表的删除：

双链表的销毁：

 双链表的遍历：

（4）循环链表

• 循环单链表

• 循环双链表

（5）静态链表

 •静态链表的相关概念

 •静态链表的定义

 •静态链表的相关基本操作

（6）顺序表和链表的对比

1.逻辑结构

2.物理结构（存储结构）

3.数据运算/基本操作

 •初始化

 •销毁

 •增删

 •查找

 •总结：

1.线性表的概念

线性表是具有相同数据类型的n(n0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为 L=(a1,a2,…,ai,ai+1,…,an)

注：

1.这里的“相同”是指每个数据元素所占空间一样大，同时强调有限序列，例如，所有整数按递增次序排列，虽然有次序，但是对象是所有整数，所以不是线性表。

2.ai是线性表中的“第i个”元素线性表中的位序（位序从1开始，数组下标从0开始）。

3.a1是表头元素；an是表尾元素。
4.除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。

2.线性表的基本操作

初始化，销毁，增删改查：

•InitList(&L)：初始化表。构造一个空的线性表L，分配内存空间。

•DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
•Listlnsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。
•ListDelete(&Li,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
•LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。
•GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。
其他常用操作:
•Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。

•PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。

•Empty(L)：判空操作。若L为空表，则返回true，否则返回false。

关于"&":

对于下面的代码：

在main函数中定义了一个变量x=1，接着调用test()，test(int x)中的“x”其实是main函数中“x”的复制品，两个"x"是不同的数据（占用不同的内存空间），所以test()中定义的"x"的值，其实修改的是复制品"x"的值，并没有修改main()中变量"x"的值。

所以输出的结果中，"调用test后x=1"。

对比下面这段代码：

test(int &x)，参数x为引用类型，所以test()中操作的参数“x”与main()中的“x”是同一份数据（占用同一个空间），所以在test()中对"x"的修改会影响到main()中"x"的值，即对参数的修改带回到了main()中。

3.存储线性表的方式

（1）顺序表

•顺序表的概念

用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

设线性表第一个元素的存放位置是 LOC(L)，由于每个数据元素在物理上连续存放，并且每个数据元素所占空间大小相同。所以有：

•顺序表的实现

静态分配：

#define MaxSize 10         //定义最大长度
typedef struct{            
    ElemType data[MaxSize];    //用静态的“数组”存放数据元素
    int length;                //顺序表的当前长度
}SqList;                   //顺序表的类型定义(静态分配方式)

/*这里的ElemType指的是元素的类型，可以是int也可以是struct，这取决于顺序表存储的数据类型*/

具体地看个示例： 

#include<stdio.h>
#define MaxSize 10         //定义最大长度
typedef struct{            
    int data[MaxSize];    //用静态的“数组”存放数据元素
    int length;                //顺序表的当前长度
}SqList;                   //顺序表的类型定义(静态分配方式)

//初始化一个顺序表
void InitList(SqList &L){
    for(int i=0;i<MaxSize;i++)
        L.data[i]=0;    //将所有数据元素设置为默认初始值
    L.length=0;    //顺序表初始长度为0    
}

int main(){
    SqList L;    //声明一个顺序表，表示在内存中分配存储顺序表L的空间，包括:MaxSize*sizeof(ElemType)和 存储 length 的空间
    InitList(L); //初始化顺序表
    return 0;
}

若没有设置默认数据元素的默认值：

#include<stdio.h>
#define MaxSize 10         //定义最大长度
typedef struct{            
    int data[MaxSize];    //用静态的“数组”存放数据元素
    int length;                //顺序表的当前长度
}SqList;                   //顺序表的类型定义(静态分配方式)

//初始化一个顺序表
void InitList(SqList &L){
    L.length=0;    //顺序表初始长度为0    
}

int main(){
    SqList L;    
    InitList(L); //初始化顺序表
    //"违规"打印整个data数组
    for(int i=0;i<MaxSize;i++)
        printf("data[%d]=%d\n",i,L.data[i]);
    return 0;
}

打印结果如下：

不同的计算机中运行此代码结果都会不同，这是因为内存中会遗留“脏数据”。虽然声明顺序表之后，系统会分配一块内存空间，但是这片内存空间之前存放的是什么我们是不知道的，所以如果不设置默认值的话，之前的脏数据就会遗留下来。

其实不设置默认初始值是可以的，只要将i<MaxSize改为i<L.length，就是不从第一个元素访问到最后一个元素，而是从第一个元素访问到实际存储的最后一个元素。例如当前没有存储任何数据，那么系统就不会打印任何值。

#include<stdio.h>
#define MaxSize 10         //定义最大长度
typedef struct{            
    int data[MaxSize];    //用静态的“数组”存放数据元素
    int length;                //顺序表的当前长度
}SqList;                   //顺序表的类型定义(静态分配方式)

//初始化一个顺序表
void InitList(SqList &L){
    L.length=0;    //顺序表初始长度为0    
}

int main(){
    SqList L;    
    InitList(L); //初始化顺序表
    for(int i=0;i<L.length;i++)
        printf("data[%d]=%d\n",i,L.data[i]);
    return 0;
}

静态分配中顺序表的内存空间是固定的，若设置的内存空间过小，那么数组很容易被存满，如果过大，则浪费内存空间。所以可以采用动态分配。

动态分配：

//malloc和free函数的头文件
#include<stdlib.h>
#define InitSize 10
typedef struct{
    int *data;    //指示动态分配数组的指针，这里是整型指针
    int MaxSize;
    int length;
}SeqList;

//使用malloc和free动态申请和释放内存空间
void InitList(seqList &L){
    L.data=(int *)malloc(InitSize*sizeof(int));
//malloc函数的参数指明要分配多大的连续内存空间
//malloc函数返回一个指针，需要强制转型定义的数据类型指针，在这里就是(int *)
    L.length=0;
    L.MaxSize=InitSize;
}

void IncreaseSize(SeqList &L,int len){
    int *p=L.data;
    L.data=(int *)malloc(L.MaxSize+len)*sizeof(int);
    for(int i=0;i<L.length;i++){
        L.data[i]=p[i];
    }
    L.MaxSize=L.MaxSize+len;
    free(p);   
}

int main(){
    SeqList L;
    InitList(L);
    IncreaseSize(L,5);
    return 0;

}

在IncreaseSize中

int *p=L.data，表示p指针与data指针指向同一个内存空间

L.data=(int *)malloc(L.MaxSize+len)*sizeof(int)，表示新分配一个内存空间，此空间包括原来顺序表的最大长度，以及新增加的长度len。同时将data指针指向这个内存空间。

 for(int i=0;i<L.length;i++){
        L.data[i]=p[i];
    }
    L.MaxSize=L.MaxSize+len;

表示将原来的数据复制到新的区域中，并且改变最大长度为新增内存空间的长度

free(p)，表示释放原来的内存空间，归还给系统。由于p变量是局部变量，所以执行完free(p)之后，存储p变量的内存空间也会被回收。

至此就实现了动态增加数组长度的操作。由于需要将旧数据复制到新的内存空间，所以会增加时间开销。

顺序表的插入：

之前讲过，在第i个位置上插入元素，需要将i及以后的元素都往后移动一位。这里是基于“静态分配"的代码。

#include <stdio.h>

#define MaxSize 10

typedef struct {
    int data[MaxSize];
    int length;
} SqList;

void InitList(SqList &L) {
    L.length = 0;
}

// 在L的位序i中插入元素e
bool ListInsert(SqList &L, int i, int 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--)
        L.data[j] = L.data[j - 1];  // 将第i个元素及之后的元素后移
    L.data[i - 1] = e;              // 在位置i上放入e
    L.length++;                     // L长度加1
    return true;
}

int main() {
    SqList L;
    InitList(L);
	for (int i = 0; i < 5; i++) {
    	ListInsert(L, i + 1, i + 1); // 插入元素，自动更新长度
	}
	
    printf("插入前的顺序表为:\n");
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");

    ListInsert(L, 3, 99);  // 在第3位插入元素99

    printf("插入后的顺序表为:\n");
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");

    return 0;
}

实现结果：

插入操作的时间复杂度（最深层循环语句的执行次数与问题规模 n的关系）是多少呢？

注：问题规模n就是线性表的表长L.length

最好情况：新元素插入到表尾，不需要移动元素

i=n+1，循环0次；最好时间复杂度=O(1)；

最坏情况：新元素插入到表头，需要将原有的n个元素全都向后移动

i=1，循环n次；最坏时间复杂度=O(n)；

平均情况：假设新元素插入到任何一个位置的概率相同，即i=1,2,3,…,length+1的概率都是p=
1/n+1

i=1，循环n次；i=2时，循环n-1次；i=3，循环n-2次…i=n+1时，循环0次

循环n次的概率是p，循环n-1的概率也是p，依此类推，将p提出来就是

p*[n+(n-1)+(n-2)+·····+0]====O(n)

顺序表的删除：

删除表与插入表的操作相反，就是将要删除的元素的后面的元素往前移动一位，并且length值减1

#include<stdio.h>
#define MaxSize 10
typedef struct{
    int data[MaxSize];
    int length;
} SqList;

void InitList(SqList &L){
    L.length = 0;
}

bool ListDelete(SqList &L,int i,int &e){
    if(i<1 || i>L.length)
        return false;
    e=L.data[i-1];
    for(int j=i;j<L.length;j++)   //将被删除的元素赋给e
        L.data[j-1]=L.data[j];    //将第i个位置后的位置前移
    L.length--;    //线性表长度减1
    return true;
}

int main()
{
    SqList L;
    InitList(L);
    printf("顺序表为:\n"); 
    for (int i = 0; i < 5; i++) {
        L.data[i] = i + 1;
        printf("%d ", L.data[i]);
        L.length++;
    }
    int e=-1;    //声明一个变量e，初始值设为-1
    if(ListDelete(L,3,e))
        printf("\n已删除第3个元素，删除元素值=%d\n",e); 
    else
        printf("位序i不合法，删除失败\n");
    printf("删除元素后的顺序表为:\n"); 
    for(int i=0;i<L.length;i++){
		printf("%d ",L.data[i]);
	}
    return 0;   
}

实现结果：

注意：

（1）

bool ListDelete(SqList &L,int i,int &e)，这里的参数e一定要是引用类型的，即删除e，再把e的值返回。

首先在main()中声明一个变量e，初始值为-1

接着调用ListDelete()时，会把要删除的变量的值复制到e变量所对应的内存区域中，即

e=L.data[i-1];

最后for循环，将删除元素之后的元素依次往前移动，并且length值减1

（2）

删除操作中，i位置后的元素往前移，是先从前面的元素往前移动的，而插入操作中，是先从后面的元素往后移动的。这个应该很好理解。

删除操作的时间复杂度是多少呢？

最好情况：删除表尾元素，不需要移动其他元素

i=n，循环0次；最好时间复杂度=O(1)

最坏情况：删除表头元素，需要将后续的n-1个元素全都向前移动i=1，循环 n-1次；最坏时间复杂度=0(n)；

平均情况：假设删除任何一个元素的概率相同，即i=1,2,3,…,length的概率都是p=1/n，

i=1，循环 n-1次；i=2 时，循环 n-2 次；i=3，循环 n-3 次…i=n时，循环0次

平均时间复杂度=O(n)

 写代码要注意：

1.题目中的i是位序i（从1开始），还是数组下标i（从0开始），例如，第3个元素其实数组下标为2。

2.算法要有健壮性，注意判断i的合法性。

顺序表的按位查找：

//静态分配方式
#define MaxSize 10
typedef struct{
    int data[MaxSize];
    int length;
} SqList;

ElemType GetElem(SqList L,int i){
    return L.data[i-1];
}


//动态分配
#define InitSize 10
typedef struct{
    ElemType *data;
    int MaxSize;
    int length;
} SeqList;

ElemType GetElem(SeqList L,int i){
    return L.data[i-1];
}

对于ElemType *data，如果一个ElemType 占6B,即 sizeof(ElemType)==6，指针 data 指向的地址为 2000。

如图所示，计算机会根据指针所指向数据类型的空间大小，计算每个数组下标对应哪些字节的数据。

例如int型变量：

这就可以解释：L.data=(int *)malloc(InitSize*sizeof(int))，使用malloc分配内存空间时需要强制转换数据类型，虽然指针指向的是同一个地址，但是指针指向的数据类型定义错误，访问元素的时候也会出现错误。

按位查找的时间复杂度：O(1)，由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素，这也体现了顺序表随机存取的特性。

顺序表的按值查找：

#define InitSize 10
typedef struct{
    ElemType *data;
    int MaxSize;
    int length;
} SeqList;

ElemType LocateElem(SeqList L,ElemType e){
    for(int i=0;i<L.length;i++)
        if(L.data[i]==e)
            return i+1;    //数组下标为i的元素值等于e,返回其位序i+1
    return 0;    //退出循环，说明查找失败

}

注意：“==”不能比较两个结构体类型：

需要依次对比各个分量比较两个结构体是否相等： 

按值查找的时间复杂度：

最好情况：目标元素在表头
循环1次；最好时间复杂度=O(1)

最坏情况：目标元素在表尾
循环n次；最坏时间复杂度=O(n)

平均情况：假设目标元素出现在任何一个位置的概率相同，都是1/n

目标元素在第1位，循环1次；在第2位，循环2次；…在第n位，循环n次

平均时间复杂度为：O(n)

顺序表的特点：

①随机访问，即可以在 O(1)时间内找到第i个元素。

②存储密度高，每个节点只存储数据元素。

③拓展容量不方便(即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高)。

④插入、删除操作不方便，需要移动大量元素。

（2）单链表

逻辑结构为线性表的数据，物理上也能采用链式存储的方式。

顺序表：

优点:可随机存取，存储密度高

缺点:要求大片连续空间，改变容量不方便

单链表：

优点:不要求大片连续空间，改变容量方便

缺点:不可随机存取，要耗费一定空间存放指针

•单链表的实现

struct LNode{    //定义单链表结点类型
ElemType data;   //每个节点存放一个数据元素
struct LNode *next;    //指针指向下一个节点
};

//增加一个新的结点:在内存中申请一个结点所需空间，并用指针p指向这个结点
struct LNode *p=(struct LNode *)malloc(sizeof(struct LNode));

每次写代码时都要写struct LNode比较麻烦，可以使用typedef关键字对数据类型重命名：
typedef struct LNode LNode；

这样：

struct LNode *p=(struct LNode *)malloc(sizeof(struct LNode));

可以写为：

LNode *p=(LNode *)malloc(sizeof(LNode));

以下两个代码都表示，定义了一个struct LNode的数据类型，接着将struct LNode重命名为LNode，并且用LinkList表示指向struct LNode的指针。

struct LNode{
    ElemType data;
    struct LNode *next;
 };
typedef struct LNode LNode;
typedef struct LNode *LinkList;

//更简洁地：
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

要表示一个单链表时，只需声明一个头指针L，指向单链表的第一个结点

LNODE * L;    //声明一个指向单链表第一个结点的指针
或者
LinkList L;


typedef struct LNode{    //定义单链表节点类型
    ElemType data;       //每个节点存放一个数据元素
    struct LNode *next;  //指针指向下一个节点    
}LNode,*LinkList;

//这里用LNode* 和 LinkList 表示都可以，只是前面用LNode*强调返回的是一个结点，后面用LinkList强调返回的是一个单链表
LNode * GetElem(LinkList L,int i){
    int i;
    LNode *p=L->next;
    if(i=0)
        return L;
    if(i<1)
        return NULL;
    while(p!=NULL && j<i){
        p=p->next;
        j++;
   
    }
    return p;
}

不带头结点的单链表：

typedef struct LNode{
    ElemType data;
    struct Lnode *next;
}LNode,*LinkList;

//初始化一个空的单链表
bool InitList(LinkList &L){
    L = NULL;    //空表，暂时还没有任何结点,设为NULL的目的是防止遗留的脏数据
    return true;
}

void test(){
    LinkList L;    //声明一个单链表指针
    InitList(L);
}

//判断单链表是否为空
bool Empty(LinkList L){
    if(L == NULL)
        return true;
    else
        return false;
}
//或者，直接写为
bool Empty(LinkList L){
    return(L=NULL);
}

带头结点的单链表：

typedef struct LNode{
    ElemType data;
    struct Lnode *next;
}LNode,*LinkList;

//初始化一个空的单链表
bool InitList(LinkList &L){
    L=(LNode *)malloc(sizeof(LNode));    
    if(L==NULL)
        return false;
    L->next=NULL;    //头结点之后暂时还没有节点
    return true;
}

void test(){
    LinkList L;    //声明一个单链表指针
    InitList(L);
}

//判断单链表是否为空
bool Empty(LinkList L){
    if(L->next == NULL)
        return true;
    else
        return false;
}
//或者，直接写为
bool Empty(LinkList L){
    return(L->next == NULL);
}

 注：头结点是不存储数据的，设置头结点只是为了后续处理更加方便。因为不带头结点的话，对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑。对空表和非空表的处理也需要用不同的代码逻辑。

单链表的插入：

▴按位序插入（带头结点）

带头结点插入时，若想在i=1时，插入一个新的结点，那么就可以将头结点看作“第0个”结点，使用和后续结点一样的处理逻辑，不带头结点则不行。

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

//在第i个位置插入元素e(带头结点)
bool ListInsert(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 个结点
//因为要在第i个位置插入，所以要找到第i-1个结点，在i-1个结点后插入
        p=p->next;
        j++;
    }
    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，即插在表头

因为i=1，不满足j<i-1，不会跳到while(p!=NULL && j<i-1)

LNode *s=(LNode*)malloc(sizeof(LNOde));//申请一个结点空间

s->data=e;//将参数e放到这一结点空间中

s->next=p->next;//s指向结点的next指针等于p结点next指针指向的位置

p->next=s;//p结点的next指针指向新结点

这种情况，因为i=1，while循环直接被跳过，所以时间复杂度为O(1)，这也是最好时间复杂度。

如果i=5，那么就是在第四个结点后插入：

s->next=p->next; //s的next指针指向p的next指针，由于p结点的next指针指向的是NULL，所以s的next指针也指向NULL

p->next=s;//最后，p的next指针指向新的结点

将新结点插到表尾，即最坏时间复杂度，为O(n)

平均时间复杂度也为O(n)

如果i=6，那么在while循环中j=5时，p==NULL，就会进入if循环，跳出循环：

if(p==NULL)    //i值不合法
        return false;

注：

s->next=p->next;        ①

p->next=s;          ②

两句不能颠倒，如果先让p的next指针指向s，即执行②，再让s的next指针指向p的next指针，就会出现如下情况：

▴按位序插入（不带头结点）

不带头结点的插入中不存在“第0个”结点，所以i=1时需要特殊处理：

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

//在第i个位置插入元素e(不带头结点)
bool ListInsert(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;    
    int j=1;     //这里j=1
    p = L;       
    while(p!=NULL && j<i-1){    
        p=p->next;
        j++;
    }
    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

        LNode *s=(LNode *)malloc(sizeof(LNode));
        s->data=e;

接着将新节点的next指针指向L所指向的结点

        s->next=L;

最后修改头指针L，使L指向新的结点

        L=s;

所以，如果不带头结点，则插入、删除第1个元素时，需要更改头指针L（L=s），如果带头结点的话，头指针永远都是指向头结点的。

后续i>1的情况，与带头结点的处理是相同的，只是需要注意，int j=1，即p指针刚开始指向的是第一个结点：

而带头结点，刚开始指向的是第“0”个结点：

▴指定结点的后插操作

由于单链表只能往后寻找，所以单链表p结点后的元素都是可知的，利用循环的方式可以知道后续元素的值。而p结点前的值是不知道的。

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

//后插操作:在p结点之后插入元素e
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;
}

时间复杂度为O(1)

实现后插操作后,可以直接写为：

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

//后插操作:在p结点之后插入元素e
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个位置插入元素e(带头结点)
bool ListInsert(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 个结点
//因为要在第i个位置插入，所以要找到第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;    //插入成功
*/
}

▴指定结点的前插操作

之前说过单链表只知道p结点后的元素，那么如何找到p的前驱结点呢？

可以传入头指针

bool InsertPriorNode(LinkList L,LNode *p,ElemType e)

传入头指针后，整个链表的信息就都能知道了。具体操作是遍历整个单链表，找到结点p的前驱节点，在前驱结点后插入元素e

时间复杂度为O(n)

如果没有传入头结点，可以这样实现：

//前插操作:在p结点之前插入元素 e
bool InsertPriorNode(LNode *p,ElemType e){
    if (p==NULL)
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));
    if(s==NULL)//内存分配失败
        return false,
    s->next=p->next;
    p->next=s;    //新结点 s连到 p 之后
    s->data=p->data;
    p->data=e;    //将p中元素复制到s中
    return true;    //p 中元素覆盖为 e

 首先申请一个新的结点，并把这一结点作为p结点的后继节点：

接着，将p结点(p指针指向的结点)存放的元素x，复制到新的结点中：s->data=p->data;

最后将要新插入的元素e覆盖原来p结点存放的元素x：

这样，即使没有传入头结点，也可以完成前插操作。

并且这一实现方式的实现方式是O(1)，而上一种实现方式是O(n)。

王道书中的写法是这样的，但是思路是一致的。

//前插操作:在p结点之前插入结点 s
bool InsertPriorNode(LNode *p,LNode *s){
    if(p==NULL s==NULL)
        return false;
    s->next=p->next;
    p->next=s;    //s连到p之后
    ElemType temp=p->data;    //交换数据域部分
    p->data=s->data;
    s->data=temp;
    return true;
}

单链表的删除：

注：对于删除结点的操作只探讨带头结点的情况

▴按位序删除（带头结点）

具体地将头结点看作"第0个"结点，找到第 i-1 个结点，将其指针指向第 i+1 个结点，并释放第i个结点。

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

bool ListDelete(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++;
    }

    if(p==NULL)    //i值不合法
        return false;
    if(p->next == NULL)   //第i-1个结点之后已无其他结点
        return false;
    LNode *q=p->next;    //令q指向被删除结点
    e = q->data;         //用e返回元素的值
    p->next=q->next;     //将*q结点从链中“断开”
    free(q);             //释放结点的存储空间
    return true;         //删除成功
}

如果i=4，经过while循环后，p会指向第3个结点（i-1个结点）：

将q指针指向p结点的next元素，即第i个结点：LNode *q=p->next

接下来会把q指针指向的结点中的元素复制给变量e：e=q->data

最后将p的next指针指向q的next指针，并且释放q：

p->next=q->next;

free(q);

▴按位序删除（不带头结点）

不带头结点的删除，若删除第一个元素，那么需要更改头指针，和不带头结点的操作类似：

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

bool ListDelete(LinkList &L,int i,ElemType &e){
    if(i<1)
        return false;
    
    if (i == 1) {
        if (L == NULL)  // 判断链表是否为空
            return false;
        LNode *q = L;
        e = q->data;
        L = L->next;    // 将头指针指向第一个结点的下一个结点
        free(q);        // 释放第一个结点的内存空间
        return true;
    }

    LNode *p;    
    int j=1;
    p = L;  
    while(p!=NULL && j<i-1){     //循环找到第 i-1 个结点
        p=p->next;    
        j++;
    }

    if(p==NULL)    //i值不合法
        return false;
    if(p->next == NULL)   //第i-1个结点之后已无其他结点
        return false;
    LNode *q=p->next;    //令q指向被删除结点
    e = q->data;         //用e返回元素的值
    p->next=q->next;     //将*q结点从链中“断开”
    free(q);             //释放结点的存储空间
    return true;         //删除成功
}

删除操作的最坏，平均时间复杂度：O(n)

最好时间复杂度：O(1)

▴指定结点的删除

如果要删除结点p，需要修改前驱结点的next指针：

可以传入头指针，循环寻找p的前驱，也可以进行类似于前插的操作：

//删除指定结点 p
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;
}

声明结点q，指向p的后继结点：LNode *q=p->next;

 

把p结点后继结点的数据复制到p结点中：p->data=p->next->data;

将p结点的next指针，指向q结点之后的位置：p->next=q->next;

将q结点释放，将内存归还给系统：free(q);

时间复杂度：O(1)

若删除的结点时最后一个结点，那么代码执行到：p->data = p->next->data 就会出错，因为找不到p结点的后继结点，这样的话，只能从表头开始依次寻找p的前驱，时间复杂度:O(n)。

单链表的查找：

▴按位查找

//按位查找，返回第 1个元素(带头结点)
LNode * GetElem(LinkList L,int i){
    if(i<0)
        return NULL;
    LNode *p;     //指针p指向当前扫描到的结点
    int j=0;      //当前p指向的是第几个结点
    p = L;        //L指向头结点，头结点是第0个结点(不存数据)
    while(p!=NULL && j<i){ //循环找到第 1 个结点
        p=p->next;    
        j++;
    }
    return p;
}

①如果p的值=0，那么会跳过while循环

②如果i的值大于链表的实际长度，例如i=8，最后返回NULL

按位查找平均时间复杂度：O(n)

王道书是这样写的，实现效果是一样的：

LNode * GetElem(LinkList L,int i){
    int j=1;
    LNode *p=L->next;
    if(i==0)    //当i的值为0时，返回头节点
        return L;
    if(i<1)
        return NULL;
    while(p!=NULL && j<i){
        p=p->next;
        j++;
    }    
    return p;
}

只是p结点刚开始是指向第1个节点，而不是第0个节点：

有了查找的功能，按位插入和按位删除中的查找操作，就可以直接调用这个函数实现：

//后插操作:在p结点之后插入元素e
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个位置插入元素e(带头结点)
bool ListInsert(LinkList &L,int i,ElemType e){
    if(i<1)
        return false;
    LNode *p=GetElem(L,i-1); //找到第i-1个结点
    return InsertNextNode(p,e);    //p后插入新元素e
}

//删除第i个位置的元素e
bool ListDelete(LinkList &L,int i,ElemType &e){
    if(i<1)
        return false;
    LNode *p=GetElem(L,i-1);

    if(p==NULL)    //i值不合法
        return false;
    if(p->next == NULL)   //第i-1个结点之后已无其他结点
        return false;
    LNode *q=p->next;    //令q指向被删除结点
    e = q->data;         //用e返回元素的值
    p->next=q->next;     //将*q结点从链中“断开”
    free(q);             //释放结点的存储空间
    return true;         //删除成功
}

▴按值查找

//按值查找，找到数据域==e 的结点
LNode *LocateElem(LinkList L,ElemType e){
    LNode *p =L->next;    //从第1个结点开始查找数据域为e的结点
    while(p != NULL && p->data != e)
        p = p->next;
    return p;    //找到后返回该结点指针，否则返回NULL，如果返回NULL表示不存在要查找的值
}

按值查找的时间复杂度为O(n)

单链表的长度：

//求表的长度
//带头结点
int Length(LinkList L){
    int len =0;//统计表长
    LNode *p =L;
// 遍历链表，统计节点个数
    while(p->next != NULL){
        p = p->next;
        len++;
    }
    return len;
}

//不带头结点
int Length(LinkList L) {
    int len = 0; // 统计链表长度
    LNode* p = L;
   
    if (p == NULL) {
        return len;
    }

    while (p != NULL) {
        len++;
        p = p->next;
    }
    
    return len;
}

求表的长度，时间复杂度O(n) 

单链表的两种建立方法：

▴尾插法建立单链表

就是每次取一个数据元素，插入到表尾：

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*LinkList;

//初始化一个单链表(带头结点)
bool InitList(LinkList &L){
    L=(LNode *)malloc(sizeof(LNode));    //分配一个头结点
    if(L==NULL)//内存不足，分配失败
        return false;
    L->next = NULL;//头结点之后暂时还没有节点
    return true;


// 尾部插入节点（带头结点）
LinkList TailInsert(LinkList &L) {
    L = (LinkList)malloc(sizeof(LNode)); // 建立头结点
    L->next = NULL; // 头结点的next指针初始化为NULL
    int x;
    LNode *s, *r = L; // r为表尾指针
    printf("请输入节点的值，输入9999表示结束：\n");
    scanf("%d", &x); // 输入结点的值
    while (x != 9999) { // 输入9999表示结束
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s; // 将新节点链接到链表尾部
        r = s; // 更新表尾指针
        scanf("%d", &x);
    }
    r->next = NULL; // 将表尾节点的next指针设置为NULL
    return L;
}


// 尾部插入节点（不带头结点）
LinkList TailInsert(LinkList &L) {
    L = NULL; // 初始化链表为空
    int x;
    LNode *s, *r = NULL; // r为表尾指针
    printf("请输入节点的值，输入9999表示结束：\n");
    scanf("%d", &x); // 输入结点的值
    while (x != 9999) { // 输入9999表示结束
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = NULL;

        if (L == NULL) {
            L = s; // 第一个节点直接作为链表头
        } else {
            r->next = s; // 将新节点链接到链表尾部
        }

        r = s; // 更新表尾指针
        scanf("%d", &x);
    }
    return L;
}

这里假设输入的值为10，也就是x=10，首先申请一个新的结点，并用s指针指向这一新结点

接着让这一新结点的值为x：s->data=x; 并且让r指向的结点的next指针指向向s：r->next=s;

最后让r指针指向s：r=s;表示现在的表尾为s指向的结点，即r指针永远指向链表最后一个结点

依次类推，若最后用户输入9999，那么r->next=NULL,最后返回这一链表

尾插法时间复杂度为O(n)

▴头插法建立单链表

头插法每插入一个元素就是对头结点的后插操作：

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*LinkList;

//初始化一个单链表(带头结点)
bool InitList(LinkList &L){
    L=(LNode *)malloc(sizeof(LNode));    //分配一个头结点
    if(L==NULL)//内存不足，分配失败
        return false;
    L->next = NULL;//头结点之后暂时还没有节点
    return true;

//头插法（带头结点）
LinkList 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;    //将新结点插入表中，L为头指针
        scanf("%d",&x);
    }
    return L;
}

//头插法（不带头结点）
LinkList HeadInsert(LinkList &L) {
    L = NULL; // 初始化链表为空
    LNode *s;
    int x;
    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode *)malloc(sizeof(LNode)); // 创建新结点
        s->data = x;
        s->next = L; // 将新结点插入链表头部

        L = s; // 更新链表头指针为新结点

        scanf("%d", &x);
    }
    return L;
}

注意：对于L->next=NULL

在尾插法中不写这一句不会有影响，因为元素是插在链表的尾部，但是使用头插法就一定不能缺这句代码：

若没有写这句话，头结点的next指针可能指向未知的区域：

接下来执行s->next=L->next;

最后头结点指向新的结点：

其他新结点插入的情况类似，最后的结点的next指针会指向未知的结点：

所以无论再写尾插法还是头插法，都建议初始化单链表，将头指针指向NULL，即

L->next=NULL;

使用头插法产生的结果是输入元素的逆序：

如果需要单链表逆置，就可以用头插法。

（3）双链表

单链表无法逆向检索，所以找前驱结点会比较麻烦，双链表可以双向检索，就不会存在这个问题：

双链表在单链表的基础上加入了一个指针prior,指向前驱结点： 

typedef struct DNode{    //定义双链表结点类型
    ElemType data;    //数据域
    struct DNode *prior,*next;    //前驱和后继指针
}DNode,*DLinklist;

• 双链表的实现

双链表的初始化：

typedef struct DNode{    //定义双链表结点类型
    ElemType data;    //数据域
    struct DNode *prior,*next;    //前驱和后继指针
}DNode,*DLinklist;

//初始化双链表
bool InitDLinkList(DLinklist &L){
    L=(DNode *)malloc(sizeof(DNode));     //分配一个头结点
    if(L==NULL)    //内存不足，分配失败
        return false;
    L->prior = NULL;    //头结点的 prior 永远指向 NULL
    L->next = NULL;    //头结点之后暂时还没有节点
    return true;
}

void testDLinkList(){
//初始化双链表
    DLinklist L;
    InitDLinkList(L);
}

//判断双链表是否为空(带头结点)
bool Empty(DLinklist L){
    if(L->next == NULL)    
        return true;
    else
        return false;
}

双链表的插入：

//在p结点之后插入s结点
bool InsertNextDNode(DNode *p,DNode *s){
    if(p==NULL || S==NULL)    //非法参数
        return false;
    s->next=p->next;
    if(p->next != NULL)    //如果p结点有后继结点
        p->next->prior=s;
    s->prior=p;
    p->next=s;    
    return true;
}

① 首先将s的next指针指向p的next指针指向的结点：s->next=p->next;

② 如果p没有后继结点，直接跳到接下来步骤③。如果有后继节点，就将p结点的后继结点的前项指针指向s：p->next->prior=s;

③ 接下来将s的前项指针指向p结点：s->prior=p;

④ 最后将p的后项指针指向s结点：p->next=s;

修改指针时要注意顺序，例如：

如果按④ ①执行：

首先p的next指针指向s结点：

再让s的next指针指向p的next指针指向的结点：

当我们进行按位插入时，只需要从头结点开始，找到某个位序的前驱结点，然后对前驱结点进行后插操作接口。但我们想在某点前做前插操作，由于双链表的特性，我们可以很方便地找到某一点地前驱结点，接着对前驱结点执行后插操作即可。

所以其他的插入操作都可以转换为用后插实现。

双链表的删除：

//删除p结点的后继结点
bool DeleteNextDNode(DNode *p){
    if(p==NULL)
        return false;
    DNode *q= p->next;    //找到p的后继结点q
    if(q==NULL)    //p没有后继
        return false;
    p->next=q->next;
    if (q->next!=NULL)    //q结点不是最后一个结点
        q->next->prior=p;
    free(q);    //释放结点空间
    return true;
}

声明q指针，指向p的后继结点。如果p没有后继，即q==NULL，返回false，否则：

① p结点的next指针会指向q结点的next指针指向的位置，也就是指向q的后继结点：

p->next=q->next;

如果q不是最后一个结点，修改q的后继结点的前项指针，执行②；如果q是最后一个结点，就会直接执行③

② q节点的后继结点的前项指针指向p结点：

q->next->prior=p;

③ 释放q结点：free(q)

q是最后一个结点，直接执行③的结果：

双链表的销毁：

void DestoryList(DLinklist &L){    //循环释放各个数据结点
    while(L->next != NULL)
        DeleteNextDNode(L);    //删除头结点的后继结点
    free(L);    //最后释放头结点
    L=NULL;    //头指针指向NULL
}

 双链表的遍历：

//后向遍历
while (p!=NULL){    //对结点p做相应处理，如打印
    p= p->next;
}

//前向遍历
while (p!=NULL){    //对结点p做相应处理
    p= p->prior;
}

//若只想处理数据结点，不想处理头结点
while (p->prior!=NULL){    //如果p结点的前项指针指的是NULL的话，表明p指针此时指向的是头结点
    p= p->prior;
}

 双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方式实现。时间复杂度O(n)

（4）循环链表

• 循环单链表

之前学习的单链表最后一个结点的next指针指向的是NULL，而循环单链表最后一个结点的next指针指向的是头结点。

所以初始化单链表时，要将头结点的指针指向自己：

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

//初始化一个循环单链表
bool InitList(LinkList &L){
    L=(LNode *)malloc(sizeof(LNode));    //分配一个头结点
    if (L==NULL)    //内存不足，分配失败
        return false;
    L->next = L;    //头结点next指向头结点
    return true;
}

//判断循环单链表是否为空
bool Empty(LinkList L){
    if(L->next == L)
        return true;
    else
        return false;
}

//判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L,LNode *p){
    if (p->next==L)
        return true;
    else
        return false;
}

对于单链表而言，从一个结点出发只能找到后续的各个结点。对于循环单链表而言，从一个结点出发可以找到其他任何一个结点。

对于单链表而言，从头结点找到尾部，时间复杂度为O(n)，对于循环单链表而言，如果指针L不指向头结点，而是指向尾部结点，那么从尾结点出发找到头部结点只需要O(1)的时间复杂度。并且，如果需要对链表尾部进行操作，也可以在O(1)的时间复杂度找到操作的位置。 

如果应用场景中需要经常对表头或表尾进行操作，使用循环单链表时，可以让L指向表尾元素。这样的话，如果想在表尾进行插入，删除时，就需要修改L。

• 循环双链表

双链表：表头结点的 prior指向 NULL；表尾结点的next指向NULL。
循环双链表：表头结点的prior指向表尾结点；表尾结点的next指向头结点。

所以初始化双链表时，需要让头结点的前项指针和后项指针都指向头结点自己，也就是头结点既是第一个结点，也是最后一个结点。

typedef struct DNode{
ElemType data;
struct DNode *prior,*next;
}DNode, *DLinklist;

//初始化空的循环双链表
bool InitDLinkList(DLinklist &L){
    L=(DNode *)malloc(sizeof(DNode));    //分配一个头结点
    if(L==NULL)    //内存不足，分配失败
        return false;
    L->prior =L;    //头结点的 prior 指向头结点
    L->next = L;    //头结点的 next 指向头结点
    return true;
}

//判断循环双链表是否为空
bool Empty(DLinklist L){
    if(L->next == L)
        return true;
    else
        return false;
}

//判断结点p是否为循环双链表的表尾结点
bool isTail(DLinklist L,DNode *p){
    if(p->next == L)
        return true;
    else
        return false;
}

void testDLinkList(){
    //初始化循环双链表
    DLinklist L;
    InitDLinkList(L);
}

 双链表的插入：

//在p结点之后插入s结点
bool InsertNextDNode(DNode *p,DNode *s){
    s->next=p->next;    //将结点*s插入到结点*p之后
    p->next->prior=s;
    s->prior=p;
    p->next=s;
}

对于普通的双链表会出现错误：

当p结点刚好是表尾结点时，p->next->prior=s;这句代码会出现错误，因为p结点没有后继结点了。

但如果使用的是循环双链表，这个逻辑就是对的，因为即便p结点是表尾结点，他的next指针指向的结点是非空的，将p的后继结点的前项指针指向s是没问题的。

双链表的删除：

双链表的删除同理：

∥删除p的后继结点q
p->next=q->next;
q->next->pior=p;
free(q);

 普通的双链表中，执行q->next->prior=p;会出现错误。而使用循环双链表则没有问题

（5）静态链表

 •静态链表的相关概念

单链表中的各个结点是离散分布在内存中的各个角落，每个结点会存放一个数据元素，以及指向下一个结点的指针（地址）。

静态链表则分配一整片连续的内存空间，各个结点集中安置。每个结点会存放一个数据元素，以及下一个结点的数组下标（游标）。

在静态链表中，0号结点充当“头结点”，头结点中不存放数据元素，而头结点的下一个结点被存放在了数据下标为2的位置。再往后的结点就是数组下标为1的结点，以此类推。所以静态链表中的数组下标（游标），和单链表中的指针作用是相同的。

区别是，指针指明的是下一个结点的地址，而游标指明的是下一个结点的数据下标。

在单链表中，表尾结点的指针是指向NULL的，而在静态链表中，表尾结点指向-1，表示静态链表后没有其他结点了。

因为静态链表中各个结点是连续存放的，如果每个数据元素4B，每个游标4B(每个结点共8B)。设起始地址为 addr。那么数组下标为2的结点的存放地址就是addr+8*2。

这样就能把静态链表中的数组下标，映射为某个数组下标对应结点的实际存放位置。

 •静态链表的定义

#define Maxsize 10    //静态链表的最大长度
struct Node{          //静态链表结构类型的定义
    ElemType data;     //存储数据元素
    int next;         //下一个元素的数组下标
};

void testSLinkList(){
    struct Node a[Maxsize];    //数组a作为静态链表
}

王道书上是这样写的：

#define Maxsize 10
typedef struct {
    ElemType data;
    int next;
}SLinkList[Maxsize];
//等价于
#define Maxsize 10
struct Node{
    ElemType data;
    int next;
};
typedef struct Node SLinkList[Maxsize];
//可用 sLinkList 定义“一个长度为 MaxSize 的Node 型数组”


//当我们声明一个SLinkList a时,其实是声明了一个数组
//这个数组的元素个数为MaxSize，每个数组元素就是一个Struct Node结构体
void testSLinkList(){
    SLinkList a;
}
//等价于
void testSLinkList(){
    struct Node a[MaxSize];
}
//使用“SLinkList a”的写法强调的是a是静态链表

 •静态链表的相关基本操作

（1）初始化静态链表：将a[0]的next设为-1。在内存中没有存放数据的地方，其实都存放着脏数据，可以在初始化时让其它结点的next为某个特殊值用来表示结点空闲。例如-2，若某个结点的游标是-2，则表明这一结点时空闲的，可以用这个结点存放新的数据元素。

（2）查找：从头结点出发挨个往后遍历结点。所以查找某个位序的结点的平均时间复杂度为O(n)

（3）插入：

① 找到一个空的结点，存入数据元素。

② 从头结点出发找到位序为i-1的结点。

③ 修改新结点的next。

④ 修改i-1号结点的next。

（4）删除：

① 从头结点出发找到前驱结点。

② 修改前驱结点的游标。

③ 被删除结点 next 设为 -2。

总结：

虽然静态链表的存储空间是一整片的，连续的存储空间，但是这片空间内，逻辑上相邻的数据元素，在物理上可以不相邻，各个数据元素之间逻辑关系是由游标来指明的。

优点：增、删操作不需要大量移动元素，只要修改相关数据元素的游标即可。

缺点：不能随机存取，只能从头结点开始依次往后查找；容量固定不可变，只要声明了一个静态链表，他所能存放的最大容量就被固定了。

适用场景:①不支持指针的低级语言②数据元素数量固定不变的场景(如操作系统的文件分配表FAT)

（6）顺序表和链表的对比

1.逻辑结构

顺序表和链表在逻辑上都是线性结构的，都属于线性表。

2.物理结构（存储结构）

顺序表：

顺序表采用了顺序存储的方式，并且各个数据元素的大小相等，由于这两个条件，只需要知道顺序表的起始地址，就可以找到第i个元素存放的位置。也就是顺序表具有随机存取的特性。

并且顺序表中的各个结点，只需要存储各个元素本身，不需要存储其他的冗余信息。因此顺序表存储密度高。

顺序存储的结构要求系统分配大片连续的存储空间，所以分配空间时不方便。改变容量也不方便。

链表：

若采用链式存储的方式实现线性结构，由于各个结点可以离散地存放在内存空间中，所以要添加一个元素时，只需要用malloc函数动态申请一小片空间即可，这样分配空间就比较方便。由于各个结点的存储空间不要求连续，因此改变容量也较为方便。

但是链式存储中要查找第i个结点时，只能从表头开始遍历寻找，所以不可随机存取。并且由于各个结点除了存储数据元素外，还需要花费一定空间存储指针，所以存储密度较低。

3.数据运算/基本操作

 •初始化

顺序表：

1.由于顺序表初始化需要一整片的内存空间，所以需要预分配大片连续空间，若分配空间过小，则之后不方便拓展容量;若分配空间过大，则浪费内存资源。

2.若顺序表采用静态分配，那么静态数组的容量是固定的。即便采用动态分配的方式，更改动态数组的容量也需要移动大量的元素，时间代价高。

链表：

1.初始化链表时，只需分配一个头结点(也可以不要头结点，只声明一个头指针)，之后方便拓展。

采用链表，存储空间更加灵活。

 •销毁

顺序表：

1.首先将length=0，这步操作只是在逻辑上把顺序表置空。但是顺序表占用的存储空间还没有回收。

2.若采用静态分配，就意味着顺序表占用的存储空间是通过声明静态数组的方式请求系统分配的。这种情况下，系统会自动回收空间。

3.若采用动态分配的方式，也就是使用malloc函数申请的一片内存空间，那么就需要用free函数手动释放空间。因为malloc函数申请的空间属于内存的堆区，堆区的内存空间系统不会自动回收。

L.data =(ElemType *)malloc(sizeof(ElemType)*InitSize)
free(L.data);

链表：

通过free函数，利用循环依次删除各个结点。

注：malloc和free必须成对存在。

 •增删

顺序表：

1.由于顺序表中的各个元素在内存中是相邻并且有序的，所以在插入/删除元素要将后续元素都后移/前移。

2.顺序表的插入时间复杂度和删除时间复杂度都是O(n)，时间开销主要来自移动元素。若数据元素很大，则移动的时间代价很高。

链表：

1.插入/删除元素只需修改指针即可。

2.链表的时间复杂度也为 O(n)，时间开销主要来自查找目标元素。查找元素的时间代价相比于移动大量元素的时间代价更低。

所以虽然顺序表和链表的插入，删除操作时间复杂度都为O(n)，但是实际上，链表的效率比顺序表高得多。

 •查找

顺序表：

1.顺序表具有随机存取的特性，采用按位查找的时间复杂度为O(1)。

2.采用按值查找，时间复杂度为O(n)，若表内元素有序，采用安值查找，那么可在O(log2n)时间内找到（采用折半查找等方式）。

链表：

1.链表只能从第一个数据元素开始依次遍历查找，按位查找时间复杂度为O(n)。

2.按值查找，也只能从第一个数据元素依次往后遍历，时间复杂度为O(n)。

所以查找操作中顺序表效率高很多。

 •总结：

1.如果线性表表长难以估计，并且经常需要增加/删除元素，那么就使用链表。

2.如果线性表表长可预估，查询(搜索)操作比较多。那么就采用顺序表。文章来源地址https://www.toymoban.com/news/detail-853552.html

到了这里，关于数据结构（二）----线性表（顺序表，链表）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！