复习Pascal——数组1.ppt

数 组(一),1、一维数组,Type 类型标识符号=array 下标类型 of 元素类型； Var 数组名：类型标识符；,or,Var 数组名：array下标类型 of 元素类型；,定义：,例6-1定义如下数组：,（1）表示20种商品的价格； （2）表示30件邮件 的安全邮递情况； （3）统计50个学生在一次考试（满分为100，最低分为0分）中各分数 的分布情况； （4）统计一篇文章中各字母的出现频率（所有字母均小写）。,Var price:array120 of real; mail:array130 of boolean; score:array0100 of integer; number:arrayaz of integer;,共有20个实型数，price1-price20,共有50个布尔型数，mail1-mail30,共有101个整型数，score0-score100,共有26个整型数，numbera-numberz,想一想：下列数组这定义对不对，如不对，为什么？,Var a:array1n of char; b:array101 of integer; c:arrayinteger of boolean; d:array1.03.0 of real; e:array150000 of real;,说明：a数组中n为变量；,b数组中，下标的上下界应从小到大；,c、e数组元素个数太多，空间分配不够；,d数组下标为实型，不是有序类型。,一维数组的基本操作：,1、数组的赋值、输入、输出,例6-1 按顺序读入10个数，再以逆序的方式输出。,分析：可以定义一个10个元素的数组，用循环读入、输出。,Program ex10-1(input,output); var x: array110 of integer; I: integer; begin for I:=1 to 10 do read(xI); writeln(fanxushuchu:); for I:=10 downto 1 do write(xI:3); end.,本例将数组下标作为循环变量，便于数组的输入、输出,运行结果：,10 31 0 -27 78 90 9 1 4 8 21,21 8 4 1 9 90 78 27 0 31 10,fanxushuchu:,数组元素的赋值可以用赋值语句。,2、数组元素的移动,例6-2 将a数组中第一个元素移动到最后数组末尾，其余数据依次往前平移一个位置。P85,分析：（1）先将第一个元素取出放在临时单元中；,（2）将a2a1、a3a2anan-1,（3）再将临时单元tempan,思考：如果将最后一个元素移到第一个位置，其余数据依次向后平移一个位置，如何修改？如果将数组实现逆序交换，又该如何修改程序？,例6-3 对于数组a，输入一个测试数据x，如果x存于数组a，则把x元素删除；否则将x插在相应的位置，要求数组仍然有序（假设数组递增),分析：本题是一个查找问题。查找的最常用方法是顺序查找和二分查找。我们先采用顺序查找，二分查找以后再讲。,顺序查找的过程是：从头开始，根据给定的值，依次与数组中的数进行比较，相同即为找到，若查遍整个数组仍然没有，则表示该元素不存在。,由题意知：本题查询的条件是数组的元素小于x，若发现有数据与x相等，则将删除该数，否则，若数组中的数大于x，则此处就是插入x的位置。,注意：如果是删除，则将x后的数向前平移一个；如果是插入，则先将x插入点的元素依次向后平移。,3、数组元素的查找、插入、删除,Program ex6-3(input,output); const n=100; var a:array1n+1 of integer; 如果x插入，数组x将增加一个数据 x:integer; I,j:integer; begin for I:=1 to n do read(aI); read(x); an+1:=x; 将an+1设为x，可以作为后面比较的结束标志 I:=1 ; while aIx do I:=I+1; 循环结束时，I即为需要插入或删除的位置 if I=n+1 then write(Not found and no place to insert.) x大于数组a中所有元素,无需处理 else if aI=x then begin 找到x，删除 writeln(found and deleted. Result:); for j:=I to n-1 do aj:=aj+1; 数据前移 for j:=1 to n-1 do write(aj:3); end else begin 没找到x，插入 writeln(not found and insert. Rusult:); for j:=n+1 downto I+1 do aj:=aj-1; 数据后移 aI:=x; for j:=1 to n+1 do write(aj:3); end; writeln; end.,4、数组元素的排序,排序的常用方法有：冒泡法、选择法、插入法、希尔法、快速分类法等。这些算法会逐步地接触到。,例6-4从键盘中输入若干个数，将它们按照从小到大的顺序输出。,分析： 选择法：设若干个数存放在a1、a2、an中。 （1）先从n个数选出一个最小数放在a1中： 即让a1分别与a2到an比较，如果发现a1ai,则将a1与aI交换。 等一轮比较下来，最小数就存放在a1中。 （2）依（1）类推，a2中放第二小，a3中放第三小数，一直到an-1，这样序就形成了。,程序如下：,Program maopao_sort(input,output); const n=10; var a:array110 of integer; I,j,temp:integer; begin for I:=1 to n do read(aI); for I:=1 to n-1 do for j:=n-1 downto i do if aj+1aj then begin temp:=aj+1; aj+1:=aj; aj:=temp end; for I:=1 to n do write(aI:4); end.,选择法简单易懂，但运行速度慢。,冒泡法是一种比较有名的排序法。,冒泡法的算法思想是：将相邻的两个数比较，小的冒到前面，大的沉到后面。,冒泡法程序：,Program mppx(input,output); const n=10; var a:array1n of integer; I,temp:integer; t:boolean; begin randomize; for I:=1 to n do begin ai:=trunc(random(100);write(ai:4); end; repeat t:=true; for i:=1 to n-1 do if aiai+1 then begin temp:=ai; ai:=ai+1;ai+1:=temp; t:=false; end until t ; writeln; for I:=1 to n do write(aI:4); End.,随机产生10个0-100的整数并输出,冒泡排序,做标记，若没有交换值则t为true,出现交换后t改为false,将排好的序输出。,应用：,例6-5 将一个十进制整数转化为二进制数。,分析：在标准类型中，长整型范围是-2147483648-21474483647,而二进制数 10000000000的十进制数为1024，因此如果直接来转换会出现数据溢出。为了能更好存储二进制的各个位数，可以采用数组。假定输入的数据是长整型，则存储二进制数的数组长度为32。,十二的方法是除以2反向取余法。,Program ex6-5(input,output); var bin:array050 of 01; x:longint; k,I:integer; Begin read(x); for I:=0 to 50 do binI:=0; 将数组清0 k:=0; while x0 do begin bink:=x mod 2; x:=x div 2; k:=k+1; end; write(二进制为:) for I:=k-1 downto 0 do write(binI:1); end.,思考：如果要求将十进制的实数转化为二进制数，如何处理？提示：小数采用乘2取整的方法。,例6-6 圆盘找数，如图所示：找出4个相邻的数，使其相加之各最大和最小的是哪4个数？并给出它们的起始位置。,本题实际上就是先求出相邻的四个数的和，然后找出最大数和最小数。如何求相邻的四个数的和呢？,设和存放在S中，我们不妨先确定一个序，即确定第一个数的位置和最后一个数的位置。假设圆盘上的20个数中5为第一个数，12为最后一个数。则可将这20个数放在a数组中。数组的下标取0-19。,0I17时， s=aI+aI+1+aI+2+aI+3 I=17时，s=aI+aI+1+aI+2+a0 I=18时，s=aI+aI+1+a0+a1 I=19时，s=aI+a0+a1+a2+a3,由取余的知识可知：I=17时，a0=a(I+3) mod 20; I=18时，a1=a(i+3) mod 20),即0I 19时，都有s=aI+a(I+1) mod 20+a(I+2) mod 20) +a(I+3)mod 20)成立。,Program ex6-6(input,output); var a:array019 of integer; s,max,min:integer; smax,smin:integer; smax,smin记录最大和以及最小和的起始位置 I:integer; begin for I:=0 to 19 do read(aI); max:=-maxint; min:=maxint; 设置最大值和最小值的初始值 for I:=0 to 19 do begin s:=aI+a(I+1) mod 20+a(I+2) mod 20+a(I+3) mod 20; if smax then begin max:=s;smax:=I;end; if smin then begin min:=s; smin:=I; end; end; write(max:,asmax:2);for I:=1 to 3 do write(+,asmax+I mod 20:2); write(=,max); writeln(start from,smax+1); write(min:,asmin:2);for I:=1 to 3 do write(+,asmin+I mod 20:2); write(=,min);writeln(start from ,smin+1); end.,例6-7投票问题：竞选时，要求选民在A、B、C、D四个候选人中选择（人数不限），如果选择了ABCD以外的人员则为废票。统计时输入“#”结束，请按候选人得票数从大到小顺序输出候选人及其得票情况。,分析：设两个数组name数组存放候选人姓名，name1放得票最多的人名，name4存放得票最少的人名。score存放各人的得票数。,假设开始时，name数组中各元素的值依次为A、B、C、D，则问题就转化为重组name数组，而score数组只起存储作用。,Program ex6-7(input,output); var score:arrayAD of integer; name:array14 of char; I,j:integer; select,ch:char; begin read(select); for ch:=A to D do scorech:=0; 将score数组清0 for I:=1 to 4 do nameI:=chr(ord(A)+I-1); name数组初始化为A、B、C、D while select# do begin if select in A,B,C,D then 有效票 scoreselect:=scoreselect+1; 对应候选人得票数加1 read(select); end; for I:=1