《七章数组.ppt》由会员分享，可在线阅读，更多相关《七章数组.ppt（48页珍藏版）》请在三一文库上搜索。
1、北京理工大学 http:/www.bit9.dhs.org/,数组,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 2 页,第七章 数组,第一节 数组的基本概念 第二节 一维数组 第三节 二维数组 第四节 应用实例,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 3 页,7-1 数组的基本概念,一班学生的学习成绩，如何存储和引用？ 一行文字怎样存储？ 一个矩阵怎样存储 ？,一组具有相同数据类型的数据的有序集合。,？,这些数据的特点：具有相同的数据类型。 为了方便地使用这些数据，C语言提供了一种构造数据类型：数组。,北京理工大学 h
2、ttp:/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; 数组名 对数组的标识
3、，遵循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语言不允许对数组的大小进行动态说 明，下列语句是
4、错误的。 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
5、(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）, 被称为下标运算符。 数组名、数组元素是两种不同性质的数据。 数组名是数组的首地址，是一个地址量。 数组元素则是数值。 引用数组元素时，根据首地址和下标数，计算出该元素的实际地址，取出该地址的内容进
6、行操作。,如引用 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）,初始化：在说明语句中赋初值。
7、考察例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:选择法排序 将
8、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
9、;,北京理工大学 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
10、 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,a5 a4 a3 a2 a1 a0,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,a5 a4 a3 a2 a1 a0,i=1,i=2,i=3,i=4,4,i 控
11、制外层循环: 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,
12、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）,例如：整型数组 b b23= 1,2,3, 4,5,6 ;,多维数组存放: 多维数组的元素按行顺序存放。,地址 值 数组元素,三、多维数组元素的存放,北京理工大学 http:/www.bit9.dhs.org/,共 12 页 第 22 页,
13、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
14、,3,4,5,6,7,8,9; int c22=1,2,3,4,5,6,7,8; 初始化结果：,例C7_302,a 结果 a0: 1 2 3 4 a1: 5 6 7 8,b 结果： b0: 1 2 3 4 b1: 5 6 7 8 b2: 9 0 0 0,c 结果： c0: c00: 1 2 c01: 3 4 c1: 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
15、,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 12 C1,1= A1,1*B1,1 + A1,2*B2,1 + A1,3*B3,1 + A1,4*B4,1 C1,2= A1,1*B1,2 + A1,2*B2,2 + A1,3*B3,2 + A1,4*B4,2 C3,3= A3,1*B1,3
16、+ 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个格子。设计一个程
17、序，使棋子从某位置开始跳马，能够把棋盘上的格子走遍。每个格子只允许走一次。,I= 1 2 3 4 5 6 7 8,J=1 2 3 4 5 6 7 8,分析： 起点坐标： I (行)、J (列),2 2, 落点坐标：X(行)、Y(列),3 4, 落点和起点的关系,X 1 2 3 4 5 6 7 8,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= 1 2 3 4 5 6 7 8,J=1 2 3 4 5 6
18、7 8,X 1 2 3 4 5 6 7 8,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= 1 2 3 4 5 6 7 8,J=1 2 3 4 5 6 7 8,X 1 2 3 4 5 6 7 8,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 2 5 6 6 5 3 2 2 3
19、 6 7 7 6 4 3 3 4 7 8 8 7 5 4 4 5 8 9 9 8 6 5 5 6 9 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
20、，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= 1 2 3 4 5 6 7 8,J=1 2 3 4 5 6 7 8,X 1 2 3 4 5 6 7 8,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
21、6 7 6 4 3 3 4 6 7 8 7 5 4 4 5 7 8 9 8 6 5 5 6 8 9 10 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
22、是： 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
23、+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 程序举例
24、（续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点的度数。 度数是该点跳
25、棋的方向数，当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
26、、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
27、( 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,1 2 3 4 5 6 7 8,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,
28、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
29、页,7-4 程序举例（续16）,改变 base 的排列顺序，可以改变马步遍历的路径,1 2 2 1 -1 -2 -2 -1 2 1 -1 -2 -2 -1 1 2,1,2,3,4,5,6,7,8,2 1 2 1 -1 -2 -2 -1 1 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; bas
30、erm01= 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, . 问魔术师手中的牌原始次序是怎样安排的？ 问题分析与算法设计 人工倒
31、推的方法是： 桌上放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
32、号元素*/ 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 页,再见,再见,