数据结构课件ppt第二章1.ppt

第二章 线性表;2.1 线性表的类型定义;2.1 线性表的类型定义;线性表的概念;线性结构的基本特征为:; 例如： 英文字母表(A, B, …, Z)就是一个简单的线性表，表中的每一个英文字母是一个数据元素， 每个元素之间存在唯一的顺序关系，如在英文字母表字母B的前面是字母A， 而字母B的后面是字母C。 在较为复杂的线性表中，数据元素(data elements)可由若干数据项组成，如学生成绩表中，每个学生及其各科成绩是一个数据元素，它由学号、姓名、各科成绩及平均成绩等数据项(item) 组成， 常被称为一个记录(record) ，含有大量记录的线性表称为文件(file)。;表2-1 车辆登记表 ; 线性表的特点可概括如下：  同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。  有穷性：线性表由有限个数据元素组成， 表长度就是表中数据元素的个数。  有序性：线性表中相邻数据元素之间存在着序偶关系ai, ai+1。  由此可看出，线性表是一种最简单的数据结构，因为数据元素之间是由一前驱一后继的直观有序的关系确定；线性表又是一种最常见的数据结构，因为矩阵、数组、字符串、堆栈、 队列等都符合线性条件。 ;抽象数据类型线性表的定义如下：; 基本操作：; InitList( L ) ; 结构销毁操作;1. ListEmpty( L );ListEmpty( L ) ;ListLength( L );PriorElem( L, cur_e, pre_e ) ;NextElem( L, cur_e, next_e );GetElem( L, i, e );LocateElem( L, e, compare( ) ); ListTraverse(L, visit( ));加工型操作 ;ClearList( L );PutElem( L, i, e ); ListInsert( L, i, e );ListDelete(L, i, e);利用上述定义的线性表 可以实现其它更复杂的操作; 假设:有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。 现要求一个新的集合A＝A∪B。; 要求对线性表作如下操作： 扩大线性表 LA，将存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。;1．从线性表LB中依次察看每个数据元素;; GetElem(Lb, i, e); // 取Lb中第i个数据元素赋给e if (!LocateElem(La, e, equal( )) ) ListInsert(La, ++La_len, e); // La中不存在和 e 相同的数据元素，则插入之; 已知一个非纯集合 B，试构造一个纯集合 A，使 A中只包含 B 中所有值各不相 同的数据元素。;集合 B;2．从线性表LB中依次察看每个数据元素;;void union(List La, List Lb) { La_len=ListLength(La); Lb_len=ListLength(Lb); } // union;若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即 ai≥ai-1 或 ai≤ai-1(i = 2,3,…, n)，则称该线性表为有序表(Ordered List)。;例2-3;例如： （2，3，3，5，6，6，6，8，12）;void purge(List La, List Lb) { InitList(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); // 求线性表的长度 for (i = 1; i = Lb_len; i++) { } } // purge ;例2-4 有序表的合并;void MergeList(List La, List Lb, List Lc) { // 本算法将非递减的有序表 La 和 Lb 归并为 Lc ; while (i = La_len) { // 当La不空时 GetElem(La, i++, ai); ListInsert(Lc, ++k, ai); } // 插入 La 表中剩余元素;课堂练习;2. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较