内存长什么样
上一节只说了线性表能做什么,没说它怎么存。这一节回答本章开头的第三个问题:怎么把它放进内存。
内存可以看成一长排编了号的格子。每个格子放一个字节,格子的编号叫地址。程序读写数据,就是按地址找格子。
下面画出其中一段,编号从100到115。两头的省略号表示前后还有很多格子:
text ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
… │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ …
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115
这排格子只有一种天然的关系:前后相邻。100号后面是101号,101号后面是102号,仅此而已。
本节问题把cat的三个字符放进三个格子,没有困难。可是线性表除了元素,还有"a在c后面"这样的关系。这条关系放在哪里?
什么是顺序存储
顺序存储就是:线性表里相邻的元素,放在内存里相邻的格子中。这样存的线性表叫顺序表。
以cat为例。c放100号,a放101号,t放102号。字符在内存里的先后,就是它们在线性表里的先后:
text ┌───┬───┬───┬───┬───┬───┬───┬───┬───┐
… │ c │ a │ t │ │ │ │ │ │ │ …
└───┴───┴───┴───┴───┴───┴───┴───┴───┘
100 101 102 103 104 105 106 107 108
关系没有单独占地方,它藏在位置里。a在101号,c在100号,两格相邻,"a在c后面"就成立了。
所以数据和关系都存下来了,而且关系一个字节都不占。另一个好处是,要取第i个元素,直接去找第i个格子就行,不用经过前面的元素。后面比较效率时,会用到这一点。
长度。上面的图还有个漏洞:103号往后的格子里是什么?没人知道,可能是这段内存上次留下的任何东西。要把这一行显示出来,从100号开始读,读到哪里停?
所以除了这段格子,还得另外记一个数:现在有效的元素有几个。cat是3,读三个就停。插入一个变成4,删掉一个变成2。这个数就是线性表的长度。
一个顺序表,就是一段连续的格子,加上一个长度。
用C语言表示顺序表
一段连续的格子,在C语言里就是数组。数组的大小在编译时就要定下来,先定100,够不够用后面再说:
c#define MAXSIZE 100
char data[MAXSIZE]; /* 一段连续的格子 */
int length; /* 当前有效的元素个数 */
data[0]到data[length-1]是有效元素,data[length]往后是空闲的。cat存进去,就是data[0]到data[2],length为3。
结构体。线性表是一个东西,现在却由两个变量表示:数组和长度。后面每个操作都要同时用到这两样,分开放很容易忘掉一个。C语言用结构体把几个变量装成一个整体:
ctypedef struct {
char data[MAXSIZE]; /* 存放元素的连续空间 */
int length; /* 当前元素个数 */
} SeqList;
SeqList就是"顺序表"这个类型。一个SeqList类型的变量L里,有一个数组和一个长度,用点号访问:L.data[i]是第i个元素,L.length是长度。
元素类型写成char,是因为本章存的是字符。要存别的类型,把char换掉就行。
例题:把cat放进顺序表,再读出来
题目定义一个SeqList类型的变量L,把c、a、t三个字符放进去。然后打印整行,再单独打印第2个元素。
分析。按存和取的先后逐步写。
- 放元素:c、a、t依次放进
L.data[0]、L.data[1]、L.data[2],相邻的元素放在相邻的格子里。 - 记长度:放了三个,
L.length设为3。 - 读整行:从
L.data[0]开始,读到L.data[L.length-1]为止,一个一个打印。 - 取第2个:直接打印
L.data[2],不用经过前面的元素。
c#include <stdio.h>
#define MAXSIZE 100
typedef struct {
char data[MAXSIZE];
int length;
} SeqList;
int main(void) {
SeqList L;
L.data[0] = 'c';
L.data[1] = 'a';
L.data[2] = 't';
L.length = 3;
for (int i = 0; i < L.length; i++) /* 读回整行 */
printf("%c", L.data[i]);
printf("\n");
printf("%c\n", L.data[2]); /* 直接取第2个 */
return 0;
}
第一行说明关系没丢:按位置从0读到length−1,顺序和线性表一致,"a在c后面"不需要任何额外记录。第二行说明取第i个元素一步到位。
这里是手工把字符放进数组的,只为看清结构。下一节有了操作之后,就不再直接碰data和length了。