双向循环链表

在上一篇双向链表的基础上增加了循环，有不小的改动，特别是一些核心的地方。

例如，如何在插入结点的过程中，确保时刻都在首位相连； 遍历循环条件怎么写 等等。

双向链表：https://blog.csdn.net/hpu2022/article/details/83146619

双向循环链表：

#include <iostream>
#include <string>
using namespace std;
typedef long long LL;

typedef struct List{
	int num;		// 编号
	string name;	// 姓名
	LL tel;			// 电话
	struct List *prior;
	struct List *next;
} List, *LinkList;		// List 定义结构体变量， LinkList 定义结构体指针

LinkList Insert(LinkList &head, LinkList &tmp);
LinkList Create()
{
	LinkList head, p;
	int num;
	string name;
	LL tel;
	head = NULL;
	cout << "input num, name and tel: \n";
	cin >> num >> name >> tel;
	while(num)
	{
		p = new List;
		p->num = num;
		p->name = name;
		p->tel = tel;
		head = Insert(head, p);
		cin >> num >> name >> tel;
	}
	return head;
}
LinkList Insert(LinkList &head, LinkList &tmp)	// 引用参数
{
	LinkList ptr, ptr1, ptr2;	// 辅助指针
	ptr = tmp;
	ptr2 = head;
	if(head == NULL)	// 插入的结点是唯一一个结点的情况
	{
		head = ptr;
		head->prior = head;
		head->next = head;
	}
	else
	{
		while((ptr->num > ptr2->num) && (ptr2->next != head))	// 寻找插入的有序位置
		{
			ptr1 = ptr2;
			ptr2 = ptr2->next;
		}
		if(ptr->num <= ptr2->num)
		{
			if(head == ptr2)	// 要插入的结点在头结点之前，是新的头结点
			{
				head = ptr;
				head->prior = ptr2->prior;	// 新的头结点的前驱仍然是原来头结点的前驱，指向最后一个节点
				head->next = ptr2;			// 新的头结点的后继结点是原来的头结点
				ptr2->prior = head;			// 原来头结点的前驱是新的头结点
//				ptr2->next = NULL;
			}
			else	// 插入在两个结点的中间
			{
				ptr1->next = ptr;
				ptr->prior = ptr1;
				ptr->next = ptr2;
				ptr2->prior = ptr;
			}
		}
		else	// 插入在末尾
		{
			ptr2->next = ptr;
			ptr->prior = ptr2;
			head->prior = ptr;	// 头结点的前驱是末尾结点
			ptr->next = head;	// 末尾结点的后继是头结点
		}
	}
	return head;
}
LinkList Delete(LinkList head, int num)		// 删除指定编号的结点
{
	LinkList ptr1, ptr2;	// 辅助指针
	while(head != NULL && head->num == num)	// 要删除的结点是头结点
	{
		ptr2 = head;
		head = head->next;
		head->prior = ptr2->prior;
		delete ptr2;	// 删除结点
	}
	if(head == NULL)	// 头结点为空等价于链表为空
		return NULL;
	ptr1 = head;
	ptr2 = head->next;
	while(ptr2 != head)
	{
		if(ptr2->num == num)
		{
			ptr1->next = ptr2->next;
			ptr2->next->prior = ptr1;
			delete ptr2;
		}
		else
			ptr1 = ptr2;
		ptr2 = ptr1->next;
	}
	return head;
}
void Print(LinkList head)	// 遍历输出
{
	if(head == NULL)
	{
		cout << "No Records" << endl;
		return;
	}
	cout << "num\t name\t tel\n";

	LinkList ptr = head;
	do{
		cout << ptr->num << "\t ";
		cout << ptr->name << "\t ";
		cout <<ptr->tel << endl;
		ptr = ptr->next;
	}while(ptr != head);

	//for(LinkList ptr = head; ptr->next != head; ptr = ptr->next)
}
LinkList Find(List *head, int num)
{
	LinkList flag = NULL;
	if(head->num == num)
		return head;
	for(LinkList ptr = head->next; ptr != head; ptr = ptr->next)
	{
		if(ptr->num == num)
		{
			flag = ptr;
		}
	}
	return flag;
}

int main()
{
	List *head, *p;
	int num;
	string name;
	LL tel;
	int choice;

	do{
		cout << "1: create\n2: insert\n3: delete\n4: print\n5: Find\n0: exit\n";
		cin >> choice;
		switch(choice)
		{
			case 1:
				head = Create();
				break;
			case 2:
				cout << "input num, name and tel: \n";
				cin >> num >> name >> tel;
				p = new List;
				p->num = num;
				p->name = name;
				p->tel = tel;
				head = Insert(head, p);
				break;
			case 3:
				cout << "input name" << endl;
				cin >> num;
				head = Delete(head, num);
				break;
			case 4:
				Print(head);
				break;
			case 5:
				cout << "input num \n";
				cin >> num;
				LinkList tmp1 = Find(head, num);
				if(tmp1 != NULL)
				{
					cout << "Find: ";
					cout << tmp1->name << " " << tmp1->tel << endl;
					cout << "Find->prior ";
					cout << tmp1->prior->name << " " << tmp1->prior->tel << endl;
					cout << "Find->next ";
					cout << tmp1->next->name << " " << tmp1->next->tel << endl;
				}
				else
					cout << "Not Find" << endl;

				break;
		}
	}while(choice != 0);




	return 0;
}