顺序表的概念及定义

顺序表

结点的概念

结点 :结点是内存中一片由用户分配的储存空间,只有一个地址来表示它的存在,没有显式名称。

在学习顺序表时,一般不会去特别强调结点的概念,此概念往往在链表学习中涉及,但并不代表结点与顺序表无关,所以我特意把结点的概念放在此处以加深对顺序表的理解。

顺序表的概念

定义:把逻辑上相邻的结点储存在物理位置上的相邻储存单元中,结点的逻辑关系由储存单元的邻接关系来体现

通俗来讲,顺序表就是把线性表中的所有元素按照其逻辑顺序,依次储存到从指定的储存位置开始的一块连续的储存空间中。

第一个元素的储存位置就是指定的储存位置,第 i+1 个元素的储存位置在第 i 个元素后面

顺序表的特性

  • 占用连续的储存空间:由定义可知顺序表的储存空间必然连续,并且存储分配只能预先进行,一旦分配完毕,在操作过程中始终不变。
  • 随机访问特性:因为储存空间是连续的,知道第一个元素的地址(即储存空间的首地址)可以轻松访问储存的所有数据。每一个结点对应一个序号,由该序号可以直接算出结点的储存地址。

顺序表三要素

  • 顺序表基地址
  • 顺序表长度
  • 顺序表总空间大小

顺序表结构体定义

1
2
3
4
5
6
typedef struct _Sqlist Sqlist;
struct _Sqlist {
int *elems; //顺序表基地址
int length; //顺序表长度
int size; //顺序表总空间大小
};

当然C语言提供了一种简单的写法(如下,以后以简单写法为例)。

1
2
3
4
5
6
typedef struct{
int *elems; //顺序表基地址
int length; //顺序表长度
int size; //顺序表总空间大小

}Sqlist;

在某些书籍上,有这样定义顺序表的

1
#define MAXSIZE 100
1
2
3
4
typedef struct {
int data[MAXSIZE]; //存放顺序表元素的数组
int length; //存放顺序表的长度
}Sqlist;
  • 实际上这种定义已经为顺序表开辟了一部分内存空间,而前者需要使用函数来顺序表初始化。
  • 但实际上两种代码本质上是一样的,因为前者在顺序表的操作——初始化顺序表中的函数定义中,我们仍需要分配一片储存空间并且定义一个存放顺序表元素的数组;而后者相当于把这一步合并到了定义中。
  • 在学习过程而非实际开发中,我更倾向于前者,因为这更能反应顺序表的三要素,并且与链表代码书写风格相似,有利于感受线性表思想的共性。

结束

我们现在已经成功定义顺序表了,但更重要的是它的操作,所以下一篇文章就来写这部分内容。