第03章 数组及其应用资料.ppt

3.3.1 数组元素值的随机生成 例3-7 随机生成20个3位以内的整数序列存放在一维数组中，然后按每行5个数输出所有数组元素。 程序一次运行结果为： 659 100 184 135 876 348 934 293 587 338 179 243 523 799 653 234 657 439 776 297 3.3.1 数组元素值的随机生成 例3-8 编程序实现如图3.10所示的矩阵转置功能，即将N×M矩阵转换为M×N矩阵；要求被处理的二维数组元素值（2位数以内）随机产生。 矩阵转置 冒泡排序（一维数组的应用） ①从较待排序列中第一个位置开始，依次比较相邻两个位置上的记录，若是逆序则交换，一趟扫描后，关键字值最大（或最小）的记录则交换到了最右边； ②不考虑已排好序的记录，将剩下的记录作为待排序列；重复①、②两步直到排序完成； ③n个记录的排序最多进行n-1趟比较，在第1趟比较中要进行n-1次两两比较，在第i趟比较中要进行n-i次两两比较。 3.3.2 数组的常用排序方法 将6个数进行冒泡排序(以升序为例) 第一趟比较中,进行了5次比较:(最大数下沉) 5 5 5 5 5 5 6 6 2 2 2 2 2 2 6 6 6 6 9 9 9 9 9 9 10 10 10 10 10 3 3 3 3 3 3 10 1次 2次 3次 4次 5次 结果 3.3.2 数组的常用排序方法 余下5个数进行排序 第二趟比较中,进行了4次比较:(次大数下沉) 5 2 2 2 2 2 5 5 5 5 6 6 6 6 6 9 9 9 9 3 3 3 3 3 9 1次 2次 3次 4次 结果 3.3.2 数组的常用排序方法 例3-9 编程实现冒泡排序算法，对随机生成的20 个整数按升序排序并输出。 总结： n个数据的排序最多进行n-1趟比较，在第1趟比较中要进行n-1次两两比较，在第i趟比较中要进行n-i次两两比较。 3.3.2 数组的常用排序方法 选择排序（交换排序的优化） 假设具有n个元素的数组a中用a[0]存放最小(或最大)的数，将此数与后面所有的数比较并用下标变量k记录最小(或最大)数所在位置。一趟比较完成后，将a[0]与a[k]交换。 在剩下的N-1个数据 (即a[1]到a[n-1]的元素)中使用相同的方法寻找最大（或最小）的数，并将a[1]与a[k]交换；以此类推,直到将整个待排数据集合处理完。 例3-10 编程序实现选择排序算法，对随机生成的20个整数按升序进行排序并输出。 将6个数进行选择排序（定义a[6],i=0～5） 在a[0]到a[5]数组元素中找最小数 a[0] a[1] a[2] a[3] a[4] a[5] 5 6 2 9 10 3 3.3.2 数组的常用排序方法 把k更新为2记下较小数下标 ①a[0]与a[2]交换后， a[0]中已是最小数2 在余下a[1]到a[5]数组元素中又找最小数 a[1] a[2] a[3] a[4] a[5] 6 5 9 10 3 ②将a[1]与a[5]交换 K更新为5 5 5 6 2 3 6 令k=i=0 令k=i=1 K更新为2 判断k==i？相等则a[0]中就是最小数，不相等则交换a[0]与a[k]值，以保证a[0]中存放序列的最小数。 3.3.3 数组的常用查找方法 顺序查找（线性查找） 从数组首元素或最后一个元素开始，往后或往前顺序比较每一个数组元素值是否等于查找关键字；如果找到相符合的元素值，则查找成功，否则,查找失败。顺序查找适应于被查找集合无序的场合。 例3-11 编程序实现顺序查找算法，在随机生成的20个整数中查找指定值，要求程序能够显示出查找进行比较的次数以及本次查找成功与否。 3