数据结构（三）---单向循环链表

发布于：2025-04-16 ⋅ 阅读:(42) ⋅ 点赞:(0)

 单向循环链表（Circular Linked List）

一、基本概念

循环链表是一种特殊的链表，其末尾节点的后继指针指向头结点，形成一个闭环。

循环链表的操作与普通链表基本一致，但需注意循环特性的处理。

二、代码实现

clList.h
#ifndef _CLLIST_H
#define _CLLIST_H

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//定义节点数据的类型
typedef int DATA;

//定义一个单向循环链表的节点
typedef struct node
{
	DATA data;     //节点数据域
	struct node *next;     //指针域，指向后继节点
}NODE;


//函数原型的声明
/**
 * 创建链表
 * @param head 待操作的链表
 * @param data 待插入的数据
 * @return 成功返回0，否则返回-1
 */
extern int cllist_create(NODE **head, DATA data);


/**
 * 在循环链表插入新节点（把新节点插入到头节点之前）
 * @param head 待操作的链表（默认是头节点）
 * @param data 待插入的数据
 * @return 成功返回0，否则返回-1
 */
extern int cllist_insert(NODE **head, DATA data);


/**
 * 实现无头节点的头插法（插入在头节点之前）
 * @param head 待操作的链表（默认是头节点）
 * @param data 待插入的数据
 * @return 成功返回0，否则返回-1
 */
extern int cllist_insertAthead(NODE **head, DATA data);


/**
 * 遍历链表数据
 * @param head 待遍历的链表
 * @return 成功返回0，否则返回-1
 */
extern int cllist_showAll(const NODE *head);


/**
 * 根据data返回查找对应的节点
 * @param head 待操作的链表
 * @param data 需要查找的节点数据
 * @return 查找到的节点
 */
extern NODE *cllist_find(const NODE *head, DATA data);
 
 
/**
 * 根据newdata修改old对应的节点数据
 * @param head 待操作的链表
 * @param old 待修改的原数据
 * @param newdata 待修改的新数据
 * @return 成功返回0，否则返回-1
 */
extern int cllist_update(const NODE *head, DATA old, DATA newdata);


/**
 * 根据data删除对应的节点
 * @param head 待操作的链表
 * @param data 待删除的节点数据
 * @return 成功返回0，否则返回-1
 */
extern int cllist_delete(NODE **head, DATA data);
 
 
/**
 * 销毁整个链表
 * @param head 待销毁的链表
 */
extern void cllist_destroy(NODE **head);


#endif //_CLLIST_H
clList.c
#include "clList.h"


//函数原型的声明
/**
 * 创建链表
 * @param head 待操作的链表(head是指向头节点指针的地址)
 * @param data 待插入的数据
 * @return 成功返回0，否则返回-1
 */
int cllist_create(NODE **head, DATA data)
{
	//如果链表存在，就无需创建
	if(*head)
	{
		//打印错误信息到标准错误流（避免影响正常输出）
		fprintf(stderr, "链表已存在，无需创建！\n");
		return -1;
	}
	
    //单向循环链表
	//创建一个新节点
	NODE *p = (NODE*)malloc(sizeof(NODE));
	//校验新节点是否创建成功
	if(!p)
		return -1;
	
	//初始化新节点
	p->data = data;
	p->next = p;     //循环特性：单个节点的next指向自身(即使单个节点也形成环）
	
	//设置头指针
	*head = p;     //将头指针设置为自己
}


/**
 * 实现无头节点的头插法（插入在头节点之前）
 * @param head 待操作的链表（默认是头节点）
 * @param data 待插入的数据
 * @return 成功返回0，否则返回-1
 */
int cllist_insertAthead(NODE **head, DATA data)
{
	//创建一个新节点
	NODE *pNew = (NODE*)malloc(sizeof(NODE));
	if(!pNew)
	{
		fprintf(stderr, "创建新节点失败！\n");
		return -1;
	}
	
	//初始化新节点的数据域，指针域暂不赋值
	pNew->data = data;
	
	NODE *p = *head;     //创建一个遍历指针用来遍历链表寻找尾节点
	
	//如果是空链表
	if(!p)
	{
		pNew->next = pNew;
		*head = pNew;
		return 0;
	}
	
	//非空链表
	pNew->next = *head;     //新节点的next指向原头节点
	//查找尾节点(原链表的最后一个节点）
	while(p->next != *head)     //单向循环链表的尾节点next永远指向头节点（非NULL）
	{
		p = p->next;
	}//此时p是尾节点
	
	p->next = pNew;
	*head = pNew;
	return 0;
}


/**
 * 在循环链表插入新节点（把新节点插入到头节点之前）
 * @param head 待操作的链表（默认是头节点）
 * @param data 待插入的数据
  * @return 成功返回0，否则返回-1
 */
int cllist_insert(NODE **head, DATA data)
{
	//创建新节点
	NODE *p = (NODE*)malloc(sizeof(NODE));
	//校验节点是否创建成功
	if(!p)
		return -1;
	//初始化新节点
	p->data = data;
	p->next = p;     //此时创建的新节点与链表还无关
	
	//情景1：若待插入的链表是空链表
	if(*head == NULL)
	{
		*head = p;     //设置头指针，相当于创建了一个新链表
		return 0;
	}
	
	//情景2：若待插入的链表是非空链表（在头节点和头节点的next之间插入，头节点不变）
	p->next = (*head)->next;     //新节点指向原头节点的下一个节点
	(*head)->next = p;     //头节点指向新节点
	
	
}


/**
 * 遍历链表数据
 * @param head 待遍历的链表
 * @return 成功返回0，否则返回-1
 */
int cllist_showAll(const NODE *head)
{
	//创建临时指针用于遍历（保持头指针不变）
	const NODE *p = head;     //p指向当前遍历的节点
	
	//空链表
	if(!p)
	{
		fprintf(stderr, "空链表，没有数据!\n");
		return -1;
	}
	
	//遍历列表
	do     //使用do—while保证至少执行依次（应对单节点循环链表）
	{
		printf("%d\t", p->data);
		p = p->next;
	}while(p != head);     //循环终止条件：回到起始节点
	printf("\n");
	
	return 0;
}


/**
 * 根据data返回查找对应的节点
 * @param head 待操作的链表
 * @param data 需要查找的节点数据
 * @return 查找到的节点
 */
NODE *cllist_find(const NODE *head, DATA data)
{
	//使用const指针避免意外修改节点
	const NODE *p = head;
	
	//空链表
	if(!head)
		return NULL;
	
	//遍历列表（确保至少执行一次）
	do
	{
		if(memcmp(&(p->data), &data, sizeof(DATA)) == 0)
		{
			return (NODE*)p;     //强转，避免类型不匹配
		}
		p = p->next;
	}while(p != head);
	
	return NULL;
}


/**
 * 根据newdata修改old对应的节点数据
 * @param head 待操作的链表
 * @param old 待修改的原数据
 * @param newdata 待修改的新数据
 * @return 成功返回0，否则返回-1
 */
int cllist_update(const NODE *head, DATA old, DATA newdata)
{
	NODE *p = cllist_find(head, old);
	
	if(!p)
	{
		fprintf(stderr, "数据未找到！\n");
		return -1;
	}
	
	//找到旧数据的节点更新为新数据
	p->data = newdata;
	
	return 0;
}


/**
 * 根据data删除对应的节点
 * @param head 待操作的链表
 * @param data 待删除的节点数据
 * @return 成功返回0，否则返回-1
 */
int cllist_delete(NODE **head, DATA data)
{
	//尾随法(p为当前节点，q为前驱节点)
	NODE *p = *head, *q = NULL;
	
	//空链表
	if(!*head)
		return -1;
	
	//遍历节点
	while(p)
	{
		//找到要删除数据的位置
		if(memcmp(&(p->data), &data, sizeof(DATA)) == 0)
		{
			//若要删除的节点是头节点
			if(q == NULL)     //指针还没有进行尾随，证明是头节点
			{
				q = p->next;     //获取头节点的下一个节点
				
				//如果此头节点是唯一的头节点(p的next执行自身--头节点）
				if(p->next == *head)
				{
					//链表置空
					*head = NULL;
				}
				else     //链表中除了要删除的头节点还有其他节点
				{
					//替换法（复制下一节点的数据并删除下一节点）
					p->data = q->data;     //用头节点的后续节点数据替换头节点的数据，删除后续节点
					p->next = q->next;
					free(q);
				}
				
				return 0;
			}
			
			//如果要删除的节点是非头节点
			q->next = p->next;     //前驱节点跳过当前节点
			free(p);     //释放当前节点
			return 0;
		}
		q = p;
		p = p->next;
		
		//因为是循环链表，所以要想办法终结循环链表
		if(p == *head)
			break;
	}
	
	return -1;
}


/**
 * 销毁整个单向循环链表
 * @param head 待销毁的链表
 */
void cllist_destroy(NODE **head)
{
	//空链表
	if(!*head)
		return;
	
	//在链表中找节点就用指针尾随法
	NODE *p = *head, *q = NULL;     //p指向当前节点，q用于保存待释放节点
	
	while(p)
	{
		q = p;
		p = p->next;
		free(q);
		
		//解除循环链表
		if(p == *head)
			break;
	}
	
	*head = NULL;     //将头节点置空，不然会产生野指针
}
app.c
#include "clList.h"

int main(int argc,char *argv[])
{
	NODE *head = NULL;
	
	//测试创建和插入
	cllist_create(&head, 111);     //创建头节点
	cllist_insert(&head, 222);
	cllist_insert(&head, 333);
	cllist_insert(&head, 444);
	cllist_showAll(head);     //111 444 333 222
	
	cllist_insertAthead(&head, 222);
	cllist_insertAthead(&head, 333);
	cllist_insertAthead(&head, 444);
	cllist_showAll(head);     //444 333 222 111 444 333 222
	
	//测试更新
	cllist_update(head, 333, 3333);
	cllist_showAll(head);     //444 3333 222 111 444 333 222
	
	//测试删除
	cllist_delete(&head, 444);
	cllist_showAll(head);     //3333 222 111 444 333 222
	
	//销毁链表
	cllist_destroy(&head);
	cllist_showAll(head);     //空链表，没有数据

    return 0;
}

三、优缺点总结

  • 优点

    1. 动态内存：无需预分配固定大小，适合数据量不确定的场景。

    2. 高效操作

      • 头插/头删：O(1)时间复杂度

      • 尾插：O(1)（维护尾指针时）或O(n)

      • 中间插入：O(1)（定位后）

    3. 循环特性：适合周期性访问场景（如：轮询调度、循环缓冲区）

    4. 内存效率：按需分配，无扩容浪费

  • 缺点：

    1. 随机访问 ：必须遍历，时间复杂度O(n)

    2. 存储开销 ：每个节点需额外存储指针

    3. 循环陷阱 ：未正确处理终止条件会导致死循环

    4. 缓存不友好 ：节点内存不连续，访问速度低于数组。

    5. 边界处理 ：需特殊处理头尾节点的指针更新。

四、常见问题

1、数据结构的应用场景

所有编程领域都会涉及，例如

  • 链表：内存管理、任务队列

  • 树/图：数据库索引、路径规划

  • 哈希表：高速缓存、字典实现

2、面试题--单次遍历找到倒数第50个节点

解法：使用双指针技术

  1. 初始化指针fast和slow指向头节点

  2. fast先移动50步

  3. 然后fast和slow同步移动，当fast到达末尾时，slow即指向倒数第50个节点

//单链表找倒数第k节点
NODE *findLastKth(NODE *head, int k)
{
    NODE *fast = head, *slow = head;
    
    //先让快指针前进k步
    for(int i = 0; i < k; i++)
    {
        //若快指针提前变空，说明链表长度不足k
        if(!fast)
            return NULL;     
        fast = fast->next;
    }
    
    while(fast != NULL)
    {
        //循环链表终止条件
        fast = fast->next;
        slow = slow->next;
    }
    
    return slow;
}
//循环链表找倒数第k节点
NODE *findLastKth_Circular(NODE *head, int k)
{
    if(!head || k <= 0)
        return NULL;
    
    NODE *fast = head, *slow = head;
    //快指针先快走n步
    for(int i = 0; i < k; i++)
    {
        if(fast == head)
            return NULL;
            
        fast = fast->next;
    }
    
    //同步移动直到fast回到起点
    while(fast != head)
    {
        fast = fast->next;
        slow = slow->next;
    }
    
    return slow;
}

时间复杂度O(n),空间复杂度O(1)

练习题

【1】（单向链表）

  • 题目：建立一个包含若干整数的单向链表，比如: 1,2,3,4,51,2,3,4,5

    通过某些算法将其中各个节点逆转，比如: 5,4,3,2,15,4,3,2,1

  • 分析：（约瑟夫环、单向循环链表）主要分析如何将链表倒转

  • 代码：

    /

#include <stdio.h>
#include <stdlib.h>

#define MAX_LENGHT 20

// 链表节点结构体
typedef struct ListNode 
{
    int data;               // 节点数据域
    struct ListNode *next;  // 指向下一节点的指针
} Node;


//尾插法创建链表
Node* createList(int arr[], int size) {
    if (size == 0) return NULL;
    
    Node *head = NULL, *tail = NULL;
    for (int i = 0; i < size; i++) {
        Node *newNode = (Node*)malloc(sizeof(Node));
        newNode->data = arr[i];
        newNode->next = NULL;
        
        if (head == NULL) {  // 链表为空时初始化头尾指针
            head = tail = newNode;
        } else {             // 尾插法维护尾指针
            tail->next = newNode;
            tail = newNode;
        }
    }
    return head;
}


//迭代反转法（三指针法）
Node* reverseByIteration(Node *head) {
    Node *prev = NULL, *current = head, *next = NULL;
    while (current) {
        next = current->next;  // 保存下一节点指针
        current->next = prev;  // 反转指针方向
        prev = current;        // 前驱指针后移
        current = next;        // 当前指针后移
    }
    return prev;  // 新头节点是原链表尾节点
}


//头插法反转
Node* reverseByHeadInsert(Node *head) {
    Node *newHead = NULL, *current = head;
    while (current) {
        Node *next = current->next;   // 保存下一节点
        current->next = newHead;      // 头插操作
        newHead = current;            // 更新新头节点
        current = next;               // 移动当前指针
    }
    return newHead;
}


//递归反转法
Node* reverseByRecursion(Node *current, Node *prev) {
    if (!current) return prev;        // 递归终止条件
    
    Node *next = current->next;       // 保存下一节点
    current->next = prev;             // 反转指针方向
    return reverseByRecursion(next, current); // 递归调用
}


//打印链表
void printList(Node *head) {
    Node *current = head;
    while (current) {
        printf("%d\t", current->data);
        current = current->next;
    }
    printf("\n");
}


//释放内存
void freeList(Node *head) {
    Node *current = head;
    while (current) {
        Node *temp = current;
        current = current->next;
        free(temp);
    }
}


int main(int argc,char *argv[])
{
	//动态分配数组
	int *arr = (int*)malloc(MAX_LENGHT * sizeof(int));
	int n;
	printf("Please enter the number of digits you want to reverse:>");
	scanf("%d", &n);
	printf("Please enter %d numbers:>\n", n);
	for(int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
	
	// 创建原始链表
    Node *original = createList(arr, n);
    printf("原链表: ");
    printList(original);
    
    // 迭代反转测试
    Node *reversed1 = reverseByIteration(original);
    printf("迭代反转: ");
    printList(reversed1);
    
    // 头插法反转测试
    Node *reversed2 = reverseByHeadInsert(reversed1);
    printf("头插法反转: ");
    printList(reversed2);
    
    // 递归反转测试
    Node *reversed3 = reverseByRecursion(reversed2, NULL);
    printf("递归反转: ");
    printList(reversed3);
    
    freeList(reversed3);
    return 0;
}

【2】约瑟夫环问题

  • 题目：罗马人占领乔塔帕特后，犹太人与 Josephus 及他的朋友躲到一个洞中，族人决定宁愿死 也不要被敌人找到，于是决定了一个自杀方式，所有人排成一个圆圈，由第 1 个人开始报数， 每报数到第 3 人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。

    然而Josephus和他的朋友并不想死，Josephus要他的朋友先假装遵从，他将朋友与自己安排在两个 特殊的位置，于是逃过了这场死亡游戏。

现在假设有n个人形成一个单向循环链表，求最后剩余的两个节点。

  • 解析：主要是分析有头结点和没有头结点，对本题的影响。一般情况下链表带头结点是比较方便的，但是 对于本题，约瑟夫环问题，带上头结点的链表反而不利于操作，画图讲解。

  • 约瑟夫环问题（Josephus Problem）是一个精度的数学与数据结构问题，其核心在于通过特定规则在循环队列中淘汰元素（删除元素），最终找到幸存者的位置

    • 基本设定：

      1. n个人围成一个环形队列，编号通常为1到n（或0到n-1）

      2. 从第一个人开始报数，每次数到m（或动态变化的密码值）时，该人出列

      3. 从出列者的下一位重新开始报数，每次数到m（或动态变化的密码值）时，该人出列

      4. 目标：确定幸存者的初始编号

    • 使用循环链表模拟环形队列，每次遍历到第m个节点时删除该节点

  • 代码：

    //yuesefu.h



#ifndef _YUESEFU_H
#define _YUESEFU_H


#include <stdio.h>
#include <stdlib.h>
#include <string.h>


//创建节点结构体
typedef struct node
{
	int number;     //人员编号（1~n）
	struct node *next;     //指针域
}NODE;


//创建无头循环链表
NODE *createCircle(int n);


//约瑟夫环淘汰逻辑
void joseph(NODE **head, int m);


#endif //_YUESEFU_H

    //yuesefu.c


#include "yuesefu.h"


//创建无头循环链表
NODE *createCircle(int n)
{
	//定义头指针和前驱节点指针（初始化为空）
	NODE *head = NULL, *prev = NULL;
	
	//循环创建n个节点，人员编号从1开始递增
	for(int i = 1; i <= n; i++)
	{
		//创建新节点
		NODE *new_node = (NODE*)malloc(sizeof(NODE));
		//检查节点是否创建成功
		if(!new_node)
			return NULL;
		//设置节点编号
		new_node->number = i;
		
		//如果链表为空则将新节点设为头节点
		if(!head)
		{
			//头指针执行新节点
			head = new_node;
			//头指针指向自身，形成单个节点的循环结构
			head->next = head;
		}
		//非空链表（尾插法插入元素）
		else
		{
			//将新节点插入到prev节点之后
			prev->next = new_node;     //前驱节点连接新节点
			new_node->next = head;     //新节点指向头节点形成闭环
		}
		
		//更新前驱节点为当前新节点
		prev = new_node;
	}
	
	return head;
}


//约瑟夫环淘汰逻辑
void joseph(NODE **head, int m)
{
	//指针尾随法寻找待删除节点
	NODE *p = *head, *q = NULL;
	
	//当剩余节点数>2时循环
	while(p->next->next != p)
	{
		//移动m-1次寻找待删除节点
		for(int i = 1; i < m; i++)
		{
			q = p;
			p = p->next;
		}
		
		//删除当前节点
		q->next = p->next;     //跳过当前节点
		printf("处死：%d\n", p->number);
		//释放被淘汰节点的内存
		free(p);
		
		//从下一节点继续
		p = q->next;
	}
	
	//输出最后两个幸存者
	printf("幸存者1：%d\t幸存者2：%d\n", p->number, p->next->number);
}
    //app.c



#include "yuesefu.h"


int main()
{
	//经典的约瑟夫问题参数
	int n = 41, m = 3;
	
	NODE *p = createCircle(n);
	joseph(&p, m);
	
	//释放最后两个节点
	free(p->next);
	free(p);
	
	return 0;
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布