[数据结构与算法]一星期肝出的线性表&链表的多种实现和各种操作的完整代码(二)(十万字解析系列)

一星期肝出的线性表&链表的多种实现和各种操作的完整代码(二)(十万字解析系列)

自从上篇更新了有关顺序表的11种操作之后，时隔两三天之后今天我来更新链表的有关操作和实现，由于链表的知识比较重要，更是后面的基础，这次我将用十万字长文来讲解！为了尽量让文章通俗易懂，这次我用同一种语言讲解和实现（上篇用了两种语言）,大家可以把代码复制到你的编译器中编译运行，Let‘s go ！

单链表的定义

同志们应该知道，我们所了解到的单链表实际上是顺序表的一种链式存储结构，其特点是用一组任意的存储单元存储线性表里的元素，在顺序存储结构中，我们知道存储在里面的存储单元必须是连续的，但是在链式存储中有个好处，就是这块存储空间可以是连续的，也可以不是连续的。
正是这种不连续性，我们就不能像数组那样存储，而是应该除了存储本身的数据信息外，每个结点还需要存储下个结点的地址信息。
一个结点就像一块倒着的长方形，前半部分存储的是结点的数据域，后半部分存储的是下一个指针域，指针需要指向下一个结点，即存储的是下一个结点的地址。若一个结点没有下一个结点，应该置这一个结点的指针域为空，废话不多说，下面开始单链表的讲解：

单链表的实现与各种操作

在这里讲一下几个名词：
头结点：头结点中不存储数据，即数据域为空，指针域不为空，指向首元结点。最重要的是，头结点可有可无。
头指针：这里和头结点区分一下，头指针是必须要有的，如果有头结点则指向头结点；若没有头节点，则指向首元结点。（这里的指向的意思就是指针里存储的是首元结点的地址）
首元结点：即第一个完整的节点（结点或者节点都可）
尾结点：顾名思义，就是最后一个节点。

1、定义一个头结点

刚刚我们说一个节点中存储了数据和下一个节点的地址，因此我们可以这样来描述一个节点：

#include<iostream>
using namespace std;
typedef int ElemType;
typedef int Status;
typedef struct LNode{              //构造结点类型结构体
	ElemType data;                   //数据域
	struct LNode *next;            //指针域，指向这个结构体的指针
}LNode,*LinkList;                  //结构体类型变量和指向单链表的头指针

在这里需要注意一下，LinkList和Lnode*本质上是一样的，但可以作指针。但是为了方便，我们一般用LinkList来定义单链表，强调定义的是链表的头指针；LNode *用来定义链表里任意的一个指向结点的指针变量。
增设头结点的作用：
1.便于首元结点的处理。首元结点的地址存储在头结点之中，对链表的第一个元素和其他元素相同，不必做特殊处理。
2.便于空表与非空表的统一处理。当链表不设头结点时，链表L为单链表的头指针，它应该指向首元结点，当链表为空时，L指针为空（即LNULL）；
当链表增加头结点时，无论链表是否为空，头指针都会是一个指向头结点的非空指针（即L->nextNULL）

2、单链表的初始化

单链表的初始化就是构造一个空表.
算法实现：
1、生成新节点作为头结点，用头指针指向头结点（指向就是连接的作用）
2、将头结点的指针域置为空。
代码实现：

Status InitList(LinkList &L)
{
	L=new LNode;    //生成新结点作为头指针，指向头结点
	L->next=NULL;  //令指针域为空
	return OK;
}

这里有一点需要注意，就是为什么要用&这个符号，这是因为这里我用的是c++的语法—引用，可以直接全局改变它的值；还有这了的new关键字，L=new LNode就相当于c语言的L=(LNode *)malloc(sizeof(Lnode)),就是给结点分配内存空间。

3、创建单链表

这里有两种创建单链表的方法，根据插入位置的不同，一种是头插法，一种是尾插法。

1、头插法

算法实现：
1、创建一个只有头结点的单链表
2、根据创建链表的元素个数，循环以下操作：
生成一个新节点*p;
输入元素给新节点赋值；
将新节点的指针域指向头结点；(即给新节点的指针域赋值)
将新节点作为新的头结点；
代码实现：

void CreateList_H(LinkList L,int n)
{
	L=new LNode;
	L->next=NULL;
	for(int i=0;i<n;i++)
	{
		LinkList p=new LNode;
		cin>>p->data;
		p->next=L;
		p=L;              
	}
}

2、尾插法

算法实现：
1、创建一个只有头结点的空链表
2、尾指针r初始化，指向头结点
3、根据元素个数，循环以下操作：
生成一个新节点；
输入元素的值赋值给新结点；
将新结点插入到尾结点之后；
尾指针指向新节点；
代码实现：

void LinkList_R(LinkList L,int n)
{
	L=new LNode;
	L->next=NULL;
	LinkList r=L;
for(int i=0;i<n;i++)
{
	LinkList p=new LNode;
	cin>>p->data;
	p->next=NULL;
	L->next=p;
	r=p;
}

4、获取单链表某个位置的值

算法实现:
获取链表某个位置的值，只能从链表的首元结点出发，顺着链表逐个结点向下访问。
1、用指针p指向首元结点，用 j 作计数器初值赋为1
2、从首元结点开始顺着next指针往下遍历，只要当前指针p不为空，则循环以下操作：
p指向下一个结点；
计数器 j 加一；
3、退出循环，用e保存当前的数据域
代码实现：

Status GetElement(LinkList L,int i,ElemType e)
{
   LinkList p=L->next;  //指针p指向首元结点
   int j=1;
   while(!p && j<i)
   {
   	p=p->next;
   	j++;
   }
   if(p==NULL || j>i)
   return ERROR;
   else
   e=p->data;
   return OK;
}

5、值的查找

给定一个值，通过遍历链表中的元素，看是否有值跟我们给定的值相同，有就返回p。
算法实现：
1、用指针p指向首元结点
2、从首元结点开始顺着next域向下遍历，直到我们给定的元素e与链表中有元素相同才停止遍历。
代码实现：

Status *LocateElem(LinkList L,ElemType e)
{
	LinkList p=L->next;
	while(p->data!=e)
	{
		p=p->next;
	}
	return p;
}

6.链表的插入操作

链表的插入操作主要是涉及到链表的操作，假设我们创建一个结点p，要将p插入在结点A和B之间，我们需要做什么呢？我们需要将A的next域指向新节点p，将p的next域指向结点B，这样就可以连接起来了。
算法实现：
1、查找结点第（i-1）,并且由指针p指向该结点。
2、生成一个新节点*s
3、将新节点的数据域赋值e
4、将s的指针域指向第i+1个结点
5、将p的指针指向结点s
代码实现：

Status ListInsert(LinkList &L,int i,ElemType e)
{
	LinkList p=L;
	int j=0;
	while(p && j<i-1)
	{
		p=p->next;
		j++;
	}
if(p==NULL || j>i-1)
return ERROR;
LinkList s=new LNode;
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}

7、链表的删除操作

给定一个表头head,并且给定一个位置i，将位置为i的结点删除,并且返回新链表的结点，为什么要返回新链表的结点呢？想一想，这是因为被删除的结点可能是原来的结点。所以链表的结点问题可以分成以下三种情况讨论：
(1)空链表：无法删除，直接返回空结点；
(2)非空链表的非头结点：缓存一下头结点的的后继结点，释放头结点，再返回这个后继结点；
(3)非空链表的头结点：这个就比较复杂了，我会在代码中注释说明每一步为什么要这样做；

LinkList ListDeleteNode(ListNode *head,int i)
{
	LinkList pre,del,aft;    //定义三个指针变量，分别指向：要被删除的结点；前驱结点；后继结点；
	int i=0;
	if(head==NULL)          //空表的情况
	{
		return NULL;
	}
	else if(i==0)                 //不是空表，但是删除的是头结点,即i=0
	{
		del=head;              //将头结点赋值给要被删除的结点，准备释放
		head=head->next; //将头结点指向下一个结点
		delete(del);            //释放头结点
		return head;          //返回头指针
	}
	pre=head;
	else if(pre && j<i-1)
	{
		pre=pre->next;
		++j;
	}
	del=pre->next;
	aft=del->next;
	pre->next=aft;
	free(del);
	return head;
}

到此为止我们把链表相关的基本操作都给做完了，下面我们来看看各个部分的功能具体是怎么实现的。
最后补一个关于链表的销毁操作

8、链表的销毁

算法实现：
1、首先肯定是要把头结点传入
2、然后循环的把结点传入free()
3、最后把链表的头结点置空

void ListDestoryList(LinkList *phead)
{
	LinkList head=* phead;
	while(head)
		{
			head=ListDeleteNode(head,0);
		}
		*phead=NULL;         //这里必须置链表的头结点的指针为空，不然之后就会成为野指针了
}

最后我们用代码把它全部实现出来:

下一篇文章更新顺序表和链表一起的所有操作，一条龙服务，打上注释，估计有一千行代码;