【数据结构】单链表

系列文章目录

顺序表

动态顺序表实现的通讯录

文章目录

系列文章目录
前言
一、pandas是什么？
二、使用步骤
- 1.引入库
- 2.读入数据
总结

前言

大家是否记得我们在顺序表中留下的几个问题？

对于顺序表的空间浪费和插入耗时过长，我们的解决方法就是使用新的数据结构——链表。

一、链表的概念及结构

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

我们可以用火车来类比链表，这两者的结构十分相似。

火车的车厢个数会随着乘客人数的变化而变化，淡季减少，旺季增加；增加的车厢可以在整个火车的任何位置插入进去，且每节车厢独立存在，不影响其他车厢。

每个车厢都有两个门，链接前后车厢。假设：每个车厢门都是关闭状态，需要钥匙打开，我们手上每次只能有一把钥匙，要能走遍所有车厢，应该怎么做？

最简单的办法：在每一节车厢中存放下一节车厢的钥匙即可。

那么在链表里，每节“车厢”是什么样的？

与顺序表不同，链表的每节“车厢”都需要独立申请内存空间，我们称为“节点/结点”。

结点主要由两部分组成：当前节点要保存的数据和下一个节点的地址（指针变量）。

我们为什么要在当前节点里保存下一个节点的地址呢？

链表中的每个节点都是独立申请内存空间，我们需要通过指针变量保存下一个节点的地址才能找到下一个节点，相当于我们要在当前车厢存放下一个车厢的钥匙，才能打开下一个车厢的门。

通过上面对于链表的结构分析，我们能给出每个节点的结构体代码：

struct list
{int val; // 当前节点需要保存的数据struct list* next; // 保存下个节点的地址
};

我们知道写出每个链表节点，接下来就要将它们连接在一起形成链表：

int main()
{struct list* phead = NULL; // 定义头指针指向第一个节点struct list* pcur = phead; // 通过该指针将所有节点连接起来for (int i = 0; i < 3; i++) // 这里创建了3个结点{struct list* newnode = (struct list*)malloc(sizeof(struct list));// 对每个结点独立申请空间newnode->val = i; // 写入该节点要保存的数据newnode->next = NULL; // 若该指针为最后一个节点，不让其指向有效地址，防止野指针if (phead == NULL) // 头指针为空，使其指向第一个节点pcur = phead = newnode;else {pcur->next = newnode; // 让上一个节点next指向当前节点pcur = newnode; // 将pcur重新指向当前节点}}return 0;
}

接下来，对于一个给定的链表，我们如何实现节点从头到尾的打印呢？

	pcur = phead; // 是遍历节点的指针指向第一个节点while (pcur) // 如果pcur为空，说明没有节点，跳出循环{printf("%d ", pcur->val); // 打印当前节点的数据pcur = pcur->next; // 让pcur指向下一个节点}

打印结果：

我们这里val的类型是int，如果想要保存的数据类型是字符，浮点或者自定义类型，改为该类型即可。

补充说明：

链式结构在逻辑上是连续的，在物理结构上不一定连续
节点一般是从堆上申请的
从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续

二、单链表的实现

我们再清楚了链表的结构后，可以尝试实现以下单链表的增删查改操作。

1. 链表节点结构体代码

typedef int Listdatatype;
typedef struct SListNode
{Listdatatype data;struct SListNode* next;
}Listnode;

2. 链表的增加

为了方便增加链表节点，我们将申请空间这个操作包装为一个函数：

Listnode* Listapply(Listdatatype x)
{Listnode* newnode = (Listnode*)malloc(sizeof(Listnode));if (newnode == NULL) // 如果申请失败，报错并结束程序{perror("malloc");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}

下面是尾删代码：

// 为了能够修改头指针的内容，需要传址调用，这里传参是二级指针接受
void Listpushback(Listnode** pphead, Listdatatype x)
{assert(pphead);Listnode* newnode = Listapply(x);if (*pphead == NULL) // 头指针为空，令头指针指向新建的第一个节点{*pphead = newnode;}else{Listnode* pcur = *pphead;while (pcur->next) // 找到链表的最后一个节点{pcur = pcur->next;}pcur->next = newnode;}
}

再有了尾增代码，接下来的头增代码很容易

void Listpushfront(Listnode** pphead, Listdatatype x)
{assert(pphead);Listnode* newnode = Listapply(x);newnode->next = *pphead;*pphead = newnode;
}

3. 链表的删除

尾删：

void Listpopback(Listnode** pphead)
{assert(pphead);assert(*pphead);Listnode* pcur = *pphead;if (pcur->next == NULL) // 链表中只有一个节点，删除该节点同时让头指针指向空{free(pcur);pcur = NULL;*pphead = NULL;}else{Listnode* prev = *pphead; while (pcur->next) // 找到最后一个节点，同时让prev指向倒数第二个节点{prev = pcur;pcur = pcur->next;}free(pcur);pcur = NULL;prev->next = NULL; // 让prev指向的节点的next指向空}
}

头删：

void Listpopfront(Listnode** pphead)
{assert(pphead);assert(*pphead);Listnode* pcur = *pphead;if (pcur->next == NULL) // 链表中只有一个节点，删除该节点同时让头指针指向空{free(pcur);pcur = NULL;*pphead = NULL;}else{pcur = pcur->next;free(*pphead);*pphead = pcur; // 修改头指针的指向}
}

最难的增删结束后，我们来看看简单点的查找和修改

Listnode* Listfind(Listnode* phead, Listdatatype x)
{assert(phead);Listnode* pcur = phead;while (pcur){if (pcur->data == x) // 找到该节点，返回该节点地址return pcur;pcur = pcur->next;}return NULL; // 没有找到返回空
}

void Listchange(Listnode* pos, Listdatatype x)
{assert(pos);pos->data = x;
}

最后就剩下了链表的销毁了

void Listdestory(Listnode** pphead)
{assert(pphead);Listnode* pcur = *pphead;Listnode* next = pcur;while (pcur){next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}