C语言程序设计课件：第4章-数组2(总例题习题).ppt

1、2022-1-222【例例】写出下面程序的运行结果写出下面程序的运行结果max=75程序举例例 读10个整数存入数组，找出其中最大值和最小值步骤:1. 输入:for循环输入10个整数2. 处理:(a) 先令max=min=x0(b) 依次用xi和max,min比较(循环) 若xi max,令max=xi 若xi min,令min=xi3. 输出:max和min #include #define SIZE 10main() int xSIZE,i,max,min; printf(Enter 10 integers:n); for(i=0;iSIZE;i+) printf(%d:,i+1);sca

2、nf(%d,&xi); max=min=x0; for(i=1;imax) max=xi; if(xi min) min=xi; printf(Maximum value is %dn,max); printf(Minimum value is %dn,min);2022-1-224 3 5 8 1 6 9 7 12-6 0 0 0要点：用两要点：用两重循环遍历重循环遍历所有元素。所有元素。【讨论】【讨论】 如果求最小如果求最小值？值？ 2022-1-225定义并初始化数组定义并初始化数组for (i=2;i40;i+ )fi=fi-1+fi-2for (i=0;i40;i+ )i%5=0NY

3、打印换行打印换行打印打印fifn=1 n=1,2fn-1+fn-2 n31 1 2 3 5 8 0,122022-1-226f0f1f2f3f4f5f39.11014523392352022-1-227main() int a55,i,j; for (i=0;i5;i+) for (j=0;j5;j+) if ( 【1】 ) aij=0; else aij=【2】; printf(%3d,aij); printf(n); 2022-1-228【分析】分析】这类题的元素值排列很有规律，一般要这类题的元素值排列很有规律，一般要从分析行列数从分析行列数 i、 j与元素值的关系着手与元素值的关系着手.

4、 .当当 i=j时时，元素值，元素值随行数随行数 i i 增加而增加，随列数增加而增加，随列数 j 增加而减小，增加而减小，这样就很容易得出其元素值与这样就很容易得出其元素值与 i，j 的关系是的关系是 i+1-j。a55分析分析: :a00 a01 a02 a03 a04a10 a11 a12 a13 a14a20 a21 a22 a23 a24a30 a31 a32 a33 a34a40 a41 a42 a43 a442022-1-229main() int a55,i,j; for (i=0;i5;i+) for (j=0;j5;j+) if ( 【1】 ) aij=0; else ai

5、j=【2】; printf(%3d,aij); printf(n); ij i+1-j a55分析分析: :a00 a01 a02 a03 a04a10 a11 a12 a13 a14a20 a21 a22 a23 a24a30 a31 a32 a33 a34a40 a41 a42 a43 a442022-1-22102022-1-22112022-1-22122022-1-22132022-1-22141 2 3 4 5 6 7 82022-1-22151 2 3 4 5 6 7 81 2 32022-1-22164 5 6 7 81 2 32022-1-22174 5 6 7 8 1 2

6、31 2 32022-1-22182022-1-22191 2 3 4 5 6 7 8182022-1-22208 2 3 4 5 6 7 1 2022-1-22218 7 3 4 5 6 2 12022-1-22228 7 6 5 4 3 2 12022-1-22231 2 3 4 5 6 7 83 2 1 4 5 6 7 83 2 1 8 7 6 5 48 7 6 5 4 3 2 12022-1-2224【例例】求出求出3 3100100之间的所有素数之间的所有素数( (质数质数) )思路：思路：定义函数定义函数int isPrimeint isPrime（int xint x），判断整数

7、是否为素数。），判断整数是否为素数。 对所有小于对所有小于x x的整数的整数i i判断，当所有的判断，当所有的i i都不被都不被x x整除时，整除时，x x为为 素数。素数。对对3-1003-100间的所有数字调用函数间的所有数字调用函数isPrimeisPrime（int xint x），判断是），判断是否为素数。否为素数。能否改进？能否改进？2022-1-2225【例例】求出求出3 3100100之间的所有素数之间的所有素数( (质数质数) )3 35 57 79 911111313151517171919212123232525272729293131333335353737393941

8、4143434545思路：思路：定义一个数组定义一个数组prime49,prime49,存储下奇数：存储下奇数： 3 3、5 5、7 7、9 9、1111、13951395、9797、9999从从第第0 0个元素个元素开始，其后的各个元素若是第开始，其后的各个元素若是第0 0个元个元 素的倍数，则将其值素的倍数，则将其值置为置为0 0，表示该元素不是素数，表示该元素不是素数再从第一个元素开始再从第一个元素开始一直到从一直到从第第4747个元素个元素开始，其后元素如是第开始，其后元素如是第4747个个 元素的倍数，则将其值置位元素的倍数，则将其值置位0 0这时这时数组数组primeprime中不

9、为中不为0 0的元素是素数的元素是素数数组数组prime49存储奇数存储奇数 3、5、7、997、99如果如果primei不为不为0，表示，表示是素数，每行输出是素数，每行输出5个元素个元素 如果数组元素如果数组元素primej不不整除它之前所有的元素整除它之前所有的元素 primei，则它就是素数，则它就是素数2022-1-2227排序基本概念排序基本概念1、排序的功能：、排序的功能：将一个数据元素（或记录）的将一个数据元素（或记录）的任意任意序列序列，重新排成一个按关键字，重新排成一个按关键字有序有序的序列。的序列。2、排序过程的组成步骤：、排序过程的组成步骤： 首先首先比较比较两个关键字

10、的大小；两个关键字的大小； 然后将记录从一个位置然后将记录从一个位置移动移动到另一个位置。到另一个位置。2022-1-22282022-1-2229数据的有序插入算法数据的有序插入算法插入数据插入数据 在有序数组中插入数据后，数组仍然有序。在有序数组中插入数据后，数组仍然有序。 要求数组有足够的空间。要求数组有足够的空间。前提：被操作数组已经是有序数组，操作前前提：被操作数组已经是有序数组，操作前后不改变数组的有序性后不改变数组的有序性2022-1-2230 插入过程：插入过程：(1) 确定数据插入位置确定数据插入位置(2) 从最后一个元素开始逐个后移，直从最后一个元素开始逐个后移，直到将第到

11、将第i个位置腾出。个位置腾出。(3) 将数据插入到相应位置中将数据插入到相应位置中2022-1-2231 插入运算插入运算ai-1.a1a0alength ai+1aikey ai-1. a1 a0 ai ai+1 alength alength ai+1 aikey 2022-1-22322022-1-22332022-1-2234数组插入排序初始化数组插入排序初始化2022-1-2235插入排序插入排序:基本思想：基本思想：从数组的第从数组的第2号元素开始，顺序从数组中取出元素，号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上并将该元素插入到其左端已排好序

12、的数组的适当位置上待排元素序列：待排元素序列：53 27 36 15 69 42第一次排序：第一次排序： 27 53 36 15 69 42第二次排序：第二次排序： 27 36 53 15 69 42第三次排序：第三次排序： 15 27 36 53 69 42第四次排序：第四次排序： 15 27 36 53 69 42第五次排序：第五次排序： 15 27 36 42 53 69 线性插入排序示例线性插入排序示例对于有对于有n个数个数据元素的待排据元素的待排序列，插入操序列，插入操作要进行作要进行n-1次次2022-1-22362022-1-2237输出原始数据输出原始数据输出排序后的数据输出排

13、序后的数据2022-1-2238排序过程：排序过程：（1）首先通过）首先通过n-1次比较，从次比较，从n个数中找出最小个数中找出最小(大大)的，的， 将它与第一个数交换将它与第一个数交换第一趟选择排序第一趟选择排序，结果，结果最小最小(大大)的数被安置在第一个元素位置上的数被安置在第一个元素位置上（2）再通过）再通过n-2次比较，从剩余的次比较，从剩余的n-1个数中找出关键字个数中找出关键字次次小小(大大)的记录，将它与第二个数交换的记录，将它与第二个数交换第二趟选择排序第二趟选择排序（3）重复上述过程，共经过）重复上述过程，共经过n-1趟排序后，排序结束趟排序后，排序结束2022-1-223

14、9k=1k=2k=0k=12022-1-2240k=2k=4k=3k=42022-1-2241例初始： 49 38 65 97 76 13 27 kji=01349一趟： 13 38 65 97 76 49 27 i=12738二趟： 13 27 65 97 76 49 38 三趟： 13 27 38 97 76 49 65 四趟： 13 27 38 49 76 97 65 五趟： 13 27 38 49 65 97 76 六趟： 13 27 38 49 65 76 97 kkkkjjjjjjjjjj从小到大排序从小到大排序例： 数组排序-选择排序main() int a10,i; for(i

15、=0;i10;i+)scanf(%d,&ai); sort_select(a,10); for(i=0;i10;i+) printf(%d ,ai); printf(n);0123456789a4968573299927137688 x首地址20000123456789a9132732495768768899x首地址20002022-1-2244思想：思想：小的浮起，大的沉底。小的浮起，大的沉底。从左端开始比较。从左端开始比较。第一趟：第一趟：第第1个与第个与第2个比较，大则交换；第个比较，大则交换；第2个个与第与第3个比较，大则交换，个比较，大则交换，关键字最大关键字最大的的记录交换到记录交

16、换到最后一个位置最后一个位置上；上；第二趟：第二趟：对前对前n-1个记录进行同样的操作，个记录进行同样的操作，关键关键字次大字次大的记录交换到第的记录交换到第n-1个个位置上；位置上； 依次类推，则完成排序。依次类推，则完成排序。2022-1-2245初始值初始值 46 55 13 42 94 5 17 70第一趟第一趟 46 13 42 55 5 17 70 94 第二趟第二趟 13 42 46 5 17 55 70 94 第三趟第三趟 13 42 5 17 46 55 70 94 第四趟第四趟 13 5 17 42 46 55 70 94 第五趟第五趟 5 13 17 42 46 55 7

17、0 94 46 13 55 42 94 5 17 7046 13 42 55 94 5 17 7046 13 42 55 5 94 17 7046 13 42 55 5 17 94 702022-1-22462022-1-2247输出原始数据输出原始数据输出排序后数据输出排序后数据2022-1-22482022-1-22492022-1-22502022-1-2251思想：先确定待查找记录所在的范围，然后逐步缩小范思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。围，直到找到或确认找不到该记录为止。前提：必须在前提：必须在有序表有序表中进行。中进行。分三种情况

18、：分三种情况：1 1）若中间项的值等于）若中间项的值等于k,k,则说明已查到。则说明已查到。2 2）若）若k k小于中间项的值，则在线性表的前半部分查找；小于中间项的值，则在线性表的前半部分查找；3 3）若）若k k大于中间项的值，则在线性表的后半部分查找。大于中间项的值，则在线性表的后半部分查找。2022-1-2252mid=(low+high)/2 不进位取整不进位取整low：下界下界high ：上界上界k=amid : 查找成功，返回查找成功，返回midkamid : low=mid+1 继续继续lowhigh : 查找不成功查找不成功2022-1-2253 8 17 25 44 68

19、77 98 100 115 125 查找查找 k=170 1 2 3 4 5 6 7 8 9mid=(0+9)/2=4mid=(0+3)/2=1lowhighmidmid=(low+high)/2 8 17 25 44 68 77 98 100 115 125lowhigh=mid-1mid查找成功！查找成功！ 8 17 25 44 68 77 98 100 115 125 查找查找k=1200 1 2 3 4 5 6 7 8 9lowhighmidmid=(0+9)/2=4 8 17 25 44 68 77 98 100 115 125 highlowmidmid=(5+9)/2=7 8 1

20、7 25 44 68 77 98 100 115 125 highlowmidmid=(8+9)/2=8 8 17 25 44 68 77 98 100 115 125 highlowmidmid=(9+9)/2=9 8 17 25 44 68 77 98 100 115 125highlowmid因为因为125120所以所以high= mid -1highlow 查找失败查找失败查找失败！查找失败！2022-1-2255函数入口参数函数入口参数找到时返回找到时返回下标位置下标位置找不到时找不到时 返回返回-1-12022-1-22562022-1-22572022-1-2258a= 1 2 3 8 12 15 元素个数为元素个数为m=6b= 2 3 7 9 元素个数为元素个数为n=4c= pqk1p2pq3pq7q8p9q12p15pkkkkkkkk0 1 2 3 4 5 6 7元素个数为元素个数为k=82022-1-22602022-1-2261mm nCA+ Bnm n2022-1-2262pnnmpmBAC2022-1-2263在一个矩阵的行中最大，列中最小的元素在一个矩阵的行中最大，列中最小的元素2022-1-22642022-1-2265每行、每列、及两条对角线上的和相等每行、每列、及两条对角线上的和相等2022-1-2266