线性表-数据结构课件-1.pdf

第二章 线性表 第二章 目录 §2.1 线性表的定义 线性表 §2.2 线线性表的顺顺序表示和实现顺顺序表 Linear List §2.3 线性表的链式表示和实现 主讲：顾为兵 §2.4 线性表的应用举例多项式的表示与实现 §2.1 线性表的定义 §2.1 线性表的定义 线性表的逻辑结构： Linear_List=(D,S) ··· ·· a a a i-1 i i+1 D={a , a , … , a } · 1 2 n S={s} s={{a ,,a ,, a ,,a ,, … ,, a ,,a ,, … ,, a ,,a }} 11 22 22 33 ii--11 ii nn--11 nn 称称：： a 是a 的直接前趋 （有时简称前趋） i-1 i a 是a 的直接后继 （有时简称后继） i+1 i a1 a2 ·· ai-1 ai ai+1 ·· an-1 an · · 起始结点 终端结点 (表头结点,首元结点) (表尾结点) §2.1 线性表的定义 线性表抽象数据类型的定义（P19－20）: 线性表是n(n=0)个结点的有限序列; ADT List{ 数据对象：D={ a | a ∈ElemSet, i=1,2,...,n,n≥0 }