循环链表

循环链表

循环单链表

  循环单链表和单链表的区别在于：循环单链表的最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环。

  在循环单链表中，表尾结点tail的next指针指向头结点，所以表中没有指针域为NULL的结点，因此，循环单链表的判空条件不是头结点的指针是否为空，而是判断头结点的指针是否等于头指针，就是说是否指向自身。

初始化

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

判空

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

判断表尾结点

bool IsTail(LinkList& L, LNode* p){
    if( p->next == L){
        return true;
    }
    return false;
}

  有时对单链表常做的操作是在表头表尾操作的，此时对循环单链表不设头指针而仅设尾指针，从而使得操作效率更高。原因是若设头指针，对表尾进行操作的时间复杂度为O（n）,而设尾指针tail，tail->next即为头指针，对于表头表尾进行操作时都只需要O（1）。

循环双链表

  知道了循环单链表，那循环双链表理解起来就很简单了。循环双链表的表尾结点的next 指针指向头结点，同时头结点的prior指针指向表尾结点。

初始化

bool InitDLinkList(DLinkList& L){
    DNode* L = (DNode*)malloc(sizeof(DNode));
    if( L == NULL){
        return false;
    }
    L->prior = L;
    L->next = L;
    return true;
}

判空

bool IsEmpty(DLinkList& L){
    if( L->next == L && L->prior = L){
        return true;
    }
    return false;
}

判断表尾结点

bool IsTail(LinkList& L, LNode* p){
    if( p->next == L){
        return true;
    }
    return false;
}

静态链表

  静态链表借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，与链表中的指针不同，这里的指针是结点的相对地址（数组下标），又称游标。静态链表也要预先分配分配一块连续的内存空间。

  静态链表结构类型的描述如下：

#define MAXSIZE 100
typedef struct{
    ElemType data;
    int next;
}SLinkList[MAXSIZE];

  静态链表以next == - 1作为其结束的标志。静态链表的插入，删除操作与动态链表的相同，只需要修改指针，而不需要移动元素。