数据结构重学日记（四）线性表和顺序存储

概念

线性表属于线性结构，是由零个或多个具有相同特性的数据元素组成的有限序列。

数据结构分为逻辑结构和存储结构，逻辑结构分为集合，线性结构，树形结构和网状结构四种。线性表就属于线性结构。

例如买奶茶排队的人，他们都是为了买奶茶，而且除了第一个和最后一个人之外，所有人都是前后边各有一个人。

其中，表中第一个元素成为表头元素，最后一个元素成为表尾元素。

记录和文件

在稍微复杂的线性表中，一个数据元素可以由若干个数据项组成，在这种情况下常把数据元素称为记录，含有大量纪录的线性表又称文件。

例如学生信息登记表中，每个学生的情况为一个记录。

---

线性表的顺序表示和实现

线性表的顺序是指用一组地址连续的存储单元（比如 C 语言里的数组），依次存储线性表中的数据元素。即顺序存储。

顺序存储的线性表叫做顺序表，也称静态表。

线性表

假设有如上图的具有 个元素的线性表，它们在存储器中占据连续的存储空间，每个数据元素占据 d 个存储单元，那么计算其中一个数据元素 的存储位置公式即为：

Loc() = Loc() + Loc(i - 1) * d。

其中 Loc() 是线性表的第一个数据元素的存储位置，通常称作线性表的起始位置或基地址。

线性表的这种存储方式称为线性表的顺序存储结构或顺序映像，只要确定了存储线性表的基地址，其中的任一数据元素都可以随机存取，所以顺序存储结构是一种随机存取的存储结构。

静态实现

静态实现即静态分配存储空间。即在定义变量时就分配存储单元并保持不变，直至整个程序结束。

先来个栗子：

#define MaxSize 50
# 定义线性表的最大长度

typedef int ElemType;
# 定义表中元素类型是 int

typedef struct {
# 顺序表的类型定义 数组

    ElemType data[MaxSize];
    # 创建最大存储容量为 50 的 int 型的数组
    # data 为数组名，线性表的基地址

    int length;  
    # 顺序表当前的长度

    int listsize;           
    #当前分配的存储容量

}SqList;

由上边的例子可以看出，静态分配线性表的存储空间，需要先确定以下三点：

• 存储空间的起始位置
• 顺序表的最大存储容量
• 顺序表当前的长度

动态实现

动态实现是在程序运行中，通过动态语句分配存储空间的大小。

栗子：

typedef int Elemtype;
typedef struct{
    ElemType *data;
    # 指示动态分配数组的指针
   # 不再开辟数组，仅设置指针，指向将要的开辟的存储空间

    int MaxSize,length;
    # 数组的最大容量和当前长度
}SeqList

# 动态分配存储空间 
#define InitSize 100
SeqList L;
L.data = (ElemType*)malloc((sizeof(ElmeType)) * InitSize
# malloc 用来分配存储空间
# sizeof  获取 ElemType 的大小
# InitSize = 100 表示 100 个数据量的存储空间

顺序存储