数据结构(三)---单向循环链表

发布于:2025-04-16 ⋅ 阅读:(32) ⋅ 点赞:(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. 初始化指针fastslow指向头节点

  2. fast先移动50步

  3. 然后fastslow同步移动,当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;
    }
    	

网站公告

今日签到

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