9. 线性表的顺序表示和实现（1）

本节主要介绍顺序表的表示和实现。
本文部分ppt、视频截图来自：[青岛大学-王卓老师的个人空间-王卓老师个人主页-哔哩哔哩视频]

1. 线性表的顺序表示

在计算机内，线性表有两种基本存储结构：顺序存储结构 和 链式存储结构。

1.1 线性表的顺序表示

线性表的顺序表示又称为顺序存储和结构或顺序映像。

• 顺序存储定义

顺序存储结构：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构

• 顺序存储结构

线性表顺序存储结构占用一片连续的存储空间。知道某个元素的存储位置就可以计算其他元素的存储位置。

• 顺序表中元素存储位置的计算

顺序表中每个元素的位置都可以由某个数据元素的位置计算得到。（随机存取，查找时间复杂度为O(1)）

某顺序表如上图所示，如果某个元素占用8个存储单元，a_i存储位置是2000单元，则a_i+1存储位置是？

a_i存储位置是2000单元，每个元素占用8个存储单元，即a_i占用2000-2007单元，所以a_i+1是从 2008 号开始存储的。

1.2 线性表顺序存储结构的实现

• 顺序表的特点

• 顺序表的顺序存储表示

可以将用一个变量表示顺序表的长度属性，将顺序表定义如下：

#define LIST_INIT_SIZE 100  //线性表存储空间的初始分配量
typedef struct {ElemType elem[LIST_INIT_SIZE];int length; //当前长度
}SqList;

• 多项式的顺序存储结构类型定义

对以上多项式，只用存储非0项的系数和指数，可以定义如下：

#define MAXSIZE 1000  //多项式可能达到的最大长度
typedef struct {      //多项式非0项的定义float p;          //系数int e;            //指数
}Polynomial;typedef struct {Polynomial *elem; //存储空间的基地址int length;       //多项式中当前项的个数
}SqList;             //多项式的顺序存储结构类型为SqList

• 图书表的顺序存储结构类型定义