第8章 数组算法.ppt

1、内容提要,数据分类 数据排序：交换法、选择法、冒泡法、插入法 数据检索：顺序查找、二分法查找 （折半查找 ） 矩阵的常用算法,第8章 数组算法,数据分类,一、数据分类,缺点：程序冗长、占机时多,常用数据分类的方法,利用if语句,利用switch语句,例：随机输入一组数据，数据在1 4之间， 输入结束统计出各类数据的个数。,分析问题给出算法一：,1、输入数据到x,2、判断该数据属于那类，分别记数,4、分别输出a、b、c、d的值,3、反复执行1、2步骤直到数据输完,为1 记入a中,为2 记入b中,为3 记入c中,为4 记入d中,利用if、switch语句,编程方法一：（用基本数据类型）,main(

2、) int i,n,x,a=0,b=0,c=0,d=0,e=0; scanf(“%d”,数组的引入，利用下标为分类（分档）问题提供了一种巧妙的方法，使程序明显简化。,利用if、switch语句,分析问题给出算法二： （用数组）,2、输入数据到x,3、判断该数据属于那类，分别记数,5、分别输出a0 a4的值,4、反复执行2、3步骤直到输入结束,a1中记1的个数,1、设定一个数组a存放统计结果,int a5,a4中记4的个数,a3中记3的个数,a2中记2的个数,ax+=1,main() int a5=0,0,0,0,0,x=1,i=0; while (x) scanf(%d, ,编程方法二：（用数

3、组）,数据排序又称为排队问题。所谓排序就是对一 个数值大小不规则的数列按从小到大（从大到小）的顺序重新组成一个新的数列。,数据排序,常用的排序算法,1：交换法排序（比较法排序、选择法排序） 算法思想： （以升序为例）,举例 原始数据： 8，6，9，2，3 要求：升序,S0Sn-1存放n个无序数，将其升序重新排列。 1.第一趟比较，结束后S0存放最小的数。 S0与S1比较，若S0S1则做交换；S0与S2比较，S0S2则做交换； 2.第二趟比较，结束后S1存放第二小的数。S 1与S 2比较，若S 1 S 2则做交换；S 1与S 2比较，S 1 S 2 ）则做交换； 3.第n-1趟比较， Sn-2与

4、Sn-1比较，Sn-2存放小的，Sn-1存放大的（也是n个数中最大数）。 经过n-1趟比较后，n个数按从小到大的顺序排列。,第 一 趟 比 较 ：,第一趟结束，找到最小值 2,第 二 趟 比 较 ：,第二趟结束，找到第二小值 3,第三趟结果：2 3 6 9 8,第四趟结果：2 3 6 8 9,算法表示：(n为数组元素个数, 升序为 “”) for (i=0;i sortj) temp=sorti ; sorti=sortj; sortj=temp;/*交换*,交换法排序算法,交换法排序 for (i=0; i scorei) 交换成绩scorej和scorei， 交换学号numj和numi；

5、,例：教材P205 例6.3,#include #define ARR_SIZE 40 main() float scoreARR_SIZE, temp1; int n, i, j; long numARR_SIZE, temp2; printf(Please enter total number:); scanf(%d, ,2：选择法排序（直接排序）,算法思想： 特点：比较后不立即互换元素，而是记下其位置并在每一趟比较完毕后和s互换 首先，比较的元素不同，以降序为例，是当前元素与上次比较后的最大元素进行比较，因此，在进行比较之前，要有一个初始化最大元素的过程 其次，确定完毕的元素的互换是在每

6、一轮完成后进行的，而不是在比较后进行的 再次，互换元素的不同，为si和spointer 举例 原始数据： 1，2，3，5，4 要求：降序,第一趟比较，初始化最大元素为 pointer=1 pointer=1 pointer=2 pointer=2 pointer=3 pointer=3 pointer=4 pointer=4 pointer=4 s1 spointer的结果 ,如此下去，第二轮找到，第三轮， 选择法排序的算法表示：,for (i=0;i sortj) pointer=j; if (i!=pointer) temp=sorti ; sort(i)=sortp; sort(p)=t

7、emp; /*交换*/ ,选择法排序,选择法排序 for (i=0; i scorek) 记录此轮比较中最高分的元素下标 k = j; 若k中记录的最大数不在位置i，则 交换成绩scorej和scorei， 交换学号numj和numi； ,选择法排序(直接排序法)算法程序示例(升序)：,#include #define ARR_SIZE 40 void Sort(float score, long num, int n); /*函数声明*/ main() float scoreARR_SIZE; int n, i; long numARR_SIZE; printf(Please enter t

8、otal number:); scanf(%d, ,/*函数功能：用交换法按成绩由高到低对学生成绩及学号重新排序 函数参数： 实型数组score，存储学生成绩 长整型数组num，存储学生学号 整型变量n，代表数组元素个数 函数返回值：无*/ void Sort(float score, long num, int n) int i, j; float temp1; long temp2; for (i=0; i scorei) ; /*交换成绩*/ temp1 = scorej; scorej = scorei; scorei = temp1; /*交换学号*/ temp2 = numj; n

9、umj = numi; numi = temp2; /*if结束*/ /*内层for循环结束*/ /*外层for循环结束*/ /*函数体结束*/,交换法,/*函数功能：用选择法按成绩由高到低对学生成绩及学号重新排序 函数参数：实型数组score，存储学生成绩 长整型数组num，存储学生学号 整型变量n，代表数组元素个数 函数返回值：无*/ void Sort(float score, long num, int n) int i, j, k; float temp1; long temp2; for (i=0; i scorek) k = j; /*内层for循环结束*/ if (k != i

10、) /*若k中记录的最大数序号不是i，即找到的最大数不在位置i*/ /*交换成绩*/ temp1 = scorek; scorek = scorei; scorei = temp1; /*交换学号*/ temp2 = numk; numk = numi; numi = temp2; /*if结束*/ /*外层for循环结束*/ /*函数体结束*/,选择法,：冒泡法排序 算法思想：（升序排序） 1.将相邻两个数比较，把小数对调到前边，如此进行一趟后，就会把最大的数换到最后 2.再进行一次，则会把第二大数排在倒数第二的位置上 3.进行n次后，整个数列即可排好,在这种排序过程中，小数如同气泡一样逐层

11、上浮，而大数逐个下沉，因此，被形象的喻为“冒泡”,举例 原始数据： 9，4，7，5，2 要求：升序,第 一 趟 比 较 ：,第一趟结束，最大值 9沉到最底,第 二 趟 比 较 ：,第二趟结束，次大值7沉到倒数第二,冒泡法的算法表示：OP 升序 (降序),for (i=0;in-1;i+) for (j=0;jn-1-i;j+)/*比较次数逐次减少*/ if (Sj OP Sj+1) t=Sj; Sj=Sj+1; Sj+1=t; /*立即互换*/,第三趟结果：4 2 5 7 9,第四趟结果：2 4 5 7 9,编写程序：数组a0a4，降序，冒泡排序法 初始态：1 2 3 5 4 排序后：5 4

12、3 2 1 用printf()输出 A数组的初始序列：1 2 3 5 4 第1趟:2 3 5 4 1 第2趟:3 5 4 2 1 第3趟:5 4 3 2 1 第4趟:5 4 3 2 1 A数组排序后序列：5 4 3 2 1 课堂作业，将程序写在纸上，并注明学号、姓名，10分钟。,编写程序：数组a0a9，降序，冒泡排序法 初始态：使用随机函数，rand()和srand()，生成10个不同的两位正整数，存入数组a。 用printf()输出 A数组的初始序列： 第1趟: 第2趟: 第3趟: 第4趟: A数组排序后序列： 课堂作业，将程序写在纸上，并注明学号、姓名，10分钟。,4：插 入法排序 算法思

13、想：（升序排序） 将数据一个一个地插入到一个已经有序的数列中，并保证每插入一个数后数列仍然有序，整个排序过程是进行了n-1趟插入。 1.将第i个数x插入前i-1个有序数列，自i-1起往前搜索，并同时后移记录。 2.先将第一个数看成是一个有序数列，然后从第二个数起逐个进行插入，进行n次插入后，整个数列即可排好,举例 原始数据： 9，4，7，5，2 要求：升序,第 一 趟 插 入：第2个数4插入有序数列9中,第一趟结束，前2个数排成有序数列4 9,9 4 7 5 2,4 9 7 5 2,4 9 7 5 2,4 7 9 5 2,第二趟结束，前3个数排成有序数列4 7 9,第 二 趟 插 入：第3个数

14、7插入有序数列4 9中,第二趟结果： 4 7 9 5 2,第一趟结果：4 9 7 5 2,第 三 趟 插 入：第4个数5插入有序数列4 7 9中,第三趟结束，前4个数排成有序数列4 5 7 9,4 7 9 5 2,4 5 7 9 2,4 5 7 9 2,2 4 5 7 9,第四趟结束，前5个数排成有序数列2 4 5 7 9,第 四 趟 插 入：第5个数2插入有序数列4 5 7 9中,第四趟结果：2 4 5 7 9,第三趟结果： 4 5 7 9 2,插入法的算法表示：OP 升序 (降序),for (i=1;i=0;j-) /*前i-1个数是有序数*/ if (sj OP x) sj+1=sj;

15、else break; /*退出for (j=i-1;j=0;j-)循环*/ sj+1=x;,算法一,算法二,插入法的算法表示：OP 升序 (降序),int i,j,x, pos; for (i=1;i= pos; j-) aj+1 = aj; /*向后移动*/ apos = x; /*插入元素x到位置pos*/ ,编写程序：数组a(1)a（5），升序，插入排序法 初始态：9 4 7 5 2 排序后：2 4 5 7 9 用printf()输出 A数组的初始序列：9 4 7 5 2 第1趟:4 9 7 5 2 第2趟:4 7 9 5 2 第3趟:4 5 7 9 2 第4趟:2 4 5 7 9 A

16、数组排序后序列：2 4 5 7 9 课堂作业，将程序写在纸上，并注明学号、姓名，10分钟。,编写程序：数组a0a9，降序，插入排序法 初始态：使用随机函数，rand()和srand()，生成10个不同的两位正整数，存入数组a。 用printf()输出 A数组的初始序列： 第1趟: 第2趟: 第3趟: 第4趟: A数组排序后序列： 课堂作业，将程序写在纸上，并注明学号、姓名，10分钟。,使用子函数 Void Input(） Void Sort() Void Output(),常用的查找算法,1： 顺序查找 算法思想： 1.顺序查找表现是把待查找的数与数组中的数从头到尾逐一比较 2.用一变量 i

17、来表示当前比较的位置，初始为0，当待查找的数与数组中 i 位置的元素相等时即可结束,否则 i=i+1 继续比较，当 i大于 数组的最大长度,也应该结束 注意退出的两种情况，分别为找到和未找到（i大于数组的最大长度）,特例：求最大值，求最小值,数据检索,int Search(long a, int n, long x) int i; for (i=0; in; i+) if (ai = x) return (i); return (-1); ,顺序查找的算法表示（为待查找的数）：,for (i=0; in; i+) if (ai = x) /*退出的两种情况*/ return (i); /*找到

18、*/ return (-1); /*没找到*/,教材P214例6.5,对于无序数组，顺序查找是唯一可行的办法 对大批量数据用顺序查找占机器时间较多。,#include #define ARR_SIZE 40 int Search(long a, int n, long x); /*函数声明*/ main() float scoreARR_SIZE; int n, i, pos; long numARR_SIZE, x; printf(Please enter total number:); scanf(%d, /*打印未找到提示信息*/ ,/*函数功能： 在有n个元素的数组a0,a1,an-1

19、中顺序查找值为x的元素 函数入口参数：长整型数组a，存储待查数组元素 整型变量n，代表数组元素个数 长整型变量x，代表待查数据 函数返回值：若找到，则函数返回x在数组a中的下标位置，若找不到，则返回-1 */ int Search(long a, int n, long x) int i; for (i=0; in; i+) /*在数组a中查找值为x的元素*/ /*若ai等于x，则返回x在数组a中的下标位置*/ if (ai = x) return (i); return (-1); /*若循环结束仍未找到，则返回 -1*/ ,2: 二分（折半）查找 算法思想 折半查找法是对有序数列进行查找的

20、一种高效查找办法。其基本思想是逐步缩小查找范围，因为是有序数列，所以采取半分作为分割范围，可使比较次数最少. 比较过程: 设置三个指针,分别指向数组序列 s 的low,high和middle,其中middle=(low+high)/2,进行下列判断 1)若待查找的数 x 等于s(middle),则已经找到,位置就是middle.否则进行下面的判断.,2)如果 x 小于 s(middle),因为是有序数列,则 x 必定落在low 和 middle-1的范围之内,下一步查找只需在此范围之内进行即可.即low位置不动,high= middle-1.重复 1) 即可. 3) 如果 x 大于 s(mid

21、dle),则 x 必定落在 middle+1 和 high之间,下一步查找范围应该是 low=middle+1 和 high,设定完low后即可转到 1) 继续判断. 注意: 在此循环过程中,low,high,middle都是表示位置的整数,如果循环到 lowhigh,则表明此数列中没有我们要找的数.应该退出循环.,折半查找,int BinSearch(long a, int n, long x) int low, high, mid; low = 0; high = n - 1; while (low amid) low = mid + 1; else if (x amid) high =

22、mid - 1; else return (mid); return(-1); ,二分查找的算法表示：,1、插入数据 在有序数组中插入数据后，数组仍然有序。 要求数组有足够的空间。,前提：被操作数组已经是有序数组，操作前后不改变数组的有序性,数组元素的插入、删除算法,插入过程： (1) 确定数据插入位置 (2) 从最后一个元素开始逐个后移，直到将第i个位置腾出。 (ai+1=ai) (3) 将数据插入到指定下标元素位置中,插入运算,ai-1,.,a1,a0,alength,ai+1,ai,x,x,例：插入数据,关键是：找到该插入的位置，然后依次移动插入位置及其后的所有元素腾出这一位置放入待插入

23、的元素,例：向有序的数组中插入数据,void Inseart(int a, int n, int x) int i, pos; for (i=0; (i ai); i+) pos = i; for (i = n-1; i = pos; i-) ai+1 = ai; /*向后移动*/ apos = x; /*插入元素x到位置pos*/ ,2、删除数据 在有序的数组中删除数据后，数组仍然有序。,删除过程： (1) 确定数据删除位置i (2)从第i1个位置开始逐个向前移动原数组元素，(ai=ai+1),这一章我们学到了,了解了在什么情况下使用数组这种数据类型 向函数传递一维数组和二维数组的方法 用数组名作为函数参数和用简单变量作为函数参数的不同之处 数据排序：交换法、选择法、冒泡法、插入法 数据检索：顺序查找、二分法查找 （折半查找 ） 数据分类,习题,P240 习题8.1、8