欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构——链表——带头结点的双向循环链表

程序员文章站 2022-03-15 19:59:14
...

带头结点的双向循环链表

#include<stdlib.h>
#include<stdio.h>
#include"headList.h"

/*
	功能:创建一个空链表
	参数:无
	返回值:
		失败返回NULL
		成功返回头结点的地址
*/
List * createLkList()
{
	List * list = (List *)malloc(sizeof(List));
	if(list == NULL)
	{
		printf("malloc fail\n");
		return NULL;//失败返回NULL
	}

	list->first = NULL;
	list->last = NULL;
	list->n = 0;//现在还是空链表
	return list;
}

/*
	功能:往链表中插入一个元素
	参数:
		@list	头结点的地址
		@x		待插入的数据
	返回值:无
*/

int insert(List * list,ElemType x)
{

	//1,分配空间
	Node * p = (Node *)malloc(sizeof(Node));
	if(p == NULL)
	{
		printf("分配内存失败\n");
		return 0;
	}

	//2,保存数据
	p->data = x;
	p->next = NULL;
	p->prev = NULL;

	//3,把该节点插入到链表中
	if(list->first == NULL)//if(list->n == n)
	{
		list->first = p;
		list->last = p; 
		
	}
	else
	{
		#if 1
			//尾插法
			list->last->next = p;
			p->prev = list->last;
			list->last = p;
		#else
			//头插法
			list->first->prev = p;
			p->next = list->first;
			list->first = p;
		#endif
	}
	list->last->next = list->first;
	list->first->prev = list->last;
	
	list->n ++;
	return 1;
}

/*
	功能:输出一个链表的所有节点数据
	参数:
		@l		该链表的头结点的地址
	返回值:无
*/
void printfLkList(List * l)
{
	
	Node * p = l->first;
	
	int i;
	for(i=0;i<l->n;i++)
	{
		printf("%d ",p->data);
		p = p->next;
	}

	printf("\n");
	
}

/*
	功能:清空一个空链表
	参数:
		@list 该链表的头结点的地址
	返回值:无
*/
void cleanList(List *list)
{
	Node * p = list->first;
	Node * q = NULL;
	int i;
	for(i=0;i<list->n;i++)
	{
		q = p->next;
		p->next = NULL;
		p->prev = NULL;
		free(p);
		p = q;
	}
	list->first=list->last=NULL;
	list->n = 0;
}

/*
	功能:销毁一个空链表
	参数:
		@list 该链表的头结点的地址
	返回值:无
*/
void destroyList(List * list)
{
	cleanList(list);
	free(list);
}

/*
	功能:查找list链表中是否存在一个值为x的元素
	参数:
		@list	该链表的头结点的地址
		@x		查询的数据
	返回值:
		找到了返回1
		没找到返回0
*/
int find(List * list,ElemType x)
{
	Node * p = list->first;

	int i;
	for(i=0;i<list->n;i++)
	{
		if(p->data == x)
		{
			return 1;
		}
		p = p->next;
	}
	return 0;

}


/*
	功能:往一个有序链表中插入一个节点,使之仍然有序
	参数:
		@list	该链表的头结点的地址
		@x		待插入的数据
	返回值:无
*/
void insertElem(List * list,ElemType x)
{
	Node * p = (Node *)malloc(sizeof(Node));

	p->data = x;
	p->next = NULL;
	p->prev = NULL;

	Node * q = list->first;
	Node * r = NULL;
	//找到第一个比我大的元素
	int i;
	for(i=0;i<list->n;i++)
	{
		if(q->data > x)
		{
			break;
		}
		r = q;
		q = q->next;
	}
	
	if(i==list->n)//没找到,插入到最后
	{
		list->last->next = p;
		p->prev = list->last;
		list->last = p;
		list->last->next = list->first;
		list->first->prev = list->last;
		
	}
	else if(q == list->first)//第一个就比我大
	{
		p->next = list->first;
		list->first->prev = p;
		list->first = p;
		list->last->next = list->first;
		list->first->prev = list->last;
	}
	else//中间位置
	{
		r->next = p;
		p->next = q;
		p->prev = r;
		q->prev = p;
	}

	list->n ++;
}

/*
	功能:删除一个链表中值为x的节点
	参数:
		@list 该链表的头结点的地址
		@x	  待删除的数据
	返回值:
		删除成功返回1
		没有这个元素返回0
*/

int delete(List * list,ElemType x)
{
	Node * p = list->first;
	Node * r = NULL;
	int i;
	for(i=0;i<list->n;i++)
	{
		if(p->data == x)
		{
			break;
		}
		r = p;
		p = p->next;
	}
	if(i==list->n)//没找到
		return 0;

	if(i<list->n)//找到了
	{
		//分情况删除
		if(p == list->first)//删除的是第一个
		{
			list->first = p->next;
			//list->first->prev = NULL;
			p->next = NULL;
			p->prev = NULL;
			free(p);
			list->last->next = list->first;
			list->first->prev = list->last;
		}
		else if(p == list->last)//删除的是最后一个
		{
			list->last = r;
			p->prev = NULL;
			p->next = NULL;
			free(p);
			list->last->next = list->first;
			list->first->prev = list->last;
		}
		else//中间
		{
			r->next = p->next;
			p->next->prev = r;
			p->next = NULL;
			p->prev = NULL;
			free(p);
		}
		list->n --;
	}

	return 1;
}