• 时间:
  • 分类:

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