Dữ liệu có cấu trúc - Phần 1: Mảng (Pascal)

Xin chào các bạn, Hôm nay WIKIPASCAL sẽ hướng dẫn các bạn về Dữ liệu có cấu trúc - Phần 1: Mảng (Pascal) trong Pascal
Du lieu co cau truc - Phần 1: Mang trong Pascal
Dữ liệu có cấu trúc - Phần 1: Mảng (Pascal)

I – Kiểu dữ liệu có cấu trúc (mảng Array)

1. Khái niệm chung về cấu trúc dữ liệu :

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. TrongPascal 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 :​


Code:
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 :

Code:
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 :

Code:
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 :

Code:
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 :

Code:
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 :​

Code:
 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ư :

Code:
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í dụ 1:

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 :

Code:
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 :

Code:
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í dụ 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 ) :


Code:
For I := 1 To 10 Do 

  C[ I ]:=A[ I ] + B[ I ] ;
Ví dụ 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

Code:
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

II – Sắp xếp mảng


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.​



Code:
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

III – Mảng nhiều chiều


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í dụ:


Code:
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 :

Code:
 Var

  MPT : Array [ 1.. 3 ] Of Array [ 1.. 5 ] Of Real ;
hoặc thường được viết gọn lại :

Code:
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 [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í dụ:


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 :

Code:
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 *)


Code:
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í dụ:

Cộng hai ma trận C = A + B
Code:
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 : 
1. Viết chương trình nhập vào một mảng gồm 10 số nguyên. Tìm và in phần tử lớn nhất ra màn hình. (Áp dụng cả vòng lặp vào chương trình)
2.Viết chương trình nhập vào một mảng gồm 5 số nguyên. Sắp xếp lại các phần tử theo thứ tự từ bé đến lớn.

Nhận xét

Bài đăng phổ biến từ blog này