顺序表的存储结构
顺序表(Sequence Lists)就是线性表(Linear List)中的顺序存储结构。
顺序表是储存在内存中的地址连续的,元素依次被塞进这个存储单元里。
在 sequence list 中获取元素的位址
假设每一个 sequence list 里的element都占据一个存储单元,
又因为 sequence list 的每一个element都是按照顺序存储在内存里,
那么就有: addr(element[i]) = addr(element[1]) + (i-1)
;
但实际上一个element其实可以占据不止一个存储单位。
那假设每个element占据的为d
,那就能有:addr(element[i]) = addr(element[1]) + (i-1) * d
。
通过这个公式可以直接计算出随便一个element的location,又因为没有循环,所以它的时间复杂度记作O(1)
,又可以说它是 random access,这是 sequence list 的一个优点
建立顺序表的结构
静态建表:首先要知道以下三个东西:
- 被分配到存储空间的首地址
- 最大储存容量
- 表当前的长度
其中表的长度一定要小过被分配到的存储空间的大小,不然系统就会觉得啊♂好大塞不下了,要溢出来了。
定义一个结构:
静态分配
// 给integer取个花名叫做elemType
typedef int elemType;
typedef struct {
elemType array[114514];
// 定义一个elemType(即integer)类型的array,
// 这个array本身就是这个线性表的起始位址;
// 这个[114514]就是这个线性表的最大存储容量
// 换句话说光这一行就定义了上面说的三个东西中的前两个
int length;
// 来储存当前的表长
}sequenceList;
// 给这个structure取个名字叫做`sequenceList`
这样子静态分配出来的线性表,它的最大储存容量是固写死的,也就是114514
。静态,就是不能按需变动,就是不灵活。
动态分配
有静就有动,除了静态分配以外,还有一种建表方法就做“动态分配”。
就是在定义顺序表的时候不直接写死它的存储空间,而是在程序运行的过程中让它按需分配。
定义结构:
typedef int elemType;
typoedef struct {
elemType *data;
// 动态分配不开array,而是给一个pointer
int size;
// 因为这回不是array了,所以要整一个变量来指示这个list的总长度
int length;
}sequenceList;
调用:
sequenceList list;
list.data = (elemType*) malloc( sizeof(elemType) * 114514);
// ~~~~~~~~~~~ ~~~~~~~~~
// ^[注1] ^[注2]
其中调用了两个 system function ,分别是 malloc()
和 sizeof()
。
malloc():就是 momery allocate。
sizeof():顾名思义,就是用来获取东西的长度的。
注1:malloc()来的内存地址不能直接赋值给 list.data
的这个 pointer ,因为 list.data
是个 elemType pointer,而 malloc()
来的是一个 void pointer,所以我们要typecasting.
注2:114514就是要创建的元素的数量,114514就是114514个。
另外需要注意的是,动态分配不等于链式。因为动态分配分来的空间还是一整块连续的。动态只是体现在它的大小可以在运行的时候被决定。
知识共享署名-署名-非商业性使用-相同方式共享 4.0 国际许可协议