C++课件第6章 数组.pptVIP

第6章 数 组 学习目标 掌握数组的定义与使用方法，学会利用数组编写程序。 掌握数组元素的初始化方法。 掌握字符数组处理字符串的技巧。 熟悉字符串处理函数的功能及使用方法。 掌握数组作为函数参数的使用方法。 6 数组 在需要处理一批具有相同类型而且又有密切关联的数据时，数组是一个非常有用的可构造的数据类型(派生数据类型) 。 派生数据类型：由已有的基本数据类型（char, float, double, …)或已构造的数据类型构造出的新类型。 6.1.1 一维数组的定义 int grades[5]; char codes[4]; double price[6]; 6.1.1 一维数组的定义 6.1.2 一维数组的初始化 一维数组的初始化： 在定义数组的同时给数组元素赋初值称为数组的初始化。其语法格式为： 类型 数组名[常量表达式]={初值1, 初值2, …, 初值n} 6.1.4 一维数组的应用 例: 将下列 10 个数按由小到大的顺序排列输出。 15，8，0，-6，2，39，-53，12，10，6 选择排序 第 1 次：在第 1 到第 n 个数中选出最小的，换到第 1 个位置； 第 2 次：在第 2 到第 n 个数中选出最小的，换到第 2 个位置; 第 i 次：在第 i 到第 n 个数中选出最小的，换到第 i 个位置; i=1, 2, …, n-1 共 n-1 次。 for (i=0; in-1; i++){ 在第 i 到第 n-1 个数中选出最小的； 换到第 i 个位置； } #include iostream using namespace std; int main(void){ const int n = 9; int a[n] = {15,8,0,-6,2,39,-53,12,10,6}; int i, j, minValue, minIndex, temp; for(i = 0; i n - 1; i++){ //外层循环控制轮次 minValue = a[i]; //假设排头数据最小 minIndex = i; 在第 i 到第 n-1 个数中选出最小的； 换到第 i 个位置； } for(i = 0; i n; i++) //输出排序后的数据 couta[i]\t; coutendl; } 6.1.4 一维数组的应用 冒泡排序： 第 0 次：将第 0 到第 n-1 个数两两比较，使大的下沉，小的上浮，最大数沉到第 n-1 个位置； 第 1 次：将第 0 到第 n-2 个数两两比较，使大的下沉，小的上浮，最大数沉到第 n-2 个位置; 第 i 次：将第 0 到第 n-i-1 个数两两比较，使大的下沉，小的上浮，最大数沉到第 n-i-1 个位置; i=0, 1, …, n-2 共 n-1 次。 for (i=0; in-1; i++){ 将 0 到 n-i-1 个数两两比较，使大的下沉，小的上浮； } #include iostream.h void main(void) { int a[10]={ 15, 8, 0, -6, 2, 39, -53, 12, 10, 6 }; int i, j, temp; for (i=0; i9; i++) 将 0 到 n-i-1 个数两两比较 大的下沉，小的上浮； for (i=0; i10; i++) couta[i]\t; coutendl; } 例: 在有序数列 { -56，-23，0，8，10，12，26，38，65，98 } 中，查找数据 38 是否存在。 两分查找： 两分查找也称折半查找。其方法是将有序数列逐次折半，并确定折半的数据位置，用待查找的数据与其比较，若相等则查找成功。否则比较两数的大小，如果待查找的数据比折半位置的数据小，那么到前半区间继续查找，否则到后半区间继续查找。 算法： 将有序数列存放在数组 s 中。 设置3个标记，low 指向待查区间的底部，high 指向待查区间的顶部，binary 指向折半的位置，即待查区间的中部：binary=(low+high)/2 比较待查数据 x 与 s[binary] 是否相等，若相等，则查找成功并结束查找；若 xs[binary]，说明 x 在 [low, binary]（前半区间）范围内，令 high=binary-1；若 xs[binary]，