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

数据结构-环形链表

news 2026/8/8 7:06:44

单向环形链表头结点创建

动态申请内存创建循环链表哨兵头结点；
内存分配失败，打印提示并返回 NULL；
将头结点 next 指针指向自身，构造空循环链表；
返回头结点地址。

node_t *cycle_linklist_create(void) { node_t *head = malloc(sizeof(node_t)); if(head==NULL) { printf("malloc fail\n"); return NULL; } head->next = head; return head; }

单向环形链表头节点后插入新节点

判断头结点指针是否为 NULL，非法则打印提示并直接返回；
动态分配新节点，分配失败打印提示并返回；
指针 p 初始指向原首节点的后继节点；
给新节点填入数据，新节点后继先指向原来链表第一个有效节点；
判断原链表为空（new->next == head）：令新节点自环；
如果链表不为空，p 向后循环遍历找到整条链表尾节点；将尾节点后继修改为新节点；
更新头结点后继指针指向新节点，完成循环链表头插。

void cycle_linklist_insert_head(node_t *head,data_t data) { if(head==NULL) { printf("head is NULL\n"); return ; } node_t *new = malloc(sizeof(node_t)); if(new==NULL) { printf("malloc fail\n"); return ; } //记录首节点位置 node_t *p = head->next->next; //新节点存入数据 new->data = data; //新节点获取首节点位置 new->next = head->next; //如果首节点位置为头结点则新节点的下一节点指向自己 if(new->next == head) { new->next = new; }else if(new->next != head) { while(p->next!=head->next) //如果新节点的下一节点不是头结点，则循环到尾节点 p = p->next; //尾节点的下一节点与首节点断开，指向新节点 p->next = new; } head->next = new; //头节点与首节点断开，指向新节点 }

单向环形链表打印链表数据

判断头结点指针是否为 NULL，非法则打印提示并返回；
判断循环链表为空，打印空链表提示并返回；
遍历指针 p 指向链表第一个有效节点；
while 循环条件：当前节点后继不等于原首节点，代表还未到达尾节点；打印当前节点数据，指针向后移动；
退出循环时 p 停留在尾节点，单独打印尾节点数据，输出换行。

void print_cycle(node_t *head) { if(head==NULL) { printf("head is NULL\n"); return ; } if(is_empty(head)==0) { printf("is empty\n"); return ; } node_t *p = head->next; while(p->next!= head->next) //循环打印，直到尾节点 { printf("%d ",p->data); p = p->next; } printf("%d\n",p->data); //单独打印尾节点数据 }

单向环形链表按数据内容查找节点

判断头结点指针是否为 NULL，非法则打印提示并返回 NULL；
判断循环链表为空，打印空链表提示并返回 NULL；
遍历指针 p 指向第一个有效节点；
while 循环条件：当前节点后继不等于首有效节点，说明还未到达尾节点；比对当前节点数据，匹配成功直接返回当前节点地址；未匹配则 p 向后移动；
退出循环时 p 停留在尾节点，单独比对尾节点数据；
尾节点匹配成功返回 p，否则遍历完毕无匹配，返回 NULL。

node_t *cycle_linklist_find_key(node_t *head,data_t key) { if(head==NULL) { printf("head is NULL\n"); return NULL; } if(is_empty(head)==0) { printf("is empty\n"); return NULL; } node_t *p = head->next; while(p->next!= head->next) //同打印数据的思路，先找到尾节点 { if(p->data == key) { return p; } p = p->next; } if(p->data == key) //单独判断尾节点数据是否符合 { return p; }else { return NULL; //都没找到就返回NULL } }

单向环形链表删除首节点

判断头结点指针是否为 NULL，非法打印提示并返回；
判断循环链表为空，打印提示并返回；
temp 保存待删除的第一个有效节点；p 用来寻找链表尾节点；
while 循环向后遍历，直到 p 停在尾节点；
修改头结点后继，指向原首节点的下一个节点；
修改尾节点的后继，指向新的首节点，维持环形结构；
释放原首节点内存，完成循环链表头删

void cycle_linklist_delete_head(node_t *head) { if(head==NULL) { printf("head is NULL\n"); return ; } if(is_empty(head)==0) { printf("is empty\n"); return ; } node_t *p = head->next; node_t *temp = head->next; while(p->next != head->next) p = p->next; head->next = temp->next; p->next = head->next; free(temp); }

单向环形链表销毁

判断二级指针 head 是否为 NULL，参数非法直接返回；
判断循环链表为空，释放头结点，外部头指针置空后函数返回；
遍历指针 p 指向第一个有效节点；
while 循环条件：当前节点后继不等于首有效节点使用 temp 保存当前待释放节点； p 先向后移动；释放 temp 指向节点；
循环结束 p 停留在尾节点，单独释放尾节点；
释放哨兵头结点；
通过二级指针将外部链表头指针置为 NULL，消除野指针。

void cycle_linklist_destroy(node_t **head) { if(head==NULL) { printf("head is NULL\n"); return ; } if(is_empty(*head)==0) { free(*head); *head = NULL; return ; } node_t *p = (*head)->next; while(p->next != (*head)->next) { node_t *temp = p; p = p->next; free(temp); } free(p); free(*head); *head = NULL; return; }