2线性表(福建教师招考信息技术算法跟程序部分).ppt

百度风云榜整理 第二章 线形表 1、线性表(Linear List) ： 定义： 由n(n≧0)个数据元素(结点)a1，a2， …an组成的有限序列。记作： L=(a1，a2，…ai-1，ai，ai+1，…an) 其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n0) 这里的数据元素ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。 例1、26个英文字母组成的字母表 （A，B，C、…、Z） 例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。 （6，17，28，50，92，188） 例3、学生健康情况登记表如下： 例4、一副扑克的点数 （2，3，4，…，J，Q，K，A） 线性表 —— 元素及元素之间的关系为线性 线性： 线性表的类型定义 抽象数据类型线性表的定义 ADT List GetElem( L, i, e ) 初始条件：线性表L已存在， 1≤i≤LengthList(L) 操作结果：用e返回L中第i个元素的值。 LocateElem( L, e, compare( ) ) 初始条件：线性表L已存在，compare( ) 是元素判定函数。 操作结果：返回L中第1个与e满足关系 compare( )的元素的位序。若这样的元素不存在，则返回值为0。 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无定义。 ListTraverse(L, visit( )) 初始条件：线性表L已存在。 操作结果：依次对L的每个元素调用函数 visit( )。一旦visit( )失败，则操作失败。 ADT List { 加工型操作 } 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个元素之前插入新的元素e，L的长度增1。 ListDelete(L, i, e) 初始条件：线性表L已存在且非空，1≤i≤LengthList(L) 操作结果：删除L的第i个元素，并用e 返回其值，L的长度减1。 } ADT List 举例 假设线性表L=(23,56,89,76,18),i=3,x=56,y=88,则对L的一组操作及结果如下： ListLength( L ) //所得结果为5 GetElem( L, i, e ) //所得结果为89 PriorElem( L, x, pre_e ) //所得结果为23 NextElem( L, x, next_e ) //所得结果为89 LocateElem( L, x, equal ) //所得结果为2 ListInsert( L, i, y ) //所得结果为(23,56,88,89,76,18) ListDelete(L, i+1, e) /所得结果为(23,56,88,76,18) 89 如何实现线性表的其它操作 例2-1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。 设计思想： 扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。 分下列三步进行： 1．从线性表LB中依次取得每个数据元素; 2．依值在线性表LA中进行查访; 3．若不存在，则插入之。 A=A∪B 算法描述： // 将所有在线性表Lb中但不在La中的数据元素插入到La中 void Union( List La，List Lb) { // 求线性表的长度 La-len = ListLength(La); Lb-len = ListLength(Lb); for( i=1; i =