数组ppt课件.ppt

第六章 数组,编程实现：输入n（n5）个数，并且以相反的顺序输出这些数。,program p1(input,output);var x1,x2,x3,x4,x5:integer;begin readln(x1,x2,x3,x4,x5);writeln(x5:2,x4:2,x3:2,x2:2,x1:2);end.,编程实现：输入n（n100）个数，并且以相反的顺序输出这些数。,结论：当n值较小时，我们通过定义5个不同变量很轻松的解决这个问题。但是当n值超过一定个数时，定义变量及数据输入、输出成为一个繁琐的过程。,思考：能不能用一个变量来表示一批数据？,答案：数组,数组是一种常用的数据类型，由固定数目的相同类型的元素按一定的顺序排列而成。,program p1_2(input,output);const n=5;var x:array1.n of integer;i:integer;begin for i:=1 to n do read(xi);for i:=n downto 1 do write(xi:2);end.,整个程序非常简洁，而且直接通过修改常量n的定义就可以解决不同的n值需要。,结论：在编程时用到一批类型相同的数据，为了处理上的方便，通常以数组的形式来定义这一批数据。,一维数组的定义：一维数组是指只有一个下标的数组。,var a:array 1.10 of integer;,type arr=array1.10 of integer;定义类型var a:arr;定义变量,或：,其中：a是这一批数据的名称，称为数组名；array、of是定义数组的保留字；中括号中的数字是数据编号的下限和上限，同时也说明了数据的个数（上限-下限+1）；最后一个是数据的基类型，如integer，char，real，boolean。下标类型：（1）子界型（2）有序的（3）有限的（4）可以是常量，变量，表达式。,例：定义如下数组：（1）表示20种商品的价格var price:array1.20 of real;（2）表示30件邮件的安全邮递情况var mail:array1.30 of boolean;（3）统计50个学生在一次考试（满分100，最低分60）中各分数的分布情况var score:array60.100 of integer;（4）统计一篇文章中各字母的出现频率（所有字母均小写）var number:arraya.z of intger;,例：判断以下数组的定义是否合理。var a:array1.n of integer;不合理。因为，数组的元素个数必须是确定的。var b:array10.1 of integer;不合理。数组下标的下界应小于上界。var c:arrayinteger of boolean;不合理。因为数组元素个数太多，空间分配不够。var d:array1.0.3.0 of real;不合理。下标为real实型，不属于有序类型。var e:array1.50000 of real;不合理。数组元素个数太多，空间分配不够。,一维数组定义举例：,由于数组中所有元素属于同一类型，所以每个元素在存储器中占用的空间大小相同。,一维数组的存储：顺序存储,假设数组的第一个元素存放的位置为LOC(k1)，每个元素占用的空间大小为S，则ki的存放位置为：LOC(ki)=LOC(k1)+S*(i-1),一维数组的基本操作：,整体运算：a:=b;输入数组名代表的并不是一个变量，而是一批变量，因而，不能直接整个数组读入，而是要逐个数组元素读入，通常用循环结构来完成这一功能。下面是几个常用输入数组元素的例子：for i:=1 to 10 do read(ai);从键盘读入数组元素的值；最常用的方法,(1)i=1时，read(a1);(2)i=2时，read(a2);(3)i=3时，read(a3);(4)i=4时，read(a4);(5)i=5时，read(a5);(6)i=6时，read(a6);(7)i=7时，read(a7);(8)i=8时，read(a8);(9)i=9时，read(a9);(10)i=10时，read(a10);,for i:=1 to 10 do ai:=i;数组元素a1到a10的值分别为1到10；数据赋初值for i:=1 to 10 do ai:=0;数组元素清0；最常用的数据初始化的方法for i:=1 to 10 do ai:=random(100);随机产生10个100以内的数，赋给各数组元素 输出和数组元素的输入相同，数组元素的输出也不能由一个write语句直接完成。同样要逐个数组元素输出。通常也用循环结构来完成这一功能：for i:=1 to 10 do write(ai,);数组元素之间用空格分隔writeln;,program p2(input,output);var a,b:array1.5 of integer;i:integer;begin writeln(-);for i:=1 to 5 do read(ai);writeln;for i:=1 to 5 do write(ai:5);writeln;b:=a;for i:=1 to 5 do write(bi:5);writeln;end.,一维数组赋值、输入、输出举例：,编程实现：从键盘输入字符，直到“”结束输入。,program p3_1(input,output);var a:array1.100 of char;ch:char;i:integer;begin writeln(-);read(ch);i:=0;while ch#do begin i:=i+1;ai:=ch;read(ch);end;end.,program p3_2(input,output);var a:array1.100 of char;ch:char;i:integer;begin writeln(-);i:=1;repeat read(ch):ai:=ch;i:=i+1;until ch=#;end.,分析：一串字符可以用数组表示。但是并不知道这一串字符的具体长度，所以不能使用for循环输入。因为知道循环结束的条件，所以可以用while或repeat循环实现。,例题：从键盘输入10个数，将这10个数逆序输出，并求这10个数的和，输出这个和。program p4;var a:array 1.10 of integer;i,s:integer;begin for i:=1 to 10 do read(ai);for i:=10 downto 1 do write(ai,);writeln;s:=0;for i:=1 to 10 do s:=s+ai;writeln(s=,s);end.,习题1：读入10个数，输出偶数项，并打印他们的和，输出奇数项，并打印它们的平均数。习题2：读入n个数，打印其中的最大数和最小数及其位置号。,program p6_4_1(input,output);var a:array1.10 of real;i:integer;ou,ji:real;ave:real;begin writeln(*p6_4_1.pas*);ou:=0;ji:=0;writeln(please input ten numbers:);for i:=1 to 10 do begin read(ai);if i mod 2=0 then ou:=ou+ai else ji:=ji+ai;end;ave:=ji/5;writeln;write(oushuxiang is:);for i:=1 to 10 do if i mod 2=0 then write(ai:8:2);writeln;writeln(sum is:,ou:12:2);write(jishuxiang is:);for i:=1 to 10 do if i mod 20 then write(ai:8:2);writeln;writeln(average is:,ave:12:2);writeln;end.,program p6_4_2(input,output);var n,i:integer;a:array1.100 of integer;max,min,bmax,bmin:integer;begin writeln(*p6_4_2.pas*);write(please input a number:);readln(n);writeln;writeln(please input,n,numbers:);for i:=1 to n do read(ai);max:=a1;min:=a1;bmax:=1;bmin:=1;for i:=1 to n do begin if aimax then begin max:=ai;bmax:=i;end;if aimin then begin min:=ai;bmin:=i;end;end;writeln;writeln(max is:,max,xiabiao is:,bmax);writeln(min is:,min,xiabiao is:,bmin);end.,一维数组的应用数据的移动,左移:将数组中的第一个元素移动到数组末尾，其余数据依次往前平移一个位置。,temp,右移:将数组中的最后一个元素移到第一个位置，其余数据依次往后平移一个位置。(1)temp:=an;(2)n-1-n,n-2-n-1,.2-3,1-2(3)temp-a1,左移程序实现：temp:=a1;for i:=2 to n do ai-1:=ai;an:=temp;,右移程序实现：temp:=an;for i:=n-1 downto 1 do an+1:=an;a1:=temp;,思考：若要将数组的所有元素实现逆序交换（即把a1和an交换，a2和an-1交换）如何？,program p5;const n=10;a:array 1.n of integer=(1,2,3,4,5,6,7,8,9,10);var i,j,temp:integer;begin writeln(-);for i:=1 to n do write(ai:4);writeln;i:=1;j:=n;while ij do begin temp:=ai;ai:=aj;aj:=temp;i:=i+1;j:=j-1;end;for i:=1 to n do write(ai:4);writeln;writeln;end.,(1)temp:=a1;(2)2-1,3-2,4-3,.n-n-1(3)temp-an,数据的查找：查找数组中值为x的元素顺序查找，while aix do i:=i+1;数据的删除：删除数组中第k个元素akfor i:=k to n-1 do ai:=ai+1;数据的插入(1)在数组的第k个位置插入 for i:=n downto k do ai+1:=ai;ak：shu;(2)如果是插入到一串数据的某一个数据之后，先要定位 while aix do i:=i+1;找到后，插入位置应为i+1,一维数组的应用：数据的查找、删除、插入,例65 P77 对于数组a，假设它的所有元素是按照递增顺序存放的。现在输入一个x，如果x存在于数组a中，则要把x元素删除；否则将x插在相应的位置，保持a数组仍然递增。,一维数组的应用数据的排序,例：从键盘输入n个数，将它们按照从大到小的顺序输出。,for i:=1 to n-1 do for j:=i+1 to n do if ajai then begin temp:=aj;aj:=ai;ai:=temp;end;,temp,(1)i=1 j=2 a2和a1比较，如果a2大于a1则交换。j=3 a3和a1比较，如果a3大于a1则交换。j=4 a4和a1比较，如果a4大于a1则交换。j=5 a5和a1比较，如果a5大于a1则交换。j=6 a6和a1比较，如果a6大于a1则交换。j=7 a7和a1比较，如果a7大于a1则交换。j=8 a8和a1比较，如果a8大于a1则交换。此次循环结果使a1中为这八个数中的最大值。(2)i=2 j=3 a3和a2比较，如果a3大于a2则交换。j=4 a4和a2比较，如果a4大于a2则交换。j=5 a5和a2比较，如果a5大于a2则交换。j=6 a6和a2比较，如果a6大于a2则交换。j=7 a7和a2比较，如果a7大于a2则交换。j=8 a8和a2比较，如果a8大于a2则交换。此次循环结果使a2中为这八个数中的次大值。（以此类推）,由于在排序过程中总是大数往前，小数往后，相当于气泡上升，所以叫冒泡排序。,练习：从键盘输入10个数，将这10个数从大到小的顺序输出。,program p6;var i,j,temp:integer;a:array1.10 of integer;begin for i:=1 to 10 do read(ai);for i:=1 to 9 do for j:=i+1 to 10 do if ajai then begin temp:=ai;ai:=aj;aj:=temp;end;for i:=1 to 10 do write(ai:5);writeln;writeln;end.,例如：编程实现。将一个十进制整数转换为二进制数。,知识回顾：将十进制整数45转换成二进制数,45,2 22,余数,高位,低位,1,0,1,1,0,1,2 11,2 5,2 2,2 1,0,于是得到：（45）10=（101101）2,一维数组的应用进制转化,program p7;var b:array1.50 of 0.1;x:longint;i,l:integer;begin writeln(-);for i:=1 to 50 do bi:=0;write(input Decimal data x:);readln(x);i:=0;while x0 do begin i:=i+1;bi:=x mod 2;x:=x div 2;end;l:=i;write(Binary:);for i:=l downto 1 do write(bi);writeln;end.,知识回顾：将十进制小数0.625转换成二进制小数,0.625,2,1.250,2,0.500,1.000,2,整数部分,1,0,1,高位,低位,于是得到：（0.625）10=（0.101）2,想一想：将十进制小数转化为二进制小数用的是乘2取整的方法，如果要求将十进制小数转化为二进制数，程序该如何改动？十进制实数改成二进制呢？,program p8;var b:array1.50 of 0.1;x:real;i,l:integer;begin writeln(-);for i:=1 to 50 do bi:=0;write(input Decimal data x:);readln(x);i:=0;while x0 do begin i:=i+1;bi:=trunc(x*2);x:=x*2-trunc(x*2);end;l:=i;write(Binary:0.);for i:=1 to l do write(bi);writeln;end.,一维数组的应用判断回文数,什么是回文数？即从左向右读与从右向左读是同一个数。如19391。,分析：如果能将这个数存放到数组中。,i:=1;j:=l;while(ai=aj)and(ij then 是回文数,关键是如何将x这个数放到数组中去。,a数组存放x数的每一位。i:=0;repeat i:=i+1;ai:=x mod 10;x:=x div 10;until x=0;,习题：试编一个程序，打印出1000以内以二进制和十进制正读和反读都一样的整数清单。,program p6_4_8(input,output);var a:array1.10 of integer;x,i,k,l,j,y:integer;begin writeln(*p6_4_8_2.pas*);for x:=1 to 1000 do begin i:=0;y:=x;repeat i:=i+1;ai:=y mod 10;y:=y div 10;until y=0;l:=i;i:=1;j:=l;while(ai=aj)and(ij then begin y:=x;l:=0;while y0 do begin l:=l+1;al:=y mod 2;y:=y div 2;end;i:=1;j:=l;while(ai=aj)and(ij then begin write(x:4,:);for k:=1 to l do write(ak);writeln;end;end;end;writeln;end.,则只需判断ai和aj是否相等，ai+1和aj+1，以此类推。,分析：素数是除了1和它本身以外没有其它约数的数。用筛法求素数的方法是：用质数筛去合数：从第一个素数2开始，把它的倍数去掉；这样2以后的第一个非0数就一定也是素数，把它的倍数也删了重复这个删数过程，直到在所找到的素数后再也找不到一个非0数。把所有非0数输出。,一维数组的应用筛法求素数,例：用筛法求100以内的素数（质数）。,program p9;var a:array 1.100 of integer;i,j,k:integer;begin for i:=1 to 100 do ai:=i;a1:=0;i:=2;while i0 then write(ai,);end.,一维数组的应用围圈问题：,圆盘找数。如图所示，找出4个相邻的数，使其相加之和最大和最小的是哪4个数？并给出它们的起始位置。,问题简化：撇去围圈问题不看。求一组数（49，38，65，97，76，13，27，49）中的最大数和最小数。可以将这组数存放到数组中。,程序实现：program p10(input,output);const a:array1.8of integer=(49,38,65,97,76,13,27,49);var i:integer;max,min:integer;begin max:=-maxint;min:=maxint;for i:=1 to 8 do begin if aimax then max:=ai;if aimin then min:=ai;end;writeln(max:8,min:8);end.,假设圆盘上20个数中，5为第一个数，12为最后一个数。假设4个数的和存于变量s中。思考：如果将这些数存放在数组a1.20 可以用如下公式吗？s=ai+ai+1+ai+2+ai+3，那么，当s大于等于18的时候，会出现数组下标越界。提示：取模操作。实现：将这些数存放在数组a0.19中，那么，s=ai+a(i+1)mod 20+a(i+2)mod 20+a(i+3)mod 20请同学们自己编程完成程序。,所以本题的关键是求和s的通项公式。,围圈问题应用约瑟夫问题。,约瑟夫问题：n个人围成一圈，从第一个人开始报数，数到k的人出圈。再由下一个人开始报数，数到k的人出圈,以此输出出圈人的编号。n的值预先设定，k的值由键盘输入。比如：n8，k6，依次出圈的为：6、4、3、5、8、7、2、1。,分析：第一步，建立数据结构。n个人存放在一个长度为n的数组中。例如：,const n=8;var a:array1.n of boolean;begin for i:=1 to n do ai:=true;.end.,则数到k的人，ai:=false;并且输出此时的i,如何数到k？变量j从1循环到k，满足 i:=(i+1)mod n;if ai then j:=j+1;,猴子选大王：有M个猴子围成一圈，每个有一个编号，编号从1到M。打算从中选出一个大王。经过协商，决定选大王的规则如下：从第一个开始，每隔N个，数到的猴子出圈，最后剩下来的就是大王。要求：从键盘输入M，N，编程计算哪一个编号的猴子成为大王。,二维数组：二维数组是数组元素有两个下标的数组,一维数组在编程中多用于描述线性的关系：如一组数；一组成绩；一组解答等。数组元素只有一个下标，表明该元素在数组中的位置。二维数组在编程中多数用于描述二维的关系：如地图、棋盘、城市街道、迷宫等等。而二维数组元素有两个下标：第一个下标表示该元素在第几行，第二个下标表示在第几列。,二维数组的定义格式如下：var a：array1.10,1.5 of integer；定义了一个二维数组a，共有10行5列,其中：（1）a是数组名，由程序员自定；（2）array和of是定义数组的保留字；（这两点和一维数组定义的格式一样）（3）中括号中的两个范围表示二维数组共有多少行、多少列（第一个范围表示行数，第二个范围表示列数）；（4）最后一个表示数组元素的类型，规定和一维数组一样。,1、数组元素：数组名行号，列号。,二维数组的输入输出：,如第三行第四个元素：a3,4。,如：for i:=1 to 5 do s:=s+a4,i;,如：for i:=1 to 10 do s:=s+ai,4;,对某一行进行处理。如累加第4行的数据。则固定行号为4。,2、二维数组的输入输出要用双重循环来控制：for i:=1 to 10 do控制行数begin for j:=1 to 5 do read(ai,j)第一行读入5个元素 readln;读入一个换行符end;最常用的方法：从键盘读入数据初始化二维数组for i:=1 to 10 do for j:=1 to 5 do ai,j:=0;最常用的方法：将二维数组清0for i:=1 to 10 dobegin for j:=1 to 5 do write(ai,j:4);writeln;end;最常用的输出方法：按矩阵形式输出二维数组的值,对某一列进行处理。如累加第4列的数据。则固定列号为4。,program p11;const n=3;type matrix=array1.n,1.nof integer;var a:matrix;i,j:1.n;begin for i:=1 to n do begin for j:=1 to n do read(ai,j);readln;end;for i:=1 to n do begin for j:=1 to n do write(aj,i:5);writeln;end;end.,且运行程序时的输入为:213 331 121则程序的输出应是:231 132 311,二维数组的输入输出实例：设有一程序：,二维数组的存储：顺序存储,由于计算机内存是一维的，二维数组的元素应排成线性序列后存入存储器。PASCAL语言中，数组按行优先顺序存储。,【例】二维数组Amn的按行优先存储的线性序列为：a11,a12,a1n,a21,a22,a2n,，am1,am2,，amn,数组元素的地址计算公式（1）按行优先顺序存储的二维数组A1.m,1.n地址计算公式 LOC(aij)=LOC(a11)+(i-1)n+j-1d其中：LOC(a11)是开始结点的存放地址（即基地址）d为每个元素所占的存储单元数,（2）下界不为1的二维数组的地址计算公式二维数组Ac1.d1,c2.d2的地址计算公式：,LOC(aij)=LOC(ac1c2)+(i-c1)(d2-c2+1)+j-c2d,下界为0的二维数组A0.d1,0.d2的地址计算公式：,LOC(aij)=LOC(a00)+i(d2+1)+jd,1.设数组a10.100,20.100以行优先的方式顺序存储，每个元素占4个字节，且已知a10,20的地址为1000，则a50,90的地址是 14240。2.已知数组a中，每个元素ai,j在存储时要占3个字节，设i从1变化到8，j从1变化到10，分配内存时是从地址sa开始连续按行存储分配的。试问：a5,8的起始地址为 sa+141。,3.以下程序段正确的输出是-1。var a:array1.3,1.4 of integer;b:array1.4,1.3 of integer;x,y:integer;begin for x:=1 to 3 do for y:=1 to 4 do ax,y:=x-y;for x:=4 downto 1 do for y:=1 to 3 do bx,y:=ay,x;writeln(b3,2);end.,例：编程。竞赛小组共有20位同学，这学期每位同学共参与了三项比赛，请统计每位同学的平均分。,二维数组的应用：,program p12;const n=5;var a:array1.n,1.4 of real;i,j:integer;begin for i:=1 to n do begin for j:=1 to 3 do read(ai,j);readln;end;for i:=1 to n do ai,4:=0;for i:=1 to n do for j:=1 to 3 do ai,4:=ai,4+ai,j;writeln(average:);for i:=1 to 5 do writeln(i,:,ai,4/3:8:2);end.,二维数组的应用：杨辉三角,分析：将杨辉三角形存储于如右图的二维数组中。问题转化为对二维数组的求值问题。,寻找规律可得：第i行的第一个元素必为1，第i行的第i个元素必为1，第i行的其余元素为上一行的两个元素之和。即：ai,j:=ai-1,j-1+ai-1,j;请同学们自行编写程序，打印杨辉三角形。,program p13;const n=10;var a:array1.100,1.100 of integer;i,j:integer;begin a1,1:=1;for i:=2 to n do begin ai,1:=1;ai,i:=1;for j:=2 to i-1 do ai,j:=ai-1,j-1+ai-1,j;end;writeln(-);for i:=1 to n do begin for j:=1 to i do write(ai,j:4);writeln;end;end.,