Cơ sở dữ liệu - Chương 12: Cấu trúc dữ liệu: kiểu tập hợp

12.1 Chương 12 Cấu trúc dữ liệu: kiểu tập hợp  Kiểu dữ liệu có cấu trúc: ARRAY, SET, RECORD, FILE 12.2 Kiểu tập hợp • Một tập hợp gồm một số các đối tượng có cùng bản chất, nghĩa là có cùng một mô tả kiểu (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à các phần tử của tập. • Số phần tử cực đại cho phép: 256 • Gắn liền với khái niệm tập hợp trong toán học. 12.3 TYPE Chu_Cai = SET OF CHAR; (* Chữ cái *) Chu_So = SET OF 0..9; (* Chữ số *) Ngay = (Hai, Ba, Tư, 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 : Chu_Cai; CH: CHAR;(* CHAR: đã được định nghĩa trước *) Ngay_Trong_Tuan : SET OF Ngay; 12.4 Các phép toán trên tập 1/ Phép gán Với mô tả và khai báo ở trên ta có thể viết: 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: không có phần tử } * Tập rỗng có thể đem gán cho mọi biến kiểu tập hợp. * Không thể gán L:=[3, 5]; vì kiểu cơ bản của chúng không tương thích 12.5 2/ Phép hợp + là tập có các phần tử thuộc hai tập. A:= [3..5]; B:= [4..6, 10, 123]; C:= A + B; { Tập C sẽ là [3..6, 10, 123] } 3/ Phép giao * là một tập có các phần tử nằm chung cả hai tập. C:= A * B; { Tập C sẽ là [4, 5] } 4/ Phép hiệu - là một tập có các phần tử thuộc tập thứ nhất nhưng không có trong tập thứ hai. C:= A - B; { Tập C sẽ là [3] } C:= B - A; { Tập C sẽ là [6, 10, 123] } 12.6 5/ Phép thử "thuộc về" với IN 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ó kiểu là Boolean. Thông thường ta viết: 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: IF Ch IN ['Y', 'y', 'C', 'c'] then ... 12.7 6/ Các phép so sánh , =, =  Hai tập phải có cùng kiểu cơ bản  Kết quả là kiểu Boolean A:=[3, 5, 9]; B:=[9, 3, 5]; IF A=B THEN writeln('A va B bang nhau!'); IF A B THEN writeln('Tap A khac tap B !');  Không tồn tại . Muốn so sánh lớn hơn hay nhỏ hơn: IF (AB) THEN Writeln(' A < B ');  IF A*B=[]THEN writeln('không có phần tử chung'); 12.8 Ghi và đọc dữ liệu kiểu tập • Lệnh Read và Write không cho phép đọc và viết 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 kiểu cơ bản của tập hợp là số nguyên, kí tự. 12.9 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); Alpha := Alpha + [Ch]; End; Writeln(' Các chữ trong tập Alpha là :'); FOR Ch:='A' TO 'Z' DO IF Ch in Alpha THEN Writeln(Ch); END. ? Nếu gõ vào a, c, A, a thì tập = 12.10 Thí dụ ứng dụng: Tính các số nguyên tố Sàng Eratosthène Thuật toán:  Lấy tập ban đầu là 1..N  Mỗi lần gặp một số nguyên tố, ta loại ra khỏi tập này tất cả các số là bội của số nguyên tố này.  Eratosthène viết các số trên đất và dùng que chọc các số bị loại ra. 12.11 PROGRAM Sang_Erathostene; {Sàng Erathostène} CONST N = 100; TYPE Nguyen = 1..N; VAR Nguyen_To, Sang: SET OF Nguyen; Number: Nguyen; I: Integer; BEGIN Nguyen_To:=[]; {chứa các số n/tố được sàng ra } Sang := [2..N]; {Cái sàng } Number := 2; 12.12 REPEAT WHILE not (Number IN Sang) DO Number := Number + 1; Nguyen_To := Nguyen_To + [Number]; Write(Number, ' '); I := Number; WHILE I <= N DO BEGIN Sang := Sang - [I]; I := I + Number; END; UNTIL Sang=[]; END.