Microsoft PowerPoint - 数据结构耿国华高教版_第2章.pdfVIP

数据结构课件 西北大学计算机系 1 2013-1-22 第2章 线性表 l 2.1 线性表的概念及运算 l 2.2 线性表的顺序存储 l 2.3 线性表的链式存储 l 2.4 一元多项式的表示及相加 2 2013-1-22 2.1 线性表的概念及运算 l 2.1.1 线性表的逻辑结构 l 2.1.2 线性表的抽象数据类型定义 3 2013-1-22 线性表的定义 线性表 (Linear List)是由n (n≥0)个类型相同的 数据元素a ,a ,… ，a 组成的有限序列，记做 1 2 n （a ,a ,…，a ，a ，a ， …，a ）。 1 2 i-1 i i+1 n 数据元素之间是一对一的关系，即每个数据 元素最多有一个直接前驱和一个直接后继。 线性表的逻辑结构图为： 4 2013-1-22 线性表的特点 Ø 同一性：线性表由同类数据元素组成，每一 个a 必须属于同一数据对象。 i Ø有穷性：线性表由有限个数据元素组成，表 长度就是表中数据元素的个数。 Ø有序性：线性表中相邻数据元素之间存在着 序偶关系a ,a 。 i i+1 5 2013-1-22 2.1.2 线性表的抽象数据类型定义 l 抽象数据类型定义 ： ADT LinearList{ 数据元素：D={a | a ∈D , i=1,2,…，n n≥0 ，D 为某一数据对象} i i 0 0 关系：Ｓ＝｛a ,a | a , a ∈D ，i=1,2, …,n-1｝ i i+1 i i+1 0 基本操作： （1）InitList （L） 操作前提：L为未初始化线性表。 操作结果：将L初始化为空表。 （2 ）DestroyList(L) 操作前提：线性表L已存在。 操作结果：将L销毁。 （3 ）ClearList(L) 操作前提：线性表L已存在 。 操作结果：将表L置为空表。 ……… }ADT LinearList 6