数据结构 (吴跃)-ch02-1.pptVIP

第2章 线性表（linear_list） 主要内容 线性表基本概念及其顺序和链式存储结构 栈的概念和相关运算及其顺序和链式存储结构 队列的概念、相关运算及几种常见的队列 数组的定义、表示、实现和应用 线性表的几种典型应用 2.1.1 线性表的定义 线性表的抽象数据类型定义 2.1.1 线性表的定义 Data_Structure ＝（D，L，S，O） 基本操作 O：是在逻辑结构上对数据结构或数据元素的一组基本运算，与具体实现无关； 可利用给定的基本操作构造更复杂的运算 如： 线性表初始化； 求线性表的长度； 按值查找；插入元素操作； 删除元素操作；等 例1：合并线性表 问题：集合A和B分别用两个线性表LA和LB表示，求A∪B并用线性表LA表示。 算法设计： 思想：从LB中逐一取出元素,判该元素是否在LA中,若不在则将该元素插入到LA中。 细化：到实现程度 逐一：从第一个到最后一个,计数型循环,前提是需要知道元素个数 如何取出第i个数据元素bi？ 如何判断bi是否已在A中？ 如果不在A中，怎样实现将bi插入？ 例：合并线性表算法 Status List_Union (ListPtr La, ListPtr Lb){ ElemType elem; /* 存放从Lb中取出的元素*/ Status status; /*状态代码*/ int i, j, len = List_Size(Lb); /*len存放Lb的元素个数*/ for (i=1; i=len; i++){ List_Retrieve(Lb, i, elem); /*取出Lb中第i个数据元素*/ status = List_Locate(La,elem,j); /*判它是否在La中*/ if(status!= success){ /*如果不在*/ status = List_Insert(La,1,elem); /*插入到第一个位置*/ if(status!= success) break; /*插入失败则退出*/ } } return status; } 例：合并线性表算法分析 如何分析？设m和n分别表示La和Lb的长度（元素个数） 先确定基本操作 ----判断是否在La中 基本操作执行次数是否确定？ 确定：次数 不确定： 最好/最坏/平均情况分析 本例不确定 最好情形分析 B为A的前面部分元素:1+2+…+n= (n+1)*n/2 最坏情形分析 B∩A为空:m+(m+1)…+(m+n-1)= n*m+(n-1)*n/2 优化？选数据元素个数少的作为Lb 例2：合并有序表 问题：已知线性表La和Lb中元素分别按非递减顺序排列，现要求将它们合并成一个新的线性表Lc，并使得Lc中元素也按照非递减顺序排列。 分析：线性表Lc初始为空。依次扫描La和Lb中的元素，比较当前元素的值，将较小值的元素插入Lc的表尾之后，如此反复，直到一个线性表扫描完毕，然后将未完的那个线性表中余下的元素逐个插入到Lc的表尾之后 细化：现有操作可实现否？ Status List_Merge (ListPtr La, ListPtr Lb, ListPtr Lc){ ElemType elem1, elem2; status = List_Init(Lc); int i=1, j=1, k=1; /*i, j, k分别用于指示La, Lb, Lc中当前元素*/ int n = List_Size(La)，m = List_Size(Lb); while(i=n j=m){ /*两个表都还未处理完*/ List_Retrieve(La,i,elem1); List_Retrieve(Lb,j,elem2); if(elem1elem2){ status = List_Insert(Lc,k,elem1); i=i+1; } else{ status = List_Insert(Lc,k,elem2); j=j+1; } k=k+1; } while(i=n){ /*表La都还未处理完*/