|
Pascal教程
|
数组
1.数组的定义
数组是程序中最常用的结构数据类型，用来描述由固定数目的同一类型的元素组成的数据结构。数组的每个
元素和下标相关联，根据下标指示数组的元素。数组的存储方式为按行存储，在编译阶段，计算机根据数组的
类型说明，确定其存储空间的大小。数组可以是任何顺序类型。
数组的定义形式：
array [<下标类型1>，……<下标类型n>] of <元素类型>
其中n称为数组的维数，每维的下标类型必须是一个顺序类型，通常为子界类型或枚举类型，其作用是指定
数组下标的编制方式和下标取值范围。
例如：
type
color=(red,yellow,blue);
sample1=array [1..10]of integer；｛有10个元素的一维数组}
sample2=arrayp[1..5,1..5]of real；{有25个元素的二维数组，依次按[1，1]……，[1，5]，[2，1]……，[2，5]，……[5，1]，……[5，5]}
2.数组的操作
当数组的元素类型为简单类型时，其下标变量和简单类型变量一样使用。例如：
a[50]:=50； a[20]:=a[5];
一个数组，下标的起始值和终止值是在类型定义中给定的，不能在程序执行中再通过其他途径来改变，所以
数组元素的个数在程序运行期间是固定不变的。数组变量作为整体仅允许同类型数组之间的赋值运算。
例如：var x,y:array[1..10]of integer;
x::=y
例：读入５个学生的学号和成绩，计算他们的平均分，若比平均分高１０分的等第为A，若比平均分高小于１０分
的等地为B，若低于平均分，则等第为C，输出他们的成绩和等第。
program sample7d1(input,output);
const n=5;
type
no=array[1..n] of integer;
s=array[1..n]of real;
var
i:integer;
k:real;
num:no;
score:s;
begin
k:=0;
for i:=1 to n do
begin
readln(num[i],score[i]);
k:=k+score[i];
end;
k:=k/n;
for i:=1 to n do
begin
write(num[i],score[i]);
if (score[i]-k)>=10 then writeln('A')
else if((score[i]-k)<10)and((score[i]-k)>0)
then writeln('B')
else
writeln('C');
end;
end.
字符串
为了使程序能够处理文字信息，Turbo Pascal特别引入了字符串类型，其值表示一个具有可变长度的字符
序列。字符串类型定义形式为：
strign[n]或者string
其中正整数n(1<=n<=255)表示构成字符串的字符最多个数，即通常所说的字符串最大长度。而字符串的实际
长度决定程序运行时的实际字符个数，可以由函数length返回。若字符串说明中没有指定长度，缺省值为255。
字符串类型定义字符串连接操作‘＋’，是将两个字符串连接成新字符串。连接操作允许字符串类型和字符
串类型混合运用。
字符串常量可以通过常量说明语句
const 字符串常量名：string[n]='字符串'；
规定其常量的串长n,并赋初值。例如：const head:string[7]='zhoufei';
Turbo Pascal还提供了不少预定义函数和过程：
(1)字符串函数
函数名
自变量及类型
意义
结果类型
concat
s1[,s2……,sN]：string
连接字符串序列
string
copy
s：string，index,count：integer
返回串s的一个子串
string
length
s：string
返回串s的动态长度
integer
pos
substr,s：string
返回子串substr在串s中的起始位置
byte
过程名
自变量及类型
意义
delete
var s,source：string；index,count：integer
从串S中删除一个子串
insert
var s：string；index：integer；
在串S中插入一个指定子串
str
var x[：width[：Decimals]]；s：string
把一数值转换成相应的字符串表示
val
var s：string；code：integer
把一字符串转换成相应的数值
例：字符串函数调用示例
program samplefun;
const
tur='turbo';
pas='pascal';
var
st:string[60];
p:byte;
begin
st:=concat(tur,pas,'is better than','stand',pas,'.');
writeln(st);
writeln(length(st));
st:=copy(st,29,15);
writeln(st);
p:=pos(pas,st);
writeln(p);
p:=pos(tur,st);
writeln(p);
end.
例：字符串过程调用示例
program guocheng;
const
typedstring:string='turbo pascal is better than standard pascal.';
total:real=388.4;
var
totalstring:string[60];
integervalue:integer;
realvalue:real;
status:integer;
begin
delete(typedstring,13,40);
writeln(typedstring);
insert('using',typedstring,1);
writeln(typedstring);
str(total:8:2,totalstring);
writeln(totalstring);
str(total,totalstring);
writeln(totalstring);
val('-33',integervalue,status);
writeln(integervalue,'':2,status);
val('-33.99',realvalue,status);
writeln(realvalue:6:2,'':2,status);
end.
|
表的数组实现
|
将一个表存储到计算机中，可以采用许多不同的方法，其中既简单又自然的是顺序存储方法，即将表中的元素逐个存放于数组的一些连续的存储单元中。在这种表示方式下，容易实现对表的遍历。要在表的尾部插入一个新元素，也很容易。但是要在表的中间位置插入一个新元素，就必须先将其后面的所有元素都后移一个单元，才能腾出新元素所需的位置。执行删除运算的情形类似。如果被删除的元素不是表中最后一个元素，则必须将它后面的所有元素前移一个位置，以填补由于删除所造成的空缺。
用数组实现表时，我们将表类型TList定义为一个记录。它有两个域，第一个域是一个数组，用于存储表中的元素，数组的大小根据表可能达到的最大长度而定；第二个域是一个整型变量last，用于指出表中结束元素在数组中的位置。表中第i个元素(1≤i≤last)存储在数组的第i个单元中。
在这种情况下，位置变量的类型TPosition是整型，位置变量p表示数组的第p个单元即表中第p个元素的位置。End(L)的函数值为last+1。这些类型可用Pascal语言说明如下:
Const
MaxLength=100; {数组的最大长度，即表的最大单元数目}
Type
TPosition = Integer;
TElement= ... {TElement要根据具体情况而定}
TList = Record
Elements: Array [1..MaxLength] of TElement;
last: TPosition;
End;
定义了实现表的数组结构后，我们就可以讨论在这种结构上如何具体地实现表的基本运算了。
函数 Insert(x,p,L)
功能
在表L的位置p处插入元素x，并将原来占据位置p的元素及其后面的元素都向后推移一个位置。例如，设L为a1,a2,…,an，那么在执行Insert(x,p,L)后，表L变为a1,a2,…ap-1,x,ap,…,an 。若p为End(L)，那么表L变为a1,a2,…,an,x 。若表L中没有位置p，则该运算无定义。
实现
Procedure Insert(x:TElement;p:TPosition;L:TList);
Var q: TPosition;
begin
if Length(L)>=MaxLength
then
Error('List is Full')
else if (p>End(L))or(p<First(L))
then
Error('Position was not defined.')
else
begin
for q←L.last downto p do
L[q]←L[q+1];
{将L的第q+1个元素复制到L的位置q上}
L.last←L.last+1;
L.Elements[p]← x;
end;
end;
说明：
算法Insert将位于p,p+1,…,last 中的元素分别移到位置p+1,p+2,…,last+1 ，然后将新元素插入位置p。注意算法中元素后移的顺序，必须从表中最后一个位置开始后移，直至将位置p处的元素后移为止。如果新元素的插入位置不合法，则调用子程序Error输出错误信息，然后终止程序。
复杂性：
现在我们来分析算法的时间复杂性。这里问题的规模是表的长度Length(L)=L.last，设它的值为n。显然该算法的主要时间花费在for循环的元素后移上，该语句的执行次数为n-p+1。由此可看出，所需移动元素位置的次数不仅依赖于表的长度，而且还与插人的位置p有关。当p=n+1时由于循环变量的终值大于初值，元素后移语句将不执行，无须移动元素；若p=1，则元素后移语句将循环执行n次，需移动表中所有元素。也就是说该算法在最好情况下需要Ο(1)时间，在最坏情况下需要Ο(n)时间。由于插入可能在表中任何位置上进行，因此，有必要分析算法的平均性能。
设在长度为n的表中进行插入运算所需的元素移动次数的平均值为EIN(n)。由于在表中第i个位置上插入元素需要的移动次数为n-i+1，故
其中，pi表示在表中第i个位置上插入元素的概率。考虑最简单的情形即假设在表中任何合法位置i (1≤i≤n+l)上插入元素的机会是均等的，则：
从而，在等概率插入的情况下，
也就是说，用数组实现表时，在表中做插入运算，平均要移动表中一半的元素，因而算法所需的平均时间仍为Ο(n)。
函数 Delete(p,L)
功能
从表L中删除位置p处的元素。例如，当L为a1,a2,…,an时，执行Delete(p,L)后，L变为a1,a2,…,ap-1,ap+1,…,an 。当L中没有位置p或p=End(L)时，该运算无定义。
实现
Procedure Delete(p:TPosition;Var L:TList);
begin
if (p>End(L)) or (p<First(L))
then Error('Position does not exist.')
else
begin
L.last ← L.last-1;
for q ← p to L.last do
L.Elements[q] ← L.Elements[q+1];
end;
说明
算法Delete通过将位于p+1,p+2,…,last中的元素分别移到位置p,p+1，…, last-1来删除原来位置p处的元素。
复杂性
该算法的时间分析与插入算法类似，元素的移动次数也是由表长n和位置p决定的。若p=n，则由于循环变量的初值大于终值，前移语句将不执行，无须移动元素；若p=1，则前移语句将循环执行n-1次，需要移动表中除删除元素外的所有元素。因此，算法在最好情况下需要O(1)时间，而在最坏情况下需要O(n)时间。
删除运算的平均性能分析与插入运算类似。设在长度为n的表中删除一个元素所需的平均移动次数为EDE(N)。由于删除表中第i个位置上的元素需要的移动次数为n-i，故
其中，pi表示删除表中第i个位置上元素的概率。在等概率的假设下，
这时
也就是说用数组实现表时，在表中做删除运算，平均要移动表中约一半的元素，因而删除运算所需的平均时间为O(n)。
函数 Locate(x,L)
功能
这是一个函数，函数值为元素x在L中的位置。若x在L中重复出现多次，则函数值为x第一次出现的位置。当x不在L中时，函数值为End(L)。
实现
Function Locate(x:TElement;var L:TLIST):TPosition;
var
q:TPosition;
begin
for q:=1 to L.last do
if L.elements[q]=x then return (q);
return(L.last+1);
end;
说明
算法Locate在数组中从前向后通过比较来查找给定元素的位置。如果在表中没有找到这样的元素，则返回last+1。
复杂性
该算法中的基本运算是两个元素的比较。若在表中位置i找到给定元素，则需要进行i次比较，否则需要进行n次比较，n为表的长度。与算法Insert和Delete的时间分析类似，算法Locate在最好情况下需要O(l)时间，在最坏情况和平均情况下都需要O(n)时间。
用数组来实现表时，我们利用了数组单元在物理位置上的邻接关系来表示表中元素之间的逻辑关系。由于这个原因，用数组来实现表有如下的优缺点。 优点是：
无须为表示表中元素之间的逻辑关系增加额外的存储空间；
可以方便地随机访问表中任一位置的元素。
缺点是：
插入和删除运算不方便，除表尾的位置外，在表的其他位置上进行插入或删除操作都必须移动大量元素，其效率较低；
由于数组要求占用连续的存储空间，存储分配只能预先进行静态分配。因此，当表长变化较大时，难以确定数组的合适的大小。确定大了将造成浪费。