研究分析数据结构第二章线性表.pptVIP

数据结构第二章 线性表 线性结构分类 直接访问型( direct access ) 顺序访问型(sequential access) 目录索引型(directory access) 线性结构分类 2.1 线性表的逻辑结构 定义：线性表(Linear List)是由n个数据元素的有限序列组成。其中数据元素的个数n 定义为表的长度。当 n=0 时称为空表，常常将非空的线性表(n0)记作： (a1，a2，…an) 这里的数据元素ai(1≤i≤n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。 性质：线性表（N , r）： 结点集N中有唯一的开始结点，它没有前驱，但有唯一的后继； 有限集N它存在唯一的终止结点，该结点有唯一的前驱而没有后继； 其它的结点皆称为内部结点，每一个内部结点既有一个唯一的前驱，也有一个唯一的后继； 线性表所包含的结点个数称为线性表的长度，长度为0的线性表称为空表； 线性表的关系r，简称前驱关系，应具有反对称性和传递性。 2.1 线性表的逻辑结构 例1、26个英文字母组成的字母表 (A，B，C、…、Z) 是一个线性表，其中的元素是单个字母字符。 例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况，可以用线性表的形式给出： （6，17，28，50，92，188） 更为复杂的线性表中，一个数据元素可以有若干个数据项(item)组成。在这种情况下，长把数据元素称为记录(record)，含有大量记录的线性表又称为文件(file)。 2.1 线性表的逻辑结构 2.1 线性表的逻辑结构 以上几个例子都是线性表的例子，都满足线性表的性质。 线性表是一种典型的线性结构。 数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。 抽象数据类型的定义为：P19 线性表类模板 templateclass ELEM class list //线性表类模板list，模板参数ELEM { //1. 线性表的取值类型： //元素的类型为ELEM，是本list类模板的模板参数ELEM。 //本线性表用的最大长度为Max_length； //2. 名字空间，使用变量访问线性表的方法： //用curr ++或 curr--控制线性表游标curr的前后游走。 //用公共变量curr_len指示线性表的尾部， //并导出表的当前长度，…等。 // 3. 运算集：请参看下面的成员函数 private: //私有变量，线性表的存储空间 //Max_length线性表的最大长度 public: int curr_len; //线性表的当前长度 int curr; //线性表的当前指针 list(); // 创建一个空的新线性表 2.1 线性表的逻辑结构 算法2.1 例2-1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。 [初值] 获取线性表LA和LB [合并线性表] 对于LB中的每一个元素x做如下操作： 若(x不属于LA） 则将x插入到LA的末尾 [算法结束] 2.1 线性表的逻辑结构 算法2.2 例2-2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。 此问题的算法： [初值] 获取线性表LA和LB，并构造空线性表LC [选择插入元素] 对于线性表LA和LB，都从其第一个元素开始做如下操作直到其中一个线性表元素全部遍历完毕： 若 （LA的元素a=LB的元素b） 则 将元素a插入到LC的末尾，并选择LA中的下一个元素a 否则 将元素b插入到LC的末尾，并选择LB中的下一个元素b [补充剩下的元素] 若 （LA还有剩余元素） 则 将LA的剩余元素全部插入到LC末尾 若 （LB还有剩余元素） 则 将LB的剩余元素全部插入到LC末尾 [算法结束] 2.1 线性表的逻辑结构 void MergeList(List La, List Lb, List Lc){ InitList(Lc); i=j=1;k=0; La_len=ListLength(La); Lb_len=ListLength(Lb); while ( (i=La_len) (j=Lb_len) ) { GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai=bj) { ListInsert(Lc,