阅读量:0
文章目录
前言
链表是数据结构中常用的结构，它可以在任意内存上申请适合的空间，极大的提高了内存的利用率，有效的解决了内存浪费的问题，那么就让我们了了解一下单链表吧。
一、链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
结构图示：
注意：
1.从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续；
2.现实中的结点一般都是从堆上申请的；
3.从堆上申请的空间，是按照一定的策略来分配的，两次分配的空间可能连续也可能不连续，所以需要使用指针去连接；
二、无头单向非循环链表
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
链表的实现
1.结构体声明
typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode; 2.单链表打印
空链表也可以打印所以不需要在开头断言
void SLTPrint(SLTNode* phead) { //不可以断言 SLTNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } 3.尾插
空链表也可以尾插，此处不用断言；
单链表的尾插比较麻烦，需要先找尾，然后插入数据。
void SLTPushBack(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySLTNode(x); if (*pphead == NULL) { *pphead = newnode; } else { //找尾 SLTNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } } 4.头插
链表的头插非常方便，可以直接在开头进行插入；
需要注意的是要将头指针的位置传出去，所以需要使用二级指针传参，或者返回指针。
void SLTPushFront(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySLTNode(x); newnode->next = *pphead; *pphead = newnode; } 5.尾删
空链表不可删除，所以需要断言；
只有一个结点时需要单独处理，将空间释放；
多个结点时再进行删除。
void SLTPopBack(SLTNode** pphead) { assert(pphead); assert(*pphead);//空链表不能删除，但可以插入，要注意 //1.只有一个结点 //2.多个结点 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { //SLTNode* prev = NULL; SLTNode* tail = *pphead; //找尾 while (tail->next->next != NULL)//找倒数第二个 { //prev = tail; tail = tail->next; } free(tail->next); tail->next = NULL; //prev->next = NULL; } } 6.头删
头删也需要进行断言，防止链表为空；
但是头删不需要找尾，也不需要单独处理单个结点的情况。
void SLTPopFront(SLTNode** pphead) { assert(pphead); assert(*pphead); SLTNode* first = *pphead; *pphead = first->next; free(first); first = NULL; } 7.单链表查找
从头开始，依次进行查找，并返回地址。
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { SLTNode* cur = phead; while (cur != NULL) { if (cur->data == x) { return cur; } //遍历链表 cur = cur->next; } return NULL; } 8.插入（在pos之前插入）
插入前需要申请新结点
SLTNode* BuySLTNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fali"); return NULL; } newnode->data = x; newnode->next = NULL; return newnode; } 在链表结点之前插入不是很方便，这是因为之前的结点没有记录，所以需要记录好前一个结点。
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { //断言 pos 不能为空 assert(pos); if (pos == *pphead) { SLTPushFront(&pos, x); } else { SLTNode* prev = *pphead; //寻找pos的前一个结点 while (prev->next != pos) { prev = prev->next; } SLTNode* newnode = BuySLTNode(x); prev->next = newnode; newnode->next = pos; } } 9.删除（在pos之前删除）
删除时需要判断链表是否为空；
对于头删的情况需要特殊处理；
删除链表之后要及时释放内存。
void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead); assert(pos); assert(*pphead); if (*pphead == pos) { SLTPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); //这里直接置空pos没用 //也可以传入二级指针ppos直接在这里释放 } } 10.插入（在pos之后插入）
结点之后插入比较方便
void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = BuySLTNode(x); newnode->next = pos->next; pos->next = newnode; } 11.删除（在pos之后删除）
void SLTEraseAfter(SLTNode* pos) { assert(pos); assert(pos->next); //为了不丢失pos->next，记录它 SLTNode* del = pos->next; pos->next = del->next; free(del); del = NULL; } 12.销毁
链表使用结束后需要及时销毁，防止内存泄漏。
void SLTDestroy(SLTNode* phead) { SLTNode* cur = phead; while (cur) { SLTNode* tmp = cur->next; free(cur); cur = tmp; } //phead 置空是没用的，可以在使用时置空 } 总结
单链表的结构有很大的弊端，比如：不好使用前面的结点。所以在实际中中有很大的不便，它也不作为主要使用的链表类型，但是它对于“头”的操作很方便，因此也作为很多结构的子结构。
请各位多多支持，不要忘记三连哦！
