循环双链表
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
结点结构
空链
0.数据结构声明
#define MAXSIZE 20 /* 存储空间初始分配量 */
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElementType;/* ElementType类型根据实际情况而定，这里假设为int */
//定义结点
typedef struct Node{
ElementType data;
struct Node *prior;
struct Node *next;
}Node;
typedef struct Node * DoublyCycleLinkedList;
1.初始化
Status InitLinkList(DoublyCycleLinkedList *list){
*list = (DoublyCycleLinkedList)malloc(sizeof(Node));
if (*list == NULL) {
return ERROR;
}
(*list)->next = (*list);
(*list)->prior = (*list);
//新增数据
DoublyCycleLinkedList p = *list;
for(int i=0; i < 10;i++){
//1.创建1个临时的结点
DoublyCycleLinkedList temp = (DoublyCycleLinkedList)malloc(sizeof(Node));
temp->data = i;
//2.为新增的结点建立双向链表关系
//① temp 是p的后继
p->next = temp;
//② temp 的前驱是p
temp->prior = p;
//③ temp的后继是*list
temp->next = (*list);
//④ 头结点的前驱指向新建的temp
(*list)->prior = temp;
//⑤ p 要记录最后的结点的位置,方便下一次插入
p = p->next;
}
return OK;
}
DoublyCycleLinkedList list;
ElementType temp,item;
InitLinkList(&list);
2.遍历
Status Description(DoublyCycleLinkedList list){
if (list == NULL) {
printf("打印的双向循环链表为空!\n\n");
return ERROR;
}
printf("双向循环链表内容: ");
DoublyCycleLinkedList p = list->next;
while (p != list) {
printf("%d ",p->data);
p = p->next;
}
printf("\n\n");
return OK;
}
Description(list);
3.插入结点
约定：当插入位置超过链表长度则插入到链表末尾
Status LinkListInsert(DoublyCycleLinkedList *list, int index, ElementType data){
//1. 创建指针p,指向双向链表头
DoublyCycleLinkedList p = (*list);
int i = 1;
//2.双向循环链表为空,则返回error
if(*list == NULL) return ERROR;
//3.找到插入前一个位置上的结点p
while (i < index && p->next != *list) {
p = p->next;
i++;
}
//4.如果i>index 则返回error
if (i > index) return ERROR;
//5.创建新结点temp
DoublyCycleLinkedList temp = (DoublyCycleLinkedList)malloc(sizeof(Node));
//6.temp 结点为空,则返回error
if (temp == NULL) return ERROR;
//7.将生成的新结点temp数据域赋值e.
temp->data = data;
//8.将结点temp 的前驱结点为p;
temp->prior = p;
//9.temp的后继结点指向p->next;
temp->next = p->next;
//10.p的后继结点为新结点temp;
p->next = temp;
//如果temp 结点不是最后一个结点
if (*list != temp->next) {
//11.temp节点的下一个结点的前驱为temp 结点
temp->next->prior = temp;
}else{
(*list)->prior = temp;
}
return OK;
}
printf("输入要插入的位置和数据用空格隔开：");
scanf("%d %d",&temp,&item);
LinkListInsert(&list,temp,item);
Description(list);
4.删除结点
/**
循环双链表删除结点
@param list 实例
@param index 位置
@param data 数据
@return 状态
*/
Status LinkListRemove(DoublyCycleLinkedList *list,int index,ElementType *data){
int i = 1;
DoublyCycleLinkedList temp = (*list)->next;
if (*list == NULL) {
return ERROR;
}
//①.如果删除到只剩下首元结点了,则直接将*list置空;
if(temp->next == *list){
free(*list);
(*list) = NULL;
return OK;
}
//1.找到要删除的结点
while (i < index) {
temp = temp->next;
if (temp != *list){
i++;
}
}
//2.给e赋值要删除结点的数据域
*data = temp->data;
//3.修改被删除结点的前驱结点的后继指针
temp->prior->next = temp->next;
//4.修改被删除结点的后继结点的前驱指针
temp->next->prior = temp->prior;
//5. 删除结点temp
free(temp);
return OK;
}
printf("输入要删除位置：");
scanf("%d",&temp);
LinkListRemove(&list, temp, &item);
printf("删除链表位置为%d,结点数据域为:%d\n",temp,item);
Description(list);