第2章线性表数据结构j（C描述）
第2章 线性表 数据结构（C描述）
目 录2.1线性表的定义及其运算2.2线性表的顺序存储结构2.33线性表的链式存贮结构本章作业
目 录 2.1 线性表的定义及其运算 2.2线性表的顺序存储结构 2.3 线性表的链式存贮结构 本章作业
2.1线性表的定义及其运算2.1.1线性表的定义1．线性表的定义线性表（linear list）是n（n≥0）个数据元素ay，a2，..a,组成的有限序列。其中n称为数据元素的个数或线性表的长度，当n=0时称为空表，n>0时称为非空表。通常将非空的线性表记为（aj，a，,a,），其中的数据元素a（1<i<n）是一个抽象的符号，其具体含义在不同情况下是不同的即它的数据类型可以根据具体情况而定，本书中，我们将它的类型设定为 elemtype，表示某一种具体的已知数据类型
2.1 线性表的定义及其运算 2.1.1线性表的定义 1． 线性表的定义 线性表（linear list）是n（n≥0）个数据元素a1，a2，.an组 成的有限序列。其中n 称为数据元素的个数或线性表的长 度，当n=0时称为空表，n>0时称为非空表。通常将非空的 线性表记为（a1，a2，.,an），其中的数据元素ai（1≤i≤n） 是一个抽象的符号，其具体含义在不同情况下是不同的， 即它的数据类型可以根据具体情况而定，本书中，我们将 它的类型设定为 elemtype，表示某一种具体的已知数据类 型
线性表的特征2.从线性表的定义可以看出线性表的特征：(1 有且仅有一个开始结点(表头结点)aj，它没有直接前驱，只有一个直接后继：(2)有且仅有一个终端结点(表尾结点)a，它没有直接后继，只有一个直接前驱；其它结点都有一个直接前驱和直接后继；3)4)元素之间为一对一的线性关系
2． 线性表的特征 从线性表的定义可以看出线性表的特征： （1 ） 有且仅有一个开始结点(表头结点)a1，它没 有直接前驱，只有一个直接后继; （2） 有且仅有一个终端结点(表尾结点)an，它没有 直接后继，只有一个直接前驱; （3） 其它结点都有一个直接前驱和直接后继； （ 4）元素之间为一对一的线性关系
线性表是一种典型的线性结构，用二元组表示为linear list-(A,R)其中A={a, I 1<i<n,n>0,a, Eelemtype}R=(r)r=[<a,ai+1> 1<i<n-1}对应的逻辑结构图如图2-1所示，aiLr图2-1线性表逻辑结构示意图
线性表是一种典型的线性结构，用二元组表示为： linear_list=(A,R) 其中 A={ai∣1≤i≤n,n≥0,ai∈elemtype} R={r} r={<ai ,ai+1 > ∣1≤i≤n-1} 对应的逻辑结构图如图2-1所示。 a1 a2 . an 图 2-1 线性表逻辑结构示意图