数据结构第二章-线性表.pptVIP

Strategic Architect Forum 2004 第二章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 线性结构特点： 在数据元素的非空有限集中： 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前驱 除最后一个外，集合中的每个数据元素均只有一个后继 2.1 线性表的类型定义 线性表(Linear_List) ：简称表，由n( n≧0 )个数据元素(结点)a1，a2， …an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n0)记作： (a1, … ,ai-1 , ai , ai+1 , … , an) 这里的数据元素ai( 1≦i≦n )只是一个抽象的符号，其具体含义在不同的情况下可以不同。 举例 例1-1、26个英文字母组成的字母表 （A，B，C、…、Z） 例1-2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。 （6，17，28，50，92，188） 例1-3、一副扑克的点数 （2，3，4，…，J，Q，K，A） 举例 例1-4、学生健康情况登记表如下： 举例 从以上例子可看出线性表的逻辑特征是： 非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai ( 2≦i≦n-1 )都有且仅有一个直接前趋ai-1和一个直接后继ai+1。 线性表是一种典型的线性结构。 数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。 抽象数据类型的定义为： ADT List { 数据对象：D＝{ai|ai∈ElemSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ai-1 ,ai|ai-1,ai,∈D, i=2,...,n } 基本操作：{结构初始化}　　InitList( L )　　　操作结果：构造一个空的线性表 L 。 {销毁结构}　　DestroyList( L )　　　初始条件：线性表 L 已存在。　　　操作结果：销毁线性表 L 。 {引用型操作} ListEmpty( L )　 初始条件：线性表L已存在。　 操作结果：若L为空表，则返回TRUE，否则返回 FALSE ListLength( L )　　初始条件：线性表 L 已存在。　　操作结果：返回 L 中元素个数。 PriorElem( L, cur_e, pre_e )　　初始条件：线性表 L 已存在。　　操作结果：若 cur_e 是 L 中的数据元素，则用 pre_e 返回它的前驱，否则操作失败，pre_e 无定义。 NextElem( L, cur_e, next_e )　　初始条件：线性表 L 已存在。　　操作结果：若 cur_e 是 L 中的数据元素，则用 next_e 返回它的后继，否则操作失败，next_e 无定义。 GetElem( L, i, e )　初始条件：线性表 L 已存在，1≤i≤LengthList(L)。　操作结果：用 e 返回 L 中第 i 个元素的值。 LocateElem( L, e, compare( ) )　初始条件：线性表 L 已存在，compare( ) 是元素判定函数 　操作结果：返回 L 中第1个与 e 满足关系 compare( ) 的元素的位序。若这样的元素不存在，则返回值为0。 ListTraverse(L, visit( ))　初始条件：线性表 L 已存在，visit( ) 为元素的访问函数。　操作结果：依次对 L 的每个元素调用函数 visit( )。一旦 visit( ) 失败，则操作失败。 {加工型操作} ClearList( L )　　初始条件：线性表 L 已存在。　　操作结果：将 L 重置为空表。 PutElem( L, i, e )　　初始条件：线性表L已存在，1≤i≤LengthList(L)。　　操作结果：L 中第 i 个元素赋值同 e 的值。 ListInsert( L, i, e )　　初始条件：线性表 L 已存在，1≤i≤LengthList(L)+1。　　操作结果：在 L 的第 i 个元素之前