数据结构-单向循环链表
对于单向链表来说，只能从头结点遍历到尾结点，而没有办法从尾结点直接访问首节点，基于单链表的弊端，引入单向循环链表构造单向循环链表的结点
typedef struct CircularLinkedList
{
DataType_t data; //结点的数据域
struct CircularLinkedList *next; //结点的指针域
}CircLList_t;创建一个空单向循环链表
CircLList_t * CircLList_Create(void)
{
//1.创建一个头结点并对头结点申请内存
CircLList_t *Head = (CircLList_t *)calloc(1,sizeof(CircLList_t));
if (NULL == Head)
{
perror("Calloc memory for Head is Failed");
exit(-1);
}
//2.对头结点进行初始化，头结点是不存储数据域，指针域指向自身，体现“循环”思想
Head->next = Head;
//3.把头结点的地址返回即可
return Head;
}创建新的结点
CircLList_t * CircLList_NewNode(DataType_t data)
{
//1.创建一个新结点并对新结点申请内存
CircLList_t *New = (CircLList_t *)calloc(1,sizeof(CircLList_t));
if (NULL == New)
{
perror("Calloc memory for NewNode is Failed");
return NULL;
}
//2.对新结点的数据域和指针域进行初始化
New->data = data;
New->next = NULL;
return New;
}头部插入元素
bool CircLList_HeadInsert(CircLList_t *Head,DataType_t data)
{
CircLList_t *New = CircLList_NewNode(data);
CircLList_t *Phead=Head->next;
//判断新结点创建是否成功
if(New == NULL){
printf("create new node false\n");
return false;
}
//判断链表是否为空
if(Head->next == Head){
Head->next = New;
New->next = New;
return true;
}
//链表不为空则执行
while(Phead->next != Head->next){
Phead = Phead->next;
}
New->next = Head->next;
Head->next = New;
Phead->next = New;
return true;
}尾部插入结点
bool CircLList_TailInsert(CircLList_t *Head,DataType_t data)
{
CircLList_t *New = CircLList_NewNode(data);
CircLList_t *Phead=Head->next;
//判断新结点创建是否成功
if (NULL == New)
{
perror("Calloc memory for NewNode is Failed");
return NULL;
}
//判断链表是否为空
if(Head->next == Head){
Head->next = New;
New->next = New;
return true;
}
//寻找尾节点
while(Phead->next != Head->next){
Phead = Phead->next;
}
Phead->next = New;
New->next = Head->next;
return true;
}指定元素后边插入
bool CircLList_DestInsert(CircLList_t *Head,DataType_t destval,DataType_t data)
{
CircLList_t *New = CircLList_NewNode(data);
CircLList_t *Phead=Head->next;
//判断新结点创建是否成功
if (NULL == New){
perror("Calloc memory for NewNode is Failed");
return NULL;
}
//判断链表是否为空
if(Head->next == Head){
Head->next = New;
New->next = New;
return true;
}
//寻找目标结点
while(Phead->next != Head->next && Phead->data != destval){
Phead = Phead->next;
}
//判断循环终止条件是否是寻找到的尾节点
if(Phead->next == Head->next){
if(Phead->data != destval){
printf("can not find this value\n");
return false;
}
//CircLList_TailInsert(Head,data);
}
//Phead = Phead->next;
New->next = Phead->next;
Phead->next = New;
return true;
}遍历打印链表
bool CircLList_Print(CircLList_t *Head)
{
//对单向循环链表的头结点的地址进行备份
CircLList_t *Phead = Head;
//判断当前链表是否为空，为空则直接退出
if (Head->next == Head)
{
printf("current linkeflist is empty!\n");
return false;
}
//从首结点开始遍历
while(Phead->next)
{
//把头结点的直接后继作为新的头结点
Phead = Phead->next;
//输出头结点的直接后继的数据域
printf("data = %d\n",Phead->data);
//判断是否到达尾结点，尾结点的next指针是指向首结点的地址
if (Phead->next == Head->next)
{
break;
}
}
return true;
}删除首结点
bool LList_HeadDel(CircLList_t *Head)
{
//对单向循环链表的头尾结点的地址进行备份
CircLList_t *Phead = Head->next;
CircLList_t *Pphead = Head->next;
//判断当前链表是否为空，为空则直接退出
if (Head->next == Head)
{
printf("current linkeflist is empty!\n");
return false;
}
//遍历链表找到尾结点
while(Phead->next != Head->next){
Phead = Phead->next;
}
//进行删除操作，重新连接
Phead->next = Pphead->next;
Head->next = Pphead->next;
Pphead->next = NULL;
free(Pphead);
return true;
}删除尾结点
bool LList_TailDel(CircLList_t *Head)
{
//对单向循环链表的头尾结点的地址进行备份
CircLList_t *Phead = Head->next;
CircLList_t *Pphead = Head->next;
//判断当前链表是否为空，为空则直接退出
if (Head->next == Head)
{
printf("current linkeflist is empty!\n");
return false;
}
//遍历链表找到尾结点
while(Phead->next != Head->next){
Pphead = Phead;
Phead = Phead->next;
}
Pphead->next = Head->next;
Phead->next = NULL;
free(Phead);
return true;
}删除指定元素
bool CircLList_DestDel(CircLList_t *Head,DataType_t destval)
{
//对单向循环链表的目标结点和直接前驱结点的地址进行备份
CircLList_t *Pphead = Head;//直接前驱的地址
CircLList_t *Phead = Head->next;
//判断当前链表是否为空，为空则直接退出
if (Head->next == Head)
{
printf("current linkeflist is empty!\n");
return false;
}
//寻找目标结点
while(Phead->next != Head->next && Phead->data != destval){
Pphead = Phead;
Phead = Phead->next;
}
//判断尾结点的data是不是目标值
if(Phead->data == destval && Phead->next == Head->next){
LList_TailDel(Head);
return true;
}
//判断首结点的data是不是目标值
else if(Pphead->next == Head->next){
LList_HeadDel(Head);
return true;
}
//到达链表尾但是没有找到目标元素
else if(Phead->next == Head->next){
printf("do not find this value,do not delete\n");
return false;
}
Pphead->next = Phead->next;
Phead->next = NULL;
free(Phead);
return true;
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]