计算机网络讲义 第5章 批量数据处理—数组 一维数组 排序和查找 二维数组 字符串.

Presentation on theme: "计算机网络讲义 第5章 批量数据处理—数组 一维数组 排序和查找 二维数组 字符串."— Presentation transcript:

1 计算机网络讲义 第5章 批量数据处理—数组 一维数组 排序和查找 二维数组 字符串

2 一维数组 有时，我们需要存储一批同类型的数据，如有十只羊，主人要保存每只羊的重量，并从中挑选一只最肥的羊。
计算机网络讲义 一维数组 有时，我们需要存储一批同类型的数据，如有十只羊，主人要保存每只羊的重量，并从中挑选一只最肥的羊。 解决方案：可以定义十个double型的变量sheep1, …,sheep10，然后比较十个值，找出一个最大值。 缺点： 定义了十个变量。要是有100只羊就要定义100个变量 程序只能用顺序结构 如果羊群规模发生变化，程序就得重写

3 数组 数组是保存一组同类元素的数据类型，它有两个特征： 定义数组要定义三个基本内容： 数组元素是有序的 数组元素是同类的 数组名字
计算机网络讲义 数组 数组是保存一组同类元素的数据类型，它有两个特征： 数组元素是有序的 数组元素是同类的 定义数组要定义三个基本内容： 数组名字 数组元素的类型 数组的大小

4 数组的定义 格式： 类型 数组名[元素个数]； 其中，元素个数必须是常量。如： int intarray[10]; 但 int n=10;
计算机网络讲义 数组的定义 格式： 类型 数组名[元素个数]； 其中，元素个数必须是常量。如： int intarray[10]; 但 int n=10; int intarray[n]; 是错的 常用的方法是将元素个数定义为一个常量。如： #define NumOfElement 10 int intarray[NumOfElement]; 相当于

5 初始化 定义数组时可以对数组初始化 float x[5] = { -1.1, 0.2, 33.0, 4.4, 5.05 };
计算机网络讲义 初始化 初始化表 定义数组时可以对数组初始化 float x[5] = { -1.1, 0.2, 33.0, 4.4, 5.05 }; 初始化表的长度短于要被初始化的数组元素数目，那么剩余元素被初始化为0。 带有初始化的数组可以不定义数组规模，编译器根据初值的个数决定数组的大小 int a[]={1,2,3,4,5}; 则默认数组大小为5

6 数组元素 数组元素的使用是通过数组名及元素的序号来指定，如intarray[2]。当数组的大小为n时，元素的序号为0 – n-1。
计算机网络讲义 数组元素 数组元素的使用是通过数组名及元素的序号来指定，如intarray[2]。当数组的大小为n时，元素的序号为0 – n-1。 元素的序号称为下标。程序中，下标可为整数、整型变量或结果为整型的任意表达式。正是这一特性，使得数组的应用非常灵活。

7 数组在内存中 定义数组就是定义了一块连续的空间，空间的大小等于元素数*每个元素所占的空间大小。 数组元素按序存放在这块空间中。
计算机网络讲义 数组在内存中 定义数组就是定义了一块连续的空间，空间的大小等于元素数*每个元素所占的空间大小。 数组元素按序存放在这块空间中。

8 计算机网络讲义 为数组分配空间 如： int intarray[5];占用了20个字节，因为每个整型数占四个字节。如给intarray[3]赋值为3，如果这块空间的起始地址为100，那么在内存中的情况是： 当你引用变量intarray[idx]时，系统计算它的地址100+idx*4，对该地址的内容进行操作。 随机值 3

9 计算机网络讲义 数组下标超界问题 C/C++语言不检查数组下标的超界。如定义数组 int intarray[10]; 合法的下标范围是0 – 9，但如果你引用intarray[10]，系统不会报错。如数组intarray 的起始地址是1000，当引用intarray[10]时，系统对1040号内存进行操作。而1040可能是另一个变量的地址 解决方法：由程序员自己控制。在对下标变量进行操作前，先检查下标的合法性。

10 数组的操作 数组的操作主要是数组元素的操作。
计算机网络讲义 数组的操作 数组的操作主要是数组元素的操作。 不能直接对数组名进行赋值。如：intarray=30 是错的。事实上，数组名中存放的是该数组的起始地址。 eg. 数组的输入输出 int main() {int intarray[10], idx; for (idx = 0; idx <= 9; ++idx) cin >> intarray[idx] ; cout << endl; for ( idx = 0; idx <= 9; ++idx) cout << intarray[idx]; }

11 数组应用—羊群问题 int main() {double sheep[10], max=0; int i, maxNum;
计算机网络讲义 数组应用—羊群问题 int main() {double sheep[10], max=0; int i, maxNum; for (i=0; i<10; ++i) { cout << “请输入第” << i <<“只羊的重量”; cin >> sheep[i];} for (i=0; i<10; ++i) if (sheep[i]>max) { max = sheep[i]; maxNum = i; } cout << “最重的羊是第” << maxNum << “只”<< endl; cout << “它的重量是” << max << endl; return 0; }

12 使羊群问题的程序更通用 方案一：可以将羊的个数定义成一个符号常量。需要时，可以修改这个符号常量的值
计算机网络讲义 使羊群问题的程序更通用 方案一：可以将羊的个数定义成一个符号常量。需要时，可以修改这个符号常量的值 方案二：定义一个足够大的数组存放羊群的信息，定义一个输入结束标志，用while循环解决这个问题。可参照分数统计程序

13 方案一 #define NUM 10 int main() {double sheep[NUM], max=0;
计算机网络讲义 方案一 #define NUM 10 int main() {double sheep[NUM], max=0; int i, maxNum; for (i=0; i<NUM; ++i) { cout << “请输入第” << i <<“只羊的重量”; cin >> sheep[i];} if (sheep[i]>max) { max = sheep[i]; maxNum = i; } cout << “最重的羊是第” << maxNum << “只”<< endl; cout << “它的重量是” << max << endl; return 0; }

14 数组应用 从终端输入一串字符，统计字符串中个字母出现的次数。 解决方法： 就可以了。
计算机网络讲义 数组应用 从终端输入一串字符，统计字符串中个字母出现的次数。 解决方法： 方法一：用26个整型变量计数26个字母，对输入字符串中的每一字符用switch语句分别计数。 方法二：用一个26个元素的数组，如num[26], 表示计数。num[0]存放a的个数, num[1]存放b的个数…。这样对每一个字符不必用switch，而只需用一个简单的计算： ++num[toupper(ch) - ’A’]; 就可以了。

15 #include <iostream> #include <ctype.h>
计算机网络讲义 #include <iostream> #include <ctype.h> using namespace std; int main() { int count[26] = {0}, i; char ch; ch = toupper(cin.get()); while (ch>='A' && ch <='Z') {++count[ch-'A']; ch = toupper( cin.get()); } for (i=0; i< 26; ++i) cout << count[i] << '\t'; return 0; }

16 计算机网络讲义 第5章 批量数据处理—数组 一维数组 排序和查找 二维数组 字符串

17 计算机网络讲义 排序和查找 顺序查找 二分查找 选择排序法 气泡排序法

18 顺序查找 被查找的数存放在一个数组中 从数组的第一个元素开始，依次往下比较，直到找到要找的元素为止。 如在一整数数组中查找元素x的存储位置。
计算机网络讲义 顺序查找 被查找的数存放在一个数组中 从数组的第一个元素开始，依次往下比较，直到找到要找的元素为止。 如在一整数数组中查找元素x的存储位置。

19 cout << "请输入要查找的元素值："; cin >> x;
计算机网络讲义 int main() { int k, x; int array[ ] = { 2, 3, 1, 7, 5, 8, 9, 0, 4, 6}; cout << "请输入要查找的元素值："; cin >> x; for (k = 0; k < 10; ++k) if (x == array[k]) { cout << k; break;} if (k == 10) cout << "not found"; return 0; }

20 计算机网络讲义 排序与查找 顺序查找 二分查找 选择排序法 气泡排序法

21 二分查找 数组元素已按某一顺序排序，如数字的大小顺序、字母的字母序等。以下讨论中都假设是按升序排序。 过程：
计算机网络讲义 二分查找 数组元素已按某一顺序排序，如数字的大小顺序、字母的字母序等。以下讨论中都假设是按升序排序。 过程： 设定查找范围的上下界：lh, rh 找出中间元素的位置：mid = ( lh + rh ) / 2 比较中间元素与欲查找的元素 key。如 key 等于中间元素，则 mid 就是要查找的元素的位置；如 key > 中间元素，则从 lh – mid 的这些元素不可能是要查找的元素，修正查找范围为 lh = mid + 1到 rh；如key < 中间元素，则从mid - rh的这些元素不可能是要查找的元素，修正查找范围为 lh 到 rh = mid - 1；如 lh > rh，则要查找的元素不存在，否则返回第二步。 如在数组 CityTable 中查找元素 San Francisco 的过程如下所示。

22 二分查找过程 Atlanta 1 Boston 2 Chicago 3 Denver 4 Detroit 5 Houston 6
计算机网络讲义 二分查找过程 Atlanta 1 Boston 2 Chicago 3 Denver 4 Detroit 5 Houston 6 Los Angeles 7 Miami 8 New York 9 Philadelphia 10 San Francisco 11 Seattle Seattle 11 San Francisco 10 Philadelphia 9 New York 8 Miami 7 Los Angeles 6 Houston 5 Detroit 4 Denver 3 Chicago 2 Boston 1 Atlanta Seattle 11 San Francisco 10 Philadelphia 9 New York 8 Miami 7 Los Angeles 6 Houston 5 Detroit 4 Denver 3 Chicago 2 Boston 1 Atlanta

23 二分查找程序 int main() {int lh, rh, mid, x;
计算机网络讲义 二分查找程序 int main() {int lh, rh, mid, x; int array[ ]={0,1,2,3,4,5,6,7,8,9}; cout <<"请输入要查找的数据："; cin >> x; lh = 0; rh = 9; while ( lh <= rh ) { mid = ( lh + rh ) / 2; if ( x== array[mid] ) { cout << x << "的位置是：" << mid << endl; break; } if ( x < array[mid]) rh = mid - 1; else lh = mid + 1; } if (lh > rh) cout << "没有找到" << endl; return 0;

24 搜索算法的效率 顺序搜索的平均时间性能 （1 + 2 + 3 + … + n ) / n = ( n + 1 ) / 2
计算机网络讲义 搜索算法的效率 顺序搜索的平均时间性能 （ … + n ) / n = ( n + 1 ) / 2 二分查找的最坏情况的时间性能 n / 2 / 2 … / 2 / 2 = 1 k=log2n K次

25 计算机网络讲义 N和log2N的值 N log2N 10 3 100 7 1000 1,000,000 20 1,000,000,000 30

26 计算机网络讲义 排序与查找 顺序查找 二分查找 选择排序法 气泡排序法

27 选择排序 使数组元素按某种次序排列 选择排序法： 用伪代码表示 在所有元素中找到最小的元素放在数组的第0个位置
计算机网络讲义 选择排序 使数组元素按某种次序排列 选择排序法： 在所有元素中找到最小的元素放在数组的第0个位置 在剩余元素中找出最小的放在第一个位置。以此类推，直到所有元素都放在适当的位置 用伪代码表示 int lh, rh, array; 输入要排序的元素，存入array; for (lh = 0; lh < n; lh++) {在array的从lh到n – 1的元素之间找出最小的放入rh; 交换下标 lh和 rh中的值;} 输出排好序的元素;

28 计算机网络讲义 选择排序实例 31 41 59 26 53 58 97 93 93 97 58 53 31 59 41 26 已正确定位 93 97 58 53 41 59 31 26 已正确定位 93 97 58 53 59 41 31 26 已正确定位

29 选择排序的完善 int main( ) { int lh, rh, k, tmp;
计算机网络讲义 选择排序的完善 int main( ) { int lh, rh, k, tmp; int array[ ] = {2, 5, 1, 9, 10, 0, 4, 8, 7, 6}; for (lh = 0; lh < 10; lh++) { rh = lh; for (k = lh; k < 10; ++k) if ( array[k] < array[rh] ) rh = k; tmp = array[lh]; array[lh] = array[rh]; array[rh] = tmp; } for (lh =0; lh<10; ++lh) cout << array[lh] << ' '; return 0; }

30 计算机网络讲义 选择排序的效率 对n个元素的排序来说，找出第一个元素要比较n次，找出第二个元素比较n-1次，…，找出第n个元素比较一次。因此，总的比较次数为： … + n = n ( n + 1 ) / 2 则称时间复杂性为O(n2)

31 计算机网络讲义 排序与查找 顺序查找 二分查找 选择排序法 气泡排序法

32 计算机网络讲义 气泡排序法 对数组元素进行扫描。第一遍扫描冒出一个最大的气泡，放入最后一个位置。然后对剩余元素再进行第二次冒泡，冒出最大的泡放入倒数第二个位置，依次执行到最后一个元素。 伪代码表示 For (i=1; i<n; ++i) 从元素0到元素n-i进行冒泡，最大的泡放入元素n-i；

33 计算机网络讲义 冒泡过程 将待冒泡的数据从头到尾依次处理：比较相邻的两个元素，如果大的在前小的在后，就交换这两个元素。这样经过从头到尾的检查，最大的一个就被交换到最后了 如果在一次起泡中没有发生交换，则表示数据都已排好序，不需要再进行起泡

34 进一步细化 for (i=1; i<n; ++i) { 从元素0到元素n-i进行起泡，最大的泡放入元素n-i；
计算机网络讲义 进一步细化 for (i=1; i<n; ++i) { 从元素0到元素n-i进行起泡，最大的泡放入元素n-i； if （没有发生过数据交换） break; }

35 待冒泡的元素 待冒泡的元素 待冒泡的元素 待冒泡的元素 待冒泡的元素 待冒泡的元素
计算机网络讲义 待冒泡的元素 5 7 3 4 2 1 9 6 8 待冒泡的元素 待冒泡的元素 5 3 4 2 1 7 6 8 9 待冒泡的元素 3 4 2 1 5 6 7 8 9 待冒泡的元素 3 2 1 4 5 6 7 8 9 2 1 3 4 5 6 7 8 9 待冒泡的元素 1 2 3 4 5 6 7 8 9

36 for (j=0; j<n-i; ++j) if (a[j+1] < a[j])
计算机网络讲义 int main() {int a[ ] = { 0, 3, 5, 1, 8, 7, 9, 4, 2, 10, 6}; int i, j, tmp, n = 11; bool flag; for (i=1; i<n; ++i) {flag = false; for (j=0; j<n-i; ++j) if (a[j+1] < a[j]) {tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; flag = true;} if (!flag) break;/* 一趟冒泡中没有发生交换，排序结束*/ } cout << endl; for (i=0; i<n; ++i) cout << a[i] << ' '; return 0;

37 计算机网络讲义 第5章 批量数据处理—数组 一维数组 排序和查找 二维数组 字符串

38 多维数组 数组的每一个元素又是数组的数组称为多维数组 最常用的多维数组是二维数组，又称为矩阵 二维数组的定义格式：
计算机网络讲义 多维数组 数组的每一个元素又是数组的数组称为多维数组 最常用的多维数组是二维数组，又称为矩阵 二维数组的定义格式： 类型说明 数组名[常量表达式1][常量表达式2] 常量表达式1表示行数，常量表达式2表示列数 eg. int a[4][5]; 相当于定义了20 个变量： a[0][0], a[0][1], ..., a[0][4],... a[3][0], a[3][1], ..., a[3][4]

39 计算机网络讲义 二维数组 col0 col1 col2 col3 col4 row0 row1 row2 row3 a[2][3]

40 计算机网络讲义 二维数组的内存排列 按行序排列 a[0][0] a[0][1] … a[0][4] a[1][0] a[3][4]

41 多维数组的初始化 格式： 类型说明 数组名[常量表达式1] [常量表达式2]={.....}; 给所有的元素赋初值。如：
计算机网络讲义 多维数组的初始化 格式： 类型说明 数组名[常量表达式1] [常量表达式2]={.....}; 给所有的元素赋初值。如： int a[3][4] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}; 也可以通过花括号把每一行括起来使这种初始化方法表示得更加清晰。 int a[3][4] = { {1,2,3,4}, {5,6,7,8}, {9,10,11,12}};

42 计算机网络讲义 多维数组的初始化 对部分元素赋值 int a[3][4] = { 1, 2 , 3, 4, 5 };

43 计算机网络讲义 多维数组的初始化 为每一行的部分元素赋初值 int a[3][4] = { {1, 2}, {3, 4}, {5}};

44 计算机网络讲义 程序举例--矩阵乘法 矩阵乘法 C=A*B A[L][M]，B[M][N] C[L][N] 输入A，B 相乘 输出C

45 #define MAX_SIZE 10 //矩阵的最大规模 int main() {int a[MAX_SIZE][MAX_SIZE]；
计算机网络讲义 #define MAX_SIZE 10 //矩阵的最大规模 int main() {int a[MAX_SIZE][MAX_SIZE]； int b[MAX_SIZE][MAX_SIZE] int c[MAX_SIZE][MAX_SIZE]; int i, j, k； int NumOfRowA, NumOfColA, NumOfColB; //输入A，B的大小 cout<< "\n输入A的行数、列数和B的列数："; cin >> NumOfRowA >> NumOfColA >> NumOfColB;

46 cout << "\n输入数组A:\n"; for (i=0; i< NumOfRowA; ++i)
计算机网络讲义 //输入数组A cout << "\n输入数组A:\n"; for (i=0; i< NumOfRowA; ++i) for (j=0; j < NumOfColA; ++j) { cout << "a[" << i << "][" << j << "] = "; cin >> a[i][j]; } //输入数组B cout << "\n输入数组B:\n"; for (i=0; i< NumOfColA; ++i) for (j=0; j< NumOfColB; ++j) { cout << "b[" << i << "][" << j << "] = "; cin >> b[i][j];

47 for (i=0; i< NumOfRowA; ++i) for (j=0; j< NumOfColB; ++j)
计算机网络讲义 //执行A*B for (i=0; i< NumOfRowA; ++i) for (j=0; j< NumOfColB; ++j) { c[i][j] = 0; for (k=0; k<NumOfColA; ++k) c[i][j] += a[i][k] * b[k][j]; }

48 cout << "\n输出数组C:"; for (i=0; i < NumOfRowA; ++i)
计算机网络讲义 //输出数组C cout << "\n输出数组C:"; for (i=0; i < NumOfRowA; ++i) { cout << endl; for (j=0; j< NumOfColB; ++j) cout << c[i][j] << '\t'; } return 0;

49 第5章 批量数据处理—数组 一维数组 排序和查找 二维数组 字符串

50 字符串 字符串的存储及初始化 字符串的输入输出 字符串处理函数 字符串应用

51 字符串 由一系列字符组成的一个数据称为字符串 在C++中，字符串常量用一对双引号括起来。如”Hello,world”
字符串变量：用字符类型的数组来表示

52 字符串的存储 字符串的本质是一系列的有序字符，因此可以用一个字符数组来保存这组字符 。用数组名表示这个字符串
由于数组名是数组的起始地址，因此该字符串从该地址开始存储。但到哪里为止？C++用‘\0’表示字符串的结束。 字符串所需的存储空间比实际的字符串长度大1 如要将字符串”Hello,world”保存在一个数组中 ，该数组的长度为12

53 字符串的初始化 char ch[ ] = { ‘H’, ’e’, ’l’, ’l’, ’o’, ’,’, ’w’, ’o’, ’r’, ’l’, ’d’, ’\0’}; char ch[ ] = {”Hello,world”}; char ch [ ] = ”Hello,world”;

54 空字符串 不包含任何字符的字符串称为空字符串。 空字符串占用的空间为1个字节，存储‘\0’ 注意‘a’和“a”的区别 ‘a’是简单变量

55 字符串 字符串的存储及初始化 字符串的输入输出 字符串处理函数 字符串应用

56 字符串的输入输出 逐个字符的输入输出：这种做法和普通的数组操作一样。 将整个字符串一次性地用cin和cout输入或输出。
通过函数gets和puts输入输出。

57 用cin和cout 如定义了一个字符数组ch。要输入一个字符串放在ch中，可直接用 cin >> ch;
注意： cin输入是以空格、回车或Tab键作为结束符。因此无法输入包含空白字符的字符串 在用cin输入时，要注意输入的字符串的长度不能超过数组的长度。因此，最好在输出的提示信息中告知允许的最长字符串长度。

58 函数gets和puts gets函数 puts函数 从终端接受一个包含任意字符的字符串，直到遇到回车。 格式：gets（字符数组）
将一个字符串（以‘\0’结束的字符序列）输出到终端 格式： puts（字符数组）

59 字符串 字符串的存储及初始化 字符串的输入输出 字符串处理函数 字符串应用

60 字符串处理函数 字符串不能直接用系统的内置运算符进行操作 C++的函数库中提供了一些用来处理字符串的函数。这些函数在库cstring中

61 函数 作用 strcpy(dst, src) 将字符从 src拷贝到dst。函数的返回值是dst的地址 strncpy(dst, src, n) 至多从 src 拷贝n个字符到dst。函数的返回值是dst的地址 strcat(dst, src) 将 src 接到 dst 后。函数的返回值是dst的地址 strncat(dst, src, n) 从 src 至多取 n 个字符接到 dst 后。函数的返回值是dst的地址 strlen(s) 返回s的长度 strcmp(s1, s2) 比较 s1 和 s2。如 s1 > s2 返回值为正数，s1=s1返回值为0，s1<s2返回值为负数 strncmp(s1, s2, n) 如 strcmp，但至多比较n个字符 strchr(s, ch) 返回一个指向s中第一次出现ch的地址 strrchr(s, ch) 返回一个指向s中最后一次出现ch的地址 strstr(s1, s2) 返回一个指向s1中第一次出现s2的地址

62 字符串 字符串的存储及初始化 字符串的输入输出 字符串处理函数 字符串应用

63 字符串的应用 实例：输入一行文字，统计有多少个单词。单词和单词之间用空格分开。 解题关键：单词的数目可以由单词间的空格决定 解题思路：
设置一个计数器num表示单词个数。开始时，num=0。 从头到尾扫描字符串。当发现当前字符为非空格，而当前字符以前的字符是空格，则表示找到了一个新的单词，num加1。 当整个字符串扫描结束后，num中的值就是单词数。

64 int main() { char sentence[80], prev = ' '; //prev 表示当前字符的前一字符 int i, num = 0; gets(sentence); for (i = 0; sentence[i] != '\0'; ++i) { if (prev == ' ' && sentence[i] != ' ') ++num; prev = sentence[i]; } cout << "单词个数为：" << num << endl; return 0; 一定要用gets输入 直接用sentence[i]

65 总结 数组通常用来存储具有同一数据类型并且按顺序排列的一系列数据。数组中的每一个值称作元素，通常用下标值表示它在数组中的位置。在C++中，下标是从0开始的。 定义一个数组时，必须定义数组的大小，而且它必须是常量 数组中的元素一般用数组名后加用方括号括起来的下标表示 数组元素通常是连续存储的。第一个元素的地址称为基地址 数组的下标可以是任意的计算结果可以自动转换成整型数的表达式，包括整型，字符型或者枚举型。 可以定义数组是多维的。多维数组可以看成数组的数组。