首页 > 代码库 > 深入浅出数据结构C语言版(4)——表与链表

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

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

  

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

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

 

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

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

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

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

 

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

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

 

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

  1.数组第一个元素在哪

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

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

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

  但这又会带来一个问题,就是大家都分散开了,又如何找到大家呢?

  让我们再次回顾数组的信息2,然后进行另一个角度的解释:

  数组中某个元素的位置其实是根据其前一个元素的位置+1来获得的,而第一个元素的位置则需要我们手动保存。换句话说,某个元素的位置是其前一个元素“告诉”我们的!

  让我们把这一想法应用到我们的新想法中!即令每一个元素“记住”其下一个元素的位置!这样一来,我们就可以根据需要来向表中添加元素了,只要加入新元素后,原先的最后一个元素“记住”新元素在哪就可以令这个表像锁链一样“链”起来!我们的“链表”思想也就诞生了~:-P

 

 

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

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

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

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

struct  Element  a={data,NULL};
struct  Element  * List=&a;

//然后向这个以List开头的链表添加元素

 

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

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

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

 

  最后总结,我们这次讲了哪些呢?

第一,什么是表。

第二,表有什么可能的用处。

第三,数组作为表的缺点。

第四,引出链表的想法以及基本思路、基本元素的“封装”

 

  下一次博文,我们将介绍链表的操作,以及特殊的“链表”——游标数组

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