【数据结构】顺序表（三）：链表之单向循环链表

ゞ浴缸里的玫瑰 2023-03-02 05:10 40阅读 0赞

### 文章目录 ###

*  单向循环链表
 *   *  一、概念
     *  二、图解
     *  三、实现源码

# 单向循环链表 #

## 一、概念 ##

> 如果将单向链表的**尾节点的指针**指向头结点，那么就形成了一个**单向的循环链表**  
> 优点：相比于单向非循环链表，在循环链表中寻找一个值无需从头指针开始寻找，从任意一个位置都可以开始寻找  
> 判断一个单向的循环链表是否为空：  
> （1）带头结点：头结点的指针指向本身，即代表链表为空  
> （2）无头结点：头指针指向NULL，即代表链表为空

## 二、图解 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70]

## 三、实现源码 ##

> 常量定义

typedef int ET;

--------------------

> 定义单向的循环链表

typedef struct Node
    { 
    	ET data;
    	Node* next;
    }Node;
    typedef Node* SCList;

--------------------

> 初始化链表

void SCLinkedListInitial(SCList *phead){ 
    	*phead = NULL;
    }

--------------------

> 产生一个节点

Node* SCLinkedListGetNode(ET val){ 
    	Node* s = (Node*)malloc(sizeof(Node));
    	assert(s != NULL);
    	s->data = val;
    	s->next = NULL;
    	return s;
    }

--------------------

> 头插法

void SCLinkedListAddFromHead(SCList *phead, ET val){ 
    	assert(phead != NULL);
    	Node* s = SCLinkedListGetNode(val);
    	Node* p = *phead;
    	if (p == NULL){ 
    		*phead = s;
    	}
    	else{ 
    		while (p->next != *phead){ 
    			p = p->next;
    		}
    		p->next = s;
    	}
    	s->next = *phead;
    	*phead = s;
    }

--------------------

> 尾插法

void SCLinkedListAddFromTail(SCList *phead, ET val){ 
    	assert(phead != NULL);
    	Node* s = SCLinkedListGetNode(val);
    	Node* p = *phead;
    	if (p == NULL){ 
    		*phead = s;
    		s->next = *phead;	//s->next = *phead;
    	}
    	else{ 
    		while (p->next != *phead){ 
    			p = p->next;
    		}
    		p->next = s;
    		s->next = *phead;
    	}
    }

--------------------

> 展示数据

void SCLinkedListShowData(SCList phead){ 
    	if (phead == NULL){ 
    		printf("单向循环链表为空！\n");
    		return;
    	}
    	printf("Over->%d->", phead->data);
    	Node* p = phead->next;
    	while (p != phead){ 
    		printf("%d->", p->data);
    		p = p->next;
    	}
    	printf("Over\n");
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70]: /images/20230208/fac2a8b4824f4f8bb1ed79893a5de4ae.png