Lý Thuyết: Kiểu Mảng Trang 53 SGK Tin Học 11: Bài 11

1. Kiểu mảng một chiều

Mảng một chiều là dãy hữu hạn các phần tử cùng kiểu.

Mảng được đặt tên và mỗi phần tử của nó có một chỉ số.

Để mô tả màng một chiều cần xác định kiểu của các phần tử và cách đánh số các phần tử của nó (mỗi phần tử của nó có một chỉ số).

Để người lập trình có thể xây dựng và sử dụng kiều mảng một chiều, các ngôn ngữ lập trình có quy tắc cách thức cho phép xác định:

- Tên kiểu mảng một chiều;

- Số lượng phần tử;

- Kiểu dữ liệu của phần tử;

- Cách khai báo biến;

- Cách tham chiếu đến phần tử.

Có thể truy cập (hay thao tác) trên mỗi phần tử của mảng, trong việc làm đó mỗi phần tử cùa mảng được xác định bởi tên của mảng và chi số tương ứng của phần tử này.

Kiểu mảng là một kiêu dữ liệu có cấu trúc, rất cần thiết và hữu ích trong nhiều chương trình.

❖ Khai báo

Khai báo mảng một chiều có dạng tổng quát như sau:

Cách 1: Khai báo trực tiếp biến mảng một chiều:

var <tên biến mảng>:array [kiểu chỉ số] of <kiểu phần tử>;

Cách 2: Khai báo gián tiếp biến mảng qua kiểu mảng một chiều:

type <tên kiểu mảng>= array [kiêu chỉ số] of <kiếu phần tử>;

var <tên biến mảng>:<tên kiểu mảng>;

Trong đó:

Kiểu chỉ số thường là một đoạn số nguyên liên tục có dạng n1...n2 với n1, n2 là các hàng hoặc biểu thức nguyên xác định chỉ số đầu và chỉ số cuối (n1<n2);

Kiểu phần tử là kiểu của phần tử mảng.

Ví dụ, các khai báo sau đây là hợp lệ về mảng một chiều:

Type

ArrayReal = array [-100..200] of real;

ArrayBoolean = array [-n+1..n+1] of boolean;

ArrayInt = array [-100..0] of interger;

trong đó, n là hằng nguyên.

Tham chiếu tới phần tử của mảng một chiều được xác định bởi tên mảng cùng với chỉ số, được viết trong cặp dấu ngoặc [ và ].

❖  Lưu ý:

• Đối với ví dụ 1 về bài toán: "Tìm phần tử lớn nhất của dãy số nguyên”. Chương trình của bài toán như sau:

Program timMax;

uses crt;

const

Nmax := 250;

type

arrint = array[1..Nmax] of integer;

var

N, i, Max, csmax: integer;

A: arrlnt;

Begin

clrscr;

write (‘Nhap so luong phan tu cua day so, N- ‘);

readln (N);

for i:= 1 to N do

begin

write (‘Phan tu thu ‘ ,i,’ = ‘ ) ;

 readln (A [ i ] );

end;

Max: =A (10); csmax:= 1;

for i:= 2 to N do if A[i] > Max then

begin

Max:= A[i]; csmax:= i;

end;

writeln(‘Gia tri cua phan tu Max: ‘, Max);

write In(’Chi so cua phan tu Max: ‘ , csmax); readln

End

Kh chạy chương trình, giả sử ta nhập giá trị các phân tử:

Phần tử thứ nhất là 15;

Phần tử thứ hai là 5;

Phần tử thứ ba là 9;

Phần tử thứ tư là 6;

Phần tử thứ năm là 8;

thì trên màn hình thông báo kết quả: ‘Gia tri cua phan tu Max: 15″, ‘Chi so cua phan tu lon nhat la 1*.

Khi đó màn hình có dạng như hình 26 dưới đây:

Từ chương trình này, chúng ta rút ra được một số điều cơ bản cần phải quan tâm, đó là:

- Dùng mảng có kiểu phần tử là nguyên để biểu diễn một dãy hữu hạn số nguyên và cách khai báo mảng này.

- Câu lệnh for-do thứ nhất trong chương trình thể hiện một nhiệm vụ trong bước 1 của thuật toán, dùng để nhập các phần tử của mảng, số phần tử thực sự của mảng do người chạy chương trinh nhập vào bởi câu lệnh ngay trước câu lệnh for-do này.

- Câu lệnh for-do thứ hai trong chương trình thể hiện vòng lặp (gồm bước 3 và 4 trong thuật toán), đùng để duyệt tuần tự từng phần tử trong mảng lọc lấy

Đối với ví dụ 2, về bài toán: “Sắp xếp dãy số nguyên bằng thuật toán đổi chỗ”. Chương trình của bài toán như sau:

program sapxep;

uses crt;

const Nmax = 250;

type

ArrInt = array[1..Nmax] of integer;

var

N,I,j,t: integer;

A: Arrlnt;

Begin

clrscr

write ( ‘ Nhap so luong phan tu cua day so, N-‘);

readln(N); for i:= 1 to N do begin

write(‘ Phan tu thu’,i,’ = ‘);

readln(A[i]);

end,

for j:= N downto 1 do begin

for i:= 1 to j-1 do if A[i] > A[i+1] then

begin

t: = A [ i ] , A[i]:= A[i+1];

A [ i +1 ] : = t;

end;

end;

writeln(‘Day so duoc sap xep la:’); for i:= 1 to N do write(A[i]:4);

readln

End.

Khi chạy chương trình, giả sử ta nhập số phần tử của dãy là 5 với giá trị các phần tử như sau:

Phần tử thứ nhất= 5;

Phần tử thứ hai= 7;

Phần tử thứ ba= 9;

phần tử thứ tư= 3;

Phần tử thứ năm= 6; t

hì trên màn hinh sẽ có thông báo:

Day so duoc sap xep la:

3 5 6 7 9

Màn hình kết quả có dạng như hình 27 dưới đây:

Từ chương trình này, chúng ta rút ra được một số điều cơ bản cần phải quan tâm, đó là:

- Khái niệm lượt: sau lượt (lần) duyệt thứ nhất giá trị lớn nhất xếp đúng vị trí là ờ cuối dãy. Tương tự, sau lượt thứ hai, giá trị lớn thứ hai được xếp ở vị trí sát cuối.. Sau mỗi lượt có ít nhất một số hạng đã xếp đúng vị tri. Trong thuật toán phải thực hiện bao nhiêu lượt như vậy, mỗi lượt thực hiện trên đoạn nào (từ đâu đến đâu) của dãy số? Giá trị của j chính là chỉ số phần tử cuối trong đoạn được duyệt của lượt. Đây chính là câu lệnh for j :  N downto 2 do với biến đếm / chạy từ N về 2.

- Mỗi lượt bao gồm việc thực hiện một số thao tác: so sánh một phần tử với phần tử đứng ngay sau nó để xử lí, bắt đầu từ phần tử đầu tiên trong dãy đến phần tử thứ j.  Thao tác so sánh để quyết định xử lý (tráo đổi hai phần tử) được lặp một số lần. Đây chính là câu lệnh lặp mà chương trình dùng để thể hiện mỗi lượt. for i: - 1 to j- 1 do if A[i’ > A[i+1] then begin

t : = A [ i ] ;

A[i] : = A[i +1 ] ;

A [ i +1 ] : = t;

end;

Giá trị biến đếm chính là chỉ số phần tử được lấy so sánh với phần tử kề sau nó

trong dãy số. Trong cấu trúc lặp này, chỉ lấy đến j-1 chứ không phải là đến j

Đối với ví dụ 3 về bài toán: "Tìm kiếm nhị phân”

 Thuật toán

Bước 1: Nhập N, các số hạng a1, a2... aN và khóa k

Bước 2: Dau <— 1, Cuoi <-N;

Bước 3: Giua <—[ Dau + Cuoi]/2

Bước 4: Nếu Agiữa = k thì thông báo chỉ số Giua rồi kết thúc;

Bước 5: Nếu Agiữa> k thì đặt Cuối= Giữa-1 rồi chuyển đến bước 7;

Bước 6: Nếu Nếu Agiữa ≤ k Dau

Bước 7: Nếu Dau > Cuoi thì thông báo dãy A không cỏ sổ hạng có giá trị bằng krồi kết thúc;

Bước 8: Ọuay lại bước 3.

Từ thuật toán của bài toán, chúng ta rút ra được một số điều cơ bản cần phải lưu ý, đó là:

- Mảng đã dược sắp xếp tăng dần

- Trong thuật toán, việc tìm kiếm thực chất là lặp một số lần (chưa xác định được trước) các thao tác sau: chọn số hạng ở "giữa” dãy, so sánh số hạng đó với k, căn cứ vào kết quả so sánh này để hoặc kết luận đã tìm thấy (trường hợp xảy ra bằng) hoặc thu hẹp phạm vi tìm kiếm(trường hợp không bằng).

- Khi nào quá trình lặp nói trên dừng lại? Quá trình lặp đó cần dừng lại với một trong hai sự kiện sau xảy ra gồm đã tìm thấy hoặc không gian tìm kiếm đã trở nên bằng rỗng (nghĩa là không còn đoạn nào của dãy cho ta hy vọng chứa phân tử cần tìm).

- Phạm vi tìm kiếm trên dãy là một đoạn được xác định bởi các biến nguyên Dau và Cuoi, tương ứng cho biết bắt đầu từ phần tử có chỉ số Dau của dãy cho đến phần tử có chỉ số Cuoi của dãy. Từ đó, ta đưa ra được công thức xác định phân tử ở "giữa” phạm vi tìm kiếm và công thức xác định lại giá trị cho biến Dau hay Cuoi trong mỗi trường hợp thu hẹp phạm vi tìm kiếm.

Chương trình của bài toán như sau:

program TK_nhiphan;

uses crt;

const

Nmax = 2 50; type

Arrlnt = array[1..Nmax] of integer;

var

N, i0 k: integer;

Advertisements (Quảng cáo)

Dau, Cuoi, Giua: integer;

A: Arrlnt;

Tim__thay: boolean;

Begin

clrscr;

write(‘Nhap so luong phan tu cua day so, N=’ ) ;

readln (N) ;

writeln(‘Nhap cac phan tu cua day so tang:’); for i:= 1 to N do

begin

write(‘Phan tu thu ‘,i,’=1); readln (A [ i ] );

end;

write(‘Nhap gia tri k =’);

readln (k) ;

Dau:= 1,  Cuoi : = N; Tim__thay : = false ;

while (Dau <= Cuoi) and not (Tim_thay) do

begin

Giua:= (Dau+Cuoi) div 2; if A[Giua] = k then Tim_thay:= true

else

if A[Giua] > k then Cuoi:= Giua-1 else Dau:= Giua + 1;

End;

if Tim_thay then writeln(‘Chi so tim duoc la:’. Giua)t else writeln(Khong tim thay’);

readln

End.

Khi chạy chương trình, giả sử ta nhập số phần tử của dãy N= 5 với giá trị các phần tử như sau:

Phần tử thứ nhất= 3;

Phần tử thứ hai= 5;

Phần tử thứ ba= 7;

Phần tử thứ tư= 9;

Phần tử thứ năm= 12; tiếp đến, ta nhập giá trị k =9 thì trên màn hình sẽ cỏ thông báo:

Chi so tim duoc la: 4

Kết quả trên màn hình có dạng như hỉnh 28 dưới đây:

Từ chương trình này, chúng ta rút ra được một số lưu ý như sau:

- Phần cơ bản của chương trình sẽ gồm một cấu trúc lặp (chưa xác định trước được sổ lần lặp);

- Cần ghi nhận được sự kiện tìm thấy, có thể đùng một biến logic Tim-thay để ghi nhận. Khi chưa tỉm kiếm, tất nhiên phải khởi tạo biến này là False. Khi tìm thấy sẽ đổi giá trị của biển Tim-thay thành True. Điều này làm dễ dàng xác định điều kiện lặp.

- Điều kiện lặp là gỉ? Thể hiện sự kiện chưa tìm thấy hoặc không gian tìm kiếm chưa rỗng bằng biểu thức lôgic nào?

- Khi kết thúc lặp, giá trị của biến logic Tim-thay cho biết có tìm thấy hay không, bởi vậy sau cấu trúc lặp, dùng câu lệnh rẽ nhánh theo giá trị của Tim- Thay để thông báo kết quả.

- Trường hợp tìm thấy, cần đưa ra kết quả chi tiết hơn, cần thông báo chỉ số của phần tử có giá trị k. Khi tìm thấy, sự kiện này được ghi nhận ngay (ngay sau khi so sánh phần từ giữa được chọn với k), rồi điều kiện lặp được kiểm tra và quá trình lặp dừng lại. Bởi vậy, lúc đó biến Giua cho biết chỉ số của phần tử cần tìm.

2. Kiểu mảnh hai chiều

- Mảng hai chiều là bảng các phần tử cùng kiểu là mạng một chiều mà mọi phần tử của nó lại là một mảng một chiêu

- Với kiểu mảng hai chiều, các ngôn ngữ lập trinh có các quy tắc, cách thức cho phép xác định:

- Tên kiều mảng hai chiều;

- Số lượng phần tử của mỗi chiều:

- Kiểu dữ liệu cùa phần tử;

- Cách khai báo biến;

- Cách tham chiếu đen phần tử.

 Ví dụ, bàng cứu chương có thể được khai báo bằn 11 Pascal như sau:

var B: array[1..9] of array[1..10] of integer;

hoặc có thể khai báo ngắn gọn hơn như sau:

var B: array[1..9,1.. 10] of integer;

❖ Khai báo

Cách 1: Khai báo trực tiếp biến mảng hai chiều như sau:

var <tên biến mảng>: array [kiểu chỉ số dòng, kiểu chỉ số cột] of <kiểu phần tử>;

Cách 2: Khai báo gián tiếp biến mảng qua kiểu máng hai chiều:

type <biến kiểu mảng>=array[kiểu chỉ số dòng, kiểu chỉ số cột] of <kiểu phần tử>;

var <tên biến mảng>: <tên kiểu mảng>:

• Ví dụ

Các khai báo sau đâv là hợp lệ:

type

ArrayReal = array[-100..2 00, 10 0..200] of real;

ArrayBoolean = array[1..n+1, n..2*n] of boolean;

var

Arraylnt: array[1..10# ..15] of integer;

ArrayLong: array [ 0 . 3* (n+1) , 0..n] of longint:;

Trong đó, n là hằng nguyên.

Tham chiếu tới phần tử cùa mảng hai chiều được xác định bởi tên mảng cùng với hai chi số được cách nhau bời dấu phẩy và viết trong cặp dấu ngoặc [ và ].

Vi dụ

Tham chiếu tới phần tử ở dòng 5, cột 9 của biến mảng Arrayỉnt được viết như sau: Arraylnt[ 5,9];

❖ Lưu ý:

- Giống như khi khai báo kiểu dữ liệu mảng một chiều, người lập trình cần phải xác định kiểu của các phần tử tạo nên mảng và kiểu chỉ số. Cách xác định kiểu chỉ số vẫn như đã biết ờ kiểu mảng một chiều, chỉ khác là ở mảng hai chiều cần xác định hai chỉ số, hai chỉ số đó độc lập với nhau.

- Giống như ở mảng một chiều, các thao tác nhập, xuất hay xử lý mỗi phần tử của mảng phải tuân theo quy định kiểu phần tử của mảng.

- Việc thực hiện các tao tác nào đó (nhập, xuất hay xử lí) lần lượt trên các phần tử của mảng hai chiều thường gần với hai câu lệnh for-do lồng nhau.

Đối với ví dụ 1 về bài toán: “Tính và đưa ra màn hình bảng cửu chương”. Chương trình tính và đưa ra màn hình bảng cửu chương:

Chương trình tính và đưa ra màn hình bảng cửu chương:

program Bangcuuchuong;

uses crt;

var

B: array[1..9, 1..10] of integer;

{B: bien mang hai chieu luu bang cuu chuong}

i, j: integer;

Begin

clrscr;

for i:=1 to 9 do

for j:=1 to 10 do

B[i, j]:= i*j;

for i:=1 to 9 do begin

for j:=1 to 10 do write(B[i,j]:4) ;

writeln;

end;

readln

End.

Khi chạy chương trình, kết quả có dạng như hình 29 dưới đây:

Đối với ví dụ 2 về bài toán: “Lập chương trình nhập vào từ bàn phím các phần tử của mảng hai chiều B gồm 5 dòng, 7 cột với các phần tử là các số nguyên

Begin

clrscr;

writel( ‘Nhap cac phan tu cua mang theo dong:’);

for i := 1 to 5 do

begin

for j:= 1 to 7 do read (b [ i, j ] );

 writeln;

end;

write(’Nhap vao gia tri k= ‘); readln(k); d: = 0 ;

writeln(‘DS cac phan tu mang nho hon ‘, k,’:’); for i:=1 to 5 do

for j:= 1 to 7 do if b[i,j] < k then begin

write(b[i,j],’ ‘); d:= d+1; end;

if d=c then writeln(‘khong co phan tu nao nho hon’, k);

readln

End.

Sau khi chạy chương trình, nhập dữ liệu với giá trị các phần tử của mảng và giá trị a = 7 thì danh sách các phần tử nhỏ hơn 7 được in ra màn hình và kết quả của chương trình như hình 30 dưới đây:

 Nhưng khi nhập vào một giá trị k = 3 nhỏ hơn các phần tử của mảng đã nhập vào thì chương trình sẽ in ra thông báo “khong co phan tu nao nho hon 5 (Hình 31)

Đối với chương trình trên, ta có thể thay đổi hình thức nhập các phần tử của mảng vào từ bàn phím. Khi đó, chương trình sẽ như sau:

program manghaichieu_2;

uses crt;

var b: array[1..5, 1..7] of integer;

d, i, j, k: integer;

Begin

clrscr;

writeln(‘Nhap cac phan tu cua mang theo dong:’); for i:= 1 to 5 do begin

for j:= 1 to 7 do begin

write(‘B[‘ ,i,’ , j, ‘] = ‘);

read(b[i,j]);

end;

writeln;

end,

write(‘Nhap vao gia tri k= ‘);

readln(k); d:=0,

writeln(‘DS cac phan tu mang nho hon ‘, k,’:’);

for i:=1 to 5 do

for j:= 1 to 7 do if b[i,j] < k then

begin

write(b[i,j],’ ‘)? d:= d+1; end;

if ‘d=0 thon writeln(’khong co phan tu nao nho hon ‘ , k ‘:’) ;

readln

End .

Kết quả chương trình có dạng như hình 32 dưới đây: