2019-11-03

code / c++

9 分钟读完 (大约 1351 个字)

Double Linked List

1.为什么要用链表

大家在存储多组数据时，会选用数组，但在数组中间删减或是增加数据时，需要将整个数组往前后“平移”。

增加：

void Add(int value, int index, int size)
{
	for(int i = index, i <= size; i++)
	{
		a[i+1] = a[i];
	}
	a[index] = value;
}

删减：

void Delete(int v, int size)
{
	for(int i = index, i <= size; i++)
	{
		a[i] = a[i+1];
	}
}

这样的时间复杂度会很高，也十分麻烦，需要遍历一遍才能完成操作，而链表可以之前在中间插入、删除。

2.双链表模型

一般来说，链表有“head”与“tail”，头与尾的中间用来存储数据，每个节点都有两个指针，指向节点的前后。

next：后指针，代表这个节点的下一个节点。

pre：前指针，代表这个节点的上一个节点。

3.创建

双链表需要一个data数据、前指针和后指针，我们使用结构体将它们封装起来。

struct list
{
	int value;//数据
	list *next;//后指针 
	list *pre;//前指针
};//链表结构体

4.初始化

我们已经创建好了一个链表，那么需要对它进行初始化操作，书写初始化函数。

我们需要为head和tail开一个新的空间，否则将成为一个没空间没内存的“野指针”。

void initialization(list *&head, list *&tail)//传入头指针与尾指针
{
	head = new list ();
	tail = new list ();
    //为head、tail开空间
	head -> next = tail;//head的"next"指向tail
	head -> pre = NULL;//head的"pre"指向NULL(空)
	tail -> pre = head;//tail的"next"指向tail
	tail -> next = NULL;//tail的"next"指向NULL(空)
}//初始化

5.插入、删除

那么链表的插入、删除是怎样实现的呢？

插入

我们想将一个new data插入data之后，我们需要将data的“next”指针指向new data，Tail的“pre”指针指向new data，new data的“next”指针指向TAIL、“pre”指针指向data。

void insert(list *&tail, int v)
{
    list *p = new list ();
    list *q = new list ();
	q = tail -> pre;
    p -> value = v;
    p -> next = tail;
    tail -> pre = p;
    p -> pre = q;
    q -> next = p;
}//添加

删除

若想将data删掉，我们需要将HAED的“next”指针指向TAIL，TAIL的“pre”指针指向HEAD。

void  Delete(list *&head, int v)
{
	list *p = head;
	p = p -> next;
	while(p -> next != NULL)
	{
		if(p -> value == v)
		{
			p -> next -> pre = p -> pre;
			p -> pre -> next = p -> next;
			break;
		}
		p = p -> next;
	}
}//删除

6.打印

若想将链表中的数据打印出来，需要从head开始向后循环，”head->value“代表head节点指向的数据，每打印一个数据后，将head替换为”head->next“,也就是head现在指向的是head的下一个，直到head为空时，也就是head打印最后一个数据后，结束打印。

void  print(list *head)
{
	cout << "开始打印"  << endl; 
	head = head -> next;
	while(head -> next != NULL)
	{
		cout << head -> value << endl;
		head = head -> next;
	}
	cout << "结束打印"  << endl; 
}//打印

7.清空

删除每一个节点指针，循环下去。需要注意的是，我们需要创建一个新的指针来存储删除前指针的下一个指针，这是因为节点被删除后就不具备指向下一个的作用了，会导致找不到节点而出现很多问题。

void Empty(list *head)
{
	list *p = new list ();
	list *HEAD = head;
	HEAD = HEAD -> next;
	while(HEAD -> next != NULL)
	{
		p = HEAD -> next;
		HEAD -> next -> pre = HEAD -> pre;
		HEAD -> pre -> next = HEAD -> next;
		delete HEAD;
		HEAD = p;
	}
}//清空

8.完整代码

网上很多代码都写了“typedef”，身边一些同学也这么写过，据了解后发现“typedef”在c语言书写时会较轻松。
因为c语言在定义一个指针时不能直接“list xxx”，而需要“struct list xxx”。

传参时是否加“&”，是根据你的功能是否需要修改链表的头指针的值，若不改变使用“*”即可。

#include<iostream>
using namespace std;
struct list
{
	int value;//数值 
	list *next;//下一个 
	list *pre;//上一个 
};//链表结构体 
int x;
void initialization(list *&head, list *&tail)
{
	head = new list ();
	tail = new list ();
	head -> next = tail;
	head -> pre = NULL;
	tail -> pre = head;
	tail -> next = NULL;
}//初始化 
void insert(list *&tail, int v)
{
    list *p = new list ();
    list *q = new list ();
	q = tail -> pre;
    p -> value = v;
    p -> next = tail;
    tail -> pre = p;
    p -> pre = q;
    q -> next = p;
}//添加 
void Empty(list *&head)
{
	list *p = new list ();
	list *HEAD = head;
	HEAD = HEAD -> next;
	while(HEAD -> next != NULL)
	{
		p = HEAD -> next;
		HEAD -> next -> pre = HEAD -> pre;
		HEAD -> pre -> next = HEAD -> next;
		delete HEAD;
		HEAD = p;
	}
	
}//清空
void  Delete(list *&head, int v)
{
	list *p = head;
	p = p -> next;
	while(p -> next != NULL)
	{
		if(p -> value == v)
		{
			p -> next -> pre = p -> pre;
			p -> pre -> next = p -> next;
			break;
		}
		p = p -> next;
	}
}//删除
void  print(list *head)
{
	cout << "开始打印"  << endl; 
	head = head -> next;
	while(head -> next != NULL)
	{
		cout << head -> value << endl;
		head = head -> next;
	}
	cout << "结束打印"  << endl; 
}//打印 
int main()
{
	list *head, *tail;
	initialization(head, tail);
	while(1)
	{
		cout << "1.insert" << endl
			 << "2.Empty"  << endl
			 << "3.print"  << endl
			 << "4.Delete" << endl
			 << "5.EXIT"   << endl;
		cin >> x;
		switch(x)
		{
			case 1: cin >> x;
			insert(tail, x);
				break;
			case 2: Empty(head);
				break;
			case 3: print(head);
				break;
			case 4: cin >> x;
			Delete(head, x);
				break;
			case 5: return 0;
		}
	}
	return 0;
}

# data structure