用故事解释顺序结构与链式结构

好好学习，天天向上

本文已收录至我的Github仓库DayDayUP：github.com/RobodLee/DayDayUP，欢迎Star

⭐⭐⭐⭐⭐转载请注明出处：https://blog.csdn.net/weixin_43461520/article/details/123962053

这个学期我们有一门课，是关于信息技术教学的，就是每位同学分配数据结构的一个章节，然后上台讲一下。分给我的是顺序结构和链式结构的内容，为了讲得有意思点，我编了个小故事，并做了些动画。感觉还不错，动画做了挺长时间的，为了不浪费我辛辛苦苦编的故事和做的动画，所以水篇文章来分享一下。

不管是顺序结构还是链式结构，都是对数据在内存中存储方式的描述。所以为了能够讲明白这两种数据结构，有必要先来介绍一下计算机的内存。

上面这张图，图中的每一行都是一个存储单元，若干个存储单元组合构成了存储体。每个存储单元都连接有一根字选线，对应内存地址。

比如现在读取内存地址为 0 的存储单元的数据：首先CPU通过地址总线将地址信息发送给MAR，MAR再将地址给译码器，译码器可以通过地址选择对应的字选线，然后给对应的存储单元一个信号。最后通过数据线(绿线)就可以将存储单元中的二进制数据发送到MDR中。这样就完成了数据的读操作，如果是写操作，只要通过读/写控制线来控制是读还是写，如果是写，则是将MDR中的数据通过数据线发送到对应的存储单元中。

这些都是计算机组成原理的一些知识，没学过的小伙伴可能看的不太明白，没关系，这里只要知道一个概念就好，那就是 计算机内存是由若干存储单元构成，每个存储单元都有独一无二的编号(内存地址)，计算机可以对指定内存地址的存储单元进行读 / 写操作。

这就好比，计算机内存可以看做是一家宾馆，每一个房间都是一个存储单元，房间号对应的就是内存地址，房间里的房客就是存在内存中的数据。

介绍顺序结构之前，先来讲一个小故事：

有一天，爷爷带着七个葫芦娃来城里旅游。

既然是来旅游的，那么总不能睡大街吧，所以爷爷和葫芦娃们准备先找一家宾馆住下。他们找了一家空房间比较多的宾馆，爷爷一次性开了七个连在一起的房间，然后让七个葫芦娃依次住了进去。

从图中可以看出，七个房间是挨在一起的，所以七个葫芦娃也是一个一个按顺序住在各自的房间里。像这样的就是顺序结构。

顺序结构，它是指各数据元素依次存储在计算机中一组地址连续的存储单元中。采用这种存储方式，在逻辑上前后相邻的两个元素在计算机内存中也是相邻的。

顺序结构对应的其实就是数组，那么用代码该怎么表示上面的例子呢：

代码中，通过new关键字开辟了一个大小为7的数组，就相当于爷爷开了七个房间，然后向数组里存放了七个数据，相当于七个葫芦娃依次住进了各自的房间里。

介绍完了顺序结构再来介绍一下链式结构。还是接着上面的故事说。

葫芦娃们在这家宾馆住了一段时间后，觉得住的有点不得劲，想换一家。但是爷爷想：在这住的好好的为什么要换呢？但是拗不过这几个小的，只能依着他们了，毕竟双拳难敌十四手嘛，虽然爷爷长的比较壮，，，

然后他们就收拾东西来到了一家新的宾馆。

由于这家宾馆生意比较好，住的人有点多，没有连在一起的七个房间了，爷爷索性就让他们随便住了，挑自己喜欢的房间住。

等住完了之后爷爷心里想：这几个小娃娃怎么住的这么分散，要是弄丢了可怎么搞，不得心疼死我呀。

于是乎，爷爷就找到了前台小姐姐，找她要了七张小纸条。

然后爷爷将七张小纸条分给了葫芦娃们，然后他们每个人都在小纸条上记着下一个葫芦娃的房间号。这样虽然几个葫芦娃都不住在一起，但是通过纸条上的房间号就可以依次找到下一个葫芦娃的房间。这样从大娃开始，就可以找到所有的葫芦娃了。

链式结构的特点是存储各个数据元素的计算机存储单元的地址不一定是连续的，但是在逻辑上相邻的。每个结点都包含数据域和指针域两部分。

故事中所表示的就是链式结构。我们再来思考一个问题，现在通过纸条可以找到下一个葫芦娃的房间，但是怎么找到上一个呢？好像不可以，稍微做一下修改，比如现在每个葫芦娃手上有两张纸条，另一张纸条上记录的是上一个葫芦娃的房间号。

其实这个就是双链表，每个结点都有两个指针，分别指向上一个结点与下一个结点。

所以说，数据结构研究的就是数据如何在内存中存储。尽管数据结构有多种，但是数据都是在内存中存放的，只不过约束条件不同，概念就有所区别。不管是栈、队列等简单一点的数据结构，还是树、图等复杂一点的数据结构，他们的实现方式无非就三种：顺序存储、链式存储、顺序存储+链式存储。bky

最后，我们再来拓展一个知识点，就是如何用顺序结构和链式结构来实现栈。

栈是一种只能从栈顶存放数据和取出数据的数据结构。不能从栈底对元素进行操作。

如果采用顺序结构实现，可以准备一个数组，规定数组起始位置为栈底，靠近末尾一侧为栈顶。那么添加和取出元素就只能从末尾一侧进行操作了。

typedef struct {
    ElemType data[MaxSize];     //用于存放数据
    int top;                    //指向栈顶
} SqStack;

如果换做是链式结构。那么规定表头为栈底，表尾为栈顶。那么就只能从表尾添加或移出元素。如果反过来规定表头为栈顶，表尾为栈底也是可以的，反正只能从一端进行操作就符合栈的定义。

typedef struct StackNode {
    ElemType data;
    struct StackNode *next;
} *LinkStack;

研究数据结构就是研究数据在内存中怎么存储，在学习某种新的数据结构时，先了解其定义，再思考它的实现方式以及如何在内存中存储，便能很容易理解。

写作不易，看完记得点赞哦~~~~

⭐⭐⭐⭐⭐转载请注明出处：https://blog.csdn.net/weixin_43461520/article/details/123962053

本文已收录至我的Github仓库DayDayUP：github.com/RobodLee/DayDayUP，欢迎Star

如果您觉得文章还不错，请给我来个点赞，收藏，关注

学习更多编程知识，WeChat扫描下方二维码关注公众号『 R o b o d 』：