七章数组.ppt

北京理工大学 http:/www.bit9.dhs.org/,数组,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 2 页,第七章 数组,第一节 数组的基本概念第二节 一维数组第三节 二维数组第四节 应用实例,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 3 页,7-1 数组的基本概念,一班学生的学习成绩，如何存储和引用？一行文字怎样存储？一个矩阵怎样存储？.,一组具有相同数据类型的数据的有序集合。,？,这些数据的特点：具有相同的数据类型。为了方便地使用这些数据，C语言提供了一种构造数据类型：数组。,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 4 页,7-1 一维数组（续1）,例如：存储学生成绩用整型数组 mark100，存储一行文字用字符数组 str200，存储一个4*6的矩阵用二维整型数组 a46。其中：mark、str、a 是数组名。方括号内是数组的下标。下标的个数称为数组的维数，mark、str是一维数组、a是二维数组。数组的成员称为数组元素。,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 5 页,7-2 一维数组,例如：float mark100;char str200;int a46;数组名 对数组的标识，遵循C语言标识符规则。mark、str、a 是数组名。数据类型 就是数组元素的数据类型，数组元素的类型叫做数组的基类型。mark是 str是 a是 实型数组、字符数组、整型数组,一、一维数组的定义,数据类型 数组名常量表达式,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 6 页,7-2 一维数组（续1）,下标运算符 数组名后面的方括号是下标运算符。不允许使用（）括号。常量表达式 是数组元素的个数，即数组长度。它必须是常量。mark的长度是100，str的长度是200，a的长度是4*6。C语言不允许对数组的大小进行动态说 明，下列语句是错误的。int n=8,a1n;Error:Constant expression required in function main,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 7 页,7-2 一维数组（续2）,数组元素在内存里顺序存放一维数组,二、数组在内存的存放,每个数据元素占用的字节数，就是基类型的字节数,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 8 页,7-2 一维数组（续3）,数组元素的引用方式：数组不能被整体引用，只能引用数组元素，格式：数组名下标表达式 例如：输出学生成绩 for(i=0;i100;i+)printf(“%fn”,marki);下标:下标表达式的值必须是整型数据。辨疑：在说明语句中,方括号内的值是元素个数，如：int a10,说明数组a一共有10个元素。引用时第一个元素的下标是 0，即a0、a1、a9。,三、数组元素的引用,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 9 页,7-2 一维数组（续4）,被称为下标运算符。数组名、数组元素是两种不同性质的数据。数组名是数组的首地址，是一个地址量。数组元素则是数值。引用数组元素时，根据首地址和下标数，计算出该元素的实际地址，取出该地址的内容进行操作。,如引用 mark2:(1)计算 2000+2*4=2008(2)从取出2008的内容,下标运算符,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 10 页,7-2 一维数组（续4）,数组元素的性质 数组元素的性质，与该类型的变量相同。例C7_201：从键盘输入10个整数，再反序输出它们。main()int i,a10;for(i=0;i=0;i-)printf(“%dn”,ai);,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 11 页,7-2 一维数组（续5）,初始化：在说明语句中赋初值。考察例C7_202,例C7_202,结论：1.变量、数组元素不赋初值时，其值不定。2.语句 int a5=1,2,3,4,5;为每一个数组元素赋初值。花括号内数据个数与元素个数一样。此时可省略数组长度，如 int a=1,2,3,4,5。3.当数据个数少于元素个数时，如 int a5=1,2,3，系统为其余元素赋 0。4.数据个数多于元素个数是错误的。给定的数据位置必须连续，如 int a5=1,3,5。,四、一维数组的初始化,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 12 页,7-2 一维数组（续6）,例C6_103:选择法排序 将 23，1，0，43，-3，7 从小到大排列。选择法是取出第一个数，依次和后面的数比较，如果后面的某数小于第一个数，则两个数交换，比较结束后，第一个数则是最小的数。然后第二个数依次和后面的数比较，如果后面的某数小于第二个数，则两个数交换，比较结束后，第二个数则是次小的数；。编程时注意循环变量的始值和终值。,五、一维数组的应用,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 13 页,7-2 一维数组（续7）,i=0,23,1,1,0,0,43,-3,7,-3,t=a0;a0=a1;a1=t;,t=a0;a0=a2;a2=t;,t=a0;a0=a4;a4=t;,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 14 页,7-2 一维数组（续7）,例C7_203,i=1,i=2,i=3,i=4,i=0,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 15 页,7-2 一维数组（续7）,i=0,ar aj,j=1,ar aj,j=2,ar aj,j=3,ar aj,j=4,ar aj,j=5,t=ai;ai=ar;ar=t;,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 16 页,7-2 一维数组（续8）,for(i=0;i a j)r=j;temp=a i;a i=a r;a r=temp;,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 17 页,7-2 一维数组（续9）,例C7_204:起泡法排序,i=0,a5a4a3a2a1a0,i=1,i=2,i=3,i=4,比较 a j a j+1 如果成立两元素交换,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 18 页,7-2 一维数组（续10）,例C6_104:起泡法排序,i=0,a5a4a3a2a1a0,i=1,i=2,i=3,i=4,4,i 控制外层循环:for(i=0;i;i+),n-1,j 控制内层循环:for(j=;j;j+),0,n-1,n-1-i,n-i-1,例C7_204,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 19 页,7-3 二维数组,下标多于一个的数组叫做多维数组。,数组名常量表达式 常量表达式,例如：int a34,b514;a3,4 a(3,4)a(3)(4),一、二维数组的定义,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 20 页,7-3 二维数组(续1）,数组a,a0:,a1:,a2:,a00,a01,a02,a03,a10,a11,a12,a13,a20,a21,a22,a23,a0是数组名，是元素a00的地址,a1是数组名，是元素a10的地址,a2是数组名，是元素a00的地址,数组a有三个分量，a是分量a0的地址,二、二维数组的数组名,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 21 页,7-3 二维数组（续2）,例如：整型数组 bb23=1,2,3,4,5,6;,多维数组存放:多维数组的元素按行顺序存放。,地址 值 数组元素,三、多维数组元素的存放,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 22 页,7-3 二维数组（续3）,可以使用 对数据分组例：int a34=1,2,3,4,5,6,7,8,9 初始化后结果：1 2 3 4 5 6 7 8 9 0 0 0 int a34=1,2,3,4,5,6,7,8,9 初始化后结果：1 2 3 0 4 5 6 0 7 8 9 0,四、二维数组的初始化,例C7_301,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 23 页,7-3 二维数组（续4）,省略下标表达式 当数据元素个数和数据个数一致时，数组说明语句中的第一个下标可以省略。例如：int a4=1,2,3,4,5,6,7,8;int b4=1,2,3,4,5,6,7,8,9;int c22=1,2,3,4,5,6,7,8;初始化结果：,例C7_302,a 结果a0:1 2 3 4a1:5 6 7 8,b 结果：b0:1 2 3 4b1:5 6 7 8b2:9 0 0 0,c 结果：c0:c00:1 2 c01:3 4c1:c10:5 6 c11:7 8,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 24 页,7-3 二维数组（续5）,省略其它位置的下标表达式是错误的。int a2=1,2,3,4,5,6,7,8;int c2 2=1,2,3,4,5,6,7,8;int c22=1,2,3,4,5,6,7,8;,例C7_303,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 25 页,7-3 二维数组（续5）,二维数组举例例C6_204:两个矩阵相乘。1 2 3 4 1 3 5 A=5 6 7 8 B=2 4 6 9 10 11 12 7 9 11 8 10 12C1,1=A1,1*B1,1+A1,2*B2,1+A1,3*B3,1+A1,4*B4,1C1,2=A1,1*B1,2+A1,2*B2,2+A1,3*B3,2+A1,4*B4,2 C3,3=A3,1*B1,3+A3,2*B2,3+A3,3*B3,3+A3,4*B4,3,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 26 页,7-3 二维数组（续6）,分析结果矩阵C有3行3列。重复求一行 for(i=0;in;i+)重复求行中一个元素 for(j=0;jn;j+)重复将每一项加入 for(k=0;km;k+)cij=cij+aik*bkj;,例C7_304,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 27 页,7-4 程序举例,例C7_401:马步遍历问题：已知国际象棋棋盘有 8 8 共64个格子。设计一个程序，使棋子从某位置开始跳马，能够把棋盘上的格子走遍。每个格子只允许走一次。,I=12345678,J=1 2 3 4 5 6 7 8,分析：起点坐标：I(行)、J(列),2 2,落点坐标：X(行)、Y(列),3 4,落点和起点的关系,X12345678,Y=1 2 3 4 5 6 7 8,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 28 页,7-4 程序举例（续1）,可能落点行坐标 X 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8,I=12345678,J=1 2 3 4 5 6 7 8,X12345678,Y=1 2 3 4 5 6 7 8,2 3 3 2 0-1-1 0,I,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 29 页,7-4 程序举例（续2）,可能落点行坐标 X I 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8,I=12345678,J=1 2 3 4 5 6 7 8,X12345678,Y=1 2 3 4 5 6 7 8,2 3 3 2 0-1-1 0,3 4 4 3 1 0 0 1,4 5 5 4 2 1 1 25 6 6 5 3 2 2 36 7 7 6 4 3 3 47 8 8 7 5 4 4 58 9 9 8 6 5 5 69 10 10 9 7 6 6 7,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 30 页,7-4 程序举例（续3）,将 I=1 时的8个可能的落点存入数组 b:b=0，2,3,3,2,0,-1,-1,0;则只要知道起点行坐标 I，就可以求出落点行坐标 X 的8个可能的取值。如：起点行坐标 I=1 则可能的落点行坐标 X 是：X=2，3，3，2，0，-1，-1，0。如：起点行坐标 I=5 则可能的落点行坐标 X 是：X=6，7，7，6，4，3，3，4。由 I 求 X 的公式：X=b k+I-1（其中：k=1,2,.,8）,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 31 页,7-4 程序举例（续4）,可能落点列坐标 Y J 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8,I=12345678,J=1 2 3 4 5 6 7 8,X12345678,Y=1 2 3 4 5 6 7 8,3 2 0-1-1 0 2 3,4 3 1 0 0 1 3 4 5 4 2 1 1 2 4 5 6 5 3 2 2 3 5 6 7 6 4 3 3 4 6 7 8 7 5 4 4 5 7 8 9 8 6 5 5 6 8 910 9 7 6 6 7 9 10,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 32 页,7-4 程序举例（续5）,起点和落点列坐标的关系将 J=1 时的8个可能的落点存入数组 d:d=0，3，2，0，-1，-1，-，2，3;则只要知道起点列坐标 J，就可以求出落点列坐标 Y 的8个可能的取值。如：起点列坐标 J=1 则可能的落点列坐标 Y 是：Y=3，2，0，-1，-1，-1，2，3。如：起点列坐标 J=5 则可能的落点行坐标 Y 是：Y=7，6，4，3，3，4，6，7。由 J 求 Y 的公式：Y=d k+J-1（其中：k=1,2,.,8）,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 33 页,7-4 程序举例（续6）,编程整理数组，将行列关系存入二维数组base82。base82=0，0 2，3，3，2，3，0，2，-1，0，-1，-1，0，-1，2，0，3，,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 34 页,7-4 程序举例（续7）,已知某一个起点 I、J 求落点：X1=base10+I-1,Y1=base11+J-1;落点X2=base20+I-1,Y2=base21+J-1;落点X3=base30+I-1,Y3=base31+J-1;落点X4=base40+I-1,Y4=base41+J-1;落点X5=base50+I-1,Y5=base51+J-1;落点X6=base60+I-1,Y6=base61+J-1;落点X7=base70+I-1,Y7=base71+J-1;落点X8=base80+I-1,Y8=base81+J-1;落点,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 35 页,7-4 程序举例（续8）,修改 base 数组 base93=0，0，0，0，1，2，0，2，1，0，2，-1，0，1，-2，0，-1，-2，0，-2，-1，0，-2，1，0，-1，2,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 36 页,7-4 程序举例（续9）,从可能的8个落点中，选定一个落点for(p=1;p=8;p+)x=i+basep1;y=j+basep2;剔除棋盘外点；剔除已落过棋子点；度数少的点为后继点；该点做落子标记；起点做标记不允许再落子；标记：建数组a99,用aij存i、j点的度数。度数是该点跳棋的方向数，当aij=0时，该点已落过棋子，不能作为落点了。,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 37 页,7-4 程序举例（续10）,度数表,2 3 4 4 4 4 3 2 3 4 6 6 6 6 4 3 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 3 4 6 6 6 6 4 3 2 3 4 4 4 4 3 2,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 38 页,7-4 程序举例（续11）,剔除棋盘外点 if(x=1 m、n 是选定后继落点坐标，min 是起点可跳步的几个点中，度数最少点的度数。,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 39 页,7-4 程序举例（续12）,跳步过程的记录 如果初始点记为1，用数字 164 记载跳步过程。设数组 object99,objectij对应于棋盘上第i行第j列的格子。object11对应棋盘左上角的格，而object6464对应棋盘右下角的格。objrctij存入的数值 m，表示第 m 步跳到该格。,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 40 页,7-4 程序举例（续13）,for(k=1;k=1,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 41 页,7-4 程序举例（续14）,度数表,遍历表,起点 I=J=,落点 1 2 3 4 5 6 7 8 X=Y=,步数,1 2 2 1-1-2-2-1,2 1-1-2-2-1 1 2,1,2,1,2 3 3 2,3 2 2 3,12345678,1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8,1,2,2,3,2 3 3 2,2 3 3 2,3 2 2 3,3 4 4 3 1 1,5 4 2 1 1 2 4 5,2,5,5,3,3,7,7,5,3,3,3,3,1,4 5 5 4 2 1 1 2,3 2 2 3,4,4,2,7,5,4,1,2,2 3 3 2 2 1 1 2,4 3 1 1 3 4,5,5,7,5,2,4,3 4 4 3 1 1,6 5 3 2 2 3 5 6,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 42 页,7-4 程序举例（续15）,度数表数组 a 赋初值。数组说明语句：int a99=0;数组a清零。数组 a 赋度数表：for(i=1;i=1,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 43 页,7-4 程序举例（续16）,改变 base 的排列顺序，可以改变马步遍历的路径,1 2 2 1-1-2-2-12 1-1-2-2-1 1 2,1,2,3,4,5,6,7,8,2 1 2 1-1-2-2-11 2-1-2-2-1 1 2,2,1,3,4,5,6,7,8,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 44 页,7-4 程序举例（续17）,rm0=1;for(cont=1;cont0;)rm1=base11;rm2=base12;base11=baserm01;base12=baserm02;baserm01=rm1;baserm02=rm2;求度数表；马步遍历；输出本次马步的路径；rm0%=8;rm0+;printf(“Continue?(1 OR 0)”);scanf(“%d”,例C7_401,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 45 页,7-4 程序举例（续18）,例C7_402:魔术师的猜牌术魔术师有13张黑桃，牌面朝下。他数到1时最上面的牌为A，把它桌上；第二次数1、2，将第一张牌放在这迭牌的下面，将第二张牌翻过来，正好是黑桃2,.问魔术师手中的牌原始次序是怎样安排的？问题分析与算法设计人工倒推的方法是：桌上放13个空盒排成一圈，从1开始顺序编号。将黑桃A放入1号盒子中，后面对空盒数数，数到几，就把该数的牌放入空盒。注意在计数时要跳过非空的盒。最后牌在盒中的顺序，就是魔术师原来牌的顺序。,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 46 页,7-4 程序举例（续19）,A,2,3,4,5,6,1,7,8,9,10,11,12,13,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 47 页,7-4 程序举例（续20）,int a14;main()int i,n,j=1;/*j:数组(盒子)下标，初始时为1号元素*/printf(The original order of cards is:);for(i=1;i13)j=1;/*j超过最后一个元素则指向1号元素*/if(aj)j+;/*跳过非空的盒子，不计数*/else if(n=i)aj=i;/*若数到第i个空,则放入*/j+;n+;/*对空盒计数，*/*下标指向下1个盒子*/while(n=i);/*控制空盒计数为i*/for(i=1;i=13;i+)/*输出牌的排列顺序*/printf(%d,ai);,例C7_402,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 48 页,再见,再见,