常用算法及数据结构.pptx

《常用算法及数据结构.pptx》由会员分享，可在线阅读，更多相关《常用算法及数据结构.pptx（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1常用算法及数据结构常用算法及数据结构主要内容主要内容n n查找n n排序n n栈第1页/共19页查找查找n n查找是指在数据元素集合中查找满足某种条件的数据元素查找是指在数据元素集合中查找满足某种条件的数据元素的过程。例如在学生成绩表中查找某一学生的成绩；在字的过程。例如在学生成绩表中查找某一学生的成绩；在字典中查找某个字等等。典中查找某个字等等。n n查找是计算机应用中最常用的操作之一，也是许多程序中查找是计算机应用中最常用的操作之一，也是许多程序中最耗时间的一部分。因而，查找方法的优劣对系统的运行最耗时间的一部分。因而，查找方法的优劣对系统的运行效率影响极大。效率影响极大。第2页/

2、共19页顺序查找顺序查找n n基本思想n n从查找表的一端开始，逐个将记录的关键字值从查找表的一端开始，逐个将记录的关键字值和给定值进行比较，如果某个记录的关键字值和给定值进行比较，如果某个记录的关键字值和给定值相等，则称查找成功；否则，说明查和给定值相等，则称查找成功；否则，说明查找表中不存在关键字值为给定值的记录，则称找表中不存在关键字值为给定值的记录，则称查找失败。查找失败。第3页/共19页顺序查找顺序查找n n例：利用随机函数产生10个100以内的整数存放在数组x中，然后读入一个待查找的数k。若k存在，显示它在数组中的位置（下标）；否则显示没有找到。第4页/共19页算法实现算法实现 i

3、nt x=new int10;int x=new int10;int k,p=-1,i;int k,p=-1,i;Random ran=new Random();Random ran=new Random();for(i=0;i x.Length;i+)for(i=0;i x.Length;i+)xi=(int)(ran.Next()%100;xi=(int)(ran.Next()%100;Console.Write(0,xi);Console.Write(0,xi);Console.WriteLine();Console.WriteLine();Console.WriteLine(pleas

4、e enter a number for Console.WriteLine(please enter a number for search:);search:);k=int.Parse(Console.ReadLine();k=int.Parse(Console.ReadLine();for(i=0;i x.Length;i+)for(i=0;i x.Length;i+)if(xi=k)p=i;break;if(xi=k)p=i;break;if(p!=-1)if(p!=-1)Console.WriteLine(0 in position 1,k,p);Console.WriteLine(

5、0 in position 1,k,p);else Console.WriteLine(0 no found!,k);else Console.WriteLine(0 no found!,k);第5页/共19页排序排序n n排序是将一组任意序列的数据元素（记录），按由大到小的顺序（降序）排列或按由小到大的顺序（升序）排列。这些数据元素（记录）可以是数值型，也可以为字符型。若为数值型，则按数值大小排列；若为字符型，则按其ASCII码的顺序排列。第6页/共19页直接选择排序直接选择排序n n基本思想直接选择排序的基本思想是：第一趟从所有的直接选择排序的基本思想是：第一趟从所有的直接选择排序的基本思

6、想是：第一趟从所有的直接选择排序的基本思想是：第一趟从所有的n n个记录中选取最小个记录中选取最小个记录中选取最小个记录中选取最小的记录放在第一位，第二趟从的记录放在第一位，第二趟从的记录放在第一位，第二趟从的记录放在第一位，第二趟从n-1n-1个记录中选取最小的记录放到第个记录中选取最小的记录放到第个记录中选取最小的记录放到第个记录中选取最小的记录放到第二位。以此类推，经过二位。以此类推，经过二位。以此类推，经过二位。以此类推，经过n-1n-1趟排序后，整个序列就成为有序序列。趟排序后，整个序列就成为有序序列。趟排序后，整个序列就成为有序序列。趟排序后，整个序列就成为有序序列。第7页/共19

7、页例例图 直接选择排序的过程初始记录的关键字：7 4 -2 19 13 6第一趟排序：-2 4 7 19 13 6第二趟排序：-2 4 7 19 13 6第三趟排序：-2 4 6 19 13 7第四趟排序：-2 4 6 7 13 19第五趟排序：-2 4 6 7 13 19第六趟排序：-2 4 6 7 13 19第8页/共19页算法实现算法实现 int i,j,k,temp;int i,j,k,temp;int a=new int 7,4,-2,19,13,6;int a=new int 7,4,-2,19,13,6;for(i=0;i a.Length-1;i+)for(i=0;i a.Le

8、ngth-1;i+)k=i;k=i;for(j=i+1;j a.Length;j+)for(j=i+1;j a.Length;j+)if(aj ak)k=j;if(aj ak)k=j;if(i!=k)if(i!=k)temp=ak;temp=ak;ak=ai;ak=ai;ai=temp;ai=temp;第9页/共19页冒泡排序冒泡排序n n基本思想冒泡排序（冒泡排序（冒泡排序（冒泡排序（Bubble SortBubble Sort）是一种简单的交换排序方法。它的基本思）是一种简单的交换排序方法。它的基本思）是一种简单的交换排序方法。它的基本思）是一种简单的交换排序方法。它的基本思想是对所有相邻

9、记录进行比较，如果是逆序，则将其交换，最终达想是对所有相邻记录进行比较，如果是逆序，则将其交换，最终达想是对所有相邻记录进行比较，如果是逆序，则将其交换，最终达想是对所有相邻记录进行比较，如果是逆序，则将其交换，最终达到有序。到有序。到有序。到有序。第10页/共19页例例图 冒泡排序过程23 38 22 45 23 67 31 15 41初始关键字序列:第一趟排序后:23 22 38 23 45 31 15 41 67第二趟排序后:22 23 23 38 31 15 41 45 67第三趟排序后:22 23 23 31 15 38 41 45 67第四趟排序后:22 23 23 15 31 3

10、8 41 45 67第五趟排序后:22 23 15 23 31 38 41 45 67第六趟排序后:22 15 23 23 31 38 41 45 67第七趟排序后:15 22 23 23 31 38 41 45 67第11页/共19页算法实现算法实现int i,j,temp;int i,j,temp;int a=new int 7,4,-2,19,13,6;int a=new int 7,4,-2,19,13,6;for(i=0;i a.Length-1;i+)for(i=0;i a.Length-1;i+)/*/*外循环控制排序的趟数外循环控制排序的趟数*/for(j=0;j a.Leng

11、th-i-1;j+)for(j=0;j aj+1)if(aj aj+1)temp=aj;/*temp=aj;/*交换两个记录交换两个记录*/aj=aj+1;aj=aj+1;aj+1=temp;aj+1=temp;第12页/共19页栈栈n n栈是一种数据结构，它是一种操作受限的数组，因为它只允许用户从数组的一头进行操作，其操作原则是先进后出，或者说是后进先出。n n栈这种数据结构的操作主要有两个，一个操作叫入栈（push）操作，它的作用是把当前数据保存到栈顶，另一个操作是出栈（pop）操作，它的作用是取出栈顶的数据。第13页/共19页栈栈n n进栈或入栈（Push）栈顶栈底ABCPush(A)P

12、ush(B)Push(C)第14页/共19页栈栈n n弹出或出栈（Pop）栈顶栈底ABCPop()Pop()Pop()第15页/共19页用一维数组模拟栈操用一维数组模拟栈操作作n n用一维数组模拟栈的操作，完成将用户输入的数组按相反的顺序显示出来。第16页/共19页 string Test;string Test;int MaxLength=50;int MaxLength=50;char str=new charMaxLength;char str=new charMaxLength;int i;int i;int CurrentPos=0;int CurrentPos=0;Console.

13、WriteLine(Console.WriteLine(输入要测试的字符串：输入要测试的字符串：输入要测试的字符串：输入要测试的字符串：););Test=Console.ReadLine();Test=Console.ReadLine();for(i=0;i Test.Length;i+)for(i=0;i=MaxLength)if(CurrentPos=MaxLength)break;break;strCurrentPos=Testi;strCurrentPos=Testi;CurrentPos+;CurrentPos+;CurrentPos-;CurrentPos-;Console.Write(Console.Write(输入字符串的反序是：输入字符串的反序是：输入字符串的反序是：输入字符串的反序是：););for(i=0;i Test.Length;i+)for(i=0;i Test.Length;i+)if(CurrentPos 0)if(CurrentPos 0)break;break;Console.Write(strCurrentPos);Console.Write(strCurrentPos);CurrentPos-;CurrentPos-;第17页/共19页第18页/共19页感谢您的观看。第19页/共19页