数据结构--双向循环链表

  • 上个文章写了循环链表是如何实现的,本文的双向循环链表和循环链表类似,只不过是讲每个节点的prior指向上一个节点,再讲尾结点指向头结点,形成了一个环,双向循环链表的优点就是在查找数据时可以进行双向查找,效率比普通链表要高。
  • 双向循环链表中每个节点定义了两个指针,next(指向下一个)和prior(指向上一个)。
  • 增加:在增加结束前的操作和单链表相同,只是在结尾处要讲头节点的prior指向尾节点,尾节点的next指向头节点。详细代码请看下面的Add函数。
  • 删除:删除时要进行判断删除的节点是否是头结点,详情请看Delete函数。
  • 双向查找:即定义两个临时变量保存头结点和尾结点,分别从两头开始查找数据,详情请看Bsearch函数。
#include <iostream>
#include <conio.h>
using namespace std;
template <class T>
class Node
{ 
public:
	Node() {  next = NULL; prior = NULL; data = 0; }
	void set_data(T _data) {  data = _data; }
	void set_next(Node<T>* p) {  next = p; }
	void set_prior(Node<T>* p) {  prior = p; }
	T& get_data() {  return data; }
	Node<T>* get_next() {  return next; }
	Node<T>* get_prior() {  return prior; }
private:
	T data;
	Node<T>* next;
	Node<T>* prior; // 指向上一个节点的指针
};

template <class T>
class List
{ 
private:
	Node<T>* head;
	int lenth;
public:
	List() {  head = new Node<T>; head->set_prior(head); head->set_next(head); lenth = 0; }
	~List()
	{ 
		Node<T>* p = head->get_next();
		Node<T>* temp = p->get_next();
		while (temp != head->get_next())
		{ 
			delete p;
			p = temp;
			temp->get_next();
		}
		delete temp;
		temp = NULL;
	}
	void set_lenth(int  _lenth) {  lenth = _lenth; }
	int get_lenth() {  return lenth; }
	Node<T>* get_head() {  return head; }

	bool isok(int n)
	{ 
		if (n == 1)
		{ 
			cout << "操作成功!\n";
			system("pause");
			return true;
		}
		else
		{ 
			cout << "未查询出此数据!\n";
			system("pause");
			return false;
		}
	}

	bool Check(T& data, Node<T>*& temp)
	{ 
		if (lenth >= 1)
		{ 
			while (temp) // 因此时表尾并未连上头节点,说以可用temp = NULL 来结束循环
			{ 
				if (temp->get_data() == data)
				{ 
					cout << "已有此数据!\n";
					--lenth; // 链表长度复位
					return true;
				}
				temp = temp->get_next();
			}
		}
		return false;
	}

	void Add(int n) // 通过head能访问头节点, head本身只存放lenth的值
	{ 
		Node<T>* p = head;	// p指向表尾,用来链接新节点
		Node<T>* q = NULL;	// q为新节点
		Node<T>* temp = head->get_next();		// 临时变量,作为输入数据查重的指针
		T data; // 暂时存储data的数据
		for (int i = 1; i <= n; i++, lenth++)
		{ 
			temp = head->get_next();
			q = new Node<T>;
			cin >> data;
			if (Check(data, temp) == false) 
			{ 
				q->set_data(data);
				q->set_next(NULL); // 将最后一个节点暂时指向空
				q->set_prior(p);
				p->set_next(q);
				p = q; // p移动到表尾
			}
		}
		delete temp;
		temp = NULL;
		q->set_next(head->get_next());// 将表尾的下一个指向表头
		head->get_next()->set_prior(q); // 将表头的上一个指向表尾,形成循环链表
	}

	bool Delete(Node<T>*& p1, Node<T>*& p2, Node<T>*& p3, int n)
	{ 
		T data;
		if (n == 1) // 判断是否为头节点
		{ 
			Node<T>* temp1 = head->get_next(); // 记录头节点
			Node<T>* temp2 = temp1->get_prior(); // 记录尾节点
			head->set_next(temp1->get_next()); // 更新头节点
			temp1->get_next()->set_prior(temp2); // 更新头节点的prior
			temp2->set_next(temp1->get_next()); // 更新尾节点的next
			delete temp1;
			temp1 = NULL;
			lenth--;
			return true;
		}
		// 删除中间尾时
		else
		{ 
			cout << "请输入要删除的数据:";
			cin >> data;
			Node<T>* temp = BSearch(p1, p2, p3, data); // 用temp记录要删除的节点
			if (temp == NULL)
			{ 
				return false;
			}
			temp->get_prior()->set_next(temp->get_next()); // 更新temp上一节点next的指向
			temp->get_next()->set_prior(temp->get_prior()); // 更新temp下一节点prior的指向
			delete temp;
			temp = NULL;
			lenth--;
			return true;
		}
	}

	Node<T>*& Modify(Node<T>*& p1, Node<T>*& p2, Node<T>*& p3, Node<T>*& temp, T& data)
	{ 
		temp = BSearch(p1, p2, p3, data);// 用temp记录要修改的节点
		if (temp)
		{ 
			return temp;
		}
	}

	bool Seek(Node<T>*& p1, Node<T>*& p2, Node<T>*& p3, T& data)
	{ 
		if (BSearch(p1, p2, p3, data) == NULL)
		{ 
			return false;
		}
		return true;
	}
	
	void Output(Node<T>* p)
	{ 
		do 
		{ 
			cout << p->get_data();
			p = p->get_next();
		} while (p != head->get_next());
		system("pause");
	}

	Node<T>*& BSearch(Node<T>*& temp_1, Node<T>*& temp_2, Node<T>*& temp_3, T& data)
	{ 
		while (temp_1->get_next() != head->get_next() || temp_2->get_prior() != head->get_next()->get_prior())
		{ 
			if (temp_1->get_data() == data)
			{ 
				return temp_1;
			}
			if (temp_2->get_data() == data)
			{ 
				return temp_2;
			}
			temp_1 = temp_1->get_next();
			temp_2 = temp_2->get_prior();
		}
		return temp_3;
	}
	void menu(List<T>& list, Node<T>& node)
	{ 
		Node<T>* p1;
		Node<T>* p2;
		Node<T>* p3;
		Node<T>* temp;
		char m[10];
		int n;
		while (1)
		{ 
			p1 = head->get_next();
			p2 = p1->get_prior();
			p3 = NULL;
			temp = NULL;
			system("cls");
			cout << "\n\n";
			printf(" 管理员页面\n");
			printf(" **************************************************\n");
			printf(" ** 1.增 加 货 物 信 息 **\n");
			printf(" ** **\n");
			printf(" ** 2.删 除 货 物 信 息 **\n");
			printf(" ** **\n");
			printf(" ** 3.浏 览 货 物 信 息 **\n");
			printf(" ** **\n");
			printf(" ** 4.修 改 货 物 信 息 **\n");
			printf(" ** **\n");
			printf(" ** 5.查 找 货 物 信 息 **\n");
			printf(" ** **\n");
			printf(" ** 6.退 出 **\n");
			printf(" **************************************************\n");
			printf("请按键选择:");
			switch (_getch())
			{ 
			case '1':
				system("cls");
				cout << "请输入要增加货物个数:";
				while (cin >> m)
				{ 
					if (atoi(m) > 0)
					{ 
						break;
					}
					else
					{ 
						cout << "请输入正确的数字:";
					}
				}
				system("cls");
				list.Add(atoi(m));
				system("pause");
				break;
			case '2':
				system("cls");
				if (list.get_lenth() == 0)
				{ 
					cout << "暂无数据!\n";
					system("pause");
					break;
				}
				cout << "请输入要删除第几个节点:";
				cin >> n;
				if (n > list.get_lenth() || n < 0)
				{ 
					cout << "输入数字越界!\n";
					system("pause");
					break;
				}
				if (list.Delete(p1, p2, p3, n))
				{ 
					cout << "删除成功!\n";
					system("pause");
				}
				else
				{ 
					cout << "删除失败!\n";
					system("pause");
				}
				break;
			case '3':
				system("cls");
				if (list.get_lenth() == 0)
				{ 
					cout << "暂无数据!\n";
					system("pause");
					break;
				}
				list.Output(list.get_head()->get_next());
				break;
			case '4':
				system("cls");
				if (list.get_lenth() == 0)
				{ 
					cout << "暂无数据!\n";
					system("pause");
					break;
				}
				cout << "请输入要修改的数据:\n";
				cin >> node.get_data();
				list.Modify(p1, p2, p3, temp, node.get_data());
				if(temp)
				{ 
					cout << "请输入修改后的数据:";
					cin >> temp->get_data();
					cout << "修改成功!\n";
					system("pause");
				}
				else
				{ 
					cout << "修改失败!\n";
					system("pause");
				}
				break;
			case '5':
				system("cls");
				if (list.get_lenth() == 0)
				{ 
					cout << "暂无数据!\n";
					system("pause");
					break;
				}
				cout << "请输入要查找的数据:\n";
				cin >> node.get_data();
				if (isok(list.Seek(p1, p2, p3, node.get_data())))
				{ 
					cout << "信息如下:" << node.get_data();
					system("pause");
				}
				break;
			case '6':
				system("cls");
				exit(0);
			}
		}
	}
};

class Worker
{ 
public:
	Worker() 
	{ 
		id = 0;
		age = 0;
		salary = 0;
		name = "";
		sex = "";
	}
	~Worker()
	{ 

	}
	friend ostream& operator<< (ostream& out, Worker& data);
	friend istream& operator>> (istream& in, Worker& data);
	Worker& operator= (Worker& data) // set_data(_data) {data = _data;}
	{ 
		this->id = data.id;
		this->age = data.age;
		this->salary = data.salary;
		this->name = data.name;
		this->sex = data.sex;
		return *this;
	}
	bool operator> (Worker& _data)
	{ 
		if (this->get_id() > _data.get_id())
		{ 
			return 1;
		}
		return 0;
	}
	bool operator== (Worker& data) // 查重
	{ 
		int flag = 0;
		int sign = 0;
		if (this->get_salary() == data.get_salary() && this->get_name() == data.get_name()
			&& this->get_sex() == data.get_sex() && this->get_age() == data.get_age())
		{ 
			flag = 1;
		}
		if (this->get_id() == data.get_id())
		{ 
			sign = 1;
		}
		if (sign == 1 && flag != 1) // 当id重复时,无论其他数据是否重复,都视为重复
		{ 
			return 1;
		}
		else if (flag == 1 && sign == 1) // 当id和其他数据重复时
		{ 
			return 1;
		}
		else if (flag == 1 && sign != 1) // 当id不重复时,其他数据可重复也可不重复
		{ 
			return 0;
		}
	}
	void set_name(string _name) {  name = _name; }
	void set_sex(string _sex) {  sex = _sex; }
	void set_salary(int _salary) {  salary = _salary; }
	void set_age(int _age) {  age = _age; }
	void set_id(int _id) {  id = _id; }

	string get_name() {  return name; }
	string get_sex() {  return sex; }
	int get_salary() {  return salary; }
	int get_age() {  return age; }
	int get_id() {  return id; }
private:
	int id;
	int age;
	int salary;
	string name;
	string sex;
};

ostream& operator<< (ostream& out, Worker& data)
{ 
	out << "ID:" << data.get_id() << "\t\t" << "性别:" << data.get_sex() << "\t" << "姓名:" << data.get_name()
		<< "\t" << "工资:" << data.get_salary() << "\t" << "年龄:" << data.get_age() << endl;
	return out;
}

istream& operator>> (istream& in, Worker& data)
{ 
	cout << "请输入id:";
	cin >> data.id;
	cout << "请输入年龄:";
	while (cin >> data.age)
	{ 
		if (data.age < 18 || data.age > 56)
		{ 
			cout << "请输入年龄在18到56之间的数:";
		}
		else
		{ 
			break;
		}
	}
	cout << "请输入工资:";
	cin >> data.salary;
	cout << "请输入姓名:";
	cin >> data.name;
	cout << "请输入性别:";
	while (cin >> data.sex)
	{ 
		if (data.sex == "男" || data.sex == "女")
		{ 
			break;
		}
		else
		{ 
			cout << "请输入男或女:";
		}
	}
	return in;
}



int main()
{ 
	List<Worker> list;
	Node<Worker> node;
	list.menu(list, node);
}
    原文作者:RooKichenn
    原文地址: https://blog.csdn.net/RooKichenn/article/details/117068672
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞