1.Khái niệm chung

Chúng ta đã làm quen với các kiểu dữ liệu đơn giản là các kiểu vô hướng (Integer, Char, Boolean, Real, kiểu liệt kê) và đoạn con. Trong Pascal tồn tại các kiểu dữ liệu có cấu trúc là các kiểu dữ liệu được tạo ra từ các phần tử có kiểu dữ liệu đơn giản bằng một cách nào đó. Chúng được đặc trưng bằng kiểu dữ liệu của các phần tử và quan trọng hơn cả là phương pháp cấu thành kiểu dữ liệu mới (điều đó cũng có nghĩa là phương pháp truy nhập vào kiểu dữ liệu có cấu trúc). Tính có cấu trúc của dữ liệu là một đặc trưng của ngôn ngữ lập trình có cấu trúc.

Pascal có tất cả 4 kiểu dữ liệu có cấu trúc mà chúng ta sẽ lần lượt ngiên cứu : mảng (Array), tập (Set), bản ghi  (Record) và tệp (File).

2.Kiểu dữ liệu có cấu trúc: MẢNG (ARRAY) 

Một mảng dữ liệu gồm một số hữu hạn phần tử có cùng kiểu gọi là kiểu cơ bản. Số phần tử của mảng được xác định ngay từ khi định nghĩa ra mảng. Mỗi phần tử của mảng đựoc truy nhập trực tiếp thông qua tên mảng cùng với chỉ dẫn truy nhập được để giữa hai ngoặc vuông [  ].

Định nghĩa kiểu mảng T có kiểu các phần tử là KPT, có kiểu chỉ dẫn KCD để hướng dẫn cách tổ chức mảng cũng như cách truy nhập vào các phần tử mảng được viết trong Pascal như sau :

Type Kiểu_mảng T = Array[ Kiểu_chỉ_dẫn KCD ] Of  Kiểu_phần_tử KPT ;

hay viết tắt thành : T = Array[ KCD ]  Of  KPT ;

Khi đó việc khai báo một biến A có kiểu là Kiểu_mảng có thể được viết như sau :

Var A : Kiểu_mảng T ;

hoặc ta có thể khai báo trực tiếp biến A cùng với kiểu của mảng trong phần khai báo biến khi không có định nghĩa kiểu trong phần Type :

Var A : Array[ KCD ] Of  KPT ;

Chúng ta hãy xét một số ví dụ định nghĩa và khai báo sau :

Type AI = Array[ 1.. 10 ] Of  Integer ;

AC = Array [ 1.. 10 ] Of  Char ;

Color = ( Red, Blue, Green, White, Black ) ;

Var

A, B, C : AI ;

X, Y : AC ;

M1, M2 : Array[ -3.. 5 ] Of  Real ;

MC : Array[ ‘A’.. ‘Z’ ]  Of  Integer ;

MM : Array[ Color ] Of  Boolean ;

AI, AC là hai kiểu mảng gồm 10 phần tử được đánh số thứ tự từ 1 đến 10 thông qua kiểu chỉ dẫn là một đoạn con các số nguyên 1.. 10. Các phần tử của AI có kiểu là số nguyên còn các phần tử của AC có kiểu là các kí tự. A, B, C  là các biến có kiểu là AI.

Còn M1, M2 là hai biến được định nghĩa kiểu luôn khi khai báo. Đây là hai biến mảng gồm 9 phần tử là các số thực, được đánh số từ  -3 đến 5.

MC là một biến mảng gồm 26 số nguyên được đánh số qua các chỉ dẫn là các chữ cái từ ‘A’ đến ‘Z’.

MM là một mảng gồm 5 phần tử kiểu Boolean, các phần tử đựoc đánh dấu qua chỉ dẫn là tên của 5 màu sắc.

Một điều lưu ý là khi khai báo mảng, kiểu chỉ dẫn chí có thể là các kiểu đơn giản như sau : kí tự ( như biến MC ), đoạn con ( ví dụ đoạn con Integer  như các kiểu AI, AC ), kiểu liệt kê do người sử dụng định nghĩa (như biến MM) và kiểu Boolean. Kiểu chỉ dẫn không được là kiểu Real hoặc Integer. Nghĩa là không được viết :

X : Array[ Integer ]  Of  Integer ;

Y : Array[ Real ]  Of  Integer ;

Việc truy nhập vào một phần tử nào đó của mảng được thực hiện qua tên biến mảng, theo sau là giá trị chỉ dẫn để trong ngoặc vuông như :

MM[ Red ] := True ;

MC[ ‘B’ ] := 5 ;

Do thời gian truy nhập vào một phần tử của mảng không phụ thuộc vào giá trị của chỉ dẫn nên cấu trúc mảng thuộc kiểu cấu trúc truy nhập trực tiếp.

       Ví du1:

Gán tất cả 5 giá trị của mảng B ( như đã định nghĩa ở trên )  qua bàn phím, ta sẽ dùng thêm một biến I có kiểu là Integer để làm biến chỉ dẫn :

Writeln (‘ Vao so lieu cho mang B ‘ ) ;

For  I := 1  To  5  Do

Begin

Write (‘ B[ ‘, I, ‘ ] = ‘) ;

Readln (  B[ I ] ) ;

End ;

Kết quả thể hiện ra màn hình với các con số là do người sử dụng gõ vào :

Vao so lieu cho mang B

B[1] = 2

B[2] = 12

B[3] = 612

B[4] = 2

B[5] = 34

Nếu bạn muốn vào số liệu của cả một hàng của Array trên cùng một dòng màn hình  thì bạn phải ghi rõ tất cả các biến cần đọc ( là các phần tử của mảng ) trong thủ tục Readln. Khi này sẽ không áp dụng vòng For được nữa :

Write (‘ Vao so lieu hang 1 ‘) ;

Readln ( B[1], B[2], B[3], B[4], B[5] ) ;

Kết quả hiện ra màn hình :

Vao so lieu hang 1 : 2  12  612  2  34

Giữa các số gõ là các dấu cách với số lượng tùy ý nhưng ít nhất phải là 1.

Ví du 2:

Cộng hai mảng C = A + B ( A, B, C với định nghĩa như trên thực ra là các mảng hay ma trận một chiều ) :

For  I := 1   To  10  Do

C[ I ]:=A[ I ] + B[ I ] ;

Ví du 3:

Giả sử ta muốn đếm trong 100 lần gõ kí tự vào qua bàn phím, số lần xuất hiện các kí tự từ  ‘A’  đến  ‘Z’  là bao nhiêu. Biến MC được khai báo dưới đây đóng vai trò là bộ đếm, biến kí tự Ch được dùng như là biến chỉ dẫn

Var

I : Integer ;

Ch : Char ;

MC : Array[ ‘A’.. ‘Z’ ]   Of   Integer ;

BEGIN

(* Xóa mảng MC về không *)

For  Ch :=  ‘A’ To ‘Z’  Do  MC[ Ch ] := 0 ;

(*  Đọc 100 kí tự và đếm *)

For  I := 1  To  100  Do

Begin

Readln ( Ch ) ;

(* Hàm Upcase biến chữ thường thành chữ hoa, Ví dụ  ‘a’ thành ‘A’  *)

Ch := Upcase ( Ch ) ;

(* Đếm số lần xuất hiện từng kí tự *) ;

Inc ( MC[ Ch ] ) ;

End ;

(* Chỉ in ra kết quả trên màn hình các chữ đã xuất hiện *)

For  Ch := ‘A’  To  ‘Z’  Do

If  MC[ Ch ] > 0  Then

Writeln ( ‘ So chu ‘, Ch,’ = ‘, MC [Ch ] : 4 ) ;

END.

Kết quả hiện ra trên màn hình có dạng :

So chu A = 2

So chu C = 68

……………………

So chu Z = 8

             Sắp xếp các phần tử của mảng theo một trật tự tăng hoặc giảm là một ví dụ rất bổ ích cho việc nắm vững các phép xử lí mảng. Sau đây sẽ trình bày một số phương pháp sắp xếp mảng qua các ví dụ.

             Giả sử ta có một dãy dữ liệu ( số thực, số nguyên, kí tự … ) được chứa trong một mảng. Sau đây là một số vì dụ về một số phương pháp xếp mảng các số nguyên. Việc các phần tử mảng là các số nguyên chỉ là một ví dụ, nó có thể là mảng các số thực hoặc mảng các xâu kí tự.

Cách làm:

             Đầu tiên đem phần tử thứ nhất so sánh với các phần tử tiếp theo, nếu nó lớn hơn thì đem đổi chỗ giá trị của hai phần tử so sánh. Kết quả sau lượt đầu tiên giữ giá trị nhỏ nhất. Tiếp theo vòng 2, Đem phần tử thứ 2 so sánh với các phần tử tiếp theo.

                     Program  SAP_XEP ;

Const N =  5 ;

Var  MI : Array[ 1.. N ]  Of  Integer ;

T : Integer ;     (* T là biến trung gian *)

I, J : Integer ;

BEGIN

(*  Đọc các số cần sắp xếp vào mảng MI *)

For  I := 1  To  N  Do

Begin

Write (‘ MI[ ‘,  I ,’ ] = ‘) ;

Readln ( MI[ I ] ) ;

End ;

(* Sắp xếp *)

For  I := 1  To  N – 1   Do

For  J :=  I + 1 To N  Do

Begin

If  MI[ I } > MI[ J ]  Then

Begin

T := MI[ I ] ;

MI[ I ]  := MI[ J ] ;

MI[ J ] := T ;

End ;

End ;

(*  In ra kết quả *)

Writeln ;

Writeln ( ‘ Sau khi sap xep ‘ ) ;

For  I := 1 To N  Do   Writeln ( MI[ I ] : 6 ) ;

END.

Kết quả chương trình hiện ra trên màn hình :

M[ 1 ] = – 1

M[ 2 ] = 456

M[ 3 ] = 34

M[4 ] = – 312

M[ 5 ] = – 56

Sau khi sắp xếp :

-312        -56           -1      34           456

             Kiểu phần tử của mảng không bị hạn chế nhiều như kiểu chỉ dẫn. Nó còn có thể là các kiểu có cấu trúc. Ví dụ sau cho thấy việc khai báo một mảng có các phần tử cũng là mảng.

   Ví du:

Type PT = Array [ 1.. 5 ]  Of  Real ;

Color = ( Red, Blue, Green, White, Black ) ;

Var  MPT : Array [ 1.. 3 ]  Of   Pt ;

Z : Array [ 1.. 3, ‘A’.. ‘C’ ]  Of Color ;

hoặc viết một lần như sau :

Var  MPT : Array [ 1.. 3 ]  Of  Array  [ 1.. 5 ] Of Real ;

hoặc thường được viết gọn lại :

Var  MPT : Array [ 1.. 3, 1.. 5 ]  Of  Real ;

MPT được định nghĩa như trên chính là ma trận hai chiều 3 hàng và 5 cột.

             Việc truy nhập đối với mảng có định nghĩa phức tạp như MPT được tiến hành qua hai lần đóng mở ngoặc vuông. Ví dụ MPT [3] [5] hoặc MPT [ 3, 5 ] biểu diễn phần tử ở hàng 3 và cột 5.

             Cách viết MPT[i] [j] và MPT[ i, j ] là tương đương nhau. Mảng được định nghĩa như trên có thể hiểu là ma trận nhiều chiều. Phần tử MPT[ i, j ]  sẽ là phần tử ở hàng thứ I, cột thứ J  của MPT

 Ví du:

Chương trình nhân hai ma trận vuông cấp N

C = A * B

Phần tử của ma trận tích được tính theo công thức :

Const N = 3 ;

Phay = ‘, ‘ ;  (* Hằng kí tự : Dấu phẩy *)

Var A, B, C  : Array[ 1.. N, 1.. N ] Of  Integer ;

I, J, K :  Integer ;

BEGIN

(* Đọc giá trị của ma trận A *)

For  I := 1  To  N  Do

For  J := 1  To  N  Do

Begin

Write ( ‘ A[ ‘, I, phay, J, ‘ ] = ‘ ) ;

Readln ( A[ I, J ] ) ;

End ;

(* Đọc giá trị của ma trận B *)

For  I := 1  To  N  Do

For  J := 1  To  N  Do

Begin

Write ( ‘ B[ ‘, I, phay, J, ‘ ] = ‘ ) ;

Readln ( B[ I, J ] ) ;

End ;

(*  Nhân hai ma trận vuông cấp N  C = A * B  *)

For  I := 1  To  N  Do

For  J := 1  To  N  Do

Begin

C[ I, J ] := 0 ;

For  K := 1  To  N  Do

C[ I, J ] := C[ I, J ] + A[ I, K ] * B[ K, J ] ;

End ;

(* In kết quả theo kiểu viết ma trận *)

Writeln (‘ Tich cua hai ma tran = ‘) ;

For  I := 1  To  N  Do

Begin

For  J := 1  To  N  Do  Write ( C[ I, J ] : 5 ) ;

Writeln ;

End ;

END.

                     Trong chương trình trên, việc đọc ma trận được tiến hành qua từng dòng cho mỗi phần tử của mảng. Bạn có thể sửa lại đọc vào ma trận dưới dạng từng dòng tương ứng với từng hàng của ma trận:

                     (*  Đọc vào giá trị của ma trận A theo từng hàng *)

For  I := 1  To  N  Do

Begin

Write (‘ Hang ‘, I, ‘ : ‘ ) ;

Readln ( A [ I, 1 ], A [ I, 2 ], A [ I, 3 ] ) ;

End ;

             Cách làm này không cho dùng vòng For mà ta phải ghi trực tiếp các phần tử cần đọc vào thủ tục Readln.

             Một cách khác lười hơn đỡ phải đọc ma trận trong khi thử, hãy làm một đoạn chương trình tạo số ngẫu nhiên cho các phần tử của ma trận. Bạn cần nhớ lại hoặc tra cứu hàm Random và Randomize.

      Mảng có thể dùng làm tham số cho chương trình con và mảng không bao giờ dùng làm kết quả của Function . Tuy nhiên cần lưu ý khai báo kiểu của tham số trong vùng khai báo Type chứ không định nghĩa trực tiếp ngay trong phần khai báo tham số của chương trình con.

             Ví du:

Cộng hai ma trận  C = A + B

Type MT = Array [ 1.. 3, 1.. 5 ]  Of  Real ;

Var  X, Y, Z : MT ;

(* —————————————————– *)

Procedure Cong_ma_tran ( A, B : MT ; Var  C : MT ) ;

Var   I, J  : Integer ;

Begin

For  I := 1  To  N  Do

For  J := 1  To  N  Do

C [ I, J ] := A [ I, J ] + B [ I, J ] ;

End ;

(* —————————————————–*)

BEGIN

……………..

Cong_ma_tran ( X, Y, Z ) ;

……………..

END.

BÀI TẬP MẪU

Bài tập 1:    Viết chương trình tìm giá trị lớn nhất của một mảng chứa các số nguyên gồm N phần tử.

Ý tưởng:

– Cho số lớn nhất là số đầu tiên: Max:=a[1].

– Duyệt qua các phần tử a[i], với i chạy từ 2 tới N: Nếu a[i]>Max thì thay Max:=a[i];

Uses Crt;

Type Mang = ARRAY[1..50] Of Integer;

Var    A:Mang;

N,i,Max:Integer;

Begin

{Nhập mảng}

Write(‘Nhap N=’); Readln(N);

For i:=1 To N Do

Begin

Write(‘A[‘,i,’]=’); Readln(A[i]);

End;

{Tìm phần tử lớn nhất}

Max:=A[1];

For i:=2 To N Do

If Max<A[i] Then Max:=A[i];

{In kết quả ra màn hình}

Writeln(‘Phan tu lon nhat cua mang: ’, Max);

Readln;

End.

BÀI TẬP TỰ GIẢI

Bài tập 1:    Viết chương trình tính tổng bình phương của các số âm trong một mảng gồm N phần tử.

Ý tưởng:

Duyệt qua tất cả các phần tử A[i] trong mảng: Nếu A[i]<0 thì cộng dồn (A[i])² vào biến S.

Bài tập 2: Viết chương trình nhập vào một mảng gồm N số nguyên. Sắp xếp lại mảng theo thứ tự tăng dần và in kết quả ra màn hình.

Ý tưởng:

Cho biến i chạy từ 1 đến N-1, đồng thời cho biến j chạy từ i+1 đến N: Nếu A[i]>A[j] thì đổi chổ A[i], A[j].

Bài tập 3: Viết chương trình nhập vào một mảng A gồm N số nguyên và nhập thêm vào một số nguyên X. Hãy kiểm tra xem phần tử X có trong mảng A hay không?

Ý tưởng:

Dùng thuật toán tìm kiếm tuần tự. So sánh x với từng phần tử của mảng A. Thuật toán dừng lại khi x=A[i] hoặc i>N.

Nếu x=A[i] thì vị trí cần tìm là i, ngược lại thì kết quả tìm là 0 (không tìm thấy).

Bài tập 4: Giả sử mảng A đã được sắp xếp theo thứ tự tăng dần. Viết hàm để kiểm tra xem phần tử X có trong mảng A hay không?

Ý tưởng:

So sánh x với phần tử ở giữa mảng A[giua]. Nếu x=A[giua] thì dừng (vị trí cần tìm là chỉ số của phần tử giữa của mảng). Ngược lại, nếu  x>A[giua] thì tìm ở đoạn sau của mảng [giua+1,cuoi], ngược lại thì tìm ở đoạn đầu của mảng [dau,giua-1].