【数据结构】-循环链表(单链表）

末蓝、 2023-02-27 14:59 5阅读 0赞

### 循环单链表-带头结点 ###

*  1.头文件及类型定义
 *  2.循环单链表结点类型定义
 *  3.函数声明
 *  4.基本操作
 *   *  4.1 初始化循环单链表
     *  4.2 判空
     *  4.3 判断表尾结点
     *  4.4 按位查找
     *  4.5 指定结点后插
     *  4.6 创建循环单链表
     *  4.7 遍历
     *  4.8 main函数
 *  5.小结

# 1.头文件及类型定义 #

#include<stdio.h>
    #include<stdlib.h>
    #define ElemType int

# 2.循环单链表结点类型定义 #

typedef struct LNode {
        		//定义单链表结点类型
    	ElemType data;			//每个结点存放一个数据元素
    	struct LNode* next;		//指针指向下一个结点
    }LNode, * LinkList;

# 3.函数声明 #

/*函数声明*/
    bool InitList(LinkList& L);						//1.初始化循环单链表
    bool Empty(LinkList L);							//2.判空
    bool isTail(LinkList L, LNode* p);				//3.判断表尾结点
    LNode* GetElem(LinkList L, int i);				//4.按位查找
    bool InsertNextNode(LNode* p, ElemType e);		//5.指定结点后插
    LinkList List_HeadInsert(LinkList& L);			//6.头插法
    void PrintList(LinkList L);						//7.遍历

# 4.基本操作 #

## 4.1 初始化循环单链表 ##

//1.初始化循环单链表(带头结点)
    bool InitList(LinkList& L) {
        
    	L = (LNode*)malloc(sizeof(LNode));			//分配一个头结点
    	if (L == NULL)
    		return false;		//内存不足，分配失败
    	L->next = L;		//头结点next指向头结点(仅此处与普通单链表有区别)
    	return true;
    }

## 4.2 判空 ##

//2.判空
    bool Empty(LinkList L) {
        
    	if (L->next == L)		//仅此处与普通单链表有区别
    		return true;
    	else
    		return false;
    	//或者 return (L->next == L);
    }

## 4.3 判断表尾结点 ##

//3.判断结点p是否为循环单链表的表尾结点
    bool isTail(LinkList L, LNode* p) {
        
    	if (p->next == L)
    		return true;
    	else
    		return false;
    }

## 4.4 按位查找 ##

//4.查找函数-按位查找：返回第i个结点
    LNode* GetElem(LinkList L, int i) {
        
    	if (i < 0)
    		return NULL;	//小于单链表长度
    	LNode* p = L;
    	int j = 0;
    	while (p != NULL && j < i) {
        
    		p = p->next;
    		j++;
    	}
    	return p;		//也可能返回NULL，当输入i大于单链表长度时
    }

## 4.5 指定结点后插 ##

//5.插入函数-指定结点后插：在指定结点之后插入元素e
    bool InsertNextNode(LNode* p, ElemType e) {
        
    	if (p == NULL)
    		return false;
    	LNode* s = (LNode*)malloc(sizeof(LNode));
    	if (s == NULL)		//内存分配失败
    		return false;
    	s->data = e;
    	s->next = p->next;
    	p->next = s;
    	return true;
    }

## 4.6 创建循环单链表 ##

//6.创建循环单链表：头插法
    LinkList List_HeadInsert(LinkList& L) {
        
    	if (InitList(L))	//初始化循环单链表
    		printf("循环单链表初始化成功！\n");
    	else
    		printf("循环单链表初始化失败！\n");
    	if (Empty(L))
    		printf("当前表为空!\n");
    	else
    		printf("当前表非空!\n");
    	ElemType x;
    	int i = 1;		//用作记录插入第几个元素
    	printf("开始创建循环单链表！\n请输入%d个元素：", i);
    	scanf("%d", &x);
    	while (x != 0) {
        
    		if (InsertNextNode(L, x)) 		//头插法本质是头结点的后插操作
    			printf("成功插入第%d个元素：%d\n", i, x);
    		else
    			printf("插入第%d个元素失败！\n", i);
    		printf("请输入%d个元素：", ++i);
    		scanf("%d", &x);
    	}
    	printf("循环单链表创建完成！\n");
    	return L;
    }

## 4.7 遍历 ##

//7.遍历循环单链表
    void PrintList(LinkList L) {
        
    	LNode* p;
    	p = L->next;
    	printf("遍历循环单链表：\n");
    	while (p != L) {
        		//此处判断与普通单链表有区别
    		printf("%d\t", p->data);
    		p = p->next;
    	}
    	printf("\n");
    }

## 4.8 main函数 ##

int main() {
        
    	LinkList L;
    	int i;
    	
    	/*以下操作只要涉及对循环单链表的改动，均遍历循环单链表*/
    
    	/*1、头插法建立循环单链表*/
    	L = List_HeadInsert(L);
    
    	/*2、判空*/
    	if (Empty(L))
    		printf("当前表为空!");
    	else
    		printf("当前表非空!");
    	PrintList(L);
    
    	/*3、按位查找*/
    	printf("请输入您要查找的位序i：");
    	scanf("%d", &i);
    	LNode* p = GetElem(L, i);
    	printf("位序为%d的值为：%d\n", i, p->data);
    
    	/*4.判断表尾结点*/
    	if (isTail(L, p))
    		printf("当前结点为表尾结点！\n");
    	else
    		printf("当前结点不是表尾结点！\n");
    
    	//*5、指定结点后插,以按位查找的p结点为例*/
    	ElemType e;
    	printf("请输入您要后插的值：");
    	scanf("%d", &e);
    	if (InsertNextNode(p, e))
    		printf("p结点后插成功，元素值为：%d\n", e);
    	else
    		printf("p结点后插失败！\n");
    
    	/*5.再次判断表尾结点*/
    	if (isTail(L, p))
    		printf("当前结点为表尾结点！\n");
    	else
    		printf("当前结点不是表尾结点！\n");
    	PrintList(L);
    	return 0;
    }

# 5.小结 #

1.  **普通单链表和循环单链表的对比**  
    (1)不同点  
    主要是**初始化**、**判空**、**判断表尾结点**、**遍历结束条件**方面有微小的变化，主要原因就是循环单链表的表尾结点指向了头结点，而不是NULL。  
    (2)相同点  
    增删查以及创建操作没有改变。
2.  **说明**  
    上述代码主要是对循环单链表中与普通单链表有区别的操作进行了测试，其他基本操作与普通单链表基本一致。