Skip to content
第1章

1.4 关系怎么放进内存 ​

本节问题
内存只是一排格子,四种关系怎么放进去?

计算机的内存可以看成一长排编了号的格子,每个格子放一个字节,编号叫地址。这排格子只有一种天然的关系:前后相邻,100号后面是101号,仅此而已。内存本身是一维的、线性的。

数据本身放进格子没有困难,问题是关系放在哪。线性关系里"a在c后面"、树形关系里"b是a的孩子"、图关系里"a和b之间有条路"——这些信息不是数据本身,它们该存在什么地方?

办法只有两种。

一种是用位置表示关系:不存关系,用位置隐含地表示它——约定相邻格子放相邻元素,"a在c后面"就是把a放在c的下一格。关系不占任何空间,它藏在位置里。代价是位置一旦定了就不能随便动——中间要插一个元素,后面的都得挪。这叫顺序存储。

另一种是用地址表示关系:把关系显式地存下来——每个元素旁边多留几个格子,记下与它有关系的元素的地址。"a在c后面"就是在c旁边写下a的地址。元素可以散落在内存任何地方,插入删除只改几个地址,不挪动别人。代价是关系要占空间,而且要找第i个元素只能顺着地址一站一站走。这叫链式存储。

两种办法各有一头快、一头慢,没有哪一种全面占优。第2章会用一个真实的任务把两种存法都做一遍,把这句话变成具体的数字。

其他存储方式,比如索引存储、散列存储,本质上都是这两种手段的组合或变形,后面用到时再介绍。四种逻辑关系也都能用这两种手段装进一维的内存:线性关系对应数组和链表;树形关系每个结点记下孩子的地址;图关系用一张二维表记录任意两点之间有没有边,或者给每个顶点挂一条链;集合关系没有关系要记,关键是"判断在不在"要快,通常用散列表。这些都是后面各章的内容。

到这里你有了
"关系存在哪里"这个问题的两个答案,以及它们各自的代价。
练一练
(1)一列火车的车厢是顺序存储还是链式存储?在中间加挂一节车厢,要动几节?(2)教室里的座位表按行列排,是哪种存储?如果每个学生手里拿着"下一个同学是谁"的纸条,又是哪种?(3)为什么链式存储"要找第i个元素只能一站一站走"?
选中正文里的任意文字,就可以针对它发表评论