目录

1. 链表的概念及结构

2. 链表的分类

3. 单链表的实现

3.1 SList.h头文件

3.2 SList.c源文件

3.3 Test_SList.c测试文件

---

关于线性表，已介绍顺序表，详见下文：

【数据结构】_顺序表-CSDN博客

本文介绍链表；

基于顺序表的特点，思考改善方案：

按需申请释放空间，不再将数据存储于连续的一整块空间中，而是需要一个数据开辟一个小空间。为了方便访问数据，首先创建一个头指针（头结点）指向存放第一个数据的内存位置处，而在该位置处，除了存储该数据本身，再分配一块空间用于存放下一个数据的地址，直至某位置存放的下一个位置的指针为空则数据截止。

同时，这种存储方式也有效地提高了插入删除数据时的效率，无需再大量挪动数据。

这种数据结构就称为链表。

1. 链表的概念及结构

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

链表在逻辑上是连续的，在物理上不是连续的；

2. 链表的分类

对于链表，有单向和双向、带头与不带头、循环与不循环的分类，不同的组合如下;

各种类型的链表示意图如下：

单向和双向：（区别标准：能从一个/两个方向遍历）

带头和不带头：（是否在第一个有效结点前增加一个头结点）

循环和非循环：（尾结点的next为NULL/指向第一个结点）

最常用的链表结构是：无头单向非循环链表 和 带头双向循环链表：

注：头结点并不是第一个有效结点，而是在第一个有效结点前再创建一个不存储有效数据的结点；

3. 单链表的实现

3.1 SList.h头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

// 链表结点
typedef int SLTDataType;
typedef struct SListNode {
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead);
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
SLTNode* SLTCreatNode(SLTDataType x);
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
// 在指定位置前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 在指定位置后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
// 删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);
// 删除pos后的结点
void SLTEraseAfter(SLTNode* pos);
// 销毁
void SLTDestory(SLTNode** pphead);

3.2 SList.c源文件

#include"SList.h"
void SLTPrint(SLTNode* phead) {
	SLTNode* pcur = phead;
	while (pcur) {
		printf("%d-> ", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}
SLTNode* SLTCreatNode(SLTDataType x) {
	SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newNode == NULL) {
		perror("malloc fail\n");
		exit(1);
	}
	newNode->data = x;
	newNode->next = NULL;
	return newNode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x) {
	assert(pphead);
	SLTNode* newNode = SLTCreatNode(x);
	// 空链表
	if (*pphead == NULL) {
		*pphead = newNode;
	}
	else {
		// 非空链表
		SLTNode* curNode = *pphead;
		while (curNode->next) {
			curNode = curNode->next;
		}
		curNode->next = newNode;
	}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
	assert(pphead);
	SLTNode* newNode = SLTCreatNode(x);
	newNode->next = *pphead;
	// 令新结点为链表的头结点
	*pphead = newNode;
}
void SLTPopBack(SLTNode** pphead) {
	assert(pphead && *pphead);
	// 链表只有一个结点
	if ((*pphead)->next == NULL) {
		free(*pphead);
		*pphead = NULL;
	}
	// 链表有多个结点
	else {
		SLTNode* tailPrevNode = *pphead;
		SLTNode* tailNode = *pphead;
		while (tailNode->next) {
			tailPrevNode = tailNode;
			tailNode = tailNode->next;
		}
		free(tailNode);
		tailNode = NULL;
		tailPrevNode->next = NULL;
	}
}
void SLTPopFront(SLTNode** pphead) {
	assert(pphead && *pphead);
	SLTNode* secNode = (*pphead)->next;
	free(*pphead);
	*pphead = secNode;
}
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {
	SLTNode* curNode = phead;
	while (curNode) {
		if (curNode->data == x) {
			return curNode;
		}
		curNode = curNode->next;
	}
	return NULL;
}
// 在指定位置前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
	assert(pphead && *pphead && pos);
	SLTNode* newNode = SLTCreatNode(x);
	if (pos == *pphead) {
		// 调用头插方法
		SLTPushFront(pphead, x);
	}
	else {
		SLTNode* posPrevNode = *pphead;
		while (posPrevNode->next != pos) {
			posPrevNode = posPrevNode->next;
		}
		posPrevNode->next = newNode;
		newNode->next = pos;
	}
}
// 在指定位置后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
	assert(pos);
	SLTNode* newNode = SLTCreatNode(x);
	SLTNode* posAfterNode = pos->next;
	pos->next = newNode;
	newNode->next = posAfterNode;
}
// 删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos) {
	assert(pphead && *pphead && pos);
	if (*pphead == pos) {
		// 调用头删方法
		SLTPopFront(pphead);
	}
	else {
		SLTNode* posPrevNode = *pphead;
		while (posPrevNode->next != pos) {
			posPrevNode = posPrevNode->next;
		}
		posPrevNode->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
// 删除pos后的结点
void SLTEraseAfter(SLTNode* pos) {
	assert(pos && pos->next);
	SLTNode* posAfterNode = pos->next;
	pos->next = posAfterNode->next;
	free(posAfterNode);
	posAfterNode = NULL;
}
// 销毁
void SLTDestory(SLTNode** pphead) {
	assert(pphead && *pphead);
	SLTNode* curNode = *pphead;
	while (curNode) {
		SLTNode* curNextNode= curNode->next;
		free(curNode);
		curNode = NULL;
	}
	*pphead = NULL;
}

3.3 Test_SList.c测试文件

#include"SList.h"
void Test11() {
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	SLTDestory(&plist);
	SLTPrint(plist);
}
void Test10() {
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	SLTNode* aimNode1 = SLTFind(plist, 3);
	SLTEraseAfter(aimNode1);
	SLTPrint(plist);
	SLTNode* aimNode2 = SLTFind(plist, 1);
	SLTEraseAfter(aimNode2);
	SLTPrint(plist);
}
void Test9() {
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	SLTNode* aimNode1 = SLTFind(plist, 3);
	SLTErase(&plist, aimNode1);
	SLTPrint(plist);
	SLTNode* aimNode2 = SLTFind(plist, 1);
	SLTErase(&plist, aimNode2);
	SLTPrint(plist);
}
void Test8() {
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	SLTNode* aimNode1 = SLTFind(plist, 3);
	SLTInsertAfter(aimNode1, 85);
	SLTPrint(plist);
	SLTNode* aimNode2 = SLTFind(plist, 1);
	SLTInsertAfter(aimNode2, 97);
	SLTPrint(plist);
}
void Test7(){
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	SLTNode* aimNode1 = SLTFind(plist, 3);
	SLTInsert(&plist, aimNode1, 85);
	SLTPrint(plist);
	SLTNode* aimNode2 = SLTFind(plist, 1);
	SLTInsert(&plist, aimNode2, 97);
	SLTPrint(plist);
}
void Test6() {
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	// SLTNode* aimNode = SLTFind(plist, 3);
	SLTNode* aimNode = SLTFind(plist, 6);
	if (aimNode == NULL)
		printf("Find nothing\n");
	else
		printf("Find successfully\n");
}
void Test5() {
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
}
void Test4() {
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
}
void Test3() {
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);
}
void Test2() {
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
}

void Test1() {
	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;
	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 2;
	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 3;
	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 4;

	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;

	SLTNode* plist = node1;
	SLTPrint(plist);
}
int main() {
	//Test1();
	//Test2();
	//Test3();
	//Test4();
	//Test5();
	//Test6();
	//Test7();
	//Test8();
	//Test9();
	//Test10();
	Test11();
	return 0;
}