数据结构之循环单链表(C语言附完整代码)

这篇具有很好参考价值的文章主要介绍了数据结构之循环单链表(C语言附完整代码)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、定义

循环单链表是单链表的另一种形式,其结构特点链表中最后一个结点的指针域不再是结束标记,而是指向整个链表的第一个结点,从而使链表形成一个环。
示意图:
数据结构之循环单链表(C语言附完整代码)

声明循环单链表

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;
		}
	}
}

删除数据元素

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构之队列(顺序队和链队)(C语言附完整代码)

    队列简称队,它是一种 操作受限的线性表 ,其限制为仅允许在表的一端进行插入操作,而在表的另一端进行删除操作。把 进行插入的一端称为队尾 ,把 进行删除的一端称为队头或队首 。向队列中插入新元素称为 进队或入队 ,从队列中删除元素称为 出队或离队 。由于队列

    2024年02月06日
    浏览(43)
  • 数据结构拓扑排序以及关键路径(出度邻接表)C语言 完整代码

    现实生活中一项工程通常会拆分成多个部分来进行,这些部分有些相互之间有发生的前提关系,还有些可以同时发生且不会互相打扰,但是合理且充分的利用时间来完成项目是一个问题。在项目完成的过程中,那些项目的完成时间被压缩可以压缩工程的总时间,以便于提高整

    2024年02月04日
    浏览(48)
  • 【数据结构】顺序表的实现及基本操作完整代码(C语言实现)

    顺序表:逻辑上相邻的数据元素,其物理次序也是相邻的 这里之所以要把int分别创建新名字为SqlElemType和Status,是因为实际应用时数据的类型不一定是int型,这样设置方便修改元素类型,提高代码适用性。 LocateElem的时间复杂度为O(n) InsertSq的时间复杂度为O(n) DeleteSq的时间

    2024年04月12日
    浏览(48)
  • C语言数据结构二叉排序树的建立、插入、删除、查找操作(原理+完整代码)

    1、若左子树不为空,左子树上所有节点值小于 它根节点的值 2、若右子树不为空,右子树上所有节点值大于 它根节点的值 3、每个节点的左右子树也是二叉排序树 目的:提高查找、插入、删除的速度(不是为了排序) 时间复杂度:由于查找性能取决于树的形态,所以

    2024年02月09日
    浏览(49)
  • C语言:数据结构(单链表)

    概念:链表是一种 物理存储结构上非连续 、非顺序的存储结构,数据元素的 逻辑顺序 是通过链表的 指针链接 次序实现的。 链表的结构跟火车车厢相似,淡季时车次的车厢会相应减少,旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上,不会影响其

    2024年04月26日
    浏览(38)
  • 数据结构——单链表(C语言)

    在这⼀条⼗分漫长的路上,我⾛过阳关⼤道,也⾛过独⽊⼩桥。路旁有深⼭⼤泽,也有平坡宜⼈;有杏花春⾬,也有塞北秋风;有⼭重⽔复,也有柳暗花明;有迷途知返,也有绝处逢⽣。——《⼋⼗述怀》 目录 一 . 什么是链表? 二 . 实现单链表 (1)创建相关源文件和头文

    2024年02月08日
    浏览(103)
  • 【C语言】数据结构-单链表

    主页:114514的代码大冒险 qq:2188956112(欢迎小伙伴呀hi✿(。◕ᴗ◕。)✿ ) Gitee:庄嘉豪 (zhuang-jiahaoxxx) - Gitee.com 文章目录 目录 文章目录 前言(链表的优势) 一、单链表是什么 二、单链表操作的具体代码实现 1.准备工作 2.打印链表 2.尾插(在链表末端添加数据) 3、头插(

    2024年02月02日
    浏览(45)
  • 单链表(数据结构)(C语言)

    这里特指无哨兵位单向非循环链表 目录 背景 概念 单链表的实现 前景提示 单链表的结构体定义 单链表的打印 关于为什么不断言phead 关于单链表的逻辑结构和物理结构 单链表的尾插 关于为什么要用到二级指针 关于尾插的本质 关于找尾整个过程的解释 关于为什么打印单链表

    2023年04月22日
    浏览(74)
  • 单链表—C语言实现数据结构

    本期带大家一起用C语言实现单链表🌈🌈🌈 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的;简单来说,线性表的链式存储结构生成的表,称作“链表”。 每个元素本身由两部分组成: 1、本身的信息,称为

    2024年02月07日
    浏览(81)
  • C语言:数据结构之单链表(三)

    上篇谈了谈尾插法和头插法,这篇谈谈中间插入元素和删除。 1、中间插入元素 既然谈到了要从中间插入那就得确定插入的位置是否合法了,我总不能链表总长为5,但是插入的位置是60,这就不对了。所以得先确定这个链表的长度为多少。这个比较简单,就是在寻找尾部的过

    2024年02月13日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包