复习Pascal——数组.pptx

JSOI2009JSOI2009年大丰冬令营（年大丰冬令营（年大丰冬令营（年大丰冬令营（B B层）层）层）层）程序设计程序设计程序设计程序设计P Pascalascalascalascal数数 组组(一一一一)1、一维数组Type 类型标识符号类型标识符号=array 下标类型下标类型 of 元素类型；元素类型；Var 数组名：类型标识符；数组名：类型标识符；orVar 数组名：数组名：array下标类型下标类型 of 元素类型；元素类型；定义：定义：例例例例6-16-1定义如下数组：定义如下数组：定义如下数组：定义如下数组：（1）表示）表示20种商品的价格；种商品的价格；（2）表示）表示30件邮件件邮件 的安全邮递情况；的安全邮递情况；（3）统计）统计50个学生在一次考试（满分为个学生在一次考试（满分为100，最低分为，最低分为0分）中各分数分）中各分数 的分布情况；的分布情况；（4）统计一篇文章中各字母的出现频率（所有字母均小写）。）统计一篇文章中各字母的出现频率（所有字母均小写）。Var price:array1.20 of real;mail:array1.30 of boolean;score:array0.100 of integer;number:arraya.z of integer;共有共有共有共有2020个实型数，个实型数，个实型数，个实型数，price1-price20price1-price20共有共有共有共有5050个布尔型数，个布尔型数，个布尔型数，个布尔型数，mail1-mail30mail1-mail30共有共有共有共有101101个整型数，个整型数，个整型数，个整型数，score0-score100score0-score100共有共有共有共有2626个整型数，个整型数，个整型数，个整型数，numbera-numberznumbera-numberzJSOI2009JSOI2009年大丰冬令营（年大丰冬令营（年大丰冬令营（年大丰冬令营（B B层）层）层）层）程序设计程序设计程序设计程序设计P Pascalascalascalascal想一想：下列数组这定义对不对，如不对，为什么？Var a:array1.n of char;b:array10.1 of integer;c:arrayinteger of boolean;d:array1.0.3.0 of real;e:array1.50000 of real;说明：说明：a数组中数组中n为变量；为变量；b数组中，下标的上下界应从小到大；数组中，下标的上下界应从小到大；c、e数组元素个数太多，空间分配不够；数组元素个数太多，空间分配不够；d数组下标为实型，不是有序类型。数组下标为实型，不是有序类型。JSOI2009JSOI2009年大丰冬令营（年大丰冬令营（年大丰冬令营（年大丰冬令营（B B层）层）层）层）程序设计程序设计程序设计程序设计P Pascalascalascalascal一一维维数数组组的的基基本本操操作作：1 1、数组的赋值、输入、输出、数组的赋值、输入、输出、数组的赋值、输入、输出、数组的赋值、输入、输出例例例例6-1 6-1 按顺序读入按顺序读入按顺序读入按顺序读入1010个数，再以逆序的方式输出。个数，再以逆序的方式输出。个数，再以逆序的方式输出。个数，再以逆序的方式输出。分析：可以定义一个分析：可以定义一个分析：可以定义一个分析：可以定义一个1010个元素的数组，用循环读入、输出。个元素的数组，用循环读入、输出。个元素的数组，用循环读入、输出。个元素的数组，用循环读入、输出。Program ex10-1(input,output);Program ex10-1(input,output);var var x:array1.10 of integer;x:array1.10 of integer;I:integer;I:integer;begin begin for I:=1 to 10 do for I:=1 to 10 do read(xI);read(xI);writeln(fanxushuchu:);writeln(fanxushuchu:);for I:=10 downto 1 do for I:=10 downto 1 do write(xI:3);write(xI:3);end.end.本例将数组下标作为循环变量，本例将数组下标作为循环变量，本例将数组下标作为循环变量，本例将数组下标作为循环变量，便于数组的输入、输出便于数组的输入、输出便于数组的输入、输出便于数组的输入、输出运行结果：运行结果：运行结果：运行结果：10 31 0 -27 78 90 9 1 4 8 2110 31 0 -27 78 90 9 1 4 8 2121 8 4 1 9 90 78 27 0 31 10 21 8 4 1 9 90 78 27 0 31 10 fanxushuchu:fanxushuchu:数组元素的赋值可以用赋值语句。数组元素的赋值可以用赋值语句。数组元素的赋值可以用赋值语句。数组元素的赋值可以用赋值语句。JSOI2009JSOI2009年大丰冬令营（年大丰冬令营（年大丰冬令营（年大丰冬令营（B B层）层）层）层）程序设计程序设计程序设计程序设计P Pascalascalascalascal2 2、数组元素的移动、数组元素的移动、数组元素的移动、数组元素的移动例例例例6-2 6-2 将将将将a a数组中第一个元素移动到最后数组末尾，其数组中第一个元素移动到最后数组末尾，其数组中第一个元素移动到最后数组末尾，其数组中第一个元素移动到最后数组末尾，其余数据依次往前平移一个位置。余数据依次往前平移一个位置。余数据依次往前平移一个位置。余数据依次往前平移一个位置。P85P85分析：（分析：（分析：（分析：（1 1）先将第一个元素取出放在临时单元中；）先将第一个元素取出放在临时单元中；）先将第一个元素取出放在临时单元中；）先将第一个元素取出放在临时单元中；（2 2）将）将）将）将a2a2a1a1、a3a3a2ana2anan-1an-1（3 3）再将临时单元）再将临时单元）再将临时单元）再将临时单元temptempananProgram ex6-2(input,output);const n=10;var a:array1.n of integer;I:integer;temp:integer;begin for I:=1 to n do read(aI);temp:=a1;for I:=1 to n-1 do aI:=aI+1;an:=temp;for I:=1 to n do write(aI:3);End.思考：如果将最后一个元素移到第一个位置，其余数据依次向后平移思考：如果将最后一个元素移到第一个位置，其余数据依次向后平移思考：如果将最后一个元素移到第一个位置，其余数据依次向后平移思考：如果将最后一个元素移到第一个位置，其余数据依次向后平移一个位置，如何修改？如果将数组实现逆序交换，又该如何修改程序一个位置，如何修改？如果将数组实现逆序交换，又该如何修改程序一个位置，如何修改？如果将数组实现逆序交换，又该如何修改程序一个位置，如何修改？如果将数组实现逆序交换，又该如何修改程序？1 2 3 4 n-1 n2 3 4 n-1 n 1JSOI2009JSOI2009年大丰冬令营（年大丰冬令营（年大丰冬令营（年大丰冬令营（B B层）层）层）层）程序设计程序设计程序设计程序设计P Pascalascalascalascal例例例例6-3 6-3 对于数组对于数组对于数组对于数组a a，输入一个测试数据，输入一个测试数据，输入一个测试数据，输入一个测试数据x x，如果，如果，如果，如果x x存于存于存于存于数组数组数组数组a a，则把，则把，则把，则把x x元素删除；否则将元素删除；否则将元素删除；否则将元素删除；否则将x x插在相应的位置，插在相应的位置，插在相应的位置，插在相应的位置，要求数组仍然有序（假设数组递增要求数组仍然有序（假设数组递增要求数组仍然有序（假设数组递增要求数组仍然有序（假设数组递增)分析：本题是一个查找问题。查找的最常用方法是顺序查找和二分查找。分析：本题是一个查找问题。查找的最常用方法是顺序查找和二分查找。分析：本题是一个查找问题。查找的最常用方法是顺序查找和二分查找。分析：本题是一个查找问题。查找的最常用方法是顺序查找和二分查找。我们先采用顺序查找，二分查找以后再讲。我们先采用顺序查找，二分查找以后再讲。我们先采用顺序查找，二分查找以后再讲。我们先采用顺序查找，二分查找以后再讲。顺序查找的过程是：从头开始，根据给定的值，依次与数组中的数进行顺序查找的过程是：从头开始，根据给定的值，依次与数组中的数进行顺序查找的过程是：从头开始，根据给定的值，依次与数组中的数进行顺序查找的过程是：从头开始，根据给定的值，依次与数组中的数进行比较，相同即为找到，若查遍整个数组仍然没有，则表示该元素不存在。比较，相同即为找到，若查遍整个数组仍然没有，则表示该元素不存在。比较，相同即为找到，若查遍整个数组仍然没有，则表示该元素不存在。比较，相同即为找到，若查遍整个数组仍然没有，则表示该元素不存在。由题意知：本题查询的条件是数组的元素小于由题意知：本题查询的条件是数组的元素小于由题意知：本题查询的条件是数组的元素小于由题意知：本题查询的条件是数组的元素小于x x，若发现有数据与，若发现有数据与，若发现有数据与，若发现有数据与x x相等，相等，相等，相等，则将删除该数，否则，若数组中的数大于则将删除该数，否则，若数组中的数大于则将删除该数，否则，若数组中的数大于则将删除该数，否则，若数组中的数大于x x，则此处就是插入，则此处就是插入，则此处就是插入，则此处就是插入x x的位置。的位置。的位置。的位置。注意：如果是删除，则将注意：如果是删除，则将注意：如果是删除，则将注意：如果是删除，则将x x后的数向前平移一个；如果是插入，则先将后的数向前平移一个；如果是插入，则先将后的数向前平移一个；如果是插入，则先将后的数向前平移一个；如果是插入，则先将x x插入点的元素依次向后平移。插入点的元素依次向后平移。插入点的元素依次向后平移。插入点的元素依次向后平移。3 3、数组元素的查找、插入、删除、数组元素的查找、插入、删除、数组元素的查找、插入、删除、数组元素的查找、插入、删除JSOI2009JSOI2009年大丰冬令营（年大丰冬令营（年大丰冬令营（年大丰冬令营（B B层）层）层）层）程序设计程序设计程序设计程序设计P PascalascalascalascalProgram ex6-3(input,output);const n=100;var a:array1.n+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 aIai,a1ai,则将则将则将则将a1a1与与与与aIaI交换。交换。交换。交换。等一轮比较下来，最小数就存放在等一轮比较下来，最小数就存放在等一轮比较下来，最小数就存放在等一轮比较下来，最小数就存放在a1a1中。中。中。中。（2 2）依（）依（）依（）依（1 1）类推，）类推，）类推，）类推，a2a2中放第二小，中放第二小，中放第二小，中放第二小，a3a3中放第三小数，中放第三小数，中放第三小数，中放第三小数，一直到一直到一直到一直到an-1an-1，这样序就形成了。，这样序就形成了。，这样序就形成了。，这样序就形成了。JSOI2009JSOI2009年大丰冬令营（年大丰冬令营（年大丰冬令营（年大丰冬令营（B B层）层）层）层）程序设计程序设计程序设计程序设计P Pascalascalascalascal程程 序序 如如 下下：Program maopao_sort(input,output);const n=10;var a:array1.10 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+1ai+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.随机产生随机产生随机产生随机产生1010个个个个0-1000-100的整数并输出的整数并输出的整数并输出的整数并输出冒冒冒冒泡泡泡泡排排排排序序序序做标记，若没做标记，若没做标记，若没做标记，若没有交换值则有交换值则有交换值则有交换值则t t为为为为true,true,出现交换出现交换出现交换出现交换后后后后t t改为改为改为改为falsefalse将排好的序输出。将排好的序输出。将排好的序输出。将排好的序输出。JSOI2009JSOI2009年大丰冬令营（年大丰冬令营（年大丰冬令营（年大丰冬令营（B B层）层）层）层）程序设计程序设计程序设计程序设计P Pascalascalascalascal应应 用用：例例例例6-5 6-5 将一个十进制整数转化为二进制数。将一个十进制整数转化为二进制数。将一个十进制整数转化为二进制数。将一个十进制整数转化为二进制数。分析：在标准类型中，分析：在标准类型中，长整型范围是长整型范围是-2147483648-21474483647,而二进而二进制数制数 10000000000的的十进制数为十进制数为1024，因，因此如果直接来转换会此如果直接来转换会出现数据溢出。为了出现数据溢出。为了能更好存储二进制的能更好存储二进制的各个位数，可以采用各个位数，可以采用数组。假定输入的数数组。假定输入的数据是长整型，则存储据是长整型，则存储二进制数的数组长度二进制数的数组长度为为32。十十二的方法是除以二的方法是除以2反向取余法。反向取余法。Program ex6-5(input,output);var bin:array0.50 of 0.1;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 2取整的方法。取整的方法。取整的方法。取整的方法。JSOI2009JSOI2009年大丰冬令营（年大丰冬令营（年大丰冬令营（年大丰冬令营（B B层）层）层）层）程序设计程序设计程序设计程序设计P Pascalascalascalascal例例6-66-6 圆盘找数，如图所示：找出圆盘找数，如图所示：找出4 4个相邻的数，使其个相邻的数，使其相加之各最大和最小的是哪相加之各最大和最小的是哪4 4个数？并给出它们的起个数？并给出它们的起始位置。始位置。1252011841661015219118137143179本题实际上就是先求出相邻的四个数的和，然本题实际上就是先求出相邻的四个数的和，然本题实际上就是先求出相邻的四个数的和，然本题实际上就是先求出相邻的四个数的和，然后找出最大数和最小数。如何求相邻的四个数后找出最大数和最小数。如何求相邻的四个数后找出最大数和最小数。如何求相邻的四个数后找出最大数和最小数。如何求相邻的四个数的和呢？的和呢？的和呢？的和呢？设和存放在设和存放在S S中，我们不妨先确定一个序，即确定第一个中，我们不妨先确定一个序，即确定第一个数的位置和最后一个数的位置。假设圆盘上的数的位置和最后一个数的位置。假设圆盘上的2020个数中个数中5 5为第一个数，为第一个数，1212为最后一个数。则可将这为最后一个数。则可将这2020个数放在个数放在a a数数组中。数组的下标取组中。数组的下标取0-190-19。0Imax 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.JSOI2009JSOI2009年大丰冬令营（年大丰冬令营（年大丰冬令营（年大丰冬令营（B B层）层）层）层）程序设计程序设计程序设计程序设计P Pascalascalascalascal例例6-76-7投票问题：竞选时，要求选民在投票问题：竞选时，要求选民在A A、B B、C C、D D四个候四个候选人中选择（人数不限），如果选择了选人中选择（人数不限），如果选择了ABCDABCD以外的人员则以外的人员则为废票。统计时输入为废票。统计时输入“#”结束，请按候选人得票数从大结束，请按候选人得票数从大到小顺序输出候选人及其得票情况。到小顺序输出候选人及其得票情况。分析：设两个数组分析：设两个数组分析：设两个数组分析：设两个数组namename数组存放候选人姓名，数组存放候选人姓名，数组存放候选人姓名，数组存放候选人姓名，name1name1放得放得放得放得票最多的人名，票最多的人名，票最多的人名，票最多的人名，name4name4存放得票最少的人名。存放得票最少的人名。存放得票最少的人名。存放得票最少的人名。scorescore存放各存放各存放各存放各人的得票数。人的得票数。人的得票数。人的得票数。假设开始时，假设开始时，假设开始时，假设开始时，namename数组中各元素的值依次为数组中各元素的值依次为数组中各元素的值依次为数组中各元素的值依次为A A、B B、C C、D D，则问题就转化为重组则问题就转化为重组则问题就转化为重组则问题就转化为重组namename数组，而数组，而数组，而数组，而scorescore数组只起存储作用。数组只起存储作用。数组只起存储作用。数组只起存储作用。JSOI2009JSOI2009年大丰冬令营（年大丰冬令营（年大丰冬令营（年大丰冬令营（B B层）层）层）层）程序设计程序设计程序设计程序设计P PascalascalascalascalProgram ex6-7(input,output);var score:arrayA.D of integer;name:array1.4 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 to 3 do for j:=I+1 to 4 do if scorenameIscorenamej then根据票数确定名次根据票数确定名次 begin ch:=nameI;nameI:=namej;namej:=ch;end;writeln(rusult:);for I:=1 to 4 do writeln(nameI,:,scorenameI);end.间接寻址思想间接寻址思想间接寻址思想间接寻址思想JSOI2009JSOI2009年大丰冬令营（年大丰冬令营（年大丰冬令营（年大丰冬令营（B B层）层）层）层）程序设计程序设计程序设计程序设计P Pascalascalascalascal小结：小结：1、数组的定义2、数组的基本操作：（1）赋值、输入、输出（2）移动 （3）查找、插入、删除（4）排序3、数组的应用：十进制二进制 圆盘找数 投票问题