计算机软件技术基础(邮电)1-8.ppt

1、1,计算机软件技术基础,课件,第一章 数据结构,第二章 操作系统,第三章 软件工程,第四章 数据库,2,第一章 数据结构,第一单元,第二单元,第三单元,第四单元,第五单元,第六单元,第七单元,第八单元,3,查找和排序,第八单元,第一章 数据结构,4,1.5 查找和排序,1.5.1 查找 一. 查找的概念 查找又称检索，它是数据处理中使用频繁的一种重要操作。 查找表(search table) 被查找的数据对象是由同一类型的数据元素(或记录)构成的集合， 查找表是一种非常灵活的数据结构。 给查找带来不便，影响查找的效率。,5,关键字(key) 规定能够标识数据元素(或记录)的一个数据项或几个数据

2、项为关键字。 主关键字(primary key) 若此关键字可以唯一地标识一个记录，则称此关键字为主关键字； 次关键字(secondary key) 它可以标识若干个记录。称为次关键字。 当记录只有一个数据项时，它就是该记录的关键字。,6,查找(searching)定义 根据结定的值，在查找表中查找是否存在关键字等于给定值的记录， 查找成功 若存在一个或几个这样的记录，则称查找成功，查找的结果可以是对应记录在查找表中的位置或整个记录的值。 查找不成功 若表中不存在关键字等于给定值的记录，则称查找不成功，查找的结果可以给出一个特定的值或“空”指针。,7,查找应明确下述两个问题 (1) 查找的方法

3、 在研究各种查找方法时，必须弄清各种方法所使用的组织方式。 (2)查找算法的评价 衡量一个算法的标准主要有两个 时间复杂度 空间复杂度。 平均查找长度,其中: Pi为查找第i个数据元素的概率;Ci为查找到第i个数据元素时,需进行的比较次数。,8,二 顺序表的查找 1.顺序查找 基本思想 从第一个元素开始，逐个把元素的关键字值和给定值比较，若某个元素的关键字值和给定值相等，则查找成功；否则，若直至第n个记录都不相等，说明不存在满足条件的数据元素，查找失败。 顺序查找的适用范围 顺序存储结构组织的查找表的查找 链式存储结构组织的查找表的查找,9,顺序查找算法 int seqsearch(int d

4、ata, int x) /*在表中查找关键字值等于x的元素，若找到，则函数值为该元素在表中的位置，若没有找到，则函数值为0 */ int i = N; /N为表的长度，从表尾开始查找 while(datai! = x) i-; return i; 顺序查找算法查找成功的平均查找长度,ASL =,10,2、折半查找 折半查找的基本思想： 由于查找表中的数据元素按关键字有序(假设递增有序)，则在查找时可不必逐个顺序比较， 而采用跳跃的方式-先与中间位置的记录关键字值比较，若相等，则查找成功；若给定值大于中间位置的关键字值，则在查找表中的后半部继续进行折半查找；否则在前半部进行折半查找。 折半查找的

5、过程 先确定待查元素所在区域，然后逐步缩小区域，直到查找成功或失败为止。,11,假设待查元素所在区域的下界为low, 上界为hig, 则中间位置mid = (low + hig)/2。 (1) 若此元素关键字值等于给定值, 则查找成功; (2) 若此元素关键字值大于给定值, 则在区域mid + 1 hig内进行折半查找; (3) 若此元素关键字值小于给定值, 则在区域lowmid - 1内进行折半查找。 折半查找的适用条件 只适用于以顺序存储结构组织的有序查找表。,12,折半查找算法 int binsearch(int data, int x) /*在表中查找关键字值等于x的元素，若找到，则函

6、数值为该元素在表中的位置，若没有找到，则函数值为0*/ int low,mid,hig； low=0; hig=last; while (low=hig) mid = (low+hig)/2; /确定中间位置 if(datamid= = x) return mid +1;,13,else if (x datamid) low = mid +1; else hig = mid -1; return 0 ; ; 折半查找成功率的平均查找长度 ASL=log(n+1)- 1,折半查找的优点是比较次数少，查找速度快。但为了快速查找多付出的代价是要对数据元素关键字值的大小进行排序，而排序一般是很费时间的

7、。所以折半查找适用于已经建立就很少变动而又经常需进行查找的有序排列。,14,3、分块查找 分块查找要求把一个大的线性表分解成若干块，在每一块中结点的存放可以任意但块与块之间必须排序。 索引表 建立一个索引表，把每块中的最大关键字值作为索引表的关键字值，按照块的顺序存放到一个辅助数组中，显然，这个辅助数组是按关键字非递减排序的。查找时，首先在索引表中进行查找，确定要找的结点所在的块,15,分块有序表的索引存储表示,最大关键字,起始地址,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17,由于由索引项组成的索引表按关键字有序排列，则确定块的查找可以用顺序查找，亦

8、可用折半查找，而块中记录是任意排列的，则在块中只能是顺序查找。,16,分块查找的速度 虽然不如折半查找算法，但比顺序查找算法要快得多，同时又不需要对全部结点进行排序。 分块查找的适用范围 特别适合于结点动态变化的情况。 空间复杂性 在空间复杂性上，分块查找的主要代价是增加了一个辅助数组。 注意： 当结点变化很频繁时，可能会导致块与块之间的结点数相差很大，这将会导致查找效率的下降。,17,三种查找方法的比较 顺序查找方法最简单最大的缺点是查找效率低，其平均查找长度在三种查找方法中最大。 折半查找最大的优点是查找效率高其平均查找长度在三种查找方法中最小。但是只有当数据采用顺序存储结构组织，并且是有

9、序序列时才能使用这种方法进行查找。 数据元素是逐段有序的，则采用分块查找方法，查找效率最高。,18,三哈希查找(散列查找) 哈希查找因使用哈希函数而得名。它是由关键字作某种运算后直接确定元素的地址。建立ki的地址间的关系 确定元素的关键字与元素地址的关系可以用哈希函数来表示 adr(ai)H(ki) 其中adr(ai)为ai的地址，H(ki)称为哈希函数。哈希函数是种映象关系函数。,19, 例:用学生的学号作为学生记录的关键字，取学号的后三位作为映象地址，那么可以得到下列这些关键字和地址的对照表,采用的哈希函数为H(ki)k一990000。 冲突现象,要求使用均匀的哈希函数，即映象后的地址是均

10、匀分布的,20,几种哈希函数 1. 自身函数 关键字自身作为哈希函数，即 H(k)k，或自身加上一个常数作为哈希函数，即H(k)k十c。 例:要统计每周学生到课情况，则取17作为关键字,哈希函数取关键字自身,则可得到哈希表如下：,21,2. 模函数 这是一种简单而较常用的函数，它利用了简单的除模取余运算，即 H(k)k MOD m十c其中m和c都是整数，m决定存储单元数，c决定存储单元地址的范围。为了得到较均匀的地址分布，m应取为质数。 例: m101，c1000时，则存储单元数为101，存储地址范围为1000至1100。当关键字k5000时，用这个哈希函数可将k转换为地址1051。当k504

11、9时，可转换为地址1100。,22,3. 平方取中函数 这是一种较常用的哈希函数。首先将关键字平方，然后取中间几位作为地址，位数可根据要求的地址范围来确定。有时不能满足所要求的范围，可再加以处理，如乘以一个比例因子等。 例: 有一个关键字M9633，平方后得到92775424，如需要的地址长度为3位，则可由中间取754作为地址。取中间几位的目的是因为中间位与关键字的各位都有关系，哈希地址的分亦可更均匀些。,23,4 折叠函数 折叠函数是压缩关键字位数的有效方法。这种方法将关键字分成位数相等的部分，最后部分的位数可能少些，每部分的位数取决于对存储地址位数的要求。把各段加起来，去掉最高位的进位就得

12、到了所要求的地址。 例:有关键字34586612，要求存储地址为3位十进制数，则可得到哈希地址是223，如图1-70(a)所示。,24,图1-70哈希地址构造过程,在使用方法上，也可将两边的两段反向然后相加，则可得到地址430，如图 1-70(b)所示。,例:有关键字34586612，要求存储地址为3位十进制数，则可得到哈希地址是223。,25,解决冲突的几种方法 (1) 开放地址法 线性探查法 设表长为m，关键字个数为n。 探查法的基本思想 将散列表看成是一个环形表，若发生冲突的单元地址为d，则依次探查 d+1,d+2, m1, 0,1,dl,直至找到一个空单元为至。 开放地址公式为 di(

13、di)m (1im1) (式1) 其中dH(key)。,26,例1-10已知一组关键字集合(26,36,41,38,44,15,68,12,06,51,25),用线性探查法解决冲突，试构造这组关键字的散列表。 令装填因子1 ,取=0.75 。 因为n11，所以, 散列表长: mn/15，即散列表为HT15。 散列函数 利用除留余数法构造散列函数，选p15,即散列函数为: H（key）15,27,28,“堆积” 用线性探查法解决冲突时,当表中 i, i1 , ik位置上已有结点时，一个散列地址为i, i+1, , i+k+1的结点都将插入在位置i+k+1上，我们把这种散列地址不同的结点，争夺同一

14、个后继散列地址的现象称为“堆积” 二次探查法 二次探直法的探查序列依次是：12，-12， 22，-22 ，即，发生冲突时，将同义词来回散列在第一个地址dH(key)的两端。,29,当发生冲突时，求下一个开放地址的公式为： d2i1(di2)m d2i(d-i2)m (1i(m-1)2) (式2) 这种方法虽然减少了堆积，但不容易探查到整个散列表空间，只有当表长m为4j3的素数时，才能探查到整个表空间这里j为某一正整数。 随机探查法 采用一个随机数作为地址位移计算下一个单元地址，,30,求下一个开放地址的公式 di(dRi)m (1i(m1) (式3) 其中，d=H(key) , Rl , R2

15、,Rm1是1, 2, m1的一个随机排列。如何得到随机排列，涉及到随机数的产生问题。在实用中，常常用移位寄存器序列代替随机数序列。 （2）拉链法 拉链法解决冲突的方法： 将所有关键字为同义词的结点链接到同一个单链表中。,31,例111已知一组关键字和选定的散列函数和上例相同，用拉链法解决冲突构造这组关键字的散列表。 因为散列函数H(key)key15的值域为0 -12，故散列表为HTP13。当把H(key)i的关键字插入第i个单链表时，既可插在链表的头上，也可以插在链表的尾上。若采用将新关键字插入链尾的方式，依次把给定的这组关键字插入表中，则所得到的散列表如图172所示。,32,拉链法解决哈希

16、地址冲突,0 1 2 3 4 5 6 7 8 9 10 11 12,图172拉链法解决哈希地址冲突,33,1.5.2 排序 功能 将一个数据元素的无序序列调整为一个有序序列。 排序的依据 排序所依据的是数据元素中的某一个数据项(或几个数据项的组合)的值，在数据元素是一个基本项时，排序就依据该数据元素的值。 排序关键字(key word) 排序所依据的数据项(或数据项的组合)统称为排序关键字。 增序排列、降序排列 和内排序。,34,一插入排序 插入排序的基本思想 每次选择待排序的记录序列的第一个记录，按照排序码的大小将其插入到已排序的记录序列中的适当位置，直到所有记录全部排序完毕。 1. 直接插

17、入排序 直接插入排序是一种最简单的排序方法，整个排序过程为：先将第一个记录看作是一个有序的记录序列，然后从第二个记录开始，依次将未排序的记录插入到这个有序的记录序列中去，直到整个文件中的全部记录排序完毕。,35,例112 假设有五个元素构成的数组，其排序码依次为：50, 20, 40, 75, 35。,20 40 75 35 从50开始,40 75 35,初始序列,将20插入到位置0,50后移到位置1,第一趟扫描后,75 35,第二趟扫描后,将40插入到位置1,50后移到位置2,第三趟扫描后,35,记录75位置不变,第四趟扫描后,将35插入到位置1，后面记录后移,图 1-73 直 接 插 入

18、排 序 示 例,36,2. 折半插入排序,35,(a),k = 0 m = 1 r = 3 3540,故r = m-1 = 0,35,(b),k = m = r = 0 35=20,故k = m+1 =1 此时kr,折半结束，找到插入位置1，将35插入到位置1，原来从位置1开始到位置3的各个记录右移一个位置。,(c),37,3. 希尔排序 希尔排序又称缩小增量排序 希尔排序的基本思想 先选取一个小于n的整数di(称之为步长),然后把排序表中的n个记录分为di个组。从第一个记录开始,间隔为di的记录为同一组,各组内进行直接插入排序。一趟之后,间隔di的记录有序,随着有序性的改善,减小步长di ,

19、重复进行,直到di1,使得间隔为1的记录有序,也就是整体达到有序。步长为1时就是直接插入排序。,38,例114 设排序表关键字序列为：39, 80, 76, 41, 13, 29, 50, 78, 30, 11, 100, 7, 41, 86,步长因子分别取5、3、1，则排序过程如图175所示。,初始序列,39 80 76 41 13 29 50 78 30 11 100 7 41 86,第一趟 di = 5,29,39,100,7,第一趟排序结果,80,50,41,76,78,30,41,86,11,13,39,第一趟排序结果,第二趟 di = 3,第二趟排序结果,13 7 39 29 11

20、 41 30 76 41 50 86 80 78 100,第三趟 di = 1及排序结果,7 11 13 29 30 39 41 41 50 76 78 80 86 100,40,希尔排序算法如下： #include #define MAX 14 int g4=5,3,1,0; /步长数组 void shellsort(int number) int i, j, k, gap,t=0,temp; gap = gt; /初始步长为5 while(gap 0) for(k = 0; k gap; k+) for(i = k+gap; i MAX; i+=gap) ,41,for(j = i - g

21、ap; j = k; j-=gap) if (numberj numberj+gap) temp=numberj; numberj=numberj+gap; numberj+gap=temp; else break; ,42,printf(步长为%d时序列为: n, gap); for(i = 0; i MAX; i+) printf(%4d, numberi); printf(n); t+; gap = gt; /取下一个步长 ,43,void main() int numberMAX = 39,80,76,41,13,29,50,78,30,11,100,7,41,86; int i; p

22、rintf(初始序列: n); for(i = 0; i MAX; i+) printf(%4d, numberi); printf(n); shellsort(number); /希尔排序 性能分析：希尔排序方法是一个不稳定的排序方法。,44,二交换排序 交换排序的基本思想 两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。 交换排序基本思想的主要排序方法冒泡 排序和快速排序。 1. 冒泡排序 工作量的分析 最坏的情况下, 对size大小的表冒泡排序要作size - 1次大循环, 内循环的平均次数是size/2, 算法的复杂性是size(size-1)/

23、2。,45,冒泡排序过程排序前 19 13 05 27 01 26 31 16 02 09 11 21第一趟13 05 19 01 26 27 16 02 09 11 2131第二趟05 13 01 19 26 16 02 09 11 21 27 31第三趟05 01 13 19 16 02 09 11 21 26 27 31第四趟01 05 13 16 02 09 11 19 21 26 27 31第五趟01 05 13 02 09 11 16 19 21 26 27 31第六趟01 05 02 09 11 13 16 19 21 26 27 31第七趟01 02 05 09 11 13 1

24、6 19 21 26 27 31,46,19 13 05 27 01 26 31 16 02 09 11 21,13 19 05 27 01 26 31 16 02 09 11 21,13 05 19 27 01 26 31 16 02 09 11 21,13 05 19 27 01 26 31 16 02 09 11 21,13 05 19 01 27 26 31 16 02 09 11 21,13 05 19 01 26 27 31 16 02 09 11 21,13 05 19 01 26 27 31 16 02 09 11 21,13 05 19 01 26 27 16 31 02 0

25、9 11 21,47,13 05 19 01 26 27 16 31 02 09 11 21,13 05 19 01 26 27 16 02 31 09 11 21,13 05 19 01 26 27 16 02 09 31 11 21,13 05 19 01 26 27 16 02 09 11 31 21,13 05 19 01 26 27 16 02 09 11 21 31,每一趟比较 的过程示意图 冒泡排序是一个稳定的排序方法。,48,冒泡排序算法： void bubblesort(int a, int size) int i,j,tmp,k,flag=1; for(i=0; i a j

26、+1) tmp = a j ; a j = a j+1; a j+1 = tmp; flag=1; ,49,if(flag) printf(第%2d 趟:,i+1); /* 打印每趟排序结果 */ for(k=0; ksize; k+) printf(%3d,ak); printf(n); /* 换行 */ ,50,void main() int a12=19,13,5,27,1,26,31,16,2,9,11,21; int size=12; int i; printf(初始序列:); for(i=0; isize; i+)printf(%3d,ai); printf(n); bubbles

27、ort(a,12); /* 排序 */ ,51,2. 快速排序 快速排序又叫作分区交换排序，是目前已知的平均速度较快的一种排序方法，它是对冒泡排序方法的一种改进。 快速排序方法的基本思想 从待排序的n个数据元素中任意选取一个元素Ri（通常选取无序序列中的第一个元素）作标准，调整序中各个元素的位置，使排在Ri前面的元素的排码都小于Ri.key，排在Ri后面的元素的排序码都大于Ri.key。通常把这样的一个过程称作一次快速排序。,52,在第一次快速排序中，确定了元素Ri最终在序列中的排列位置，同时也把剩余的数据元素分成了两个子序列。对两个子序列再分别进行快速排序，又确定了两个元素在序列中应处的位置

28、，并将剩余元素分成了四个子序列，如此重复下去，当各个子序列的长度为1时，全部元素排序完毕。 可见，快速排序中的基本操作是子序列的划分操作。,53,设当前处理的元素序列的下界是low，上界是high，划分操作的步骤如下： (1) 让两个指针i , j分别指向序列的第一个元素和最后一个元素(即i=low:j=high) ，并将第一个元素的排序码保存在k中； （2）从右向左扫描过程 用k与j指向的元素的排序码key比较，若k Rj.key，则再比较j的前一个元素的排序码(j=j-1)；否则将元素Rj和Ri互换位置。此过程又称为从右向左扫描过程。,54,(3)从左向右扫描过程 用k与i指向的元素的排序

29、码key比较，若kRi.key，则再与i的后一个元素排序码比较(i=i +1)；否则将元素Ri和Rj互换位置。此过程又称从左向右扫描过程。 (4) 比较i和j，ij，则重复上面(2)、 (3)操作，直到i=j时，划分操作结束 例: 一组待排序元素的排序码序列为（49，38，60，90，70，15，30，49），试画出在第一趟快速排序中元素的交换示意图。,55,i = j 结束序 30 38 15 49 70 90 60 49 列状态为,继续循环 30 38 15 49 70 90 60 49,初始状态 49 38 60 90 70 15 30 49,从右向左扫描后 30 38 60 90 70

30、 15 49 49,从左向右扫描后 30 38 49 90 70 15 60 49,重复从右向左后 30 38 15 90 70 49 60 49,重复从左向右后 30 38 15 49 70 90 60 49,56,结束 结束 49 60 70 90,初始状态 49 38 60 90 70 15 30 49 ,一次划分之后 30 38 15 49 70 90 60 49 ,分别进行快排序15 30 38,49 60 结束,结束,有序序列 15 30 38 49 49 60 70 90,快速排序示例排序的全过程,57,快速排序的划分算法算法 struct Record int key; R11

31、=0,49,14,38,74,96,65, 8,49,55,27; int k=1; /记录划分次数 int Partition(struct Record R,int low, int high) /*对Rlowhigh，以Rlow为基准对象进行划分，算法返回基准对象记录的最终位置*/ R0.key=Rlow.key; /*缓存基准对象记录*/,58,while(low= R0.key) high-; if(lowhigh) Rlow.key = Rhigh.key; low+; /*将比基准对象小的记录交换到前面*/ while(lowhigh /*将比基准对象大的记录交换到后面* ,59

32、,Rlow.key = R0.key; /*基准对象记录到位*/ return low; /*返回基准对象记录所在的位置*/ 快速排序的算法： void Quick_Sort(struct Record R, int s, int t) /*对顺序表Rlowhigh进行快速排序*/ int i,j;,60,if(st) i = Partition(R,s,t); /*将表一分为二*/ printf(第%d次划分 :,k+); for(j=1; j11; j+)printf(%5d,Rj.key); printf(n); Quick_Sort(R,s,i-1); /*对基准对象前端子表进行快速排

33、序*/ Quick_Sort(R,i+1,t); /*对高端子表进行快速排序*/ ,快速排序是一个不稳定的排序方法。,61,void main() int n=11,i; printf(初始序列为:); for(i=1; in; i+)printf(%5d,Ri.key); printf(n); Quick_Sort(R,1,10); /* 排序 */ printf(最终序列为:); for(i=1; in; i+)printf(%5d,Ri.key); printf(n); ,62,三选择排序 选择排序的基本思想 对等待排序的记录Rl，R2，Rn进行n次选择操作，其中第i次操作是选择第i小(或大)的记录故在第i个(或n-i+1个)位置上。 简单选择排序： 简单选择排序的基本思想是： 第一趟排序 第一趟排序是在无序的K1,K2,K3,Kn按排序码选出最小的元素,将它与K1交换；,63,第二趟排序 第二趟排序是在无序的K2,K3,Kn中选出最小的元素，将它与K2交换； 第i趟排序 而第i趟排序时K1,K2,Ki-1已排好序，在当