第七章数组和字符串.ppt

《第七章数组和字符串.ppt》由会员分享，可在线阅读，更多相关《第七章数组和字符串.ppt（74页珍藏版）》请在三一文库上搜索。

1、第七章 数组和字符串,河师大附中信息技术教研组,第一节 数组 一、数组的定义 数组是程序中经常使用的结构数据类型，用来描述由固定数目的同一类型的元素组成的数据结构。数组的每个元素与下标相关联，根据下标指示数组的元素。数组的存贮方式为按行存贮，在编译阶段，计算机根据数组的类型说明，确定其存贮空间的大小。 数组的定义形式： array ， of 其中n称为数组的维数，每维的下标类型必须是一个序数类型，通常为子界类型或枚举类型，其作用是指定数组下标的编制方式和下标取值范围。数组的元素类型是除文件类型和指针类型(下面将介绍)以外的一切类型。例如：,type color=(red，yellow，blue

2、)； sample1=array 110 of integer； 类型sample1的元素是整数，有10个元素，维数为1，依次按110编下标 sample2=array 15，15 of real；类型sample2的元素是实数，有25个元素，维数为2，依次按1，1，1，5，2，1，2，5，5，1，5，5编下标 sample3=array color of color；类型sample3的元素属color类型，有3个元素，一维，依次按red，yellow，blue编下标 var a：sample1； b，c：sample2； d，e：sample3；,注意，类型和变量是二个不同的概念，不能混淆

3、。程序中使用的是数组变量而不是数组类型，即a，b，c，d，e。但数组的类型定义和变量定义可以合并在一起。例如： var a：array 110 of integer； b：array 15，15 of integer； d：array red，yellow，blue of (red，yellow，blue)；,二、数组的操作 当数组的元素类型为简单类型时，其下标变量与简单类型变量一样使用。例如： a5：=50； a20：=a5； 由于下标变量的下标可以作为表达式，使得数组有广泛的应用。例如，设有如下变量说明 var i，sum：integer； 下面的语句可求数组变量a的元素和,sum：=0；

4、 for i：=1 to 10 do sum：=ai+sum； PASCAL允许用同一数组类型的变量相互赋值。如d：=e也是合理的，它把数组变量e 的所有元素依次赋给数组变量d，即等价于下面说明 begin dred：=ered； dyellow：=eyellow； dblue：=eblue； 一个数组常量可以通过常量说明语句来定义。,若是一维数组常量，其定义形式如下： const 数组常量名：array 下标变量 of 元素类型=(元素值1，元素值2，元素值n)； 等号右方用括号括起来的部分，是指定数组各元素的值，它们彼此间用逗号隔开。例如： const digits：array 09 of

5、 char=(0，1，2，3，4，5，6， 7，8，9)； 若是二维数组常量，则括号中的每一个常量元素可以看作是行的所有列元素，列元素间用逗号分隔。这些常量元素用括号括起来，彼此间也用逗号隔开。例如 move:array 14，14 of integer=(1，2，3，4)，(5，6，7，8)，(9，10，11，12)， (13，14，15，16)；,例7-1 输入N个学生的成绩（都为0至100的整数），打印输出最高分，最低分，以及平均分。 Program example7_1; var a : array1100 of byte; i,n,max,min,ave : integer; beg

6、in repeat write(N = ); readln(n); until n 100; ave := 0;,max := 0; min := 32767; for i := 1 to n do begin read(ai); if ai max then max := ai; if ai min then min := ai; ave := ave+ai; end; writeln(Max : ,max); writeln(Min : ,min); writeln(Ave : ,ave/n:0:2); end.,例7-2 求裴波拉契数列a1,a2,a3,a4,an。裴波拉契数列可以按如下

7、定义： a1 = 1 a2 = 1 an = an-1 + an-2 (n 2) Program example7_2; var a : array150 of longint; n,i : integer; begin write(N = ); readln(n); a1 := 1; write(a1:10); a2 := 1; write(a2:10); for i := 3 to n do begin ai := ai-2+ai-1; write(aI:10); end; end.,例7-3 有一个养鸭专业户，赶了一大群鸭子出去卖。他每经过一个村庄，卖出所赶鸭子的一半再多一只，这样他经过

8、七个村庄后，还剩下两只鸭子，编程打印输出他每经过一个村庄后卖出多少只鸭子？剩下多少只鸭子？ Program example7_3; var a : array07 of word; i, j : byte; begin a7 := 2; for i := 7 downto 1 do ai-1 := 2*(ai+1); for i := 1 to 7 do writeln(No.,i, : ,ai-1-ai:5,ai:5); end.,例7-4 输入一串字符，以！作为结束，不分大小写，统计其中每种英文字符出现的次数。 Program example7_4; var ch : arrayA Z o

9、f byte; c : char; i,j : byte; begin for c := A to Z do chc := 0; read(c); while c ! do begin c := upcase(c); if (c = A) and (c = Z) then chc := chc+1; read(c); end; writeln; for c := A to Z do writeln(c, : ,chc); end.,例7-5 有N个灯放在一排，从1到N依次顺序编号。有N个人也从1到N依次编号。1号将灯全部关闭，2将凡是2的倍数的灯打开；3号将凡是3的倍数的灯作相反处理(该灯如为

10、打开的，则将它关闭；如关闭的，则将它打开)。以后的人都和3号一样，将凡是自己编号倍数的灯作相反处理。试计算第N个操作后，哪几盏灯是点亮的。(1表示灯打开，0表示灯关闭),program example7_5; var k,n,I,j : integer; a : array1100 of 01; N盏灯的状态 begin write(N = ); readln(n); for i := 1 to n do ai := 0; 初始化 for i:= 2 to n do begin 从第1号队员开始，依次操作 j := i; 从第i号队员操作后各灯的状态 while j = n do begin

11、aj := 1-aj; j := j+i; end; end; for i := 1 to n do write(ai); writeln; end.,例7-6 选择排序：随机地产生100个自然数，将它们从小到大地排序后，将它们打印输出。 program example7_6; const n = 100; var a : array1n of word; i,j,temp : word; begin randomize; for i := 1 to n do ai := random(65535); for i := 1 to n do write(ai:8); writeln;,for i

12、 := 1 to n-1 do for j := i+1 to n do if ai aj then begin temp := ai; ai := aj; aj := temp; end; readln; for i := 1 to n do write(ai:8); writeln; end.,例7-6 冒泡法排序：随机地产生100个自然数，将它们从小到大地排序后，将它们打印输出。,program example7_6; const n = 100; var a : array1n of word; i,j,temp : word; f:boolean; begin randomize;

13、for i := 1 to n do ai := random(65535); for i := 1 to n do write(ai:8); writeln;,repeat f:=true; for i:= 1 to n-1 do if ai ai+1 then begin temp := ai; ai := ai+1; ai+1 := temp; f:=false; end; until f; for i := 1 to n do write(ai:8); writeln; end.,希尔法排序,44 55 12 42 94 18 6 67 第一次jump=4后：44 18 6 42 94

14、 55 12 67 第二次jump=2后：6 18 12 42 44 55 94 67 第三次jump=1后：6 12 18 42 44 55 67 94,希尔法排序,program example7_6; const n = 100; var a : array1n of word; i,jump,temp : word; f:boolean; begin randomize; for i := 1 to n do ai := random(65535); for i := 1 to n do write(ai:8); writeln;,jump:=n; While jump=1 do be

15、gin jump:=jump div 2; repeat f:=true; for i:= 1 to n-jump do if ai aj+jump then begin temp := ai; ai := ai+jump; ai+jump := temp; f:=false; end; until f; end; for i := 1 to n do write(ai:8); writeln; end.,有对小兔子，出生一个月后变成大兔子，两个月后生出第一对小兔子，自己变成一对老兔子，上个月生的小兔子变成大兔子。此时，共有3对兔子（一对老兔子，一对大兔子，一对小兔子）。4个月后大兔子变成老兔

16、子，小兔子变成大兔子，两对老兔子生出两对小兔子，此时共有5对兔子（老、小两对、大一对）请编程序，计算11个月后共有多少对兔子。,program tuzi7_7; const n=11; var a:array111of integer; i:integer; begin a1:=1; for i:=2 to n do ai:=2*ai-1; writeln(an); end.,例7-8 繁殖问题：有一家生化所，一月份引入一对新生的小白鼠，这种小白鼠生长两个月后，在第三、第四 、第五个月各繁殖一对小白鼠，在第六个月停止繁殖，在第七个月则死亡。新生的小白鼠也如此繁殖，问N个月后（N 50）,活的小

17、白鼠有多少对？,program example7_8; var a : array150 of longint; n,i,j : shortint; sum : longint; Begin repeat write(Input n : ); readln(n); until n in 350; for i := 2 to n do ai := 0; a1 := 1; a3 := 1; a4 := 1; for i := 5 to n do ai := ai-4+ai-3+ai-2; sum := 0; for i := n-5 to n do if i 0 then sum := sum+a

18、i; writeln(sum); End.,例7-9 输入N名同学5门课的考试成绩，输出各人的各课成绩及总分。 program example7_9; const n = 3; var a : array1n,16 of byte; i,j : byte; begin writeln(Input score :); for i := 1 to n do begin ai,6 := 0;,write(No.,i, : ); for j := 1 to 5 do begin read(ai,j); ai,6 := ai,6+ai,j; end; end; for i := 1 to n do be

19、gin for j := 1 to 6 do write(ai,j:5); writeln; end; end.,例7-10 输入正整数N（N 12）,打印杨辉三角形的前N行。杨辉三角形如下： N = 6 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 其特点是二个腰上的数都为1，其它位置上的数是它的上一行相邻二个数之和。用二维数组很容易记下三角矩阵，然后再打印输出。,program example7_10; var a : array112,112 of byte; i,j,n : byte; begin repeat write(N = ); rea

20、dln(n); until n 13; for i := 1 to n do begin ai,1 := 1; ai,i := 1; end; for i := 3 to n do for j := 2 to i-1 do ai,j := ai-1,j+ai-1,j-1; for i := 1 to n do begin write(ai,1:30-2*i); for j := 2 to i do write(ai,j:4); writeln; end; end.,例7-11 输入正整数N（N 10）,输出如下的对应字符图形： N = 2 A A A A B A A A A N = 4 A A

21、 A A A A A A B B B B B A A B C C C B A A B C D C B A A B C C C B A A B B B B B A A A A A A A A,program example7_11; var a : array119,119 of char; i,j,n,t : byte; begin repeat write(N = ); readln(n); until n 11; t := 2*n-1; for i := 1 to n do for j := i to t+1-i do begin ai,j := chr(64+i); aj,i := ch

22、r(64+i); at+1-i,t+1-j := chr(64+i); at+1-j,t+1-i := chr(64+i); end; for i := 1 to t do begin for j := 1 to t do write(ai,j:2); writeln; end; end.,例7-12 有四个人玩游戏，每局一个人输，三个人赢，输的人需根据赢的人手中的筹码等量付给，每个人都输一局，这样玩了四局后，每个人手中正巧都有16根筹码。打印输出开始时每人手中各有多少根筹码，每玩一局后每人手中各有多少根筹码。,program example7_12; var a : array14,15 o

23、f byte; i,j,s : byte; begin for i := 1 to 4 do ai,5 := 16; for j := 4 downto 1 do begin s := 0; for i := 1 to 4 do if i j then begin ai,j := ai,j+1 div 2; s := s+ai,j; end; aj,j := aj,j+1 + s; end;,writeln(No.:10,1:10,2:10,3:10,4:10); for j := 1 to 5 do begin write(j-1:10); for i := 1 to 4 do write(

24、ai,j:10); writeln; end; end.,例7-13奇数阶魔阵 ： 魔阵是用自然数1、2、3、n2填n阶方阵的各个元素位置，使方阵的每行的元素之和、每列元素之和及主对角线元素之和均相等；奇数阶魔阵的一个算法是将自然数数列从方阵的中间一行最后一个位置排起，每次总是向右下角排（即Ai,j的下一个是Ai+1,j+1），但若遇以下四种情形，则应修正排数法。 （1）、列排完（即j=n+1时），则转排第一列 （2）、行排完（即i=n+1时），则转排第一行 （3）、对An,n的下一个总是An,n-1 （4）、若Ai,j已排进一个自然数，则排Ai1,j2,var a : array199,19

25、9of integer; i,j,k,n : integer; begin fillchar(a,sizeof(a),0); write(“n=“);readln(n); i:=n div 2+1;j:=n; ai,j:=1; for k:=2 to n*n do begin if (i=n)and(j=n) then j:=j-1 else begin i:=i mod n +1; j:=j mod n +1; end;,if ai,j0 then begin i:=i-1; j:=j-2; end; ai,j:=k; end; for i:=1 to n do begin for j:=1

26、 to n do write(ai,j:5); writeln; end; end.,7-14.找出一个二维数组的鞍点，即该位置上的元素在该行上最大、该列上最小，也可能没有鞍点。数组的值从键盘输入，如： 19 23 21 13 61 25 34 45 67 32 39 29 39 98 27 56 如果没有鞍点则显示NO!，有则显示每个鞍点的位置和值，一个占一行,program t7_14; var a:array0100,0100of integer; i,j,n,l,h,hh,k:integer; f:boolean; begin readln(n); f:=true; for i:=1

27、to n do for j:=1 to n do read(ai,j); for i:=1 to n do ai,0:=0; for i:=1 to n do a0,i:=32767; for i:=1 to n do begin l:=0;,for j:=1 to n do if ai,lak,l then hh:=k; if (h=hh)and(h0) then begin writeln(,i,h,),ah,l); f:=false; end; end; if f then writeln(no); end.,7-15.打印一个可变大小的方阵，N为每边字符的个数（3=N=20),要求：最

28、外层是T,第二层是J,从第三层开始打印1，2，3，。如：N=10 TTTTTTTTTT TJJJJJJJJJJT TJ1111111JT TJ1222221JT TJ1233321JT TJ1234321JT TJ1233321JT TJ1222221JT TJ1111111JT TJJJJJJJJJJT TTTTTTTTTT,var a:array1100,1100of char; n,k,i,j:integer; t:char; begin readln(n); for k:=1 to n div 2+1 do if k=1 then for i:=1 to n do for j:=1 t

29、o n do ai,j:=Telse if k=2 then for i:=2 to n-1 do for j:=2 to n-1 do ai,j:=J else for i:=k to n-k+1 do for j:=k to n-k+1 do ai,j:=chr(46+k);,for i:=1 to n do begin for j:=1 to n do write(ai,j:2); writeln; end; readln; end.,7-16、蛇形填数：,上三角 x+y=i+1；奇数行y:=j; 偶数行x:=j;,下三角 An+1-I,n+1-j:=n*n+1-aI,j,const m

30、=100; var a:array1m,1mof integer; i,j,n,c:integer; begin write(n=,);readln(n); c:=1; 上三角 for i:=1 to n do if odd(i) then for j:=1 to i do begin ai-j+1,j:=c; inc( c ); end else for j:=1 to i do begin aj, i-j+1:=c; inc( c); end;,行列与坐标关系填数,下三角 for i:=1 to n-1 do for j:=n-i downto 1 do an+1-i,n+1-j:=n*n

31、+1-ai,j; for i:=1 to n do begin for j:=1 to n do write(aI,j:4); writeln; end; end.,模拟填数,const m=100; var a:array1m,1mof integer; i,j,x,y,n,c:integer; begin write(n=); readln(n); c:=1; x:=1; y:=1; for i:=1 to n do if odd(i) then begin for j:=1 to i-1 do begin ax,y:=c; inc(c); dec(x); inc(y); end;,ax,

32、y:=c; inc(c); inc(y);end else begin for j:=1 to i-1 do begin ax,y:=c; inc(c); inc(x); dec(y); end; ax,y:=c; inc(c); inc(x); end;,if odd(n) then begin dec(y);inc(x) end else begin dec(x);inc(y);end; for i:=n-1 downto 1 do begin if odd(i) then begin for j:=1 to i-1 do begin ax,y:=c;inc(c);dec(x);inc(y

33、); end; ax,y:=c;inc(c); inc(x); end else begin for j:=1 to i-1 do begin ax,y:=c;inc(c); inc(x);dec(y); end;,ax,y:=c;inc(c); inc(y); end; end; for i:=1 to n do begin for j:=1 to n do write(ai,j:4); writeln; end; readln; end.,7-17、旋转填数：,const m=100; var a:array1m,1mof integer; i,j,k,n,c,x,y:integer; t

34、emp:integer; begin write(n=); readln(n); k:=(n+1)div 2; c:=1;,for i:=1 to k do begin x:=i;y:=i; for j:=i to n-i do begin ax,y:=c; inc(c); inc(y); end; for j:=i to n-i do begin ax,y:=c; inc(c); inc(x); end;,for j:=i to n-i do begin ax,y:=c; inc(c); dec(y); end; for j:=i to n-i do begin ax,y:=c; inc(c

35、); dec(x); end; end;,if odd(n) then ak,k:=n*n; for i:=1 to n do begin for j:=1 to n do write(ai,j:3); writeln; end; end.,7-17、模拟填数：,const d:array14,12 of -11= (0,1),(1,0),(0,-1),(-1,0); var a:array0101,0101of integer; x,y,i,j,n,m,c:integer; begin write(n=); readln(n); for i:=0 to n+1 do for j:=0 to

36、n+1 do if (i=0)or(j=0)or(i=n+1)or(j=n+1) then aI,j:=1 else aI,j:=0; c:=1; x:=1;y:=1; ax,y:=c; inc( c);,模拟填数,m:=n*n; j:=1; while c0 then begin x:=x-dj,1;y:=y-dj,2; Inc( j); if j=5 then j:=1;end else begin ax,y:=c; inc( c); end; end; for i:=1 to n do begin for j:=1 to n do write(aI,j:4); writeln; end;

37、 end.,布尔数组,布尔数组是指数组的元素为布尔类型，即它的取值为true或false. 用筛法求2到1000之间的所有素数。 （利用布尔数组实现） 程序： const n=1000; var a:array2nof boolean; I,k,m,count:integer;,begin for i:=2 to n do ai:=true; k:=2; m:=trunc(sqrt(n); repeat if ak then for i:=2 to n div k do ai*k:=false; k:=k+1; until k=m; count:=0; for i:=2 to n do if

38、ai then begin write(i:6); inc(count); if count mod 10=0 then writeln; end; writeln; writeln(count=, count); end.,第二节 字符串类型,PASCAL支持一种更方便的类型，字符串类型。 一、先来看看定义方法： type st=string 10； var name：st； 上面首先定义了一个字符串类型：st，长度是10个字符，然后再定义了一个字符串类型的变量name。,当然也可以这样定义： var name：string10；推荐大家都这样定义 长度必须是一个正整数，范围是 1 到 25

39、5 之间，也就是说字符串类型最多可以存放255个字符。如果长度不写的话就默认为 255 个。但可以没有字符，这种叫空串。如果string255，就可以简写为string，它是系统已经定义好的一个长度为255字符串的标准类型。 如：name:string; 说明： 字符串类型称为动态串，虽然最长长度是固定的，但是在这个范围内可以自由变化。也就是说你可以定义 255个字符长的字符串，但是你可以只输入5个字符。,数组的类型也可以是字符串，也就是说一个数组元素可以是一个字符串。比如： type st=string10； var a: array13 of st； b：integer； begin fo

40、r b：=1 to 3 do readln（ab）； 上面的定义含义；st是字符串类型，a是一个字符串类型的数组，它有3个元素，其中每一个元素最多可以存放10个字符，以回车作为一个元素输入结束标志。 如果你一行输入超过10个字符则后面的字符自动作废。,如果是下面的话呢： for b:=1 to 10 do read（ab） 假设你输入的是：ABCDE HJKLM NOP QRSTU。那么每个数组元素存的是什么呢？,这样的话它将前面的10个字符送给A1，包括空格。再把后面的10个字符送给A2，以此类推。 如果超过了30个字符则程序会出错，因为超过了STRING定义的范围。如果没有30个字符则后面

41、的元素为空。如果你只输入5个字符就按回车那么又怎么分配呢？,输入原则：只能少，不能多！,字符串类型定义字符串连接操作+(或Pascal库函数concat)，是将两个字符串连接生成新字符串。连接操作允许字符类型和字符串类型混合运算。 字符串常量可以通过常量说明语句 const 字串常量名： stringn = 字串； 规定其常量的串长n，并赋初值。例如 const heading：string7 = section；,Pascal还提供了不少预定义的过程和函数用于对字符串进行操作。下面介绍几种最常用的过程和函数。 一、length函数 格式： length(st) 这个函数返回串表达式st的长度

42、，即串字符的个数，其结果类型为整型。 例如： st的值为ABCD1234，则length(st)的值为8。,二、copy函数 格式： copy(st，pos，num) st为串表达式，pos和num为整型表达式。copy返回一个子串，它包含st中pos开始的num个字符。如果pos超出串长，则返回一个空串。如果得到的字符在串尾之外，即pos+num超过了串长，则返回串里的那部分字符。 例如： st的值为abcdefg，则 copy(st，4，2)，返回值为de； copy(st，4，5)，返回值为defg。,三、pos函数 格式： pos(substr，st) substr和st都是串表达式，

43、其结果类型为整型，pos函数搜索st中的第一个出现的substr字符串，返回该位置值。如果没有找到，返回值为0。 例如： st的值为abcdefg，则 pos(de，st)，返回值为4； pos(ed，st)，返回值为0。,四、delete过程 格式： delete(st，pos，num) st是串变量，pos和num是两个整型表达式。delete删除st中从pos开始的num个字符的子串。如pos大于st的长度，则不删除任何字符，若企图删除多于串长度的子串，即pos+num大于串长，则仅删除串内字符。 例如： st的值为abcdefg，则 delete(st，4，2)，结果为abcfg； d

44、elete(st，4，10)，结果为abc。,五、insert过程 格式： insert(substr，st，pos) substr是串表达，st是串变量，pos为整型表达式。insert和substr插入到串st的pos位置上。若pos大于st的长度，那么将substr联接到st上，若大于st的最大长度，那么截去超过部分。 例如： st的值为abcdefg，则 insert(123，st，3)的结果为ab123cdefg。,六、str过程 格式： str(value，st) value为整型或实型书写参量，st是串变量。书写参量是指带场宽的整型或实型数。str将value的数字值按value

45、给出的格式转成字符串，并把结果存到st中。 例如： i的值为2568，则str(i：6，st)，给st的值为 2568。,七、val过程 格式： val(st，var，code) val将串表达式st转换为与var同类型的值，并将这个值赋给var。st必须一个按照数值常量规则来表示的数值的串，其首尾不允许有空格。var为一个整型或实型变量，code为一个整型变量，如果检测时未出错，变量code置0；否则code置为出错的第一个字符的位置，且var的值无定义。 例如： st的值为234，i为整型变量，则val(st，i，code)，i的值为234，code的值为0。 st的值为23X56，则va

46、l(st，i，code)，i的值无定义，code的值为3，表示第三个字符出错。,例7-13 输入一串字符，其长度小于200。判断该串字符是否构成回文。 所谓回文是指从左到右和从右到左读一串字符的值是一样的。如abcba就是一个回文。 Program example7_13; var st : string; i,j : byte; begin write(Input a string : ); readln(st); j := length(st); i :=1; while (j i) and (sti = stj) do begin i := i+1; j := j-1; end; if

47、j=i then writeln(Yes) else writeln(No) end.,714编写一个函数，在字符串1中查找字符串2，找到了就用字符串3来替换，直至全部替换完。 const st1:string=abmncdefghigklmnopqrmnst; st2:string=mn; st3:string=speed; var i,j,k:integer; begin writeln(string1=,st1); writeln(string2=,st2); writeln(string3=,st3); k:=pos(st2,st1);,repeat delete(st1,k,length(st2); insert(st3,st1,k); k:=pos