当前位置：首页 > news >正文

数据结构——线性表（循环链表）

news 来源：原创 2024/9/20 10:35:16

一、循环链表定义

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表(circular linked list)。
循环链表解决了一个很麻烦的问题。如何从当中一个结点出发，访问到链表的全部结点。为了使空链表与非空链表处理一致，我们通常设一个头结点，当然，这并不是说循环链表一定要头结点，这需要注意。

二、循环列表的基本操作

循环列表的操作原理和单链表相似。

1、循环链表创建

//创建循环链表
cirLinkList LinkList_create(){cirLinkList header = (cirLinkList)malloc(sizeof(Node));header->next = header;return header;
}

2、循环链表插入元素

//循环链表L中第i个元素位置插入e值
int cirLinklist_insert(cirLinkList head, int i, ElemType e) {cirLinkList p = head;int j = 0;while (p && j < i){p = p->next;j++;}if(!p || j > i+1){return ERROR;}cirLinkList s = (cirLinkList)malloc(sizeof(cirLinkList));s->data = e;s->next = p->next;p->next = s;return OK;
}

3、循环链表删除元素

//循环链表L中删除第i个元素
int cirLinklist_del(cirLinkList list,int i)
{cirLinkList head = list;int j = 0;while(head && j < i){head = head->next;j++;}if(!head || j > i){return ERROR;}cirLinkList q;q = head->next;q->next = head->next->next;head->next = q->next;free(q);return OK;
}

4、循环链表输出所有元素

//打印循环链表中所有的元素
void cirLinkList_print(cirLinkList list)
{cirLinkList head = list->next;while(head != list){printf("%d ",head->data);head = head->next;}printf("\n");
}

5、输出循环链表中指定位置的元素

// //返回L中第i个数据元素的值
ElemType cirLinkList_getElem(cirLinkList list,int i){cirLinkList p = list->next;int j = 0;while(p && j < i){p = p->next;j++;}if(!p || j > i){return ERROR;}return p->data;
}

6、销毁循环链表

//销毁循环链表
void cirLinkList_destroy(cirLinkList heard){if(heard == NULL){return;}cirLinkList p = heard->next;cirLinkList q = NULL;while(p != heard){q = p->next;free(p);p = q;}free(heard);
}

代码示例：

int main()
{cirLinkList list;list = LinkList_create();cirLinklist_insert(list,0,1);cirLinkList_print(list);cirLinklist_insert(list,0,2);cirLinkList_print(list);cirLinklist_insert(list,1,3);cirLinkList_print(list);cirLinklist_insert(list,1,4);cirLinkList_print(list);int data = cirLinkList_getElem(list,1);printf("%d \n",data);cirLinklist_del(list,1);cirLinkList_print(list);cirLinkList_destroy(list);return 0;
}

运行结果：