双向循环单链表

//函数声明：#include"cirtwowaylinklist.h"

#define _CRT_SECURE_NO_WARNINGS 1
#include
#include

typedef int ElemType;
typedef struct CirDulNode
{
	struct CirDulNode *prior;
	ElemType data;
	struct CirDulNode *next;
}DulNode;

void judgement_NULL(DulNode *head);
DulNode * creat();                                     //创建链表

void insert(DulNode *head, int i, ElemType x);         //插入结点

void delete_element(DulNode *head, ElemType x);         //删除链表中所有值为X的结点
void delete_place(DulNode *head, int i);                //删除链表中第i个结点

void find_place(DulNode *head, ElemType x);             //寻找链表中所有x，所在的结点位置
void find_element(DulNode *head, int i);                //寻找第i个结点上的值

void length(DulNode *head);

void initslinklist(DulNode *head);                        //释放整个链表

void sortrank(DulNode *head);                             //对链表进行排序

void output_order(DulNode *head);      //正序打印
void output_back(DulNode *head);       //逆序打印

int means();                           //选择方式




//函数实现：#include"cirtwowaylinklist.c"

#include"cirtwowaylinklist.h"
void judgement_NULL(DulNode *head)              //判断动态内存是否开辟成功
{
	if (head == NULL)
	{
		perror("out of memory\n");
		exit(EXIT_FAILURE);
	}
}

DulNode * creat()
{
	DulNode *head, *p, *r;
	ElemType x;
	head = (DulNode *)malloc(sizeof(DulNode));
	judgement_NULL(head);
	r = head;
	printf("开始建立：");
	while (1)
	{
		scanf("%d", &x);
		if (x != 0)                          //建立链表，以0作为结束标志 
		{
			p = (DulNode *)malloc(sizeof(DulNode));
			judgement_NULL(p);
			p->data = x;
			r->next = p;
			p->prior = r;
			r = p;
		}
		else
			break;
	}
	head->prior = r;                                 //将链表首尾链接
	r->next = head;
	printf("创建成功\n");
	return head;
}

void insert(DulNode *head, int i, ElemType x)             //在i位置上插入一个X,因为链表循环，所以i>1就一定能找到一个位置
{
	DulNode *p, *r;
	p = (DulNode *)malloc(sizeof(DulNode));
	judgement_NULL(p);
	p->data = x;
	r = head;
	while (1)
	{
		if (i <= 1)
			break;
		r = r->next;
		i--;
	}
	if (i < 1)
		printf("没有该结点\n");
	else
	{
		p->next = r->next;                     //在头结点之前，之后都可以插入
		p->prior = r;
		r->next = p;
		p->next->prior = p;
	}
}

void delete_element(DulNode *head, ElemType x)          //删除链表中所有的x元素所在的结点
{
	DulNode *p, *r;
	int count = 0;
	p = head->next;
	while (p != head)
	{
		if (p->data == x)
		{
			count++;
			r = p;
			p = p->next;
			r->prior->next = r->next;
			r->next->prior = r->prior;
			free(r);
			r = NULL;
		}
		else
			p = p->next;
	}
	if (count == 0)
		printf("链表中没有此元素\n");
	else
		printf("共删除%d个\n", count);
} 

void delete_place(DulNode *head, int i)        //删除一个指定位置的结点，结点位置i>0
{
	DulNode *p;
	p = head;
	while (1)
	{
		if (i <= 1)
			break;
		p = p->next;
		i--;
	}
	if (i < 1)
		printf("没有该结点\n");
	else
	{
		if (p->next = head)           //如果要删除的结点是头结点则跳过删除头结点之后的结点
		{
			p = head->next;
			head->next = p->next;
			p->next->prior = head;
		}
		else
		{
			p->prior->next = p->next;
			p->next->prior = p->prior;
			free(p);
		}
	}
}

void find_place(DulNode *head, ElemType x)       //找到链表中所有的x元素所在的结点位置
{
	int count = 0;
	int flag = 0;
	DulNode *p;
	p = head->next;
	while (p != head)
	{
		count++;
		if (p->data == x)
		{
			flag++;
			printf("此元素结点位置：%d\n", count);
		}
		p = p->next;
	}
	if (flag == 0)
		printf("链表中没有此元素\n");
}

void find_element(DulNode *head, int i)           //找到i结点上的元素，并输出
{
	DulNode *p;
	p = head->next;
	while (p != head)
	{
		if (i <= 1)
			break;
		p = p->next;
		i--;
	}
	if (p == head || i != 1)
		printf("没有该结点\n");
	else
		printf("此结点元素：%d\n", p->data);
}

void length(DulNode *head)
{
	int len = 0;
	DulNode *p;
	p = head->next;
	while (p != head)
	{
		len++;
		p = p->next;
	}
	printf("链表长度:%d\n", len);
}

void initslinklist(DulNode *head)               //释放整个链表
{
	DulNode *p;
	p = head->next;
	while (p != head)
	{
		p = p->next;
		free(p->prior);
		p->prior = NULL;
	}
	free(head);
	head = NULL;
	p = NULL;
}

void sortrank(DulNode *head)                       //对整个链表进行排序
{
	DulNode *p, *r;
	ElemType tmp;
	p = head->next;
	while (p->next!= head)
	{
		r = head->next;
		while (r->next!= head)
		{
			if ((r->data) >(r->next->data))
			{
				tmp = r->data;
				r->data = r->next->data;
				r->next->data = tmp;
			}
			r = r->next;
		}
		p=p->next;
	}
	printf("排序成功\n");
}


void output_order(DulNode *head)                   //正向打印整个链表
{
	DulNode *p;
	p = head;
	if (head->next == head)
		printf("链表为空\n");
	else
	{
		printf("正序打印链表：");
		p = p->next;
		while (p != head)
		{
			printf("%d ", p->data);
			p = p->next;
		}
		printf("\n");
	}
}

void output_back(DulNode *head)                   //反向打印整个链表
{
	DulNode *p;
	p = head->prior;
	if (head->next == head)
		printf("链表为空\n");
	else
	{
		printf("反向打印链表：");
		while (p != head)
		{
			printf("%d ", p->data);
			p = p->prior;
		}
		printf("\n");
	}
}

int means()                                          //选择以哪种方式进行操作
{
	int m = 0;
	while (1)
	{
		printf("请选择方式：");
		scanf("%d", &m);
		if (m == 1 || m == 2)
			break;
		printf("选择无效，请重新选择\n");
	}
	return m;
}







//函数测试：

#include"cirtwowaylinklist.h"
int main()
{
	DulNode *ret = NULL;
	int n = 0;
	int i = 0;
	ElemType x;
	printf("*********************************************\n");
	printf("*********************************************\n");
	printf("*1.CreatLinkList          2.Insert **********\n");
	printf("*3.Delete                 4.Find   **********\n");
	printf("*5.Length                 6.Output **********\n");
	printf("*7.InitsLinkLinst         8.Sortrank ********\n");
	printf("*0.Exit                   *******************\n\n\n");

	while (1)
	{
		printf("请选择功能：");
		scanf("%d", &n);
		if (n == 0)                          //选择0直接退出
		{
			free(ret);                       //退出前先释放列表
			exit(1);
		}
		if (ret == NULL)                     //如果ret为空，则首先建立链表
		{
			if (n == 1)
			{
				printf("创建链表以0作为结束标志\n");
				ret = creat();
			}
			else
				printf("请先建立链表\n");
		}
		else
		{
			switch (n)                              //选择剩下的功能
			{
			case 1:                             //当ret不为空时不能建立链表
				printf("当前链表未结束，请先初始化链表\n");
				break;
			case 2:
				printf("请输入要插入的元素和位置：");
				scanf("%d", &x);
				scanf("%d", &i);
				insert(ret, i, x);
				break;
			case 3:
				printf("*1.delete_element     2.delete_place*\n");
				if (means() == 1)
				{
					printf("请输入要删除的元素：");
					scanf("%d", &x);
					delete_element(ret, x);
				}
				else
				{
					printf("请输入要删除的结点：");
					scanf("%d", &i);
					delete_place(ret, i);
				}
				break;
			case 4:
				printf("*1.find_place         2.find_element*\n");
				if (means() == 1)
				{
					printf("请输入要查找的元素：");
					scanf("%d", &x);
					find_place(ret, x);
				}
				else
				{
					printf("请输入要查找的位置：");
					scanf("%d", &i);
					find_element(ret, i);
				}
				break;
			case 5:
				length(ret);
				break;
			case 6:
				printf("*1.output_order         2.output_back*\n");
				if (means() == 1)
					output_order(ret);
				else
					output_back(ret);
				break;
			case 7:                                      //将当前链表释放
				initslinklist(ret);
				ret = NULL;
				break;
			case 8:
				sortrank(ret);
				break;
			default:
				printf("选择无效，请重新选择\n");
				break;
			}                                                //switch()语句结束
		}
		n = 0;
	}                                                        //循环结束
	system("pause");
	return 0;
}

创新互联建站主要从事成都网站建设、成都网站设计、网页设计、企业做网站、公司建网站等业务。立足成都服务尖草坪,10余年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:028-86922220