专题研讨课二： 数组在解决复杂问题中的作用

Presentation on theme: "专题研讨课二： 数组在解决复杂问题中的作用"— Presentation transcript:

1 专题研讨课二： 数组在解决复杂问题中的作用
专题研讨课二： 数组在解决复杂问题中的作用

2 Part I 要点提示

3 一维数组 类型名 数组名[数组长度] int a[5],b[10]; float x[7]; double y[20]; 定义：
类型名 数组名[数组长度] 每个元素的类型 数组变量的名称，合法的标识符 数组的大小，整型常量表达式 为什么数组长度不能是变量？ int N=10; int a[N]; int a[5],b[10]; float x[7]; double y[20];

4 一维数组 初始化：类型名 数组名[数组长度] = {初值表};
初始化：类型名 数组名[数组长度] = {初值表}; int a[10] = { 0,1, 2, 3, 4, 5, 6, 7, 8, 9 }; int a[ ] = { 0, 1, 2, 3, 4, 5, 6, 7, 9, 9 }; 部分初始化： int a[10] = { 0, 1, 2, 3, 4 }; 没有初始化的元素值是什么？

5 一维数组 引用：数组名[下标]; 数组变量的名称 整型表达式 例如：int a[10], i; 那么：a[ i ] 引用数组a的第i个元素

6 一维数组 int a[10]; 存储方式： 连续存放于内存（RAM） 数组名代表其首元素的地址 元素a[ i ] 的地址记为：a + i
2 3 4 5 6 7 8 ⁞ 9 a 内存 int a[10]; 元素a[ i ] 的地址记为：a + i a[ i ] 的实际地址是什么？

7 对于 <0 或者 >N-1 的k, a[k]是哪个元素？
一维数组 存储方式： 连续存放于内存（RAM） 数组名代表其首元素的地址 1 2 3 4 5 6 7 8 ⁞ 9 a 内存 对于长度为N的数组，末尾元素为a[N-1] 对于 <0 或者 >N-1 的k, a[k]是哪个元素？ 修改a[k]有何后果？

8 可执行程序 指令：运算指令、控制指令 数据：常量、变量 由编译器根据源程序编译链接生成 处理数据时，必须要知道其大小 简单变量类型
数据变量类型和长度 自定义结构先定义

9 数组越界 对于<0的k：改变a[k]可能导致数组前面的数据/代码异常
内存 ⁞ 对于<0的k：改变a[k]可能导致数组前面的数据/代码异常 对于>=N的k：改变a[k]可能导致数组后面的数据/代码异常 数组a 长度N ⁞ 试图修改系统相关的数据和代码 将会被阻止执行

10 二维数组 类型名 数组名[行长][列长] int a[2][4]; float x[5][10]; double y[1][1]; 定义：
类型名 数组名[行长][列长] 每个元素的类型 数组变量的名称，合法的标识符 数组的大小，整型常量表达式 int a[2][4]; float x[5][10]; double y[1][1];

11 二维数组 部分初始化： 初始化： int a[3][2] = { {1}, {3, 4} }; 初始化了两行 第一行只初始化部分元素
int b[3][2] = { , {1, ,3 }}; 那些被初始化了？

12 二维数组 存储方式：逐行连续存放于RAM中 int a[3][2]; 二维数组的元素在内存中按行方式存放 a[0][0] a[0][1]
3 行 2 列， 6 个元素 表示1个3行2列的矩阵 二维数组的元素在内存中按行方式存放 a[0][0] a[0][1] a[1][0] a[1][1] a[2][0] a[2][1] 第0行a[0] 第1行a[1] 第2行a[2] a[0][0] a[0][1] a[1][0] a[1][1] a[2][0] a[2][1]

13 数组应用 —— 存储数据 大量数据 … 相同类型 循环遍历 文字信息、数据统计、图像视频 所有元素具有相同的类型/结构 处理方式相同
一般利用循环语句进行处理

14 数组应用 数值计算 向量运算 矩阵运算 多元方程 算法设计 制作查找表 简化程序结构

15 数组使用 设计函数处理数组 数组作为函数参数 void ReverseIntArray( int array[], int n ) {
int i, k, tmp; for (i = 0, k=n-1; i < k; i++, k--) { tmp = array[i]; array[i] = array[k]; array[k] = tmp; }

16 形参数组array（的地址值）等于实参数组a（的地址值），于是它们指向同一块内存。因此，对array的操作等价于对a的操作。
1000 1000 1002 1004 1006 1008 1010 1012 1014 1494 1496 1498 1 2 3 4 5 . a [0] a [1] a [2] a [3] a [4] a [5] a [6] a [7] a [247] a [248] a [249] array[0] array[1] array[2] array[3] array[4] array[5] array[6] array[7] array[247] array[248] array[249] array 1000 假设a数组的首地址为1000，当执行 ReverseIntArray(a, 5) 形参数组array（的地址值）等于实参数组a（的地址值），于是它们指向同一块内存。因此，对array的操作等价于对a的操作。

17 Part II 应用举例

18 1：数组排序 输入n个数，将它们从小到大排序后输出。 3 5 2 8 1 选择法排序：选择最小的元素，交换到前列 3 5 2 8 1
(1) (2) (3) (4)

19 一般地， (1) a[0] ~ a[n-1] 中找最小数，与 a[0] 交换
(k) ……（第k轮） （n-k个数中最小的） (n-1) a[n-2]，a[n-1]中最小数，与 a[n-2] 交换 （2个数中最小的）

20 排序主程序 SortArray void SortArray(int array[ ], int n) { int k, iMin;
for (k = 0; k < n-1; k++) { /* 找到第k次最小值的下标 */ iMin = FindMinIndex( array, k, n ); if ( k != iMin ) /*交换*/ SwapArrayElements(array, iMin, k); }

21 找最小值 FindMinIndex int FindMin(int a[ ], int start, int n) { int k, m;
m = start; /*初始化为起始元素的下标*/ for ( k = start+1; k < n; k++ ) if ( a[k] < a[m] ) m = k; /*找到更小的，更新下标*/ return m; }

22 交换 SwapArrayElements void SwapArrayElements(int a[ ], int i, int j) {
int tmp; tmp = a [i]; a [i] = a [j]; a [j] = tmp; }

23 思考 如何将数组从大到小进行排序？ 想想排序的其他方法？

24 2：数组查找 在一个整数数组a[ ]中，查找给定的整数x int Find( int a[ ], int n, int x)
返回整数x在数组a中的下标。 如不存在，则返回-1。 n是数组a中元素的个数

25 Naïve方法 逐个查询 int Find( int a[ ], int n, int x ) { int i;
for( i=0; i<n; i++ ) if( a[i]==x ) return i; return -1; }

26 二分查找 假设数组a具有从小到大的顺序 思想：将数据一分为二，在包含x的1/2数组中继续查找。直至找到或查找范围为空 s t k
s、t是数组的首尾下标（不包括t） k k为中分下标 s t a[k] < x t s a[k] > x a[k]==x return k

27 二分查找 int Find( int a[ ], int n, int x ) { int s = 0, t = n, k; if( n<1 || x<a[0] || x>a[n-1] ) return -1; while( s < t ) { k = (s + t) / 2; if( a[k]<x ) s = k+1; else if ( a[k]>x ) t = k; else return k; } s t k s t t s

28 二分查找 利用了数组结构的优点 连续存放 随机存取

29 3：数组循环移位 将一个长度为n的数组A[ ]，向右循环m个位置: A[0] A[1] A[2] …….. … A[n-2] A[n-1]
变成 A[n-m] …A[n-1] A[0] A[1]…A[n-m-1] （1）不能使用额外的数组 （2）不妨假设0<m<n，否则取m=m%n

30 Naïve方法 重复执行m次，每次将数组向右移动1位 总的移位次数为m*n void shift( int A[], int n ) {
int i, e = A[n-1]; for( i=n-1; i>0; i-- ) A[i] = A[i-1]; A[0] = e; } void main() { … for( i=0; i<m; i++ ) shift(A,n); } 总的移位次数为m*n

31 翻转方法 A[0] A[1] A[2] A[3] … A[n-2] A[n-1] 整体翻转 A[n-1]… A[n-m] A[n-m-1]…A[1] A[0] 分段翻转 A[n-m] …A[n-1] A[0] A[1] … A[n-m-1]

32 翻转方法 void reverse(int A[ ], int s, int t) { int temp; while (s<t ) { temp = A[s]; A[s++] = A[t]; A[t--] = temp; } void main() { … reverse(A, 0, n-1 ); reverse(A, 0, m-1); reverse(A, m, n-1 ); } 总的移位次数为2*n

33 移位次数比较： m*n VS 2*n 当m>2时，翻转法的效率更高 思考更好的方法?（移位次数为n） 处理大数组（大数据）时，审慎考虑算法效率

34 4：扑克牌计算24点 4张扑克牌，各代表1~13之间的1个整数 采用+，-，*，/ 四种算术运算，得到24。
（利用数组建立查找表，简化代码） 4张扑克牌，各代表1~13之间的1个整数 采用+，-，*，/ 四种算术运算，得到24。 如能，输出算式；如不能，输出NO。 可以添加括号，改变运算优先级

35 解决思路 a P b Q c R d 考虑4个整数算式的各种组合情况 操作数 a,b,c,d 可以任意排列
24种情况 运算符P,Q,R都可以4种运算之一 64种情况

36 解决思路 a P b Q c R d 考虑4个整数算式的各种组合情况 P,Q,R的运算顺序有6种情况
PQR，PRQ，QPR，QRP，RPQ, RQP PRQ和RPQ的结果是一样的 （a P b）Q（c R d） 所以只需要考虑5种： PQR，PRQ，QPR，QRP，RQP

37 解决思路 逐个情况，分别处理  建立查找表，循环处理  分析各种情况， 将参数保存在数组中 操作数、运算符

38 程序设计 运算符数组：char op[64][3]; char opc[] = “+-*/”; n=0;
for( i=0; i<4; i++) for( j=0; j<4; j++) for(k=0; k<4; k++) { op[n][0]=opc[ i ]; op[n][1]=opc[ j ]; op[n][2]=opc[ k]; n++; }

39 程序设计 操作数数组：int abcd[24][4]; /* 4张牌的点数保存在 int a[4] 中*/ n=0;
for( i=0; i<4; i++) for( j=0; j<4; j++) for( k=0; k<4; k++) for(m=0; m<4; m++) { if( i==j || i==k || i==m || j==k || j==m || k==m ) continue; abcd[n][0] = a[i]; abcd[n][1] = a[j]; abcd[n][2] = a[k]; abcd[n][3] = a[m]; n++; }

40 程序设计 运算测试 found = 0; for( n=0; n<24 && !found; n++ )
for( m=0; m<64 && !found; m++ ) { /*提取运算符和操作数*/ a = abcd[n][0]; b = abcd[n][1]; c = abcd[n][2]; d = abcd[n][3]; P = op[m][0]; Q = op[m][1]; R = op[m][2]; if( found = test(a,b,c,d,P,Q,R) ) break; }

41 测试函数 int test( int a, int b, int c, int d, char P, char Q, char R) {
/* PQR: ((a P b) Q c) R d */ if( calc( calc( calc(a,P,b), Q, c), R, d)==24 ) { printf(…….); return 1; } /* PRQ: (a P b) Q (c R d) */ if( calc( calc(a, P, b), Q, calc(c, R, d) )==24 ) { printf(…….); return 1; } 【其他情况雷同处理，略…】 }

42 calc函数 double calc( double a, char op, double b) {
if( op==‘+’ ) return a+b; if( op==‘-’ ) return a-b; if( op==‘*’ ) return a*b; if( op==‘/’ && b!=0 ) return a/b; else return 1.0E10; }

43 4：扑克牌计算24点 程序的运算量是多少？ 如何找出所有、不同的算式？ 扩展：N张扑克牌 N-1个运算符 得到结果M

44 The End!

45 5：扩展的扑克牌问题 难度转移 操作数排列情况急剧增加：N! 运算符情况急剧增加：4^(N-1)
存储空间急剧增长 测试函数的处理的优先级情况急剧增加：(N-1)! 无法采用固化的分支程序处理

46 N元算式的优先级分析与计算 a0 P1 a2 P2 … Pn an 每执行一个运算之后，算式减少一元 适合采用递归方法进行测试和计算

47 N元算式的递归计算 int test( double a[], char p[], int N, int M ) { int i; double s, a1[54], p1[54]; if( N==2 ) { if( (s = calc(a[0], p[0], a[1]) )==M ) printf(…); return s==M; } for( i=0; i<N-1; i++ ) { s = calc(a[i], p[i], a[i+1]); 构造对应的N-1元算式，并存储到数组a1[ ]和p1[ ]中 if ( test( a1, p1, N-1, M ) ) return 1; return 0;

48 5：扩展的扑克牌问题 参考上述的递归的test函数，编写程序解决扩展的扑克牌问题。 假设N<10 打印算式

49 6：螺旋方阵 如下图，已知N*N（3<=N<=25）的方阵，从左上角第1个格子开始，按顺时针螺旋方向将1、2、3……的数据布满整个方阵。

50 基本思路： 螺旋方阵数据的产生有一定规律。从外到内，可以圈为单位生成数据。比如N=4时，刚好就是两圈数据： 第1圈： 1 2 3 4
第2圈： 13 14 16 15 基本规律是：当N为偶数时，需要N/2圈；当N为奇数时，也需要N/2圈，但是最后还生成一个数据就是N*N。 实现要点：使用二维数组存储螺旋方格子中的数据；二维数组所有数据的生成，可应用循环，根据所需要的圈数，从左右下左上，四个方向来产生数据。

51 [main] #define MAX_SCREW 20 /*螺旋最大边长*/ int InputScrewArray();
void GenScrewArray(int ScrewArray[MAX_SCREW][MAX_SCREW], n); void PrintScrewArray(ScrewArray[MAX_SCREW][MAX_SCREW], n); main() { int ScrewArray[MAX_SCREW][MAX_SCREW];/*二维螺旋矩阵*/ int n;/*实际边长*/ n = InputScrewArray(); /*输入螺旋边长*/ GenScrewArray(ScrewArray, n); /*生成螺旋矩阵*/ PrintScrewArray(ScrewArray, n);/*打印螺旋矩阵*/ ｝

52 [GenScrewArray] void GenScrewArray(int ScrewArray[MAX_SCREW][MAX_SCREW], int n) { int row, col; /*每一圈的左上角起始坐标*/ int len； /*每一圈的边长*/ int count; /*螺旋计数，每填上一个数，自增1*/ int i, k; row = col = 0; /*起始位置（0，0）*/ len = n; /*最外圈边长*/ count = 1；/*第一个数是1*/ for (i = 0; i < n/2; i++) { /*圈数循环*/ for (k=col;k<col+len-1;k++) ScrewArray[row][k]=count++;/*上：左到右*/ for (k=row;k<row+len-1;k++) ScrewArray[k][col+len-1]=count++;/*右：上到下*/ for (k=col+len-1;k>col;k--) ScrewArray[row+len-1][k]=count++;/*下：右到左*/ for (k=row+len-1;k>row;k--) ScrewArray[k][col]=count++;/*下：右到左*/ row++; col++; len -= 2;/*下一圈的左上角起始位置与边长调整*/ } if (n%2) ScrewArray[n/2][n/2] = count; /*奇数边长，补填中心元素值n*n */ ｝