资源描述：
《算法设计方法课件教学配套课件作者吴哲辉第3章在线阅读下载》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、吴哲辉崔焕庆马炳先吴振寰编著机械工业出版社j第3章散列与凝聚算法I>1散列算法>矩阵乘法的凝聚算法>非负整数向量卷积的凝聚算法3.1散列算法■散列是指把一组无序的数据散列到各个存储单元(存储区)中。散列并不要求把数据排序，然后按顺序存放这些数据，而是通过一个散列函数来把这些数据映射到各个存储单元(存储区)中。散列函数(Hash函数)可定义为：/:数据集T存储区■一般地，要求力蕎足以下两个条件：(1)计算速度快，即算法的时间复杂度低；(2)没有冲突，或尽量减少冲突。■所谓冲突，是指数据集中存在两个数据q和冃(a,<>aj)使得f佝)7佝)。■冲突处理的方法主要有两种：(1)设置另一个散列函
2、数，对那些有冲突的数据再次散列；⑵设置链表，把每一组互相冲突的数据存放在一个链表中。算法设计方法j3.1散列算法■散列查找算法散列查找要解决的问题可概括为：在一组杂乱的数据中查找某个（某些）数据。即设A>,an},要查找数据也,b,bk等是否在/中。3.1散列算法散列查找算法的设计思路可以用以下3个步骤来描述。(1)设计一个散列函数/；for(/^1;/<=/?;/++)计算f佝)，并根据f佝)的值把分配到相关单元；⑵如果相关单元已存放有力中的另一个数据，则要进行冲突处理；(3)for(/=1;/<=/g/++){(3.1)计算f(bj;(3.2)根据f(bj)的值查找相关单元；(3.2
3、.1)若相关单元中无数据，则输出“不在/!中”；(3.2.2)若相关单元中有数据，则遍历链表，并逐个同比较，若查找到等于的数据，则输出“在力中”；若遍历完链表没有找到等于的数据,则输出“不在/中”。j3.1散列算法■1.散列查找算法适用于查找多个数据的情况。■2.散列查找算法的关键在于散列函数的设计。■3.假设使用拉链式冲突处理方法。j3.1散列算法■例3.1设A>{28,101,93,86,372,157,80,99,100,17&166,13,42,71,175,453,122,231,431,245,234&为一个（无序的）数据集,要查找3>{86,122,75,231,94,17
4、8}中的各个数据是否在/I中。1>a.(mod10)2>^(hkxIK))3>a,(mod10)5>q.(mod10)6>q(mod10)7>(mod10)8>q(mod10)9>^(modlO)4>q.(modlO)3.1散列算法■桶排序算法基本思想是把这组数据“散列”成若干“桶”，然后分别对各桶的数据进行排序。在这里，“散列”的含义有一定程度的变化，要求各个桶是按一定顺序排列的。假设待排序的数据为ax,a2,B,an,其中/?是一个很大的数值。如果已知B（）/a.=B,i>1,2,B,n并且/7个数据的数值比较均匀地分布在Bo和匪间o那么把它们分为Zr纟且，然后对每个中的元素进行排序
5、。j3.1散列算法例3.2设4>{274,384,123,77,201,15,375,145,101,64,341,235,38,178,137,264,350,212,184,26},用分桶选择排序算法对/中的元素排序。0=①/100二100=①/200200=①/3003()0=a./400>0=q/100100=j/2(X)2(M)=q"300300=a./4(X)26381841379机械工业出版就件2122&4扌］3.2矩阵乘法的凝聚算法■凝聚算法的基本思想是把分散的、有规则排列(存放)的、计算过程中需要多次重复使用的一组数据凝聚成一个数，通过对单个数的计算来实现对这一组的多次
6、重复计算，然后再把对单个数的计算结果散列成原问题需要求解的一组数据。■多项史昶值的;方法可以用作数据凝聚的喺*段炉"'对予占组非%,负整数，设置一个n-1次多项式如果把越取为大于各个系数的一个正整数，那么Pn_1(x)的值同这一组数之间就存在一一对应关系。3.2矩阵乘法的凝聚算法■当两个矩阵A和B的元素引和bq都是非负整数时，可以用多项式求值的方法把它们凝聚，即对非负整数矩阵知和勺乘法使用凝聚算法，见算法3.4。■当用口殆卩是任意整数（而不要求非负整数）矩阵时，可以把怖龄别分解为A>A.A>[atj]/MW•[afjB>B>[殆]…•[几oo+T=dQ9I9"o>B211>•JmB211
7、>>9ooo3.2矩阵乘法的凝聚算法■当知品卩是有理数矩阵时，记a..>—,i>1,2,B，加，j>1,2,B,n,i>1,2,Bj>1,2,B、q求出qij和tij的最小公倍数g,取和马勺积矩阵。机械工业出版牡课件3.2矩阵乘法的凝聚算法■对凝聚算法进行改进的主要思路是只对其中一个矩阵的歹U或行进行凝聚。设力为一个777行77列非负整数矩阵，助一个门行g列矩阵，要计算C=AB。当rn>=q时，只对矩阵力的各列元素进行凝聚，否则（即
