第一章线性表 线性表是一种最简单的线性结构
线性表是一种最简单的线性结构
线性结构的基本特征 线性结构是 个数据元素的有序(次序)集 1.集合中必存在唯一的一个“第一元素”; 2.集合中必存在唯一的一个“最后元素” 3.除最后元素在外,均有唯一的后继; 4.除第一元素之外,均有唯一的前驱
线性结构的基本特征: 1．集合中必存在唯一的一个“第一元素”； 2．集合中必存在唯一的一个 “最后元素” 3．除最后元素在外，均有 唯一的后继； 4．除第一元素之外，均有 唯一的前驱。 线性结构 是 一个数据元素的有序（次序）集
21线性表的类型定义 22线性表类型的实现 顺序映象 23线性表类型的实现 链式映象 24一元多项式的表示
2.1 线性表的类型定义 2.3 线性表类型的实现 ⎯ 链式映象 2.4 一元多项式的表示 2.2 线性表类型的实现 ⎯ 顺序映象
线性表的类型定义
抽象数据类型线性表的定义如下 ADT List 数据对象 D={a1a1∈ Elem Set,i=1,2,…,n,n>0} {称n为线性表的表长 称n=0时的线性表为空表。} 数据关系 R1={<a1,a1>a1,a1∈D,i=2,…,n} 设线性表为(a1,a2,,a1,,a 称为a1在线性表中的位序。}
抽象数据类型线性表的定义如下： ADT List { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } {称 n 为线性表的表长; 称 n=0 时的线性表为空表。} 数据关系： R1＝{ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n } {设线性表为 (a1，a2 , . . . ，ai，. . . ，an ), 称 i 为 ai 在线性表中的位序。}