数据描述 - 4

,母版标题样式,单击此处编辑母版文本样式,*,*,母版标题样式,单击此处编辑母版文本样式,*,*,12/1/2024,1,数据描述,第三章,12/1/2024,2,引言,线性表,公式化描述,链式描述,间接寻址,模拟指针,本章内容,12/1/2024,3,3.8.1,箱子排序,(Bin Sort),3.8.2,基数排序,(Radix Sort),3.8.3,等价类,(Equivalence Classes),3.8.4,凸包,(Convex Hull),3.8,应用,12/1/2024,4,对,0 1 0 0,范围内的分数排序，如果采用第,2,章中所给出的任一种排序算法，所需要花费的时间均为,O(n,2,),，,有更快的方法吗？,一种更快的排序方法为箱子排序（,bin sort,）。,在箱子排序过程中，节点首先被放入箱子之中,具有相同分数的节点都放在同一个箱子中,通过把箱子链接起来就可以创建一个有序的链表,3.8.1,思考,12/1/2024,5,12/1/2024,6,箱子描述,每个箱子都是一个由节点组成的线性表。,箱子中的节点数目介于,0,到,n,之间。,一种简单的实现就是把每个箱子都描述成一个,链表,。,12/1/2024,7,箱子排序实现,1.,节点被分配到箱子之中,从欲排序链表的首部开始，逐个删除每个节点,把所删除的节点放入适当的箱子中（即相应的链表中）,2.,把箱子链接起来就可以创建一个有序的链表,.,从箱子链表的首部开始删除（从最后一个箱子开始）,插入元素在有序表的首部,12/1/2024,8,程序,3-40,一种用于箱子排序的节点类,class Node,friend ostream,public:,int operator!=(Node x)const,return(score!=x.score);,private:,int,score,;,char,*name,;,;,ostream&operator(ostream&out,const Node&x),out x.score ;return out;,12/1/2024,9,程序,3-43,箱子排序,Void BinSort(Chain&X,int range),/,按分数排序,int len=X.Length();Node x;,Chain*bin,;,bin=new Chainrange+1;,/,分配到每个箱子中,for(inti=1;i=0;j-),while(!binj.IsEmpty(),binj.Delete(1,x);,X.Insert(0,x);,deletebin;,时间复杂性,Q(n+range).,12/1/2024,10,箱子排序程序,2-,（,1/3,）,程序,3-44 Binsort,作为,Chain,类的成员,template,Void Chain:BinSort(int range),/,按分数排序,int b;/,箱子索引号,ChainNode,*bottom,*top,;,/,箱子初始化,bottom=new ChainNode*range+1;,top=new ChainNode*range+1;,for(b=0;blink)/,添加到箱子中,b=first-data;,if(bottomb)/,箱子非空,topb-link=first;,topb=first;,else/,箱子为空,bottomb=topb=first;,12/1/2024,12,箱子排序程序,2-,（,3/3,）,/,收集各箱子中的元素，产生一个排序链表,ChainNode*y=0;,for(b=0;blink=bottomb;,else/,第一个非空的箱子,first=bottomb;,y=topb;,if(y)y-link=0;,deletebottom;,deletetop;,12/1/2024,13,思考,b=first-data;?,12/1/2024,14,从,Node,类型到数字类型的转换,程序,3-42,又一种处理操作符重载的方法,class Node,friend ostream,public:,int operator!=(Node x)const,return(score!=x.score|name0!=x.name0;,operator int()const return score;,private:,int score;,char*name;,;,ostream&operator(ostream&out,const Node&x),out x.score x.name0 data;,需要被改写为：,b=value(first-data),;,12/1/2024,18,例子,Inline int F1(Node,Inline int F2(Node,Inline int F3(Node,Void main(void),Node x;,Chain L;,randomize();,for(inti=1;i=20;i+),x.exam1=i/2;,x.exam2=20-i;,x.exam3=random(100);,x.name=i;,L.Insert(0,x);,12/1/2024,19,例子,L.BinSort(10,F1);,coutSort on exam1endl;,coutLendl;,L.BinSort(20,F2);,coutSort on exam2endl;,coutLendl;,L.BinSort(130,F3);,coutSort on sum of examsendl;,coutLendl;,12/1/2024,20,3.8.2,箱子排序约束,关键值介于一个,“,合适的范围内,”,。,Range=n,c,.,时间复杂性,:Q(n+range)=Q(n+n,c,)=Q(n,c,).,假定对范围在,0999,之间的,10,个整数进行排序。,如果使用,range=1000,来调用,BinSort,，那么箱子的初始化将需要,1000,个执行步，节点分配需要,10,个执行步，从箱子中收集节点需要,1000,个执行步，总的执行步数为,2010,。,12/1/2024,21,3.8.2,基数排序,不直接对这些数进行排序，而是采用一些,基数,r,来分解这些数。,在基数排序（,radix sort,）中，把数按照某种基数分解为数字，然后对数字进行排序。,基数,r=,箱子个数，如下所示：,十进制数,928,可以按照基数,10,分解为数字,9,，,2,和,8.,用基数,10,来分解,3725,可得到,3,，,7,，,2,和,5,，,.,3725,用基数,60,来进行分解则可以得到,1,，,2,和,5.(3725)10=(125)60,12/1/2024,22,12/1/2024,23,解释,由于箱子排序是稳定排序，次低位数字相同的节点，其相对次序保持不变（与按最低位数字排序时所得到的次序相同）。,12/1/2024,24,时间复杂性,对范围在,0 n,c,1(c:,常量,),之间的,n,个整数进行排序。,r=n,，,range=n,，每个数分解的数字的个数,=c,时间复杂性,:Q(cn)=Q(n).,上述例子中：,进行三次排序，每次排序,range=10,需要,10,个执行步来对箱子进行初始化,10,个执行步用来把数分配至相应的箱子节点，,10,个执行步用来收集箱子节点,总的执行步数为,90,。,12/1/2024,25,比较,对,1000,个范围在,010,6,-1,之间的整数进行排序。,使用基数,r=10,6,的排序方法。需要,10,6,执行步对箱子初始化，,1000,个执行步分配箱子节点，另外,10,6,执行步收集箱子节点，因此总的执行步数为,2001000,。,对于,r=1000,的排序。每次排序都需要,3000,个执行步，所以排序完成时共需要,6000,个执行步。,12/1/2024,26,比较,若使用,r=100,。则需使用三次箱子排序过程依次对每两位数字进行排序，每次箱子排序需要,1200,个执行步，总的执行步数为,3600,。,如果使用,r=10,。则要进行六次箱子排序，每次针对一位数字，总的执行步数为,6(10+1000+10)=,6120,。,因此，,对于本例，采用基数,r=100,的排序效率最高。,12/1/2024,27,结论,对于一般的基数,r,，相应的,分解式,为：,x%r;(x%r,2,)/r;(x%r,3,)/r,2,;.,当使用基数,r=n,对,n,个介于,0n,c,-1,范围内的整数进行分解时，每个数将可以分解出,c,个数字。,因此，可以采用,c,次箱子排序，每次排序时取,range=n,。整个排序所需要的时间为,(cn)=,(n),（因为,c,是一个常量）。,山东大学计算机科学与技术学院 数据结构 第,3章 数据描述,28,3.8.3 等价类,定义,:,U=1,2,3,4,n /n,个元素的集合,R=(i,1,j,1,),(i,2,j,2,),(i,r,j,r,)/,具有,r,个关系的集合,关系,R,是一个等价关系（,equivalence relation,），当且仅当如下条件为真时成立：,对于所有的,a,，有,(a,a),R,（即关系是反身的）。,当且仅当,(b,a),R,时，,(a,b),R,（即关系是对称的）。,若,(a,b),R,且,(b,c),R,，则有,(a,c),R,（即关系是传递的）。,山东大学计算机科学与技术学院 数据结构 第,3章 数据描述,29,等价关系,在给出等价关系,R,时，我们通常会忽略其中的某些关系，这些关系可以利用等价关系的反身、对称和传递属性来获得,.,例,:,n,=14;,R,=(1,11)，(7,11)，(2,12)，(12,8)，,(11,12)，(3,13)，(4,13)，(13,14)，,(14,9),，,(5,14),，,(6,10),山东大学计算机科学与技术学院 数据结构 第,3章 数据描述,30,等价类定义,元素,a,和,b,等价,如果,(a,b),R，则元素,a,和,b,是等价的。,等价类（,equivalence class）,等价类是指相互等价的元素的最大集合。,“,最大,”,意味着不存在类以外的元素，与类内部的元素等价。,离线等价类,已知,n,和,R,，确定所有的等价类。,注意每个元素只能属于某一个等价类。,山东大学计算机科学与技术学院 数据结构 第,3章 数据描述,31,在线等价类,初始有,n,个元素，每个元素都属于一个独立的等价类。,需要执行以下的操作：,(1),Combine(a,b,),-把包含a和b的等价类合并成一个等价类。,(2),Find(e,),-确定哪个类包含元素e。,combine(a,b)等价于:,i=Find(a);j=Find(b);,If (i!=j)Union(i,j);,向,R,中添加新关系,(a,b):,i=Find(a);j=Find(b);,If(i!=j)Union(i,j);,在线等价类问题，通常又称之为,union-find问题.,山东大学计算机科学与技术学院 数据结构 第,3章 数据描述,32,在线等价类问题的解决办法,第一种解决方案,:,使用一个数组,E,Ee：包含元素e 的等价类,第二种解决方案,针对每个等价类设立一个相应的链表,山东大学计算机科学与技术学院 数据结构 第,3章 数据描述,33,第一种解决方案,void,Initialize,(int n),/,初始化,n,个类，每个类仅有一个元素,E=new int n+1;,For(int e=1;e=n;e+),Ee=e;,void,Union,(int i,int j),/,合并类,i,和类,j,For(int k=1;k=n;k+),if (Ek=j)Ek=i;,int,Find,(int e),return Ee;/,搜索包含元素,i,的类,1 2 3 4 5,E 1 2 3 4 5 n,1 3 3