（38）4.27 数据结构第二章线性表（循环链表和静态链表）

1.循环单链表

#define ElemType int 
typedef struct LNode
{
    ElemType data;
    struct LNode* next;
}LNode, * LinkList;
//1.初始化一个循环单链表
bool InitLinkList(LinkList& L)
{
    L = (LNode*)malloc(sizeof(LNode));//分配一个头结点
    if (L == NULL)
        return false;
    L->next = L;       //头结点next指向头结点
    return true;
}
//判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L, LNode* p)
{
    if (p->next == L)
        return true;
    else
        return false;
}
//判断循环链表是否为空
bool Empty(LinkList L)
{
    if (L->next == L)
        return true;
    else
        return false;
}

2.循环双链表

//2.循环双链表的初始化
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->next = L; 
    L->prior = L;//头结点next指向头结点
    return true;
}
//判断结点p是否为循环单链表的表尾结点
bool isTail(DLinkList L, DNode* p)
{
    if (p->next == L)
        return true;
    else
        return false;
}
//判断循环链表是否为空
bool Empty(DLinkList L)
{
    if (L->next == L)
        return true;
    else
        return false;
}

3.静态链表

查找：
从头结点出发挨个往后遍历结点

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

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

静态链表：用数组的方式实现链表
优点：增删操作不需要大量移动元素
缺点：不能随机存储，只能从头结点开始依次往后查找，****容量固定不可变*****

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