一、定义
循环单链表是单链表的另一种形式,其结构特点链表中最后一个结点的指针域不再是结束标记,而是指向整个链表的第一个结点,从而使链表形成一个环。
示意图:
声明循环单链表
typedef struct LNode //定义单链表结点类型
{
ElemType data;
struct LNode *next;
} LinkNode;
注意:本文章讨论的循环单链表是带头结点的循环单链表。
增加头结点的优点如下:
1.循环单链表中首结点的插入和删除操作与其他结点一致,无需进行特殊处理。
2.无论循环单链表是否为空都有一个头结点,因此统一了空表和非空表的处理过程。
二、基本运算
头插法建立循环单链表
void CreateListF(LinkNode *&L,ElemType a[],int n)
//头插法建立循环单链表
{
LinkNode *s;int i;
L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
L->next=NULL;
for (i=0;i<n;i++)
{
s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点
s->data=a[i];
s->next=L->next; //将结点s插在原开始结点之前,头结点之后
L->next=s;
}
s=L->next;
while (s->next!=NULL) //查找尾结点,由s指向它
s=s->next;
s->next=L; //尾结点next域指向头结点
}
该运算依次从数组a中读取数据,生成一个新的结点,将该数据储放到新结点的数据域,然后将其插入到当前链表的表头(即头结点之后),直到所有的数据读完为止。然后查找尾结点,将尾结点的后继指针指向头结点L。
例如:数组 a={ 1,2,3,4 },使用头插法得到的链表顺序为 4,3,2,1。
插入操作如下:
s->next=L->next;
L->next=s;
首先修改s结点的后继指针next,使其指向头节点L的后继指针next所指结点,然后修改头结点的后继指针next,使其指向s结点。
本算法的时间复杂度为O(n)
尾插法建立循环单链表
void CreateListR(LinkNode *&L,ElemType a[],int n)
//尾插法建立循环单链表
{
LinkNode *s,*r;int i;
L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
L->next=NULL;
r=L; //r始终指向终端结点,开始时指向头结点
for (i=0;i<n;i++)
{
s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点
s->data=a[i];
r->next=s; //将结点s插入结点r之后
r=s;
}
r->next=L; //尾结点next域指向头结点
}
该运算依次从数组a中读取数据,生成一个新的结点,将该数据储放到新结点的数据域,然后将其插入到当前链表的表尾,直到所有的数据读完为止。其过程是设置一个指针r,让它始终指向当前链表的尾结点,每次插入一个新结点后,让r指向这个新结点,所有元素插入完后,使r所指结点(尾结点)的后继指针next指向头结点L。
例如:数组 a={ 1,2,3,4 },使用尾插法得到的链表顺序为 1,2,3,4。
插入操作如下:
r->next=s;
r=s;
首先修改r结点的后继指针next,使其指向s结点,最后让r指向s结点。
本算法的时间复杂度为O(n)
初始化循环单链表
void InitList(LinkNode *&L)
{
L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
L->next=L;
}
该运算建立一个空的单链表,其过程是创建一个头结点,并将其后继指针next指向自身。
本算法的时间复杂度为O(1)
销毁循环单链表
void DestroyList(LinkNode *&L)
{
LinkNode *p=L,*q=p->next;
while (q!=L)
{
free(p);
p=q;
q=p->next;
}
free(p);
}
该运算释放单链表L占用的内存空间,即逐一释放全部结点存储空间。设置p,pre两个指针指向两个相邻的结点,初始时pre指向头节点,p指向首结点(链表第一个元素),当p不为头结点L执行循环:先释放pre,然后pre,p同步后移一个结点。循环结束时,pre指向尾结点,再将其释放。
本算法的时间复杂度为O(n)
判断链表是否为空表
bool ListEmpty(LinkNode *L)
{
return(L->next==L);
}
该运算判断单链表是否为空表,当头结点的后继指针next指向其本身时,表示链表为空,返回1,否则返回0。
本算法的时间复杂度为O(1)
求链表的长度
int ListLength(LinkNode *L)
{
LinkNode *p=L;int i=0;
while (p->next!=L)
{
i++;
p=p->next;
}
return(i);
}
该运算返回链表L中数据元素的个数,设置指针p(初始指向头节点),i(初始值为0)用来记录链表中结点的个数,遍历链表,当p不为头结点L时执行循环:i加1,p指向下一个结点。循环结束后返回i。
本算法的时间复杂度为O(n)
输出链表
void DispList(LinkNode *L)
{
LinkNode *p=L->next;
while (p!=L)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
该运算逐一输出各结点的data域值,设置指针p(初始指向首结点),p不为头结点L执行循环:输出当前结点的数据域,p指向下一个结点。
本算法的时间复杂度为O(n)
求链表中某一位置数据元素的值
bool GetElem(LinkNode *L,int i,ElemType &e)
{
int j=0;
LinkNode *p;
if (L->next!=L) //单链表不为空表时
{
if (i==1)
{
e=L->next->data;
return true;
}
else //i不为1时
{
p=L->next;
while (j<i-1 && p!=L)
{
j++;
p=p->next;
}
if (p==L)
return false;
else
{
e=p->data;
return true;
}
}
}
else //单链表为空表时
return false;
}
按元素的值查找
int LocateElem(LinkNode *L,ElemType e)
{
LinkNode *p=L->next;
int n=1;
while (p!=L && p->data!=e)
{
p=p->next;
n++;
}
if (p==L)
return(0);
else
return(n);
}
该运算在单链表中从头开始找到第一个data域值与e相等的结点,如果存在这样的结点,则返回逻辑序号,否则返回0。设置指针p(初始指向首结点),i(初始值为1),当p不为头结点L且p结点的data域值不等于e时执行循环:p指向下一个结点,i加1。循环结束时有两种情况:如果p=NULL,表示不存在值为e的结点,返回0;否则表示存在值为e的结点,返回其逻辑序号i。
本算法的时间复杂度为O(n)
插入数据元素
bool ListInsert(LinkNode *&L,int i,ElemType e)
{
int j=0;
LinkNode *p=L,*s;
if (p->next==L || i==1) //原单链表为空表或i==1时
{
s=(LinkNode *)malloc(sizeof(LinkNode)); //创建新结点s
s->data=e;
s->next=p->next; //将结点s插入到结点p之后
p->next=s;
return true;
}
else
{
p=L->next;
while (j<i-2 && p!=L)
{
j++;
p=p->next;
}
if (p==L) //未找到第i-1个结点
return false;
else //找到第i-1个结点p
{
s=(LinkNode *)malloc(sizeof(LinkNode)); //创建新结点s
s->data=e;
s->next=p->next; //将结点s插入到结点p之后
p->next=s;
return true;
}
}
}
删除数据元素文章来源:https://www.toymoban.com/news/detail-414484.html
bool ListDelete(LinkNode *&L,int i,ElemType &e)
{
int j=0;
LinkNode *p=L,*q;
if (p->next!=L) //原单链表不为空表时
{
if (i==1) //i==1时
{
q=L->next; //删除第1个结点
e=q->data;
L->next=q->next;
free(q);
return true;
}
else //i不为1时
{
p=L->next;
while (j<i-2 && p!=L)
{
j++;
p=p->next;
}
if (p==L) //未找到第i-1个结点
return false;
else //找到第i-1个结点p
{
q=p->next; //q指向要删除的结点
e=q->data;
p->next=q->next; //从单链表中删除q结点
free(q); //释放q结点
return true;
}
}
}
else
return false;
}
三、完整代码
#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct LNode //定义单链表结点类型
{
ElemType data;
struct LNode *next;
} LinkNode;
void CreateListF(LinkNode *&L,ElemType a[],int n)
//头插法建立循环单链表
{
LinkNode *s;int i;
L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
L->next=NULL;
for (i=0;i<n;i++)
{
s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点
s->data=a[i];
s->next=L->next; //将结点s插在原开始结点之前,头结点之后
L->next=s;
}
s=L->next;
while (s->next!=NULL) //查找尾结点,由s指向它
s=s->next;
s->next=L; //尾结点next域指向头结点
}
void CreateListR(LinkNode *&L,ElemType a[],int n)
//尾插法建立循环单链表
{
LinkNode *s,*r;int i;
L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
L->next=NULL;
r=L; //r始终指向终端结点,开始时指向头结点
for (i=0;i<n;i++)
{
s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点
s->data=a[i];
r->next=s; //将结点s插入结点r之后
r=s;
}
r->next=L; //尾结点next域指向头结点
}
void InitList(LinkNode *&L)
{
L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
L->next=L;
}
void DestroyList(LinkNode *&L)
{
LinkNode *p=L,*q=p->next;
while (q!=L)
{
free(p);
p=q;
q=p->next;
}
free(p);
}
bool ListEmpty(LinkNode *L)
{
return(L->next==L);
}
int ListLength(LinkNode *L)
{
LinkNode *p=L;int i=0;
while (p->next!=L)
{
i++;
p=p->next;
}
return(i);
}
void DispList(LinkNode *L)
{
LinkNode *p=L->next;
while (p!=L)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
bool GetElem(LinkNode *L,int i,ElemType &e)
{
int j=0;
LinkNode *p;
if (L->next!=L) //单链表不为空表时
{
if (i==1)
{
e=L->next->data;
return true;
}
else //i不为1时
{
p=L->next;
while (j<i-1 && p!=L)
{
j++;
p=p->next;
}
if (p==L)
return false;
else
{
e=p->data;
return true;
}
}
}
else //单链表为空表时
return false;
}
int LocateElem(LinkNode *L,ElemType e)
{
LinkNode *p=L->next;
int n=1;
while (p!=L && p->data!=e)
{
p=p->next;
n++;
}
if (p==L)
return(0);
else
return(n);
}
bool ListInsert(LinkNode *&L,int i,ElemType e)
{
int j=0;
LinkNode *p=L,*s;
if (p->next==L || i==1) //原单链表为空表或i==1时
{
s=(LinkNode *)malloc(sizeof(LinkNode)); //创建新结点s
s->data=e;
s->next=p->next; //将结点s插入到结点p之后
p->next=s;
return true;
}
else
{
p=L->next;
while (j<i-2 && p!=L)
{
j++;
p=p->next;
}
if (p==L) //未找到第i-1个结点
return false;
else //找到第i-1个结点p
{
s=(LinkNode *)malloc(sizeof(LinkNode)); //创建新结点s
s->data=e;
s->next=p->next; //将结点s插入到结点p之后
p->next=s;
return true;
}
}
}
bool ListDelete(LinkNode *&L,int i,ElemType &e)
{
int j=0;
LinkNode *p=L,*q;
if (p->next!=L) //原单链表不为空表时
{
if (i==1) //i==1时
{
q=L->next; //删除第1个结点
e=q->data;
L->next=q->next;
free(q);
return true;
}
else //i不为1时
{
p=L->next;
while (j<i-2 && p!=L)
{
j++;
p=p->next;
}
if (p==L) //未找到第i-1个结点
return false;
else //找到第i-1个结点p
{
q=p->next; //q指向要删除的结点
e=q->data;
p->next=q->next; //从单链表中删除q结点
free(q); //释放q结点
return true;
}
}
}
else return false;
}
int main()
{
LinkNode *L;
ElemType e;
ElemType a[]={1,2,3,4};
CreateListF(L,a,4); //尾插法建立链表
printf("尾插法所得顺序为: ");
DispList(L);
DestroyList(L);
CreateListR(L,a,4); //头插法建立链表
printf("头插法所得顺序为:");
DispList(L);
printf("链表的长度为:%d\n",ListLength(L));
ListInsert(L,4,5); //在链表第四个元素前插入5
printf("插入一个元素后链表的元素为:");
DispList(L);
ListDelete(L,1,e); //删除链表中第一个元素,并将它的值赋给e
printf("删除的元素为:%d\n",e);
printf("删除一个元素后链表的元素为:");
DispList(L);
printf("当前链表是否为空:%d\n",ListEmpty(L));
GetElem(L,1,e);
printf("链表第一个元素为:%d\n",e);
printf("值为2的元素在链表中的位置为:%d\n",LocateElem(L,2));
return 0;
}
参考资料:
李春葆《数据结构教程》(第五版)文章来源地址https://www.toymoban.com/news/detail-414484.html
到了这里,关于数据结构之循环单链表(C语言附完整代码)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!