资源描述：
《第3讲 线性表的顺序存储结构ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第3讲线性表主讲人：陈红丽利用线性表类型实现其它更复杂的操作例2-2例2-3例2-1假设:有两个集合A和B分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合A＝A∪B。例2-1要求对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。上述问题可演绎为：1．从线性表LB中依次查看每个数据元素;2．依值在线性表LA中进行查访;3．若不存在，则插入之。GetElem(LB,i)→eLocateElem(LA,e,equal())ListInsert(LA,n+1,e
2、)(n表示线性表LA当前长度)操作步骤：重复上述三步直至LB为空表为止。GetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal()))ListInsert(La,++La_len,e);//La中不存在和e相同的数据元素，则插入之La_len=ListLength(La);//求线性表的长度Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){}//for}//unionvoidunion(List&La,ListLb){已知一个非纯集合B，试构造一个纯集合A
3、，使A中只包含B中所有值各不相同的数据元素。仍选用线性表表示集合例2-2集合B集合A从集合B取出物件放入集合A要求集合A中同样物件不能有两件以上因此，算法的策略应该和例2-1基本相同,差别仅在于集合A的初始状态是“空集”voidunion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);}//unionGetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal()))ListInsert(La,++La_len,e);//La中
4、不存在和e相同的数据元素，则插入之for(i=1;i<=Lb_len;i++){}//forInitList(La);//构造(空的)线性表La若线性表中的数据元素相互之间可以比较，并且数据元素在表中依值非递减或非递增有序排列，即ai≥ai-1或ai≤ai-1(i=2,3,…,n)，则称其为有序表(OrderedList)。试改变结构，以有序表表示集合。例如：（2，3，3，5，6，6，6，8，12）对集合B而言，值相同的数据元素必定相邻对集合A而言，数据元素依值从小至大的顺序插入因此，数据结构改变了，解决问题的策略也相应要改变。voidpurge(Lis
5、t&La,ListLb){InitList(La);La_len=ListLength(La);Lb_len=ListLength(Lb);//求线性表的长度for(i=1;i<=Lb_len;i++){}//for}//purgeGetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(ListEmpty(La)
6、
7、!equal(en,e)){ListInsert(La,++La_len,e);en=e;}//La中不存在和e相同的数据元素，则插入之则归并两个“其数据元素按值非递减有序排列”的有序表LA和LB，求得有序表LC也具有同样特性。
8、设La=(a1,…,ai,…,an),Lb=(b1,…,bj,…,bm)Lc=(c1,…,ck,…,cm+n)且已由(a1,…,ai-1)和(b1,…,bj-1)归并得(c1,…,ck-1)例2-3k=1,2,…,m+n1．初始化LC为空表；基本操作：2．分别从LA和LB中取得当前元素ai和bj；3．若ai≤bj，则将ai插入到LC中，否则将bj插入到LC中；4．重复2和3两步，直至LA或LB中元素被取完为止；5．将LA表或LB表中剩余元素复制插入到LC表中。//La和Lb均非空，i=j=1,k=0GetElem(La,i,ai);GetElem(Lb,
9、j,bj);if(ai<=bj){//将ai插入到Lc中ListInsert(Lc,++k,ai);++i;}else{//将bj插入到Lc中ListInsert(Lc,++k,bj);++j;}voidMergeList(ListLa,ListLb,List&Lc){//本算法将非递减的有序表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);//构造空的线
10、性表Lci=j=1;k=0;La_len=ListLength(La);Lb_l
