数据结构6(4月28日)课件.ppt

1、查找：查找：根据给定的关键字值，在一组数据根据给定的关键字值，在一组数据值等于给定值的数据元素的过程。若存在这样的数据元素，值等于给定值的数据元素的过程。若存在这样的数据元素，则称查找成功；若不存在这样的数据元素，则称查找失败。则称查找成功；若不存在这样的数据元素，则称查找失败。关键字关键字:指数据元素中可以标识该数据元素的一组数据项。例如学指数据元素中可以标识该数据元素的一组数据项。例如学生记录中的学号；公民记录中的身份证号码等。生记录中的学号；公民记录中的身份证号码等。查找表：查找表：指一组待查数据元素的集合。它具有一定存储结构，如顺指一组待查数据元素的集合。它具有一定存储结构，如顺序表结

2、构、链式结构、树形结构等。序表结构、链式结构、树形结构等。2.6 2.6 查找查找 1)1)查找的方法查找的方法 查找某个数据元素依赖于查找表中数据元素的组织方式。按照查找某个数据元素依赖于查找表中数据元素的组织方式。按照数据元素的组织方式决定采用某种查找方法；反之数据元素的组织方式决定采用某种查找方法；反之,为了提高查找为了提高查找方法的效率，又要求数据元素采用某些特殊的组织方式。因此，在方法的效率，又要求数据元素采用某些特殊的组织方式。因此，在研究各种查找方法时，必须弄清各种查找方法所适用的组织方式。研究各种查找方法时，必须弄清各种查找方法所适用的组织方式。2)2)查找算法的评价查找算法的

3、评价 衡量一个算法的标准主要有两个：时间复杂度和空间复杂度。衡量一个算法的标准主要有两个：时间复杂度和空间复杂度。而在查找算法中，基本运算是给定值与关键字值的比较，即算法的而在查找算法中，基本运算是给定值与关键字值的比较，即算法的主要时间是花费在主要时间是花费在“比较比较”上的，所以，用上的，所以，用平均查找长度平均查找长度作为评价作为评价查查找算法好坏的依据。找算法好坏的依据。对于含有对于含有n n个数据元素的查找表，查找成功的平均查找长度为个数据元素的查找表，查找成功的平均查找长度为niiiCP1ASL=其中：其中：P Pi i为查找第为查找第i i个数据元素的概率；个数据元素的概率；C

4、Ci i为查找到第为查找到第i i个数个数据元素时，需进行的比较次数。据元素时，需进行的比较次数。*查找方法分类查找方法分类线性查找法线性查找法 顺序查找法顺序查找法 对半查找法对半查找法 分块查找法分块查找法基于树的查找法基于树的查找法 二叉排序树二叉排序树 B B树树 计算式查找法计算式查找法哈希法哈希法顺序存储的查找方法顺序存储的查找方法链式存储的查找方法链式存储的查找方法散列存储的查找方法散列存储的查找方法2.6.12.6.1 顺序查找法顺序查找法 基本思想是：从数组的第一个元素开始，与查找的关键字基本思想是：从数组的第一个元素开始，与查找的关键字逐个比对，直到找到关键字所在的位置或遇

5、到数组的结尾逐个比对，直到找到关键字所在的位置或遇到数组的结尾为止，若找到，则返回关键字在数组中的位置，否则返回为止，若找到，则返回关键字在数组中的位置，否则返回-1(1(因为因为C#C#的数组下标不可能为的数组下标不可能为-1)-1)。public int search(int keyValue)int i=0；while()i+;if()return(i);else return(-1);假设每个元素等概假设每个元素等概率查找率查找,则平均查则平均查找次数为找次数为(n+1)/2(n+1)/2ilength&datai!=keyValueiamidkamid,则取表的后半部分作为新表再去查

6、找。则取表的后半部分作为新表再去查找。（3 3）若若kamidkamid,则取表的前半部分作为新表再进行查找。则取表的前半部分作为新表再进行查找。这个过程一直进行到查找成功或子表的长度这个过程一直进行到查找成功或子表的长度为为0 0为止。为止。对半查找是基于关键字比较的最优方法。对半查找是基于关键字比较的最优方法。public int binSearch(int keyValue)int low,high,mid;low=0;high=length-1;while()mid=(low+high)/2;if(datamid=keyValue);else if(datamid keyValue);

7、else ;return(-1);low=highreturn(mid)low=mid+1high=mid-1对半查找成功时比较对半查找成功时比较次数最多为次数最多为loglog2 2n+1n+1*分块查找分块查找(索引顺序查找）索引顺序查找）“分块有序分块有序”表特点：表特点：(1)(1)表中数据分块表中数据分块 (2)(2)块中块中数据不必有序数据不必有序 (3)(3)块间块间有序有序“分块有序分块有序”表的结构有两部分：表的结构有两部分：(1)(1)顺序存储结构的线性表顺序存储结构的线性表 (2)(2)索引表（由每块的最大元素组成）索引表（由每块的最大元素组成）分块查找过程：分块查找过程

8、：(1)(1)用对半查找法查找索引表，确定待查项用对半查找法查找索引表，确定待查项x x 所在的块。所在的块。(2)(2)在相应的块中用顺序查找法查找待查项在相应的块中用顺序查找法查找待查项x x。2.6.3 2.6.3 二叉排序树及查找二叉排序树及查找 若线性表中的结点经常插入和删除，就应设计成把链表和二若线性表中的结点经常插入和删除，就应设计成把链表和二分法结合的查找方法。分法结合的查找方法。二叉排序树是将线形表中的元素组织成二叉树的形式，以达二叉排序树是将线形表中的元素组织成二叉树的形式，以达到与对半查找相同的查找效率。到与对半查找相同的查找效率。1 1、二叉排序树定义：、二叉排序树定义

9、：（1 1）若它的左子树不空，则左子树上所有的关键字均小于它若它的左子树不空，则左子树上所有的关键字均小于它 的的根结点的关键字；根结点的关键字；（2 2）若它的右子树不空，则右子树上所有的关键字均大于或若它的右子树不空，则右子树上所有的关键字均大于或 等等于它的根结点的关键字；于它的根结点的关键字；（3 3）它的左、右子树也是二叉排序树。它的左、右子树也是二叉排序树。如果按中序遍历二叉排序树，可得到一个递增排列的序列。如果按中序遍历二叉排序树，可得到一个递增排列的序列。526481937中序遍历序列：中序遍历序列：1 1、2 2、3 3、4 4、5 5、6 6、7 7、8 8、9 9二叉排序

10、树示例：二叉排序树示例：/TreeNode/TreeNode类类public class TreeNodepublic class TreeNode public char data;public char data;public TreeNode leftChild public TreeNode leftChild;public TreeNode rightChild public TreeNode rightChild;public TreeNode(char public TreeNode(char c)c)data=c;data=c;leftChild leftChild=null;

11、=null;rightChild rightChild=null;=null;/BiTree/BiTree类类public class BiTreepublic class BiTree private TreeNode private TreeNode root;root;public BiTree public BiTree()()root=null;root=null;public void insBTree(char public void insBTree(char k)k)/二叉排序树创建二叉排序树创建 public TreeNode banSearch(charpublic Tr

12、eeNode banSearch(char k)k)/二叉排序查找方法二叉排序查找方法 二叉排序树代码表示：二叉排序树代码表示：2 2、查找算法及实现、查找算法及实现 在给定的二叉排序树在给定的二叉排序树t t中查找给定待查关键字中查找给定待查关键字k k：从根结点出发从根结点出发 （1 1）如果树）如果树t t为空，那么查找失败。算法结束；否则，转（为空，那么查找失败。算法结束；否则，转（2 2）（2 2）如果）如果t.datat.data等于等于k k，则查找成功。算法结束。否则转（，则查找成功。算法结束。否则转（3 3）（3 3）如果）如果kt.datak k);else ;return

13、(p);(p!=null)&(p.data!=k)p=p.leftChildp=p.rightChild 假设一组数据元素的关键字序列如下：假设一组数据元素的关键字序列如下：4545，2424，5353，1212，3737，9393，3030，4040，80 80 分析查找元素分析查找元素4040 452453123795803040P1P2P3P4如何创建二叉排序树？如何创建二叉排序树？3 3、创建二叉排序树创建二叉排序树 通过在初始为空的树中不断插入数通过在初始为空的树中不断插入数k k来建立二叉排序树，步骤：来建立二叉排序树，步骤：（1 1）若二叉排序树为空，则插入结点应为根结点）若二叉

14、排序树为空，则插入结点应为根结点 （2 2）若二叉排序树非空，根据关键字比较的结果确定是在左）若二叉排序树非空，根据关键字比较的结果确定是在左子树还是在右子树中继续查找插入位置，直至某个结点的子树还是在右子树中继续查找插入位置，直至某个结点的左子树或右子树空为止，则插入结点应为该结点的左孩子左子树或右子树空为止，则插入结点应为该结点的左孩子或右孩子。或右孩子。假定由整数序列假定由整数序列1010，6 6，1919，2222，8 8，22生成一棵二叉排生成一棵二叉排序树，可以采用逐个元素插入的方法实现。序树，可以采用逐个元素插入的方法实现。(1)(1)首先将首先将1010作为根结点作为根结点(2

15、)(2)然后插入然后插入6 6时，通过比较知时，通过比较知610610，所以将，所以将6 6作为作为1010的的 左孩子插入；左孩子插入；(3)(3)同理将同理将1919作为作为1010的右孩子插入；的右孩子插入；(4)(4)整数整数2222通过和通过和1010、1919比较后，作为比较后，作为1919的右孩子插入。的右孩子插入。(5)(5)依次插入剩余的其他元素依次插入剩余的其他元素 public void insBTree(char k)/将将k k插入到二叉排序树插入到二叉排序树 TreeNode p,q;q=new TreeNode(k);if(root=null)/树为空，该节点即根

16、节点树为空，该节点即根节点 root=q;return;p=root;/从根开始从根开始开始找位置开始找位置 while(p.leftChild!=q)&(p.rightChild!=q)/尚未插入新节点尚未插入新节点 if(k 1N1，则执行第，则执行第1 1步，否则结束排序步，否则结束排序 初始状态初始状态 45 21 34 19 52 60 34 2445 21 34 19 52 60 34 24 第第1 1趟（趟（i=1i=1）1919 21 34 45 52 60 21 34 45 52 60 3434 24 24 第第2 2趟（趟（i=2i=2）1919 2121 34 45 52

17、 60 34 45 52 60 3434 24 24 第第3 3趟（趟（i=3i=3）1919 21 2421 24 45 52 60 45 52 60 3434 34 34 第第4 4趟（趟（i=4i=4）1919 21 24 21 24 3434 52 60 45 34 52 60 45 34 第第5 5趟（趟（i=5i=5）1919 21 24 21 24 34 34 3434 60 45 52 60 45 52 第第6 6趟（趟（i=6i=6）1919 21 24 21 24 34 34 3434 45 45 60 52 60 52 第第7 7趟（趟（i=7i=7）1919 21 24

18、 21 24 34 34 3434 45 52 45 52 60 60可见，可见，选择排序是一种不稳定的排序选择排序是一种不稳定的排序。具体算法描述如下具体算法描述如下:public void selectSort()int i,j,k;for(i=0;i length-1;i+);for(j=i+1;j n;j+)if()k=j;/记录最小元素的位置记录最小元素的位置 if()int x=datai;datai=datak;datak=x;k=idataj datakk!=i2.6.2 2.6.2 交换排序交换排序1 1、冒泡排序、冒泡排序 将待排序文件中的记录两两比较，若为逆序，则进行交换

19、。按将待排序文件中的记录两两比较，若为逆序，则进行交换。按此方法将文件从头到尾处理一遍称作一趟起泡。一趟起泡的结果是此方法将文件从头到尾处理一遍称作一趟起泡。一趟起泡的结果是将关键字最大的记录交换到了表尾。对余下将关键字最大的记录交换到了表尾。对余下n-1n-1个记录，重复此过个记录，重复此过程，直至文件排好序为止。若某一趟起泡过程中没有任何交换发生，程，直至文件排好序为止。若某一趟起泡过程中没有任何交换发生，则表明此时文件已经排好序了，不必再继续重复起泡过程。初始状则表明此时文件已经排好序了，不必再继续重复起泡过程。初始状态态 45 21 34 19 52 60 45 21 34 19 52

20、 60 3434 24 24第一趟第一趟 21 34 19 45 52 21 34 19 45 52 3434 24 60 24 60 第二趟第二趟 21 19 34 45 21 19 34 45 3434 24 52 60 24 52 60 第三趟第三趟 19 21 34 19 21 34 3434 24 45 52 60 24 45 52 60 第四趟第四趟 19 21 34 24 19 21 34 24 3434 45 52 60 45 52 60 第五趟第五趟 19 21 24 34 19 21 24 34 3434 45 52 60 45 52 60 第六趟第六趟 19 21 24

21、34 19 21 24 34 3434 45 52 60 45 52 60可见，可见，冒泡算法是稳定冒泡算法是稳定的。的。public void bubSort()public void bubSort()bool needChange=true;bool needChange=true;int j=length-1;int j=length-1;while()while()needChange=false;/needChange=false;/先假定不需要交换先假定不需要交换 for(int i=0;i j;i+)for(int i=0;i datai+1)if(datai datai+1)

22、;int temp=datai;int temp=datai;datai=datai+1;datai=datai+1;datai+1=temp;datai+1=temp;j-;j-;needChangeneedChange的作用是当前内循环无交换时，的作用是当前内循环无交换时，即终止程序的运算即终止程序的运算 。needChange&j 0needChange=true*直接插入排序直接插入排序基本思想：基本思想：将将n n个待排序元素看成为一个有序表和一个无序表。个待排序元素看成为一个有序表和一个无序表。开始有序表只有一个元素，无序表中则有开始有序表只有一个元素，无序表中则有n-1n-1个元

23、素。排序个元素。排序过程中每次从无序表中取出第一个元素，将其关键字与有序过程中每次从无序表中取出第一个元素，将其关键字与有序表的关键字比较，将其插入到适当位置，使之成为新的有序表的关键字比较，将其插入到适当位置，使之成为新的有序表。表。插入步骤：插入步骤：（1 1）将无序表中的第一个元素存入辅助变量）将无序表中的第一个元素存入辅助变量temptemp中。中。（2 2）将）将temptemp和有序表中从最后一个元素开始进行比较，若和有序表中从最后一个元素开始进行比较，若小于有序表中的元素，则有序表中该元素后移一位，同时继小于有序表中的元素，则有序表中该元素后移一位，同时继续和前一元素比较。否则插

24、入到该元素的后面。续和前一元素比较。否则插入到该元素的后面。初始状态初始状态 45 21 34 19 52 60 34 24 第一趟第一趟 21 45 34 19 52 60 34 24 第二趟第二趟 21 34 45 19 52 60 34 24 第三趟第三趟 19 21 34 45 52 60 34 24 第四趟第四趟 19 21 34 45 52 60 34 24 第五趟第五趟 19 21 34 45 52 60 34 24 第六趟第六趟 19 21 34 34 45 52 60 24 第七趟第七趟 19 21 24 34 34 45 52 60 有序文件有序文件 19 21 24 34

25、 34 45 52 60插入排序是稳定的排序插入排序是稳定的排序public void insertSort()int i,j,temp;for(i=1;i=0&tempdataj);j-;dataj+1=datajdataj+1=temptemp=datai2.6.4 快速排序快速排序基本思想：基本思想：在待排序的在待排序的n n个元素中任取一个元素个元素中任取一个元素R R，以该元素排序码，以该元素排序码k k为准，为准，将所有剩下的将所有剩下的n-1n-1个元素分割为两个子序列：个元素分割为两个子序列：第一个子序列中每个元素的排序码均小于或等于第一个子序列中每个元素的排序码均小于或等于k

26、 k；第二个子序；第二个子序列中每个元素的排序码均大于或等于列中每个元素的排序码均大于或等于k k。然后将。然后将k k所对应的元素所对应的元素放在两个子序列之间。完成第一趟排序，使得待排序序列成为放在两个子序列之间。完成第一趟排序，使得待排序序列成为 1 R R 2分别对子序列分别对子序列1 1和子序列和子序列2 2重复上述划分，直到每个子序列中只重复上述划分，直到每个子序列中只有一个元素时为止。有一个元素时为止。线性表分割步骤线性表分割步骤:（1 1）设置两个指示器）设置两个指示器i i和和j j，其初始状态分别指向区间内第一，其初始状态分别指向区间内第一个记录和最后一个记录。个记录和最后

27、一个记录。（2 2）将第一个记录移向辅助变量）将第一个记录移向辅助变量x x中中（3 3）从）从j j所指位置起向前搜索第一个小于所指位置起向前搜索第一个小于x x的记录，找到后，的记录，找到后，将将ajaj移至移至aiai的位置；的位置；（4 4）从）从ii所指向的位置向后搜索第一个关键字大于所指向的位置向后搜索第一个关键字大于x x的记录，的记录，找到后，将找到后，将aiai移至移至ajaj的位置；的位置；（5 5）重复）重复3 3、4 4两步，直至两步，直至i=ji=j，最后将，最后将x x送至送至aiai中去。中去。至此一趟排序完成，文件划分为两个子序列。重复以上步骤至此一趟排序完成，

28、文件划分为两个子序列。重复以上步骤直到每个子序列中只有一个元素时为止。直到每个子序列中只有一个元素时为止。初始状态初始状态 45 21 34 19 52 60 45 21 34 19 52 60 3434 24 24 i j i j一次交换一次交换 24 21 34 19 52 60 24 21 34 19 52 60 3434 2424 i j i j二次交换二次交换 24 21 34 19 24 21 34 19 5252 60 60 3434 52 52 i j i j三次交换三次交换 24 21 34 19 34 24 21 34 19 34 6060 3434 52 52 i j i

29、 j 24 21 34 19 34 45 60 52 24 21 34 19 34 45 60 52 ij ij (a)(a)一趟排序一趟排序初始状态初始状态 45 21 34 19 52 60 34 2445 21 34 19 52 60 34 24第一趟第一趟 24 21 34 19 34 45 60 5224 21 34 19 34 45 60 52第二趟第二趟 19 21 24 34 3419 21 24 34 34第三趟第三趟 19 2119 21第四趟第四趟 34 3434 34第五趟第五趟 52 6052 60有序文件有序文件 19 21 24 34 3419 21 24 34

30、34 45 52 60 45 52 60 (b)(b)全部快速排序全部快速排序 private void qkOne(int start,int end,out int mid)int x,i,j;i=start;j=end;x=datai;/将第一个值保存在将第一个值保存在x中中 while()while(i=x)/自右向左扫描自右向左扫描 ;if(i j);i+;while(i j&datai=x)/自左向右扫描自左向右扫描 ;if(i j)dataj=datai;j-;mid=i;i!=jj-datai=dataji+datai=x一趟分割的代码一趟分割的代码快速排序是不稳定的排序，但是

31、内排序中速度最快的。快速排序是不稳定的排序，但是内排序中速度最快的。public void qkSort()int start=0,end=length-1,mid;ArrayStack as=new ArrayStack(100);/建立一个堆栈建立一个堆栈 as.push(start);as.push(end);while(!as.isEmpty()end=as.pop();/与压栈的次序相反，弹出位置与压栈的次序相反，弹出位置 start=as.pop();while(start end)qkone(start,end,out mid);as.push(mid+1);/将分割后的第二个序

32、列压栈将分割后的第二个序列压栈 as.push(end);end=mid-1;/调节位置准备对第一个序列再分割，位置从调节位置准备对第一个序列再分割，位置从 start start 到到 mid-1mid-1 快速排序2.7.3 2.7.3 归并排序归并排序 采用二路归并技术，即每次将数组采用二路归并技术，即每次将数组a a中两个相邻的有序序中两个相邻的有序序列归并为一个有序序列。列归并为一个有序序列。排序步骤：排序步骤：（1 1）假设待排序文件含有）假设待排序文件含有n n个记录，则可看成是个记录，则可看成是n n个有序的个有序的子序列，每个子序列的长度为子序列，每个子序列的长度为1 1（2

33、 2）两两归并，得到）两两归并，得到n/2n/2个长度为个长度为2 2或或1 1的有序子序列的有序子序列（3 3）再两两归并，直到得到一个长度为）再两两归并，直到得到一个长度为n n的有序文件为止的有序文件为止。初始状态初始状态 45 21 34 19 52 60 45 21 34 19 52 60 3434 24 24 第一趟第一趟 21 45 19 34 52 60 24 21 45 19 34 52 60 24 3434 第二趟第二趟 19 21 34 45 24 19 21 34 45 24 3434 52 60 52 60 第三趟第三趟 19 21 24 34 19 21 24 34

34、 3434 45 52 60 45 52 60二路归并排序过程示例二路归并排序过程示例 二路归并排序是稳定的排序二路归并排序是稳定的排序有序文件有序文件as.mas.m和和am+1.tam+1.t归并为归并为bs.tbs.t的算法的算法:twoSort(int a,int s,int m,int t,inttwoSort(int a,int s,int m,int t,int b)b)int int i,j,k;i,j,k;i=s;/i i=s;/i是是as.mas.m 的指示器的指示器 j=m+1;/jj=m+1;/j是是am+1.t am+1.t 的指示器的指示器 k=s-1;/kk=s-

35、1;/k是是bs.tbs.t 的指示器的指示器 while()while()k+;k+;if(ai=aj)if(ai=aj);i+;i+;else else ;j+;j+;bk=aibk=aji=m&jm)for(;j+)k+;bk=aj;else for(;i+)k+;bk=ai;j=ti=2 while(n-i=2*k)k)twosort(a,i,i+k-1,i+2 twosort(a,i,i+k-1,i+2*k-1,b);k-1,b);i=i+2 i=i+2*k;k;if(n-ik)if(n-ik)twosort(a,i,i+k-1,n-1,b);twosort(a,i,i+k-1,n-

36、1,b);else else for(;i for(;in;i+)n;i+)bi bi=ai;=ai;一趟归并后，有序子文件长度为一趟归并后，有序子文件长度为2 2，二趟归并后，有序子文件，二趟归并后，有序子文件长度为长度为4 4，因归并的结果在，因归并的结果在b b中中,故每次归并完将其复制到故每次归并完将其复制到a a中。中。重复此过程，直到有序子文件为重复此过程，直到有序子文件为n n，具体算法描述如下，具体算法描述如下void mergeSort(int a,intvoid mergeSort(int a,int n)n)int int k=1,bN;/N k=1,bN;/N为已定义的符号常量为已定义的符号常量,代表线性表的长度代表线性表的长度 while(kwhile(kn)n)merge(a,k,n,b merge(a,k,n,b););k=2 k=2*k;k;for(int i=0;iN;i for(int i=0;iN;i+)+)ai=bi ai=bi;（学号（学号-6-1-6-1）将如下一组数据插入到一棵二叉排序树中，并将）将如下一组数据插入到一棵二叉排序树中，并将该二叉排序树的中序遍历结果输出。该二叉排序树的中序遍历结果输出。45，24，53，12，37，93，30，40，80作业作业