数据结构线性表顺序表.ppt

顺序表----基本算法（10）求后继next=L.elem[i];在顺序表中查找元素cur_e，位序为ii=LocateElem(L,cur_e);cur_e是顺序表中元素，但不是最后一个元素便有直接后继next时间复杂度为O(1)第32页,共48页，2024年2月25日，星期天顺序表----经典算法分析算法插入删除基本操作移动元素移动元素平均移动次数时间复杂度O(n)O(n)最好情况在n+1处插入，不需移动删除第n个，不需移动第33页,共48页，2024年2月25日，星期天线性表应用举例例1：合并线性表例2：归并线性表第34页,共48页，2024年2月25日，星期天例1：合并线性表假设有两个集合A和B分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合A＝A∪B。——去掉重复元素第35页,共48页，2024年2月25日，星期天扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。问题分析：第36页,共48页，2024年2月25日，星期天1．从线性表LB中依次取得每个数据元素;2．依值在线性表LA中进行查访;3．若不存在，则插入之。GetElem(LB,i)→eLocateElem(LA,e,equal())ListInsert(LA,n+1,e)操作步骤：第37页,共48页，2024年2月25日，星期天GetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal()))ListInsert(La,++La_len,e);//La中不存在和e相同的数据元素，则插入之voidunion(ListLa,ListLb){La_len=ListLength(La);//求线性表的长度Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i++){}}//union第38页,共48页，2024年2月25日，星期天算法分析时间复杂度： O(ListLength(LA)*ListLength(LB))空间复杂度： O(1)第39页,共48页，2024年2月25日，星期天例2：归并线性表已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。——不去掉重复元素第40页,共48页，2024年2月25日，星期天LC中的数据元素或是LA中的数据元素，或是LB中的数据元素。则先设LC为空表，然后将LA或LB中的元素逐个插入到LC中。为使LC表按值非递减有序排列，可设两个整型变量i、j，分别指向LA和LB，比较i、j所指元素的大小，决定哪个元素插入LC。插入后，在LA或LB中顺序后移。问题分析：第41页,共48页，2024年2月25日，星期天voidMergeList(ListLa,ListLb,ListLc){//本算法将非递减的有序表La和Lb归并为Lc}//merge_listwhile((i=La_len)(j=Lb_len)){……//La和Lb均不空}while(i=La_len)//若La不空while(j=Lb_len)//若Lb不空InitList(Lc);//构造空的线性表Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);第42页,共48页，2024年2月25日，星期天GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}第43页,共48页，2024年2月25日，星期天while(i=La_len){//当La不空时