2.循环链表

#include<cstdio>
#include <cstdlib>
#include<iostream>

#define ElemType int
using namespace std;
typedef struct LNode {
    ElemType data = 0;
    struct LNode *next = nullptr;
} LinkList;

typedef struct DLNode {
    ElemType data;
    struct DLNode *next, *prior;
} DLinkList;

void CreateCListF(LinkList *&L, ElemType a[], int n) {
    // 头插法建立循环单链表
    LinkList *s;
    L = (LinkList *) malloc(sizeof(LinkList));
    L->next = L;  //置为空的循环单链表
    for (int i = 0; i < n; i++) {
        s = (LinkList *) malloc(sizeof(LinkList)); //创建新节点
        s->data = a[i];
        s->next = L->next; //将*s插在首节点之前，头节点之后
        L->next = s;
    }
}

void CreateListR(LinkList *&L, ElemType a[], int n) {
    // 尾插法建立循环单链表
    LinkList *s, *r;
    L = (LinkList *) malloc(sizeof(LinkList));
    r = L;   //r始终指向终端节点，开始时指向头节点
    for (int i = 0; i < n; i++) {
        s = (LinkList *) malloc(sizeof(LinkList)); //创建新节点
        s->data = a[i];
        r->next = s;  //将*s插入*r之后
        r = s;
    }
    r->next = L; //尾节点的next域指向头节点
}

int FindLinkList(LinkList *L, ElemType x) {
    int n = 1;
    LinkList *p = L->next; //p指向第一个数据节点
    while (p != L && p->data != x) {
        p = p->next;
        n++;
    }
    if (p == L)
        return 0;
    else
        return n;  // 找到则返回其序号
}

/*
 * 在循环单链表中*p之后插入*q：q->next = p->next;p->next = q;
 * 在循环单链表中删除节点：p->next = p->next->next;
 * */
int Count(LinkList *L) {
    // 统计循环单链表中节点个数
    LinkList *p = L->next;  //p指向起始节点
    int n = 0;
    while (p != L) {
        n++;
        p = p->next;
    }
    return n;
}

void DelMax(LinkList *&L) {
    // 删除单链表中第一个最大值的节点
    LinkList *p = L->next, *pre = L, *maxp = p, *maxpre = pre;
    while (p != L) {
        if (p->data > maxp->data) {
            maxp = p;
            maxpre = pre;
        }
        pre = p;
        p = p->next;
    }
    maxpre->next = maxp->next;
    free(maxp);
}

void reverseList(LinkList *&L) {
    // 逆置循环单链表
    LinkList *p = L->next, *q;
    L->next = L;  //建立一个空循环单链表
    while (p != L) {
        q = p->next;
        p->next = L->next; //将*p插入到前端
        L->next = p;
        p = q;
    }
}

//————————————————————————————————————————————————————————————————————————————————
void CreateCDListF(DLinkList *&L, ElemType a[], int n) {
    // 头插法建立循环双链表
    DLinkList *s;
    L = (DLinkList *) malloc(sizeof(DLinkList));
    L->next = L->prior = L;//建立一个空的循环双链表
    for (int i = 0; i < n; i++) {
        s = (DLinkList *) malloc(sizeof(DLinkList));
        s->data = a[i];
        s->next = L->next; //将*s插入首节点之前，头节点之后
        if (L->next != NULL)
            L->next->prior = s;

        L->next = s;
        s->prior = L;
    }
}

void CreateCDListR(DLinkList *&L, ElemType a[], int n) {
    // 尾插法建立循环双链表
    DLinkList *s, *r;
    L = (DLinkList *) malloc(sizeof(DLinkList));
    r = L;  //r始终指向终端节点，开始时指向头节点
    for (int i = 0; i < n; i++) {
        s = (DLinkList *) malloc(sizeof(DLinkList));
        s->data = a[i];
        r->next = s;  //将*s插入*r之后
        s->prior = r;
        r = s;
    }
    r->next = L; //尾节点的next指向头节点
    L->prior = r;  // 头节点的prior指向尾节点
}

int FindCDLinkList(DLinkList *L, ElemType x) {
    //在循环双链表中查找元素x
    int n = 1;
    DLinkList *p = L->next; // p指向第一个数据节点，n置为1
    while (p != L && p->data != x) {
        p = p->next;
        n++;
    }
    if (p == L)
        return 0;
    else
        return n;
}

/*
 * 在循环双链表中*p之后插入*q： q->next = p->next;
 *                          p->next->prior = q;
 *                          q->prior = p;
 *                          p->next = q;
 * 删除节点： q = p->next;p->next = q->next;
 *          q->next->prior = p;
 * */

int count(DLinkList *L, ElemType x) {
    // 计算循环双链表中元素值为x的节点个数
    int n = 0;
    DLinkList *p = L->next;
    while (p != L) {
        if (p->data == x)
            n++;
        p = p->next;
    }
    return n;
}

int del_node(DLinkList *&L, ElemType x) {
    // 删除循环双链表中第一个值为x的节点
    DLinkList *p = L->next;
    while (p != L && p->data != x)
        p = p->next;
    if (p == L)
        return 0;   //查找失败，返回0
    else {
        p->prior->next = p->next;  // *p前驱节点的next指向*p的后继
        p->next->prior = p->prior;  // *p后继节点的prior指向*p的前驱节点
        free(p);
        return 1;
    }
}

int swap(DLinkList *&L, ElemType x) {
    // 含两个以上节点的循环双链表，将第一个元素值为x的节点与其后继节点进行交换
    ElemType tmp;
    DLinkList *p = L, *q;
    if (p->data != x) {
        p = p->next;
        while (p != L && p->data != x)
            p = p->next;
        if (p == L)
            return 0; // 查找失败，返回0
    }
    if (p->next != L) { // 若*p不是尾节点，则交换
        q = p->next;  //q指向*p的后继节点
        tmp = p->data;  // 交换两节点的data值
        p->data = q->data;
        q->data = tmp;
        return 1;
    } else return 0;
}

void reverse2(DLinkList *&L) {
    // 逆置两个节点以上的循环双链表
    DLinkList *p = L, *post;
    do {
        post = p->next;
        p->next = p->prior;
        p->prior = post;
        p = post;
    } while (p != L);
}

int symmetry(DLinkList *L) {
    // 判断带头节点的循环双链表是否对称
    DLinkList *p = L->next, *q = L->prior;  //p指向开始节点，q指向尾节点
    while (p != q && p->next != q) {
        if (p->data == q->data) {
            p = p->next;
            q = q->prior;
        } else return 0;
    }
    return 1;
}