Bài giảng Ngôn ngữ lập trình Pascal: Chương 12 - Cấu trúc dữ liệu - Kiểu tập hợp

Bài giảng Ngôn ngữ lập trình Pascal: Chương 12 - Cấu trúc dữ liệu - Kiểu tập hợp bao gồm những nội dung về kiểu tập hợp, các phép toán trên tập, ghi và đọc dữ liệu kiểu tập. Bài giảng phục vụ cho các bạn chuyên ngành Công nghệ thông tin và những bạn quan tâm tới lĩnh vực này.
Nội dung trích xuất từ tài liệu:
Bài giảng Ngôn ngữ lập trình Pascal: Chương 12 - Cấu trúc dữ liệu - Kiểu tập hợp 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.1Kiể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.2TYPE 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.3Các phép toán trên tập1/ 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.42/ 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.55/ 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.66/ 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 < và >. Muốn so sánh lớn hơn hay nhỏ hơn: IF (AGhi 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.8TYPE 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.9Thí dụ ứng dụng: Tính các số nguyên tố Sàng EratosthèneThuậ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.10PROGRAM 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.11REPEAT WHILE not (Number IN Sang) DO Number := Number + 1; Nguyen_To := Nguyen_To + [Number]; Write(Number, ); I := Number; WHILE I