单链表专题(冲冲冲)

禁默

发布于 2025-12-19 14:21:05

1500

本节内容小编将讲解单链表的内容，谢谢大家捧场！

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;
}

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