3.数据结构——链表（单链表，双向链表，循环链表）

2024-02-01 20:23:28

链表

链表的特点
1.逻辑位置上是相邻的，并且一一对应
2.物理位置上不是相邻的，链式存储
3.进行访问操作的时候速度比线性表更慢，是顺序存取，存取第N个数据时，必须先访问前（N-1）个数据。

#################################################################################################
链表有很多种，但是只需要搞懂最基本的单链表就可以搞定所有的链表

链表基本组成是结点，结点是一个结构体，由数据域和指针域组成

首先我们来讲讲什么是头指针，首元结点，头节点

首元结点一定是第一个存放链表数据的结点

单链表也分为两种，一种是带头节点的单链表，一种是不带头结点的单链表。

不带头节点的单链表：

带头结点的链表

讨论1

如何表示空表呢？

不带头结点：


Head_ptr->NULL;//直接头指针指向NULL

带头节点：


*Head_ptr.next->NULL;//头结点指向NULL

讨论2

带头节点和不带头节点又有什么区别呢？

1.便于首元结点的处理（头节点的作用就是简化一些操作，比如我们进行插入操作的时候，如果没有头节点，那么我们的插入就要特判是不是插入到第一个位置的前面，然后单独处理这种情况，如果我们有头节点，那么就会简单许多，省去了特判。）

2.便于空表和非空表的统一处理（无论链表是否为空，头指针都是指向头节点的非空指针，因此空表和非空表处理也统一了）

后面会详细讲解插入操作的各种方法，加头节点后怎么办？不加头节点又如何处理？

讨论3

头节点的数据域中存储什么用呢？

1.头结点中的数据域可以不存储任何的数据，也可以存储我们结点的个数

注意： 头节点不能算链表的长度！！！！

#################################################################################################

先放上最基本的信息

#include <iostream>
using namespace std;
#define MAXSIZE 100
#define TRUE 1
#define failure 0
#define FALSE 0
#define OK 1 
#define ERROR 0
#define INFEASIBLE -1//不可行的
#define OVERFLOW -2//溢出
typedef int Status;//状态，一般指返回值的类型，为什么是int？状态一般用用来判断是否成功
typedef char ElemType;//一般指元素的类型，也可以自己随便定义

typedef struct
{
	string name;
	int yaer;
}ElemType;
typedef struct Lnode//声明结点的类型和指向结点的指针类型
{
	ElemType data;            //数据域
	struct Lnode *next;     //指针域
} Lnode, *LinkList;  //LinkList为指向结构体Lnode的指针类型

#################################################################################################

我们现在写的都是带头节点的链表

1.链表初始化

Status InitList(LinkList &L)
{
	L = new Lnode;//生成头节点
	if (!L)
	{
		cout << "内存空间不足" << endl;
		return ERROR;
	}
	L->next = NULL;
	return OK;
}

2.判断链表是否为空

//判断思路：何为空表，链表中没有元素，我们可以称为空链表
//头指针和头节点不算做链表的长度，所以我们就只需要判断头
//节点指针域是否为空就可以
int EmptyList(LinkList L)
{
	if (L->next)
		return 1;
	else
	{
		return 0;
	}
}

3.链表的销毁操作,因为都是new出来的，所以我们必须每一个都手动释放掉

Status DestorryList(LinkList &L)
{
	LinkList temp;
	while (L)
	{
		temp = L;
		L = L->next;
		delete temp;
	}
	return OK;
}

4.清空单链表，清空单链表和销毁单链表非常的相似，销毁是连头指针一起销毁，但是清空单链表我们就需要保留头指针，其他的和销毁的单链表一样

Status ClearList(LinkList &L)
{
	Lnode* p, *q;
	p = L->next;
	while (p)//没到表尾一直执行
	{
		q = p->next;
		delete p;
		p = q;
	}
	L->next = NULL;//将头节点指针域置为空
	return OK;
}

5,求单链表的长度

int GetListLen(LinkList L)
{
	int len = 0;
	while (L->next)
	{
		len++;
		L = L->next;
	}
	return len;
}

6.获取单链表中的第i个元素

Status GetElem(LinkList L, int i, ElemType &e)
{
	int j = 1;
	LinkList p;
	p = L->next;
	while (p&&j < i)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i)
		return ERROR;
	e = p->data;
	return OK;
}

7.单链表的查找，返回查找到的位置

int LocateList(LinkList L, ElemType e)
{
	int i = 0;
	LinkList p = L->next;
	while (p)
	{
		i++;
		if (p->data.name == e.name &&p->data.yaer == e.yaer)
			return i;
		p = p->next;
	}
	return 0;
}

8.在第i个结点前面插入元素e

Status InsrtList(LinkList &L, int i, ElemType e)
{
	int j = 0;
	LinkList p;
	p = L;
	while (p || j < i - 1)//寻找第i-1个结点，p指向i-1结点
	{
		j++;
		p = p->next;
	}
	if (!p || j > i - 1)//p为空或者插入位置不合法
		return ERROR;
	LinkList temp = new Lnode;
	temp->data.name = e.name;
	temp->data.yaer = e.yaer;
	temp->next = p->next;
	p->next = temp;
	return OK;
}

9.删除第i个结点

Status DeleteList(LinkList &L, int i, ElemType &e)
{
	int j = 0;
	LinkList p = L;
	while (p || j < i - 1)//找到第i-1个结点
	{
		j++;
		p = p->next;
	}
	if (!(p->next) || j > i - 1)
	{
		return ERROR;
	}
	e.name = p->next->data.name;
	e.yaer = p->next->data.yaer;
	p->next = p->next->next;
	delete p->next;
	return OK;
}

10.头插法,插入n个元素进去

void Head_InsertList(LinkList &L, int n)
{
	for (int i = 0; i < n; i++)
	{
		Lnode *temp = new Lnode;
		cin >> (L->data.name);
		cin >> temp->data.yaer;
		temp->next = L->next;
		L->next = temp;
	}
}

11.尾插法

void End_InsertList(LinkList &L, int n)
{
	//找到最后一个位置
	LinkList q;
	q = L;
	while (q)
	{
		q = q->next;
	}
	//这个时候q就是最后一个元素了
	for (int i = 0; i < n; i++)
	{
		Lnode *temp = new Lnode;
		cin >> (L->data.name);
		cin >> temp->data.yaer;
		temp->next = q->next;
		q->next = temp;
		q = q->next;
	}
}

#################################################################################################

以上就是带头结点的各种简单的操作，我们刚才说带头结点就会简化插入等操作，那我们现在来看看不带头节点的链表是如何插入的

分为三种情况

1.插入到最前面
2.插入到中间
3.插入到最后面

先看看新的结构体和结点

#include <iostream>
#include <string>
using namespace std;
#define False1 0
#define True1 1
typedef struct Node
{
	int value;
	struct Node *next;
}Node, *LinkList;

先上一段“错误的”插入代码

int Insert_List(LinkList &L, int new_value)
{
	Node *previous;
	Node *current;
	current = L->next;
	while (current&&new_value>current->value )//找到当前结点current
	{
		previous = current;
		current = current->next;
	}
	Node* temp = new Node;
	if (!temp)
	{
		cout << "空间不足" << endl;
		return False1;
	}
	if (current)//如果这个结点不是空结点，就可对这个结点进行操作
	{
		previous->next = temp;
		temp->next = current;
	}
	return True1;
}

但我们的插入位置在链表的中间的时候这段代码就是正确的，但是，当你的插入位置变成代码的最后面的时候那么我们的插入代码便会失效，更可怕的是如果我们的插入位置如果是第一个元素，因为头指针指向的是第一元素！！那么这个代码的头指针将会改变！！！

解决方法1:

将头指针设置为全局变量，但是这样设置以后我们的这个函数就只能对这个链表起作用了

解决方法2：

我们传入一个指向头指针的指针作为函数的参数进行传递，然后进行间接访问，函数不仅可以获得头指针的值，还可以向它存储一个新的指针值。所以我们传入参数的类型应该是Node**(等价于LinkList*)

看看新的函数：

int Insert_List(LinkList *L, int val)
{
	Node *current;
	Node *previous=NULL;
	Node *temp;
	current = *L;
	while (current!=NULL&&current->value <val)//这个时候的val在previous和current之间了
	{
		previous = current;
		current = current->next;
	}
	temp = new Node;
	if (!temp)
	{
		return False1;
	}
	temp->value = val;
	temp->next = current;
	//关键的一步，因为我们前面初始化的时候
	//previous=NULL，如果还是NULL，说明我们的前面就是
	//没有变，也就是我们插入的位置是第一个位置
	if (previous->next == NULL)
	{
		*L = temp;//插入的位置是第一个位置那么我们就把第一个位置进行改变，
		//头节点也会跟着L改变的
	}
	else
	{
		previous->next = temp;
	}

	return True1;
}

#################################################################################################

循环链表

优点：从一节点出发可以找到表中其他结点（可以从a1找到an，也可以从an找到a）

和普通链表唯一不同的就是最后一个链表的指针域指向了第一个结点

讨论1：如何表示空表？

这个节点是头节点，头节点的指针域中存放了头指针

讨论2：既然是循环，那么如何中止呢？

普通单链表中判断中止的条件是指针域为空，但是这个地方没有空的指针域，那么判断条件就是看指针域是不是等于头指针

p->next!=L;

讨论3：时间复杂度分析

这个情况下我们找第一个元素的时间复杂度是O（1），找最后一个元素的时间复杂度是O（n）

讨论4：尾指针表示单链表循环

假设尾指针的存储位置是R

那么a1的位置就是

R->next->next;

这样之后我们找第一个结点和找最后一个结点的复杂度就都是O(1)

**所以，我们使用循环链表的时候通常是使用带尾指针的循环链表 **

合并两个循环链表

Ta，Tb分别是尾结点

int connect_List(LinkList &Ta, LinkList &Tb)//Ta，Tb是尾结点
{
	//我们只需要一个头结点，所以我们要释放一个头节点
	LinkList p = Ta->next;//先弄一个p来保存Ta的头结点
	Ta->next = Tb->next->next;//Tb的表头链接Ta的表尾
	delete Tb->next;
	Tb->next = p;
	return 1;
}

#################################################################################################

双向链表

和单链表非常相似，不过多了一个前驱节点的地址，操作起来更加的方便，我们进而推广可以创建出双循环链表！

讨论1：如何表示空表

头指针的前驱和后继都是NULL

注意1：我们的普通双向链表头节点的prior为NULL，尾结点的next也是NULL;在双向循环链表中，尾结点的next指向的是头节点的prior,头节点的prior指向的是尾结点的next

双向循环链表示意图

双向链表的特征：

1.链表的对称性

我们就讲两个特殊的：

双向链表的插入和删除操作

#include <iostream>
#include <string>
using namespace std;
#define False1 0
#define True1 1
typedef struct Node
{
	int value;
	struct Node *next;
	struct Node *prior;
}Node, *LinkList;
int Insert_DouList(LinkList &L,int val)
{
	Node *current=L;
	Node *temp;
	while (current->next !=NULL && val<( current->value ) )
	{
		current = current->next;
	}
	while (current == NULL)
	{
		return False1;
	}

	//核心代码
	temp = new Node;
	temp->prior = current->prior;
	current->prior->next = temp;
	temp->next = current;
	current->prior = temp;
	temp->value = val;
	return True1;
}

int DeleteDouList(int i,LinkList L)//删除第i个元素
{
	Node *current=L;
	int j = 0;
	while (current != NULL &&j < i)
	{
		j++;
		current = current->next;
	}
	while (current == NULL)
	{
		return False1;
	}
	//围绕第i个元素进行操作；
	current->prior->next = current->next ;
	current->next->prior = current->prior;
	return True1;
}

码农公寓

链表

循环链表

双向链表

相关文章