循环链表与静态链表

一.循环链表

1）循环单链表

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

bool InitList(LinkList L)
{
    L=(LNode *)malloc(sizeof(LNode));
    if(L=NULL) return false;
    L->next=L;
    return true;
}

bool Empty(LinkList L)
{
    if(L->next=L) return true;
    return false;
}

bool isTail(LinkList L,LNode * p) //判断一个结点是否为尾节点
{
    return(p->next==L);
}

使用循环单链表时，如果经常需要对表头、表尾操作，可以使L指向表尾，这样找到表头、表尾的时间复杂度都是O（1）。

2）循环双链表

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

bool InitList(LinkList L)
{
    L=(LNode *)malloc(sizeof(LNode));
    if(L=NULL) return false;
    L->next=L;
    L->prior=L;
    return true;
}

bool Empty(LinkList L)
{
    if(L->next=L) return true;
    return false;
}

bool isTail(LinkList L,LNode * p) //判断一个结点是否为尾节点
{
    return(p->next==L);
}

bool ListInsert(DNode * p,DNode * s) 
{
    if(p==NULL||s==NULL) return false;
    s->next=p->next; //1
    p->next->prior=s; //2 尾节点会指向头结点，不会置空，因此不需要条件判断
    s->prior=p; //3
    p->next=s;  //4  1,2必须在4前
    return true;
}


bool ListDelete(DNode * p) //删除指定结点的后继节点
{
    if(p==NULL) return false;
    DNode * q=p->next; 
    p->next=q->next;
    q->next->prior=p;
    free(q);
    return true;
}

指针类链表小结

链表类代码在编写时需要考虑三个问题：

1.如何判空，知道空的状态如何判断就知道如何初始化

2.如何判断表头，表尾，知道怎么判断表头表尾就知道怎么遍历，就知道了怎么去查找、删除、增加

3.表尾、表头是否需要特殊处理

二.静态链表

1）静态链表的定义

#define MaxSize 10

typedef struct Node
{
    int data;
    int next;
}SLinkList[MaxSize];

void InitList()
{
    SLinkList a;
}

2）静态链表的基本操作

初始化：要将a[0]置为-1；将其他空的结点游标置为-2（方便后续计算机判断哪些结点是空结点）；

查找：通过游标依次遍历元素，时间复杂度为O(n)

插入：

1.找到一个空的结点用来存放元素

2.找到位序为i-1的结点

3.修改新的结点的next游标

4.修改i-1结点的next

删除：

1.找到其前驱结点

2.修改前驱结点游标

3.被删除结点的游标置为-2；

3）静态链表的优缺点

优点：增删容易，不需要大量的移动数据

缺点：查找需要遍历，容量固定