循环链表
循环链表:将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表。如图所示:
非空的循环链表如图:
循环链表与单链表的主要差异在于循环的判断上,原来是判断p->next是否为空,现在则是p->next不等于头结点,则循环未结束。
单循环链表的定义与实现:
(1)头文件:
代码实现:
#pragma once
//循环链表,尾节点next保存头结点地址
typedef struct CNode
{
int data;
struct CNode *next;
}CNode,*CList;
void InitList(CList plist);
bool Insert_head(CList plist,int val);//头插法
bool Insert_tail(CList plist,int val);//尾插法
CNode *Search(CList plist,int key);//查找
bool Delete(CList plist,int key);//删除
bool IsEmpty(CList plist);//判空
int GetLength(CList plist);//获取长度
void Show(CList plsit);//打印
CNode *Getprio(CList plist,int key);//获取key的前驱
CNode *GetNext(CList plist,int key);//获取key的后继
void Clear(CList plist);//清空数据
void Destroy(CList plist);//销毁数据
(2)源文件:
代码实现:
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include"clist.h"
void InitList(CList plist)
{
assert(plist != NULL);
if (plist == NULL)
{
return;
}
plist->next = plist;
}
bool Insert_head(CList plist,int val)//头插法
{
CNode *p = (CNode *)malloc(sizeof(CNode));
p->data = val;
p->next = plist->next;
plist->next = p;
return true;
}
bool Insert_tail(CList plist,int val)//尾插法
{
CNode *p;
for (p=plist; p->next!=plist; p=p->next);
CNode *q = (CNode *)malloc(sizeof(CNode));
q->data = val;
q->next = p->next;
p->next = q;
return true;
}
CNode *Search(CList plist,int key)//查找
{
for (CNode *p=plist->next; p!=plist; p=p->next)
{
if (p->data == key)
{
return p;
}
}
return NULL;
}
bool Delete(CList plist,int key)//删除
{
CNode *p = Getprio(plist,key);
if (p == NULL)
{
return false;
}
CNode *q=p->next;
p->next = q->next;
free(q);
return true;
}
bool IsEmpty(CList plist)//判空
{
return plist->next == plist;
}
int GetLength(CList plist)//获取长度
{
int count = 0;
for (CNode *p=plist->next; p!=plist; p=p->next)
{
count++;
}
return count;
}
void Show(CList plist)//打印
{
for (CNode *p=plist->next; p!=plist; p=p->next)
{
printf("%d\n",p->data);
}
}
CNode *Getprio(CList plist,int key)//获取key的前驱
{
for (CNode *p=plist; p->next!=plist; p=p->next)
{
if (p->next->data == key)
{
return p;
}
}
return NULL;
}
CNode *GetNext(CList plist,int key)//获取key的后继
{
CNode *p = Search(plist,key);
if (p==NULL||p->next==plist)
{
return NULL;
}
return p->next;
}
void Clear(CList plist)//清空数据
{
Destroy(plist);
}
void Destroy(CList plist)//销毁数据
{//删除第一个
CNode *p;
while (plist->next != plist)
{
p = plist->next;
plist->next = p->next;
free(p);
}
}
测试用例:
1.尾插法,将0-9分别插入循环链表
2.头插法,将50插入最前面
3.获取长度(去掉了头插)
4.查找5
5.查找前驱下标
6.查找后继下标
7.删除6
8.清空
9.摧毁