顺序表(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个。

另外需要注意的是,动态分配不等于链式。因为动态分配分来的空间还是一整块连续的。动态只是体现在它的大小可以在运行的时候被决定。

标签: none