nbhkdz.com冰点文库

数组下


数组(下)
二维数组

一、定 义 二、存 储 三、查 询

一、定义
? Var 数组名 : array[行下标起点..下标终点,列下标起 点..下标终点] of 数据类型; ? 例如: ? var a : array[1..3,1..5] of integer; ? //定义a为3*5(3行5列)的数组,数组类型为

整型 ? 二维数组本质上是以一维数组作为数组元素的数组, 即“数组的数组”。

二、存储
? 物理存储 ? 定义N行M列的二维数组: ? var a : array[1..N,1..M] of T; // T :类型名,如char , double, integer等。 ? // M、N : 正整数,或值为正整数的常量表达式 ? 每个元素都是一个类型为T的变量 ? N× M个元素在内存里是一个挨一个连续存放的。 ? 数组占用了一片连续的、大小总共为 N× M× sizeof(T)字节 的存储空间。 ? 表达式“sizeof(a)”的值就是整个数组的体积,即 N× M× sizeof(T) 。

二、存储
? ? ? ? ? ? ? 逻辑存储 循环初始化 for i := 1 to n do for j := 1 to m do a[i,j] := 0; 函数初始化 fillchar(a,sizeof(a),0); 常量初始化const dir: array[1..4,1..2] : integer = ((1,0),(0,1),(1,0),(0,-1));

? ? 数组名[行下标] [列下标] := 元素值;

考虑这样一个问题:
? 例1:矩阵存储。输入一个n*n二维矩阵,并原样输出。

输入: 3 1 2 3 4 5 6 7 8 9

输出: 1 2 3 4 5 6 7 8 9

? 例1:矩阵存储。输入一个n*n二维矩阵,并原样输出。
1. 2. 3. 4. 5. 6. const maxn = 20; var a : array[1..maxn,1..maxn] of integer; i, j, n, x: integer; begin fillchar(a,sizeof(a),0); readln(n); 13. for i := 1 to n do 14. begin 15. for j := 1 to n do 16. begin 17. write(a[i,j],' '); 18. end; 19. writeln; 20. end; 21. end.

7. 8. 9. 10. 11. 12.

for i := 1 to n do for j := 1 to n do begin read(x); a[i,j] := x; end;

? 例2:矩阵旋转。输入一个n*n二维矩阵,并90度顺时针 旋转输出。

输入: 3 1 2 3 4 5 6 7 8 9

输出: 7 4 1 8 5 2 9 6 3

? 例2:矩阵旋转。输入一个n*n二维矩阵,并90度顺时针 旋转输出。
1. 2. const maxn = 20; var a, b : array[1..maxn,1..maxn] of integer; n, i, j, x: integer; begin readln(n); 13. for i := 1 to n do 14. begin 15. for j := 1 to n do 16. write(b[i,j],' '); 17. writeln; 18. end; 19. end.

3. 4. 5. 6. 7. 8. 9. 10. 11. 12.

for i := 1 to n do for j := 1 to n do begin read(x); a[i,j] := x; b[j,n+1-i] := a[i,j]; end;

? ? ? ? ? ? ?

逻辑存储 循环初始化 for i := 1 to n do for j := 1 to m do a[i,j] := 0; 函数初始化 fillchar(a,sizeof(a),0); 常量初始化const dir: array[1..4,1..2] : integer = ((1,0),(0,1),(1,0),(0,-1));

? ? 数组名[行下标,列下标] = 元素值;

三、查询
例3:稀疏矩阵。大部分元素是0的矩阵称为稀疏矩阵。假 设有k个非0元素,则可把稀疏矩阵用k*3的矩阵简记之,其 中第一列是行号,第二列是列号,第三列是该行列下的非 元素值。

输入: 3 4 0 0 0 5 0 2 0 0 0 1 0 0

输出: 1 4 5 2 2 2 3 2 1

1. 2. 3. 4. 5. 6. 7. 8. 9.

const maxn = 20; var a : array[1..maxn,1..maxn] of integer; b : array[1..maxn,1..3] of integer; n, m, i, j, cnt: integer; begin readln(n, m); for i := 1 to n do for j := 1 to m do read(a[i,j]);

10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25.

cnt := 0; for i := 1 to n do for j := 1 to m do begin if a[i,j] <> 0 then begin cnt := cnt + 1; b[cnt,1] := i; b[cnt,2] := j; b[cnt,3] := a[i,j]; end; end; for i := 1 to cnt do begin writeln(b[i,1],' ',b[i,2],' ',b[i,3]); end;

26. end.

例4:计算鞍点。给定一个5*5的矩阵,,每行只有一个最 大值,每列只有一个最小值,寻找这个矩阵的鞍点。 鞍点指的是矩阵中的一个元素,它是所在行的最大值,并 且是所在列的最小值。如果存在鞍点,输出鞍点所在的行、 列及其值,如果不存在,输出"not found"

输入: 11 3 5 6 9 12 4 7 8 10 10 5 6 9 11 8 647 2 15 10 11 20 25

输出: 418

例4:计算鞍点。给定一个n * m的矩阵,每行只有一个最 大值,每列只有一个最小值,寻找这个矩阵的鞍点。 鞍点指的是矩阵中的一个元素,它是所在行的最大值,并 且是所在列的最小值。如果存在鞍点,输出鞍点所在的行、 列及其值,如果不存在,输出"not found" 主要步骤: 1:生成矩阵A矩阵中的元素(1≤i≤n,1≤j≤m) 2:i=1(i代表行) 3: 找出第i行上最大的数maxval,并记录该值所在列的位置 maxj 4:找出第maxj列上最小的数minval及所在行mini 5:如果maxval = minval and mini = i,则找到了鞍点,否 则无 6:i=i+1 当i <= m,返回步骤3,否则结束

四、填充
? 例5:拐角矩阵
对于键入的n(1≤n≤20),显示一个n行n列的拐角矩阵。下面 给出的是n=5时的拐角矩阵。

1 1 1 1 1

1 2 2 2 2

1 2 3 3 3

1 2 3 4 4

1 2 3 4 5

分析:找出位置和其值的对 应关系 。

a[i][j]=

i j

i<=j i>j

想一想:
找出位置和其值的对应关系 。
5 4 3 2 1 4 4 3 2 1 3 3 3 2 1 2 2 2 2 1 1 1 1 1 1 1 2 3 4 5
a[i][j]=

1 2 3 4 4

1 2 3 3 3

1 2 2 2 2

1 1 1 1 1

1 1 1 1 1

2 2 2 2 1

3 3 3 2 1

4 4 3 2 1

5 4 3 2 1

][j]=

n+1-j i≤j n+1-i i>j

a[i][j]= i i + j≤n+1 n+1-j i+j>n+1

j i+ j≤n+1 n+1-i i+j>n+1

? 例6:回型矩阵

1 1 1 1 1 1 1

1 2 2 2 2 2 1

1 2 3 3 3 2 1

1 2 3 4 3 2 1

1 1 1 2 2 1 3 2 1 3 2 1 3 2 1 2 2 1 1 1 1

? 例6:回型矩阵

有点赖皮,但很容易想到……
1 1 1 2 2 1 1 1 3 1 2 1 2 1 2 2 3 1 1 1 3 1 2 1 2 1 1 2 1 2 1 1 1 1 1 2 1 2 3 1 2 3 4 1 2 3 1 2 1 1 1 2 1 2 3 1 2 3 1 2 3 1 2 1 1 1 2 1 2 1 2 1 2 1 2 1 1 1 1 1 1 1 1 1

? 例6:回型矩阵

1 1 1 1 1 1 1 1 2 2 2 2 2 1 1 2 3 3 3 2 1 1 2 3 4 3 2 1 1 2 3 3 3 2 1 1 2 2 2 2 2 1 1 1 1 1 1 1 1

有两条对角线,实对角线(反 对角线)上的元素位置的共同 点是 i+j=n+1。其上、下半部 分别满足i+j<n+1和 i+j>n+1。 观察实对角线的上、下部,得出:
i j n+1-j n+1-i i+j≤n+1且i≤j i+j≤n+1且i>j i+j>n+1且i≤j i+j>n+1且i>j

A[i],[j]=

? 例6:回型矩阵

法III:
1 1 1 1 1 1 1 1 2 2 2 2 2 1 1 2 3 3 3 2 1 1 2 3 4 3 2 1 1 2 3 3 3 2 1 1 2 2 2 2 2 1 1 1 1 1 1 1 1

将回形方阵看成由若干圈构成, 最外圈全是1,次外圈都是2。 只要我们找出任意一点[i][j]所 在圈的圈号就好了。如:下图 上的点(4,3)到四边的距离(上 右下左)分别是i=4,n+1-j=5, j=3, n+1-i=4,那么它所在圈号 就是4个距离中的最短者,即3。 由此:

A[i][j]=min(i,n+1-j,j, n+1-i)

? 例7:螺旋矩阵

N=7 19 20 18 37 17 36 16 35 15 34 14 33 13 12

21 38 47 46 45 32 11

22 39 48 49 44 31 10

23 40 41 42 43 30 9

24 25 26 27 28 29 8

1 2 3 4 5 6 7

? 例7:螺旋矩阵

逐圈考虑,每圈四边,顺序为右上 ?右下,右下?左下, 左下?左上,左上?右上 圈号i 行j 列k 第i圈的四边为: 1 1~6 7 右边:a[i][n+1-i]—>a[n-i][n+1-i] 2 2~5 6 下边:a[n+1-i][n+1-i]—>a[n+1-i][i+1] 3 3~4 5
左边:a[n+1-i][i]—>a[i+1][i]
上边:a[i][i]—>a[i][n-i]

19 20 21 22 23 24 18 37 38 39 40 25 17 36 47 48 41 26 16 35 46 49 42 27 15 34 45 44 43 28 14 33 32 31 30 29 13 12 11 10 9 8

1 2 3 4 5 6 7

? 例7:螺旋矩阵

从1开始填写。设“笔”的坐标为(x,y),则一开始 x= 1, y = n,即第1行,第n列。“笔”的移动轨迹是:下, 下,下,左,左,左,上,上,上,右,右,右,下,下, 下……总之,先是下,到不能填为止,然后是左,接着是 上,最后是右。“不能填”是指再走就出界,或者再走就 要走到以前填过的格子。

法III:

? 例7:螺旋矩阵

那么:能否直接根据行号和列号直接计算出矩 阵元素值呢?
当n给定时,则螺旋矩阵是唯一的,即每一个元素也是唯一 的,因此行号列号必然与元素值之间存在唯一的映射关系,但 这种关系不是很直观的,需要我们通过观察,运用数学知识进 行推导。 通过观察螺旋矩阵,我们不难得出如下结论: 1、矩阵由若干圈组成,n为奇数时最内圈是一个点; 2、每一圈右上角的元素最小; 3、每一圈上的元素从右上角开始递增; 4、从最外圈往内数,每一的边长依次为n、n-2、n-4……

? 例7:螺旋矩阵

难点1 如何确定每圈右上角的第一个元素值 难点2 如何确定每圈上其他位置与第一个元素值 之间的关系
如果我们知道每一圈右上角的元素值a,和每一圈的边长L, 则运用简单的代数关系可以求出e[i,j],可以分四种情况讨论: 1、j=L,此时e在正方形圈的右边长上 2、i=L,此时e在正方形圈下边长上 2、i=1,此时e在正方形圈的左边长上 3、j=1,此时e在正方形圈的上边长上

? 例8:蛇形矩阵

? 例8:蛇形矩阵 对角线编号i:1~n
上三角

1

2

3

4
奇对角线:纵坐标变化 j:i ~ 1 横坐标 x+j = i+1 x = i+1-j 偶对角线 j:1~i 横坐标 x+j = i+1 x = i+1-j

? 例8:蛇形矩阵 对角线编号i:n+1~2*n-1
上三角

5
6 7

奇对角线:纵坐标变化 j:n ~ i+1-n 横坐标 x+j = i+1 x = i+1-j 偶对角线 j:i+1-n~ n 横坐标 x+j = i+1 x = i+1-j

? 例9: (奇数)幻方矩阵
把整数1到n^2(n为奇数)排成一个n*n方阵,使方阵中的每一行、每一列以及 对角线上的数之和都相同。如图就是一个五阶魔方阵。

15 8

1 24 17 5 23

分析:当n为奇数时,魔方阵可按下列方法构成: (1)把1填在第一行的正中间,然后依次填入2到n^2; (2)如果数K填在第I行第J列的格子中,那么数K+1应 填在它的左上方,即第I-1行、第J-1列的位置中,若左 上方无格子,即I-1=0,那么填在第N行第J-1列的格子 中;若J-1=0,则填在第I-1行第N列的格子中;若I-1和 J-1均为0,那么填在第N行第N列的格子中。

16 14 7

22 20 13 6 4
3 9 21 19 12 10 2 25 18 11

(3)如果按(2)的方法找到的格子中已填过数了,那么数K+1改 填在第K个数的正下方。即填在第I+1行、第J列的那个格子中。

Var magic:array[1..100,1..100] of integer; for i:=1 to n do i,j,r,c,tot : integer; n:integer; begin begin for j:=1 to n do read(n); for i:=1 to n do for j:=1 to n do write(magic[i,j]:3); magic[i,j]:=0; {魔方阵清0} writeln; tot:=1; i:=1;j:=n div 2+1;magic[i,j]:=k; while tot<n*n do end; begin end. tot:=tot+1; r:=i-1;c:=j-1 {h,l用来试探可填数的位置 } if r = 0 then r := n; {I-1=0情况} if c = 0 then c:= n; {j-1=0情况} if magic[r,c]=0 then {未填数} begin magic[r,c]:=tot; i:=r; j:=c; {填数,改变行列值} end; else begin magic[i+1,j]:=tot; i:=i+1; {照(3)填数,产生新行值} end; end;

? 例9: (奇数)幻方矩阵

数组(下) 数组(下)
字符数组 字符串

一、定 义 二、存 储 三、查 询

一、定义
? ? ? ? ? Var 数组名 : array[下标起点..下标终点] of 数据类型; 例如: var a : array[1..26] of char; //定义a为包含16个字符类型的字符数组 字符数组在输入输出方面与其它类型的数组是一样的。使用字符数 组在处理字符串内容时,在删除、添加、取子串等方面很不方便,编 程也相对复杂,一般针对字符串的处理我们可以使用更加方便灵活的 字符串类型,它具有字符数组的全部特征,并且具有自己的一整套处 理过程与标准函数。 ? Var 字符串变量 : string[n]; 其中n必须是0~255之间的整数 ? 字符串定义时,如不指定长度,则按该类型的最大长度(255个字符) 分配空间,使用时最大可用长度为255个;如果在中括号中给出一个 具体的值(1—255之间),则按这个值的大小分配空间。使用时,最 大的可用长度即为该值。更长的字符串处理则需要使用ansistring。

字符串的函数和过程
? ? ? ? ? ? ? ? Copy(s,m,n) 取s中第m个字符开始的n个字符 Length(s) 求s的长度 Pos(sub,s) 在s中找子串sub,返回sub在s中的位置 Insert(sour,s,m) 在s的第m个字符位置处插入子串sour Delete(s,m,n) 删除s中第m个字符开始的n个字符串 Str(x,s) 将整数或实数x转换为字符串s Val(s,x) 将字符串s转换成整数或实数 Upcase(ch) 将字母ch转换为大写字母

二、存储
? 例1 格式化处理。读入一整行只包含大小写字符的字符串, 将其统一转换为大写或小写。
1. 2. 3. 4. 5. 6. 7. 8. var s : string; len,i : integer; begin readln(s); len := length(s); for i := 1 to len do if (s[i] >= 'A') and (s[i] <= 'Z') then s[i] := chr(ord(s[i]) + 32);

9. for i := 1 to len do 10. write(s[i]); 11. writeln; 12. end.

三、查询
? 例2 数字统计。请统计某个给定范围[L,R]的所有整数中, 数字2出现的次数。 ? 输入样例: ? 2 22 ? 输出样例: ? 6

1. 2. 3. 4. 5.

var L, R : integer; i, t, cnt : integer; begin cnt := 0; readln(L,R);

6. 7. 8. 9. 10. 11. 12. 13. 14.

for i := L to R do begin t := i; while t > 0 do begin if t mod 10 = 2 then inc(cnt); t := t div 10; end; end;

15. writeln(cnt); 16. end.

1. 2. 3. 4. 5.

var L, R : integer; s : string; i, j, len, cnt : integer; begin readln(L,R);

6. 7. 8. 9. 10. 11. 12. 13. 14.

for i := L to R do begin str(i,s); len := length(s); for j := 1 to len do begin if s[j] = '2' then inc(cnt); end; end;

15. writeln(cnt); 16. end.

? 例3 数字反转。给定一个整数,请将该数各个位上的数字 反转得到一个新数。新数也应满足整数的常见形式,即除 非给定的原数为0,否则反转后得到的新数的最高位数字 不应为0。 ? 输入样例: ? 123 ? 输出样例: ? 321

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.

var n, m : longint; begin m := 0; readln(n); if n < 0 then begin write('-'); n := -n; end; while n > 0 do begin m := m * 10 + n mod 10; n := n div 10; end;

15. writeln(m); 16. end.

? 例4 统计单词数。给定一个单词,输出它在给定的文章中 出现的次数和第一次出现的位置。单词匹配时,不区分大 小写;给定单词是某一单词的一部分不算匹配。 ? 输入样例: ? To ? to be or not to be is a question ? 输出样例: ? 21

四、计算
? 高精度计算。利用计算机进行数值计算,有时会遇到这样 的问题:有些计算机要求精度高,希望计算的数的位数可 达几十位甚至几百位,这时则涉及到高精度计算。 ? 高精度计算需要处理的几个问题: ? 1、数据的读入与存储 ? 2、进位、借位处理 ? 3、输出

? 例5 [问题描述] 输入两个正整数(最多250位),输出它 们的和。 ? 比如输入: 999999999999999999999999999999999999999999999 999999999 ? 12345678999999999999999999999999 ? 输出: 100000000000000000000001234567899999999999999 9999999998

先加,后统一处理进位 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. for i := 1 to len1 do a[i] := ord(s1[len1+1-i]) - ord('0'); for i := 1 to len2 do b[i] := ord(s2[len2+1-i]) - ord('0'); if len1 > len2 then len := len1 else len := len2; for i := 1 to len do c[i] := a[i] + b[i]; for i := 1 to len do if c[i] > 10 then begin c[i] := c[i] - 10; c[i+1] := c[i+1] + 1; end; if c[len+1] > 0 then len := len + 1;

一边加,一边处理进位 ? i := 1 ; t := 0; ? ? ? ? ? ? ? ? ? ? ? ? ? while (i <= len1) or (i <= len2) do begin c[i] := a[i] + b[i] + t; t := c[i] div 10; c[i] := c[i] mod 10; i := i + 1; end; if t > 0 then begin len := i; c[i] := t; end else len := i - 1;


C语言 数组的最大值及下标(数组)

C语言 数组的最大值及下标(数组)_IT/计算机_专业资料。在一个n(1<=n<=100)个元素的一维整型数组中找出最大值及下标。0821-数组的最大值及下标(数组)时间限...

如何使用下标遍历一维数组

如何使用下标遍历一维数组_工学_高等教育_教育专区。如何使用下标遍历一维数组 1.2 如何使用下标遍历一维数组这是一个微不足道的问题。在数据结构中,经常需要遍历...

定义下标为零的数组

[0];//主要是用来得到一个数组的地址,再由数组的个数来访问 }; int main() { struct helloworld_t *p; unsigned int size = sizeof(struct helloworld_t...

第4章数组练习题

17 4. 引用数组元素时,数组下标可以是_D___ 5. 定义了 int 型二维数组 a[6][7]后,数组元素 a[3][4]前的数组元素个数为__B__ 6. 下列初始化字符...

java入门:得到数组中最有效的元素和下标

java入门:得到数组中最有效的元素和下标_IT/计算机_专业资料。java相关技术1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18...

数组_参考答案

point.length;i++) { System.out.println(point[i]); } } } 5. 在一个有 8 个整数(18,25,7,36,13,2,89,63)的数组中找出其中最大的数及 其下标...

数组下--C语言

关于c语言数组(含例题) 5页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 数组下--C语言 隐藏>> 编程题 3: ...

通过指针带下标的方法访问数组元素

通过指针带下标的方法访问数组元素_数学_自然科学_专业资料 暂无评价|0人阅读|0次下载|举报文档 通过指针带下标的方法访问数组元素_数学_自然科学_专业资料。#...

JQuery index方法获取Jquery对象的数组下标

JQuery index方法获取Jquery对象的数组下标_计算机软件及应用_IT/计算机_专业资料。JQuery index方法获取Jquery对象的数组下标 JQuery index 方法获取 Jquery 对象的数组...

第五章 判断题-数组

第五章 判断题 1.下标用于指出数组中某个元素位置的数字。() 2.把数组中元素按某种顺序排列的过程叫做查找。() 3.确定数组中是否含有某个关键字的过程叫做排序...