数据结构-双向循环链表-题解(C语言代码)

859 阅读 0 评论 0 点赞

````c

typedef struct _Node
{
	int data;
	struct _Node* prev;
	struct _Node* next;
	char zero[4];//内存对齐 
}NODE,*PNODE;

PNODE Head = NULL;
PNODE Last = NULL;

//双向循环链表
void insert(int index, int value);//在index处插入value值 
void delByInd(int index);//根据index删除链表中的值 
void printList();//打印链表中的值 
int contain(int value);//value值是否包含在链表中 
 
int contain(int value)
{
	PNODE tmp = Head;
	if(tmp == NULL)
		return 0;	//不包含 
	while(1)
	{
		if(tmp->data == value)//判断当前节点的值是否等于value
		{
			return 1;	//包含 
		}else	//不等于，就判断下一个节点是否等于头结点（Head) 
		{
			if(tmp->next != Head)
			{
				tmp = tmp->next; //不等于，tmp指针指向下一个节点 
			}else	//等于头结点，退出，表示没找到。 
			{
				return 0;//不包含 
			}
		}
	}
}
void insert(int index, int value)
{
	if(Head == NULL)
	{
		Head = (NODE*)malloc(sizeof(NODE));
	//	Last = Head;//尾部指向头部 
		//初始化Head结构 
		Head->data = value;
		Head->prev = Head;
		Head->next = Head;
		Last = Head;
		return;
	}
	if(contain(value))//表示当前链表已经有此值。 
		return;

PNODE temp = Head;
	NODE* nd = (NODE*)malloc(sizeof(NODE));
	nd->data = value;
	nd->prev = Head;
	nd->next = Head;
	
	if(index == 1)//作为头结点插入
	{
		//将头尾节点的指针更新 
		nd->prev = Last;
		Last->next = nd;
		//将nd节点作为头结点 
		nd->next = temp;
		temp->prev = nd; 
		Head = nd;
		Last = Head->prev;
		
	}else
	{
		
		int i = 1;
		//遍历到指定位置
		while(i != index && temp->next != Head)//当前节点的下一个节点不等于头结点 
		{
			temp = temp->next;
			i++;	
		}
		if(i == index && temp == Last)//指定位置是尾节点
		{// 思路是将尾节点的上一个节点更新为插入节点
			temp->prev->next = nd;//尾节点的上一个节点重新指向插入节点
			nd->next = temp;
			temp->prev = nd;
		}else if(i != index && temp == Last)//没有指定的位置，也就是超过了尾节点
		{//将插入节点作为尾节点进行处理
			temp->next = nd;
			nd->prev = temp;
			nd->next = Head;
			//更新尾指针
			Last = nd;
			//更新头指针
			Head->prev = Last;		
		}else	 //在中间节点插入
		{// 思路是更新前后指针
			nd->prev = temp->prev;
			temp->prev->next = nd;
			
			nd->next = temp;
			temp->prev = nd;	
		}
	}
}
 
void delByInd(int index)
{
	PNODE temp = Head;
	PNODE tmp2 = NULL;
	if(temp == NULL)
		return;
	
	if(index == 1)//删除头结点 
	{
		if(temp->next != Head)//表示有一个以上的节点 
		{
			if(temp->next == Last)//只有两个节点 
			{//更新头尾指针
				Head = temp->next;
				Last = Head;
				Head->prev = Last;
				Head->next = Last;
				
				free(temp);
				temp = NULL;
			}else	//多个节点 
			{//更新头尾指针，尾指针的prev重新指向新的Head，
			//将下一个节点作为头指针
				Head = temp->next;
				Head->prev = Last;
				Last->next = Head;
				
				free(temp);
				temp = NULL;
			}
		}else //只有一个节点 
		{//释放内存，更新头尾指针为空
			Last = NULL;
			free(Head);
			Head = NULL;
		} 
	}else	//在其他位置上删除
	{
	
		int i;
		for(i = 1; i != index && temp->next != Head; ++i)//当前节点的下一个节点不等于头结点 
		{
			temp = temp->next;
		}
		if(i == index)// 找到指定位置
		{
			
			if(temp == Last)//删除节点是尾节点 
			{
				
				Last = temp->prev;//当前节点的上一个节点作为尾节点 
				Head->prev =  Last;
				Last->next = Head;
				
				free(temp);
				temp = NULL;
				
			}else //删除中间节点 
			{
				temp->prev->next = temp->next;
				temp->next->prev = temp->prev;
			
				free(temp);
				temp = NULL;
			}
		}
	}
}
void printList()
{
	PNODE temp = Head;
	if(temp != NULL)
	{
		printf("%d",temp->data);
	}else
	{
		return;
	 } 
	while(temp->next != Head)//当前节点的下一个节点不等于头结点 
	{
		temp = temp->next;
		printf(" %d",temp->data);
	}
	printf("\n");
}

````

0.0分

0 人评分

本文分类：题解列表
浏览次数：859 次浏览
发布日期：2019-07-15 10:30:51
本文链接：https://blog.dotcpp.com/a/60744

上一篇 > [编程入门]结构体之时间设计-题解(C语言代码)
下一篇 > 弟弟的作业-题解(C语言描述_冰煌雪舞)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

数据结构-双向循环链表-题解(C语言代码)

评论列表共有 0 条评论

发表评论取消回复

数据结构-双向循环链表-题解(C语言代码)

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 0 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 0 条评论

发表评论取消回复