· 链表的实现与介绍

——————————————本文旨在交流计算机知识，欢迎指正————————————— 首先，我们回顾一下上一期讲的顺序表：顺序表是一种物理结构上连续的，一整块连续空间的逻辑表，但是，试想一下，如果每次我们都是申请在一块整块空间里面的顺序表，但是我们并不知道堆空间里面我们malloc一块空间之后我们并不知道它的存储样式，假设我们申请了两段空间，但是这两块空间之间只有两个单位，但是我们要新存下四个单位的顺序表，那么这两个单位的空间显然装不下我们的顺序表，我们需要另外申请一块新的空间去存它，但是这些夹着的碎片化空间就会造成浪费，无法使用：于是，我们这时候需要一种新的结构去存储，来避免这种空间浪费的情况，链式存储结构应运而生：这样，我们就能理论上节约内存了；（PS: 事实上，由于操作系统的存在，我们存储的只是在虚拟内存上，而它真实的内存其实映射到我们的物理内存上并非是如此的，于是对于顺序表操作系统给我们分配的物理内存其实并非真正连续的，我们这里讨论的其实只是无操作系统下关于内存的合理化分配）下面，我们来详细讲讲关于链表的知识：首先我们给出链表的图形化结构：我们的链表包含一个头节点，一个尾部节点和数个中间节点，头结点的前驱是空，尾节点的后继也是空，中间节点都拥有前驱与后继。关于每一个节点，我们将其分为两个部分：1、数据域 2、地址域；数据域存储该节点应该存储的数值，地址域指向下一个地址，然后我们通过地址域来访问下一个值。

这样，我们就构成了一份链式存储结构；于是，下面我们来尝试写一下代码：

首先，和顺序表一样，我们先来定义链表的节点结构：

1
#ifndef COMMON_H
2
#define COMMON_H
3
typedef int Element_t;
4
// 1. 定义链表的节点结构
5
typedef struct _node{
6
Element_t val;//数据域
7
struct _node *next;//存储下一个节点地址的地址域
8
} node_t;
9

10
#endif //COMMON_H

第二步，我们来写链表头结点的定义及函数的定义（如果对这里有所不明白的地方请翻到我的上一篇文章查看.h文件与.c文件的关系）：

1
#ifndef CHAIN_LIST_H
2
#define CHAIN_LIST_H
3
#include "common.h"
4

5
// 2. 定义带头指针的链表头结构
6
typedef struct {
7
node_t *header;
8
int count;
9
} ChainList_t;
10

11
// 3. 链表头放到数据区，放到全局变量
12
void initChainList(ChainList_t *table);
13

14
void destroyChainList(ChainList_t *table); // 销毁该链表的元素区域，头不管
15

16
int insertChainListHeader(ChainList_t *table, Element_t val);//头插法
17

18
int insertChainListPos(ChainList_t *table, int pos, Element_t val);//按位插入
19

20
int deleteChainListElement(ChainList_t *table, Element_t val);//按值删除
21

22
void showChainList(const ChainList_t *table);//显示链表
23
#endif //CHAIN_LIST_H

第三步，我们开始正式写函数啦：（一）初始化函数

1
void initChainList(ChainList_t* table) {
2
table->count = 0;//表头不计入元素个数
3
table->header = NULL;//表头指向NULL
4
}

（二）销毁链表函数

1
void destroyChainList(ChainList_t *table) {
2
// 创建虚拟头节点，方便统一处理所有节点
3
node_t dummy;
4
dummy.next = table->header;
5
// 从虚拟头节点开始遍历链表
6
node_t *p = &dummy;
7
node_t *tmp;
8
// 逐个释放链表中的所有节点
9
while (p->next) {
10
tmp = p->next; // 保存当前要删除的节点
11
p->next = tmp->next; // 从链表中移除该节点
12
free(tmp); // 释放节点占用的内存
13
--table->count; // 更新链表节点计数
14
}
15

16
// 输出链表剩余节点数
17
printf("LinkList have %d node!\n", table->count);
18
// table->header = NULL;
19
}

（三）头插法

1
int insertChainListPos(ChainList_t* table, int pos, Element_t val) {
2
node_t dummy;
3
dummy.next = table->header;
4

5
// 1. 判断边界值
6
if (pos  table->count) {
7
printf("insert pos invalid!\n");
8
return -1;
9
}
10
// 2. 找到pos - 1索引的节点首地址
11
node_t *p = &dummy;
12
int index = -1;
13
while (index next;
14
++index;
15
}
16
node_t *new_node = malloc(sizeof(node_t));
17
new_node->val = val;
18
new_node->next = p->next;
19
p->next = new_node;
20
++table->count;
21

22
table->header = dummy.next;
23
return 0;
24
}

（四）、删除操作

1
int deleteLinkListElement(LinkList_t* table, Element_t val)
2
{
3
node_t *p = &table->head;//引入辅助节点
4
while (p->next!=NULL)
5
{
6
if (p->next->val == val)break;//如果当前辅助节点存储的值val等于删除目标，退出循环
7
p = p->next;//辅助节点不断向后遍历
8
}
9
if (p->next == NULL)//判断是否有该值
10
{
11
return -1;
12
}
13
node_t *tmp = p->next;
14
p->next = tmp->next;
15
free(tmp);
16
table->count--;//记录链表节点减1
17
return 0;
18
}

（五）、展现函数

1
void showChainList(const ChainList_t* table) {
2
node_t *p = table->header;
3
printf("link list: %d\n", table->count);
4
while (p) {//如果p存在
5
printf("%d\t", p->val);
6
p = p->next;
7
}
8
printf("\n");
9
}

（六）、主函数（测试函数）

1
// 带头节点的单向链表测试
2
int test01() {
3
LinkList_t* table = createLinkList();
4
if (table == NULL) {
5
return -1;
6
}
7
for (int i = 0; i < 10; ++i) {
8
insertLinkListHeader(table, i + 100);
9
}
10
insertLinkListPos(table, 3, 300);
11
showLinkList(table);
12
printf("========================\n");
13
deleteLinkListElement(table, 105);
14
showLinkList(table);
15

16
releaseLinkList(table);
17
return 0;
18
}
19

20
int main() {
21
test01();
22
return 0;
23
}

锵锵~到这里就要收尾啦！希望这篇文字对你有所帮助！

音乐

文章分享

评论区

音乐

音乐

文章目录