王道p40 17.设计一个算法用于判断带头结点的循环双链表是否对称(c语言代码实现)

这篇具有很好参考价值的文章主要介绍了王道p40 17.设计一个算法用于判断带头结点的循环双链表是否对称(c语言代码实现)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

补充循环双链表的知识:循环双链表是一种链表数据结构,在链表的基础上增加了头尾相连的循环特性,即链表的最后一个节点指向第一个节点,同时每个节点除了储存下一个节点的指针外还储存前一个节点的指针,这样可以实现在链表两端快速插入和删除元素的操作。

与普通双链表相比,循环双链表的特点是最后一个节点的 next 指针指向第一个节点,第一个节点的 prior指针指向最后一个节点,这样就构成了一个环形结构。循环双向链表可以作为一种序列容器,可以支持在任意位置插入和删除节点,并且可以通过指向任意节点的指针在 O(1) 时间内访问该节点前一个和后一个节点。

在循环双链表L中,某结点*p为尾结点时,p->next==L;当循环双链表为空表时,其头结点的prior域和next域都等于L。

循环双链表的判空条件为:L->prior==L;

                                           L->next==L;

本题算法思想:让p从左向右扫描,q从右向左扫描,直到他们指向同一结点或相邻结点为止,若他们值相同,则继续进行下去,否则返回0。若比较全部相等,则返回1。

本题需要注意的是循环的跳出条件(p!=q是处理结点个数为奇数的,q->next!=p是判断结点个数为偶数。

偶数情况:

王道p40 17.设计一个算法用于判断带头结点的循环双链表是否对称(c语言代码实现),王道课后习题单链表,算法,数据结构,c语言

奇数情况:

王道p40 17.设计一个算法用于判断带头结点的循环双链表是否对称(c语言代码实现),王道课后习题单链表,算法,数据结构,c语言

本题代码如下

int symmetry(linklist* L)//判断循环双链表是否对称
{
	lnode* p = (*L)->next, * q = (*L)->prior;
	while (p!=q && q->next!= p)/* ***注意这里的跳出条件(p!=q是处理结点个数为奇数的,q->next!=p是判断结点个数为偶数)*/
	{
		if (p->data != q->data)
		{
			return 0;
		}
			p = p->next;
			q = q->prior;
	}
		return 1;
}

完整测试代码

#include<stdio.h>
#include<stdlib.h>
typedef struct lnode
{
	int data;
	struct lnode* prior;
	struct lnode* next;
}lnode,*linklist;
int n = 5;
int a[5] = { 1,2,3,2,1 };
void buildlinklist(linklist* L)//建立循环双链表
{
	(*L)->next =*L;//初始化头结点
	(*L)->prior =*L;
	lnode * r = *L;
	int i = 0;
	for (i = 0; i < n; i++)
	{
		lnode *s = (lnode*)malloc(sizeof(lnode));//创建新结点
		s->data = a[i];
		s->next = r->next;//插入新结点
		s->prior = r;
		r->next->prior= s;
		r->next = s;
		r = s;
	}
}
int symmetry(linklist* L)//判断循环双链表是否对称
{
	lnode* p = (*L)->next, * q = (*L)->prior;
	while (p!=q && q->next!= p)
	{
		if (p->data != q->data)
		{
			return 0;
		}
			p = p->next;
			q = q->prior;
	}
		return 1;
}
void print(linklist* L)//输出链表
{
	lnode* k = (*L)->next;
	while (k!=*L)
	{
		printf("%d ", k->data);
		k = k->next;
	}
}
int main()
{
	linklist L=(lnode*)malloc(sizeof(lnode));//创建头结点
	L->next = L;
	L->prior = L;
	buildlinklist(&L);//构建循环双链表
	printf("原始单链表为:");
	print(&L);
	int ret = symmetry(&L);
	if (ret == 1)
	{
		printf("\n带头结点的循环双链表对称");
	}
	else
	{
		printf("带头结点的循环双链表不对称");
	}
	return 0;
}

王道p40 17.设计一个算法用于判断带头结点的循环双链表是否对称(c语言代码实现),王道课后习题单链表,算法,数据结构,c语言文章来源地址https://www.toymoban.com/news/detail-724708.html

到了这里,关于王道p40 17.设计一个算法用于判断带头结点的循环双链表是否对称(c语言代码实现)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包