链表之单链表

上一篇博客我们学习了线性表中的顺序表，这一篇博客让我们继续往下了解线性表的链表，链表分为好几种结构，活不多说，让我们开始学习吧！

---

目录

1.链表

2.链表的结构

3.单链表的实现

---

1.链表

1.概念：它是一种物理存储结构上非连续非顺序的存储结构，数据元素的逻辑顺序是通过链                表中的指针链接次序实现的。它在空间上，按需给空间，不要求物理空间的连续，                和顺序表不同，它头部和中间的数据的插入就不需要挪动数据。链表的实现是通过                指针的。

2.有些老铁可能不明白什么是物理结构，它就是在内存中实实在在的存储形式。

什么是不连续非顺序，我们画图来给大家解释一下：

在这些节点中间，我们可以插入新的节点，又是新的地址，所以说它不是按顺序走的。这些节点在内存中，可能这有一个节点，也可能那有一个节点，但它们彼此之间通过指针相连接，只要指针不断，就可以找到下一个节点。

3.链表只能一个一个诶个访问，只能从头找，因为一旦它找到下一个节点，它就不知道上一个节点的位置了（双向链表可以找到上一个，我们到了那个章节在继续学习）。这时，又显示出顺序表的好处了，因为它可以直接定位到要查找数据的位置，但是它会造成空间的浪费，所以说有好有坏，需要大家自己体会。

2.链表的结构

链表分为八种结构，在这里先给大家一个总体的框架，方便接下来的学习：

单链表，双链表，不带头链表，带头链表，循环链表，不循环链表，这六种链表构成了链表的八种结构，分别是：

1.单向不带头不循环链表

2.单向不带头循环链表

3.单向带头不循环链表

4.单向带头循环链表

5.双向不带头不循环链表

6.双向不带头循环链表

7.双向带头不循环链表

8.双向带头循环链表

我们今天在这里会实现第一种结构，单向不带头不循环链表，相信通过这个链表的实现，大家可以把2,3,4种结构都实现。

3.单链表的实现

现在我们来实现这个单链表，可以类比顺序表写，这一部分的代码都大差不差，具体要看怎么实现。

SList.h文件

#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int ALTDataType; //创建结构体，用来创建链表组成元素 typedef struct SListNode { ALTDataType data;//链表数据 struct SListNode* next;//链表指向下一个元素的指针，指向下一个节点的位置 }SLN; //开辟空间来存入数据 SLN* BuySListNode(ALTDataType x); //打印链表 void SListPrint(SLN* phead); //头插 void sListPushFront(SLN** pphead, ALTDataType x); //尾插 void sListPushBack(SLN** pphead, ALTDataType x); //头删 void sListPopFront(SLN** pphead); //尾删 void sListPopBack(SLN** pphead); //查找链表 SLN* sListFind(SLN* phead, ALTDataType x); //修改对应链表位置的数据 void sListModify(SLN* phead, SLN* pos, ALTDataType x, ALTDataType y); //任意位置的插入,在pos位置的前一个位置插入 void sListInsert(SLN** pphead, SLN* pos, ALTDataType x); //任意位置的删除 void sListErase(SLN** pphead, SLN* pos); //销毁链表 void destorySList(SLN* phead);

SList.c文件

#include"SList.h" //开辟空间来存入数据 SLN* BuySListNode(ALTDataType x) { SLN* newnode = (SLN*)malloc(sizeof(SLN)); if (newnode == NULL) { perror("malloc"); return NULL; } newnode->data = x; newnode->next = NULL; return newnode; } //打印链表 void SListPrint(SLN* phead) { assert(phead); SLN* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("\n"); } //头插 //想要头插，我们要把新节点的地址给到头节点，再把新节点定义为新的头节点 void sListPushFront(SLN** pphead, ALTDataType x) { SLN* newnode = BuySListNode(x); newnode->next = *pphead; *pphead = newnode; } //尾插 void sListPushBack(SLN** pphead, ALTDataType x) { SLN* newnode = BuySListNode(x); //若一开始链表为空，我们直接插入一个新节点 if (*pphead == NULL) { *pphead = newnode; } //我们要创建一个变量，找到链表的尾端，从尾端插入 SLN* tail = *pphead; while (tail->next) { tail = tail->next; } tail->next = newnode;//尾节点链接新节点 } //头删 void sListPopFront(SLN** pphead) { assert(*pphead); SLN* next = (*pphead)->next;//*小于->的优先级，编译器不通过 free(*pphead); *pphead = NULL; *pphead = next; } //尾删 void sListPopBack(SLN** pphead) { assert(*pphead); //当只有一个节点时 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; return; } SLN* tail = *pphead; SLN* prev = NULL; while (tail->next) { prev = tail; tail = tail->next; } free(tail); tail = NULL; prev->next = NULL; } //查找链表 SLN* sListFind(SLN* phead, ALTDataType x) { assert(phead); SLN* cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } //修改对应链表位置的数据 void sListModify(SLN* phead, SLN* pos, ALTDataType x, ALTDataType y) { pos = sListFind(phead, x); pos->data = y; } //任意位置的插入,在pos位置的前一个位置插入 void sListInsert(SLN** pphead, SLN* pos, ALTDataType x) { if (pos == *pphead) { sListPushFront(pphead, x); return; } SLN* newnode = BuySListNode(x); SLN* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = newnode; newnode->next = pos; } //任意位置的删除,删除pos位置的值 void sListErase(SLN** pphead, SLN* pos) { if (pos == *pphead) { sListPopFront(pphead); return; } SLN* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } //销毁链表,这些空间，我们要一个一个释放，防止内存泄漏 void destorySList(SLN* phead) { assert(phead); SLN* tail = phead->next; while (tail) { SLN* next = tail->next; free(tail); tail = NULL; tail = next; } free(phead); phead = NULL; }

test.c文件

#include"SList.h" void Test1() { SLN* plist = NULL; SLN* pos = NULL; sListPushFront(&plist, 4); sListPushFront(&plist, 3); sListPushFront(&plist, 2); sListPushFront(&plist, 1); SListPrint(plist); sListPushBack(&plist, 5); sListPushBack(&plist, 6); sListPushBack(&plist, 7); sListPushBack(&plist, 8); SListPrint(plist); sListPopFront(&plist); sListPopFront(&plist); SListPrint(plist); sListPopBack(&plist); sListPopBack(&plist); SListPrint(plist); pos = sListFind(plist, 5); if (pos == NULL) { printf("找不到该数据\n"); } else { printf("已找到该数据，现在进行修改\n"); sListModify(plist, pos, 5, 50); } SListPrint(plist); pos = sListFind(plist, 50); if (pos == NULL) { printf("找不到该数据\n"); } else { printf("已找到该数据，现在进行在pos前插入数据\n"); sListInsert(&plist, pos, 20); } SListPrint(plist); pos = sListFind(plist, 20); if (pos == NULL) { printf("找不到该数据\n"); } else { printf("已找到该数据，现在进行对pos位置数据的删除\n"); sListErase(&plist, pos); } SListPrint(plist); destorySList(plist); printf("链表已销毁\n"); } int main() { Test1(); return 0; }

结果：大家下去还是要自己敲一遍代码，才能做到掌握

---

好了，今天的内容就是这些，我们下期再见铁汁们！

感谢品读！！！