有没有大佬可以详细的讲讲链表？第1页

timothyqiu 网友的相关建议:

这么多东西一股脑儿混在一起学确实很麻烦，一样一样来就好了。

既然你觉得动态内存分配和指针学得不扎实，影响你理解链表。那我们先不用动态内存分配和指针，只用普通数组，是不是就可以理解了呢？

       #include <stdio.h>  int main() {     struct node {         char payload;           // 节点的负载数据         int next_index;         // 下一个节点的索引号     };     struct node nodes[16];      // 索引号索引的是这个数组      // 设置 4 个节点，在内存中不连续     nodes[1].payload = 'A';     nodes[1].next_index = 11;      nodes[11].payload = 'B';     nodes[11].next_index = 3;      nodes[3].payload = 'C';     nodes[3].next_index = 7;      nodes[7].payload = 'D';     nodes[7].next_index = -1;   // 用无效的索引号表示链表结束      int head_index = 1;         // 链表头节点索引号      // 遍历输出 A -> B -> C -> D -> END     for (int cur = head_index; cur != -1; cur = nodes[cur].next_index) {         printf("%c -> ", nodes[cur].payload);     }     puts("END");      // 删除位置是 2 的节点（C）     // 如果删除的是 0，就更简单了，调整 head_index 就行     {         // 找到这个位置的前一个节点         int prev_index = head_index;         for (int i = 1; i < 2; i++) {             prev_index = nodes[prev_index].next_index;         }         // 在 B->C->D 里删除 C         // 直接让 B->D 就行了         nodes[prev_index].next_index = nodes[nodes[prev_index].next_index].next_index;     }      // 遍历输出 A -> B -> D -> END     for (int cur = head_index; cur != -1; cur = nodes[cur].next_index) {         printf("%c -> ", nodes[cur].payload);     }     puts("END");      // 在 1 号位置（A 之后）插入新节点     // 如果在 0 插入，就更简单了，调整 head_index 就行     {         // 找到这个位置的前一个节点         int prev_index = head_index;         for (int i = 1; i < 1; i++) {             prev_index = nodes[prev_index].next_index;         }         // 在 A->B 之间插入 X         // 很多网文里说，一定要先让 X->B 再让 A->X         // 没必要这么教条，如果你记录了 B 是什么，完全可以把顺序反过来         int const next_index = nodes[prev_index].next_index;         nodes[prev_index].next_index = 4; // A->X         nodes[4].payload = 'X';         nodes[4].next_index = next_index; // X->B     }      // 遍历输出 A -> X -> B -> D -> END     for (int cur = head_index; cur != -1; cur = nodes[cur].next_index) {         printf("%c -> ", nodes[cur].payload);     }     puts("END"); }

理解之后，你大概率就会觉得索引号用起来太麻烦了，还得写这种又臭又长的：

       // 装修前 nodes[prev_index].next_index = nodes[nodes[prev_index].next_index].next_index

翻翻书，复习一下指针怎么用，就可以把索引号都换成指针，代码也会简洁不少：

       // 装修后 prev->next = prev->next->next;

整个代码就变成了：

       #include <stdio.h>  int main() {     struct node {         char payload;           // 节点的负载数据         struct node *next;      // 下一个节点的指针     };     struct node nodes[16];      // 指针指向的内容都在这个数组里      // 设置 4 个节点，在内存中不连续     nodes[1].payload = 'A';     nodes[1].next = &nodes[11];      nodes[11].payload = 'B';     nodes[11].next = &nodes[3];      nodes[3].payload = 'C';     nodes[3].next = &nodes[7];      nodes[7].payload = 'D';     nodes[7].next = NULL;       // 用空指针表示链表结束      struct node *head = &nodes[1];  // 链表头节点指针      // 遍历输出 A -> B -> C -> D -> END     for (struct node *cur = head; cur != NULL; cur = cur->next) {         printf("%c -> ", cur->payload);     }     puts("END");      // 删除位置是 2 的节点（C）     // 如果删除的是 0，就更简单了，调整 head_index 就行     {         // 找到这个位置的前一个节点         struct node *prev = head;         for (int i = 1; i < 2; i++) {             prev = prev->next;         }         // 在 B->C->D 里删除 C         // 直接让 B->D 就行了         prev->next = prev->next->next;     }      // 遍历输出 A -> B -> D -> END     for (struct node *cur = head; cur != NULL; cur = cur->next) {         printf("%c -> ", cur->payload);     }     puts("END");      // 在 1 号位置（A 之后）插入新节点     // 如果在 0 插入，就更简单了，调整 head_index 就行     {         // 找到这个位置的前一个节点         struct node *prev = head;         for (int i = 1; i < 1; i++) {             prev = prev->next;         }         // 在 A->B 之间插入 X         // 很多网文里说，一定要先让 X->B 再让 A->X         // 没必要这么教条，如果你记录了 B 是什么，完全可以把顺序反过来         struct node *const next = prev->next;         prev->next = &nodes[4]; // A->X         nodes[4].payload = 'X';         nodes[4].next = next;   // X->B     }      // 遍历输出 A -> X -> B -> D -> END     for (struct node *cur = head; cur != NULL; cur = cur->next) {         printf("%c -> ", cur->payload);     }     puts("END"); }

然后你可能觉得写死数组里的索引号太傻了，1、11、3、7、4 什么的一点意义都没有。那么就可以放弃 nodes 数组改用动态分配：

       #include <stdio.h> #include <stdlib.h>  int main() {     struct node {         char payload;           // 节点的负载数据         struct node *next;      // 下一个节点的指针     };      // 设置 4 个节点，在内存中不连续     struct node *a = malloc(sizeof(struct node));     struct node *b = malloc(sizeof(struct node));     struct node *c = malloc(sizeof(struct node));     struct node *d = malloc(sizeof(struct node));     a->payload = 'A';     a->next = b;     b->payload = 'B';     b->next = c;     c->payload = 'C';     c->next = d;     d->payload = 'D';     d->next = NULL;         // 用空指针表示链表结束      struct node *head = a;  // 链表头节点指针      // 遍历输出 A -> B -> C -> D -> END     for (struct node *cur = head; cur != NULL; cur = cur->next) {         printf("%c -> ", cur->payload);     }     puts("END");      // 删除位置是 2 的节点（C）     // 如果删除的是 0，就更简单了，调整 head_index 就行     {         // 找到这个位置的前一个节点         struct node *prev = head;         for (int i = 1; i < 2; i++) {             prev = prev->next;         }         // 在 B->C->D 里删除 C         // 直接让 B->D 就行了         prev->next = prev->next->next;     }      // 遍历输出 A -> B -> D -> END     for (struct node *cur = head; cur != NULL; cur = cur->next) {         printf("%c -> ", cur->payload);     }     puts("END");      // 在 1 号位置（A 之后）插入新节点     // 如果在 0 插入，就更简单了，调整 head_index 就行     struct node *x = malloc(sizeof(struct node));     {         // 找到这个位置的前一个节点         struct node *prev = head;         for (int i = 1; i < 1; i++) {             prev = prev->next;         }         // 在 A->B 之间插入 X         // 很多网文里说，一定要先让 X->B 再让 A->X         // 没必要这么教条，如果你记录了 B 是什么，完全可以把顺序反过来         struct node *const next = prev->next;         prev->next = x;     // A->X         x->payload = 'X';         x->next = next;     // X->B     }      // 遍历输出 A -> X -> B -> D -> END     for (struct node *cur = head; cur != NULL; cur = cur->next) {         printf("%c -> ", cur->payload);     }     puts("END");      free(a);     free(b);     free(c);     free(d);     free(x); }

然后你觉得，这么长一串代码挤在 main 里看起来太累了，于是简单地封装了几个函数：

       #include <stdio.h> #include <stdlib.h>  struct node {     char payload;           // 节点的负载数据     struct node *next;      // 下一个节点的指针 };  struct list {     struct node *head;      // 链表头节点指针 };  // 初始化 void list_init(struct list *l) {     l->head = NULL;         // 用空指针表示链表结束 }  // 遍历输出 void list_print(struct list *l) {     for (struct node *cur = l->head; cur != NULL; cur = cur->next) {         printf("%c -> ", cur->payload);     }     puts("END"); }  // 指定位置插入节点 void list_insert(struct list *l, int pos, struct node *node) {     if (pos == 0) {         // 如果在 0 插入，就更简单了，调整 head_index 就行         node->next = l->head;         l->head = node;     } else {         // 找到这个位置的前一个节点         struct node *prev = l->head;         for (int i = 1; i < pos; i++) {             prev = prev->next;         }         // 在 A->B 之间插入 X         // 很多网文里说，一定要先让 X->B 再让 A->X         // 没必要这么教条，如果你记录了 B 是什么，完全可以把顺序反过来         struct node *const next = prev->next;         prev->next = node;  // A->X         node->next = next;  // X->B     } }  // 指定位置删除 void list_erase(struct list *l, int pos) {     if (pos == 0) {         // 如果删除的是 0，就更简单了，调整 head_index 就行         l->head = l->head->next;     } else {         // 找到这个位置的前一个节点         struct node *prev = l->head;         for (int i = 1; i < pos; i++) {             prev = prev->next;         }         // 在 B->C->D 里删除 C         // 直接让 B->D 就行了         struct node *const next = prev->next->next;         prev->next = next;     } }  int main() {     struct list l;      list_init(&l);      // 设置 4 个节点，在内存中不连续     struct node *a = malloc(sizeof(struct node));     a->payload = 'A';     list_insert(&l, 0, a);      struct node *b = malloc(sizeof(struct node));     b->payload = 'B';     list_insert(&l, 1, b);      struct node *c = malloc(sizeof(struct node));     c->payload = 'C';     list_insert(&l, 2, c);      struct node *d = malloc(sizeof(struct node));     d->payload = 'D';     list_insert(&l, 3, d);      // 遍历输出 A -> B -> C -> D -> END     list_print(&l);      // 删除位置是 2 的节点（C）     list_erase(&l, 2);      // 遍历输出 A -> B -> D -> END     list_print(&l);      // 在 1 号位置（A 之后）插入新节点     struct node *x = malloc(sizeof(struct node));     x->payload = 'X';     list_insert(&l, 1, x);      // 遍历输出 A -> X -> B -> D -> END     list_print(&l);      free(a);     free(b);     free(c);     free(d);     free(x); }

到目前为止，我们（链表的使用方）都在手动管理内存，链表自身只负责组织节点。

于是我现在表示看 main 结尾的那五个free 不爽，不想自己管理内存了，于是修改一下插入和删除节点的逻辑，再添加一个释放整个链表的函数就可以了：

       // 指定位置插入节点 void list_insert(struct list *l, int pos, char value) {     struct node *node = malloc(sizeof(struct node));     node->payload = value;      if (pos == 0) {         // 如果在 0 插入，就更简单了，调整 head_index 就行         node->next = l->head;         l->head = node;     } else {         // 找到这个位置的前一个节点         struct node *prev = l->head;         for (int i = 1; i < pos; i++) {             prev = prev->next;         }         // 在 A->B 之间插入 X         // 很多网文里说，一定要先让 X->B 再让 A->X         // 没必要这么教条，如果你记录了 B 是什么，完全可以把顺序反过来         struct node *const next = prev->next;         prev->next = node;  // A->X         node->next = next;  // X->B     } }  // 指定位置删除 void list_erase(struct list *l, int pos) {     if (pos == 0) {         // 如果删除的是 0，就更简单了，调整 head_index 就行         struct node *const next = l->head->next;         free(l->head);         l->head = next;     } else {         // 找到这个位置的前一个节点         struct node *prev = l->head;         for (int i = 1; i < pos; i++) {             prev = prev->next;         }         // 在 B->C->D 里删除 C         struct node *const next = prev->next->next;         free(prev->next);         // 直接让 B->D 就行了         prev->next = next;     } }  // 结束 void list_terminate(struct list *l) {     struct node *cur = l->head;     while (cur) {         struct node *const next = cur->next;         free(cur);         cur = next;     } }  int main() {     struct list l;      list_init(&l);      // 设置 4 个节点，在内存中不连续     list_insert(&l, 0, 'A');     list_insert(&l, 1, 'B');     list_insert(&l, 2, 'C');     list_insert(&l, 3, 'D');      // 遍历输出 A -> B -> C -> D -> END     list_print(&l);      // 删除位置是 2 的节点（C）     list_erase(&l, 2);      // 遍历输出 A -> B -> D -> END     list_print(&l);      // 在 1 号位置（A 之后）插入新节点     list_insert(&l, 1, 'X');      // 遍历输出 A -> X -> B -> D -> END     list_print(&l);      list_terminate(&l); }

最后，你想对外隐藏链表的实现细节，于是单独搞了一个头文件。

       #ifndef DEMO_LIST_H_ #define DEMO_LIST_H_  struct list;  // 初始化 struct list *list_init(); // 结束 void list_terminate(struct list *l);  // 遍历输出 void list_print(struct list *l); // 指定位置插入节点 void list_insert(struct list *l, int pos, char value); // 指定位置删除 void list_erase(struct list *l, int pos);  #endif  // DEMO_LIST_H_

当然这样一来，struct list 就不能在栈上创建了，必须使用指针。那么就干脆把 list_init 也改了，整个链表都动态分配：

       // 初始化 struct list *list_init() {     struct list *l = malloc(sizeof(struct list));     l->head = NULL;         // 用空指针表示链表结束     return l; }  // 结束 void list_terminate(struct list *l) {     struct node *cur = l->head;     while (cur) {         struct node *const next = cur->next;         free(cur);         cur = next;     }     free(l); }

这样原来的代码就看上去顺眼多了：

       #include "list.h"  int main() {     struct list *l = list_init();      // 设置 4 个节点，在内存中不连续     list_insert(l, 0, 'A');     list_insert(l, 1, 'B');     list_insert(l, 2, 'C');     list_insert(l, 3, 'D');      // 遍历输出 A -> B -> C -> D -> END     list_print(l);      // 删除位置是 2 的节点（C）     list_erase(l, 2);      // 遍历输出 A -> B -> D -> END     list_print(l);      // 在 1 号位置（A 之后）插入新节点     list_insert(l, 1, 'X');      // 遍历输出 A -> X -> B -> D -> END     list_print(l);      list_terminate(l); }

当然代码是我临时在知乎这个超难用的 Markdown 编辑器里瞎写的，错误处理也没做，但原理是这样的，不保证没有 BUG :D

s.invalid 网友的相关建议:

理解链表的确是应该和内存空间分配以及指针联系起来的。但糅合起来前，先把每个元素分别弄清楚会事半功倍。

先说指针。

其实指针很容易理解：比如你声明了一个整型变量A，这个A就对应着内存条上的某几个门电路，你修改A的值就是让这几个门电路记录你给出的某些信息，读取A的值就是从这些门电路把信息读取出来。

既然内存条可以存储8G、16G甚至更多数据，变量A又只占用了其中几个“格子”；那么问题来了：你是怎么从内存条上海量的“格子”中，找到变量A对应的那几个呢？

事实上，为了能够使用内存条，它的每个格子我们都会编个地址。

C系编程语言可以用&A取出变量A对应的那几个格子的地址。比如令int *p=&A，于是就取出一个值0x12397AB0存到指向整型数据的指针p里面去了——意思是变量A的内容就存储在地址0x12397AB0开头的八个格子里（对64位系统来说）。

注意这里一定要清楚区分变量A的值、A这个符号以及变量A的地址三者。

比如，声明变量A，并设置A的值为123，对应的程序语句就是：

       int A=123；

而

       printf("%d", A);

就可以把123打出来。

A这个符号是帮助你记忆的，因此实际程序里最好不要用A、B、C之类没有意义的名字。你应该根据用途，为每个变量起一个含义明确的名字，比如sumOfMoney（现金总计）等。

注意A、sumOfMoney这类符号在程序编译之后就会消失，编译器只会记录变量A对应的地址，不会再记A、sumOfMoney之类东西。因为CPU不需要知道这些。

但这样我们调试程序时就很不方便了，一堆数字谁看得懂什么意思啊。因此我们会要求编译器把程序编译成debug版。这会额外生成个符号表，把内存地址和变量名称联系起来，方便我们理解。

A的地址就是前面提到的0x12397AB0之类东西。这个东西必须在程序运行时才能得到，因为操作系统不一定把你的程序加载到内存条的哪个位置；因此必须程序运行起来了，A才会得到自己的地址（对局部变量的话还必须执行到对应的函数、且函数未曾返回前，这个变量才是有效的）——这就涉及到进程的概念，考验你基础知识牢固程度的时候到了。

这个听起来挺复杂，也的确不好理解。但你可以写个程序，用单步执行跟一下，这些过程就清清楚楚摆在眼前了——写程序，然后单步跟踪，这是理解计算机程序执行过程最大的捷径。

缺乏直观的理解，就容易“学而不思则罔”；实际跟着看一看，把学过的知识回想回想、一点点和实物对应上，直观理解就来了。

当然，你也不能尽信单步跟踪。因为很多东西是编译器相关的、同时还有优化选项的干扰（会使得生成的机器码和你敲出的程序不再对应）；因此需要不停的和C/C++标准对照着看，否则就“思而不学则殆”了。

类似的，指针是一个特殊的变量。比如我们可以定义一个整形指针p：

       int *p=&A;

和普通的变量A一样，指针变量p同样有自己存储的值、自己的名字以及自己的地址。

在这个案例里，指针变量p存储着0x12397AB0，也就是A的地址。或者说，p的值就是0x12397AB0。

p的名字是p，这个是方便我们记忆的——和A一样，就不多说了。

p的地址是&p——没错，指针变量和普通的变量一样，也要在内存中占据若干个格子；它占据的格子同样有地址，我们同样需要借助地址访问它（想起“指针的指针”这种奇怪的东西了吗？其实它就这么简单）。

注意：指针p和内存地址0x12397AB0并不等价。因为0x12397AB0仅仅指向了内存空间某几个格子的起始处；但一个int可能有2个、4个甚至8个字节，也就是占据2~8个格子，仅仅一个0x12397AB0是不包含长度信息的。而int* p这个声明就明确指示了编译器：p指向的地址，也就是0x12397AB0，并不是简单的一个单元格（一个字节），而是足够放下一个int型数据的内存区域。

类似的，我们还可以搞出指针的指针、指针的指针的指针之类东西。你同样可以自己写个程序然后用单步执行跟着看看，从而彻底把这块搞清楚——只听别人讲、看书上说是不够用的；必须自己动手、动脑，彻底把相关概念搞明白。

理工科的东西极重概念。概念不清，后面什么都别想学进去。

再说内存分配。

对PC机来说，内存就是主板上插的内存条。你可以把它理解为一个面积超大的黑板，你的程序、音乐播放器、杀毒软件、操作系统等等，都要在上面“演算”一些东西，也就是都要在上面占据一些空间。

但内存比较贵，空间有限；加上程序太多，大家都要用。那么乱用显然是不行的，不然你演算一半别人把你的内容擦掉你就傻了；或者，你只管用不去擦，别人见上面有内容又不敢擦，那么大片内存空间就会浪费掉，闹得大家都没法干活。

因此，操作系统定下了一些规矩，要求所有程序都必须照规矩使用内存。其中：

程序代码本身因为很少改变，操作系统会按一定规则直接载入内存（还可能加上只读保护，也就是检测并阻止对程序代码占用的内存区的改写动作，从而避免恶意破坏）。
你声明的全局变量、静态变量、字符串常量等也会分别安置在一个固定的内存区域。
程序运行时，不可避免的要调用一些函数；这些函数用到的局部变量会被一个叫做“栈”的数据结构管理；而栈本身可以被CPU指令直接支持，因此速度极快。

其中，栈的大小是动态变化的，由CPU自动维护；但其它区域都是固定不变的——程序一写出来，占用的内存空间大小就确定了。

但这样显然不够用。因为还会有很多无法事先确定空间大小的任务，比如载入一个word文档、一副图片、从硬盘加载一个庞大的游戏地图，等等。

这些功能并不能用栈支持。这是因为栈空间是连续的，栈内存的使用是伴随着函数调用自动分配/归还的，规整而死板（调用函数时，局部变量就得到可用的栈上空间；一旦函数返回，栈上空间就自动归还：因此C语言有很多“返回栈上空间指针”的题目，就是考察你知不知道“不能返回局部变量的指针”）。

然而很多场景里，内存空间的占用时间并不能事先确定——比如说，玩家控制的角色发射了一个“火球”，我们就要为火球分配内存、并且在屏幕上画上一个火球；但这个火球并不能在createFireball这个函数返回后马上删除，而是需要在屏幕上飞行一段时间、击中目标或者超出射程才可以删除它。

如果放到栈上，一旦函数返回，这个火球就会被提前删除；然后如果再调用了其它函数，火球占用的内存空间就会被挪作它用，整个执行逻辑就错乱了。

因此，我们需要一个更灵活的内存管理方式，这就是malloc/new（C系程序员习惯称其为堆分配）。

堆分配说白了也很简单：

你调用malloc/new这个语言提供的库函数/关键字提出需求：老兄，我需要内存！
库函数malloc/关键字new替你调用操作系统API：大哥，给点内存！
操作系统一查，有内存可用；再一查，这次malloc是进程1239调用的；于是记下一笔账：题主启动的、进程id为1239的进程找我要了XX字节内存，将来它退出时我要全部收回！（这里实际上颇为复杂，比如还可能存在内存池之类东西，但现在不用管）
malloc拿着操作系统分给你的内存，返回给你：喏，你要的内存空间给你安排好了！
于是，你得到了一个地址；从这个地址开始的、你要求大小的那块内存都是你的（new更复杂一些，它还要调用你的构造函数、帮你初始化这块内存空间，暂不深入讨论）。

这就是所谓的随机内存分配。

归还也一样，你调用free，传入malloc返回给你的那个地址，库函数free就替你把内存归还了——然后操作系统就把你的欠账从小本本上一笔划掉了。

典型的内存分配代码：

       //分配可用存储100个int的内存空间 int* p = malloc(sizeof(int)*100); //malloc返回一个地址，我们把这个地址存储在指针p中，方便将来使用  //使用p指向的内存空间完成工作 ...  //工作完成后，归还内存 //注意malloc会做一个暗记，比如把分配的内存大小存储到p指向的地址的前面几个单元里（不同编译器手法可能不同） //因此这里不需要给free传入待归还的内存大小 //当然，如果你故意搞破坏，比如把p-1位置的内容置零，那么乐子可就大了 free(p);

还记得前面关于指针变量的讨论吗？

没错：

指针变量p被分配在栈上或者其它的固定存储区里（后者对应全局变量/静态变量等情况）
p存储的内容是malloc函数返回的一个内存地址

看出不同了吗？

没错：和指针变量p以及常规的变量A不同，我们通过malloc新分配的100个int，它是没有名字的！

它仅仅是一个地址；我们可以想办法用指针p来保存这个地址、也可以把它传递给另一个指针；但它并不像普通的变量那样有一个名字。

这是因为，它是动态分配的内存，是程序执行时才分配的东西，是脱离编译器控制的——前面讨论过，变量名称是方便我们记忆的东西；编译器需要把我们写在程序里的A、p、sumOfMoney等符号自动转换成内存地址。

而malloc分配的东西是运行时才能得到的一块内存，是不可能像其它变量那样直接通过名称使用的。我们必须借助指针p之类东西间接访问它。

那么，你可能就要问了：如果我们的程序很复杂很复杂，比如可能有一千个火球，那该怎么办啊？

总不能这样吧：

       //直接申请1000个火球的空间 //但是1000个火球可能还不够用，因为战斗就有那么激烈！ //但是绝大多数战斗只会同时存在两三个火球，空余1000个火球太浪费空间了！ //我们还得处理火球飞行之类动作。这样是不是每一帧画面就要遍历1000个火球对应的空间？ fireBall *pFireBall=malloc(sizeof(fireBall)*1000);  //怎么办呢？难道这样: //这得占用多少栈空间啊 //而且1000个变量，这程序写出来……成什么狗屎了！ fireBall *pFireBall1=malloc(sizeof(fireBall)); fireBall *pFireBall2=malloc(sizeof(fireBall)); fireBall *pFireBall3=malloc(sizeof(fireBall)); ……

怎么办呢？

没错，上链表。

我们知道，C语言允许我们把基本数据类型组合起来，搞一个自定义数据结构（struct）；甚至还可以在struct里面存放另一个struct，嵌套出复杂的数据结构。那么：

       struct fireBallNode{    fireBall fb; //火球对应的数据结构    fireBallNode* next; //这里指向下一个node节点 };  //现在,用p记录第一个火球对应的内存空间 fireBallNode *p = malloc(fireBallNode); fireBallNode *pHead = p; //记住链表首节点的位置，避免后面搞丢。 //初始化第一个火球 initFireball(p->fb);  //第二个火球继续往后挂 p->next = malloc(fireBallNode); //初始化第二个火球 //也可以是p=p->next; initFireball(p->fb);这种写法和初始化第一个火球完全相同，更方便循环执行 initFireball(p->next->fb);   p=p->next; //让p指向第二个节点，这样接下来的代码形式相同，可以写成循环  //再生成并初始化剩下的998个火球 //其实你可以改写一下，从第一个火球开始就放进循环里，不需要前面两段重复代码 //总之就这个意思，明白了爱怎么写怎么写；不明白就眼花缭乱 for(size_t i=2; i<1000; i++) {   p->next = malloc(fireBallNode);   p=p->next;   initFireball(p->fb); }

你看，就好像链条一样，我们只需一个变量p，就可以灵活管理一大溜的、数量不限的火球了——搞一百万个火球也不怕，我们的程序肯定能处理；只是机器性能/内存容量可能顶不住罢了。

进一步抽象：其实任何需要在运行时灵活决定数量的东西，都可以用类似方式组织数据。

那么我们其实可以做一个通用的实现，这样就不用在管理冰雹、人员或别的什么时，都从头写那么一大堆链表访问链表维护操作代码了：

       struct Node{    void* data; //这里保存用户自己申请的内存空间，随便用户存什么咱都不需要管    Node* next; //这里指向下一个节点，咱靠它帮用户把一拉溜内存空间串起来，别的不需要咱管 };  //为了方便使用，我们需要再定义一组可以方便的操纵链表的接口 //比如增加节点、删除节点，比如链表倒置，等等 //这样就不需要每个项目都重写一遍了 //这就是所谓的“库”  //对火球这个应用来说，你malloc块内存按火球的要求初始化、然后把Node里面的data指针指向这块内存就行了 //可参考前面的代码，把它迁移到这个“库”上面来  //你也可以参考libc的list以及c++的list（c++的list用了泛型，要难懂一些）， //想想这些list该如何用、它们的使用/控制接口是否和你想象的以及课本上的有所不同

你看，就这么土，一点都不神秘。

容易看出，链表这种东西适合存储数量随机、顺序不限的东西。比如游戏里的火球/子弹等对象，比如操作系统里面的内存分配表，比如账务软件里面的流水账，比如一条条的日志信息，等等。

但如果要在上面做搜索、或者需要实现“优先级队列”（比如操作系统的进程列表）、或者有别的稀奇古怪的需求，链表就力不从心了——这时候，就需要队列、栈、树、map等东西出场了。

但总的来说思路是差不多的：想要提高速度、节约空间，那就要用连续内存空间、上各种索引；想要灵活控制空间大小，那就通过类似链表的、借助指针一层层“钩挂”数据的思想来管理数据结构——不同的需求经常还需要把各种思路“杂交”起来（比如各种map就是“增强版”的、便于搜索的数组，但同时为了方便管理也会借助类似链表的手法管理空间、仅仅把key放进排序数组；再比如树就是“增强版链表”，只不过它有两个以上的next指针，分别指向大于/小于当前节点的索引值的其它数据，从而可以在像链表那灵活管理内存的基础能力之外、提供强悍的搜索能力）……于是，五花八门无限复杂的各种数据结构就出现了。

总之，不要把链表及其相关算法当咒语背。这种东西极其实用，自己在机器上实现出来、在项目中用一用，马上就全明白了。

这东西实在太基础了，稍微有一点上机练习、稍微给自己点任务压一压，独立从头发明出来都不难；也必须学到这个水平，将来遇到稍微复杂一点的任务时，才可能随机应变的根据实际需要“捏造”出最适合自己需要的数据结构——这，就是为何说“算法+数据结构=程序”的原因（现在颇有一些半瓶子咣当的家伙喜欢扯淡什么“算法+数据结构=程序已经落伍了、失效了，现在都面向对象了”；只要你稍有经验，就知道那纯属外行扯淡）。

当然，如果你自己不动手、不琢磨，希望别人给你讲懂、希望通过看书看懂……那是绝对不可能的。神仙都学不会。

没错，再强调一遍：链表、树、广义表、各种map……这些东西，自己写出来、发明出来，都不难；因为这本就是程序员们每天都在进行的普通工作，本就应该随手拈来、任意化用的——不然动态创建几个火球你是不是就晕菜了？稍微上点规模的程序里满满当当可都是资源管理！

而且，很多情况下，你还必须结合设计目的正确选择数据结构、甚至不得不因地制宜的综合若干种数据结构之长，这才能简洁高效的实现功能——比如操作系统里面广泛应用的“优先级队列”，你看数据结构这本书里讲过吗？可一但真学会了算法，这玩意你就应该听到名字、稍微一琢磨它的技术要求，自己就马上能发明一个出来。

当然，重复一遍：想走到这一步是不可能一蹴而就的；你必须从语言基础开始逐一夯实基础，尽量理解到“水到渠成”的水准，这才可能真正掌握相关知识。

有没有大佬可以详细的讲讲链表？的其他答案点击这里

有没有大佬可以详细的讲讲链表？第1页

相关话题

前一个讨论

下一个讨论

相关的话题

有没有大佬可以详细的讲讲链表？ 第1页

相关话题

前一个讨论

下一个讨论

相关的话题

有没有大佬可以详细的讲讲链表？第1页