18 | 重新认识数据结构（上）：初识链表结构

胡光

你好，我是胡光，欢迎来到“算法数据结构篇”的第一课。
在之前的学习中，我们对数据结构的认识，主要集中在它是用来做数据的表示，更具体地讲，就是数据结构所讨论的问题，是将现实中的数据如何合理地表示在程序中，以使程序完成既定的目标任务。
不知道你还记不记得，在上节课 Shift-And 算法的学习中，我们发现不同的数据，或者说信息表示方式，会给解决问题的效率带来很大的影响。因此，基本确定了数据的表示，在程序设计过程中发挥着非常重要的作用，也就意味着我们必须对数据结构的学习重视起来。
之前我们所讨论的数据结构呢，其实都只是停留在程序内部的数据结构，这是一种具体的，可见的数据结构，并对我们设计的程序产生重要影响。我们也认识到，这种具体的数据结构的重要作用，会对我们设计的程序产生重要的影响。今天呢，我将带你重新认识数据结构，发现它的另一面，那就是数据结构对我们思维方式的影响，这种影响更抽象，也更重要。
接下来的两次课程内容呢，我将通过链表结构的讲解，让你认识这种思维层面的数据结构。
必知必会，查缺补漏今天我们将要学习的链表，是一种常见的基础数据结构，属于数据结构中线性结构的一种。在讲如何学习链表之前，我们先来看一看通常情况下，如何学习数据结构的相关的知识。

公开

同步至部落

取消

完成

0/2000

荧光笔

直线

曲线

笔记

复制

AI

深入了解
翻译
英语
中文简体
中文繁体
法语
德语
日语
韩语
俄语
西班牙语
阿拉伯语
解释
总结

本文介绍了链表结构的基本概念和操作方法。作者首先强调了数据结构对程序设计的重要性，指出了数据结构对思维方式的影响。随后详细介绍了链表的结构定义，包括数据信息和地址信息，并给出了链表节点的示意图和代码定义。文章重点讲解了链表的插入操作，引入了虚拟头结点的概念，并提出了删除节点的作业。最后，强调了链表结构中数据域的灵活性和指针域的重要性，并展望了其他形式的链表结构。整体来说，本文通过简洁清晰的语言，帮助读者重新认识了链表结构，突出了链表结构的灵活性和重要性。文章内容涵盖了链表的基本概念和操作方法，对于想要深入了解数据结构的读者具有一定的参考价值。

仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《人人都能学会的编程入门课》，新⼈⾸单¥59

立即购买

登录后留言

全部留言(17)

最新
精选

🤪HappyJoo
老师您好，请问一下，这个虚拟头结点是如何不影响链表的呢？我的理解是，每次执行插入函数（这个*insert是函数吧。C语言的函数就是方法？）时，都创造一个虚拟结点（计算机会自动创造吗？），让它指向链表的真正头结点，执行函数。函数执行结束后，将虚拟结点与真正头结点断开，这样子就可以做到“虚拟”了。请问老师我的理解有哪些不对的地方吗？谢谢老师~~~
作者回复: 当然不是计算机自动创造的，而是我们通过代码逻辑加上去的。所谓虚拟，就是只有在操作过程中，存在的一个节点，这个节点完全是为了操作简便，额外加上去的，不是链表的实际节点。
2020-02-29

2
徐洲更
python里的list可以存放不同数据类型，也是用链表实现的嘛，C语言如何写出这种数据结构呢
作者回复: python中的list不是用链表实现的，那样的话，查找效率太差了，C中的话，可以用指针数组实现，指针类型是void *即可指向任意一种类型数据。
2020-02-27

2
宋不肥
作业打卡： #include<stdio.h> struct Node { int data; struct Node *next; }; struct Node *insert(struct Node *head, int ind, struct Node *a) { struct Node ret, *p = &ret; ret.next = head; // 从【虚拟头节点】开始向后走 ind 步 while (ind--) p = p->next; // 完成节点的插入操作 a->next = p->next; p->next = a; // 返回真正的链表头节点地址 return ret.next; } struct Node *erase(struct Node *head, int ind){ struct Node ret, *p = &ret; ret.next = head; while(ind--) p = p->next; p->next = p->next->next; return ret.next; } main(){ struct Node N1,N0,N3; N0.data = 0; N0.next = &N1; N1.data = 1; N1.next = &N3; N3.data = 3; N3.next = NULL; struct Node N2; N2.data = 2; N2.next = NULL; insert(&N0, 2, &N2); printf("%d\n",(N1.next)->data); erase(&N0, 2); printf("%d",(*N1.next).data); } 然后有个问题，被删除的结点的内存需要手动释放嘛？感觉这样就只是不用这个结点了，他占用的内存会被当做垃圾碎片嘛
作者回复: 对，实际上是需要手动释放的，如果是 C 的话，你可以使用 free 来进行释放。没有强调释放的原因是，咱们这个不是一份完整的链表代码，没有从创建开始讲，所以突然提到释放，就会很突兀。你可以想到这个问题，是很棒的！
2020-02-29

1
🤪HappyJoo
不知道有没有用，“画”了一个图给对于插入不太懂的同学看看哈哈哈哈： ----p----p.next----| ----> |----p p.next---- | ----> | \ / | ----> | \ / -------a-----------| ----> | a
作者回复: d(^_^o)给个封号：最强助教！
2020-02-29

1
doge
struct Node* erase(struct Node *head, int ind){ struct Node ret, *p = &ret, *q = NULL; if (ind < 1){ err("invalid position %d\n", ind); return head; } ret.next = head; while (--ind && p->next != NULL) p = p->next; if (ind != 0) err("invaild position, node not found\n"); else { q = p->next; p->next = q->next; free(q); } return ret.next;
作者回复: 非常棒！还实现了非法情况判断！d(^_^o)
2020-02-28

1
奕
// 删除指定索引位置的节点 struct Node *erase(struct Node *head, int ind) { struct Node preNode, *p = &preNode; preNode.next = head; while (ind--) { p = p->next; } // 指向删除节点的下一个位置 p->next = p->next->next; return preNode.next; }
作者回复: 完美！d(^_^o)
2020-02-27

1
一溢孤行
#include <stdio.h> #include <stdlib.h> #include <string.h> //定义单链表结点的数据结构 typedef struct Node { int data; //数据类型及其相应的值 struct Node* next; //指向下一个结点 }Node; //创建单链表的一个结点 Node* create_node(int num) { //给每个节点分配结构体一样的空间大小 Node* p = malloc(sizeof(Node)); if (p == NULL) { printf("malloc error!\n"); return NULL; } //由于结构体在未初始化的时候数据是杂乱的，所以要清先进行清理 memset(p, 0, sizeof(Node)); //初始化第一个节点 p->data = num; //将节点的后继指针设置为NULL p->next = NULL; } Node* insert(Node* head, int ind, Node* a) { Node ret, * p = &ret; ret.next = head; // 从【虚拟头节点】开始向后走 ind 步 while (ind--) p = p->next; // 完成节点的插入操作 a->next = p->next; p->next = a; // 返回真正的链表头节点地址 return ret.next; } //链表的遍历 void Print_Node(Node* pH) { //获取当前的位置 Node* p = pH; //获取第一个节点的位置 p = p->next; //如果当前位置的下一个节点不为空 while (p->next != NULL) { //(1)打印节点的数据 printf("data: %d\n", p->data); //(2)移动到下一个节点,如果条件仍为真，则重复(1)，再(2) p = p->next; } //如果当前位置的下一个节点为空，则打印数据 //说明只有一个节点 printf("data: %d\n", p->data); } int main() { int i; Node* header = create_node(0);//给头结点赋值为0 for (i = 1; i < 10; ++i) { insert(header, i, i); } Print_Node(header); } 老师，我这段代码哪里有错误啊，为什么编译到你提供的插入函数的时候就访问异常了呀？
作者回复: 代码 BUG 尽量自己找吧，程序员的职业道德是，自己写的 bug 自己找啊~~~~~ 你首先看你的 print_node 里面的 while 循环逻辑。不应该是 p->next != NULL，而是 p 就不能为 null 啊~~~，p 不为 null，才能合法访问 p->data 啊
2020-08-10


1043
在“数据结构 = 结构定义 + 结构操作”这个公式里结构定义已经是像乐高玩具的形状一样做好的模型，这个基本上不改动硬件设施就不能变了，在计算机中这个操作是否是操作计算机是指令系统？结构操作是以给定的形状和结构特点自己拼装，这就涉及操作是否规范了，有的操作可能带来破坏性的结果，在计算机中这个结构操作也可能出现破坏性的结果或者直接能去通过计算操作损坏硬件吗？最古老的时代有个病毒记得叫CHI还行就能损坏硬件，好像也是c语言编写的，c真的有这么大的破坏力吗？
作者回复: 结构性质是自己定义的，结构操作也是你自己实现的，所以是否规范，主要看操作是否破坏结构性质。操作系统是C语言写的，你想想C语言如果要是想干坏事儿，得多容易。(｡ì _ í｡)
2020-04-14


webmin
```golang type Node struct { Val int Next *Node } func erase(head *Node, ind int) *Node { if head == nil { return head } ret := &Node{ Next: head, } p, prev := ret, ret for ; ind >= 0; ind-- { if p == nil || p.Next == nil { return ret.Next } prev = p p = p.Next } prev.Next = p.Next return ret.Next } func NewNode(nums []int) *Node { if len(nums) == 0 { return nil } head := &Node{ Val: nums[0], } h := &Node{ Next: head, } for i := 1; i < len(nums); i++ { head.Next = &Node{ Val: nums[i], } head = head.Next } return h.Next } func TestErase(t *testing.T) { head := NewNode([]int{1, 2, 3, 4, 5, 6}) head = erase(head, 3) for head != nil { fmt.Printf("%d -> ", head.Val) head = head.Next } fmt.Println() fmt.Println("###########") head = NewNode([]int{1, 2, 3, 4, 5, 6}) head = erase(head, 0) for head != nil { fmt.Printf("%d -> ", head.Val) head = head.Next } fmt.Println() fmt.Println("###########") head = NewNode([]int{}) head = erase(head, 1) for head != nil { fmt.Printf("%d -> ", head.Val) head = head.Next } fmt.Println() fmt.Println("###########") head = NewNode([]int{1, 2, 3, 4, 5, 6}) head = erase(head, 5) for head != nil { fmt.Printf("%d -> ", head.Val) head = head.Next } fmt.Println() fmt.Println("###########") head = NewNode([]int{1, 2, 3, 4, 5, 6}) head = erase(head, 7) for head != nil { fmt.Printf("%d -> ", head.Val) head = head.Next } } ```
作者回复: 可以可以！d(^_^o)
2020-04-02


信念
我记得我们上学期计算机老师专门有一节课讲过数组和链表，数组是连续的，而链表不一定是连续的
作者回复: 老师说的没错！
2020-03-14



收起评论