第二章线性表
第二章 线 性 表
2.1线性表的逻辑结构 2.2线性表的顺序表示和实现 2.3线性表的链式表示和实现 2.4顺序表和链表的比较
2．1 线性表的逻辑结构 2．2 线性表的顺序表示和实现 2．3 线性表的链式表示和实现 2．4 顺序表和链表的比较
2.1线性表的逻辑结构 2.1,1线性表的定义 1.线性表的定义 线性表(linear list)是n(n≥0)个类型相同数据元 素a1,a2,.an组成的有限序列
2．1 线性表的逻辑结构 2.1.1 线性表的定义 1． 线性表的定义 线性表（linear list）是n（n≥0）个类型相同数据元 素a1，a2，…an组成的有限序列
!其中n称为线性表的长度，当O时称为空表： 4通常将非空的线性表记为(a,a2,,a)，数 据元素a,(I≤i≤n)的数据类型可以根据具体情 况而定； 4a.1(2≤i≤n)是a,的直接前驱，有且只有一个： a+(1≤i≤n-1)a的直接后继，有且只有一个； 所有元素的性质是相同的：
其中n 称为线性表的长度，当n=0时称为空表； 通常将非空的线性表记为（a1，a2，…,an），数 据元素ai（1≤i≤n）的数据类型可以根据具体情 况而定； a i-1 (2≤i≤n)是a i 的直接前驱，有且只有一个； a i+1(1≤i≤n-1)a i的直接后继，有且只有一个； 所有元素的性质是相同的；
2.线性表的逻辑结构特征 生有且仅有一个开始结点（表头结点）a,它没有直接 前驱，只有一个直接后继 牛有且仅有一个终端结点（表尾结点）a。,它没有直接 后继，只有一个直接前驱 !其它结点都有一个直接前驱和直接后继 半元素之间为一对一的线性关系
2． 线性表的逻辑结构特征 有且仅有一个开始结点(表头结点)a1，它没有直接 前驱，只有一个直接后继 有且仅有一个终端结点(表尾结点)an，它没有直接 后继，只有一个直接前驱 其它结点都有一个直接前驱和直接后继 元素之间为一对一的线性关系