数据结构集合与字典幻灯片.ppt

《数据结构集合与字典幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构集合与字典幻灯片.ppt（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构集合与字典数据结构集合与字典1第1页，共67页，编辑于2022年，星期六集合及其表示集合及其表示集合基本概念集合基本概念集合是成员集合是成员集合是成员集合是成员(对象或元素对象或元素对象或元素对象或元素)的一个群集。集合中的成员可的一个群集。集合中的成员可的一个群集。集合中的成员可的一个群集。集合中的成员可以是原子以是原子以是原子以是原子(单元素单元素单元素单元素)，也可以是集合。，也可以是集合。，也可以是集合。，也可以是集合。集合的成员必须互不相同。集合的成员必须互不相同。集合的成员必须互不相同。集合的成员必须互不相同。在算法与数据结构中所遇到的集合，其单元素通常是在算法与数据结构中

2、所遇到的集合，其单元素通常是在算法与数据结构中所遇到的集合，其单元素通常是在算法与数据结构中所遇到的集合，其单元素通常是整数、字符、字符串或指针，且同一集合中所有成员整数、字符、字符串或指针，且同一集合中所有成员整数、字符、字符串或指针，且同一集合中所有成员整数、字符、字符串或指针，且同一集合中所有成员具有相同的数据类型。具有相同的数据类型。具有相同的数据类型。具有相同的数据类型。colour=red,orange,yellow,green,black,blue,colour=red,orange,yellow,green,black,blue,purple,white name=“An”,“

3、Cao”,“Liu”,“Ma”,purple,white name=“An”,“Cao”,“Liu”,“Ma”,“Peng”,“Wang”,“zhang”“Peng”,“Wang”,“zhang”第2页，共67页，编辑于2022年，星期六集合中的成员一般是无序的，没有先后次序关系。但在表集合中的成员一般是无序的，没有先后次序关系。但在表集合中的成员一般是无序的，没有先后次序关系。但在表集合中的成员一般是无序的，没有先后次序关系。但在表示它时，常常写在一个序列里。示它时，常常写在一个序列里。示它时，常常写在一个序列里。示它时，常常写在一个序列里。我们常设定集合中的单元素具有线性有序关系，此关系可

4、我们常设定集合中的单元素具有线性有序关系，此关系可我们常设定集合中的单元素具有线性有序关系，此关系可我们常设定集合中的单元素具有线性有序关系，此关系可记作记作记作记作“”“”，表示，表示，表示，表示“优先于优先于优先于优先于”。若若a,b是集合中的两个单元素，则是集合中的两个单元素，则是集合中的两个单元素，则是集合中的两个单元素，则a ab三者必居其一；三者必居其一；若若a,b b,c c是集合中的三个单元素，且是集合中的三个单元素，且是集合中的三个单元素，且是集合中的三个单元素，且a ab b,b bc c，则则a c c。(传递性传递性传递性传递性)整数、字符和字符串都有一个自然的线性顺序

5、。而指针整数、字符和字符串都有一个自然的线性顺序。而指针整数、字符和字符串都有一个自然的线性顺序。而指针整数、字符和字符串都有一个自然的线性顺序。而指针也可以依据其在序列中安排的位置给予一个线性顺序。也可以依据其在序列中安排的位置给予一个线性顺序。也可以依据其在序列中安排的位置给予一个线性顺序。也可以依据其在序列中安排的位置给予一个线性顺序。集合操作有求集合的并、交、差、判存在等。集合操作有求集合的并、交、差、判存在等。集合操作有求集合的并、交、差、判存在等。集合操作有求集合的并、交、差、判存在等。第3页，共67页，编辑于2022年，星期六集合运算的文氏集合运算的文氏(Venn)图图用位向量实

6、现集合抽象数据类型用位向量实现集合抽象数据类型n n当集合是全集合当集合是全集合 0,1,2,n 的一个的一个子集，且子集，且 n是不大的整数时，可用位是不大的整数时，可用位(0,1)向量来实现集合。向量来实现集合。n n 当全集合是由有限的可枚举的成员组成当全集合是由有限的可枚举的成员组成的集合时，可建立全集合成员与整数的集合时，可建立全集合成员与整数 0,1,2,的一一对应关系，用位向量来表的一一对应关系，用位向量来表示该集合的子集示该集合的子集第4页，共67页，编辑于2022年，星期六集合的位向量集合的位向量(bit Vector)类的定义类的定义#include const int D

7、efaultSize=100;class Set private:int*bitVector;int MaxSize;public:Set(int MaxSetSize=DefaultSize);Set()delete bitVector;void MakeEmpty()for(int i=0;i 0);bitVector=new int MaxSize;assert(bitVector!=0);for(int i=0;i=0&x=0&x MaxSize);if(bitVectorx)bitVectorx=0;return 1;return 0;第8页，共67页，编辑于2022年，星期六集合复

8、制集合复制Set&Set:operator=(Set&right)assert(MaxSize=right.MaxSize);for(int i=0;i MaxSize;i+)bitVectori=right.bitVectori;return*this;集合并运算集合并运算Set&Set:operator+(Set&right)assert(MaxSize=right.MaxSize);for(int i=0;i MaxSize;i+)bitVectori=bitVectori|right.bitVectori;return*this;第9页，共67页，编辑于2022年，星期六集合交运算集合

9、交运算Set&Set:operator*(Set&right)assert(MaxSize=right.MaxSize);for(int i=0;i MaxSize;i+)bitVectori=bitVectori&right.bitVectori;return*this;集合差运算集合差运算Set&Set:operator-(Set&right)assert(MaxSize=right.MaxSize);for(int i=0;i=0&x MaxSize);return bitVectorx;判断两个集合是否相等判断两个集合是否相等int Set:operator=(Set&right)as

10、sert(MaxSize=right.MaxSize);for(int i=0;i MaxSize;i+)if(bitVectori!=right.bitVectori)return 0;return 1;第11页，共67页，编辑于2022年，星期六若若This集合是集合是right的子集则返回的子集则返回1否则为否则为0int Set:SubSet(Set&right)assert(MaxSize=right.MaxSize);for(int i=0;i MaxSize;i+)if(bitVectori!right.bitVectori)return 0;return 1;第12页，共67页

11、，编辑于2022年，星期六使用示例使用示例 Set s1,s2,s3,s4,s5;int index,equal;/构造集合构造集合 for(int k=0;k 10;k+)/集合赋值集合赋值 s1.AddMember(k);s2.AddMember(k+7);/s1:0,1,2,9,s2:7,8,9,16 s3=s1+s2;/求求s1与与s2的并的并 0,1,16 s4=s1*s2;/求求s1与与s2的交的交 7,8,9 s5=s1-s2;/求求s1与与s2的差的差 0,1,2,3,4,5,6 index=s1.SubSet(s4);/求求s4在在s1中首次匹配中首次匹配 cout inde

12、x endl;/位置位置，index=7 equal=s1=s2;/集合集合s1与与s2比较相等比较相等 cout equal endl;/equal为为0,两集合不等两集合不等第13页，共67页，编辑于2022年，星期六用有序链表实现集合的抽象数据类型用有序链表实现集合的抽象数据类型用带表头结点的有序链表表示集合用带表头结点的有序链表表示集合 用有序链表来表示集合时，链表中的每个结点表示集合的一用有序链表来表示集合时，链表中的每个结点表示集合的一个成员。个成员。各结点所表示的成员各结点所表示的成员 e0,e1,en 在链表中按升序排列在链表中按升序排列，即即 e0 e1 en。在一个有序链表

13、中寻找一个集合成员时，一般不用搜索整在一个有序链表中寻找一个集合成员时，一般不用搜索整个链表，搜索效率可以提高很多。个链表，搜索效率可以提高很多。集合成员可以无限增加。因此，用有序链表可以表示无穷集合成员可以无限增加。因此，用有序链表可以表示无穷全集合的子集。全集合的子集。第14页，共67页，编辑于2022年，星期六集合的有序链表类的定义template class SetList;template class SetNode friend class SetList;public:SetNode(const Type&item):data(item),link(NULL);private:T

14、ype data;SetNode*link;template class SetList private:SetNode*first,*last;public:第15页，共67页，编辑于2022年，星期六 SetList();void MakeEmpty();int AddMember(const Type&x);int DelMember(const Type&x);SetList&operator=(SetList&right);SetList&operator+(SetList&right);SetList&operator*(SetList&right);SetList&operato

15、r-(SetList&right);int Contains(const Type&x);int operator=(SetList&right);Type&Min();Type&Max();第16页，共67页，编辑于2022年，星期六 集合的搜索、加入和删除操作集合的搜索、加入和删除操作template 判断判断X是否为集合成员是否为集合成员int SetList:Contains(const Type&x)SetNode*temp=firstlink;while(temp!=NULL&tempdata x)temp=templink;if(temp!=NULL&tempdata=x)ret

16、urn 1;else return 0;第17页，共67页，编辑于2022年，星期六将将X插入到集合中插入到集合中template int SetList:AddMember(const Type&x)SetNode*p=firstlink,*q=first;while(p!=NULL&pdata x)q=p;p=plink;if(p!=NULL&pdata=x)return 0;SetNode*s=new SetNode(x);slink=p;qlink=s;if(p=NULL)last=s;return 1;第18页，共67页，编辑于2022年，星期六删除集合中的删除集合中的Xtempla

17、te int SetList:DelMember(const Type&x)SetNode*p=firstlink,*q=first;while(p!=NULL&pdata x)q=p;p=plink;if(p!=NULL&pdata=x)qlink=plink;if(p=last)last=q;delete p;return 1;else return 0;第19页，共67页，编辑于2022年，星期六用有序链表表示集合时的几个重载函数用有序链表表示集合时的几个重载函数template 复制集合复制集合SetList&SetList :operator=(SetList&right)SetNo

18、de*pb=right.firstlink;SetNode*pa=first=new SetNode;while(pb!=NULL)palink=new SetNode(pbdata);pa=palink;pb=pblink;palink=NULL;last=pa;return*this;第20页，共67页，编辑于2022年，星期六template 集合并SetList&SetList:operator+(SetList&right)SetNode*pb=right.firstlink;SetNode*pa=firstlink;SetNode*pc=first;while(pa!=NULL&p

19、b!=NULL)if(padata=pbdata)pclink=pa;pa=palink;pb=pblink;else if(padata pbdata)pclink=pa;pa=palink;else第21页，共67页，编辑于2022年，星期六 pclink=new SetNode(pbdata);pb=pblink;pc=pclink;if(pa!=NULL)pclink=pa;else while(pb!=NULL)pclink=new SetNode(pbdata);pc=pclink;pb=pblink;pclink=NULL;last=pc;return*this;第22页，共67

20、页，编辑于2022年，星期六template 集合交集合交SetList&SetList:operator*(SetList&right)SetNode*pb=right.firstlink;SetNode*pa=firstlink;SetNode*pc=first;while(pa!=NULL&pb!=NULL)if(padata=pbdata)pc=pclink;pa=palink;pb=pblink;else if(padata pbdata)pclink=palink;delete pa;pa=pclink;else pb=pblink;第23页，共67页，编辑于2022年，星期六 w

21、hile(pa!=NULL)pclink=palink;delete pa;pa=pclink;last=pc;return*this;第24页，共67页，编辑于2022年，星期六template 集合差集合差SetList&SetList:operator-(SetList&right)SetNode*pb=right.firstlink;SetNode*pa=firstlink;SetNode*pc=first;while(pa!=NULL&pb!=NULL)if(padata=pbdata)pclink=palink;delete pa;pa=pclink;pb=pblink;else

22、if(padata pbdata)pc=pclink;pa=palink;else pb=pblink;if(pa=NULL)last=pc;return*this;第25页，共67页，编辑于2022年，星期六判断集合相等判断集合相等template int SetList:operator=(SetList&right)SetNode*pb=right.firstlink;SetNode*pa=firstlink;while(pa!=NULL&pb!=NULL)if(padata=pbdata)pa=palink;pb=pblink;else return 0;if(pa!=NULL|pb!

23、=NULL)return 0;return 1;第26页，共67页，编辑于2022年，星期六并查集并查集(Union-Find Sets)把每一个对象看作是一个单元素集合，然后按一定顺序将把每一个对象看作是一个单元素集合，然后按一定顺序将把每一个对象看作是一个单元素集合，然后按一定顺序将把每一个对象看作是一个单元素集合，然后按一定顺序将属于同一等价类的元素所在的集合合并。在此过程中将反属于同一等价类的元素所在的集合合并。在此过程中将反属于同一等价类的元素所在的集合合并。在此过程中将反属于同一等价类的元素所在的集合合并。在此过程中将反复地使用一个搜索运算，确定一个元素在哪一个集合中。复地使用一个

24、搜索运算，确定一个元素在哪一个集合中。复地使用一个搜索运算，确定一个元素在哪一个集合中。复地使用一个搜索运算，确定一个元素在哪一个集合中。能够完成这种功能的集合就是能够完成这种功能的集合就是能够完成这种功能的集合就是能够完成这种功能的集合就是并查集并查集并查集并查集。它支持以下三。它支持以下三。它支持以下三。它支持以下三种操作：种操作：种操作：种操作：UnionUnion(RootRoot1,1,RootRoot2)2)/并操作并操作并操作并操作；要求两个集合互不相交 Find Find(x x)/搜索操作搜索操作搜索操作搜索操作；UFSetsUFSets(s s)/构造函数构造函数构造函数构

25、造函数。第27页，共67页，编辑于2022年，星期六n n 对于并查集来说，每个集合用一棵树表示。对于并查集来说，每个集合用一棵树表示。n 集合中每个元素的元素名分别存放在树的结点中，集合中每个元素的元素名分别存放在树的结点中，此外，树的每一个结点还有一个指向其双亲结点的此外，树的每一个结点还有一个指向其双亲结点的指针。指针。n 为此，需要有两个映射：为此，需要有两个映射：n 集合元素到存放该元素名的树结点间的对应；集合元素到存放该元素名的树结点间的对应；n 集合名到表示该集合的树的根结点间的对应。集合名到表示该集合的树的根结点间的对应。n 设设 S1=0,6,7,8，S2=1,4,9，S3=

26、2,3,5 第28页，共67页，编辑于2022年，星期六第29页，共67页，编辑于2022年，星期六为简化讨论，为简化讨论，忽略实际的集合名，仅用表示集合的忽略实际的集合名，仅用表示集合的树的根来标识集合树的根来标识集合。如果我们确定了元素如果我们确定了元素 i 在根为在根为 j 的树中，而且的树中，而且 j 有一个指向集合名字表中第有一个指向集合名字表中第 k 项的指针，则集合项的指针，则集合名即为名即为 namek。为此，采用树的双亲表示作为集合存储表示。为此，采用树的双亲表示作为集合存储表示。集合元素的编号从集合元素的编号从0到到 n-1。其中。其中 n 是最大元素是最大元素个数。在双亲

27、表示中，第个数。在双亲表示中，第 i 个数组元素代表包个数组元素代表包含集合元素含集合元素 i 的树结点。根结点的双亲为的树结点。根结点的双亲为-1，表示，表示集合中的元素个数。为了区别双亲指针信息集合中的元素个数。为了区别双亲指针信息(0)，集合元素个数信息用负数表示，集合元素个数信息用负数表示。第30页，共67页，编辑于2022年，星期六第31页，共67页，编辑于2022年，星期六const int DefaultSize=10;class UFSets /并查集的类定义并查集的类定义public:UFSets(int s=DefaultSize);UFSets()delete paren

28、t;const UFSets&operator=(UFSets const&Value);void Union(int Root1,int Root2);int Find(int x);void UnionByHeight(int Root1,int Root2);private:int*parent;int size;第32页，共67页，编辑于2022年，星期六UFSets:UFSets(int s)/构造函数构造函数 size=s;parent=new int size+1;for(int i=0;i=size;i+)parenti=-1;unsigned int UFSets:Find(

29、int x)/搜索操作搜索操作 if(parentx parentj，则则让让 j 成为成为 i 的双亲的双亲，否则，让，否则，让i成为成为j的双亲。的双亲。此即此即Union的加权规则的加权规则。parent0(=-4)parent4(=-3)第35页，共67页，编辑于2022年，星期六void UFSets:WeightedUnion(int Root1,int Root2)/按按Union的加权规则改进的算法的加权规则改进的算法 int temp=parentRoot1+parentRoot2;if(parentRoot2 valuekey-valuen n主要字典操作：主要字典操作：n

30、 n 检索检索(search)(search)n n 插入元素插入元素(insert)(insert)n n 删除元素删除元素(delete)(delete)n n 修改某修改某keykey对应的值对应的值 p269p269字典的抽象数据结构字典的抽象数据结构39第39页，共67页，编辑于2022年，星期六n n最主要也是使用最频繁的操作是检索（也称查找）最主要也是使用最频繁的操作是检索（也称查找）n n检索效率是字典实现中最重要的考虑因素检索效率是字典实现中最重要的考虑因素n n静态字典：建立后保持不变的字典静态字典：建立后保持不变的字典n n动态字典：内容经常动态变动的字典动态字典：内容经

31、常动态变动的字典n n静态字典的基本操作就是检索。实现中主要考虑检静态字典的基本操作就是检索。实现中主要考虑检索效率索效率n n动态字典除检索外还有插入和删除，实现中还需要考虑：动态字典除检索外还有插入和删除，实现中还需要考虑：n n 插入删除操作的效率插入删除操作的效率n n 插入删除可能导致字典结构变化，动态变化中能否保证插入删除可能导致字典结构变化，动态变化中能否保证检索效率？（使字典性能不随操作的进行而逐渐恶化）检索效率？（使字典性能不随操作的进行而逐渐恶化）40第40页，共67页，编辑于2022年，星期六n n 存储和检索是计算机信息处理中最基本的工作存储和检索是计算机信息处理中最基

32、本的工作n n 字典就是实现存储和检索的结构字典就是实现存储和检索的结构n n 需要存储和检索的信息有许多具体情况，因此要考虑各需要存储和检索的信息有许多具体情况，因此要考虑各种不同的字典实现技术。种不同的字典实现技术。n n 这里的基本问题是空间利用率和操作效率检索效率这里的基本问题是空间利用率和操作效率检索效率的评价标准：检索过程中关键码的平均比较次数，即的评价标准：检索过程中关键码的平均比较次数，即平均检索长度平均检索长度ASLASL（average search lengthaverage search length），定义为：），定义为：n nASL=ASL=n ni=1i=1p p

33、i ic ci in nc ci i 和和p pi i 分别为元素分别为元素i i 的检索长度和概率。若各元素的检索的检索长度和概率。若各元素的检索概率相等，就有概率相等，就有p pi i=1/n=1/n。ASL=1/n cASL=1/n ci i 。n n字典的组织方法很多，如：顺序、跳表、散列、二叉树字典的组织方法很多，如：顺序、跳表、散列、二叉树和和B B树等。树等。41第41页，共67页，编辑于2022年，星期六 线性表表示线性表表示 n n线性表可以保存信息，因此可以作为字典的实现基础线性表可以保存信息，因此可以作为字典的实现基础n n关联在线性表里顺序排列，形成关联的序列关联在线性

34、表里顺序排列，形成关联的序列n n检索就是在线性表里查找关键码合适的元素检索就是在线性表里查找关键码合适的元素n n数据元素的插入删除都是很平常的线性表操作数据元素的插入删除都是很平常的线性表操作n n 顺序表表示n n 链表表示（p270）42第42页，共67页，编辑于2022年，星期六顺序检索算法顺序检索算法n n/*/*在字典中顺序检索关键码为在字典中顺序检索关键码为keykey的元素的元素*/n nint seqSearch(SeqDic*pdic,KeyType key,int*position)int seqSearch(SeqDic*pdic,KeyType key,int*po

35、sition)n nint i;int i;n nfor(i=0;i n;i+)/*for(i=0;i n;i+)/*从头开始向后扫描从头开始向后扫描*/n n if(pdic-elementi.key=key)if(pdic-elementi.key=key)n n *position=i;*position=i;n n return TRUE;/*return TRUE;/*检索成功检索成功*/n n n n*position=-1;*position=-1;n nreturn FALSE;/*return FALSE;/*检索失败检索失败*/n n n n失败时由失败时由position

36、 position 设置一个特殊值。设置一个特殊值。43第43页，共67页，编辑于2022年，星期六n n平均检索长度分析平均检索长度分析n n ASL=1*pASL=1*p1 1+2*p+2*p2 2+n*p+n*pn nn n=(1+2+=(1+2+n)/n(pi=1/n+n)/n(pi=1/n 时时)n n=(n+1)/2=O(n)=(n+1)/2=O(n)n n 优点：数据结构和算法简单，元素是否有序均可使用优点：数据结构和算法简单，元素是否有序均可使用n n 缺点：平均检索长度大，缺点：平均检索长度大，n n很大时检索耗时太多很大时检索耗时太多n n不适合动态变化频繁的字典不适合动态

37、变化频繁的字典n n删除元素需顺序检索，删除元素需顺序检索，O(n)O(n)，可能大量移动数据，可能大量移动数据n n插入元素（关联）时可保存在已有元素之后，插入元素（关联）时可保存在已有元素之后，O(1)O(1)操作；若要防止出现重复关键码，就需要检查所有元素，操作；若要防止出现重复关键码，就需要检查所有元素，O(n)O(n)n n动态变化中字典的检索效率不变（已经是最低效的）动态变化中字典的检索效率不变（已经是最低效的）44第44页，共67页，编辑于2022年，星期六n n二分法检索算法二分法检索算法n n如果字典元素之间有关系，就可能利用它加快检索速度。如果字典元素之间有关系，就可能利用

38、它加快检索速度。最常见的关系是关键码有序，这时将元素按序排列（从最常见的关系是关键码有序，这时将元素按序排列（从小到大或从大到小）排列，就可以快速检索（二分法）小到大或从大到小）排列，就可以快速检索（二分法）n n二分法检索基本过程（假设元素按关键码升序排列）：二分法检索基本过程（假设元素按关键码升序排列）：n n1.1.初始时，考虑范围是整个字典（顺序表）初始时，考虑范围是整个字典（顺序表）n n2.2.取考虑范围中位于中间的元素，用这个元素的关键码取考虑范围中位于中间的元素，用这个元素的关键码与检索关键码比较。如果相等则检索结束；否则与检索关键码比较。如果相等则检索结束；否则n n3.3.

39、如果检索关键码较大，把检索范围改为位置高的一半；如果检索关键码较大，把检索范围改为位置高的一半；如果检索关键码较小，把检索范围改为低一半如果检索关键码较小，把检索范围改为低一半n n4.4.如果范围里已经无元素，检索失败结束，否则回到如果范围里已经无元素，检索失败结束，否则回到2 245第45页，共67页，编辑于2022年，星期六n n/*/*在字典中用二分法检索关键码为在字典中用二分法检索关键码为keykey的元素的元素*/n nint biSearch(SeqDic*pdic,KeyType key,int*position)int biSearch(SeqDic*pdic,KeyType

40、 key,int*position)n nint low=0,high=pdic-n-1,mid;int low=0,high=pdic-n-1,mid;n nwhile(low=high)while(lowelementmid.key=key)/*if(pdic-elementmid.key=key)/*检索成功检索成功*/n n *position=mid;return TRUE;*position=mid;return TRUE;n n n n else if(pdic-elementmid.key key)else if(pdic-elementmid.key key)n n high

41、=mid-1;/*high=mid-1;/*要检索的元素在左半区要检索的元素在左半区*/n n else low=mid+1;/*else low=mid+1;/*要检索的元素在右半区要检索的元素在右半区*/n n n n*position=-1;*position=-1;n nreturn FALSE;/*return FALSE;/*检索失败检索失败*/n n 46第46页，共67页，编辑于2022年，星期六n n分析分析n n每次比较将范围缩小一半，第每次比较将范围缩小一半，第i i次可能比较的元素个次可能比较的元素个数数 n n比较次数比较次数 可能比较的元素个数可能比较的元素个数n

42、n1 1=21 1=20 0n n2 2=22 2=21 1n n3 4=23 4=22 2n n n nn 2n 2j-1j-1n n若元素个数若元素个数n n刚好为刚好为2 20 0+2+21 1+2+2j-1j-1=2=2j j-1-1则最大检索长则最大检索长度为度为j j；n n若若2 2j j-1n2-1n2j j+1-1+1-1，则最大检索长度为，则最大检索长度为j+1j+1。n n所以，二分法的最大检索长度为所以，二分法的最大检索长度为loglog2 2(n+1)(n+1)47第47页，共67页，编辑于2022年，星期六n n二分法检索（排序顺序字典）：n n 优点是检索速度快，

43、O(log n)n n 插入时需要维护元素顺序，O(n)操作（检索插入位置可以用二分法，O(log n)）n n 删除可用二分法查找元素，但需移动后面元素，O(n)n n 只能用于元素按关键码排序的字典，只适合顺序存储结构n n总结：排序表实现字典，检索效率高。为保持元素顺序，插入删除操作效率低。因此不适合用于实现大的动态字典48第48页，共67页，编辑于2022年，星期六跳表跳表n n在一个使用有序链表描述的具有n 个元素的字典中进行搜索，至多需进行n 次比较。如果在链中部节点加一个指针，则比较次数可以减少到n/2+1。搜索时，首先将欲搜索元素与中间元素进行比较。如果欲搜索的元素较小，则仅需

44、搜索链表的左半部分，否则，只要在链表右半部分进行比较即可。49第49页，共67页，编辑于2022年，星期六50第50页，共67页，编辑于2022年，星期六n n通常0级链包括n个元素，1级链包括n/2个元素，2级链包括n/4个元素，而每2i 个元素有一个i级链指针。当且仅当一个元素在0i 级链上，但不在i+1级（若该链存在）链上时，我们就说该元素是i 级链元素。在图中，4 0是2级链上唯一的元素而7 5是1级链元素。2 0、3 0、6 0、8 0是0级链元素。n n图所示的结构为跳表（skip list）。在该结构中有一组有层次的链。0级链是包含所有元素的有序链表，1级链是0级链的一个子集。i

45、 级链所包含的元素是i-1级链的子集。图中，i 级链上所有的元素均在i-1级链上。51第51页，共67页，编辑于2022年，星期六跳表的插入和删除跳表的插入和删除n n在图中可以看到，一个指针的元素有n/2个，两个指针的元素有n/4个，三指针的元素有n/8，有i指针的元素有n/2i个。他们处在i级的链上。n n在进行插入和删除时，要想保持跳表结构，必须耗时O(n)。n n跳表是用空间+插入和删除上的时间来换取搜索上的时间。n n这是一种处理方法，但不是很好。52第52页，共67页，编辑于2022年，星期六散列散列(Hashing)前面讲的字典数据结构（算法）中，元素的存储位置与元素的关键码之间

46、不存在直接对应关系，因此查找关键码需要一系列的比较。搜索的效率取决于比较的次数。散列表与散列方法散列表与散列方法 散列方法在表项的存储位置与它的关键码之间建立一个确定的对应函数关系Hash(),使每个关键码与结构中的唯一存储位置相对应：Address=Hash(Rec.key)53第53页，共67页，编辑于2022年，星期六散列方法：在存放表项时，通过相同函数计算存储位置，并按此位置存放，这种方法称为散列方法。散列函数：在散列方法中使用的函数。散列表：按上述方法构造出来的表称为散列表。通常关键码集合比散列表地址集合大的多，因此有可能经过散列函数的计算，把不同的关键码映射到同一个散列地址上。称这

47、些散列地址相同的不同关键码为同义词。54第54页，共67页，编辑于2022年，星期六 对于散列方法需要讨论两个问题(1)对于给定的一个关键码集合，选择一个计算简单且地址分布比较均匀的散列函数，避免或尽量减少冲突。(2)拟订解决冲突的方案。散列函数散列函数 构造散列函数应注意以下几个问题：(1)散列函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址，其值域必须在1m-1之间。(2)散列函数计算出来的地址应能均匀分布在整个地址空间中。(3)散列函数应是简单的。55第55页，共67页，编辑于2022年，星期六1.直接定址法 此类方法取关键码的某个线形函数值作为散列地址：Hash(k

48、ey)=a*key+b 其中a,b为常数 这类散列函数是一对一的映射，一般不会产生冲突。但是，它要求散列地址空间的大小与关键码集合的大小相同，这种要求一般很难实现。56第56页，共67页，编辑于2022年，星期六2.数字分析法 设有n个d位数，每一位可能有r种不同的符号。这r种不同的符号在各位上出现的频率不一定相同。可根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址。计算各位数字中符号分布均匀度其中，表示第I个符号在第k位上出现的次数，n/r表示各种符号在n个数中均匀出现的期望值。计算 值越小，表明在该位各种符号分布的越均匀。57第57页，共67页，编辑于2022年，星期六3.除

49、留余数法 设散列表中允许的地址数为m，取一个不大于m，但最接近或等于m的质数p，或选取一个不含有小于20的质因子的合数作为除数。这样的散列函数为：hash(key)=key%p pm其中，“%”是整数除法取余的运算，要求这时的质数p不是接近2的幂。58第58页，共67页，编辑于2022年，星期六4.平方取中法 先计算构成关键码的表示符的内码的平方，然后按照散列表的大小取中间的若干位作为散列地址。在平方取中法中，一般取散列地址为2的某次幂。59第59页，共67页，编辑于2022年，星期六5.折叠法 有两种方法：(1)移位法-把各部分的最后一位对齐相加。(2)分界法-各部分不折断，沿各部分的分界来

50、回折叠，然后对齐相加，将相加的结果当作散列地址。60第60页，共67页，编辑于2022年，星期六处理冲突的闭散列方法 若设散列表有m个地址，将其改为m个桶。其桶号与散列地址一一对应。每个桶可存放s个表项。如果对不同的关键码用散列函数计算得到同一个散列地址，就产生了冲突，它们可以放到桶内的不同位置，只有当桶内所s个表项都放满后才会产生冲突。61第61页，共67页，编辑于2022年，星期六处理冲突的一种常用的方法就是闭散列，也叫开地址法。所有的桶都直接放在散列表数组中。因此，每一个桶只有一个表项。如果在存放表项时发现，该位置已被别的表项占据，则在整个表中查找新的位置，如果表未被装满，则在允许的范围