【数据结构（6）】2.4 线性表的顺序表示和实现_空的顺序表示意图

作者：笔触狂放9 | 2024-08-01 19:51:33

踩

空的顺序表示意图

文章目录

1. 线性表的顺序存储表示
- 顺序表的存储结构类型定义
- 顺序表示意图
2. 顺序表的基本操作的实现
3. 顺序表小结

在计算机内，线性表分为顺序存储结构和链式存储结构

1. 线性表的顺序存储表示

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

顺序存储定义

把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
逻辑上相邻的元素，在物理位置上也相邻。

线性表的第一个数据元素 a1 的存储位置，称为线性表的起始位置或基地址

顺序存储结构

例如：线性表（1，2，3，4，5）的存储结构：

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

知道某个元素在什么位置，以及元素的数据类型，那么下一个元素在什么位置就很容易算出来了。

如果每个元素占用 8 个存储单元，ai 存储位置是 2000 单元，那么 ai+1 的存储位置就是 2008单元。
假设线性表的每个元素占 t 个存储单元，则第 i + 1 个数据元素的存储位置和第 i 个数据元素的存储位置之间满足关系：
- LOC(ai+1) = LOC(ai) + t
由此，所有数据元素的存储位置均可由第一个数据元素的存储位置得到：
- LOC(ai) = LOC(a₁) + (i - 1) x t

线性表的特点

以物理位置相邻表示逻辑关系。
任一元素均可随机存取（优点）。

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

如何让线性表可长可短？

额外找一个变量来表示线性表的长度。

线性表的类型定义模板

用这个就可以修改成各种顺序存储结构的类型定义

#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量

typedef struct
{
        int ElemType elem[LIST_INIT_SIZE];
        int length;//当前长度，存储线性表中元素的个数

}SqList;
1
2
3
4
5
6
7
8

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

多项式只存储非 0 项的系数和指数，每一项都要存储系数和指数两个信息。

#define MAXSIZE 100 //多项式可能达到的最大长度

typedef struct //多项式非0项的定义
{
        float p;//存储非0项的多项式的系数
        int   e;//存储非0项的多项式的指数
}polynomial;

typedef struct
{
        Polynomial* elem ;//存储空间的首元素地址
        int length;//多项是中当前项的个数

}SqList;//多项式的顺序存储结构类型为SqList
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

#define MAXSIZE 100 //图书表可能达到的最大长度

typedef struct //图书信息定义
{
        char  no[20]  ;//图书ISBN
        char  name[50];//图书名
        float price   ;//图书价格
}BOOK;

typedef struct
{
        BOOK* elem ;//存储空间的首元素地址
        int length;//图书表中当前图书的个数

}SqList;//图书表的顺序存储结构类型为SqList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

顺序表示意图

就像 int a一样，用 int 来定义a，a 是 int 类型的。
SqList是自定义的顺序表类型，SqList L就能将 L 定义成一个顺序表。

typedef struct
{
        ElemType* elem ;
        int length;

}SqList;//定义的顺序表类型为SqList

int main()
{
        SqList L= {0};//定义并初始化一个SqList类型的的顺序表L。
}
1
2
3
4
5
6
7
8
9
10
11