单链表专题(冲冲冲)-天翼云

1.链表的概念和结构

1.1概念

链表是一种物理存储结构上非 连续、非顺序的存储结构，数据元素的 逻辑顺序是通过链表中的 指针链接次序实现的。

链表的结构可以类似于火车车厢。

淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上，不会影响其他车厢，每节车厢都是独立存在的，且每节车厢都有车门。

想象一下这样的场景，假设每节车厢的车门都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带一把钥匙的情况下如何从车头走到车尾？

最简单的做法：每节车厢里都放一把下一节车厢的钥匙。

在链表里，每节“车厢”是什么样的呢？

在这里，与前面的顺序表相比，这里的每节车厢都是后续申请的独立空间，我们称之为 节（结）点。

节点的组成主要有两个部分：当前节点要 保存的数据和保存 下一个节点的地址（指针变量）。

图中指针变量 plist保存的是第一个节点的地址，我们称plist此时“指向”第一个节点，如果我们希望plist“指向”第二个节点时，只需要修改plist保存的内容为0x0012FFA0。

为什么还需要指针变量来保存下⼀个节点的位置？

链表中每个节点都是独立申请的（即需要插入数据时才去申请一块节点的空间），我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点。

这里的节点是我们自定义的类型，所以可以使用结构体创建。

假设节点保存的数据为整型。

struct ListNode{
int data;//节点数据
struct ListNode *next;//用来保存下一个节点的地址
};

当我们想要保存一个整型数据时，实际是向操作系统申请了一块内存，这个内存不仅要保存整型数据，也需要保存下一个节点的地址（当下⼀个节点为空时保存的地址为空）。

当我们想要从第一个节点走到最后⼀个节点时，只需要在前一个节点拿上下一个节点的地址（下一个节点的钥匙）就可以了。

void SLNodePrint(ListNode*pphead){
  ListNode *pcur=pphead;
  while(pcur){
  printf("%d",pcur->data);
  pcur=pcur->next;
}
printf("\n);
}

单链表专题(冲冲冲)

1.2思考

当我们想保存的数据类型为字符型、浮点型或者其他自定义的类型时，该如何修改？

在顺序表当中提到typedef定义数据类型，这里我们可以同样采取这种方式。

typedef int datapate; // 改变数据类型时将int改成需要的形式即可！

1.3补充说明

1、链式结构在逻辑上是连续的，在物理结构上不一定连续。

2、节点一般是从堆上申请的。

3、从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续。

2.单链表的实现

同样我们采用类似项目的格式来实现单链表。

2.1头文件的建立（包含节点建立以及所需要创建的函数种类）

这里我们将该头文件命名为“Slist.h”

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//定义节点的结构--数据+指向下一个节点的指针
typedef  int SLdatatype;//定义数据类型，也可方便以后修改数据类型
typedef struct  SListNode {
	SLdatatype  data;//节点数据
	struct SListNode* next;//指针保存下一个节点的地址
}Node;
void SLTprint(Node* phead);

//尾插+头插
void PushBack(Node** pphead, SLdatatype x);
void PushFront(Node** pphead, SLdatatype x);
//尾删+头删
void PopBack(Node** pphead);
void PopFront(Node** pphead);
//查找
Node* SLTFind(Node* phead, SLdatatype x);
void SLTInsert(Node** pphead, Node* pos, SLdatatype x);
//删除pos节点
void SLTErase(Node** pphead, Node* pos);
//在指定位置之后插⼊数据
void SLTInsertAfter(Node* pos, SLdatatype x);
//删除pos之后的节点
void SLTEraseAfter(Node* pos);
//销毁链表
void SListDesTroy(Node** pphead);

注意

这里同样要注意传址和传值的区别，与顺序表类似。

2.2 函数功能实现

2.2.1节点值的打印

void SLTprint(Node* phead) {
	Node* pcur = phead;
	while (pcur)//pcur!=NULL
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

2.2.2新节点的创建

Node* SLTBuyNode(SLdatatype x) {
	Node* newnode = (Node*)malloc(sizeof(Node));
	if (newnode == NULL) {
		perror("malloc fail !");
		exit(1);//原理上正常返回0.异常返回非0
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

2.2.3尾插和头插的实现

//尾插
void PushBack(Node** pphead, SLdatatype x) {
	assert(pphead);//不能直接传空指针
	Node* newnode = SLTBuyNode(x);
	if (*pphead == NULL) {
		*pphead = newnode;
	}
	else
	{
		//找尾节点
		Node* ptail = *pphead;
		while (ptail->next) {
			ptail = ptail->next;
		}
		//ptail指向的就是尾节点
		ptail->next = newnode;
	}

}
//头插
void PushFront(Node **pphead, SLdatatype x) {
	assert(pphead);
	Node* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

2.2.4头删和尾删的实现

void PopFront(Node** pphead)
{
	assert(pphead && *pphead);
	Node* pcur = *pphead;//Node*next=(*pphead)->next;
	(*pphead) = pcur->next;//free(*pphead);
	free(pcur);            //(*pphead)=next;
	pcur = NULL;
	
}
//尾删
 void PopBack(Node** pphead) {
	assert(pphead && *pphead);
	//链表只有一个节点时
	if ((*pphead)->next == NULL) {//->优先级大于*
		free(*pphead);
		*pphead = NULL;
	}
	//链表有多个节点
	else
	{
		Node* ptail = *pphead;
		Node* prev = *pphead;
		//找尾节点
		while (ptail->next) {
			prev = ptail;
			ptail = ptail->next;
		}
		free(ptail);
		ptail = NULL;
		prev->next = NULL;
	}
}

2.2.5节点的查找

Node* SLTFind(Node* phead, SLdatatype x) {
 Node* pcur = phead;
 while (pcur)//pcur!=NULL
 {
	 if (pcur->data == x) {
		 return pcur;
	 }
	 pcur = pcur->next;
 }
 //pcur==NULL;
 return NULL;
}

2.2.6指定位置前后节点的插入

void SLTInsert(Node** pphead, Node* pos, SLdatatype x) {
 assert(pphead && *pphead);
 assert(pos);
 Node* newnode = SLTBuyNode(x);
 //pos==*pphead.说明是头插
 if (pos == *pphead) {
	 PushFront(pphead, x);
 }
 else
 {
	 Node* prev = *pphead;
	 while (prev->next != pos) {
		 prev = prev->next;
	 }
	 newnode->next = pos;
	 prev->next = newnode;
 }
}
void SLTInsertAfter(Node* pos, SLdatatype x) {
 assert(pos);
 Node* newnode = SLTBuyNode(x);
 newnode->next = pos->next;
 pos->next = newnode;
}

2.2.7指定节点的删除

void SLTErase(Node** pphead, Node* pos) {
 assert(pphead && *pphead);
 assert(pos);
 //pos是头结点
 if (pos == *pphead) {
	 PopFront(pphead);
 }
 else
 {
	 Node* prev = *pphead;
	 while (prev->next != pos) {
		 prev = prev->next;
	 }
	 prev->next = pos->next;
	 free(pos);
	 pos = NULL;
 }
}
//删除pos之后的节点
void SLTEraseAfter(Node* pos) {
 assert(pos && pos->next);
 Node* del = pos->next;
 pos->next = del->next;
 free(del);
 del = NULL;
}

2.2.8链表的销毁

//链表的销毁(销毁一个一个的节点)
void SListDesTroy(Node** pphead) {
 assert(pphead && *pphead);
 Node* pcur = *pphead;
 while (pcur) {
	 Node* next = pcur->next;
	 free(pcur);
	 pcur = next;
 }
 *pphead = NULL;
}

2.3代码测试

//#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"
void test1() {//实验链表是否建立成功
	Node*node1 = (Node*)malloc(sizeof(Node));
	node1->data = 1;
	
	Node* node2 = (Node*)malloc(sizeof(Node));
	node2->data = 2;
	
	Node* node3 = (Node*)malloc(sizeof(Node));
	node3->data = 3;
	
	Node* node4 = (Node*)malloc(sizeof(Node));
	node4->data = 4;
	//j将四个节点连接起来
	
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;
	//定义一个头指针指向node1
	Node* head = node1;
	SLTprint(head);
}
void test2() {
	Node* plist = NULL;
	//形参若引起实参的改变需要传址
	PushBack(&plist, 1);//尾插
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	//PushBack(NULL, 4);--error
	SLTprint(plist);
	/*
	Node* ret = SLTFind(plist, 3);
	if (ret == NULL) {
		printf("not found!");
	}
	else
		printf("找到了!\n");
	Node* find = SLTFind(plist, 3);
	SLTInsert(&plist,find, 11);//指定位置插入
	SLTprint(plist);
	
	PushFront(&plist, 6);//头插
	PushFront(&plist, 8);
	PushFront(&plist, 9);
	SLTprint(plist);
	
	PopFront(&plist);//头删
	SLTprint(plist);
	//PopBack(&plist);
	//SLTprint(plist);
	PopBack(&plist);//尾删
	SLTprint(plist);
	PopFront(&plist);
	SLTprint(plist);
	PopFront(&plist);
	SLTprint(plist);
	
	//删除pos节点
	Node* find1 = SLTFind(plist, 11);
	SLTErase(&plist, find1);
	SLTprint(plist);
	//在指定位置之后插⼊数据
	SLTInsertAfter(find,12);
	SLTprint(plist);
	//删除pos之后的节点
	SLTEraseAfter(find);
	SLTprint(plist);
	*/
	PopFront(&plist);
	SLTprint(plist);
	//SListDesTroy(&plist);
	//SLTprint(plist);
}  
int main() {
	//test1();
	test2();
	return 0;
}

根据自身情况可将注释符号去掉测试相应函数功能。

注意

对于2.2和2.3的代码运用都要引用定义好的头文件“Slist.h”

3.链表的分类（简要介绍）

后续小编会详细讲解

链表的结构非常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构。

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构： 单链表和双向带头循环链表

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

活动

应用商城

合作伙伴

开发者

支持与服务

了解天翼云

单链表专题(冲冲冲)

单链表专题(冲冲冲)

1.链表的概念和结构

1.1概念

1.2思考

1.3补充说明

2.单链表的实现

2.1头文件的建立（包含节点建立以及所需要创建的函数种类）

2.2 函数功能实现

2.3代码测试

注意

对于2.2和2.3的代码运用都要引用定义好的头文件“Slist.h”

3.链表的分类（简要介绍）

相关文章

LeetCode：142.环形链表II

LeetCode：19.删除链表倒数第N个节点

LeetCode：203.移除链表元素

LeetCode：24. 两两交换链表中的节点

LeetCode：206.反转链表

C语言基础之——指针（上）

算法——滑动窗口

算法题 75. 颜色分类，76. 最小覆盖子串，77. 组合

算法题 152. 乘积最大子数组，153. 寻找旋转排序数组中的最小值，160. 相交链表

算法题 169. 多数元素，200. 岛屿数量，199. 二叉树的右视图

作者介绍

最新文章

LeetCode：142.环形链表II

LeetCode：19.删除链表倒数第N个节点

LeetCode：24. 两两交换链表中的节点

LeetCode：206.反转链表

指针扩展之——数组指针

【list】list库介绍 + 简化模拟实现

热门文章

简单指针实现两个数比较大小

python matplotlib的三层结构

leetcode-单链表-23

go 指针使用【2】

LeetCode 141. 环形链表

Golang：3.5、Golang 指针

热门标签

相关产品

弹性云主机

天翼云电脑（公众版）

对象存储

云硬盘

随机文章

特定类型的图与应用 - 离散数学系列（六）

LeetCode：24. 两两交换链表中的节点

第九节（结构、联合typedef）

剑指Offer(25)--复杂链表的复制

二叉树的链式结构

mongodb副本集搭建