关于线性表的点点滴滴

Asolmn

2022-01-23

数据结构

表

线性表

本文部分截图来自王道考研
书籍参考：[1]王晓东.数据结构（语言描述）[M].北京：电子工业出版社.2019前言

前言

线性表是一种非常灵便的结构，可以根据需要改变的表的长度，也可以在表中任何位置对元素进行访问、插入、删除等操作。还可以将多个表连接成为一个表，也可以对一个表进行拆分成多个表。

线性表的定义，是具有相同数据类型的$n(n \geq 0)$个数据元素组成的有限序列，其中元素$n$的个数定义为表的长度。当$n=0$时，线性表是一个空表，当$n \geq 1$时，称元素$a(k)$位于该表的第$k$个位置。若用L命名线性表，则其一般表示为

$$
L=(a_1,a_2,…..,a_i,a_{i+1},…..,a_n)
$$

除此之外，还要定义一些关于线性表的运算，将这一个数学模型成为一个抽象数据List。用$x$表示表中的一个元素，$k$表示元素在表中的位置。

InitList(&L)：初始化表，创建一个新的线性表$L$，分配内存空间
Destroy(&L)：销毁线性表，释放$L$所占的内存空间
ListEmpty(&L) ：测试表$L$是否为空
ListLength：表$L$的长度
ListLocate(&x,&L)：元素$x$在表中$L$的位置，如果$x$在表中重复出现，返回最前面的
ListRetrieve(&k,&L)：返回$L$中的$k$处位置的元素
ListInsert(&k,&x,&L)：在表$L$的k处位置插入元素$x$，将原来占据该位置的元素及其后面都向后推一个位置
ListDelete(&k,&L)：将表$L$的$k$处位置的元素删除，并返回删除的元素。
PrintList(&L)：将表$L$中的所有元素按照位置顺序打印输出

顺序表（数组实现）

定义

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

这种方法，容易实现对表的遍历，在表的尾部插入一个元素很容易。但是如果要在表的头和中间的位置插入一个新元素。那么这个新元素插入位置的后面所有元素都要后移一位，为空出位置，存放新元素。删除以是如此，如果删除的元素不是表的最后一位，那么被删除元素后面的所有元素，都要往前移动一位，填补空缺。

代码实现

顺序表的实现-静态分配

// 定义一个表的结构，ElemType在数据结构表示，任何一种数据类型，并无实际的此类型
// 如果是int类型，将ElemType改为int即可
#define MaxSize 10 // 定义最大长度

typedef struct{
    ElemType data[MaxSize]; // 用静态的数组存放数据元素
    int length; //顺序表当前长度
}SqList; //顺序表的类型定义（静态分配方式）

// 实现代码
// 顺序表-静态分配
#include <stdio.h>

#define MaxSize 10  // 定义最大长度

// 表的类型定义
typedef struct{
    int data[MaxSize]; // 用静态的数组存放数据元素
    int length; // 表的当前长度
}SqList;

typedef SqList *List;

void InitList(List L){
    /* 初始化一个数组 */
    for (int i=0; i<MaxSize; i++){
        L->data[i]=0;  // 将所有数据元素设置为默认初始值 
    }
    L->length=0;
}

int main(){
    List L;
    InitList(L);
    return 0;
}

在IinitList初始化表的函数中，用了一个for函数对每一个元素进行了初始化，如果不怎么会给内存遗留的脏数据污染（如下图）。

静态分配的精髓就是再data[MaxSize]，直接设置一个固定的长度的数组。但是有非常大的缺陷，如果存满的只能放弃这个数组，因为静态数组的表长确定后创建是不能更改的。

顺序表的实现-动态分配

#define InitSize 10 // 顺序表的初始长度
typedef struct{
    ElemType *data; //动态分配数组的指针
    int maxsize; // 顺序表的最大容量
    int length; // 顺序表的当前长度
}SeqList;

c语言实现顺序表的动态分配，主要依靠malloc free两个函数，一个进行动态申请内存空间，一个进行释放内存空间，包含在头文件<stdlib.h>头文件中

#include <stdlib.h>

L->data = (ElemType *)malloc(sizeof(ElemType)*InitSize); // 申请空间
free(L); //释放空间

#include <stdio.h>
#include <stdlib.h>

#define InitSize 10

typedef struct{
    int *data;
    int maxsize;
    int length;

}SeqList;

typedef SeqList *SList;

void InitList(SList L){
    /* 初始化一个动态分配数组 */
    L->data=(int *)malloc(InitSize*sizeof(int)); // 申请InitSize值的内存空间
    L->length = 0;
    L->maxsize = InitSize;
}

void IncreaseSize(SList L,int len){
    /* 增加动态数组的长度 */
    int *p = L->data; //先将原先的数组保存
    L->data = (int *)malloc((L->maxsize+len)*sizeof(int)); // 申请加上len之后的内存空间大小
    for (int i=0; i<L->length; i++){
        L->data[i] = p[i]; //将数据复制到新区域
    }
    L->maxsize = L->maxsize+len; // 顺序表最大长度添加len
    free(p); // 释放原来的内存空间
}

void ListFree(SList L){
    /* 释放表 */
    free(L->data);
    free(L);
}


int main(){
    //动态分配
    SList L;
    InitList(L);
    IncreaseSize(L,5);
    return 0;
}

不管是动态分配还是静态分配，都具有一些相同的特性

随机访问，可以在$O(1)$时间内找到第i个元素
存储密度高，每一个节点只存储数据元素本身

关于顺序表的基本操作

代码实现

表的类型定义

typedef struct alist{
    int n; // 表长
    int MaxSize; // 定义数组长度
    int curr; //当前位置
    int *table; //存放数据元素的数组
}Alist;

typedef Alist *List;

初始化size大小的表

List ListInit(int size){
    /* 初始化表 */
    List L = (List)malloc(sizeof(*L)); //为表L申请一块内存空间
    L->table = (int *)malloc(size*sizeof(int)); // 为表L中存放数据的数组申请一块内存空间
    L->MaxSize = size;
    L->n = 0; // 因为是动态数组，所以先另表长为0
    return L; //返回表L
}

测试表L是否为空

int ListEmpty(List L){
    /* 测试是否为空 */
    return L->n == 0; //如果表L的n等于0，代表表当前长度为0
}

释放表L的所申请的内存空间

void ListFree(List L){
    free(L->table);
    free(L);
}

在表L的k位置处插入元素x

void ListInsert(int k, int x, List L){
    /* 表中插入元素 */
    if (k<1 || k>L->n+1){
    	// 如果插入的位置小于1或者大于表当前长度,返回false
        ListFree(L);
        exit(1);
    }
    if (L->n >= L->MaxSize){
        // 如果插入的位置大于表的最大长度,返回false
        ListFree(L);
        exit(1);
    }
    for (int j=L->n; j>=k; j--){
         // 如果j大于k，那么将k以及后面的元素后移
        L->table[j] = L->table[j-1];
    }
    L->table[k-1] = x; // 在k位置存入x
    L->n++; // 表的当前长度+1
}

删除表中k处的元素

int ListDelete(int k, List L){
    /* 删除k处的元素 */
    if (k<1 || k>L->n) 
        // 如果删除的位置小于1或者大于表当前长度,返回false
        ListFree(L);
        exit(1);
    }
    int x = L->table[k-1];
    for (int i=k; i<L->n; i++){
        // 将所有的值往前移一位
        L->table[i-1] = L->table[i];
    }
    L->n--; // 表长减一
    return x;
}

元素x在表中的位置（按值查找）

int ListLocate(int x, List L){
    /* 元素x在表中的位置 */
    for (int i=0; i<L->n; i++){
        //循环表
        if (L->table[i] == x){
            // 如果第i位的元素，等于x，证明x在i位
            return i+1; // 因为表是从0开始，所以返回位置的时候，要加一位
        }
    }
    return 0;
}

表中k处的元素（按位查找）

int ListRetrieve(int k, List L){
    /* 返回表中k处位置的元素 */
    if (k<1 || k>L->n){
        // 如果调用的函数时，k的参数是小于1，或者大于表长的，则退出程序
        exit(1);
    }
    return L->table[k-1];
}

部分表操作的时空复杂度

插入的时空复杂度

如果插入的地方，为表尾，那么这是最好的情况，时间复杂度为$O(1)$。最坏情况下需要$O(n)$的时间。因为插入的位置可以是表的任意位置，所以需要分析一下平均时间复杂度。设在长度为$n$的表中进行插入，那么所需元素移动次数的平均值为$E_{IN}(n)$。在表中第$k$个位置插入元素x需要移动数组元素$n-k$次。所以
$$
E_{IN}(n)=\sum_{k=0}^nP_k(n-k)
$$
$P_k$表示在表中第$k$个位置插入元素的概率，假设在表中任何合法位置插入元素的机会是均等的，则
$$
P_0=P_1=…=P_n=\frac{1}{n+1}
$$
那么在同等概率下
$$
E_{IN}(n)=\sum_{k=0}^nP_k(n-k)=\sum_{k=0}^n\frac{n-k}{n+1}=\frac{n}{2}
$$
因为使用大n表示法，系数可以忽略，所以平均时间复杂度为
$$
O(n)
$$

删除的时空复杂度

与插入一样，设在长度为$n$的表中删除一个元素，所需要元素移动次数的平均值为$E_{DE}(n)$。删除表中第$k$个位置上的元素移动次数为$n-k$次。所以
$$
E_{DE}(n)=\sum_{k=0}^nQ_k(n-k)
$$
$Q_k$表示在第$k$个位置删除元素的概率，在等概率删除的情况下
$$
Q_1=Q_2=…=Q_n=\frac{1}{n}
$$
所以可知
$$
E_{DE}(n)=\sum_{k=0}^nQ_k(n-k)=\sum_{k=0}^n\frac{n-k}{n}=\frac{n-1}{2}
$$
同样因为是大n表示法，所以平均时间复杂度为
$$
O(n)
$$

链表-单链表

定义

单链表是一种链式存储，由一个个节点构成。每一个节点除了存放数据元素外，还要存放指向下一个节点的指针，用指针依次串联起来。

这种方法不需要大片连续的存储空间，改变容量方便。插入和删除运算时，不在需要移动元素来移动或者填补空缺。但缺点就是因为每一个节点中设置了指针来表示元素之间的逻辑关系，所以增加了一定的空间开销，同时不可以在随机存取。如果表是$ a(1),a(2),(3)….a(n) $，那么元素$a(k)$的指针应指含有元素$a(k+1)$的单元。

代码实现

单链表的实现

// 单链表节点类型
typedef struct LNode{
    ElemType data; // 每一个节点存放一个数据类型 称为数据域
    struct LNode *next; // 指针指向下一个节点 称为指针域
}LNode;

增加一个新的节点，在内存中申请一个节点所需空间，并用指针p指向这个节点

1 2	typedef struct LNode LNode; LNode p = (LNode )malloc(sizeof(struct LNode));

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

// 两种写法
typedef struct LNode *LinkList;
LNode * L;
LinkList L;
// 两种定义方法效果是一样的，用LinkList可读性好一些

不带头节点的单链表

// 单链表-代码
#include <stdio.h>
#include <stdbool.h>

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

// 初始化一个空的单链表
bool InitList(LinkList L){
    /* 初始化单链表 */
    L = NULL; // 空表暂时没有节点
    return true;
}

void testLink(){
    /* 测试不带头节点的单链表 */
    LinkList L; //声明一个指向单链表的指针
    InitList(L); //初始化一个空表
}

int main(){  
	testLink();
    
    return 0;
}

另L=NULL，和之前顺序表的初始化一样，也是为了除去内存遗留的脏数据

带头节点的单链表

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

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

typedef LNode *LinkList;

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

void testHeadLink(){
    /* 测试带头节点的单链表 */
    LinkList L;
    InitHeadList(L);
}

int main(){
    // testLink();
    testHeadLink();

    return 0;
}

其中不带头节点的话，头指针指向的下一个元素存储数据，而带头节点则是头节点是不存储数据的，头节点的下一节点才存储。不带头节点写代码更加麻烦，对第一个数据节点和后续的节点都需要不同的代码逻辑，对空表和非空表的处理也不相同，所以大多数情况，还是使用带头节点的单链表。

关于单链表的基本操作

（除了特别声明，默认操作的都是带头节点的单链表）

代码实现

表的类型定义

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

单链表的初始化

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

按位序插入（在第i位插入元素e）

bool LinkInsert(LinkList L, int i, int 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;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next; //s的next指向原先第i-1节点的下一个节点
    p->next = s; // 将节点s连接到p
    return true;
}

首先定义一个指针p，用于指向当前的节点，定义一个变量j用于表示p是第几个节点。然后在初始化中的头节点L等于p。开始进行循环，将p扫描节点依次后移，直至不满足循环条件，这时指针p就为第i-1个节点，然后定义一个新的节点s，然后s的next指向原先第i-1节点的下一个节点（**如果是一条从头节点开始的全新单链表，那么p的next是NULL，为了考虑到插入的情况，可能是已经前后都含有数据的单链表，所以s的next不能直接设置为NULL，必须设置为p节点的next**），使第i-1个节点的next指向s。

指定节点的后插操作

bool InsertNextNode(LNode *p, int e){
    /*后插操作：在p节点之后插入元素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;
}

这里没有什么可以说的，就是把s的下一个指向等于p的下一个指向，再让p的下一个指向等于节点s。可以扩展一下的就是，可以将后插操作的函数应用到位序插入中

bool LinkInsert(LinkList L, int i, int 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++;
    }
    InsertNextNode(p, e);
}

指定节点的前插操作

bool InsertPriorNode(LNode *p, int e){
    /* 在节点p之前插入元素e */
    if (p==NULL){
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s==NULL){
        return false;
    }
    s->next = p->next; //新节点s连接到p之后
    p->next = s;
    s->data = p->data; // 对p节点和s节点的数据元素进行替换
    p->data = e;
    return true;
}

实现方式可以有两种，一种是传入一个单链表L，然后进行遍历，时间复杂度为$O(n)$。一种将新节点放在指定节点之后，然后对新节点和指定节点的数据元素进行替换，使得逻辑上达到了前插操作，同时将时间复杂度变成了$O(1)$。

按位序删除

int ListHeadDelete(LinkList L, int i){
    if (i<1){
        return false;
    }
    LNode *p; // 指针p指向当前扫到的节点
    int j=0; // 当前p指向的是第几个节点
    p = L; // L指向头节点
    while (p!=NULL && j<i-1){
        // 另p等于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指向被删除节点
    int e = q->data; //e为返回元素的值
    p->next=q->next; // 将*q从链中剔除
    free(q); // 释放节点存储空间
    return e;
}

指定节点的删除

bool DeleteNode(LNode *p){
    /* 删除指定的节点 */
    if (p==NULL){
        return false;
    }
    LNode *q = p->next; // 令q指向*p的后继节点
    p->data = p->next->data; //和后继节点交换数据域，此时p就相当于变成了逻辑意义上的下一个节点
    p->next = q->next; // 再将p的下一个链接到q的下一个
    free(q); //释放q
    return true;
}

这于指定节点的插入，是同样的道理，依旧是运用了数据域内容的交换，实现了逻辑意义上的删除，同时时间复杂度为$O(1)$

按位查找

LNode *GetElem(LinkList L,int i){
    if(i<0){
        return NULL;
    }
    LNode *p;
    int j=0;
    p=L;
    while (p!=NULL && j<i){
        // 循环找到第i个节点，上面的操作和插入一样
        p=p->next;
        j++;
    }
    return p;
}

基本与按位插入是一样的原理，只不过按位插入是循环到底i-1个节点，查找是循环到第i个节点。如果查找的节点刚为第一个的话，那么时间复杂度为$O(1)$，平均时间复杂度为$O(n)$。

按值查找

LNode *LocateElem(LinkList L,int e){
    /* 按值查找 */
    LNode *p = L->next; //令p等于头指针的下一个节点
    while (p!=NULL && p->data !=e){
        // 如果p的数据元素不等于查找值，继续下一个节点，直到满足
        p=p->next;
    }
    return p;
}

因为它是依次往后扫描寻找，当e再第n个位置的时候，那么就循环了n次，所以它的平均时间复杂度为$O(1)$。

单链表的长度

int Length(LinkList L){
    int len=0;
    LNode *p = L;
    while (p->next!=NULL){
        p=p->next;
        len++;
    }
    return len;
}

因为单链表不具备随机访问的特性，是依次查询，所以它的平均时间复杂度为$O(1)$。

单链表的建立

如果有很多个数据元素，要把它们存入到一个单链表中。有两种方法可以实现，一种是尾插法，一种是头插法。

初始化一个单链表，每次取一个元素，插入到表尾/表头

尾插法

LinkList List_Tailnsert(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)); //在r节点之后插入元素s
        s->data = x;
        r->next = s;
        r = s; // 保持r永远是最后一个指针
        scanf("%d",&x);
    }
    r->next = NULL; // 表尾指针指向NULL
    return L; 
}

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

头插法

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);
    } 
}

链表-双链表

定义

单链表中，从表的任一节点出发，都可以找到其前驱结点，但需要$O(n)$的时间。那么可以在链表的每一个结点中设置两个指针，一个指向后继结点，另一个指向前驱结点，称为双链表

代码实现

双链表的实现

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

带头节点的双链表

// 双链表
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

typedef struct DNode{
    int 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);
}

int main(){
    testDLinklist();

    return 0;
}

只是在单链表的基础上，多了一个前驱指针。用来指向上一个结点，剩下基本一样。要注意的是，头结点因为是第一个结点，所它的前驱指针永远是指向NULL的。

关于双链表的基本操作

后插操作

bool InsertNextDNode(DNode *p, DNode *s){
    if (p==NULL || s==NULL){
        // 非法参数
        return false;
    }
    s->next=p->next; // 令p的后继结点等于s的后继结点
    if (p->next!=NULL){
        // 判断是否为表尾，如果是表尾，那么p的下一结点是NULL
        p->next->prior = s; // 令p后继结点的前驱结点等s
    }
    s->prior = p; // s的前驱结点为p
    p->next = s; // p的后继结点为s
    return true;
}

例如p结点的下一结点为k，这时要在p后面插入结点s。首先将p的下一个结点，也就是k，变成s的下一结点。在令k的前驱结点指向s，s的前驱结点指向p，p的下一个结点指向s。这就完成了在原先的p和k中间位置插入了结点s。

删除操作

bool DeleteNextDNode(DNode *p){
    /* 删除p结点的后继结点 */
    if (p==NULL){
        // 验证非法参数
        return false;
    }
    DNode *q = p->next; // 找到p的后继结点q
    if (q=NULL){
        // p没有后继结点
        return false; 
    }
    p->next = q->next; // 令p的后继结点等于q的后继结点
    if (q->next!=NULL){ 
        // 判断q是不是最后一个结点
        q->next->prior = p; // q的后继结点的前驱结点等于p
    }
    free(q);
    return true;
}

销毁一个双链表

void DeleteDLinklist(DLinklist L){
    /* 销毁一个双链表 */
    while (L->next != NUll){
        DeleteDLinklist(L);
    }
    free(L);
    L = NULL;   
}

遍历操作

void PrintDLinklist(DNode *p){
    /* 遍历一个双链表 */
    while (p!=NULL){
        printf("%d",p->data);
        p = p->next;
    }
}

没啥逻辑可说的，就是给定一个结点，然后对结点进行判断是否为NULL，满足循环条件进入循环，打印结点数据，然后将p指向给定结点的下一个结点，时间复杂度为$O(n)$

链表-循环链表

定义

单链表最后一个结点的指针为空指针，循环链表就是将这个空指针指向了头结点。使整个链表形成了一个环，首尾相接。

代码实现

循环单链表的实现

// 循环链表
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

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 = L; // 将头节点的后继结点指向头结点
    return true;
}

int main(){
    
    LinkList L;
    InitList(L);

    return 0;
}

循环双链表的实现

typedef struct DNode{
    int data;
    struct DNode *prior, *next;
}DNode, *DLinkList;

bool InitDLinkList(DLinkList L){
    /* 初始化循环链表 */
    L = (DNode *)malloc(sizeof(DNode));
    if (L==NULL){
        return false;
    }
    L->prior = L; // 头结点的前驱结点指向头结点
    L->next = L; // 头结点的后继结点指向头结点
}

int main(){
    
    DLinkList L;
    InitDLinkList(L);

    return 0;
}

链表-静态链表

定义

设置一个游标，游标是数组中指示数组单元地址的下标值。它指示表中下一个元素在数组中的存储地址（数组下标）。虽然是用数组的方式存储表中的元素，但是插入和删除操作，并不需要移动表中元素，只需要修改游标。

代码实现

静态链表的实现

// 静态链表
#include <stdio.h>
#include <stdlib.h>

#define MaxSize 10 // 静态链表的最大长度

typedef struct SNode{
    int data; // 存储的数据元素
    int next; // 下一个元素的数组下标
}SNode, SLinkList[MaxSize];

void InitSLinkList(SLinkList L){
    L = (SNode *)malloc(MaxSize*sizeof(SNode)); // 申请一片地址
    for (int i=0; i<MaxSize; i++){
        L[i].data = 0; // 初始化每一个数组元素
        L[i].next = i+1; //初始化每一个游标
    }
    L[MaxSize-1].next = -1; // 设置最后一个游标为-1代表表尾
}

void testSLinkList(){
    SLinkList L;
    InitSLinkList(L);
}

int main(){
    testSLinkList();
    return 0;
}