循环链表是一种链式存储结构,它的最后一个结点指向头结点,形成一个环。因此,从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致,差别仅仅在于算法中的循环条件有所不同。

单向循环链表编辑

存储结构和单链表相同。

// 设立尾指针的单循环链表的12个基本操作
void InitList(LinkList *L) { // 操作结果:构造一个空的线性表L
    *L = (LinkList)malloc(sizeof(struct LNode)); // 产生头结点,并使L指向此头结点
    if (!*L) // 存储分配失败
        exit(OVERFLOW);
    (*L)->next = *L; // 指针域指向头结点
}

void DestroyList(LinkList *L) { // 操作结果:销毁线性表L
    LinkList q, p = (*L)->next; // p指向头结点
    while (p != *L) { // 没到表尾
        q = p->next;
        free(p);
        p = q;
    }
    free(*L);
    *L = NULL;
}

void ClearList(LinkList *L) /* 改变L */ { // 初始条件:线性表L已存在。操作结果:将L重置为空表
    LinkList p, q;
    *L = (*L)->next; // L指向头结点
    p = (*L)->next; // p指向第一个结点
    while (p != *L) { // 没到表尾
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = *L; // 头结点指针域指向自身
}

Status ListEmpty(LinkList L) { // 初始条件:线性表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE
    if (L->next == L) // 空
        return TRUE;
    else
        return FALSE;
}

int ListLength(LinkList L) { // 初始条件:L已存在。操作结果:返回L中数据元素个数
    int i = 0;
    LinkList p = L->next; // p指向头结点
    while (p != L) { // 没到表尾
        i++;
        p = p->next;
    }
    return i;
}

Status GetElem(LinkList L, int i, ElemType *e) { // 当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR
    int j = 1; // 初始化,j为计数器
    LinkList p = L->next->next; // p指向第一个结点
    if (i <= 0 || i > ListLength(L)) // 第i个元素不存在
        return ERROR;
    while (j < i) { // 顺指针向后查找,直到p指向第i个元素
        p = p->next;
        j++;
    }
    *e = p->data; // 取第i个元素
    return OK;
}

int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType)) { // 初始条件:线性表L已存在,compare()是数据元素判定函数
    // 操作结果:返回L中第1个与e满足关系compare()的数据元素的位序。
    //           若这样的数据元素不存在,则返回值为0
    int i = 0;
    LinkList p = L->next->next; // p指向第一个结点
    while (p != L->next) {
        i++;
        if (compare(p->data, e)) // 满足关系
            return i;
        p = p->next;
    }
    return 0;
}

Status PriorElem(LinkList L, ElemType cur_e, ElemType *pre_e) { // 初始条件:线性表L已存在
    // 操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,
    //           否则操作失败,pre_e无定义
    LinkList q, p = L->next->next; // p指向第一个结点
    q = p->next;
    while (q != L->next) { // p没到表尾
        if (q->data == cur_e) {
            *pre_e = p->data;
            return TRUE;
        }
        p = q;
        q = q->next;
    }
    return FALSE; // 操作失败
}

Status NextElem(LinkList L, ElemType cur_e, ElemType *next_e) { // 初始条件:线性表L已存在
    // 操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,
    //           否则操作失败,next_e无定义
    LinkList p = L->next->next; // p指向第一个结点
    while (p != L) { // p没到表尾
        if (p->data == cur_e) {
            *next_e = p->next->data;
            return TRUE;
        }
        p = p->next;
    }
    return FALSE; // 操作失败
}

Status ListInsert(LinkList *L, int i, ElemType e) /* 改变L */ { // 在L的第i个位置之前插入元素e
    LinkList p = (*L)->next, s; // p指向头结点
    int j = 0;
    if (i <= 0 || i > ListLength(*L) + 1) // 无法在第i个元素之前插入
        return ERROR;
    while (j < i - 1) { // 寻找第i-1个结点
        p = p->next;
        j++;
    }
    s = (LinkList)malloc(sizeof(struct LNode)); // 生成新结点
    s->data = e; // 插入L中
    s->next = p->next;
    p->next = s;
    if (p == *L) // 改变尾结点
        *L = s;
    return OK;
}

Status ListDelete(LinkList *L, int i, ElemType *e) /* 改变L */ { // 删除L的第i个元素,并由e返回其值
    LinkList p = (*L)->next, q; // p指向头结点
    int j = 0;
    if (i <= 0 || i > ListLength(*L)) // 第i个元素不存在
        return ERROR;
    while (j < i - 1) { // 寻找第i-1个结点
        p = p->next;
        j++;
    }
    q = p->next; // q指向待删除结点
    p->next = q->next;
    *e = q->data;
    if (*L == q) // 删除的是表尾元素
        *L = p;
    free(q); // 释放待删除结点
    return OK;
}

void ListTraverse(LinkList L, void(*vi)(ElemType)) { // 初始条件:L已存在。操作结果:依次对L的每个数据元素调用函数vi()
    LinkList p = L->next->next; // p指向首元结点
    while (p != L->next) { // p不指向头结点
        vi(p->data);
        p = p->next;
    }
    printf("\n");
}

双向循环链表编辑

循环链表的应用问题编辑

Josephu问题:据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人找到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。 如何用循环链表来求解Josephu问题?