Dữ liệu có cấu trúc - Phần 2: Tập hợp (Set) trong 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 2: Tập hợp (Set) trong Pascal trong Pascal

Dữ liệu có cấu trúc - Phần 2: Tập hợp (Set) trong Pascal

I – Khái niệm và định nghĩa

1. Kiểu tập hợp:

Một tập hợp bao gồm một số các đối tượng nào đó có cùng bản chất. Trong Pascal điều đó có nghĩa là có cùng một mô tả kiểu, kiểu này được gọi là kiểu cơ bản. Kiểu cơ bản bắt buộc phải là một kiểu vô hướng hay một đoạn con và không được là số thực. Các đối tượng này được gọi là phần tử của tập. Số phần tử cực đại cho phép có thể còn tùy thuộc vào chương trình dịch Pascal của các hãng khác nhau. Ví dụ trong Turbo Pascal và IBM Pascal số này là 256. Khái niệm tập hợp trong ngôn ngữ Pascal gắn liền với khái niệm tập hợp trong toán học.​

Để mô tả kiểu và khai báo biến kiểu tập hợp người ta dùng từ khóa SET OF theo sau là kiểu cơ bản T (kiểu của các phần tử của tập hợp).


Ví dụ:

Code:

Type

  Chu_Cai = Set Of Char ; (* Chữ cái *)

  Chu_So = Set Of 0.. 9 ; (* Chữ số *)

  Ngay = ( Hai, Ba, Tu, Nam, Sau, Bay, ChuNhat ) ;

   So_N = 0.. 320 ;

  Kieu_Xe_Dap = ( ThongNhat, Eska, Mifa, Peugeot ) ;

Var

  A, B, C : Set Of So_N ;

  Xe : Set Of Kieu_Xe_Dap ;

  L : Set Of Chu_Cai ;

  Ch : Char ;  (* Char : Tập hợp được định nghĩa trước *)

  Ngay_trong_tuan : Set Of Ngay ;

2. Xác lập một tập:

Một tập hợp được xác lập bằng cách liệt kê các phần tử của tập hợp, chúng cách nhau bằng dấu phẩy và được đặt giữa hai ngoặc vuông. Ví dụ với các biến đã được khai báo ở trên, ta có thể viết các tập :

[ ] ; (* Tập rỗng, không có phần tử *)

[ 3.. 5 ] ; (* Tập các chữ số 3, 4, 5 *)

[ 3, 4, 5, 8 ] ; hoặc [ 3.. 5, 8 ] ;

[ 'A'.. 'C', 'Y', 'Z' ] ;

[ Hai.. Tu, ChuNhat ] ;(* Tập một số ngày trong tuần *0​

Bản thân các phần tử của tập hợp cũng có thể cho bằng biến hoặc bằng biểu thức :

[ X + Y, I * J, 3, 4 ]​

biểu diễn tập hợp các số nguyên gồm số 3, số 4 và các số nguyên nhận được qua biểu thức X + Y và I * J (với X, Y, I, J là các số nguyên).

II – Các phép toán trên tập

1. Phép gán:

Các giá trị có được từ các biểu thức xác lập một tập hợp và kiểu cơ bản của chúng đương nhiên phải là giống nhau

Ví dụ : Với mô tả và khai báo ở trên ta có thể viết các câu lệnh :

Code:

A := [ 3.. 5 ] ;

B := [ 4.. 6, 10, 123 ] ;

L := [ 'A', 'B', 'D' ] ;

L := [ 'A'.. 'D', 'M', 'P ' ] ;

Ngay_trong_tuan := [ Ba, Sau ] ;

L := [ ] ;

Tập rỗng có thể đem gán cho mọi biến kiểu tập hợp khác nhau.

Chúng ta không thể gán L := [ 3, 5 ]; vì kiểu cơ bản của chúng không tương thích với nhau.

2. Phép hợp:

Được kí hiệu bằng dấu +.

Hợp của hai tập và một tập có các phần tử thuộc hai tập.


Ví dụ :

Code:

A := [ 3.. 5 ] ;

B := [4..6, 10, 123] ;

C := A + B ; (* Tập C sẽ là [ 3..6, 10, 123] *)

3. Phép giao:

Được kí hiệu bằng dấu*.

Giao của hai tập là một tập có các phần tử nằm chung của cả hai tập.


Ví dụ :

Code:

C := A * B ;  (* Tập C sẽ là [ 4,5] *)

4. Phép hiệu:

Được kí hiệu bằng dấu -.

Hiệu của hai tập là một tập có các phần tử thuộc tập thứ nhất nhưng không thuộc tập thứ hai.


Ví dụ :

Code:

C := A - B ; (* Tập C sẽ là [ 3 ] *)

C := B - A ; (* Tập C sẽ là [6,10,123] *)

5. Phép thử "thuộc về":

Là một phép thử để xem một biến hay một giá trị có thuộc một tập nào đó không. Kết quả của phép "thuộc về" có kiểu là Boolean. Phép thử này được dùng với từ khóa IN.​

Ví dụ : Để thử xem biến Ch ( kiểu char ) cónằm trong câu trả lời “Có” bằng tiếng Việt và “Yes” bằng tiếng Anh hay không, bằng cách thử thông thường ta viết :

Code:

Readln (Ch) ;

If ( Ch = 'Y' ) or ( Ch = 'y' ) or ( Ch = 'C' ) or ( Ch = 'c' ) Then ...

Song ta có thể viết gọn lại với phép thử In như sau :

Code:

If Ch In [ 'Y', 'y ', 'C ', 'c' ] Then...

Hoặc nếu dùng một biến A ( kiểu tập )

Code:

A := ['Y ','y ', 'C', 'c' ] ;

If Ch In A Then ...

6. Các phép so sánh <>, =, <= và >= :

Hai tập được đem ra so sánh bằng các phép toán so sánh này trước hết phải có cùng kiểu cơ bản. Kết quả của các phép so sánh này là giá trị kiểu Boolean, tức là đúng ( True ) hoặc Sai ( False ).

Hai tập là bằng nhau nếu chúng có các phần tử như nhau từng đôi một ( không kể thứ tự sắp xếp các phần tử trong hai tập ). Ngược lại với phép = là phép so sánh khác nhau <>.​

Ví dụ :

Code:

 A := [ 3, 5, 9 ] ;

B := [ 9, 3, 5 ] ;

If A = B Then Writeln ('Hai tap A và B bang nhau ') ;

If A<>B Then Writeln (' Tap A khac tap B ') ;/[code]

[INDENT] Phép so sánh <= sẽ có giá trị là True nếu tất cả các phần tử tập thứ nhất đều thuộc tập thứ hai.

Phép so sánh >= sẽ có giá trị là True nếu tất cả các phần tử tập thứ hai đều thuộc tập thứ nhất.[/INDENT]

* Cần lưu ý là trong Pascal không tồn tại phép so sánh nhỏ hơn < và lớn hơn >. Muốn so sánh lớn hơn hay nhỏ hơn ta có thể dùng thủ thuật sau :

[code]If ( A<=B ) and ( A<>B ) Then Writeln('A < B') ;

Để thử xem hai tập A và B có phần tử nào chung không ta dùng phép thử :

Code:

If A * B = [ ] Then Writeln ('A va B khong co phan tu chung ') ;

​

III – Ghi và đọc dữ liệu kiểu tập

Lệnh Read và Write không cho phép đọc và ghi trực tiếp dữ liệu kiểu tập hợp. Song ta có thể lập chương trình thực hiện các thao tác này khi mà kiểu cơ bản của tập hợp là số nguyên, kí tự.​

Ví dụ:Đọc vào N kí tự để xây dựng một tập các kí tự Alpha nghĩ a là xáx định xem trong N số kí tự được đưa vào ( không kể số lần gõ ) sau đó in ra kết quả.

Code:

Type 

  Chu_Hoa = Set Of 'A'.. 'Z' ;

Var

Alpha, Beta : Chu_Hoa ;

I, N : integer ;

Ch : char ;

BEGIN

Alpha := [ ] ;

Write (' Enter N : ') ;

Readln (N) ;

For I := 1 To N Do

Begin

  Readln ( Ch ) ;

  Ch := Upcase (Ch) ; (* Đổi chữ cái nhỏ thành lớn *)

  Alpha := Alpha + [Ch] ;

End ;

(* In ra các phần tử có trong tập Alpha *)

Writeln (' Cac chu cai co trong tap Alpha la : ') ;

For Ch :='A' To 'Z' Do

   If Ch IN Alpha Then Writeln(Ch) ;

END.

Kết quả chạy chương trình như sau :

Với N = 4, bạn gõ vào các kí tự theo thứ tự sau : 'a', 'c', 'A', 'a'

Enter N : 4

a

c

A

a



Cac chu cai co trong tap Alpha la :



A

C

Giả sử ta đã biết số phần tử của tập Alpha. Khi này ta có thể in ra các phần tử của tập Alpha một cách có hiệu quả hơn vì nếu chúng ta biết được số phần tử của tập thì sẽ tránh được việc rà soát cả tập từ 'A' đến 'Z' ngay cả khi tập là rỗng hoặc chỉ chứa chữ 'B'.​

Code:

I := 0 ; ch :='A' ;

While I < So_phan_tu> Do

Begin

  If Ch IN Alpha Then

  Begin

  I := I +1 ;

  Writeln (Ch) ;

  End ;

  Ch := Succ(Ch) ;

End ;

Cách thứ hai là dùng vòng lặp While. Tập Beta đựoc dùng để tránh cho tập Alpha không bị phá hủy vì trong vòng lặp ta có dùng phép hiệu :

Code:

BEGIN

  Beta := Alpha ;

  Ch := 'A' ;

  While Beta <> [ ] Do

  Begin

  If Ch IN Beta Then Writeln (Ch) ;

  Beta :=Beta - [Ch] ;

  Ch := Succ(Ch) ;

  End ;