C++编程数据组织1-数组

1、,6 数据的组织与处理（一）数组,1,递推的解题思路 数组的概念、定义和初始化 字符数组、字符串处理 筛法的解题思路 数组元素的查找（线性查找与二分查找） 数组排序的思路（冒泡排序法） 多维数组（维以上）,学 习 目 标,2,【任务 一】 A、B、C、D、E 五人合伙夜间捕鱼，凌晨时都疲惫不堪，各自在湖边的树丛中找地方睡着了。 日上三竿，A第一个醒来，他将鱼平分作五份，把多余的一条扔回湖中，拿自己的一份回家去了。B第二个醒来，也将鱼平分为五份，扔掉多余的一条，只拿走自己的一份。接着 C、D、E 依次醒来，也都按同样的办法分鱼。 问五人至少合伙捕到多少条鱼？每个人醒来后看到的鱼数是多少条？,3,

2、为了解决上面这种类型的问题，需要学习和运用“递推”的思想，以及如何使用“数组”这种数据组织的形式来实现递推的过程。 下面先来介绍“递推”的算法思想。,4,递推是计算机数值计算中的一个重要算法，可以将复杂的运算化为若干重复的简单运算，以便充分发挥计算机长于重复处理的特点。 通常，使用循环结构来实现重复处理。解决此类问题的关键是：分析简单情况，归纳总结出前后项的关系（通项公式）。,递 推,5,【任务 A】 求自然数n的阶乘。 任务分析： 令fact(n)表示n的阶乘，依据后项与前项的关系， 可以写出下面的“递推”公式： fact(1) = 1 - 起始条件（边界条件） fact(n) = n *

3、fact(n-1) - 通项公式 算法实现： 根据前后项的关系，显然，用循环结构来实现这种递推关系是非常自然的。请看下面的代码实现。,6,#include using namespace std; int main() int N; cout N; int fact; for (int n=1; n=N; n+) if (n = 1) fact = 1; else fact = n * fact; / fact_n = n * fact_n_1 cout fact( N ) = fact endl; return 0; ,7,【任务 B】 王小二自夸刀功不错，有人放一张饼在砧板上，问他：“饼不

4、许离开砧板，如果切刀，你最多能将饼分成多少块？”,刀,刀,刀,刀,8,在编程之前要找到规律 分析： 令q(n)表示切n刀能分成的块数。从前面的图中可以找出下列关系： q(1) = 1 + 1 = 2 q(2) = 1 + 1 + 2 = 4 q(3) = 1 + 1 + 2 + 3 = 7 q(4) = 1 + 1 + 2 + 3 + 4 = 11 由于要求最多的块数，所以每刀都是让每两条线都有交点。用归纳法不难得到： q(0) = 1 - 初始条件（边界条件） q(n) = q(n-1) + n - 通项公式,9,#include using namespace std; int main(

5、) int q; for (int n=0; n=100; n+) if (n = 0) q = 1; else q = n + q; / q_n = n + q_n_1 cout q(100) = q endl; return 0; ,10,11,数组是计算机语言提供的组织多个数据的一种重要方式： 提供了多个同类型的数据（值）在内存中连续存放的工具 提供了对无限量内存单元进行高效“命名”的途径 提供了在程序运行过程中动态改变“变量名称”的手段 是一些重要算法思想的实现基础,数组,12,类型说明符 数组名常量表达式 ; TYPE array_nameconst_expr; 例：float sh

6、eep_weight10; int _a20011000; char student_name20; 说明 1. 数组变量的名称，必须符合语言对变量命名的要求； 2. 用方括号将常量表达式括起； 3. 常量表达式定义了数组元素的个数；,数组的定义,13,注意：在使用VC+6.0进行编程时，数组元素的数目，要使用常量表达式，其中不能包含变量 例如int n; n = 5; int an;不合法！ 因为 n 是变量，不是常量,VC+ 6.0: error C2057: expected constant expression,14,数组中每个元素所在的内存单元，可以通过“数组名位置下标”来访问（赋

7、值、读取）。数组元素的位置下标从 0 开始计数。 例如，int a5；定义了一个含有5个整数的数组，各元素的“变量名称”分别为： a0, a1, a2, a3, a4 是5个带下标的变量，它们的类型是相同的。该数组的效果与下面的变量定义相同： int a0, a1, a2, a3, a4;,数组中元素的“名称”,15,数组元素的位置关系与内存地址,a a0 a1 a2 a3 a4 说明： a0元素的内存地址，即 其中，v1, v2等表示常量表达式。 例如：int a5 = 3, 5, 4, 1, 2 ; char b5 = c, h, i, n, a ; 如果是由字符（char）组成的数组，则

8、还可以使用： char array_nameN = 各种字符; 例如：char a5 = china; 其初始化结果为： a0 = c; a1 = h; ; a4 = a;,数组变量的初始化,17,#include using namespace std; int main() / 在定义时设定值，被称为“变量初始化” char A10 = B, e, i, J, i, n, g; / 一共只给出了7个字符 for (int i=0; i10; i+) cout Ai int(Ai) endl; / 强制类型转换，将字符值转换成整数值，即其ASCII码 / 语法格式： dst_type (sr

9、c_value) return 0; / char_test.cpp,阅读示例代码1，注意总结,18,19,#include using namespace std; int main() / 在定义时设定值，被称为“变量初始化” char A10 = BeiJing; / 一共只给出了7个字符 for (int i=0; i10; i+) cout Ai int(Ai) endl; / 强制类型转换，将字符值转换成整数值，即其ASCII码 / 语法格式： dst_type (src_value) return 0; / char_test_2.cpp,阅读示例代码2，注意总结,20,21,#

10、include using namespace std; int main() / 在定义时设定值，被称为“变量初始化” char A = BeiJing; / 一共给出了7个字符 int B = 1,2,3,4,5; / 一共给出了5个整数 for (int i=0; i10; i+) cout Ai int(Ai); cout Bi endl; return 0; / char_test_3.cpp,阅读示例代码3，注意总结,22,23,#include using namespace std; int main() / 在定义时设定值，被称为“变量初始化” charA1 = BeiJin

11、g;/ 一共给出了7个字符 intB1 = 1,2,3,4,5; / 一共给出了5个整数 cout sizeof(A1) sizeof(A1) endl; cout sizeof(B1) sizeof(B1) endl; charA210 = BeiJing;/ 一共给出了7个字符 intB210 = 1,2,3,4,5;/ 一共给出了5个整数 cout sizeof(A2) sizeof(A2) endl; cout sizeof(B2) sizeof(B2) endl; return 0; / char_test_4.cpp,阅读示例代码4，猜猜输出,24,A1,25,总结说明,数组变量在

12、“初始化”时（即至少提供了一个初始值），如果提供的初始值数目少于数组元素的个数，则依下标大小顺序，从下标为0的元素开始，逐一设定初始值，缺少初始值的数组元素，将被编译器自动设置成0。 以字符串常量方式对字符数组进行“初始化”时，也同样遵循上述规则。 如果初始化时不设定数组大小（元素数目），则编译器自动根据初始值的数目来设定数组的大小。 如果是字符数组，则编译器设定的数组大小是：“字符串常量长度+1”，即不遵循上述规则！,26,数组变量的赋值,27,28,这是一个伪命题！,数组变量的赋值,29,所有类型的数组变量 均不可以直接赋值,数组变量的赋值,30,int a5; char b5; a =

13、1,2,3,4,5; b = CHINA;,数组变量的赋值,31,单独一个一个进行赋值 int a5; a0=1; a3=23; 使用for语句，连续赋值 char a5; for (int i=0; i5; i+) ai = A + i;,数组中各元素的赋值,32,使用一些特殊的库函数 （）使用memset函数，格式为 memset(起始地址, 初始值, 空间大小)； 举例： memset(sheep, 0, sizeof(sheep); 将名为 sheep 的数组中的全部元素均初始化为 0。调用此库函数需要加入头文件 。 （）使用字符串处理函数，例如： strcpy(字符数组名，字符串常量

14、或变量); 举例：char school_name20; strcpy(school_name, Tsinghua);,数组中各元素的赋值,33,#include using namespace std; int main() char h = 123456; h = abcdef; cout h endl; return 0; 程序会出什么问题？,Line 6: error: ISO C+ forbids assignment of arrays,34,#include using namespace std; int main() char h = 123456; h = “abcef”;

15、 cout h endl; return 0; ,strcpy(h, abcdef);,35,通过cin操作，对字符数组变量进行“赋值”,数组中各元素的赋值,#include using namespace std; int main() char h = 123456789; cin h; / 设键入的是 abcdef cout h endl; / 则程序输出 abcdef return 0; 如果键入的是 123456789012345 则程序会输出什么？,36,如果是字符数组（变量），则cout会将数组的所有元素一齐输出出来，字符之间无空格。 如果是其他类型的元素组成的数组（变量），则c

16、out只会输出该数组变量的地址，也即数组第一个元素所在内存单元的地址。 cout是如何根据数据类型来决定输出方式的呢？这个问题，将在下学期面向对象程序设计中予以解答。,数组变量的“cout 输出”,37,#include using namespace std; int main() char h = tsinghua; h0=a; h1=b; h2=4; h3=7; h4=c; cout h endl; int a = 1,2,3,4,5; a0 = 79; a1 = 88; a2 = 34; a3 = 64; a4 = 99; cout a endl; cout ,38,上述结果说明：数组

17、a的第一个元素的地址，与a的值相等。 即 cout a; 与 cout 等效。,39,字符数组（字符串）的应用示例 “老张开车去东北，撞了！ 肇事司机耍流氓，跑了！” 目击者对交警说：肇事汽车的号码为4位完全平方数，且数字从左到右一个比一个大。 请帮交警算出肇事车的号码。,40,#include #include using namespace std; void find_it() / . int main() find_it( ); return 0; ,41,思路I： 令 n 为车号 n为 4 位数 n = i*i, i = 32, 33, , 99 (31*31=961) 对 i 进行

18、枚举，得不同的 n , 对每个 n ，检查 n的各位， 从高位到低位, 是否一个比一个大？即，低位的数值最大。 n n3 n2 n1 n0 n3 n2 n1 n0,42,void find_it() for (int i=32; i100; i+) int n = i * i; if ( ( (n/1000) (n/100 % 10) ) ,四位数的千位数字 n3 = n / 1000,百位数字 n2 = n / 100 % 10,十位数字 n1 = n / 10 % 10,个位数字 n0 = n % 10,43,现在，车号升级啦！变成了五位！ 闯祸的车号居然还是一个完全平方数! 依然还是从高

19、位到低位一个比一个大！ （越来越大） 这时，程序该怎么编（或修改）呢？,44,思路II（还是以四位数的车号为例说明）： 令 n 为车号 n为 4 位数， n = i*i i = 32, 33, , 99 (31*31=961) 枚举 i 到 n , 查 n 从高位到低位, 是否一个比一个小 将 n 分解为 4 个数字字符: char *itoa( int value, char *string, int radix) value: 待转换整数 string: 存放转换结果的字符串指针 radix: 2-16进制整数,45,n= i * i i 3 3 n 1 0 8 9 itoa( n, bu

20、f , 10 ); buf 1 0 8 9 0 0 1 2 3 4,46,#include #include using namespace std; int main() char buf5; /定义数组 int i=0, n=0; /定义整数变量,47,for( i=32; i100; i+) / 计数循环 n = i*i; / 构造4位数n itoa( n, buf , 10 ); / 把10 进制数 n 转换为字符串放入 buf 数组 if ( (buf0buf1) ,能把程序改得更简洁清晰吗？,48,for ( i=32; i= bufj+1) break; / 若n符合要求，则FO

21、R循环会全部执行完！ if (j = 3) cout 肇事汽车号码为 n endl; / _for_ return 0; ,修改后的程序，是不是更简洁清晰了？,49,for ( i=32; i= bufj+1) break; / 若n符合要求，则FOR循环会全部执行完！ if (j = 3) cout 肇事汽车号码为 n endl; / _for_ return 0; ,想一想：如何把程序改成能解决五位数（或更多）的车号呢？,50,for ( i=32; i= bufj+1) break; / 若n符合要求，则FOR循环会全部执行完！ if (j = 3) cout 肇事汽车号码为 n end

22、l; / _for_ return 0; ,这些地方需要修改！,51,52,任务一的解题思路:,假定A、B、C、D、E 五人的编号分别为1、2、3、4、5，整数数组 fishk 表示第 k 个人所看到的鱼数。fish1 表示A所看到的鱼数，fish2 表示 B 所看到的鱼数 fish1 A所看到的鱼数，合伙捕到鱼的总数 fish2 = (fish1 - 1) * 4 / 5 B所看到的鱼数 fish3 = (fish2 - 1) * 4 / 5 C所看到的鱼数 fish4 = (fish3 - 1) * 4 / 5 D所看到的鱼数 fish5 = (fish4 - 1) * 4 / 5 E所看

23、到的鱼数,53,写成一般式fish i = ( fish i - 1 1 ) * 4 / 5i = 2, 3, ,5,这个公式可用于已知 A 看到的鱼数去推算 B 看到的，再推算 C 看到的，.。现在要求的是 A 看到的。能否倒过来，先知 E 看到的再反推 D 看到的，直到A看到的。为此将上式改写为： fish i-1 = fish i * 5 / 4 +1 i = 5, 4,2,54,分析上式 . 当 i = 5 时，fish i 表示 E 醒来所看到的鱼数，该数应满足被整除后余，所以初值设为+ 2. 当 i = 5 时，fish i-1 表示 D 醒来所看到的鱼数，这个数要满足 fish

24、4 = fish 5 * 5 / 4 + 1 显然，fish 4 必须是整数，所以fish5必须满足 fish 5 % 4 = 0 这个结论同样可以用至 fish 3 , fish 2 和 fish 1 ,55,3 . 按题意要求 5 人合伙捕到的最少鱼数，可以从小往大枚举，即： 可以先让 E 所看到的鱼数最少为 6 条，即 fish 5 初始化为 6 来试，之后每次增加 5 再试，直至递推到 fish 1 ，均为整数。 根据上述思路，我们可以构思如下的程序框图：,56,fish5=fish5+5; for (i=4; i=1; i-) fishi+1%4 !=0 true fales bre

25、ak; fishi=1+ fishi+1*5/4; do while( i= 1),定义数组并初始化,输出计算结果,57,上图的说明：,该图可分为三部分 (1) 是说明部分：包含定义数组 fish6，并初始化为 1 和定义循环控制变量 i，并初始化为 0。 (2) 是 do.while 直到型循环，其循环体又含两块： (2.1) 是枚举过程中的 fish5 的初值设置，一开始 fish5=1+5; 以后每次增 5。 (2.2) 是一个 for 循环，i的初值为 4，终值为 1，步长为 -1，该循环的循环体是一个分支语句，如果 fishi+1不能被 4 整除，则跳出 for 循环（使用 brea

26、k 语句;）否则，从 fishi+1 算出fishi。,58,当 break 语句让程序退出循环时，意味着某人看到的鱼数不是整数，当然不是所求，必须令fish 5 加 5 后再试，即重新进入直到型循环 do while 的循环体。 当正常退出 for 循环时，一定是控制变量 i 从初值 4，一步一步执行到终值 1，每一步的鱼数均为整数，最后 i = 0，表示计算完毕，且也达到了退出直到型循环的条件。 (3) 输出计算结果,59,#include using namespace std; int main() int fish6=1,1,1,1,1,1; / 记录每人醒来后看到的鱼数 int i

27、=0; do fish5=fish5+5; / 让E看到的鱼数增5。 for (i=4; i=1; i-) if ( fishi+1%4 !=0 ) break; / 跳出for循环 else fishi=fishi+1*5/4+1; / 计算第i人看到的鱼数 while( i=1 ); / 当 i=1 继续做do循环 / 输出计算结果 for (i=1; i=5; i+) cout fishi endl; return 0; ,60,/* /* 程 序 名：9_.cpp（五人合伙捕鱼） * /* 作 者：wuwh * /* 编制时间：2002年10月2日 * /* 主要功能：递推算法的实现

28、* /* #include / 预编译命令 using namespace std; int main() /主函数 int fish6=1,1,1,1,1,1; / 整型数组，记录每人 / 醒来后看到的鱼数 int i=0;,61,do fish5=fish5+5; for (i=4; i=1; i=i-1) if ( fishi+1%4 !=0 ) break; / 跳出for循环 else fishi=fishi+1*5/4+1; while( i=1 );,62,初始化E=1 E=E+5 break yes 递 E E%4 !=0 D=( E*5/4 )+1 no 推 yes D D%

29、4 !=0 方 C= ( D*5/4 )+1 no yes 向 C C%4 !=0 B= ( C*5/4 )+1 no yes B B%4 !=0 A= ( B*5/4 )+1 no A,63,3121 2496 1996 1596 1276,输出结果,64,#include using namespace std; int main() int fisher6; / 五个人看到的鱼数 for (int num = 6; ; num += 5) / 对各种可能性进行枚举 int n; for (n=5; n=1; n-) / 对五个人看到的鱼数进行递推 if (n = 5) fishern =

30、 num; else / fishern+1 = (fishern - 1) / 5 * 4; if (fishern+1 % 4 != 0) break; / 鱼数num不满足条件，要尝试下一个num，停止递推 else / 下式所得fishern必然满足 fishern % 5 = 1 fishern = fishern+1 * 5 / 4 + 1; if (n = 0) / 说明鱼数num满足所有人的条件 break; / 找到最小鱼数了，停止枚举 / 输出各个人看到的鱼数 for (int n=1; n=5; n+) cout fisher n = fishern endl; retu

31、rn 0; ,第种算法实现,65,#include using namespace std; int main() int fisher6; / 五个人看到的鱼数 for (int num = 6; ; num += 5) / 对各种可能性进行枚举 int n; for (n=1; n=5; n+) / 对五个人看到的鱼数进行递推 if (n = 1) fishern = num; else/ 下式所得fishern 必然是整数 fishern = (fishern-1 - 1) / 5 * 4; if (fishern % 5 != 1) break; / 鱼数num不满足条件，要尝试下一个

32、num，停止递推 if (n = 6) / 说明鱼数num满足所有人的条件 break;/ 找到最小鱼数了，停止枚举 / 输出各个人看到的鱼数 for (int n=1; n=5; n+) cout fisher n = fishern endl; return 0; ,第种算法实现,66,#include using namespace std; bool IsOK(int num, int fisher6) for (int n=1; n=5; n+) / 对五个人看到的鱼数进行递推 if (n = 1) fishern = num; else / 下式所得fishern必然是整数 fis

33、hern = (fishern-1 - 1) / 5 * 4; if (fishern % 5 != 1) return false; / 鱼数num不满足条件，停止递推 return true; int main() int fisher6; / 五个人看到的鱼数 for (int num = 6; ; num += 5) / 对各种可能性进行枚举 if (IsOK(num, fisher) break; / found / 输出各个人看到的鱼数 for (int n=1; n=5; n+) cout fisher n = fishern endl; return 0; ,第种算法实现,67

34、,任务二、求100以内的所有素数,6 . 2 筛 法,68,什么是“筛法”？ 想象将100个数看作沙子和小石头子，让小石头子权称素数；让沙子当作非素数。弄一个筛子，只要将沙子筛走，剩下的就是素数了。 非素数一定是 2、3、4 的倍数。 使用数组，让下标就是100以内的数，让数组元素的值作为筛去与否的标志。比如筛去以后让元素值为1。,69,方法的依据： 1至100这些自然数可以分为三类： 单位数：仅有一个数1。 素数： 是这样一个数，它大于1，且只有1 和它自身这样两个正因数。 合数： 除了1和自身以外，还有其他正因数。,1不是素数，除1以外的自然数，当然只有素数与合数。筛法实际上是筛去合数，留

35、下素数。,70,为了提高筛法效率，注意到： 令 n 为合数（这里是100）， c 为 n 的最小正因数， 据初等数论，只要找到 c 就可以确认 n 为合数，将其筛去。,一定注意：要进行“筛”的1100的数字是与数组prime101的下标相对应的，而每个数组元素的取值只有2个：是0或1，分别代表（标志）与下标相对应的数字是素数或不是素数。,71,0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 。 0 0 1 0 1 0 1 1 1 0 1 0 1 1 1 2 3 4 5 6 7 8 9 10 11 12 13

36、14 15 16 。 寻找2的倍数 寻找3的倍数 寻找4的倍数,72,程序框图如下：,请分析左边程序的结构 从而了解算法的设计思路 为程序代码的实现创造条件,73,上述框图很清晰地描述了筛法的思路： STEP 1. 将prime数组清零，使用了一个计数型的循环语句。 STEP 2. 将正因数d 初始化为 d = 2。 STEP 3. 循环筛数。这里用了一个 do while 语句，也称为“直到型循环”。 STEP 4. 输出“筛”过后的数组，即剩下的所有素数，这里使用了标识数组。,74,补充说明,在dowhile语句中，检测primek是否为零。若是零，则说明k是质数。这是因为 sqrt(k)k，所以，当检测到k时，2 sqrt(k)必然已全部测试过了。如果在sqrt(k)中有整除k的数，则primek必会被设为。因此，若此时primek是零，则说明2sqrt(k)中没有遇到