深入浅出数据结构C语言版(4)——表与链表

  在我们谈论本文具体内容之前,我们首先要说明一些事情。在现实生活中我们所说的“表”往往是二维的,比如课程表,就有行和列,成绩表也是有行和列。但是在数据结构,或者说我们本文讨论的范围内,我们所说的“线性表”是一维的,即所有“元素”都是前后排列的。就我个人而言,这样的“表”用“队列”来形容比较恰当。但是,数据结构中“队列”这个名词是被一种特殊的“线性表”给占用了的,所以我们没法再用“队列”来表示“线性表”,后期我们会对“队列”进行介绍。

  

  在第一段的说明过程中,我们其实已经说出了“线性表”的定义,就是若集合中的元素在逻辑上是一前一后像队伍一样联系起来的,那么这个集合就是一个表(准确地说是线性表)。

  显然,我们常用的数组就是表的一种,它符合“元素一前一后联系起来”的要求。线性表是最基础的数据结构(虽然结构体也能存多个数据在内,但其整体还是视为一个对象的),每当我们需要存储的数据不存在特殊的关系(比如以后会说的一对多关系),或者存在的关系为“一前一后”时(比如用户输入多个字符,字符间就存在输入顺序上的“一前一后”关系),我们就可以使用线性表。

  那么,线性表的相关知识讲到这儿就算结束了吗?毕竟数组大家应该都会用了。显然不是,我们说了,数组是线性表的一种,但也只是线性表的一种。

  接下来我们就要说说,使用数组作为线性表的缺点。首先让我们假设一种情况(这个在(1)中提到过):

  我们要写一个程序,这个程序的过程很简单:获取用户输入(这里就需要用到表来存储用户的输入),对用户的输入进行计算或操作,输出结果。

  但是这个程序要考虑一个情况:用户有时候只需要输入几个数据,而有时候却需要输入几万个数据(可能有人会说怎么可能输入那么多,人都累死了。。。但是别忘了有一种操作叫文件重定向,虽然我记不得也没用过)。对于C程序来说,这个问题是不得不考虑的,如果你决定使用数组来存储用户的输入,那么数组的大小在创建之时就要确定好。很显然,数组的大小很好确定,比如十万,反正绝对大于用户可能的输入数量就行。但是这会带来一个很严重的问题,就是你的程序在不需要那么多空间的情况下依然会使用那么多空间,比如用户平均输入只有几百个,然而每次运行程序都先占用了十万大小的数组空间。显然这样的程序很不好,一来用户的内存可能还有别的程序需要使用,二来可能别的用户不需要十万个的存储空间而且他的内存也不够。

  那么对于这种情况,我们该怎么办呢?

  首先我们发现我们依然要用到线性表(假设用户的输入数据间的关系就是一前一后),所以我们先确定下来使用的是线性表类型的数据结构。然后我们希望的关键点其实就是:线性表能够随着需要而改变大小。那么我们该如何实现这样一个线性表呢?现在,不需要你去思考解决方案了,我们已经有了现成的数据结构,那就是链表!

  回顾数组,我们发现,其实我们知道的信息有两个:

  1.数组第一个元素在哪(数组名)

  2.数组中元素都是相邻的,后一个元素就在前一个元素的后面,中间没有“空”

  因为我们知道这两个信息,所以我们不需要知道各个元素的具体位置,只要根据某个元素在线性表中的顺序位置n,就可以由第一个元素的位置加上n来得到该元素。

  但这也正是数组的不足所在,为了满足第2点,我们必须在创建数组时就指定其大小,只有这样我们才能找到满足2的一整块区域给数组。那么,为了解决这个不足,我们要做的就是不再使用一整块区域,而是令各元素自取所需。即元素不一定是相邻的了,只要添加元素时找一个可以放下该元素的容身之所就行,这一点的实现显然是利用malloc()。

  但这又会带来一个问题,由于各元素都是通过malloc()获取的内存,所以各元素都分散开了,那么我们该如何找到各元素呢?实现的办法很简单,就是令每个元素“记住”下一个元素的位置!这样一来,我们就只需要保存第一个元素的位置就可以了,第二个元素的位置在第一个元素中,第三个元素的位置又在第二个元素中,以此类推。

  接下来我们要做的,就是将这个想法付诸实现了。相信很快,我们就会发现,实现链表的关键之处在于如何“令元素记住下一个元素的位置”?在这里我们要多嘴一句,正如第一篇博文所说的,数据结构不仅决定如何存储数据,有时候也要决定或者说不得不考虑“存储什么数据”。现在我们就遇上了这样的问题。显然,原始元素本身是不会记住下一个元素在哪的,比如原始元素类型为int,它又如何去记住下一个int在哪?这时候,我们就需要对数据“封装”一下,形成一种新的数据类型,然后这种数据类型要能够记住下一个相同数据类型的位置。

  思路已经出来了,就是“封装”出新的数据类型,然后要求其能记住下一个相同数据类型数据的位置。“封装”可以令我们想到结构体(也许你想不到但没关系,现在知道了),而“位置”则会让我们想到指针。因此我们“封装”出来的新数据类型应该是一个类似这样的结构体:

struct  Element
{
DataType data; //DataType根据实际元素类型决定
struct Element * next; //next意味着其存储下一个元素的位置
}

  然后在我们的程序中,我们只需要知道第一个元素在哪就行了(第一个会告诉我们第二个在哪,以此类推):

struct  Element  a={data,NULL};
struct Element * List=&a; //这个List就是一个“链表”

  现在,对于为什么要使用链表,以及链表该如何实现的基本思想及如何“封装”出链表的元素我们应该都明白了。

  但是虽然知道了链表添加新元素时该怎么做已经有了口头上的描述,却还没有给出代码上的实现,并且如何从链表中删除一个元素以及如何找到第n个元素也还没给出实现。

  这些可以统称为对链表的操作,也可以说是能对链表这种数据结构使用的算法。关于这些,我们将在下一次博文中介绍。

上一篇:k8s家族Pod辅助小能手Init容器认知答疑?


下一篇:35 编码 ASCII Unicode UTF-8 ,字符串的编码、io流的编码