数据结构.ppt

西南大学电子信息工程学院第二章线性表西南大学电子信息工程学院 线性表的类型定义西南大学电子信息工程学院线性表的定义线性表的定义定义定义 n n( (??0 0) )个数据元素的有限个数据元素的有限序列序列,记作,记作( (a a 1 1 , a a 2 2 , …a i-1 ,a i ,a i+1 ,..., a a n n) ) a a i i是表中数据元素, 是表中数据元素, n n 是表长度。是表长度。线性表的特点线性表的特点除第一个元素外,其他每一个元素有一个且仅有一个除第一个元素外,其他每一个元素有一个且仅有一个直接前驱直接前驱。。除最后一个元素外,其他每一个元素有一个且仅有一个除最后一个元素外,其他每一个元素有一个且仅有一个直接后继直接后继。。 a i-1称为 a i的直接前驱 a i+1 称为 a i的直接后继定义西南大学电子信息工程学院线性结构的特点在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外,集合中的每个数据元素均只有一个前驱除最后一个外,集合中的每个数据元素均只有一个后继西南大学电子信息工程学院线性表举例例英文字母表( A,B,C, …..Z) 是一个线性表例计算机拥有量( 6, 17 , 28 , 50 , 92 , 188 ) 例学号姓名年龄 001 张三 18 002 李四 19 ………………数据元素文件数据项西南大学电子信息工程学院线性表特征( a 1 ,a 2, ……..,a n) 线性表中的元素具有相同属性, 同构同构元素个数 n:表长度表长度 n=0 空表非空线性表中每个元素都有一个确定位置位置称a i为第 i个元素, i为a i的的位序位序相邻元素之间存在序偶关系, 1< i<n 时 ai的直接前驱前驱是ai-1 ,a1 无直接前驱 ai的直接后继后继是 ai+1 ,an 无直接后继操作: 访问,插入,删除访问,插入,删除西南大学电子信息工程学院线性表的 ADT 讲解: P19 注意:数据结构的基本运算,不是它的全部运算。每一个基本运算在实现时可根据不同的存储结构派生出一系列相关的运算来。例:线性表的查找在链式存储结构中还会有按序号查找例:插入运算,可以是将新元素x插入到适当位置上建议:掌握了某一数据结构上的基本运算后,其它的运算可以通过基本运算来实现,也可以直接去实现。西南大学电子信息工程学院例 2-1 Void union(List &La,List Lb){ // 将所有在线性表 Lb 中但不在 La 中的数据元素插入到 La 中 La_len = ListLength(La ); Lb_len = ListLength(Lb ); for(i=1;i<= Lb_len;i ++){ GetElem(Lb,i,e ); if(!LocateElem(La,e,equal )) ListInsert(La,++La_len,e ); } }//union 西南大学电子信息工程学院例 2-2 Void MergeList(List La,List Lb,List & Lc ){ // 已知线性表 La 和 Lb 中的数据元素按值非递减排列// 归并 La 和 Lb 得到新的线性表 Lc , 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,++k,ai ); ++i);} else{ListInsert(Lc,++k,bj ); ++j;} } ..... 后续西南大学电子信息工程学院 while(i<= La_len ){ Getelem(la,i++,ai ); ListInsert(lc,++k,ai ); } while(j<= Lb_len ){ Getelem(lb,j++,bj ); ListInsert(lc,++k,bj ); } } // MergeList