结点 :结点是内存中一片由用户分配的储存空间,只有一个地址来表示它的存在,没有显式名称。
在学习顺序表时,一般不会去特别强调结点的概念,此概念往往在链表学习中涉及,但并不代表结点与顺序表无关,所以我特意把结点的概念放在此处以加深对顺序表的理解。
顺序表的概念定义:把逻辑上相邻的结点储存在物理位置上的相邻储存单元中,结点的逻辑关系由储存单元的邻接关系来体现
通俗来讲,顺序表就是把线性表中的所有元素按照其逻辑顺序,依次储存到从指定的储存位置开始的一块连续的储存空间中。
第一个元素的储存位置就是指定的储存位置,第 i+1 个元素的储存位置在第 i 个元素后面
顺序表的特性 占用连续的储存空间:由定义可知顺序表的储存空间必然连续,并且存储分配只能预先进行,一旦分配完毕,在操作过程中始终不变。随机访问特性:因为储存空间是连续的,知道第一个元素的地址(即储存空间的首地址)可以轻松访问储存的所有数据。每一个结点对应一个序号,由该序号可以直接算出结点的储存地址。 顺序表三要素 顺序表基地址顺序表长度顺序表总空间大小 顺序表结构体定义 typedef struct _Sqlist Sqlist;struct _Sqlist { int *elems; //顺序表基地址 int length; //顺序表长度 int size; //顺序表总空间大小};当然C语言提供了一种简单的写法(如下,以后以简单写法为例)。
typedef struct{ int *elems; //顺序表基地址 int length; //顺序表长度 int size; //顺序表总空间大小 }Sqlist;在某些书籍上,有这样定义顺序表的
#define MAXSIZE 100 typedef struct { int data[MAXSIZE];//存放顺序表元素的数组 int length;//存放顺序表的长度}Sqlist; 实际上这种定义已经为顺序表开辟了一部分内存空间,而前者需要使用函数来顺序表初始化。但实际上两种代码本质上是一样的,因为前者在顺序表的操作——初始化顺序表中的函数定义中,我们仍需要分配一片储存空间并且定义一个存放顺序表元素的数组;而后者相当于把这一步合并到了定义中。在学习过程而非实际开发中,我更倾向于前者,因为这更能反应顺序表的三要素,并且与链表代码书写风格相似,有利于感受线性表思想的共性。 结束我们现在已经成功定义顺序表了,但更重要的是它的操作,所以下一篇文章就来写这部分内容。