【数据结构】双链表(c++)

数据结构 前端之家
前端之家收集整理的这篇文章主要介绍了【数据结构】双链表(c++)，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。

头文件：



#pragma once

#include <iostream>
#include <assert.h>
using namespace std;

template<class Type>
class List;

// 结点类
template<class Type>
class NodeList
{
	friend class List<Type>;
public:
	NodeList();
	NodeList(Type d,NodeList<Type> *n = NULL,NodeList<Type> *m = NULL);
private:
	Type data;
	NodeList<Type>* next;
	NodeList<Type>* prio;
};

// 链表类
template<class Type>
class List
{
public:
	List();
	~List();
public:
	void show_list();
	void tail_insert(Type const &x);
	void head_insert(Type const &x);
	void sort();
	void head_delete();
	void tail_delete();
	void val_insert(Type const &x);
	NodeList<Type>* find(Type const &x);
	void val_delete(Type const &x);
	Type length();
	void reverse();
	void clear();
	void destroy();
	void quit_system(Type &x);
protected:
	NodeList<Type>* BuyNode(Type x = Type())
	{
		NodeList<Type>* p = new NodeList<Type>(x);
		assert(p != NULL);
		return p;
	}
private:
	NodeList<Type>* first;
	NodeList<Type>* last;
};

// 结点类的构造函数
template<class Type>
NodeList<Type>::NodeList()
{
	data = Type();
	next = NULL;
	prio = NULL;
}

template<class Type>
NodeList<Type>::NodeList(Type d,NodeList<Type> *m = NULL)
{
	data = d;
	next = n;
	prio = m;
}

// 链表类的构造函数
template<class Type>
List<Type>::List()
{
	first = last = BuyNode();
	first->prio = NULL;
}

// 链表类的析构函数
template<class Type>
List<Type>::~List()
{
	destroy();
}

// 显示
template<class Type>
void List<Type>::show_list()
{
	NodeList<Type> *p = first->next;
	while (p != NULL)
	{
		cout << p->data << "->";
		p = p->next;
	}
	cout << "NULL" << endl;
}

// 尾插
template<class Type>
void List<Type>::tail_insert(Type const& x)
{
	NodeList<Type> *p = BuyNode(x);
	last->next = p;
	p->prio = last;
	last = p;
	first->data++;
}

// 头插
template<class Type>
void List<Type>::head_insert(Type const &x)
{
	NodeList<Type> *p = BuyNode(x);
	if (first->data == 0)
	{
		first->next = p;
		p->prio = first;
		last = p;
	}
	else
	{
		p->next = first->next;
		first->next = p;
		p->prio = first;
		p->next->prio = p;
		last = p;
		for (int i = 0; i < first->data; ++i)
		{
			last = last->next;
		}
	}
	first->data++;
}

// 排序
template<class Type>
void List<Type>::sort()
{
	if (first->data == 0)
	{
		return;
	}
	if (first->data == 1)
	{
		show_list();
	}
	NodeList<Type> *t = first->next;
	NodeList<Type> *p = t->next;
	NodeList<Type> *q = NULL;
	t->next = NULL;
	p->prio = NULL;
	last = t;
	first->data = 1;
	while (p != NULL)
	{
		val_insert(p->data);
		q = p;
		p = p->next;
		delete q;
	}
}

// 头删
template<class Type>
void List<Type>::head_delete()
{
	if (first->data == 0)
	{
		cout << "the list is empty,cannot delete!" << endl;
		return;
	}
	NodeList<Type> *p = first->next;
	if (first->data == 1)
	{
		last = first;
		first->next = NULL;
	}
	else
	{
		first->next = p->next;
		p->next->prio = first;
	}
	delete p;
	first->data--;
}

// 尾删
template<class Type>
void List<Type>::tail_delete()
{
	if (first->data == 0)
	{
		cout << "the list is empty,cannot delete!" << endl;
		return;
	}
	NodeList<Type> *s = last;
	if (first->data == 1)
	{
		first->next = NULL;
		first->prio = NULL;
		last = first;
	}
	else
	{
		last = last->prio;
		last->next = NULL;
		first->prio = NULL;
	}
	delete s;
	first->data--;
}

// 按值插入
template<class Type>
void List<Type>::val_insert(Type const &x)
{
	if (first->data == 0)
	{
		tail_insert(x);
		return;
	}
	NodeList<Type> *p = first->next;
	NodeList<Type> *s = BuyNode(x);
	while (p->data < x && p->next != NULL)
	{
		p = p->next;
	}
	if (p->data >= x)
	{
		p->prio->next = s;
		s->prio = p->prio;
		s->next = p;
		p->prio = s;
		first->data++;
	}
	else
	{
		tail_insert(x);
	}
}

// 查找
template<class Type>
NodeList<Type>* List<Type>::find(Type const &x)
{
	NodeList<Type> *s = first->next;
	while (s != NULL)
	{
		if (s->data == x)
		{
			return s;
		}
		s = s->next;
	}
	return NULL;
}

// 按值删除
template<class Type>
void List<Type>::val_delete(Type const &x)
{
	if (first->data == 0)
	{
		cout << "the list is empty,cannot delete!" << endl;
		return;
	}
	NodeList<Type> *s = find(x);
	if (s == NULL)
	{
		cout << "the number is not exist,can not delete!" << endl;
		return;
	}
	if (s->next != NULL)
	{
		s->prio->next = s->next;
		s->next->prio = s->prio;
		first->data--;
		delete s;
	}
	else
	{
		tail_delete();
	}
}

// 求长度
template<class Type>
Type List<Type>::length()
{
	return first->data;
}

// 反转
template<class Type>
void List<Type>::reverse()
{
	if (first->data == 0)
	{
		return;
	}
	if (first->data == 1)
	{
		show_list();
	}
	NodeList<Type> *t = first->next;
	NodeList<Type> *p = t->next;
	NodeList<Type> *q = NULL;
	t->next = NULL;
	p->prio = NULL;
	last = t;
	first->data = 1;
	while (p != NULL)
	{
		head_insert(p->data);
		q = p;
		p = p->next;
		delete q;
	}
}

// 清空
template<class Type>
void List<Type>::clear()
{
	if (first->data == 0)
	{
		return;
	}
	while (first->next != NULL)
	{
		tail_delete();
	}
}

// 摧毁
template<class Type>
void List<Type>::destroy()
{
	clear();
	delete first;
}

// 退出系统
template<class Type>
void List<Type>::quit_system(Type &x)
{
	x = 0;
}



主函数：

// 用c++实现单链表

#include "DList.h"

int main()
{
	List<int> mylist;
	int input = 1;
	int insert;
	while (input)
	{
		cout << "*********************************************************************" << endl;
		cout << "*     [1] show_list                       [2] tail_insert           *" << endl;
		cout << "*     [3] head_insert                     [4] sort                  *" << endl;
		cout << "*     [5] head_delete                     [6] tail_delete           *" << endl;
		cout << "*     [7] val_insert　　　　　　　　　　　[8] find                  *" << endl;
		cout << "*     [9] val_delete                      [10] length               *" << endl;
		cout << "*     [11] reverse                        [12] clear                *" << endl;
		cout << "*     [13] destroy                        [14] quit_system          *" << endl;
		cout << "*********************************************************************" << endl;
		cout << "please choose:";
		cin >> input;
		switch (input)
		{
		case 1:
			mylist.show_list();
			break;
		case 2:
			cout << "please enter the number want to insert(-1 end):";
			while (cin >> insert,insert != -1)
			{
				mylist.tail_insert(insert);
			}
			break;
		case 3:
			cout << "please enter the number want to insert(-1 end):";
			while (cin >> insert,insert != -1)
			{
				mylist.head_insert(insert);
			}
			break;
		case 4:
			mylist.sort();
			break;
		case 5:
			mylist.head_delete();
			break;
		case 6:
			mylist.tail_delete();
			break;
		case 7:
			cout << "please enter the number want to insert:";
			cin >> insert;
			mylist.val_insert(insert);
			break;
		case 8:
			cout << "please enter the number want to find:";
			cin >> insert;
			if (mylist.find(insert) == NULL)
			{
				cout << "the number is not exist!" << endl;
			}
			else
			{
				cout << "the number at the " << mylist.find(insert) << endl;
			}
			break;
		case 9:
			cout << "please enter the number want to delete:";
			cin >> insert;
			mylist.val_delete(insert);
			break;
		case 10:
			cout << "the length is" << "  " << mylist.length() << endl;
			break;
		case 11:
			mylist.reverse();
			break;
		case 12:
			mylist.clear();
			break;
		case 13:
			mylist.destroy();
			break;
		case 14:
			mylist.quit_system(input);
			break;
		default:
			break;
		}
	}
	return 0;
}



清空：








头删：







头插：






反转：






排序：






尾删：






尾插：






按值删除：






按值插入：




猜你在找的数据结构相关文章

【数据结构】键树
键树的基本概念 键树又称数字查找树（Digital Search Tree）。 它是一棵度大于等于2的树，...
【数据结构】绪论
[TOC] 基本概念 数据： 数据 是对客观事物的符号表示，在计算机科学中指所有能输入到计算机...
【数据结构】证明法
[TOC] 反证法 基本概念： 一般地，假设原命题不成立（即 在原命题的条件下，结论不成立），...
数据结构与算法系列之目录
最近抽空整理了&quot;数据结构和算法&quot;的相关文章。在整理过程中，对于每种数...
【数据结构】数组
[TOC] 矩阵在计算机图形学、工程计算中占有举足轻重的地位。在数据结构中考虑的是如何用最...
[操作系统]操作系统中断机制
1.当中断发生时，cpu立即进入核心态 2.当中断发生后，当前进程进入暂停状态，操作系统内核...
[日常] 浏览器前进后退与数据结构的思想
一张图保存一下 红点是当前地址 白色箭头是新打开页面 黑色箭头是后退页面 栈的思想 , 后退...
[算法] 开放寻址法解决哈希冲突方式
开放寻址法：又称开放定址法，当哈希冲突发生时，从发生冲突的那个单元起，按照一定的次序...
二叉树的基本概念介绍与代码实现（多图+代码）
@ 树的基本概念 图1 树的结点 结点：使用树结构存储的每一个数据元素都被称为“结点”。例...
史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)
1.准备工作 首先包含头文件，定义链表结构体，产生随即链表的范围，定义全局头尾节点。 #i...
LinuxWindowsCentOSUbuntuNginxWebServiceScalaMemcacheApacheRedisDockerBashAzureTomcatLNMPShell数据结构服务器运维网络安全
xebugnodemondocker-copydcoselasticsearcwindows-contdocker-windodocker-awsamazon-cloudenvoyproxyhashicorp-vaswisscomdevkafka-pythonzscalerphoton-osdocker-swarmkamongoogle-cloudconcoursewso2-ampersistent-vapi-managerprocess-manamanjarojenkins-workhypriotremoteapikeystonejsbitcoindbitcoin-test