C++数据结构笔记（8）循环链表实现

1.循环链表与单链表的区别在于尾部结点存在指向头结点的指针

2.无论尾部结点指向第一个结点（头结点）还是第二个结点（第一个有效结点），都可以被称为循环链表

3.判断循环结束的两种方式：遍历次数等于size;或判断next指针是否指向头结点

4.在初始化时，头结点需要指向自己。

CirCleLinkLsist.h头文件

#ifndef CIRCLELINKLIST
#define CIRCLELINKLIST

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

//结点结构体 
typedef struct CirCleLinkNode{
	struct CirCleLinkNode* next;
}CirCleLinkNode;
//链表结构体 
typedef struct CirCleLinkList{
	CirCleLinkNode head;
	int size;
	//结构体的本质就是维护链表的诸多性质 
}CirCleLinkList;

//比较回调 
typedef int(*ComPareNode)(CirCleLinkNode*,CirCleLinkNode*);
//打印回调
typedef void(*PrintNode)(CirCleLinkNode*); 

//初始化
CirCleLinkList* Init_CirCleLinkList();
//插入
void Insert_CirCleLinkList(CirCleLinkList *clist,int pos,CirCleLinkNode* data);
//获取第一个元素 
CirCleLinkNode* Front_CirCleLinkList(CirCleLinkList* clist,int pos);
//根据位置删除
void RemoveByPos_CirCleLinkList(CirCleLinkList* clist,int pos);
//根据值删除 
void RemoveByValue_CirCleLinkList(CirCleLinkList* clist,CirCleLinkNode* data,ComPareNode compare);
//获得链表长度
int Size_CirCleLinkList(CirCleLinkList* clist); 
//判断是否为空
int IsEmpty_CirCleLinkList(CirCleLinkList* clist); 
//按值查找
int Find_CirCleLinkList(CirCleLinkList* clist,CirCleLinkNode* data,ComPareNode compare);
//打印
void Print_CirCleLinkList(CirCleLinkList* clist,PrintNode print);
//释放内存
void FreeSpace_CirCleLinkList(CirCleLinkList* clist);

#endif

CirCleLinkLsist.c源文件

初始化

CirCleLinkList* Init_CirCleLinkList(){
	
	CirCleLinkList* clist=(CirCleLinkList*)malloc(sizeof(CirCleLinkList)) ;
	clist->head.next=&(clist->head);
	clist->size=0;
	
	return clist;
}

插入

void Insert_CirCleLinkList(CirCleLinkList *clist,int pos,CirCleLinkNode* data){
	if(clist==NULL)
		return;
	if(data==NULL)
		return;
	if(pos<0||pos>clist->size)
		pos=clist->size;
	//如果越界则直接在最后一位插入即可 
	//创建辅助指针
	CirCleLinkNode* pCurrent=&(clist->head);
	for(int i=0;i<pos;i++)
	 	pCurrent=pCurrent->next;
	//新数据入链表
	data->next=pCurrent->next;
	pCurrent->next=data;
	
	clist->size++;
	
}

获取第一个元素 

CirCleLinkNode* Front_CirCleLinkList(CirCleLinkList* clist,int pos){
	return clist->head.next;
	//注意返回的是头结点的下一位 
}

根据位置删除

void RemoveByPos_CirCleLinkList(CirCleLinkList* clist,int pos){
	if(clist==NULL)
		return;
	if(pos<0||pos>=clist->size)
		return;
	CirCleLinkNode* pCurrent=&(clist->head);
	for(int i=0;i<pos;i++)
	 	pCurrent=pCurrent->next;
	
	//缓存目标被删除结点的下一个结点
	
	CirCleLinkNode* pNext=pCurrent->next; 
	pCurrent->next=pCurrent->next;
	
	clist->size--;
}

根据值删除 

void RemoveByValue_CirCleLinkList(CirCleLinkList* clist,CirCleLinkNode* data,ComPareNode compare){
	if(clist==NULL)
		return;
	if(data==NULL)
		return;
		
	CirCleLinkNode* pPrev=&(clist->head);
	CirCleLinkNode* pCurrent=pPrev->next;
	for(int i=0;i<=clist->size;i++)
	{
		if(compare(pCurrent,data)==1)
		{
			pPrev->next=pCurrent->next;
		}
			break;
		//指针后移 
		pPrev=pCurrent;
		pCurrent=pPrev->next;
	}
	clist->size--;
}

获得链表长度

int Size_CirCleLinkList(CirCleLinkList* clist){
	return clist->size;
}

判断是否为空

int IsEmpty_CirCleLinkList(CirCleLinkList* clist){
	if(clist->size==0)
		return 1;
	else
		return 0;
	
	return 0;
}

按值查找

int Find_CirCleLinkList(CirCleLinkList* clist,CirCleLinkNode* data,ComPareNode compare){
	if(clist==NULL)
		return -1;
	if(data==NULL)
		return -1;
	
	int flag=-1;
	CirCleLinkNode* pCurrent=clist->head.next;
	for(int i=0;i<clist->size;i++)
	{
		if(compare(pCurrent,data)==1)
		{
			flag=i;
			break;
		}
		pCurrent=pCurrent->next;
	} 
	return flag;
}

打印

void Print_CirCleLinkList(CirCleLinkList* clist,PrintNode print){
	if(clist==NULL)
		return;
	CirCleLinkNode* pCurrent=clist->head.next;
	for(int i=0;i<clist->size;i++)
	{
		if(pCurrent==&(clist->head))
			pCurrent=pCurrent->next;
			//成倍打印时要跳过头结点 
		print(pCurrent);
		pCurrent=pCurrent->next;
	}

}

释放内存

void FreeSpace_CirCleLinkList(CirCleLinkList* clist){
	if(clist==NULL)
		return;
	free(clist); 
}

main.cpp测试文件

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
#include"CircleLinkList.h"
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

typedef struct goal{
	CirCleLinkNode node;
	int num;
	string name;
}goal; 

void MyPrint(CirCleLinkNode* data)
{
	goal* g=(goal*)data;
	cout<<(g->name)<<":"<<(g->num)<<endl;	
} 

int main(int argc, char** argv) {
	goal g1,g2;
	
	g1.name="Jsl";
	g2.name="Hyh";
	g1.num=2019;
	g2.num=2013;
	
	CirCleLinkList* clist=Init_CirCleLinkList();
	
	Insert_CirCleLinkList(clist,0,(CirCleLinkNode*)&g1);
	Insert_CirCleLinkList(clist,0,(CirCleLinkNode*)&g2);
	cout<<"一共有几个元素："<<(Size_CirCleLinkList(clist))<<endl;
	//头部插入（合法范围内任意） 
	Print_CirCleLinkList(clist,MyPrint);
	FreeSpace_CirCleLinkList(clist);
	
	return 0;
}

测试结果如下：