[数据结构]单链表详解

目录

一、顺序表的问题及思考

二、单链表的实现

1.结构体内容的定义（typedef struct SListNode）

2.链表的打印（void SLTPrint(SLTNode* phead)）

​编辑3.链表的尾插（void SLPushBack(SLTNode* phead, SLTDataType x)）

3.1尾插错误示范：

3.2注意事项：

3.3修改后的尾插函数：

3.4打印结果：

 3.5知识梳理：

4.链表的头插：（void SListPushFront(SLTNode** pphead, SLTDataType x)）

5.链表的尾删：（void SListPushFront(SLTNode** pphead, SLTDataType x)）

6.链表的头删：（void SListPopFront(SLTNode** pphead)）

7.链表的查找：（SLTNode* SListFind(SLTNode* phead, SLTDataType x)）

8.在指定位置（pos）之前插入:（void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)）

9.在指定位置（pos）位置删除:（void SLTErase(SLTNode** pphead, SLTNode* pos)）

10.在指定位置（pos）后面插入：（void SLTInsertAfter(SLTNode* pos, SLTDataType x)）

11.链表的销毁：（void SLTDestroy(SLTNode* phead)）

三、单链表功能汇总

SList.h：

SList.c

test.c

---

一、顺序表的问题及思考 问题： 1. 中间 / 头部的插入删除，时间复杂度为 O(N) 2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。 3. 增容一般是呈 2 倍的增长，势必会有一定的空间浪费。例如当前容量为 100 ，满了以后增容到 200 ，我们再继续插入了 5 个数据，后面没有数据插入了，那么就浪费了 95 个数据空间。 思考：如何解决以上问题呢？下面给出了链表的结构来看看。 上一个节点存着下一个结点的地址，每一个结点都是一个结构体 二、单链表的实现 1.结构体内容的定义（typedef struct SListNode） #pragma once #include <stdlib.h> #include<stdio.h> typedef int SLTDataType; typedef struct SListNode { SLDataType data; struct SListNode* Next;//这里并不是结构体里面有个结构体，而是结构体里面有个指针，它的类型是结构体类型 //SListNode* Next; 这里还不能这样写，这里涉及到编译器的查找规则：如果一个函数或者一个类型需要使用，那么编译器会向上查找而不会向下 }SListNode; 2.链表的打印（void SLTPrint(SLTNode* phead)） void SLTPrint(SLTNode* phead) { //不需要assert断言，因为空的链表可以打印，只是没有数据而已 SLTNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->Next;//Next是下一个节点的地址 } printf("NULL\n"); } 3.链表的尾插（void SLPushBack(SLTNode* phead, SLTDataType x)）

尾插本质：原尾结点中要存储新的尾结点的地址

3.1尾插错误示范： void SLPushBack(SLTNode* phead, SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail"); } newnode->data = x; newnode->Next = NULL; //找尾 SLTNode* tail = phead; while (tail->Next != NULL) { tail = tail->Next; } tail->Next = newnode;//tail= newnode;这样写是错的，要想把两个链表链接起来，必须要让一个链表的最后一个数的下一个地址存放着下一个数的地址，tail目前存的是最后一个元素的地址而不是最后一个元素的下一个元素的地址 }

3.2注意事项：

test.c文件：

#define _CRT_SECURE_NO_WARNINGS 1 #include "SList.h" void TestSList1() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPrint(plist); } int main() { TestSList1(); return 0; }

这里phead的改变不会引起plist的改变，现在要改变的是SLTNode*，传进去SLTNode*根本不起作用，应该传SLTNode**

3.3修改后的尾插函数： void SLTPushBack(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail"); } newnode->data = x; newnode->Next = NULL; if (*pphead == NULL) { *pphead = newnode; }。 else { //找尾 SLTNode* tail = *pphead; while (tail->Next != NULL) { tail = tail->Next; } tail->Next = newnode;//tail= newnode;这样写是错的，要想把两个链表链接起来，必须要让一个链表的最后一个数的下一个地址存放着下一个数的地址， //tail目前存的是最后一个元素的地址而不是最后一个元素的下一个元素的地址 } } 3.4打印结果：

改变传过去的指针，那么就要传指针的地址，不改变就可以不传，所以print函数就没有传

 3.5知识梳理： 空链表可以打印，不用断言 空链表可以尾插，不用assert(*pphead),但是需要assert(pphead) 空链表可以头插，不用assert(*pphead),但是需要assert(pphead)把 空链表不能尾删，assert(pphead)和assert(*pphead)都需要，且pphead断言在*pphead之前 4.链表的头插：（void SListPushFront(SLTNode** pphead, SLTDataType x)） void SListPushFront(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySLTNode(x); newnode->Next = *pphead; //原本*pphead是第一个节点的地址，现在把原来第一个节点的地址放在新插入的节点的尾巴中，让新的第一个节点存放原来第一个节点的地址 *pphead = newnode;// 把头指针的地址改成新插入的指针的地址 //这种写法可以针对空链表，因为空链表的*pphead的next是NULL，现在相当于把newnode->Next赋值为NULL，并把newnode改为头指针，完全可行 } 5.链表的尾删：（void SListPushFront(SLTNode** pphead, SLTDataType x)） void SListPushFront(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySLTNode(x); newnode->Next = *pphead; //原本*pphead是第一个节点的地址，现在把原来第一个节点的地址放在新插入的节点的尾巴中，让新的第一个节点存放原来第一个节点的地址 *pphead = newnode;// 把头指针的地址改成新插入的指针的地址 //这种写法可以针对空链表，因为空链表的*pphead的next是NULL，现在相当于把newnode->Next赋值为NULL，并把newnode改为头指针，完全可行 } // 单链表的尾删 void SListPopBack(SLTNode** pphead) { assert(pphead); assert(*pphead != NULL); //1.只有一个结点 //2.有多个结点 if ((*pphead)->Next == NULL) { free(*pphead); } //找尾 SLTNode* prev = NULL; SLTNode* tail = *pphead; while (tail->Next != NULL) { prev = tail;//tail在每次往下走之前先把值留给prev tail = tail->Next; } free(tail); tail = NULL; prev->Next = NULL; } 为什么需要 prev？            单链表的单向性：单链表的每个节点只有 Next 指针，指向下一个节点，而没有指向前一个节点的指针。因此，当你找到尾节点（tail）时，无法直接知道它的前一个节点是谁。 删除尾节点的操作：            删除尾节点时，需要将尾节点的前一个节点（prev）的 Next 指针置为 NULL，以表示它是新的尾节点。如果不记录 prev，就无法修改前一个节点的 Next 指针，链表会处于一个不正确的状态。 释放尾节点的内存：            在释放尾节点的内存之前，必须确保前一个节点的 Next 指针已经被正确修改，否则会导致链表断裂或内存泄漏。  tail 和 prev 的关系：            tail 是用来遍历链表的指针，最终会指向尾节点（即要删除的节点）。            prev 是用来记录 tail 的前一个节点的指针。            tail = NULL 的作用：            tail = NULL 只是将局部变量 tail 置为 NULL，并不会影响链表的结构。            链表的结构是由节点的 Next 指针决定的，而不是由局部变量 tail 决定的            还有一种写法： SLTNode* tail = *pphead; while (tail->Next->Next != NULL) { tail = tail->Next; } free(tail->Next); tail->Next = NULL; 6.链表的头删：（void SListPopFront(SLTNode** pphead)） void SListPopFront(SLTNode** pphead) { assert(*pphead != NULL); SLTNode* first = *pphead; *pphead = first->Next; free(first); first = NULL; } 7.链表的查找：（SLTNode* SListFind(SLTNode* phead, SLTDataType x)） SLTNode* SListFind(SLTNode* phead, SLTDataType x) { SLTNode* cur = phead; while (cur != NULL) { if (cur->data == x) { return cur; } else { cur = cur->Next; } } return NULL; } 8.在指定位置（pos）之前插入:（void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)）

这个函数一般配合SListFind函数一起使用

pos是第几个位置，如果pos=3，那么就是在2和3之间插入，但是：单链表不适合在前面插入，因为有了3的位置却找不到2的位置，需要从头开始遍历

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { //plist有可能为空，但是pphead不能为空。plist的值有可能为空，但是pphead存放的是pphead的地址，不能为空（phead有可能为空->代码空链表） assert(pphead != NULL); assert(pos); if (pos == *pphead)//如果pos为头指针，那么类似于头插 { SListPushFront(pphead, x); } else { //找到pos的前一个位置 SLTNode* prev = *pphead; 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)） void SLTErase(SLTNode** pphead, SLTNode* pos)//删除pos的位置必须知道pos的前一个的位置 { assert(pphead); assert(pos); assert(*pphead); if (pos == *pphead) { SListPopFront(pos); } else { //找到pos的前一个位置 SLTNode* prev = *pphead; while (prev->Next != pos) { prev = prev->Next; } prev->Next = pos->Next; free(pos); //pos = NULL;这句话其实没用因为形参的改变不影响实参 } } 10.在指定位置（pos）后面插入：（void SLTInsertAfter(SLTNode* pos, SLTDataType x)） void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = BuySLTNode(x); newnode->Next = pos->Next; pos->Next = newnode; } //在pos位置后面删除 void SLTEraseAfter(SLTNode* pos) { assert(pos); assert(pos->Next); SLTNode* del = pos->Next;//先标记好要删除的节点，以免后面这块结点丢失 pos->Next = pos->Next->Next; free(del); del = NULL; } 11.链表的销毁：（void SLTDestroy(SLTNode* phead)）

注意用完这个函数后得把实参置空，因为这个函数里面phead=NULL这句话是没意义的，因为形参改变不会改变实参。或者用二级指针。

void SLTDestroy(SLTNode* phead) { SLTNode* cur = phead; while (cur) { SLTNode* tmp = cur->Next; free(cur); cur = tmp; } }

 //删除的经典错误：         // 1.         // free(cur);         // cur=cur->Next;  野指针，cur的使用权被释放了，这行代码是非法操作         // 2.         // SLTNode *tmp=cur;         // free(cur);         // cur=tmp->Next;  和上面一样，tmp和cur指向的是同一块内存空间，如果释放就一起释放了         //你退房了，把房卡给别人，别人也不能开酒店的房门，一样的道理         //最好的方法不是保存cur而是保存cur的next

三、单链表功能汇总 SList.h： #pragma once #include <stdlib.h> #include <stdio.h> #include <assert.h> #include <errno.h> typedef int SLTDataType; typedef struct SListNode { SLTDataType data; // 数据域 struct SListNode* Next; // 这里并不是结构体里面有个结构体，而是结构体里面有个指针，它的类型是结构体类型 // SListNode* Next; 这里还不能这样写，这里涉及到编译器的查找规则：如果一个函数或者一个类型需要使用，那么编译器会向上查找而不会向下 } SLTNode; // 打印链表 void SLTPrint(SLTNode* phead); // 尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x); // 单链表的头插 void SListPushFront(SLTNode** pphead, SLTDataType x); // 单链表的尾删 void SListPopBack(SLTNode** pphead); // 单链表头删 void SListPopFront(SLTNode** pphead); // 单链表查找 SLTNode* SListFind(SLTNode* phead, SLTDataType x); //在pos之前插入 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); //在pos位置删除 void SLTErase(SLTNode** pphead, SLTNode* pos); //在pos后面插入 void SLTInsertAfter(SLTNode*pos, SLTDataType x); //在pos位置后面删除 void SLTEraseAfter(SLTNode* pos); //链表的删除 void SLTDestroy(SLTNode* phead); SList.c #include "SList.h" //创建插入元素的封装节点 函数 SLTNode* BuySLTNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail"); } newnode->data = x; newnode->Next = NULL; return newnode; } //打印 void SLTPrint(SLTNode* phead) { //不需要assert断言，因为空的链表可以打印，只是没有数据而已 SLTNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->Next;//Next是下一个节点的地址 } printf("NULL\n"); } // 尾插 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;//tail= newnode;这样写是错的，要想把两个链表链接起来，必须要让一个链表的最后一个数的下一个地址存放着下一个数的地址， //tail目前存的是最后一个元素的地址而不是最后一个元素的下一个元素的地址 } } // 单链表的头插 void SListPushFront(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySLTNode(x); newnode->Next = *pphead; //原本*pphead是第一个节点的地址，现在把原来第一个节点的地址放在新插入的节点的尾巴中，让新的第一个节点存放原来第一个节点的地址 *pphead = newnode;// 把头指针的地址改成新插入的指针的地址 //这种写法可以针对空链表，因为空链表的*pphead的next是NULL，现在相当于把newnode->Next赋值为NULL，并把newnode改为头指针，完全可行 } // 单链表的尾删 void SListPopBack(SLTNode** pphead) { assert(pphead); assert(*pphead != NULL); //1.只有一个结点 //2.有多个结点 if ((*pphead)->Next == NULL) { free(*pphead); } //找尾 SLTNode* prev = NULL; SLTNode* tail = *pphead; while (tail->Next != NULL) { prev = tail;//tail在每次往下走之前先把值留给prev tail = tail->Next; } free(tail); tail = NULL; prev->Next = NULL; } // 单链表头删 void SListPopFront(SLTNode** pphead) { assert(*pphead != NULL); SLTNode* first = *pphead; *pphead = first->Next; free(first); first = NULL; } // 单链表查找 SLTNode* SListFind(SLTNode* phead, SLTDataType x) { SLTNode* cur = phead; while (cur != NULL) { if (cur->data == x) { return cur; } else { cur = cur->Next; } } return NULL; } //在pos之前插入,配合SListFind函数一起使用 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { //plist有可能为空，但是pphead不能为空。plist的值有可能为空，但是pphead存放的是pphead的地址，不能为空（phead有可能为空->代码空链表） assert(pphead != NULL); assert(pos); if (pos == *pphead)//如果pos为头指针，那么类似于头插 { SListPushFront(pphead, x); } else { //找到pos的前一个位置 SLTNode* prev = *pphead; while (prev->Next != pos) { prev = prev->Next; } SLTNode* newnode = BuySLTNode(x); prev->Next = newnode; newnode->Next = pos; } } //在pos位置删除 void SLTErase(SLTNode** pphead, SLTNode* pos)//删除pos的位置必须知道pos的前一个的位置 { assert(pphead); assert(pos); assert(*pphead); if (pos == *pphead) { SListPopFront(pos); } else { //找到pos的前一个位置 SLTNode* prev = *pphead; while (prev->Next != pos) { prev = prev->Next; } prev->Next = pos->Next; free(pos); //pos = NULL;这句话其实没用因为形参的改变不影响实参 } } //在pos后面插入 void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = BuySLTNode(x); newnode->Next = pos->Next; pos->Next = newnode; } //在pos位置后面删除 void SLTEraseAfter(SLTNode* pos) { assert(pos); assert(pos->Next); SLTNode* del = pos->Next;//先标记好要删除的节点，以免后面这块结点丢失 pos->Next = pos->Next->Next; free(del); del = NULL; } //链表的删除 void SLTDestroy(SLTNode* phead) { SLTNode* cur = phead; while (cur) { SLTNode* tmp = cur->Next; free(cur); cur = tmp; } } test.c #define _CRT_SECURE_NO_WARNINGS 1 #include "SList.h" void TestSList1() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPrint(plist); SListPopFront(&plist); SLTPrint(plist); SLTNode* ret=SListFind(plist, 2); SLTPrint(plist); SLTInsert(&plist, ret, 20); SLTPrint(plist); } int main() { TestSList1(); return 0; }