内容发布更新时间 : 2024/5/19 15:45:30星期一 下面是文章的全部内容请认真阅读。

第二章

2.1线性表的概念及其抽象数据类型的定义

2.1.1 线性表的逻辑结构 线性表的定义

线性表是n个类型相同的数据元素的有限序列，对n>0,除第一个元素无直接前驱，最后一个元素无直接后继外，其余的每个数据元素只有一个直接前驱和一个直接后继。 线性表的特点：

1）同一性：线性表有同类元素数据组成，每一个ai必须属于同一数据类型。

2）有穷性：线性表由有限个数据元素组成，表长就是表中数据元素的个数。

3）有序性：线性表中相邻数据元素之间存在着序偶关系

?ai,ai?1?。

2.1.2线性表的抽象数据类型定义

抽象数据类型定义：见课本P38~P39。

2.2线性表的顺序存储

2.2.1线性表的顺序存储结构 顺序存储结构的定义

线性表的顺序存储结构是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑上相邻的数据元素存储

在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构的线性表通常称为顺序表。

将线性表归纳为：关系线性化，节点顺序存。

假定顺序表中有n个元素，每个元素占k个单元，第一个元素的

(a1)，则可通过如下公式计算出第i个元素的地址地址为LocLoc(ai)：

Loc(ai)?Loc(a1)?(i?1)?k

其中，Loc(a1)称为基地址。 线性存储结构的C语言定义

#define MAXSIZE 100 typedef struct {

ElemType elem[MAXSIZE]; /*ElemType 可为int，char等*/

int last; /*记录线性表中最后一个元素在数组elem[ ]中的位置(下标值)*/

}Seqlist;

上述为定义一个结构体，结构名为Seqlist。

知识延伸（typedef）（C课本P 326~P330用typedef声明新类型名）2.2.2 线性表顺序存储结构上的基本运算 线性表的基本运算

1、查找操作 2、插入操作 3、删除操作 4、顺序表合并算法

线性表顺序存储结构的优缺点分析

2.3 线性表的链式存储

链表定义：采用链式存储结构的线性表称为链表。 链表的分类：

1）按实现角度看：链表可分为动态链表和静态链表。 2）按链接方式的角度看：链表可分为单链表、循环链表和双链表。 2.3.1 单链表