§5  数组
【引例】输入20个数，将它们按从大到小的次序排序后输出。
讨论：如果按我们前面学的知识，我们应设20个变量来存储这20个数，如果要排序的数不是20个，而是100个，那我们就应设100个变量？没这么笨吧，我们有更好的办法解决。
§5.1  一维数组
数组是由固定数量的相同类型的元素按一定顺序排列而成。
只有一个下标类型的数组称为一维数组。
1．数组类型定义和说明
类型定义的一般形式为：
  TYPE <类型标识符> = ARRAY [下标类型] OF <基类型>；
数组说明：
      VAR  <数组名> ：<数组类型标识符>；
数组名是由用户定义的标识符，下标类型可以是子界类型或枚举类型，下标规定了数组元素的个数和排列次序。基类型表示数组中每个元素的类型，它可以是任何数据类型，但同一数组中的元素类型必须相同。
如：
    type
        A = array [1..20]  of  integer;
        B = array [0..50]  of  char;
    Var
        x , y : A;
        a : B;
其中x、y被说明为A类型数据，即均为拥有20个元素的数组，下标从1到20，元素类型为整型；a被说明为B类型数据，即拥有51个元素的数组，下标从0到50，元素类型为字符型。
★  数组也可以直接在说明部分说明数组的类型，如：
var  x , y : array [1..20]  of  integer;
          a : array [0..50]  of  char;
请输入一个长度0和5之间的字符串
0
1
2
3
4
5
6
7
……
50
数组中的每个元素都是变量，每个元素在数组中有固定的位置，可以用数组名及方括号括起的下标来表示。
如a数组中的第5个元素可表示为：a [4]
数组元素的运算和变量相同，如：
readln (a[4]);  x[3]:=x[3]+y[1];
2．数组元素的赋值和引用
  如为一个数组A[1..10] 赋值，可用下列语句实现：
        for i:=1 to 10 do read (A[i]);
  如果两个数组类型相同，如数组x和y，可用赋值语句： x:=y；
  把y的10个元素值赋给x的相应元素，它等效于： for i:=1 to 20 do x[i]:=y[i];
  但要给数组元素赋同一个值，不能这样赋值： x:=0; 
  而应该用如下语句：
for i:=1 to 20 do x[i]:=0;
【例1】求100以内的所有素数。
筛法：
主要用于求一个区间上的质数表
• 去掉1
• 从2开始，把凡是2的倍数的数去掉（2保留）
• 从下一个未被去掉的数k开始，把凡是k的倍数的数去掉（k保留）
• 依此类推，直至
筛选过程：
  (a) 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 …… 98 99 100
  (b) 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 …… 98 99 100
  (c) 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 …… 98 99 100
  ……  ……
算法分析：
（1）设布尔类型数组A[2..100]
以下标2～100代表整数2～100；数组元素的布尔值代表其是否为素数；
设A[i]=true 则i为素数，A[i]=false 则i为合数；
A中元素初始均赋为true；
（2）从数组中新一个素数P；
（3）从P+1开始，把凡是P的倍数的数筛去（赋为false）；
（4）重复步骤2、3，直到P>
（5）打印数组中未被筛去的元素（元素值为true）；
√
√
√
√
√
√
√
√
√…
√
2
3
4
5
6
7
8
9
……
100
√
√
X
√
X
√
X
√
……
X
2
3
4
5
6
7
8
9
……
100
参考程序：
program prime;
const n=100;
var
a : array [2..n] of boolean;
i , p : integer;
begin
for  i:=2  to  n  do  a[i]:=true;  {a数组初始化，全部置true}
for  i:=2  to  n div 2  do
  if  a[i]  then begin  { a[i] 相当于 a[i]=true }
                p:=i*2;
                while p<=n do begin  {将a中i的倍数去掉}
                    a[p]:=false;
    p:=p+i;
                end; {while}
              end; {then}
for i:=2 to n do  {打印素数}
if  a[i]=true  then  write(i:4);
end.
【例2】输入n个数，将它们按从小到大排序后输出。
          请先思考自己的算法，再看以下内容！
[方法一] 选择排序
基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
排序过程： 在数组元素[1..n]中出最小数，将数组第1位上的数与最小数交换；
          在剩下的数中[2..n]中出最小数，与第2位上的数交换；
          依次类推，直到全部的数排完。
    技巧： 寻最小数——借助哨兵变量x，存放的不是最小数的值，而是最小数的位置（下
标），扫描一趟后，最小数即S[x]。
          交换数组元素S[i]和最小数——即交换S[i]和S[x]
例如：      初始状态  [49 38 65 97 76 13 27 49]

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。