C语言学习笔记——链表

原 作者 张毅迅 | 发表于 | 分类于 2019级

C语言学习笔记

链表

创建链表

  • 链表是什么：
    • 其实是多个结构体，里面存有数据和指针，其中上一个结构体的指针成员指向了下一个结构体，如此往复，就可以实现链表。
    • 如果我们想在链表后面加入新的内容，只需要再创建（malloc）一个节点，并使之前尾部的节点中的指针指向他。
  • 链表可以分为两种：有空头和无空头，有空头也就是第一个节点使不储存数据的，其他节点都接在他的后面，无空头的链表第一个节点存有数据。
  • 下面是一个无空头链表的创建：
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

//节点结构体
struct Node
{
	int a;
	struct Node* pNext;
};


//全局位置定义链表头尾指针
struct Node* g_pHead = NULL;
struct Node* g_pEnd = NULL;


//创建链表，在链表中增加一个数据(尾添加)
void AddNodeToList(int a)
{
	//创建一个节点
	struct Node* pTemp = (struct Node*)malloc(sizeof(struct Node)); 

	//节点数据进行赋值
	pTemp -> a = a;
	pTemp -> pNext = NULL;//链表访问越界经常是因为这一步没有写，这一步非常重要

	//链接到前面
	if( NULL == g_pHead || NULL == g_pEnd)
	{
		//这里的意义是即使头也是尾，体现了无空头的意义。
		g_pHead = pTemp;
		g_pEnd = pTemp;
	}


	else
	{
		//这里的意义是尾巴先接上、在挪动，顺序一定不能错
		g_pEnd -> pNext = pTemp;
		g_pEnd = pTemp;
	}
	return;
}


int main()
{
	g_pHead;
	AddNodeToList(1);
	AddNodeToList(2);
	AddNodeToList(3);
	AddNodeToList(4);
	AddNodeToList(5);
	
		
	return 0;
}
  • 链表创建完成之后，对于链表的操作还有增、删、改、查，后面都会讲到。

链表的头插法

  • 通过上面的代码，可以发现，每次我们创建新的节点时，都是在尾部创建的，移动的是pEnd指针，这样的插入方式比较符合我们的习惯，就像贪吃蛇一样，指针在向后移动。
  • 既然能向后插入，也就是尾插法，那一定也会有头插法，即移动的指针是pHead，不断向前移动。
void headinsert(int a)
{
	NODE* new = (NODE*)malloc(sizeof(NODE));
	
	new->a = a;
	new->pNext = NULL;
	
	if(NULL == pHead || NULL == pEnd)
	{
		pHead = new;
		pEnd = new;
	}
	else
	{
		new->pNext = pHead;
		pHead = new;
	}
}
  • 这样就完成了头插法链表节点的创建。
  • 头插法的好处是，每次插入新节点，都在原有节点的前面，因此在读取时，会自动将所有输入的数据倒置，非常适合逆序输出。

节点删除

  • 有时候，我们不再需要某个节点时，可以将其删除掉，这样在我们再次遍历时，就不会再次检索到这个节点。
  • 注意点：首先要使用free函数来进行操作，同时要注意在删去原有节点之前，一定要做好前后两节点的链接，代码如下：
void delete(int a)
{
	NODE* p = pHead;
	while(p != NULL)
	{
		if(a == p->pNext->a)
		{
			p->pNext = p->pNext->pNext;
			free(p);
			break();
		}
		p = p->pNext;
	}
}
  • 这样删除后，数据a所在的结构体的那一块空间就被释放了，可以通过再次打印a的值来验证。进行打印后，我们发现a的值是个随机数，说明空间确实被释放了。
  • 学会了节点的删除后，如果我们又想在删除的部分加上一个新的节点，也是同样的道理，这是链表增的操作，不再赘述。

双向链表

  • 双向链表顾名思义，每个节点有三部分组成：
第一部分：指向上一个节点的结构体指针
第二部分：数据部分
第三部分：指向下一个节点的结构体指针
  • 双向链表的好处是即可以从前向后遍历、也可以从后向前遍历，适用于一组数据同时进行正向、反向打印等情况。
  • 每个节点如下所示：
typedef struct node
{
	struct node* pPrior;
	int a;
	struct node* pNext;
}NODE;
  • 在写创建新节点的函数时，要注意也要先将pPrior赋值为0。在进行节点之间的链接时，应该是以下格式（尾插法）：
pEnd->pNext = p;
p->pPrior = pEnd;
pEnd = p;
  • 通过这样的赋值，实现了新节点p与上个节点的双向链接。

双向链表删除节点

  • 双向链表的由于多了一个结构体指针pPrior，所以在删除时相较于单向链表更加简单。
viod delete(int a)
{
	NODE* p = pHead;
	while(p != NULL)
	{
		if(a == p->a)
		{
			p->pNext->pPrior = p->pPrior;
			p->pPrior->pNext = p->pNext;
			free(p);
		}
		p = p->pNext;
	}
}
  • 注意在进行删除前，一定要进行该节点前后的节点的链接，否则会造成数据丢失。
  • 使用free函数进行空间释放时，要注意释放的是指针指向的那块空间，和指针名、指针的类型以及存储的内存区域无关。

循环链表

  • 循环链表和普通链表的区别在它的首尾是相连的，也就是说pEnd->pNext == pHead。
  • 这样的好处是如果我们限制节点的个数，然后让一大组数据一个一个地赋给每个节点，不断地循环、覆盖，就能得到一个很特殊的结果：举个例子，如果今天是星期五，问：再过2020天之后是星期几。这样的问题就可以使用循环链表来解决。

静态链表

  • 之前的各种链表都是使用指针来实现的，链表中节点空间的分配和释放都是使用了系统提供的标准函数动态实现的，也被叫做动态链表。但是有一些语言没有提供指针这种数据类型，如果仍需要使用链表来作为存储结构，我们可以使用数组来模拟链表，也就是静态链表。
  • 其定义如下：
typedef struct SNode
{
	int data;
	int next;
}StaticList[11];
StaticList L;
  • 这里的L就是定义的结构体数组。其中next经常被称作游标cursor来模拟指针。
  • next的含义是下一个节点的下标，也就是说L[L[0].next] == L[1].data，要注意的是物理上相邻的元素逻辑上并不一定相邻。