第三章 数组一、数组的结构数组是我们很熟悉的一种数据结构，它可以看作线性表的推广。数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。图 5.1 是一个 m 行 n列的二维数组。数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识，因此，在数组上不能做插入、删除数据元素的操作。通常在各种高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。在数组中通常做下面两种操作：(1) 取值操作：给定一组下标，读其对应的数据元素。(2) 赋值操作：给定一组下标，存储或修改与其相对应的数据元素。我们着重研究一维和二维数组，因为它们的应用是广泛的，尤其是一维数组。例题 3_1、编制用筛选法求 N 以内素数的程序。 分析：由希腊数学家埃拉托色尼提出的“筛选法”，步骤如下： 1）将所有候选放入筛中； 2）找了出筛中最小数（必为素数）P； 3）将 P 的所有倍数从筛中筛去； 4）重复 2）至 3）直到筛空。 编程时，用数组 R 表示筛子，R(i)为 1 时，表示 i 在筛中，R(i)为 0 时，表示 i 已从筛中筛去。程序设计步骤：1．建立一个包括 2，3，…，N 的数据“集合”R；a11 a12 … a1na21 a22 … a2n… … … …am1 am2 … amn图 5.1 m 行 n 列的二维数组A= 2．顺序取 R 中的数（从素数 2 开始），同时将其及能整除它的数从 R 中划去。“筛法求素数”的过程如下图示：素数R[1] 数据集合 R 2{ 2， 3， 4， 5， 6， 7， 8， 9，10，11，12，……} 3{ 3， 5， 7， 9， 11， ……} 5{ 5， 7， 11， ……} …… ……… 这样便可得到所求的素数：2，3，5，……。[源程序] 例程见 exm_3_1.pasprogram Sushu;var i,j,k,n,w,t:integer; R,P:array [1..500] of integer;Begin write('N=');readln(n); if (n<2) or (n>500) then begin writeln('Input N error!');halt end; for i:=2 to n do R[i-1]:=i; writeln('Result:');t:=0;k:=n-1; while k>0 do begin P:=R; {数组 R 保存在 P 中} write(R[1]:5); {输出素数} t:=t+1;w:=R[1];j:=0; for i:=1 to k do if P[i] mod w<>0 then {划去 w 及 W 的倍数} begin j:=j+1; R[j]:=P[i];end; {重新构造集合 R} k:=j; {新建后 R 的元素个数} end; writeln;writeln('Total=',t);end.
