第五章数组PPT课件

《第五章数组PPT课件》由会员分享，可在线阅读，更多相关《第五章数组PPT课件（100页珍藏版）》请在装配图网上搜索。

1、第五章第五章 数组数组 第一节第一节 一维数组一维数组第二节第二节 二维数组二维数组第三节第三节 字符数组和字符串类型字符数组和字符串类型第一节第一节 一维数组一维数组一、为什么要使用数组通过前面几章的学习，我们已经可以编写程序来解决各种相当复杂的问题了，但是当需要处理的数据比较多时，仅依靠前面的知识是不够的，即使简单的问题也可能需要比较复杂的程序来处理。请看下面的例子：例题：输入50个学生的某门课程的成绩，打印出低于平均分的学生序号与成绩。【分析】在解决这个问题时，虽然可以通过一个变量来累加读入的50个成绩求出学生的总分，进而求出平均分。但因为只有读入最后一个学生的分数后才能求得平均分，并且

2、要求打印出低于平均分的学生序号和成绩，故必须把50个学生的成绩都保留起来，然后逐个和平均分比较，把低于平均分的成绩打印出来。如果，用简单变量a1，a2,，a50存储这些数据，要用50个变量保存输入的数据，程序片断如下：cina1a2a10;cina41a42a50;注意，如果真正要像上面这样编写程序，则上面的所有省略号必须用完整的语句写出来。可以看出，这样的程序是多么繁琐。如果说处理的数据规模达到成千上万，上面的例子单单读入就会异常复杂，电脑的优势没有得到体现。从以上的讨论可以看出，如果只使用简单变量处理大量数据，就必须使用大量只能单独处理的变量，即使是简单问题也需要编写冗长的程序。选手们可能

3、已经看出，我们需要把一大批具有相同性质的数据组合成一个新类型的变量，可以用简单的程序（比如循环50次）对这个新变量的各个分量进行相同的处理，每个分量仍然保留单个变量的所有性质（在上面的例子中，各分量是整型变量或实型变量的性质）。如果能像数学中使用下标变量ai形式表示这50个数，则问题就容易实现。在C+语言中，具有下标性质的数据类型是数组。如果使用数组，上面的问题就变得十分简单、清晰。例如，读入50个学生的成绩，只需写如下语句即可：for(int i=1;iai;在这里引用了带下标的变量（分量变量称为数组元素）ai来代替a1,a2,a50,方括号中的i称为下标，当循环变量i=1时ai就是a1；当

4、i=2时ai就是a2；当i=50时ai就是a50。输入的时候，让i从1变化到50，循环体内输入语句中的ai也就分别代表了a1,a2,a50这50个带下标的变量。这样上述问题的程序可写为：tot=0;/tot存储50个学生的总分for(int i=1;iai;tot+=ai;ave=tot/50;/计算平均分for(int i=1;i=50;+i)if(aiave)coutNo.i ai;/如果第i个同学成绩小于平均分，则将输出这个学生的序号和成绩。要在程序中使用下标变量，必须先说明这些下标变量的整体为数组，即数组是若干个同名（如上面的下标变量的名字都为a）下标变量的集合，这些变量的类型全部一致

5、。二、一维数组的定义当数组中每个元素只带有一个下标时，我们称这样的数组为一维数组。数组的定义格式如下：类型标识符 数组名常量表达式说明：数组名的命名规则与变量名的命名规则一致。常量表达式表示数组元素的个数。可以是常量和符号常量，但不能是变量。例如：int a10;/数组a定义是合法的 int bn;/数组b定义是非法的 其中，a是一维数组的数组名，该数组有10个元素，依次表示为：a0,a1,a2,a3,a4,a5，a6,a7,a8,a9。需要注意的是：a10不属于该数组的空间范围。当在说明部分定义了一个数组变量之后,C+编译程序为所定义的数组在内存空间开辟一串连续的存储单元，每个数组第一个元素

6、的下标都是0，因此第一个元素为第0个数组元素。例如：上例中的a数组在内存的存储如表所示：a数组共有10个元素组成，在内存中10个数组元素共占10个连续的存储单元。a数组最小下标为0，最大下标9。按定义a数组所有元素都是整型变量。a0 a1 a2 a3 a4 a5 a6 a7 a8 a9三、一组数组的引用三、一组数组的引用 通过给出的数组名称和这个元素在数组中的位置编号(即下标)，程序可以引用这个数组中的任何一个元素。一维数组元素的引用格式：一维数组元素的引用格式：数组名数组名下标下标例如：若i、j都是int型变量，则 a5 ai+j ai+都是合法的元素。说明：说明：(1)下标可以是任意值为整

7、型的表达式，该表达式里可以包含变量和函数调用。引用时，下标值应在数组定义的下标值范围内。(2)数组的精妙在于下标可以是变量，通过对下标变量值的灵活控制，达到灵活处理数组元素的目的。(3)C+语言只能逐个引用数组元素，而不能一次引用整个数组。(4)数组元素可以像同类型的普通变量那样使用，对其进行赋值和运算的操作，和普通变量完全相同。例如：c10=34;实现了给c10赋值为34。四、一维数组的初始化 数组的初始化可以在定义时一并完成。格式：类型标识符 数组名常量表达式=值1，值2，例如：int a5=1,2,3,4,5说明：(1)在初值列表中可以写出全部数组元素的值，也可以写出部分。例如，以下方式

8、可以对数组进行初始化：int x10=0,1,2,3,4;该方法仅对数组的前5个元素依次进行初始化，其余值为0。(2)对数组元素全部初始化为0，可以简写为：。例如：int a5=;将数组a的5个元素都初始化为0。【说明说明】程序1、程序2和程序3的区别在于数组定义在int main()之外与之内，程序1中数组定义放在int main()之外，其初始值是0值。程序2中数组定义放在int main()之内，其初始值是随机的。程序2中数组定义放在int main()之内，只给a0、a1赋初值，但后面的a2a4元素自动赋0值。五、数组越界五、数组越界 C+语言规定，使用数组时，要注意：(1)、数组元素

9、的下标值为正整数。(2)、在定义元素个数的下标范围内使用。然而，当在程序中把下标写成负数、大于数组元素的个数时，程序编译的时候是不会出错的。例如：int a10;a-3=5;a20=15;a10=20;int k=a30 这些语句的语法是正确的，能够通过程序的编译。然而，它们要访问的数组元素并不在数组的存储空间的，这种现象叫数组越界。例如下面程序：#includeusing namespace std;int main()int a5;for(int i=0;i=10;i+)ai=i;coutai;return 0;【说明说明】该程序能够通过编译，也能运行出结果，程序的问题是定义a5，使用时数

10、组下标超过了4。C+语言中，数组越界访问系统时不一定会给出任何的提示，也就是说，程序可以超出数组边界进行读/写，从而造成内存的混乱。数组越界是实际编程中常见的错误，而且这类错误往往难以捕捉。因为越界语句本身并不一定导致程序立即出错，可能在遇到某些数据时才导致错误，有时由于越界，意外地改变了变量或指令，导致在调试器里调试的时候，程序不按照应当的次序运行的怪现象。六、一维数组的应用例5.1 输入n个数,要求程序按输入时的逆序把这n个数打印出来，已知整数不超过100个。也就是说，按输入相反顺序打印这n个数。【分析】我们可定义一个数组a用以存放输入的n个数,然后将数组a中的内容逆序输出。#includ

11、e#includeint a100;int a100;int main()int main()int x,n=0;int x,n=0;while(scanf(%d,&x)=1)while(scanf(%d,&x)=1)an+=x;an+=x;/相当相当an=x;n+;an=x;n+;for(int i=n-1;i=1;-i)for(int i=n-1;i=1;-i)printf(%d,ai);printf(%d,ai);/注意注意%d%d后面有一个空格，保证行首行尾均无空格后面有一个空格，保证行首行尾均无空格 printf(%dn,a0);printf(%dn,a0);return 0;ret

12、urn 0;【说明】：语句int a100声明了一个包含100个整型变量的数组，它们是：a0，a1，a2，a99。注意，没有a100。在上述程序中，数组a被声明在main函数的外面。只有放在外面时，数组a才可以开得很大；放在main函数内时，数组稍大就会异常退出。它的道理将在后面讨论，只需要记住规则即可。数组不能够进行赋值操作：如果声明的是int aMAXN，bMAXN,是不能赋值b=a的(Pascal语言可以的)。如果要从数组a复制k个元素到数组b，可以这样做：memcpy(b,a,sizeof(int)*k)。当然了，如果数组a和b都是浮点型的，复制时要写成memcpy(b,a,sizeo

13、f(double)*k)。如果需要把数组a全部复制到数组b中，可以写得简单一些：memcpy(b,a,sizeof(a)。使用memcpy函数要包含头文件cstring。例5.2 将a数组中第一个元素移到数组末尾,其余数据依次往前平移一个位置。【分析】为完成题目所要求的操作，其算法应该包括以下几个主要步骤：把第一个元素的值取出放在一个临时单元 temp中；通过 a2a1,a3a2,a4a3，anan-1,实现其余元素前移 将 temp值送入an.#include#include /调用setw函数需注明使用该库const int n=10;using namespace std;int an,

14、temp;int main()coutread n datasendl;for(int i=0;iai;temp=a0;for(int i=0;in-1;+i)ai=ai+1;an-1=temp;coutResult:endl;for(int i=0;in;+i)coutsetw(3)ai;/setw函数控制输出场宽return 0;运行结果:read 10 datas:1 2 3 4 5 6 7 8 9 10 Result:2 3 4 5 6 7 8 9 10 1 例5.3 宾馆里有一百个房间，从1-100编了号。第一个服务员把所有的房间门都打开了，第二个服务员把所有编号是2的倍数的房间“相

15、反处理”，第三个服务员把所有编号是3的倍数的房间作“相反处理”，以后每个服务员都是如此。当第100个服务员来过后，哪几扇门是打开的。（所谓“相反处理”是：原来开着的门关上，原来关上的门打开。）【分析】此题较简单，用a1,a2,an表示编号为1，2，3，,n的门是否开着。模拟这些操作即可，参考程序如下：#include#include#define MAXN 100+10int aMAXN;int main()int n,k,first=1;memset(a,0,sizeof(a);for(int i=1;i=100;+i)for(int j=1;j=100;+j)if(j%i=0)aj=!aj

16、;for(int i=1;i=100;+i)if(ai)if(first)first=0;else printf();printf(%d,i);printf(n);return 0;运行结果：14 9 16 25 36 49 64 81 100【说明】：memset(a,0,sizeof(a)的作用是把数组a清零，它在cstring中定义。虽然也能用for循环完成相同的任务，但是用memset又方便又快捷。另一个技巧在输出：为了避免输出多余空格，设置了一个标志变量first，可以表示当前要输出是否为第一个。第一个变量前不应该有空格，但其他都有。例5.4 约瑟夫问题：N个人围成一圈，从第一个人开

17、始报数，数到M的人出圈；再由下一个人开始报数，数到M的人出圈；输出依次出圈的人的编号。N，M由键盘输入。【分析】（1）由于对于每个人只有出圈和没有圈两种状态，因此可以用布尔型标志数组存储游戏 过程中每个人的状态。不妨用true表示出圈，false 表示没有出圈。（2）开始的时候，给标志数组赋初值为false，即全部在圈内。（3）模拟报数游戏的过程，直到所有的人出圈为止。程序如下：#includeusing namespace std;int n,m,s,f,t;bool a101;/根据题意开出数组大小int main()cinnm;/共n人，报到m出圈 coutendl;for(t=1;t=

18、n;+t)at=false;/等同于memset(a,0,sizeof(a),要调用cstring库 f=0;t=0;s=0;/刚开始所有变量默认值也是0,或者用f=t=s=0;do +t;/逐个枚举圈中的所有位置 if(t=n+1)t=1;/数组模拟环状，最后一个与第一个相连 if(at=false)+s;/第t个位置上有人则报数 if(s=m)/当前报的数是m s=0;/计数器清零 coutt;/输出出圈人的编号 at=true;/此处的人已出圈，设置为空 f+;/出圈的人数增加一个 while(f!=n);/直到所有的人都出圈为止 return 0;运行结果：输入：8 5输出：5 2 8

19、 7 1 4 6 3这是一个在算法设计上很有名气的经典约瑟夫（Josephu）问题，它有很多变例。如猴子选大王、持密码报数、狐狸追兔子等（见上机练习）。例例5.5 5.5 输入输入n n个整数个整数,存放在数组存放在数组a1a1至至anan 中，输出最大数中，输出最大数所在位置所在位置(n=10000)(n=10000)。输入样例：输入样例：5 67 43 90 78 32输出样例：输出样例：3 【分析分析】设maxa存放最大值，k存放对应最大值所在的数组位置，maxa的初值为a1，k的初值对应为1，枚举数组元素，找到比当前maxa大的数成为maxa的新值，k值为对应位置，输出最后的k值。程序

20、如下程序如下：#include using namespace std;const int MAXN=10001;int main()int aMAXN;/定义10001个数组 int i,n,maxa,k;cinn;for(i=1;iai;/读入n个存到a1-an中 maxa=a1;k=1;/赋最大值初值和初始位置 for(i=2;imaxa)/枚举数组，找到最大数和位置 maxa=ai;k=i;coutk;/输出最大数所在数组中的位置 return 0;例例5.6 编程输入十个正整数，然后自动按从大到小的顺序输出。（冒泡排序）编程输入十个正整数，然后自动按从大到小的顺序输出。（冒泡排序）【

21、问题分析问题分析】用循环把十个数输入到A数组中；从a1到a10，相邻的两个数两两相比较，即：a1与a2比，a2与a3比，a9与a10比。只需知道两个数中的前面那元素的标号，就能进行与后一个序号元素（相邻数）比较，可写成通用形式ai与ai+1比较，那么，比较的次数又可用1(n-i)循环进行控制(即循环次数与两两相比较时前面那个元素序号有关)；在每次的比较中，若较大的数在后面，就把前后两个对换，把较大的数调到前面，否则不需调换位置。下面例举5个数来说明两两相比较和交换位置的具体情形：5 6 4 3 7 5和6比较，交换位置，排成下行的顺序；6 5 4 3 7 5和4比较，不交换，维持同样的顺序；6

22、 5 4 3 7 4和3比较，不交换，顺序不变 6 5 4 3 7 3和7比较，交换位置，排成下行的顺序；6 5 4 7 3 经过（1（n-1）次比较后，将3调到了末尾。经过第一轮的1(N-1)次比较，就能把十个数中的最小数调到最末尾位置，第二轮比较1(N-2)次进行同样处理，又把这一轮所比较的“最小数”调到所比较范围的“最末尾”位置；每进行一轮两两比较后，其下一轮的比较范围就减少一个。最后一轮仅有一次比较。在比较过程中，每次都有一个“最小数”往下“掉”，用这种方法排列顺序，常被称之为“冒泡法”排序。程序如下程序如下：#includeusing namespace std;const int

23、n=10;int an+1;/定义数组int main()for(int i=1;iai;/输入十个数 for(int i=1;i=n-1;+i)/冒泡法排序 for(int j=1;j=n-i;+j)/两两相比较 if(ajaj+1)swap(aj,aj+1);/比较与交换 for(int i=1;i=n;+i)cout ai;/输出排序后的十个数 coutfloor(sqrt(N)为止；打印输出a数组中留下来、未被筛掉的各元素值，并按每行五个数显示。用筛法求素数的过程示意如下（图中用下划线作删去标志）：2 3 4 5 6 7 8 9 10 11 12 13 14 1598 99 100 /

24、置数 2 3 4 5 6 7 8 9 10 11 12 13 14 1598 99 100 /筛去被2整除的数 2 3 4 5 6 7 8 9 10 11 12 13 14 1598 99 100 /筛去被3整除的数 2 3 4 5 6 7 8 9 10 11 12 13 14 1598 99 100 /筛去被整除的数程序如下：#include#include /在Dev C+中可调用数学函数库cmath#includeusing namespace std;const int n=100;int t;bool an+1;int main()for(int i=0;i=n;+i)ai=true

25、;/等同于memset(a,1,sizeof(a),要调用cstrin库 a1=false;for(int i=2;i=sqrt(n);+i)if(ai)for(int j=2;j=n/i;+j)ai*j=false;t=0;for(int i=2;i=n;+i)if(ai)coutsetw(5)i;t+;if(t%5=0)coutendl;return 0;【上机练习】1、与指定数字相同的数的个数【1.6编程基础之一维数组01】输出一个整数序列中与指定数字相同的数的个数。输入:输入包含三行：第一行为N，表示整数序列的长度(N=100)；第二行为N个整数，整数之间以一个空格分开；第三行包含一个

26、整数，为指定的数字m。输出:输出为N个数中与m相同的数的个数。样例输入:3 2 3 2 2样例输出:2【上机练习】2.陶陶摘苹果【1.6编程基础之一维数组02】Noip2005普及组第1题 陶陶家的院子里有一棵苹果树，每到秋天树上就会结出10个苹果。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有个30厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。现在已知10个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。输入:包括两行数据。第一行包含10个100到200之间(包括100和200)的整数(以厘米

27、为单位)分别表示10个苹果到地面的高度，两个相邻的整数之间用一个空格隔开。第二行只包括一个100到120之间(包含100和120)的整数(以厘米为单位)，表示陶陶把手伸直的时候能够达到的最大高度。输出:包括一行，这一行只包含一个整数，表示陶陶能够摘到的苹果的数目。样例输入:100 200 150 140 129 134 167 198 200 111 110样例输出:5【上机练习】3.计算书费【1.6编程基础之一维数组03】下面是一个图书的单价表：计算概论 28.9元/本 数据结构与算法 32.7元/本 数字逻辑 45.6元/本 C+程序设计教程 78元/本 人工智能 35 元/本 计算机体系

28、结构 86.2元/本 编译原理 27.8元/本 操作系统 43元/本 计算机网络 56元/本 JAVA程序设计 65元/本 给定每种图书购买的数量，编程计算应付的总费用。输入:输入一行，包含10个整数(大于等于0，小于等于100)，分别表示购买的计算概论、数据结构与算法、数字逻辑、C+程序设计教程、人工智能、计算机体系结构、编译原理、操作系统、计算机网络、JAVA程序设计的数量（以本为单位）。每两个整数用一个空格分开。输出:输出一行，包含一个浮点数f，表示应付的总费用。精确到小数点后一位。样例输入:1 5 8 10 5 1 1 2 3 4样例输出:2140.2【上机练习】4.数组逆序重【1.6

29、编程基础之一维数组04】将一个数组中的值按逆序重新存放。例如，原来的顺序为8,6,5,4,1。要求改为1,4,5,6,8。输入:输入为两行：第一行数组中元素的个数n（1n100)，第二行是n个整数，每两个整数之间用空格分隔。输出:输出为一行：输出逆序后数组的整数，每两个整数之间用空格分隔。样例输入:5 8 6 5 4 1样例输出:1 4 5 6 8【上机练习】5.年龄与疾病【1.6编程基础之一维数组05】某医院想统计一下某项疾病的获得与否与年龄是否有关，需要对以前的诊断记录进行整理，按照0-18、19-35、36-60、61以上（含61）四个年龄段统计的患病人数占总患病人数的比例。输入:共2行

30、，第一行为过往病人的数目n（0n=100)，第二行为每个病人患病时的年龄。输出:按照0-18、19-35、36-60、61以上(含61)四个年龄段输出该段患病人数占总患病人数的比例，以百分比的形式输出，精确到小数点后两位。每个年龄段占一行，共四行。样例输入:10 1 11 21 31 41 51 61 71 81 91样例输出:20.00%20.00%20.00%40.00%【上机练习】6.校门外的树【1.6编程基础之一维数组06】Noip2005普及组第2题 某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L

31、的位置；数轴上的每个整数点，即0，1，2，L，都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。输入:第一行有两个整数L（1=L=10000）和 M（1=M=100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。对于20%的数据，区域之间没有重合的部分；对于其它的数据，区域之

32、间有重合的情况。输出:包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。样例输入:样例输出:500 3 298 150 300 100 200 470 471【上机练习】7.向量点积计算【1.6编程基础之一维数组07】在线性代数、计算几何中，向量点积是一种十分重要的运算。给定两个n维向量a=(a1,a2,.,an)和b=(b1,b2,.,bn)，求点积ab=a1b1+a2b2+.+anbn。输入:第一行是一个整数n(1=n=1000)。第二行包含n个整数a1,a2,.,an。第三行包含n个整数b1,b2,.,bn。相邻整数之间用单个空格隔开。每个整数的绝对值都不超过1000。输出:一个

33、整数，即两个向量的点积结果。样例输入:3 1 4 6 2 1 5样例输出:36【上机练习】8.开关灯【1.5编程基础之循环控制28】假设有N盏灯(N为不大于5000的正整数)，从1到N按顺序依次编号，初始时全部处于开启状态；有M个人(M为不大于N的正整数)也从1到M依次编号。第一个人(1号)将灯全部关闭，第二个人(2号)将编号为2的倍数的灯打开，第三个人(3号)将编号为3的倍数的灯做相反处理（即将打开的灯关闭，将关闭的灯打开）。依照编号递增顺序，以后的人都和3号一样，将凡是自己编号倍数的灯做相反处理。请问：当第M个人操作之后，哪几盏灯是关闭的，按从小到大输出其编号，其间用逗号间隔。输入:输入正

34、整数N和M，以单个空格隔开。输出:顺次输出关闭的灯的编号，其间用逗号间隔。样例输入:10 10样例输出:1,4,9【上机练习】9.查找特定的值【1.9编程基础之顺序查找01】在一个序列(下标从1开始)中查找一个给定的值，输出第一次出现的位置。输入:第一行包含一个正整数n，表示序列中元素个数。1=n=10000。第二行包含n个整数，依次给出序列的每个元素，相邻两个整数之间用单个空格隔开。元素的绝对值不超过10000。第三行包含一个整数x，为需要查找的特定值。x的绝对值不超过10000。输出:若序列中存在x，输出x第一次出现的下标；否则输出-1。样例输入:5 2 3 6 7 3 3样例输出:2【上

35、机练习】9.查找特定的值【1.9编程基础之顺序查找01】在一个序列(下标从1开始)中查找一个给定的值，输出第一次出现的位置。输入:第一行包含一个正整数n，表示序列中元素个数。1=n=10000。第二行包含n个整数，依次给出序列的每个元素，相邻两个整数之间用单个空格隔开。元素的绝对值不超过10000。第三行包含一个整数x，为需要查找的特定值。x的绝对值不超过10000。输出:若序列中存在x，输出x第一次出现的下标；否则输出-1。样例输入:5 2 3 6 7 3 3样例输出:2【上机练习】10.不高兴的津津【1.9编程基础之顺序查找03】Noip2004普及组第1题 津津上初中了。妈妈认为津津应该

36、更加用功学习，所以津津除了上学之外，还要参加妈妈为她报名的各科复习班。另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。但是津津如果一天上课超过八个小时就会不高兴，而且上得越久就会越不高兴。假设津津不会因为其它事不高兴，并且她的不高兴不会持续到第二天。请你帮忙检查一下津津下周的日程安排，看看下周她会不会不高兴；如果会的话，哪天最不高兴。输入:包括七行数据，分别表示周一到周日的日程安排。每行包括两个小于10的非负整数，用空格隔开，分别表示津津在学校上课的时间和妈妈安排她上课的时间。输出:包括一行，这一行只包含一个数字。如果不会不高兴则输出0，如果会则输出最不高兴的是周几（用1,2,3,4,5,6,7分

37、别表示周一，周二，周三，周四，周五，周六，周日）。如果有两天或两天以上不高兴的程度相当，则输出时间最靠前的一天。样例输入:样例输出:5 3 3 6 2 7 2 5 3 5 4 0 4 0 6 【上机练习】11.最大值和最小值的差【1.9编程基础之顺序查找05】输出一个整数序列中最大的数和最小的数的差。输入:第一行为M，表示整数个数，整数个数不会大于10000；第二行为M个整数，以空格隔开，每个整数的绝对值不会大于10000。输出:输出M个数中最大值和最小值的差。样例输入:5 2 5 7 4 2样例输出:5 【上机练习】12.不与最大数相同的数字之和【1.9编程基础之顺序查找07】输出一个整数数

38、列中不与最大数相同的数字之和。输入:输入分为两行：第一行为N(N为接下来数的个数，N=100)；第二行N个整数，数与数之间以一个空格分开，每个整数的范围是-1000,000到1000,000。输出:输出为N个数中除去最大数其余数字之和。样例输入:3 1 2 3样例输出:3 【上机练习】13.白细胞计数【1.9编程基础之顺序查找08】医院采样了某临床病例治疗期间的白细胞数量样本n份，用于分析某种新抗生素对该病例的治疗效果。为了降低分析误差，要先从这n份样本中去除一个数值最大的样本和一个数值最小的样本，然后将剩余n-2个有效样本的平均值作为分析指标。同时，为了观察该抗生素的疗效是否稳定，还要给出该

39、平均值的误差，即所有有效样本（即不包括已扣除的两个样本）与该平均值之差的绝对值的最大值。现在请你编写程序，根据提供的n个样本值，计算出该病例的平均白细胞数量和对应的误差。输入:输入的第一行是一个正整数n（2 n=300），表明共有n个样本。以下共有n行，每行为一个浮点数，为对应的白细胞数量，其单位为109/L。数与数之间以一个空格分开。输出:输出为两个浮点数，中间以一个空格分开。分别为平均白细胞数量和对应的误差，单位也是109/L。计算结果需保留到小数点后2位。样例输入:样例输出:5 11.00 1.00 12.0 13.0 11.0 9.0 10.0 【上机练习】14.直方图【1.9编程基础

40、之顺序查找09】给定一个非负整数数组，统计里面每一个数的出现次数。我们只统计到数组里最大的数。假设 Fmax（Fmax10000）是数组里最大的数，那么我们只统计0,1,2.Fmax里每个数出现的次数。输入:第一行n是数组的大小。1=n=10000。紧接着一行是数组的n个元素。输出:按顺序输出每个数的出现次数，一行一个数。如果没有出现过，则输出0。对于例子中的数组，最大的数是3，因此我们只统计0,1,2,3的出现频数。样例输入:5 1 1 2 3 1样例输出:0 3 1 1 【上机练习】15.最长平台【1.9编程基础之顺序查找12】已知一个已经从小到大排序的数组，这个数组的一个平台（Plate

41、au）就是连续的一串值相同的元素，并且这一串元素不能再延伸。例如，在 1，2，2，3，3，3，4，5，5，6中1，2-2，3-3-3，4，5-5，6都是平台。试编写一个程序，接收一个数组，把这个数组最长的平台找出 来。在上面的例子中3-3-3就是最长的平台。输入:第一行有一个整数n，为数组元素的个数。第二行有n个整数，整数之间以一个空格分开。输出:输出最长平台的长度。样例输入:10 1 2 2 3 3 3 4 5 5 6样例输出:3 【上机练习】16.整数去重【1.9编程基础之顺序查找13】给定含有n个整数的序列，要求对这个序列进行去重操作。所谓去重，是指对这个序列中每个重复出现的数，只保留该

42、数第一次出现的位置，删除其余位置。输入:输入包含两行：第一行包含一个正整数n（1=n=20000），表示第二行序列中数字的个数；第二行包含n个整数，整数之间以一个空格分开。每个整数大于等于10、小于等于100。输出:输出只有一行，按照输入的顺序输出其中不重复的数字，整数之间用一个空格分开。样例输入:5 10 12 93 12 75样例输出:10 12 93 75【上机练习】17.铺地毯【1.9编程基础之顺序查找14】Noip2011提高组第1题 为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有n张地毯，编号从1到n。现在将这些地

43、毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。输入输出样例1说明：如下图，1号地毯用实线表示，2号地毯用虚线表示，3号用双实线表示，覆盖点（2，2）的最上面一张地毯是3号地毯。输入输出样例2说明：如下图，1号地毯用实线表示，2号地毯用虚线表示，3号用双实线表示，覆盖点（4，5）的最上面一张地毯是3号地毯。【上机练习】输入:第一行，一个整数n，表示总共有n张地毯。接下来的n行中，第i+1行表示编号i的地毯的信息，包含四个正整数a，b，g，

44、k，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标（a，b）以及地毯在x轴和y轴方向的长度。第n+2行包含两个正整数x和y，表示所求的地面的点的坐标（x，y）。输出:输出共1行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1。样例输入:样例输出:样例#1：样例#1：3 31 0 2 30 2 3 32 1 3 32 2样例#2：样例#2：3 -11 0 2 30 2 3 32 1 3 34 5第二节第二节 二维数组二维数组一、二维数组的定义当一维数组元素的类型也是一维数组时，便构成了“数组的数组”，即二维数组。二维数组定义的一般格式：数据类型 数组名常量表达式1

45、常量表达式2；例如：int a410;a数组实质上是一个有4行、10列的表格，表格中可储存40个元素。第1行第1列对应a数组的a00，第n行第m列对应数组元素an-1m-1。说明：当定义的数组下标有多个时，我们称为多维数组，下标的个数并不局限在一个或二个，可以任意多个，如定义一个三维数组a和四维数组b：int a10035;int b10010035;多维的数组引用赋值等操作与二维数组类似。二、二维数组元素的引用二维数组的数组元素引用与一维数组元素引用类似，区别在于二维数组元素的引用必须给出两个下标。引用的格式为：下标1下标2说明：显然，每个下标表达式取值不应超出下标所指定的范围，否则会导致致

46、命的越界错误。例如,设有定义：int a35;则表示a是二维数组（相当于一个3*5的表格），共有3*5=15个元素，它们是：a00 a01 a02 a03 a04a10 a11 a12 a13 a14a20 a21 a22 a23 a24因此可以看成一个矩阵（表格），a23即表示第3行第4列的元素。三、二维数组的初始化二维数组的初始化和一维数组类似。可以将每一行分开来写在各自的括号里，也可以把所有数据写在一个括号里。例如：int direct42=1,0,0,1,-1,0,0,-1 int direct42=1,0,0,1,-1,0,0,-1 /尽量不要用四、二维数组程序设计例5.8 设有一程

47、序#include#include#includeconst int n=3;using namespace std;int an+1n+1;int main()for(int i=1;i=n;+i)for(int j=1;jaij;for(int i=1;i=n;+i)for(int j=1;j=n;+j)coutsetw(5)aji;coutendl;return 0;程序的输入:2 1 33 3 11 2 1程序的输出:2 3 11 3 23 1 1例5.9 已知一个6*6的矩阵（方阵），把矩阵二条对角线上的元素值加上10，然后输出这个新矩阵。【分析】矩阵即表格，是一个二维数组，有6行6

48、列共36个元素，每个矩阵都有二条对角线，本题难点在于对角线的元素怎么确定。#include#includeusing namespace std;int a77;int main()for(int i=1;i=6;+i)/输入矩阵元素 for(int j=1;jaij;for(int i=1;i=6;+i)/更改对角线上元素的值 for(int j=1;j=6;+j)if(i=j)|(i+j=7)aij+=10;/寻找对角线的特征 for(int i=1;i=6;+i)/输出6行6列的矩阵元素 for(int j=1;j=6;+j)coutsetw(5)aij;coutendl;return

49、0;例5.10 大部分元素是0的矩阵称为稀疏矩阵，假设有k个非0元素，则可把稀疏矩阵用K*3的矩阵简记之，其中第一列是行号，第二列是列号，第三列是该行、该列下的非元素的值。如：0 0 0 5 写简记成：1 4 5 /第1行第4列有个数是50 2 0 0 2 2 2 /第2行第2列有个数是20 1 0 0 3 2 1 /第3行第2列有个数是1试编程读入一稀疏矩阵，转换成简记形式，并输出。【分析】本题中需要解决的主要问题是查找非零元素并记忆位置。将原始矩阵存于数组a。转换后的矩阵存于数组b，当然b数组的行数可以控制在一个小范围内。#include#includeconst int n=3,m=5;

50、using namespace std;int main()int an+1m+1,b1014,k=0;for(int i=1;i=n;+i)/矩阵初始 for(int j=1;jaij;for(int i=1;i=n;+i)for(int j=1;j=m;+j)if(aij!=0)/找到非零值，存储 +k;bk1=i;bk2=j;bk3=aij;for(int i=1;i=k;+i)/输出 for(int j=1;j=3;+j)coutsetw(3)bij;coutendl;return 0;运行结果：输入：0 0 0 0 5 0 0 4 0 0 1 0 0 0 1输出：1 5 5 2 3

51、4 3 1 1 3 5 1例5.11 打印杨辉三角形的前10行。杨辉三角形如下图：1 1 1 1 1 1 1 2 1 1 2 1 1 3 3 1 1 3 3 11 4 6 4 1 1 4 6 4 1 图5-1 图5-2【问题分析】观察图5-1，大家不容易找到规律，但是如果将它转化为图5-2，不难发现杨辉三角形其实就是一个二维表的小三角形部分，假设通过二维数组yh存储，每行首尾元素为1，且其中任意一个非首位元素yhij的值其实就是yhi-1j-1与yhi-1j的和，另外每一行的元素个数刚好等于行数。有了数组元素的值，要打印杨辉三角形，只需要控制好输出起始位置就行了。#include#includ

52、eusing namespace std;int main()int a1111;a11=1;/设定第一行的值 for(int i=2;i=10;+i)/从第二行开始推 ai1=1;aii=1;/设定每一行的首尾值为1 for(int j=2;j=i-1;+j)/当前行非首尾的数 aij=ai-1j-1+ai-1j;/每个数等于上一行的二个数之和 for(int i=1;i=10;i+)if(i!=10)coutsetw(30-3*i);/控制每行的起始位置，即空格数量 for(int j=1;j=i;j+)coutsetw(6)aij;coutendl;return 0;例5.12 输入一串

53、字符,字符个数不超过100,且以“.”结束。判断它们是否构成回文。【分析】所谓回文指从左到右和从右到左读一串字符的值是一样的，如12321,ABCBA,AA等。先读入要判断的一串字符（放入数组letter中），并记住这串字符的长度，然后首尾字符比较，并不断向中间靠拢，就可以判断出是否为回文。程序如下：#includeusing namespace std;int main()char ch,letter101;int i=0,j=1;coutch;while(ch!=.)/读入一个字符串以.号结束 +i;letteri=ch;cinch;while(j=i)coutYesendl;else c

54、outNoendl;return 0;例5.13 蛇形填数 在n*n方阵里填入1,2,3,n*n，要求填成蛇形。例如n=4时方阵为：10 11 12 1 9 16 13 2 8 15 14 3 7 6 5 4 上面的方阵中，多余的空格只是为了便于观察规律，不必严格输出，n=8。【分析】：类比数学中的矩阵，我们可以用一个所谓的二维数组来储存题目中的方阵。只需声明一个int aMAXNMAXN，就可以获得一个大小为MAXNMAXN的方阵。在声明时，两维的大小不必相同，因此也可以声明int a3050这样的数组，第一维下标范围是0,1,2,29，第二维下标范围是0,1,2,49。让我们从1开始依次填

55、写。设“笔”的坐标为(x,y)，则一开始x=0，y=n-1，即第0行，第n-1列（别忘了行列的范围是0到n-1，没有第n列）。“笔”的移动轨迹是：下，下，下，左，左，左，上，上，上，右，右，下，下，左，上。总之，先是下，到不能填了为止，然后是左，接着是上，最后是右。“不能填”是指再走就出界（例如45），或者再走就要走到以前填过的格子（例如1213）。如果我们把所有格子初始为0，就能很方便地加以判断。#include#include#define MAXN 10int aMAXNMAXN;int main()int n,x,y,tot=0;scanf(%d,&n);memset(a,0,size

56、of(a);tot=ax=0y=n-1=1;while(totn*n)while(x+1=0&!axy-1)ax-y=+tot;while(x-1=0&!ax-1y)a-xy=+tot;while(y+1n&!axy+1)ax+y=+tot;for(x=0;xn;+x)for(y=0;yn;+y)printf(%3d,axy);printf(n);return 0;【说明】：这段程序充分利用了C+语言简洁的优势。首先，赋值x=0和y=n-1后马上要把它们作为a数组的下标，因此可以合并完成；tot和a0n-1都要赋值1，也可以合并完成。这样，我们用一条语句完成了多件事情，而且并没有牺牲程序的可读

57、性，这段代码的含义显而易见。那4条while语句有些难懂，不过十分相似，因此只需介绍其中的第一条：不断向下走，并且填数。我们的原则是：先判断，再移动，而不是走一步以后发现越界了再退回来。这样，我们需要进行“预判”，即是否越界，以及如果继续往下走会不会到达一个已经填过的格子。越界只需判断x+1n，因为y值并没有修改；下一个格子是(x+1,y)，因此只需ax+1y=0，简写成!ax+1y（其中!是“逻辑非”运算符）。细心的读者也许会发现这里的一个“潜在bug”；如果越界，x+1会等于n，ax+1y将访问非法内存！幸运的是，这样的担心是不必要的。&是短路运算符。如果x+1n为假，将不会计算!ax+1

58、y，也就不会越界了。至于为什么是+tot而不是tot+，留给读者思考。【上机练习】1.矩阵交换行【1.8编程基础之多维数组01】给定一个5*5的矩阵(数学上，一个rc的矩阵是一个由r行c列元素排列成的矩形阵列)，将第n行和第m行交换，输出交换后的结果。输入:输入共6行，前5行为矩阵的每一行元素,元素与元素之间以一个空格分开。第6行包含两个整数m、n，以一个空格分开（1=m,n=5）。输出:输出交换之后的矩阵，矩阵的每一行元素占一行，元素之间以一个空格分开。样例输入:1 2 2 1 2 5 6 7 8 3 9 3 0 5 3 7 2 1 4 6 3 0 8 2 4 1 5样例输出:3 0 8 2

59、 4 5 6 7 8 3 9 3 0 5 3 7 2 1 4 6 1 2 2 1 2【上机练习】2.同行列对角线的格【1.8编程基础之多维数组02】输入三个自然数N，i，j（1=i=n，1=j=n），输出在一个N*N格的棋盘中(行列均从1开始编号)，与格子(i，j)同行、同列、同一对角线的所有格子的位置。如：n=4，i=2，j=3表示了棋盘中的第二行第三列的格子，如下图：当n=4，i=2，j=3时，输出的结果是：(2,1)(2,2)(2,3)(2,4)同一行上格子的位置(1,3)(2,3)(3,3)(4,3)同一列上格子的位置(1,2)(2,3)(3,4)左上到右下对角线上的格子的位置(4,1

60、)(3,2)(2,3)(1,4)左下到右上对角线上的格子的位置【上机练习】输入:一行，三个自然数N，i，j，相邻两个数之间用单个空格隔开(1=N=10)。输出:第一行：从左到右输出同一行格子位置；第二行：从上到下输出同一列格子位置；第三行：从左上到右下输出同一对角线格子位置；第四行：从左下到右上输出同一对角线格子位置。其中每个格子位置用如下格式输出：(x,y)，x为行号，y为列号，采用英文标点，中间无空格。相邻两个格子位置之间用单个空格隔开。样例输入:4 2 3样例输出:(2,1)(2,2)(2,3)(2,4)(1,3)(2,3)(3,3)(4,3)(1,2)(2,3)(3,4)(4,1)(3

61、,2)(2,3)(1,4)【上机练习】3.计算矩阵边缘元素之和【1.8编程基础之多维数组03】输入一个整数矩阵，计算位于矩阵边缘的元素之和。所谓矩阵边缘的元素，就是第一行和最后一行的元素以及第一列和最后一列的元素。输入:第一行分别为矩阵的行数m和列数n（m100，n100），两者之间以一个空格分开。接下来输入的m行数据中，每行包含n个整数，整数之间以一个空格分开。输出:输出对应矩阵的边缘元素和。样例输入:3 3 3 4 1 3 7 1 2 0 1样例输出:15【上机练习】4.计算鞍点【1.8编程基础之多维数组05】给定一个5*5的矩阵，每行只有一个最大值，每列只有一个最小值，寻找这个矩阵的鞍点

62、。鞍点指的是矩阵中的一个元素，它是所在行的最大值，并且是所在列的最小值。例如：在下面的例子中（第4行第1列的元素就是鞍点，值为8）。输入:输入包含一个5行5列的矩阵。输出:如果存在鞍点，输出鞍点所在的行、列及其值，如果不存在，输出not found。样例输入:11 3 5 6 9 12 4 7 8 10 10 5 6 9 11 8 6 4 7 2 15 10 11 20 25样例输出:4 1 8【上机练习】5.图像相似度【1.8编程基础之多维数组06】给出两幅相同大小的黑白图像（用0-1矩阵）表示，求它们的相似度。说明：若两幅图像在相同位置上的像素点颜色相同，则称它们在该位置具有相同的像素点。

63、两幅图像的相似度定义为相同像素点数占总像素点数的百分比。输入：第一行包含两个整数m和n，表示图像的行数和列数，中间用单个空格隔开。1=m=100,1=n=100。之后m行，每行n个整数0或1，表示第一幅黑白图像上各像素点的颜色。相邻两个数之间用单个空格隔开。之后m行，每行n个整数0或1，表示第二幅黑白图像上各像素点的颜色。相邻两个数之间用单个空格隔开。输出：一个实数，表示相似度（以百分比的形式给出），精确到小数点后两位。样例输入:样例输出:3 3 44.44 1 0 1 0 0 1 1 1 0 1 1 0 0 0 1 0 0 1【上机练习】6.矩阵加法【1.8编程基础之多维数组07】输入两个n

64、行m列的矩阵A和B，输出它们的和A+B。输入:第一行包含两个整数n和m，表示矩阵的行数和列数(1=n=100，1=m=100)。接下来n行，每行m个整数，表示矩阵A的元素。接下来n行，每行m个整数，表示矩阵B的元素。相邻两个整数之间用单个空格隔开，每个元素均在11000之间。输出:n行，每行m个整数，表示矩阵加法的结果。相邻两个整数之间用单个空格隔开。样例输入:样例输出:3 3 2 4 6 1 2 3 5 7 9 1 2 3 8 10 12 1 2 3 1 2 3 4 5 6 7 8 9 【上机练习】7.矩阵乘法【1.8编程基础之多维数组08】计算两个矩阵的乘法。n*m阶的矩阵A乘以m*k阶的

65、矩阵B得到的矩阵C 是n*k阶的，且Cij=Ai0*B0j+Ai1*B1j+Aim-1*Bm-1j(Cij表示C矩阵中第i行第j列元素)。输入:第一行为n,m,k，表示A矩阵是n行m列，B矩阵是m行k列，n,m,k均小于100。然后先后输入A和B两个矩阵，A矩阵n行m列，B矩阵m行k列，矩阵中每个元素的绝对值不会大于1000。输出:输出矩阵C，一共n行，每行k个整数，整数之间以一个空格分开。样例输入:3 2 3 1 1 1 1 1 1 1 1 1 1 1 1样例输出:2 2 2 2 2 2 2 2 2 【上机练习】8.矩阵转置【1.8编程基础之多维数组09】输入一个n行m列的矩阵A，输出它的转

66、置AT。输入:第一行包含两个整数n和m，表示矩阵A的行数和列数(1=n=100，1=m=100)。接下来n行，每行m个整数，表示矩阵A的元素。相邻两个整数之间用单个空格隔开，每个元素均在11000之间。输出:m行，每行n个整数，为矩阵A的转置。相邻两个整数之间用单个空格隔开。样例输入:3 3 1 2 3 4 5 6 7 8 9样例输出:1 4 7 2 5 8 3 6 9【上机练习】9.图像旋转【1.8编程基础之多维数组10】输入一个n行m列的黑白图像，将它顺时针旋转90度后输出。输入:第一行包含两个整数n和m，表示图像包含像素点的行数和列数。1=n=100，1=m=100。接下来n行，每行m个整数，表示图像的每个像素点灰度。相邻两个整数之间用单个空格隔开，每个元素均在0255之间。输出:m行，每行n个整数，为顺时针旋转90度后的图像。相邻两个整数用单个空格隔开。样例输入:3 3 1 2 3 4 5 6 7 8 9样例输出:7 4 1 8 5 2 9 6 3【上机练习】10.图像模糊处理【1.8编程基础之多维数组12】给定m行n列的图像各像素点的灰度值，要求用如下方法对其进行模糊化处理：