【数据结构】循环链表和静态链表

阅读本文，需要对C语言的知识有所掌握，参考我的C语言合集。

C语言合集

循环链表和静态链表

1. 单链表和循环单链表

单链表：

1. 表尾结点的next指针指向NULL。
2. 从一个结点出发只能找到后续的各个结点。

循环单链表：

1. 表尾结点的next指针指向头结点。
2. 从一个结点除法可以找到其他任何一个结点。
3. 从头部找到尾部，时间复杂度为O(n)。
4. 从尾部找到头部，时间复杂度为O(1)。
5. 很多时候对链表的操作都是从头部或尾部，可以让L指向表尾元素，方便插入、删除等操作。

定义单链表头结点

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==NULL){
        return true;
    } else{
        return false;
    }
}

判断尾结点

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

注意：注意判断条件。

2. 双链表与循环双链表

双链表：

1. 表头结点的prior指向NULL。
2. 表尾结点的next指向NULL。

循环双链表：

1. 表头结点的prior指向表尾结点。
2. 表尾结点的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;
    }
}

注意：注意判断条件。

循环双链表的插入

// 在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的后继结点q
bool DeleteNextDNode(DNode *p,DNode *q){
    p->next=q->next;
    q->next->prior=p;
    free(q);
}

3. 静态链表

什么是静态链表？

单链表：各个结点在内存中星罗棋布、散落天涯。

静态链表：分配一整片连续的内存空间，各个结点集中安置。

每个数据元素4B，每个游标4B（每个结点共8B），设起始地址为addr。

e1的存放地址为：addr=8*2

定义一个静态链表

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

void testSLinkList(){
    SLinkList addr;  // addr为起始地址
    // ...后续代码
}

静态链表的初始化

把a[0]的next设为-1。

为了防止脏数据，可以把其他节点的next设为一个特殊值来表示空闲结点，如-2。

静态链表的基本操作

查找：

从头到尾出发挨个往后遍历结点。

插入位序为i的结点：

1. 找到一个空的结点，存入数据元素。
2. 从头结点出发找到位序为i-1的结点。
3. 修改新结点的next。
4. 修改i-1号结点的next。

删除某个结点：

1. 从头结点出发找到前驱结点。
2. 修改前驱结点的游标。
3. 被删除的结点next设为-2，

4. 小结

循环链表：

静态链表：

用数组的方式实现的链表。

优点：增、删操作不需要移动大量元素。

缺点：不能随机存取，只能从头结点开始依次往后查找。容量固定不可变。

适用场景：1.不支持指针的低级语言。2.数据元素数量固定不变的场景（如操作系统的文件分配表FAT）。