›
›

Giáo trình Ngôn ngữ lập trình Pascal - Lê Mạnh Thạnh (Phần 2)

pdf 64 trang hapham 2200
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Ngôn ngữ lập trình Pascal - Lê Mạnh Thạnh (Phần 2)", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfgiao_trinh_ngon_ngu_lap_trinh_pascal_le_manh_thanh_phan_2.pdf

Nội dung text: Giáo trình Ngôn ngữ lập trình Pascal - Lê Mạnh Thạnh (Phần 2)

  1. Ch−ơng 6 Kiểu tập hợp và kiểu mảng 6.1. Kiểu tập hợp (Set Type) 6.1.1. Định nghĩa – Dữ liệu kiểu tập hợp là một tập hợp của những dữ liệu cùng thuộc một kiểu vô h−ớng đếm đ−ợc (kiểu cơ sở của kiểu tập hợp). – Một kiểu tập hợp đ−ợc định nghĩa bởi dạng sau: TYPE = SET OF ; trong đó là tên của kiểu dữ liệu cần định nghĩa là tên hoặc là định nghĩa một kiểu dữ liệu nào đó gọi là kiểu cơ sở. Ví dụ 1. Sau đây là các ví dụ về định nghĩa kiểu dữ liệu tập hợp và mô tả biến thuộc kiểu dữ liệu đó: Type Chu_so = Set Of 0 9 ; Chu_cai_lon = Set Of ‘A’ ’Z’; Var So: chu_so; Chu : Chu_cai_lon; Mau : Set Of (Xanh, Vang, Tim); – Nếu là kiểu nguyên thì giá trị cần phải nằm trong đoạn 0 đến 255. – Hằng kiểu tập hợp đ−ợc biểu diễn d−ới dạng liệt kê các phần tử nằm trong 2 dấu ngoặc vuông [ ]. Chẳng hạn, [‘A’,‘D’,‘E’] , [3, 5 , . . , 9] là các hằng kiểu tập hợp. – Hằng tập hợp rỗng đ−ợc kí hiệu bởi [ ]. – Biến tập hợp cho phép có từ 0 đến 255 phần tử. Có thể sử dụng phép gán đối với các biến kiểu tập hợp. Chẳng hạn, chúng ta có các phép gán sau đây: so:=[1,2,7]; Chu:= [ ]; Mau:= [Vang,Tim,Xanh]; 52
  2. 6.1.2. Các phép toán trên tập hợp a. Phép toán quan hệ – Phép toán = (bằng) cho giá trị true nếu 2 tập hợp bằng nhau. – Phép toán = (lớn hơn hoặc bằng): A>=B cho giá trị true nếu B là tập con của A. Chú ý. Để kiểm tra tập hợp A có thật sự nằm trong tập hợp B hay không ta sử dụng phép toán AND nh− trong câu lệnh sau đây: if (A<>B) AND (A<=B) then Write (‘A la tap hop con thuc su cua B’); b. Phép toán IN – Dùng để xét xem một phần tử nào đó có nằm trong tập hợp không? Nếu phần tử đó có trong tập hợp thì phép toán sẽ trả về giá trị True, ng−ợc lại trả về giá trị False. Ví dụ 2. ‘C’ In [‘A’,’C’,’D’] cho giá trị True. ‘E’ In [‘A’,’C’,’D’] cho giá trị False. c. Các phép toán hợp, giao, hiệu Gọi A,B là hai dữ liệu cùng kiểu tập hợp – A+B là hợp của A và B (tập hợp các phần tử thuộc A và thuộc B). – A*B là giao của A và B (tập hợp các phần tử thuộc và thuộc B). – A-B là hiệu của A và B (tập hợp các phần tử thuộc A và không thuộc B). Chẳng hạn, nếu A=[1,3,9], B=[9,2,5] thì A+B có giá trị là [1,2,3,5,9], A*B có giá trị là [9], A- B có giá trị là [1,3]. Ví dụ 3. Ch−ơng trình d−ới đây nhập vào một chữ cái và xác định xem chữ cái đó là nguyên âm hay phụ âm? Use Crt; Var Chucai, nguyenam: Set of Char; Ch: char; Begin Chucai:=[‘A’ ’Z’, ‘a’, ’z’]; nguyenam:=[‘A’,’E’,’I’,’O’,’U’]; 53
  3. Repeat Clrscr; Write(‘Nhap mot chu cai:’); readln (ch); Until ch In chucai; If Upcase(Ch) In Nguyenam Then Writeln(Ch,’La Nguyen am’) Else Writeln (Ch, ‘La Phu am’); Readln; End. 6.2. Kiểu mảng (Array Type) 6.2.1. Khái niệm kiểu mảng (Array) Mảng là một kiểu cấu trúc dữ liệu đ−ợc dùng để l−u trữ nhiều phần tử dữ liệu cùng kiểu cùng tính chất nào đó trong cùng một tên chung. Các thành phần của mảng đ−ợc xác định thông qua truy xuất các chỉ số của nó. Chẳng hạn, mảng a một chiều gồm 5 phần tử đ−ợc phân bố nh− sau: a[1] a[2] a[3] a[4] a[5] Mảng cũng có thể có nhiều chiều, có nghĩa là mỗi một phần tử của mảng đ−ợc xác định bởi một bộ nhiều hơn một chỉ số. Chẳng hạn, để l−u trữ các mảng n hàng, m cột ta có thể sử dụng mảng hai chiều a có nìm phần tử. Phần tử ở dòng i cột j của bảng là a[i,j]. 6.2.2. Khai báo mảng một chiều Dạng định nghĩa kiểu mảng: TYPE = ARRAY [ ] OF ; trong đó là một tên định nghĩa kiểu mảng, là một kiểu vô h−ớng đếm đ−ợc có hữu hạn phần tử, là kiểu dữ liệu của các phần tử của mảng. Để khai báo biến kiểu mảng ta có thể sử dụng một trong hai cách: • Cách 1. VAR : ; • Cách 2. VAR : ARRAY[ ] OF ; trong đó là một tên đ−ợc dùng để đặt cho mảng cần khai báo. 54
  4. Ví dụ 4. ta có thể định nghĩa một mảng 20 phần tử thuộc kiểu Real, có chỉ số chạy từ 20 đến 39 nh− sau: Type DAY_THUC = Array[20 39] Of Real; Khi đó để A, B là các mảng thuộc kiểu mảng trên ta cần khai báo: Var A,B : DAY_THUC; Ta có thể thay khai báo này bằng khai báo trực tiếp: Var A,B: Array [20 39] Of Real; Chú ý. – Việc truy nhập vào một phần tử nào đó của biến mảng đ−ợc thực hiện qua tên biến mảng, theo sau là giá trị chỉ số để trong dấu [ ]. – Có thể gán một mảng cho một biến mảng khác cùng kiểu. Chẳng hạn, ta có thể thực hiện phép gán A:=B (nghĩa là, A[20]:=B[20], A[21]:=B[21], , A[39]:=B[39]). 6.2.3. Một số ví dụ sử dụng mảng a. Nhập xuất giá trị cho một mảng Các thủ tục nhập xuất biến nh−: Writeln, Readln, không thể truy xuất thẳng biến mảng mà phải truy xuất từng thành phần nó. Ví dụ 5. Ch−ơng trình d−ới đây nhập vào từ bàn phím một dãy số nguyên M và xuất ra màn hình theo thứ tự ng−ợc lại. Program Day_so_nguyen; Use Crt; Const Max=100; Var M : Array [1 Max] of Integer; i,n: Byte; Begin Clrscr; Repeat Write (‘Cho biet so phan tu (< ’, Max, ‘): ’); Readln (n); Until n<= Max; For i:=1 to n Do Begin 55
  5. Write (‘phan tu thu’ , i ‘la: ’); Readln (M[i]); End; Writeln (‘ ‘); Writeln (‘In dau theo thu tu nguoc lai:’); For i:=n downto 1 do Write (M[i]#32); Writeln; Writeln(In cac doi so của day:’); For i:=1 to n do Write (-M[i],#32); Readln; End. b. Ví dụ sắp xếp các phần tử trong mảng Ch−ơng trình sau đây thực hiện việc đọc vào một dãy số và sắp xếp lại nó theo thứ tự tăng. Program săp_xep; Var A: array [1 100] of Real; i, j, n : Byte; T:real; Begin Write (‘Dua vao so phan tu cua day: ‘); readln(n); For i:=1 to n do Begin Write(‘a[‘, i, ’] = ‘); readln(a[i]) end; For i:=n downto 2 do For j:=1 to i-1 do If A[j]>A[j+1] then Begin T:= A[j]; A[j]:=A[j+1] ; A[j+1]:=T End; For j:=1 to n do Writeln(A[j],#32) End. 6.2.4. Mảng nhiều chiều Phần sau đây chủ yếu trình bày mảng hai chiều. Các mảng nhiều hơn hai chiều đ−ợc suy diễn lên một cách tự nhiên. 56
  6. Khai bao mảng hai chiều : Khai báo mảng hai chiều cũng t−ơng tự nh− mảng một chiều, chỉ có điều có hai tập chỉ số cách nhau bởi dấu phẩy (,). Dạng định nghĩa kiểu: TYPE =ARRAY[ , ] OF ; trong đó và là các kiểu vô h−ớng đếm đ−ợc hữu hạn phần tử. Đây là các giá trị mà các chỉ số của các phần tử của mảng có thể nhận đ−ợc. Khai báo các biến của mảng nhiều chiều t−ơng tự nh− khai báo các biến mảng hai chiều. Ví dụ 6. Ta có thể định nghĩa kiểu mảng 2 chiều Type M_2C=Array [1 4,’A’ ’D’] Of Integer; Khi đó mảng A với kiểu dữ liệu M_2C có thể khai báo qua tên: Var A : M_2C; hay khai báo trực tiếp: A: Array [1 4,’A’ ’D’] Of Integer; Câu hỏi – Bài tập Ch−ơng 6 1. Viết ch−ơng trình nhập vào một dãy số và xuất ra màn hình các thông tin sau: a) Phần tử lớn nhất của dãy, b) Phần tử nhỏ nhất của dãy, c) Tổng các phần tử của dãy, 2. Viết trong cùng một ch−ơng trình thực hiện các yêu cầu sau: a) Nhập vào từ bàn phím một dãy số nguyên M có 10 phần tử và một số nguyên x thoả mãn tính chất : chữ số tận cùng của x bằng 6 và –180≤x≤1200. b) Xuất ra màn hình số phần tử trong dãy M thoả mãn tính chất : có hai chữ số và chia đúng cho x. c) Tính tích của các phần tử M[i] thoả mãn tính chất: 10<M[i]<20. 3. Viết ch−ơng trình đổi số nguyên d−ơng từ hệ có số 10 sang hệ cơ số 2. 57
  7. 4. Viết ch−ơng trình tính điểm trung bình, xếp loại cho các học sinh trong một lớp với 2 môn thi là Văn, Toán và các thông tin thống kê sau: – Số l−ợng các học sinh đ−ợc xếp loại giỏi, khá, trung bình, yếu. Tỉ lệ phần trăm t−ơng ứng. – Số l−ợng học sinh d−ới điểm trung bình môn Văn, Toán. Tỉ lệ phần trăm t−ơng ứng. 5. Viết ph−ơng trình nhập vào từ bàn phím một dãy B có 10 phần tử và một số x. Dò tìm xem trong dãy có hai phần tử liên tiếp nào mà tổng của chúng bằng x không ? 6. Viết ch−ơng trình nhập vào từ bàn phím một dãy số nguyên và xuất ra màn hình tần suất (số lần xuất hiện) của các số trong dãy số đó. 7. Viết ch−ơng trình tạo và in ra trên màn hình ma trận đơn vị cấp 10. 8. Viết ch−ơng trình nhập vào từ bàn phím một ma trận vuông và xuất ra màn hình tổng các phần tử trên đ−ờng chéo chính. 9. Viết ch−ơng trình nhập vào từ bàn phím giá trị l−ợng m−a trung bình của 12 tháng trong năm. In ra màn hình biểu đồ cột đứng biểu thị l−ợng m−a từng tháng (sử dụng ký tự #219). 10. Viết ch−ơng trình nhập vào một chuỗi rồi tách ra các nguyên âm và phụ âm của chuỗi đó. 11 Viết ch−ơng trình nhập vào 2 xâu rồi in ra màn hình các kí tự xuất hiện trong cả 2 xâu. 12. Viết ch−ơng trình nhập vào các kí tự cho đến khi nào gặp dấu ! thì kết thúc. Hãy in ra kết quả. a) Số lần xuất hiện của mỗi chuỗi loại kí tự Alphabet. b) Tổng số các chữ cái đ−ợc nhập vào. c) Số kí tự nhập vào không phải là Alphabet. 13. Viết ch−ơng trình in ra màn hình 100 số ngẫu nhiên từ 1 dến 100 sao cho không có 2 số nào trùng nhau. 14. Viết ch−ơng trình in ra màn hình tập hợp các từ có trong một xâu kí tự. 58
  8. Ch−ơng 7 Ch−ơng trình con 7.1. Khái niệm về ch−ơng trình con Khi lập trình th−ờng gặp những đoạn ch−ơng trình cùng giải quyết một công việc giống nhau ở nhiều chỗ khác nhau. Để ngắn gọn và dễ sửa đổi ch−ơng trình ng−ời ta thay thế việc lập những đoạn ch−ơng trình này thành một ch−ơng trình con, sau đó chỉ cần gọi tên ch−ơng trình con thay cho việc lặp lại cả đoạn ch−ơng trình. Chẳng hạn, có thể xây dựng ch−ơng trình con có tên MAX với hai tham số a, b để tính chọn giá trị lớn nhất trong hai số a, b sau đó mỗi khi cần tính giá trị lớn nhất của hai số x,y nào đó trong ch−ơng trình ta chỉ cần gọi ch−ơng trình con MAX(x,y). Một ứng dụng khác của ch−ơng trình con là phát triển các ch−ơng trình lớn. Khi đó có thể chia nhỏ công việc thành nhiều ch−ơng trình con riêng biệt (Module). Các lập trình viên có thể làm việc độc lập với nhau, ng−ời quản lí chung chỉ cần tập hợp và sử dụng các ch−ơng trình con để phát triển ch−ơng trình chính. Ph−ơng pháp này cho phép nhìn nhận và giải quyết vấn đề một cách tổng quát, không bị sa vào các chi tiết nhỏ. Trong Pascal có hai loại ch−ơng trình con : Ch−ơng trình con thủ tục và ch−ơng trình con hàm. 7.1.1. Ch−ơng trình con hàm a. Dạng tổng quát của khai báo hàm FUNCTION ( ) : ; ; Begin End; trong đó: – là một tên dùng để kí hiệu hàm. Kết quả thực hiện hàm giá trị l−u trong . – là một dãy các tên biến cùng với mô tả kiểu của nó. Các biến này đ−ợc gọi là tham số hình thức của ch−ơng trình con. Trong các biến đ−ợc khai báo kiểu bằng hai cách: + Cách 1 : : . Các biến trong danh sách biến đ−ợc gọi là các tham trị. + Cách 2 : Var : . Các biến trong danh sách biến đ−ợc gọi là các tham biến. 59
  9. là một tên kiểu dữ liệu hoặc định nghĩa kiểu dữ liệu, nó quy định kiểu dữ liệu cho kết quả. – là các khai báo thêm cho ch−ơng trình con nếu cần. Phần này th−ờng sử dụng để khai báo các biến không phải là tham số hình thức và chỉ đ−ợc sử dụng trong ch−ơng trình con (gọi là các biến cục bộ). – là một dãy các câu lệnh Pascal (có thể là lệnh ghép) để thực hiện việc tính giá trị cho mỗi khi có lời gọi hàm. Ví dụ 1. Sau đây là một ch−ơng trình con dạng hàm tính dùng để tính hàm tang: Function tg(x: Real): Real; Begin tg:=Sin(x)/Cos(x); End; b. Lời gọi hàm Hàm đ−ợc gọi nh− là một toán hạng trong biểu thức. Lời gọi hàm nh− sau: ( ); trong đó là một dãy các biểu thức t−ơng ứng với các biến trong . Nếu tham số hình thức là tham biến thì tham số thực sự t−ơng ứng phải là tên biến. Nếu tham số hình thức là tham trị thì tham số thực sự t−ơng ứng có thể là biểu thức. Ví dụ 2. Nh− hàm đã định nghĩa ở trên ta có thể có lời gọi: y:=tg(x*x+2); 7.1.2. Thủ tục a. Dạng tổng quát của khai báo thủ tục PROCEDURE ( ); ; Begin End; trong đó: – là một tên dùng để kí hiệu thủ tục. – là một dãy các tên biến cùng với mô tả kiểu của nó. Trong các biến đ−ợc khai báo kiểu dữ liệu của nó bằng hai cách nh− đối với ch−ơng trình con 60
  10. FUNCTION. ( ) có thể không có. – và đ−ợc xác định nh− đối với ch−ơng trình con FUNCTION. Ví dụ 3. Ch−ơng trình con MAX sau đây thực hiện việc tìm số lớn nhất trong 2 số nguyên cho tr−ớc. Procedure MAX(x,y:Real; Var z: Real); Begin If x>y then z:=x else z:=y; End; b. Lời gọi thủ tục Thủ tục đ−ợc gọi nh− là một lệnh đơn trong ch−ơng trình. Dạng gọi thủ tục nh− sau: (tham số thực sự>); trong đó là một dãy các biểu thức t−ơng ứng với các biến trong . Nếu tham số hình thức là tham biến thì tham số thực sự t−ơng ứng phải là tên biến. Nếu tham số hình thức là tham trị thì tham số thực sự t−ơng ứng có thể là biểu thức. Kết quả của lời gọi thủ tục là giá trị nhận đ−ợc ở các tham biến. Ví dụ 4. Lời gọi sau đây cho kết quả là giá trị lớn nhất giữa hai giá trị a*a+2 và b-1, với a, b là hai biến có giá trị đã đ−ợc xác định tr−ớc đó. Kết quả đ−ợc l−u trong tên biến c. MAX(a*a+2, b-1, c); Chú ý. – Các tham số có mặt trong và trong phải t−ơng ứng với nhau về số l−ợng tham số và kiểu dữ liệu. – Các biến trong ch−ơng trình có sử dụng ch−ơng trình con (tr−ớc từ khoá BEGIN) đ−ợc chia thành hai loại: + Biến toàn cục : đ−ợc khai báo ở ngoài ch−ơng trình con trong phần khai báo của ch−ơng trình chính. + Biến cục bộ : đ−ợc khai báo bên trong ch−ơng trình con và chỉ đ−ợc sử dụng bên trong ch−ơng trình con đó. – Các biến thực sự t−ơng ứng với tham trị sau khi ra khỏi ch−ơng trình con vẫn giữ nguyên giá trị tr−ớc khi vào ch−ơng trình con. Có nghĩa là giá trị của nó không bị thay đổi bởi các phép gán trong ch−ơng trình con. Ví dụ 5. Hai ch−ơng trình d−ới đây sẽ chỉ rõ sự khác nhau giữa tham biến và tham trị trong các ch−ơng trình con. ♦ Ch−ơng trình 1. Program Tham_tri; 61
  11. Var a,b,c: Integer; Procedure InTri(x,y,z : Integer); Begin x:=x*2; y:=y*2; z:=z*2; Writeln(‘Trong thu tuc ta co 3 so:’,x,#32,y,#32,z); End; Begin a:=10; b:=20; c:=30; Writeln (‘Truoc khi vao thu tuc ta co 3 so:’, a,#32,b,#32,c); Intri(a,b,c); Writeln (‘sau khi ra thu tuc ta co 3 so:’, a,#32,b,#32,c); End. Trong ví dụ này ta thấy a, b, c không thay đổi mặc dầu thủ tục InTri đã nhân x, y, z cho 2. ♦ Ch−ơng trình 2. Program Tham_bien; Var a,b,c: Integer; Procudure InTri(Var x,y,z : Integer); Begin x:=x*2; y:=y*2; z:=z*2; Writeln (‘Trong thutuc ta co 3 so:’,x,#32,y,#32,z); End; Begin a:=10; b:=20; c:=30; Writeln (‘Truoc khi vao thu tuc ta co 3 so:’,a,#32,b,#32,c); Intri(a,b,c); Writeln (‘sau khi ra thu tuc ta co 3 so :’,a,#32,b,#32,c); End. Trong ví dụ này khi thủ tục InTri nhân x, y, z với 2 thì biến toàn cục thay đổi. 7.2. Một số hàm và thủ tục của Turbo Pascal 7.2.1. Các thủ tục – CLRSCR: Thủ tục này có tác dụng xoá toàn bộ màn hình và đ−a con trỏ màn hình (cursor) về vị trí (1,1) trên màn hình. – CLREOL : Thủ tục này có tác dụng xoá từ vị trí con trỏ màn hình đến cuối dòng hiện hành trên màn hình. – INSLINE : Thủ tục này có tác dụng chèn dòng trống vào vị trí hiện hành của con trỏ màn hình trên màn hình. 62
  12. – DELLINE : Thủ tục này có tác dụng xoá dòng chứa con trỏ màn hình, các dòng sau sẽ đ−ợc chuyển lên một dòng. – TEXMODE( : Integer). Thủ tục này có tác dụng chọn chế độ trình bày văn bản. Tham số sẽ lấy giá trị: BW40=0; {40x25 B/W trên Color Adapter}, C40=1; {40x25 Color trên Color Adapter}, BW80=2; {80x25 B/W trên Color Adapter}, C80=3; {80x25 Color trên Color Adapter}, Mono=7; {80x25 trên Monochrome Adapter}, Font8x8=256; EGA và VGA: 43, 50 Line Mode. LastMode= -1. Khi khai báo TextMode (LastMode) ch−ơng trình tự động thử xem Mode màn hình tr−ớc đó và ấn định Mode đó cho ch−ơng trình. Điều này đặc biệt thuận lợi khi ta muốn ch−ơng trình chạy đ−ợc trên nhiều loại máy khác nhau. – WINDOW (x1,y1,x2,y2): Thủ tục này có tác dụng thiết lập một cửa sổ để trình bày. (x1,y1) là toạ độ góc trái phía trên của cửa sổ, (x2,y2) là toạ độ góc phải phía d−ới của cửa sổ. Cửa sổ mặc nhiên là Window(1,1,80,25). Thủ tục này ảnh h−ởng đến các lệnh trình bày dữ liệu trên màn hình ở chế độ văn bản. – GOTOXY(x,y) : Thủ tục này có tác dụng đ−a con trỏ màn hình đến tọa độ (x,y) : dòng y, cột x. – HIGHVIDEO : Thủ tục này cho phép hiển thị trên màn hình với độ chói cao. – LOWVIDEO : Thủ tục này cho phép hiển thị trên màn hình với độ chói thấp. – NORMVIDEO: Thủ tục này khôi phục thuộc tính màn hình, mặc định theo các thuộc tính đã hiện hữu ở vị trí con trỏ màn hình khi thực hiện ch−ơng trình. – SOUND(Hz) : Thủ tục này cho phép phát âm thanh có tần số Hz cho đến khi gặp thủ tục NoSound. – NOSOUND : Thủ tục này có tác dụng tắt loa phát âm thanh ở máy. – DELAY (ms) : Thủ tục này tạm treo ch−ơng trình trong thời gian ms mili giây. – TEXTCOLOR(color) : Thủ tục này chọn màu của kí tự trình bày trên màn hình. Color có giá trị từ 0 đến 255 – TEXTBACKGROUND(color). Thủ tục này chọn màu nền trong chế độ văn bản. 63
  13. Các hằng xác định màu nền và chữ: Black = 0 Brown = 6 LightRed = 12 Blue = 1 LighGray = 7 LightMagenta = 13 Green = 2 DarkGray = 8 Yellow = 14 Cyan = 3 LightBlue = 9 White = 15 Read = 4 LightGreen = 10 Magenta = 5 LightCyan = 11 Hằng xác định nhấp nháy: Blink = 128 Chú ý. Nếu muốn màu nền loang đều trên màn hình thì sau khi phát lệnh TextBackGround(color) thì đánh tiếp lệnh ClrScr. 7.2.2. Các hàm – KEYPRESSED : Hàm kiểm tra có nút nào đ−ợc nhấn trên bàn phím không. Nếu có cho giá trị True, nếu không cho giá trị False. – READKEY : Hàm đọc kí tự từ bàn phím (ký tự nhập không đ−ợc trình bày trên màn hình). Các nút trên bàn phím nh−: A, B, C, chỉ tạo một kí tự khi đ−ợc nhấn. Còn các nút chức năng F1, F2, Home, end, Alt, Ctrl, tạo hai kí tự khi đ−ợc nhấn, trong đó kí tự thứ nhất sẽ mang mã 0. Hàm ReadKey chỉ đọc đ−ợc kí tự thứ nhất (kết quả đều nh− nhau). Để sử dụng đ−ợc các nút này, trong lập trình ta sử dụng: Ch:= ReadKey; If Ch=#0 then Ch:= ReadKey; Nếu nhấn nút chức năng thì đọc tiếp kí tự còn lại trong bộ đệm của keyboard. 7.2.3. Thủ tục và hàm đệ quy Trong Pascal chuẩn cũng nh− trong Turbo Pascal đều cho phép gọi đệ quy trong các ch−ơng trình con thủ tục và hàm. Ch−ơng trình con (thủ tục hoặc hàm) là đệ quy nếu trong nó chứa lời gọi đến chính nó. Để thấy rõ hơn ta xét hai ch−ơng trình con sau đây: Ch−ơng trình con 1. Thủ tục đệ quy sau đây thực hiện việc in ra dãy các chữ số của một số tự nhiên theo thứ tự ng−ợc lại: Procedure In_so(n:word); Begin if n <>0 then begin write(n mod 10); In_so(n div 10) 64
  14. end End; Khi có lời gọi, chẳng hạn In_so(123) thì quá trình thực hiện sẽ nh− sau: – IN số 3 (theo lệnh write(123 mod 10). – Gọi thủ tục In_so(12) (theo lời gọi In_so(123 div 10)). – In số 2 (theo lệnh write(12 mod 10). – Gọi thủ tục In_so(1) (theo lời gọi In_so(12 div 10)). – In số 1 (theo lệnh write(1 mod 10). – Gọi thủ tục In_so(0) (theo lời gọi In_so(1 div 10)). Đến đây dừng vì n=0. Ch−ơng trình con 2. Ch−ơng trình con hàm sau đây thực hiện việc tính giai thừa của một số tự nhiên n. Function G_thua(var n:word): word Var GT: word; Begin If n=0 then G_thua:=1 else begin GT:=G_thua(n-1); G_thua:=n*GT end End; Khi đó lời gọi hàm, chẳng hạn A:=G_thua(4), quá trình thực hiện sẽ nh− sau: – A=4.G_thua(3)(G_thua:=4*GT mà GT:=G_thua(4-1)). – A=4. 3.G_thua(2)( G_thua:=3*GT mà GT:=G_thua(3-1)). – A=4. 3.2.G_thua(1)( G_thua:=2*GT mà GT:=G_thua(2-1)). – A=4. 3. 2. 1.G_thua(0)( G_thua:=1*GT mà GT:=G_thua(0)). → Cuối cùng A=4.3.2.1.1 = 4! Câu hỏi – Bài tập Ch−ơng 7 1. Viết ch−ơng trình tính tổng: 65
  15. 1! + 2! + 3! + +n! với n < 12 và đã đ−ợc nhập vào từ bàn phím. 2. Viết ch−ơng trình có các chức năng sau: – Tìm −ớc số chung lớn nhất của hai số nguyên. – Tìm bội số chung nhỏ nhất của hai số nguyên. – Tìm số bé nhất trong ba số. 3. Viết ch−ơng trình vẽ một đ−ờng thẳng đứng (bằng kí tự *) có chiều dài bằng 5 tại cột 4 và cho di chuyển đến cột 20. 4. Viết trong cùng một ch−ơng trình : – Khai báo một hàm tên là F nhằm mục đích đối chiếu số nguyên k có thoả mãn tính chất : số tận cùng của k là 6 và k chia hết cho 4 hay không? – Trong phần ch−ơng trình chính : Nhập vào một mảng số nguyên M gồm 8 phần tử từ bàn phím. Dùng hàm F đếm và in ra số phần tử trong mảng M thoả mãn tính chất : Chữ số tận cùng là 6 và chia hết cho 4. 5. Viết ch−ơng trình đọc vào một dãy số, xác định phần tử nhỏ nhất, lớn nhất và trung bình cộng của dãy số đó. Hãy sử dụng 4 ch−ơng trình con sau: DOC (đọc vào các phần tử của mảng), MAX (tìm giá trị lớn nhất của mảng), MIN (tìm giá trị nhỏ nhất của mảng) và TRUNGBINH (tìm giá trị trung bình cộng của mảng). 6. Tàu NT1 cứ k ngày cập bến cảng một lần, tàu NT2 cứ m ngày cập bến cảng một lần (k≠m). Viết ch−ơng trình nhập k và m từ bàn phím rồi tính xem nếu hai tàu cùng rời cảng thì sau thời gian ngắn nhất là bao nhiêu ngày chúng lại cùng cập cảng. Biết rằng ngày rời cảng luôn luôn cùng với ngày cập cảng. 7. Viết ch−ơng trình nhập từ bàn phím 2 ma trận vuông cấp 2 và xuất ra màn hình các kết quả sau: a) Ma trận tổng A + B. b) Ma trận hiệu A – B. c) Ma trận tích A * B. d) Ma trận chuyển vị của A. 8. Viết hàm Function NTo(n:word) : Boolean; để kiểm tra xem n có phải là số nguyên tố ? 9. Viết 2 hàm tìm Max, Min của 3 số thực. 10. Viết hàm LOWCASE(c: Char): Char để đổi chữ cái hoa C thành chữ th−ờng. 11. Viết thủ tục KHUNG(x1,y1,x2,y2:Integer) để vẽ một khung hình chữ nhật có đỉnh trên bên trái là (x1,y1) và đỉnh d−ới bên phải là (x2,y2). 12. Viết thủ tục FILL(x1,y1,x2,y2:Integer; ch:Char) để tô một vùng màn hình hình chữ nhật có đỉnh trên bên trái là (x1,y1) và đỉnh d−ới bên phải là (x2,y2) bằng các kí tự ch. 13. Viết thủ tục để hoán đổi hai giá trị x,y cho nhau. 14. Viết hàm tìm BSCNN và USCLN của 2 số nguyên a,b đ−ợc khai báo nh− sau: 66
  16. Function USCLN(a,b: word ) : word; Function BSCNN(a,b: word ) : word; 15. Viết thủ tục để tối giản phân số a/b, với a, b là 2 số nguyên. 16. Viết các hàm đệ quy để tính : S1 = 1 + 2 + 3 + +n ; S2 = 1 + 1/2 + + 1/n ; n+1 S3 = 1 – 1/2 + + (–1) 1/n; S4 = 1/1*2 + 1/2*3 + + 1/(n – 1)*n; 2 n S5 = 1 + sin(x) + sin (x) + + sin (x). k n0kk-1k 17. Viết hàm đệ quy tính C n biết : C=nn1,C=1,Cn=Cn-1+Cn-1 18. Cho m, n nguyên d−ơng. Lập hàm đệ quy tính: ⎧m+1 n=0 ⎪ A(m,n) = ⎨A(n - 1,1) n ≠ 0, m = 0 ⎪ ⎩A(n - 1, A(n,m - 1)) n > 0 ^ m > 0 19. Lập hàm đệ quy để tính dãy Fibonaci : ⎧1n=1∨ n=2 F(n) = ⎨ ⎩F(n - 1) + F(n - 2) n > 2 20. Viết hàm đệ quy tìm USCLN của 2 số. 67
  17. Ch−ơng 8 Kiểu chuỗi kí tự 8.1. Khai báo kiểu chuỗi Chuỗi là kiểu dữ liệu có cấu trúc dùng để tổ chức l−u trữ và xử lí các xâu kí tự. Một chuỗi đ−ợc khai báo bằng từ khoá STRING theo sau là số kí tự cực đại có thể có của chuỗi đ−ợc đặt trong hai dấu ngoặc vuông [ ]. Định nghĩa kiểu chuỗi: TYPE = String[ ]; trong đó là tên của kiểu dữ liệu, là một số nguyên d−ơng chỉ độ dài tối đa của mỗi chuỗi có thể đ−ợc l−u trữ trong biến thuộc kiểu dữ liệu này. Đối với Turbo Pascal: – String có chiều dài tối đa là 255. – Có thể không chỉ ra khi đó mặc nhiên độ dài cực đại là 255. Biến kiểu chuỗi có thể đ−ợc khai báo bằng tên hoặc khai báo trực tiếp nh− trong ví dụ sau đây: Ví dụ 1. Var Hoten : String[30]; St : String; Nếu St là một chuỗi, để chỉ ra kí tự thứ i của St ta viết St[i]. Chẳng hạn, nếu St:= ‘ABCDE’; thì lệnh Writeln(St[3]); sẽ cho ra kí tự ‘C’. Cấu trúc của một biến kiểu chuỗi nh− sau : Trong bộ nhớ, nó chiếm số byte bằng cộng thêm một byte đầu tiên (gọi là byte 0) để chứa kí tự mà mã thập phân ASCII của kí tự này là số kí tự thực có của chuỗi. Chẳng hạn, biến Hoten đ−ợc khai báo ở trên đ−ợc gán giá trị : Hoten:=‘HO DUC’ ; khi đó độ dài của chuỗi chỉ là 6 kí tự, mặc dù ở độ dài cho phép của Hoten la 30. Sau đây là cấu trúc chuỗi Hoten:=‘HO DUC‘. 0 1 2 3 4 5 6 7 8 28 29 30 68
  18. ♠ H O D U C * * * * * Kí tự đầu là kí tự mà mã ASCII của nó chỉ độ dài thực có của String, ở đây nó là kí tự ♠. Kí tự * biểu diễn kí tự không xác định. Chú ý. – Có thể dùng Write(St) hay Writeln (St) để in kí tự St trong khi đó không thể dùng Write và Writeln để viết ra cả một mảng. – Readln(St) sẽ đọc các kí tự cho chuỗi St với độ dài thực sự là số kí tự gõ vào từ bàn phím. Nếu ta gõ luôn, không cho kí tự nào thì St = ‘’ (chuỗi rỗng). 8.2. Các phép toán trên chuỗi kí tự a) Phép gán Đối với các đại l−ợng thuộc kiểu chuỗi kí tự ta có thể thực hiện lệnh gán dạng: := ; trong đó là tên biến thuộc kiểu chuỗi kí tự, còn là một biểu thức kiểu chuỗi kí tự. Biểu thức kiểu chuỗi kí tự là một dãy hằng, biến, hàm kiểu chuỗi kí tự đ−ợc nối với nhau bằng phép ghép (+) các chuỗi kí tự. b) Ghép nối chuỗi Phép nối String : Kí hiệu bởi dấu (+). Chẳng hạn : Nếu A:= ‘Turbo’; B:= ‘Pascal’; C:= A + B; thì sau khi thực hiện 3 lệnh này C sẽ có nội dung là chuỗi ‘Turbo Pascal’. c) So sánh chuỗi Giữa các đại l−ợng kiểu chuỗi kí tự có các phép so sánh (lớn hơn), >= (lớn hơn hoặc bằng), = (bằng), <> (khác). – Khi so sánh hai chuỗi, các kí tự của hai chuỗi đ−ợc so sánh từng cặp một từ trái qua phải theo giá trị của bảng mã ASCII. – Nếu hai chuỗi có độ dài khác nhau song số kí tự giống nhau đến độ dài chuỗi ngắn nhất thì chuỗi có độ dài ngắn hơn đ−ợc coi là bé hơn. Ví dụ 2. Các phép so sánh: ‘ABC’ = ‘ABC’ có trị là True. ‘ABC’ = ‘AB’ có trị là False. ‘ABCD’ < ‘ABED’ có trị là True. 69
  19. ‘ABC’ > ‘AD’ có trị là False. 8.3. Các thủ tục trên chuỗi kí tự ♦ Thủ tục DELETE ( , , ); trong đó là biến kiểu String, và là các biểu thức nguyên. Thủ tục này xoá khỏi chuỗi một số kí tự là và bắt đầu từ vị trí thứ (tính từ trái sang phải). Ví dụ 3. Nếu St là biến kiểu chuỗi kí tự thì sau khi thực hiện dãy lệnh: St:=’ABCDEFG’; Delete(St, 2, 4); Writeln(St); trên màn hình sẽ có kết quả là : AFG. ♦ Thủ tục INSERT( , , ); trong đó là biến kiểu String, là biểu thức kiểu String, là biểu thức kiểu nguyên. Thủ tục này dùng để chèn chuỗi kết quả của biểu thức vào chuỗi ở vị trí . Ví dụ 4. Nếu St là biến kiểu chuỗi thì dãy lệnh: St:= ‘ABCD’; Insert(‘TFG’, St, 3); Writeln(St); sẽ cho kết quả trên màn hình là: ABTFGCD. Tr−ờng hợp v−ợt quá chiều dài của thì sẽ đ−ợc nối đuôi vào . ♦ Thủ tục STR( , ); trong đó là một biểu thức nguyên hay thực có kèm theo dạng in ra, là biến kiểu chuỗi kí tự. Thủ tục này đổi giá trị số thành chuỗi rồi gán cho . Ví dụ 5. Nếu St là tên biến thuộc kiểu kí tự, I là biến nguyên thì sau khi thực hiện dãy lệnh sau: i:=1234; Str(i:5, St); Writeln(St); thì kết quả xuất hiện trên màn hình là: 1234 (có năm kí tự, kí tự đầu tiên là kí tự trắng). ♦ Thủ tục VAL( , , ); trong đó là biểu thức kiểu chuỗi kí tự, là biến nguyên hay thực, còn là biến nguyên. Thủ tục này đổi chuỗi chữ số (biểu diễn một số nguyên hay thực) thành số và gán cho biến . là số nguyên để phát hiện lỗi : Nếu phép biến đổi đúng thì có giá 70
  20. trị bằng 0, nếu sai do không biểu diễn đúng số nguyên hay thực, sẽ nhận giá trị bằng vị trí của kí tự sai trong chuỗi . Ví dụ 6. Nếu St là biến kiểu chuỗi kí tự, i và e là hai biến nguyên thì sau khi thực hiện dãy lệnh: St:=‘234’ ; e:=0; Val(St, i, e); Writeln(i); sẽ cho kết quả trên màn hình là : 234 Nếu thay lệnh đầu tiên là St:=‘2121x’ thì i không xác định và e=3 (kí tự thứ 3 gây lỗi). Sau đây là một ứng dụng dùng thủ tục Val để đọc số nguyên từ bàn phím. Bình th−ờng ta dùng thủ tục Readln(i) để đọc số nguyên i, song nếu chẳng may ta gõ nhầm chữ cái vào máy thì máy dừng lại, có thể gây lãng phí thời gian, bây giờ ta muốn máy kiểm tra lỗi, nếu có thì báo lỗi để gõ lại số liệu. Procedure DOC_Integer(Var: Integer); Var St: String[6]; e: Integer; Begin Repeat Readln(St); Val(St,I,e); If e ); trong đó là một biểu thực chuỗi. Hàm này cho ta độ dài của biểu thức chuỗi kí tự . Ví dụ 7. Nếu St là biến chuỗi , i là một biến nguyên thì sau khi thực hiện dãy lệnh sau: St = ‘ABCDEF’ ; i:= Length(St); Writeln(i); sẽ cho kết quả trên màn hình là số nguyên 7. Hàm COPY( , , ); 71
  21. trong đó là biểu thức kiểu chuỗi kí tự, , là các biểu thức kiểu nguyên. Hàm cho ta một chuỗi mới bằng cách chép kí tự từ chuỗi , bắt đầu từ vị trí . Ví dụ 8. Nếu St1, St2 là các biến kiểu chuỗi kí tự thì sau khi thực hiện dãy lệnh: St1:=‘BCDEF’; St2:=Copy(St1, 3, 2); Writeln(St2); thì trên màn hình sẽ cho kết quả là chuỗi : CD Nếu + lớn hơn Length ( ) thì Copy chỉ nhận các kí tự nằm trong chuỗi . Nếu lớn hơn Length( ) thì Copy sẽ cho một chuỗi rỗng. Hàm CONCAT( , , , ); trong đó , , , là các biểu thức kiểu chuỗi kí tự. Hàm này cho kết quả là ghép nối tất cả các chuỗi , , , thành một chuỗi theo thứ tự đã viết. Chú ý. – Số l−ợng đối số của hàm concat phải ≥ 2. – Nếu tổng số chiều dài của các chuỗi cộng lại > 255 thì máy sẽ báo lỗi. – Có thể dùng phép (+) để ghép nối chuỗi thay Concat. • Hàm POS( , ); trong đó , là hai biểu thức kiểu chuỗi kí tự. Hàm này cho ta số nguyên chỉ vị trí đầu tiên của chuỗi gặp trong chuỗi . Nếu không tìm thấy thì có giá trị bằng 0. Chẳng hạn, nếu St:=‘ABCDEFBCD’ thì Pos(‘DE,St) cho kết quả là 4, Pos(‘XY’,St) là 0; Pos(‘BCD’, St) là 2 Ví dụ 9. Viết ch−ơng trình nhập vào từ bàn phím một chuỗi kí tự và in ra màn hình chuỗi ng−ợc t−ơng ứng. Ví dụ, nhập vào ‘TRUNG TAM’ xuất ra “MAT GNURT’. Program Chuoi_nguoc; Uses Crt; Var cau : String[80]; i : Byte; Begin 72
  22. Writeln(‘Nhập vào một câu: ’); Readln(cau); For i := Length(cau) Downto 1 Do Writeln(cau[i]); Readln End. Ví dụ 10. Viết ch−ơng trình nhập vào một chuỗi, sau đó tách thành chuỗi con theo ý muốn, bằng cách cho biết vị trí đầu tiên và độ dài của chuỗi con. Program Tach_chuoi; Uses Crt; Var St: String[80]; Vt, dd: Byte; begin Clrscr; Writeln(‘Nhap vao mot chuoi: ’); Readln(St); Write(‘Muon tach tai vi tri nao?: ’); Readln(Vt); Writeln(‘Dua vao do dai cua chuoi con?: ”); Readln(dd); Writeln(‘ ’); Writeln(‘Chuoi con can tach la: ’) , Copy(St,VT,dd)); Readln; End. 73
  23. Câu hỏi – Bài tập ch−ơng 8 1. Viết ch−ơng trình nhập vào từ bàn phím họ và tên Việt Nam và chỉ xuất phần tên ra màn hình. Chẳng hạn, nhập ‘Nguyễn Văn Long’, xuất ‘Long’. 2. Viết ch−ơng trình nhập vào từ bàn phím một chuỗi kí tự bằng các kí tự th−ờng hay hoa và xuất ra màn hình chuỗi đó bằng kí tự hoa. Chẳng hạn, nhập ‘Trung Tam’ xuất ra ‘TRUNG TAM’. 3. Viết ch−ơng trình đổi một số nguyên d−ơng hệ cơ số 10 sang hệ cơ số bất kì. 4. Viết ch−ơng trình đọc vào từ bàn phím một câu đ−ợc kết thúc bằng dấu chấm và cho biết có bao nhiêu nhóm kí tự ‘T.R’ trong câu này. 5. Viết ch−ơng trình đọc vào từ bàn phím một câu đ−ợc kết thúc bằng dấu chấm. Hãy đếm trong câu có bao nhiêu từ. Để đơn giản, ta định nghĩa từ là một dãy liên tục các kí tự khác khoảng trắng, khoảng trắng là dấu tách từ duy nhất. 6. Viết ch−ơng trình xuất lên màn hình một khung hình chữ nhật và một dòng chữ di chuyển từ phải qua trái bên trong khung cho đến khi nhấn một phím bất kì. 7. Viết hàm Trim(St:String):String, có kết quả trả về chuỗi St đ−ợc loại bỏ các khoảng trống bên phải. 8. Viết ch−ơng trình tính tổng các số hạng của một số nguyên d−ơng bất kì nhập vào từ bàn phím. 74
  24. Ch−ơng 9 Kiểu bản ghi và kiểu tập tin 9.1. Kiểu bản ghi (Record type) 9.1.1. Khái niệm và định nghĩa Các kiểu cấu trúc dữ liệu nh− kiểu mảng, kiểu tập hợp đều đ−ợc tạo ra bằng một tập hợp các phần tử có cùng kiểu. Chẳng hạn, các phần tử của mảng đ−ợc mô tả bởi Array[1 50] of Integer là các số nguyên. Để tạo ra một kiểu cấu trúc dữ liệu mới với các phần tử dữ liệu có kiểu khác nhau, ng−ời ta định nghĩa ra các bản ghi (Record). Record là một cấu trúc nhiều thành phần. Các thành phần có thể thuộc các kiểu dữ liệu khác nhau và đ−ợc gọi là tr−ờng (Field), mỗi tr−ờng đều đ−ợc đặt bởi một tên. Để định nghĩa kiểu T có cấu trúc kiểu bản ghi với danh sách các tr−ờng có tên là: S1, S2, , Sn và có các mô tả kiểu t−ơng ứng là T1, T2, ,Tn ta có cách viết nh− sau: TYPE T = RECORD S1 : T1; S2 : T2; Sn : Tn; END; Ví dụ 1. Để định nghĩa kiểu thời gian DATE có 3 tr−ờng Ngay (ngày), Thang (tháng) và Nam (năm) trong Pascal có thể viết: Type Date = Record Ngay : 1 1; Thang : 1 12; Nam : Word; End; Ví dụ 2. Định nghĩa kiểu bản ghi Dia_chi (địa chỉ) bao gồm có 3 tr−ờng : So_nha (số nhà), Duong_pho (tên đ−ờng phố), Thanh_pho (tên thành phố). 75
  25. Type Dia_chi = Record So_nha : Word; Duong_pho : String[20]; thanh_pho : String[15]; End; Để mô tả một biến kiểu bản ghi ta có thể mô tả bằng tên kiểu bản ghi hoặc mô tả thông qua định nghĩa trực tiếp. Chẳng hạn, với tên Dia_chi đã đ−ợc định nghĩa trong ví dụ 2 ta có thể mô tả: Var X,Y,Z : Dia_chi; hoặc có thể mô tả trực tiếp nh− sau: Var X,Y,Z : Record So_nha : Word; Duong_pho : String[20]; Thanh_pho : String[15]; End; 9.1.2. Sử dụng biến kiểu bản ghi Muốn truy xuất một biến kiểu bản ghi ta phải truy xuất theo thành phần của chúng. Cú pháp để truy xuất đến một thành phần nào đó là: . trong đó, là tên của biến kiểu bản ghi cần truy xuất còn là tên của tr−ờng cần truy xuất trong biến kiểu bàn ghi. Ví dụ 3. Với mô tả biến : Var X : Record Ngay : 1 31; Thang : 1 12; Nam : Word; End; ta có thể sử dụng các lệnh truy xuất sau: X.Ngay := 01 ; X. Thang := 06; X.Nam := 1953; Ví dụ 4. Ch−ơng trình sau đây thực hiện việc nhập lí lịch cán bộ cho một đơn vị. 76
  26. Uses Crt; Type Date=Record Ngay : 1 31; Thang : 1 12; Nam : Integer; End; Nhan_su = Record Holot : String[20]; Ten : String[7]; Ngaysinh: Date; Luong : Real; Giadinh: Boolean; End; Var Ds : Array[1 50] Of nhan_su; i, socb : Byte; Gd : Char; Begin ClrScr; Writeln(‘NHAP HO SO CAN BO’); Write(‘So can bo: ‘); Readln(socb); Window (20,4,60,17); For i:= 1 To Socb do Begin Clrscr; Write(‘Holot: ’); Readln(ds[i].Holot); Write(‘ten: ’); Readln(ds[i].ten); Write(‘Ngaysinh: / /’ ); Goto XY(14,3); Readln (ds[i].ngaysinh.ngay); Goto XY(17,3); Readln (ds[i].ngaysinh.thang); Goto XY(20,3); Readln (ds[i].ngaysinh.nam); Write(‘Luong: ’); Readln(ds[i].luong); Write(‘Co gia dinh (Y/N)?:’); Readln(Gd); 77
  27. If Upcase(Gd)=’Y’ then ds[i].giadinh:=True else ds[i].giadinh:=False; End; Readln; End. Chú ý. 1. Các biến có cùng một kiểu bản ghi có thể gán cho nhau. Chẳng hạn, với mô tả biến: Var cb1, cb2: Record Holot : String[20]; Ten : String[7]; Ngaysinh : Date; Luong : Real; Giadinh : Boolean; End; ta có thể thay dãy các lệnh gán: cb2.holot := cb1.holot; cb2.ten := cb1.ten; cb2.ngaysinh.ngay : = cb1.ngaysinh.ngay; cb2.ngaysinh.thang : = cb1.ngaysinh.thang; cb2.ngaysinh.nam : = cb1.ngaysinh.nam; cb2.luong := cb1.luong; cb2.giadinh := cb1.giadinh; bằng một lệnh duy nhất: cb2:=cb1 ; 2. Giữa các biến có cùng một kiểu bản ghi có thể sử dụng phép so sánh bằng nhau (=). Chẳng hạn, trong câu lệnh sau: If cb2=cb1 Then Writeln (‘Cung mot nguoi’); 9.1.3. Sử dụng câu lệnh With Khi cần truy cập vào nhiều thành phần của một biến kiểu bản ghi ta có thể dùng câu lệnh With để ch−ơng trình đ−ợc gọn hơn. Dạng câu lệnh: 78
  28. WITH DO ; trong đó là tên của một biến kiểu bản ghi còn là một câu lệnh Pascal, thông th−ờng là một lệnh ghép chứa nhiều tr−ờng của bản ghi. Ví dụ 5. Ta có thể thay đoạn ch−ơng trình trong ví dụ 4 bằng đoạn sau đây: For i:=1 To Socb Do With ds[i] Do Begin Clrscr; Write(‘Holot: ’); Readln(holot); Write(‘ten: ’); Readln(ten); Write(‘ngay sinh: / / ’); With ngay sinh Do Begin GotoXY(14,3);Readln(Ngay); GotoXY(17,3);Readln(Thang); GotoXY(20,3);Readln(Nam); End; Write(‘Luong: ’); Readln(luong); Write(‘Có gia dinh (Y/N)?: ’); Readln(gd); If Upcase(Gd)=‘Y’ then ds[i].Giadinh:=True Else ds[i].Giadinh:=False End; {With} Nh− vậy chúng ta còn có thể lồng các chỉ thị With Do vào với nhau để thâm nhập vào các tr−ờng ở sâu trong record phức tạp nh− biến ds[i]. 9.1.4. RECORD có cấu trúc thay đổi Các kiểu Record đ−ợc trình bày ở trên là kiểu Record cố định vì số thành phần cũng nh− cấu trúc của Record là cố định. Bên cạnh đó ngôn ngữ Pascal còn cho phép thành lập các Record có một phần cấu trúc thay đổi đ−ợc. Tr−ớc hết ta xét ví dụ sau: Trong mục Nhan_su, nếu ta xét thêm tr−ờng Nghenghiep (nghề nghiệp) thì sẽ thấy có tr−ờng hợp xảy ra. Chẳng hạn: – Công nhân : Cần ghi rõ ngành gì, thợ bậc mấy? 79
  29. – Kĩ s− : Ngành gì ? trình độ thực tế ? – Bác sĩ : Chuyên khoa gì ? – Cá biệt : Không ghi gì thêm. Khi đó ta có thể lập một Record đầy đủ các tr−ờng hợp kể trên nh−ng rất cồng kềnh và chiếm nhiều ô nhớ (trong khi giả sử một ng−ời tại một thời điểm nào đó chỉ có một nghề). Hay có thể lập ra 4 kiểu Record giống nhau phần đầu (Holot, Ten, Ngaysinh, Luong, Giadinh) nh−ng chỉ khác nhau phần cuối là Nghenghiep sẽ có các tr−ờng t−ơng ứng với 4 nghề khác nhau. Điều này cũng làm phức tạp và cồng kềnh ch−ơng trình vì ta phải dùng đến bốn kiểu Record. Ngôn ngữ Pascal cho phép lập Record có dạng sau để tiết kiệm ô nhớ và cho phép linh hoạt khi sử dụng: Type Nghe = (Congnhan, Kisu, Bacsi, Cabiet); Nganh = (Khaithac, Cokhi, Chebien, Nuoi, Kinhte); Khoa = (Noi, Ngoai, Nhi, Phu); Nhan_su = Record Holot : String[20]; Ten : String[7]; Ngaysinh : Date; Luong : Real; Giadinh : Boolean; Case Nghenghiep: Nghe of Congnhan: (NganhCN: Nganh; Bactho: Byte); Kisu : (NganhKS : Nganh; TrinhdoTT: (Kem, TB, Kha, Gioi)); Bacsi: (Chuyenkhoa : Khoa); Cabiet : (); End; {Of Record} Var cb1, cb2 : Nhan_su; Begin With cb1 Do Begin Holot:=‘Nguyen Van’; Ten:=‘Luong’; Nghenghiep:=Congnhan; NganhCN:=Cokhi; 80
  30. Bactho:=3; End; With cb2 do Begin Holot:=‘Le Thi’; Ten:=‘Hoa’; Nghenghiep:=Kisu; NganhCN:=Nuoi; Trinhdo:=Kha; End; End. Holot, Ten, Ngaysinh, Giadinh là các tr−ờng cố định của Record Nhan_su. NganhCN, NganhKS, TrinhdoTT, Chuyenkhoa, Bactho là các thành phần thay đổi của các biến thuộc kiểu bản ghi nhân sự. Trong khai báo một kiểu bản ghi các thành phần thay đổi (nếu có) phải nắm chắc các thành phần cố định và chỉ đ−ợc phép có nhiều nhất là một tr−ờng thay đổi. Nói cách khác phần thay đổi đ−ợc đặt sau cùng trong danh sách các tr−ờng và nó đ−ợc bắt đầu bằng lệnh Case. Tuy nhiên phần thay đổi có thể lại chứa kiểu bản ghi khác có cấu trúc thay đổi. Chú ý. – Phần thay đổi bao gồm một tr−ờng gọi là tr−ờng đánh dấu (Tag Field) đ−ợc đặt trong câu lệnh Case. ứng với mỗi giá trị của tr−ờng đánh dấu ta có các biến dạng của kiểu bản ghi với danh sách các tr−ờng t−ơng ứng đ−ợc đặt sau các nhãn của lệnh Case và toàn bộ danh sách này phải đ−ợc đặt trong hai dấu ngoặc đơn. – Tr−ờng đánh dấu phải đ−ợc mô tả bằng một kiểu đơn giản. – Tất cả các tên biến trong phần thay đổi đều bắt buộc phải khác nhau. Ví dụ 6. Ch−ơng trình sau đây thực hiện việc nhập họ tên và điểm trung bình của một lớp theo thứ tự giảm dần của điểm trung bình và có xếp hạng. Program Tinhdiem; Uses Crt; Const Max = 100; Type Svien = Record 81
  31. Hoten : String[30]; Dtb : Real; End; Lop = Array [1 max] Of Svien; Var L: Lop; N : Integer; Procedure Nhap; {Thu tuc nhap ho ten va diem trung binh cua lop} Var i:Integer; Begin Write (‘So sinh vien:’); Readln(N); For i:=1 To N Do With L[i] Do Begin Write (‘Ho ten :’); Readln (Hoten); Write (‘Diem TB: ’); Readln (Dtb); End; End; {Nhap} Procedure Sap_xep; Var i,j : Integer; Tam : Svien; Begin {Sap Xep} For i:=2 to N Do For j:= N Downto i Do If L[j-i].Dtb<L[i].dtb Then Begin Tam:=L[j-i]; L[j-i]:=L[i]; L[i] :=tam; End; End; {Sap_Xep} Procedure Liet_ke; {Tinh hang va liet ke} 82
  32. Var i, hang: Integer; Begin Sap_xep; hang:=1 ; Clrscr; Writeln; Writeln (‘TT HO VA TEN DIEM HANG’); Writeln; For i:=1 To N Do Begin If (i>1) and (L[i].dtb = FILE OF ; trong đó là một tên định danh cho tập tin, là một kiểu dữ liệu nào đó khác với kiểu tập tin và thông th−ờng là kiểu bản ghi. 83
  33. Ta cũng có thể mô tả tên biến kiểu tập tin qua tên kiểu tập tin hoặc qua định nghĩa trực tiếp của tập tin. Ví dụ 7. Sau đây là một ví dụ về định nghĩa một kiểu dữ liệu File của các bản ghi: Type FileReal = File Of Real; Date = Record Ngay : 1 31; Thang : 1 12; Nam : Word; End; Nhansu = Record Maso : Word; Holot : String[20]; Ten : String[7]; Ngaysinh : Date; Luong : Real; End; Fnhasu = File Of nhansu; Var F1 : FileReal; F2 : Fnhansu; Ta cũng có thể mô tả tập tin trực tiếp bằng định nghĩa. Chẳng hạn nh− mô tả sau: Var F3: File Of Char; F4: File Of Array [1 5] Of Integer; Những điểm giống và khác nhau giữa tập tin và mảng đ−ợc thể hiện ở bảng sau: ARRAY FILE – Tập hợp các dữ liệu cùng kiểu. – Tập hợp các dữ liệu cùng kiểu. – Chứa tạm trong RAM. – L−u trữ trên đĩa. – Truy xuất ngẫu nhiên đến các – Truy xuất ngẫu nhiên hay thành phần. tuần tự. – Số phần tử đ−ợc xác định khi khai – Số phần tử không đ−ợc xác định báo. khi khai báo. 84
  34. Biến tập tin là một biến dữ liệu thuộc kiểu tập tin. Một biến tập tin đại diện cho một tập tin. Việc truy xuất dữ liệu ở một tập tin đ−ợc thể hiện qua các thao tác với thông số là biến tập tin đại diện. 9.2.2. Cấu trúc và phân loại tập tin Các phần tử của mảng có thể truy cập đ−ợc tuỳ ý thông qua tên biến và chỉ số. Các phần tử của tập tin không có tên và việc truy nhập không thể tuỳ tiện đ−ợc. Các phần tử của tập tin đ−ợc sắp xếp thành 1 dãy và ở mỗi thời điểm ch−ơng trình có thể truy nhập vào một phần tử của tập tin thông qua giá trị của một biến đệm. Biến đệm đ−ợc dùng để đánh dấu vị trí truy nhập hay còn gọi là cửa sổ của tập tin. Mỗi tập tin đều đ−ợc kết thúc bằng một dấu hiệu đặc biệt để báo hiệu hết tập tin hay gọi là EOF (End Of File). Hàm chuẩn EOF có kiểu Boolean với tham số là biến tập tin để xem cửa sổ đã đặt vào vị trí kết thúc tập tin đó ch−a. Nếu cửa sổ con ch−a trỏ vào phần tử cuối tập tin F thì EOF(F) có giá trị là False. Việc phân loại tập tin dựa trên việc bố trí các phần tử của tập tin ở bộ nhớ ngoài và cách truy nhập vào tập tin. Tập tin truy nhập tuần tự (Sequential Access), tập tin truy nhập trực tiếp (Direct Access). Tập tin truy nhập tuần tự có các đặc điểm sau: – Việc đọc một phần tử bất kì của tập tin phải đi qua các phần tử tr−ớc đó. – Muốn thêm 1 phần tử vào tập tin, phải đặt cửa sổ vào vị trí cuối tập tin. Tập tin truy nhập trực tiếp có các đặc điểm sau: – Có thể đặt cửa sổ vào một phần tử bất kì của tập tin. Tập tin truy nhập trực tiếp đ−ợc định nghĩa ở Turbo Pascal, còn Pascal chuẩn không có và d−ới đây nếu không nói rõ tập tin loại gì thì hiểu là tập tin tuần tự, sau đó chúng ta sẽ nghiên cứu thêm về tập tin truy nhập trực tiếp. 9.2.3. Các thao tác trên tập tin a. Mở tập tin để cất dữ liệu Ch−ơng trình chỉ có thể cất dữ liệu vào một tập tin sau khi ta làm thủ tục mở tập tin. Việc mở tập tin đ−ợc tiến hành với hai thủ tục đi liền nhau theo thứ tự. Assign( , ); Rewrite( ); ở đây là biến kiểu tập tin, là một hằng chuỗi kí tự gán cho tập tin đặt trong thiết bị nhớ ngoài (Quy tắc đặt tên theo quy định của HĐH). Nên đặt tên sao cho nó phản ánh đ−ợc ý nghĩa hay bản chất nội dung của tập tin. 85
  35. Ví dụ 8. Các lệnh sau đây cho phép mở các tập tin F1 và F2 có tên trên đĩa t−ơng ứng là ‘LUONG.DAT’ và ‘NGUYEN.DAT’. Assign(F1,‘LUONG.DAT’); Rewrite(F1); Assign(F2,‘NGUYEN.DAT’); Rewrite(F2); Sau khi mở tập tin xong, tập tin sẽ rỗng vì tập tin ch−a có phần tử nào, cửa sổ tập tin sẽ không có giá trị xác định vì nó trỏ vào cuối tập tin (EOF). Chú ý. Khi mở tập tin, nếu trên bộ nhớ ngoài đã có sẵn tập tin có tên trùng với tên tập tin đ−ợc mở thì nội dung tập tin cũ sẽ bị xoá. Ghi các giá trị vào tập tin với thủ tục WRITE. Thủ tục Write sẽ đặt các giá trị mới vào tập tin. Cú pháp: Write( , , , , ); trong đó , , , là các giá trị cần ghi vào tập tin, có thể là các hằng, biến, biểu thức. Ví dụ 9. Ghi vào tập tin các số nguyên (NGUYEN.DAT) các giá trị 4, 15, 31 ta viết: Write(F2, 4, 15, 31); khi đó nội dung của tập tin NGUYEN.DAT sẽ nh− sau: 4 15 31 EOF và vị trí cửa sổ ở phần tử cuối tập tin, cụ thể là ở đây là ở giá trị 31. b. Đóng tập tin B−ớc cuối cùng của việc đặt dữ liệu vào tập tin là đóng tập tin lại bằng thủ tục CLOSE để đảm bảo thông tin trên tập tin này là đầy đủ và tin cậy. Cú pháp: Close( ); Ví dụ 10. Tạo một tập tin chứa các số nguyên từ 1 đến 100 với tên tập tin trên đĩa là NGUYEN.DAT. Program Tao_Tap_Tin_1; Var 86
  36. i : Byte; F : File Of Byte; Begin Assign(F,’NGUYEN.DAT’); Rewrite(F); For i:= 1 To 100 Do Write(F,i); Close(F); End. Một tập tin có thể đ−ợc dùng làm tham số của ch−ơng trình con với lời khai báo bắt buộc phải sau chữ Var tức là tập tin đ−ợc dùng làm tham biến. Chẳng hạn nh− trong ví dụ sau: Ví dụ 11. Program Tao_Tap_Tin_2; Type F1 = File Of Byte; St30 = String[30]; Var Myfile: F1; FileName : St 30; Procedure Tao_File(Var F: F1; Ten: St30); Var i = Byte; Begin Assign(F,Ten); Rewrite(F); For i:=1 To 100 Do Write(F,i); Close(F); End; Begin {CT_Chinh} Write (‘Ten tap tin: ’); Readln(FileName); Tao_File(MyFile, FileName); End. c. Đọc dữ liệu từ một tập tin đã có Đối với tập tin tuần tự, ta không thể vừa ghi vừa đọc đ−ợc cùng một lúc. Sau khi ghi dữ liệu vào tập tin và đóng lại, ta có thể đọc lại các giá trị dữ liệu trong tập tin. 87
  37. Một ch−ơng trình muốn sử dụng các dữ liệu đã đ−ợc chứa trong một tập tin, đầu tiên phải mở tập tin đó ra để đọc. d. Mở tập tin để đọc Mở tập tin để đọc ta sử dụng cặp lệnh: Assign( , ); Reset( ); Sau lệnh Reset nếu tập tin không rỗng thì cửa sổ bao giờ cũng trỏ vào phần đầu tiên của tập tin và ch−ơng trình sẽ copy phần tử của tập tin đ−ợc trỏ sang biến đệm của cửa sổ. Nội dung của tập tin này không bị xoá. Nếu ta mở tập tin ch−a tồn tại trên đĩa sẽ có lỗi thời gian thi hành. e. Đọc dữ liệu từ tập tin Dùng thủ tục READ dạng nh− sau: Read( , , , , ); trong đó , , , là các biến có cùng kiểu với kiểu thành phần của . Gặp lệnh này, máy sẽ đọc các giá trị tại vị trí cửa sổ đang trỏ (nếu có) gán sang biến cùng kiểu t−ơng ứng sau đó cửa sổ dịch chuyển đến vị trí tiếp theo và đọc giá trị cho biến khác, cứ thế đọc cho đến biến . READ chỉ có thể đọc các giá trị của tập tin để gán giá trị cho các biến. Việc đọc một phần tử của tập tin cần có điều kiện: Phải thử xem tập tin có còn phần tử nào không – tức là cửa sổ ch−a trỏ đến EOF. Do đó tr−ớc khi làm một thao tác gì để đọc tập tin gán cho biến X, cần phải thử xem tập tin đó đã kết thúc ch−a bằng câu lệnh: If Not Eof( ) Then Read( ,X) Hoặc nếu muốn đọc tất cả các phần tử của tập tin ta có thể viết: While Not Eof( ) Do Begin Read( ,X); End; Công việc cuối cùng kết thúc việc đọc tập tin là đóng tập tin lại với thủ tục : lose( ). Ví dụ 12. Giả sử đã tồn tại một tập tin là NGUYEN.DAT chứa các số kiểu byte có chứa ít nhất là 3 phần tử. Ch−ơng trình sau đây đọc ra giá trị thứ nhất và thứ ba của tập tin và gán cho hai biến A, B t−ơng ứng. Program Doc_1; 88
  38. Var A,B :Byte; FI : File Of Byte; Begin Assign(FI,”NGUYEN.DAT); Reset(FI); Read(FI,A); {Doc 1 phan tu thu 1 của file ra bien A} Read(FI,B); {Doc 1 phan tu thu 2 của file ra bien B} Read(FI,B); {Doc 1 phan tu thu 3 của file ra bien B} Close(FI); End. Ba lần đọc Read(FI, ) ở trên có thể thay thế bằng một lệnh đọc duy nhất: Read(Fi,A,B,B); Ví dụ 13. Ch−ơng trình sau đây đọc tất cả các phần tử của tập tin chứa các số có kiểu Byte nào đó và ghi ra màn hình giá trị các số đó và cuối cùng ghi ra số phần tử của tập tin. Program Doc_2; Uses Crt; Var i, So_pt :Byte; Fi : File Of Byte; FileName: String[20]; Begin Clrscr; Write(‘Cho biet ten file (chua cac so nguyen):’);Readln(Filename); Assign(FI,FileName); Reset(FI); So_pt:=0; While Not EOF (FI) Do Begin Read(FI,i); {doc mot phan tu của file ra bien i} Write(i, ‘ ’); So_pt:=So_pt+1 ; {dem so phan tu} End; 89
  39. Close(FI); Writeln; Write(‘So_Phan_Tu_Cua_File: ’ , FileName, ‘la:’, So_pt); Readln End. 9.2.4. Tập tin truy nhập trực tiếp Pascal chuẩn chỉ định nghĩa một kiểu tập tin truy nhập tuần tự. Tuy nhiên một số loại bộ nhớ ngoài, chẳng hạn nh− đĩa từ, có thể cho phép tính toán toạ độ của một phần tử bất kì trong tập tin (vì độ dài các phần tử là nh− nhau), do đó có thể truy nhập trực tiếp vào một phần tử của tập tin mặc dù cấu tạo logic của tập tin vẫn là dạng tuần tự. Trong Turbo Pascal để truy nhập trực tiếp vào phần tử của tập tin, ta dùng thủ tục SEEK. Cú pháp: Seek( , ); trong đó là tên tập tin nh− định nghĩa ở trên còn là số thứ tự của phần tử trong tập tin (phần tử đầu tiên là số 0). Gặp thủ tục này máy sẽ đặt cửa sổ của tập tin vào phần tử thứ . Tiếp theo muốn đọc phần tử đó ta dùng READ và nếu muốn đặt giá trị mới vào ta dùng WRITE. Ví dụ 14. Giả sử tập tin NGUYEN.DAT trên đĩa ở th− mục hiện hành đã chứa 100 số nguyên từ 1 đến 100. Ta kiểm tra xem phần tử thứ 2 (đếm từ 0) của tập tin có giá trị bằng 3 không? Nếu không thì sửa lại. Var I : Byte; F : File Of Byte; Ans : Char; Begin Assign(F,’NGUYEN.DAT’); Reset(F); Seek (F,2); {dat cua so vao vi tri thu 3} Read(F,i); Writeln(‘i =’,i); Write(‘Co sua lai khong (C/K) ?:’); Readln(Ans); If ans In [‘c’,’C’] Then Begin Seek(F,2); {dat lai cua so vao vi tri 3} Write(‘i=’); Readln(i); 90
  40. Write(F,i); {Thay doi gia tri tap tin} End; Close(F); End. 9.2.5. Các thủ tục và hàm xử lí tập tin của Turbo Pascal – Hàm FileSize( ) Cho số phần tử của tập tin . Hàm nhận giá trị 0 khi tập tin rỗng. – Hàm FilePos( ) Cho biết vị trí hiện tại của con trỏ (cửa sổ) trong tập tin (phần tử đầu tiên là phần tử số 0). Một tập tin đã tồn tại chỉ có thể lớn lên bằng cách ghi thêm phần tử mới vào vị trí cuối cùng của tập tin. Muốn vậy, tr−ớc hết ta phải đ−a con trỏ tập tin vào vị trí cuối cùng của tập tin bằng lệnh sau: Seek( , FileSize( )); – Thủ tục Erase( ); Xoá tập tin trên đĩa có tên ấn định với biến tập tin . – Thủ tục Rename( , ); trong đó là một hằng kí tự. Thủ tục này dùng thay đổi tên tập tin với tên mới kiểu string chứa trong chuỗi . Chú ý – Tên mới phải không trùng tên tập tin nào có sẵn trên đĩa đang làm việc. – Không đ−ợc đổi tên tập tin đang mở. Ví dụ 15. 1. Dãy lệnh sau đây thực hiện việc xoá tập tin ở trong bộ nhớ ngoài, có tên đ−ợc nhập từ bàn phím : Write(‘Cho biet tap tin can xoa:’); Readln(Ten_File); Assign(F,Ten_File); Erase(F); 2. Muốn đổi tập tin có tên là File1.dat thành File2.dat ta cần viết cặp lệnh sau: Assign(F,’File1.dat’); 91
  41. Rename(F,’File2.dat’); Kiểm tra tập tin khi đang mở Một số vấn để nảy sinh khi làm việc với tập tin: – Khi dùng Reset(F) liệu tập tin F đã tồn tại ch−a? – Khi vào tập tin F thì liệu trên đĩa còn đủ chỗ để chứa thêm dữ liệu không ? Turbo Pascal cung cấp lời h−ớng dẫn (Directive) cho ch−ơng trình dịch để đóng/mở việc kiểm tra lỗi trong quá trình vào ra tập tin. . {$I+} : Mở việc kiểm tra. Khi gặp lỗi vào/ra, ch−ơng trình sẽ báo lỗi và dừng lại. Đây là chế độ mặc nhiên. . {$I-} : Không kiểm tra lỗi vào/ra, ch−ơng trình không dừng lại nh−ng sẽ treo tất cả các thủ tục vào/ra khác cho đến khi lời gọi hàm có kết quả IOResult (có kiểu Integer), hàm IOResult=0 nếu mọi việc xảy ra tốt đẹp. Ví dụ 16. Thủ tục sau đây thực hiện việc kiểm tra lỗi vào ra khi mở một tập tin mới: Procedure OpenInputFile; Var OK : Boolean; Begin Repeat Write(‘Ten Tap Tin:’); Readln(TenFile); Assign(F,TenFile); {$I-} {chuyen viec kiem tra cho nguoi dung} Reset(F); OK:= IOResult=0; {$I+} If Not OK Then Write(‘Khong the mo); Until OK; End; 9.2.6. Tập tin văn bản (Text File) Trong Pascal có một kiểu tập tin đã đ−ợc định nghĩa tr−ớc, đó là tập tin văn bản. Tập tin này đ−ợc định nghĩa với tên chuẩn Text. Chẳng hạn, d−ới đây là cách khai báo các tập tin F1, F2 có kiểu Text: Var F1 , F2: Text; 92
  42. Thành phần cơ sở của tập tin kiểu Text là kí tự. Tuy nhiên tập tin văn bản đ−ợc cấu trúc thành các dòng, mỗi dòng đ−ợc kết thúc bởi dấu EOL (End Of Line). Trong Turbo Pascal đó là cặp kí tự kiểu CR (Carriage Return: nhảy về đầu dòng, mã ASCII=13) và LF (Line Feed: nhảy thẳng xuống dòng tiếp theo, mã ASCII=10). Nh− vậy, tập tin văn bản khác với Text of Char. Với Text Of Char thì coi dấu hết dòng nh− một kí tự bình th−ờng. Nh− vậy: muốn đọc và in ra từng dòng của tập tin văn bản dùng dạng Text, muốn đọc và in ra từng kí tự của tập tin văn bản thì dùng File Of Char. Tập tin văn bản đ−ợc kết thúc bởi dấu End_of_file, cụ thể với Turbo Pascal là Ctrl+Z (^Z), mã ASCII=26. Ví dụ, tập tin các ch−ơng trình nguồn của Pascal, Basic, công văn, bức th−, là một tập tin văn bản. Ví dụ, đoạn văn bản: ‘BO MON TOAN ma so 1221’ đ−ợc chứa trong tập tin văn bản thành một dãy nh− sau: BO MON TOAN ma so 1221EOF Vì chiều dài của các dòng th−ờng là khác nhau nên Text file chỉ có thể truy xuất theo kiểu tuần tự, ngoài ra không thể tiến hành cả hai hoạt động đọc và ghi cùng lúc trên Text File. Các thủ tục đã trình bày với File có cấu trúc cũng sử dụng đ−ợc trong file văn bản. Tuy nhiên Text File có đặc điểm khác sẽ đ−ợc trình bày sau. a. Hàm chuẩn – Hàm Eof (Var F: Text): Boolean; Hàm này cho giá trị False khi cửa sổ tập tin ch−a đến điểm cuối tập tin, ng−ợc lại cho giá trị True. Nó th−ờng dùng để kiểm tra xem đã đọc hết Text File ch−a. b. Ghi vào một tập tin văn bản Chúng ta có thể ghi các trị kiểu Integer, Real, Boolean, String vào tập tin văn bản bằng lệnh Write hay Writeln. Cách ghi này cho phép chuyển các giá trị bằng số sang dạng kí tự, tức là d−ới dạng đọc đ−ợc một cách t−ờng minh nh− trên trang giấy viết bình th−ờng, cho phép viết các kiểu bảng dữ liệu với quy cách mong muốn. Có 3 dạng viết: Dạng 1. Write( , , , , ); Dạng 2. Writeln( , , , , ); Dạng 3. Writeln( ); Dạng 1 ghi các giá trị của các , , , là các hằng hay biểu thức có kiểu đơn giản nh−: nguyên, thực, kí tự, chuỗi, logic vào biến tập tin . Dạng 2 t−ơng tự nh− dạng 1 nh−ng đ−a thêm dấu hiệu hết dòng vào tập tin sau khi đã viết hết các giá trị , , , . 93
  43. Dạng 3 chỉ thực hiện việc đ−a thêm dấu hiệu hết dòng vào tập tin. Ví dụ 17. Ch−ơng trình sau tạo một Text file có 6 dòng: Program Tao_File; Begin Assign(F,‘VanBan.txt’); Rewrite(F); Writeln(F,‘Cong Hoa Xa Hoi Chu Nghia Viet Nam’); Writeln(F,‘Doc lap – Tu do – Hanh phuc’); Writeln(F,‘ ’); Writeln(F); Writeln(F,‘Danh sach hoc vien lop Pascal’); Writeln(F,‘ Khoa 1 ’); Close(F); End. Chú ý. Trong Write, Writeln có thể dùng cách in có quy cách nh− đã trình bày. c. Đọc dữ liệu từ tập tin văn bản Chúng ta có thể đọc không những các kí tự từ tập tin văn bản mà còn có thể đọc lại các số nguyên, thực, logic từ tập tin văn bản thông qua các thủ tục: Dạng 1. Read( , , , , ); Dạng 2. Readln( , , , , ): Dạng 3. Readln( ); trong đó , , , là các biến thuộc kiểu kí tự, Nguyên, Thực, Logic, Chuỗi. Dạng 1 đọc một hay nhiều phần tử mà không chuyển cửa sổ tập tin xuống dòng. Dạng 2 t−ơng tự dạng 1 nh−ng chuyển cửa sổ tập tin sang đầu dòng tiếp theo sau khi đã lần lần l−ợt đọc các biến t−ơng ứng. Dạng 3 đ−a cửa sổ tập tin sang đầu dòng tiếp theo mà không đọc gì cả. Ví dụ 18. Ch−ơng trình sau đây đọc và in ra màn hình nội dung của tập tin kiểu Text file có tên Vanban.txt đ−ợc tạo ra từ ch−ơng trình sau: Program Doc_File; Uses Crt; 94
  44. Var F: Text; Dong:String[80]; Begin Clrscr; Assign(F,’VanBan.txt’); Reset(F); While Not EOF(F) Do Begin Readln(F,dong); Writeln(dong); End; Close(F); Readln; End. d. Thủ tục thêm dòng – Thủ tục Append(Var F:Text); Mở tập tin văn bản để thêm vào các dòng. Thủ tục Append mở tập tin theo lối ghi, định vị cửa sổ tập tin, sau đó nếu gặp thủ tục Write hay Writeln nội dung thêm vào sẽ đ−ợc đặt vào cuối tập tin. Ví dụ 19. Ch−ơng trình sau đây thêm hai dòng vào cuối tập tin VanBan.txt Program Them; Var F:Text; Begin Assign(F;’VanBan.txt’); Append(F); Writeln(F,’Day la dong thu nhat them vao’); Writeln(F,’Day la dong thu hai them vao’); Close(F); End. e. Các tập tin thiết bị 95
  45. Một số phần mềm của Pascal coi các thiết bị ngoài nh− các tập tin văn bản. Nghĩa là việc xuất nhập đ−ợc thực hiện bằng các thao tác nh− với tập tin văn bản. Chẳng hạn đối với Turbo Pascal ta có thể sử dụng các tập tin chuẩn sau : (Không cần khai báo lại). – OUTPUT là tập tin xuất cơ bản. Thông th−ờng OUTPUT đã đ−ợc tự động gán cho màn hình. Khi dùng biến tập tin OUTPUT, các thủ tục Write, Writeln không cần ghi rõ OUTPUT. Đó cũng chính là cách viết Write, Writeln mà ta đã học từ đầu. Chẳng hạn, lệnh Writeln(a,b,c); đ−ợc hiểu ngầm là Writeln(Output,a,b,c); – INPUT là tập tin nhập cơ bản t−ơng ứng với tập tin chứa dữ liệu nguồn vào, th−ờng đ−ợc tự động gán cho bàn phím (tr−ớc đây có thể máy đọc bìa, đọc băng). INPUT không phải ghi vào vị trí FileVar trong thủ tục Read hay Readln. Chẳng hạn, Read(Var); đ−ợc hiểu là Read(Input,Var) – LST : Trong Turbo Pascal, máy in đ−ợc định nghĩa là biến tập tin có tên LST. Biến này đ−ợc đặt trong đơn vị ch−ơng trình PRINTER.TPU, vì vậy cần khai báo unit Uses PRINTER sau đó có thể sử dụng các thủ tục thủ tục Write(LST, ), Writeln(LST, ). Ví dụ 20. Ch−ơng trình sau in tập tin VanBan.txt ra máy in. Program In_File; Uses Printer; Var F:Text; Dong:String[80]; Begin Assign(F,‘Vaban.txt’); Reset(F); While Not Eof(F) Do Begin Readln(F,dong); Writeln(Lst,dong); End; Close(F); Writeln; End. 96
  46. Câu hỏi – Bài tập Ch−ơng 9 1. Viết ch−ơng trình quản lí điểm của mỗi lớp học gồm các công việc sau: – Nhập hồ sơ của mỗi học sinh gồm có họ tên, năm sinh, điểm trung bình học kì I, điểm trung bình học kì II. – In danh sách các học sinh của lớp có điểm trung bình toàn năm từ 5 điểm trở lên và theo thứ tự giảm dần của điểm trung bình toàn năm. – In danh sách các học sinh phải thi lại (điểm trung bình toàn năm d−ới 5) theo thứ tự abc của tên. – In bảng thống kê tần suất (số lần xuất hiện) của các loại điểm trung bình toàn năm. 2. Viết ch−ơng trình in ra phiếu thanh toán tiền thuê máy tính theo mẫu sau: Phiếu thanh toán tiền thuê máy tính Họ và tên ng−ời sử dụng: Đơn vị công tác: Ngày thuê máy: Từ giờ: đến giờ: Tổng số giờ thuê máy: Số tiền phải trả: Thủ quỹ Các số liệu nhập vào từ bàn phím. Tiền 1 giờ thuê máy là 2000 đồng. Cuối cùng in ra bảng tổng kết ngày có dạng: Thống kê tiền thuê máy Ngày tháng năm STT Họ và tên Đơn vị Số giờ Số tiền 1 2 Tổng cộng: Thủ quỹ 97
  47. 3. Viết ch−ơng trình quản lí điểm thi học phần của sinh viên bao gồm các tr−ờng sau : Họ tên, Điểm Tin, Điểm Ngoại Ngữ, Điểm trung bình, Xếp loại. Thực hiện các công việc sau: a) Nhập vào danh sách sinh viên của một lớp (không quá 30 ng−ời) : Họ tên, Điểm Tin, Điểm Ngoại ngữ. b) Tính điểm trung bình và xếp loại cho từng sinh viên. c) In ra màn hình danh sách sinh viên của lớp đó theo dạng sau: Họ tên Điểm Điểm Điểm Xếp loại tin Ngoại ngữ Trung bình Trần Văn An 8 9 8.5 Giỏi Lê Thị Bích 7 5 6.0 T.Bình d) In ra màn hình danh sách các sinh viên phải thi lại (nợ một trong hai môn). e) In ra danh sách những sinh viên xếp loại Giỏi. f) Tìm những sinh viên có điểm trung bình cao nhất lớp. g) Sắp xếp lại danh sách sinh viên theo thứ tự Alphabet. h) Sắp xếp lại danh sách sinh viên theo thứ tự giảm dần của điểm trung bình. 4. Viết ch−ơng trình quản lí sách ở th− viện gồm các tr−ờng sau : Mã số sách, Nhan đề, Tên tác giả, Nhà xuất bản, Năm xuất bản. a) Nhập vào kho sách của th− viện (gồm tất cả các tr−ờng). b) Tìm một cuốn sách có mã số đ−ợc nhập vào từ bàn phím. c) Tìm tất cả các cuốn sách có cùng tác giả. d) Lọc ra các cuốn sách đ−ợc xuất bản trong cùng một năm nào đó. e) Tìm các cuốn sách mà Nhan đề có chứa từ TIN HOC. 5. Viết ch−ơng trình hiển thị nội dung của một file văn bản đã có trên đĩa (Lệnh TYPE). 6. Viết ch−ơng trình nối 2 file văn bản thành một file thứ 3 (Lệnh COPY dạng 2). 7. Viết ch−ơng trình đếm số dòng có trong một file văn bản. 8. Viết ch−ơng trình đếm số từ có trong một file văn bản 9. Cho 2 file số nguyên đã có thứ tự tăng dần. Hãy nối 2 file đó lại với nhau sao cho file mới vẫn có thứ tự tăng dần. 2 n 10. Cho đa thức P(x) = a0 + a1x + a2x + + anx , 98
  48. trong đó n là bậc của đa thức và a0, a1, , an là các hệ số của đa thức đ−ợc l−u trong một file văn bản với quy −ớc sau: – Dòng đầu của file văn bản chứa bậc của đa thức và giá trị của x. – Dòng tiếp theo chứa các hệ số của đa thức. Chẳng hạn, P(x) = 3 + 2x – 5x2 + 4x3 , x = 2.5 sẽ đ−ợc l−u trong file văn bản nh− nhau: 3 2.5 3 2 –5 4 Viết ch−ơng trình đọc file văn bản trên để lấy các số liệu rồi tính giá trị của đa thức. 11. Viết ch−ơng trình quản lí sinh viên (dùng dữ liệu kiểu File để l−u trữ) gồm các công việc chính sau: – Nhập vào danh sách, l−u vào File. – Bổ sung một số sinh viên mới. – Sửa đổi một số dữ liệu (Nếu dữ liệu trong File ch−a chính xác). – Đọc danh sách sinh viên l−u vào bộ nhớ (l−u vào Mảng). – Sắp xếp lại danh sách sinh viên theo thứ tự Alphabet. – Tính toán điểm, xếp loại cho từng sinh viên. – L−u danh sách từ bộ nhớ vào đĩa. 99
  49. Ch−ơng 10 Kiểu con trỏ và biến động Khi sử dụng mảng để l−u trữ danh sách có nhiều phần tử dữ liệu th−ờng xảy ra một trong hai hiện t−ợng sau : – Khai báo thiếu, có nghĩa là không gian nhớ không đủ để bổ sung phần tử vào mảng và do đó ch−ơng trình không tiếp tục thực hiện đ−ợc. – Khai báo thừa, tức là không gian nhớ dành cho mảng quá lớn so với yêu cầu dẫn đến lãng phí bộ nhớ. Để khắc phục những nh−ợc điểm này, Turbo Pascal cho phép dùng biến động (dynamic variable). Các biến này đ−ợc l−u trữ trong vùng HEAP (danh sách các từ máy) khi cần chúng có thể tạo ra để chứa dữ liệu, khi không cần có thể xoá đi để giải phóng bộ nhớ. Do vậy mà số biến này hoàn toàn không đ−ợc xác định từ tr−ớc. Biến động có tên và do con trỏ quản lí. 10.1. Biến con trỏ Biến con trỏ (Pointer Variable) là một loại biến đặc biệt có kích th−ớc 2 byte, không dùng để chứa dữ liệu, mà dùng để chứa địa chỉ của các biến động. 10.1.1. Khai báo biến con trỏ (Pointer) Trong Turbo Pascal, biến kiểu con trỏ đ−ợc định nghĩa nh− sau: TYPE = ^ ; trong đó là tên biến dùng để kí hiệu một kiểu con trỏ, là một kiểu nào đó. Thông th−ờng là kiểu bản ghi có chứa một vài tr−ờng có kiểu con trỏ. Để mô tả biến kiểu con trỏ ta có thể sử dụng tên đã định nghĩa hoặc mô tả thông qua định nghĩa trực tiếp. Chẳng hạn, ta có thể mô tả biến trỏ Ptr nh− sau: Var Ptr : ; Hoặc Var Ptr : ^ ; Để thâm nhập vào biến động có địa chỉ nằm trong biến con trỏ Ptr ta dùng kí hiệu Ptr^. Ví dụ 1. Sau đây là một vài định nghĩa kiểu con trỏ và mô tả biến trỏ. Type 100
  50. Danh_sach=^Nhansu; Nhansu = Record Hoten: String[30]; Ngaysinh: String[8]; Diachi: String[40] Luong: Real; Tiep: Danhsach; End; Var ds1, ds2: Danh_sach; 10.1.2. Các thao tác đối với con trỏ (Pointer) a. Phép gán (:=) Hai biến cùng một kiểu con trỏ có thể gán cho nhau. Chẳng hạn, với mô tả : Var P, Q : ^ Byte; Ta có thể thực hiện phép gán : P := Q; b. So sánh hai con trỏ cùng kiểu Với dữ liệu kiểu con trỏ, chúng ta không thể thực hiện các phép toán so sánh: , = mà chỉ có thể so sánh = (bằng nhau) và so sánh <> (khác nhau). c. Hằng con trỏ NIL NIL là một giá trị hằng đặc biệt dành cho các biến con trỏ để báo con trỏ không trỏ vào đâu cả. Ta có thể gán NIL cho bất kì biến con trỏ nào. Chẳng hạn khi gán P:=NIL thì P không trỏ đến dữ liệu nào cả. 10.2. Biến động (Dynamic Variable) 10.2.1. Cấp phát vùng nhớ cho biến động Để cấp phát vùng nhớ cho các biến động do con trỏ P trỏ tới ta dùng thủ tục NEW nh− sau: NEW(P); Thực chất đây là thủ tục tạo ra một vùng nhớ có kiểu và kích th−ớc do P quy định, h−ớng con trỏ P tới vùng biến động trên. Nếu trong một ch−ơng trình ta dùng n lần NEW(P) liên tục thì cuối cùng ta có n biến động, song con trỏ P sẽ chỉ vào biến động đ−ợc tạo ra lần cuối cùng. Ví dụ 2. Nếu chúng ta có dãy lệnh: NEW(P); 101
  51. P^.Ho_Ten:= ‘Nguyen Mot’; P^.dtb:=1 ; New(P); P^.Ho_Ten:= ‘Le Hai’; P^.dtb:=2; thì sau khi thực hiện dãy lệnh này trong bộ nhớ sẽ xuất hiện hiện t−ợng sau: Nguyen Mot Biến động 1 p Le Hai Biến động 2 đ−ợc tạo ra Tóm lại, sau mỗi lần dùng New(P) thì con trỏ sẽ chứa địa chỉ của P^ vừa đ−ợc tạo ra, còn các biến động đ−ợc tạo ra bằng New(P) tr−ớc đó sẽ không đ−ợc P trỏ vào nữa. Muốn truy nhập vào các biến động đ−ợc tạo ra từ tr−ớc đó, ta phải có biện pháp l−u trữ chúng lại. 10.2.2. Giải phóng hay thu hồi ô nhớ của biến động Khi một biến động không đ−ợc dùng tới nữa trong ch−ơng trình ta có thể thu hồi lại ô nhớ mà nó chiếm dụng để dùng vào việc khác bằng thủ tục DISPOSE. Để giải phóng ô nhớ của biến động P^, ta dùng lệnh : DISPOSE(P); Ví dụ 3. Var P1, P2: ^Integer; Begin New(P1); P1^:=1595; P2:= P1; Writeln(‘Nam sinh’,P2^); Dispose(P2) ; End. 10.2.3. Phân bố bộ nhớ HEAP và STACK HEAP là vùng nhớ mà Turbo Pascal dùng để l−u trữ các biến động mà nó sẽ đ−ợc tạo ra bởi hàm New. Thông th−ờng Turbo Pascal dùng tất cả các vùng nhớ tự do (th−ờng rất lớn) của máy 102
  52. PC cho HEAP. Turbo Pascal quản lí HEAP thông qua con trỏ của HEAP. Con trỏ của HEAP luôn luôn trỏ vào byte (ô nhớ) tự do đầu tiên của vùng ô nhớ còn tự do của HEAP. Mỗi lần gọi hàm New, con trỏ của Heap đ−ợc dịch chuyển về phía đỉnh của vùng ô nhớ tự do một số byte t−ơng ứng với kích th−ớc của biến động mới đ−ợc tạo ra. STACK là vùng nhớ dành cho các biến cục bộ đ−ợc ch−ơng trình con sử dụng. Kích th−ớc mặc định của nó là 10KB. Tuy vậy có thể dùng Memory Size trên bảng chọn Option để thay đổi kích th−ớc dành cho Stack. Hình d−ới đây cho thấy cách bố trí ch−ơng trình, Stack, Heap trong bộ nhớ của máy PC. Bộ nhớ ch−ơng trình và biến tĩnh Con trỏ của Stack ↓ Vùng bộ nhớ Stack Vùng ô nhớ còn tự do Con trỏ của Heap ↑ Heap : vùng ô nhớ dành cho biến động Có hai hàm để kiểm soát HEAP là MemAvail và MaxAvail. Hàm MemAvail cho tổng số byte còn rỗi trên Heap. Hàm MaxAvail cho số byte liên tục lớn nhất còn rỗi trên Heap. Các vùng nhớ còn rỗi trên Heap th−ờng bị phân thành các chuỗi nhỏ do máy cấp phát và giải toả các vùng nhớ trên Heap không theo một trật tự nào. Khi tạo biến cấp phát động trên Heap thì điều cần quan tâm là kích th−ớc của khối chứ không phải là tổng số vùng nhớ còn rỗi trên Heap. Để tránh tràn Heap tr−ớc khi cấp phát bộ nhớ cho một đối t−ợng có kích th−ớc lớn (nh− mảng, mảng bản ghi) ta nên dùng hàm MaxAvail để kiểm tra có đủ bộ nhớ không. 10.2.4. Giải toả vùng Heap Thủ tục Dispose chỉ có tác dụng xoá một biến động. Nhiều khi ta cần giải toả một vùng nhớ đang bị chiếm bởi nhiều biến, thậm chí cần xoá toàn bộ Heap. Để giải quyết yêu cầu đó ta dùng thủ tục Mark và Release. – Thủ tục MARK( ); trong đó là một con trỏ dùng nh− để đánh dấu vị trí đầu của vùng ô nhớ cần giải phóng sau này. Thủ tục này sẽ gán giá trị của con trỏ Heap cho . Sau thủ tục Mark, ta có thể dùng một loạt lời gọi hàm New để tạo các biến động khác nhau và chúng sẽ chiếm ô nhớ kể từ vị trí đã đ−ợc đánh dấu. – Thủ tục RELEASE( ); 103
  53. Thủ tục này xoá tất cả các biến động đã tạo từ khi đánh dấu bởi Mark. Ví dụ 4. Ch−ơng trình sau đây cho thấy một ứng dụng của các thủ tục Mark và Release. Program Tong; Var PMark : Pointer; Pds : Array[1 20] Of ^Integer; S, i : Integer; Begin {Danh dau vung Heap} Mark(PMark); For i:=1 to 20 Do Begin New(Pds[i]; Readln(Pds[i]^); End; S:=0; For i:=1 to 20 Do S:=S+Pds[i]^; Release(PMark); Write(‘Tong = ’,S); End. 10.2.5. Khai báo các mảng cỡ lớn Khi xử lí các bài toán thực tế, ta th−ờng phải sử dụng các mảng số thực cỡ lớn. Khi dùng lệnh New(P) ta chỉ có thể tạo đ−ợc mảng số thực có độ lớn nhiều nhất là 10922 phần tử (vì mỗi số thực kiểu real chiếm 6 byte bộ nhớ và 64 Kbyte= 65536 byte). Nh− vậy, với bộ nhớ quy −ớc là 640 Kbyte ta chỉ có thể khai báo 9 mảng số thực 10922 phần tử là cùng. Khi những mảng lớn không còn dùng đến nữa ta nên dùng lệnh Dispose(P) để giải phóng vùng nhớ trên Heap nhằm khai báo các mảng lớn khác. 10.3. Danh sách liên kết (Linhked List) Khi muốn lập một danh sách, ví dụ danh sách học viên, mà biết tr−ớc đ−ợc số ng−ời thì ta có thể sử dụng cấu trúc dữ liệu kiểu mảng. Tuy nhiên khi số phần tử của danh sách lại không đ−ợc biết tr−ớc, nếu sử dụng mảng thì bao giờ cũng cho số phần tử cực đại có thể dùng tới để khai báo mảng và nếu ta dùng không hết thì gây ra lãng phí ô nhớ có thể đang thiếu cho việc khác. Nếu ta dùng biến động thì cần đến đâu sẽ tạo ra đến đó. Hoặc nhiều khi ô nhớ bị hạn chế, nên ta không 104
  54. thể đồng thời sử dụng nhiều biến tĩnh cùng một lúc. Do đó, một trong các biện pháp khắc phục là dùng biến con trỏ để xây dựng một danh sách các phần tử móc nối với nhau gọi là danh sách liên kết. 10.3.1. Định nghĩa Danh sách liên kết là một danh sách mà các phần tử đ−ợc nối kết lại với nhau thông qua vùng liên kết của chúng. Một phần tử của danh sách liên kết bao gồm hai vùng chính: Một vùng chứa thông tin gọi là vùng Info, một vùng chứa địa chỉ gọi là vùng liên kết Link. Hình ảnh của một từ máy (hay còn gọi là nut) nh− sau: Info Link Ngoài các phần tử thuộc danh sách liên kết, ta còn dùng một biến chỉ điểm đầu First (kiểu Pointer) chứa địa chỉ của phần tử đầu tiên của danh sách liên kết. Tổ chức của danh sách liên kết nh− sau FIRST → | ↓ | ↓ | ↓ NIL Ví dụ 5. Danh sách học viên có sắp xếp theo thứ tự tăng dần đ−ợc chứa trong một danh sách liên kết nh− sau: Vị trí Họ lót Tên Liên kết 0000 Mai Thị Ph−ơng Thảo NIL 0032 Nguyễn Châu Ph−ơng 0110 0064 Lê Thị Lan 0096 0096 Võ Thành Lộc 0032 0110 Hà Hải Quân 0000 FIRST 0064 105
  55. a. Loại bỏ một phần tử trong danh sách Để loại bỏ một phần tử trong danh sách ta chỉ cần thay đổi vùng liên kết của phần tử đứng ngay tr−ớc nó. Ví dụ 6. Muốn loại bỏ tên học viên Võ Thành Lộc, ta chỉ cần sửa vùng liên kết của Lê Thị Lan từ 0096 thành 0032 và các vùng liên kết của các phần tử còn lại vẫn giữ nguyên. Kết quả ta có danh sách liên kết mới nh− sau : Vị trí Họ lót Tên Liên kết 0000 Mai Thị Ph−ơng Thảo NIL 0032 Nguyễn Châu Ph−ơng 0110 0064 Lê Thị Lan 0032 0110 Hà Hải Quân 0000 FIRST 0064 b. Thêm một phần tử mới vào danh sách Để thêm một phần tử mới vào danh sách, ta có thể chứa phần tử này ở một vùng bất kì trong bộ nhớ và cho vùng liên kết của phần tử đứng ngay sau nó. Ví dụ 7. Muốn thêm tên học viên Trần Phúc Quyền vào danh sách, ta sửa vùng liên kết của Hà Hải Quân từ 0000 thành 0200 và gán giá trị vùng liên kết của Trần Phúc Quyền là 0000. Ta có danh sách liên kết nh− sau : 106
  56. Vị trí Họ lót Tên Liên kết 0000 Mai Thị Ph−ơng Thảo NIL 0032 Nguyên Châu Ph−ơng 0110 0064 Lê Thị Lan 0096 0096 Võ Thành Lộc 0032 0110 Hà Hải Quân 0200 0200 Trần Phúc Quyền 0000 FIRST 0064 Danh sách liên kết có −u điểm: Tốc độ thực hiện các phép toán thêm vào, loại bỏ phần tử nhanh chóng, không phụ thuộc vào số phần tử của danh sách. Nó phù hợp với loại danh sách có nhiều biến động. Nh−ợc điểm : Thêm vào một vùng biến liên kết (tốn thêm bộ nhớ). 10.3.2. Các phép toán trên danh sách liên kết a. Khởi tạo danh sách liên kết Khi khởi tạo danh sách thì danh sách là rỗng, ta cho First là NIL. Giải thuật : First:=NIL; b. Thêm một phần tử vào danh sách liên kết Phần tử mới có địa chỉ là P với nội dung là Newinfor và danh sách sau của phần tử là q. Giải thuật : New(P) p^.info:=NewInfo; p^.Link:=q^.Link; {Tao 1} q^.Link:=p {Tao 2} c. Loại bỏ phần tử trong danh sách liên kết Loại bỏ phần tử có địa chỉ p ngay sau phần tử có địa chỉ q. Giải thuật : p:=q^.Link; If p<>NIL Then 107
  57. Begin q^.Link:=p^Link; Dispose(p) End. d. Tìm kiếm một phần tử trong danh sách Giả sử danh sách đ−ợc sắp xếp thứ tự tăng dần theo vùng Info. Ta tìm kiếm một phần tử có Info là X. Giải thuật : p:=First; While p X Then { } ; End; 10.3.3. Ví dụ về các danh sách liên kết Ch−ơng trình sau đây thực hiện tổ chức danh sách sinh viên và thực hiện một số thao tác trên danh sách. Độc giả có thể tìm thấy các phép xử lí trên danh sách thông qua các thủ tục trong ch−ơng trình. User Crt; Type svPointer=^sinhvien; sinhvien = Record Maso :String[6]; Hoten : String[30]; dtb : real; Next : svPointer; End; 108
  58. Var First, Last, p, q: svPointer; Masv : String[6]; Chon1 : Byte ; Traloi : Char; Procedure Menu(Var cho : Byte); Begin Window(50,14,80,25): Writeln (‘ ’); Writeln (‘ Cac thao tac ’); Writeln (‘ 1. Tao danh sach sinh vien ’); Writeln (‘ 2. Duyet danh sach sinh vien ’); Writeln (‘ 3. Bo sung vao cuoi danh sach ’); Writeln (‘ 4. Loai bo ’); Writeln (‘ 5. Cham dut ’); Writeln (‘ Chon so: ’); GotoXY(21,8); Readln(Chon); Clrscr; End; { Menu } (* *) Procedure Taosd; Var Ptr : svPointer; i:Integer ; Begin First:=NIL; i:=1 ; Repeat Write(i:3,‘>Mã số SV(Enter : Kết thúc):’); 109
  59. Readln(masv); If masv NIL Do 110
  60. Begin Writeln(i:3,’ ‘,Ptr^.maso:5,’ ‘,Ptr^.hoten:25,’ ‘,Ptr^.dtb:5:2); Ptr:=Ptr^.Next; i:=i+1; End; End; { DuyetDS } (* *) Procedure Themsv; Var Ptr:Pointer; Begin New(Ptr); Writeln(‘Nhap thong tin mot sinh vien moi’); Write(‘Mã số:’); Readln(Ptr^.maso); Write(‘Họ tên:’); Readln(Ptr^.hoten); Write(‘Điểm TB:’); Readln(Ptr^.dtb); Ptr^.Next:=NIL; Last^.Next:=Ptr; Last :=Ptr; End; { ThemSV } (* *) Procedure XoaSV; Var Timco: Boolean; Begin Write(‘Ma so sinh vien can loai khoi danh sach:’); Readln(masv); p:=First; If p NIL) And Not Timco Do 111
  61. If p^.maso=masv Then Timco:=True Else Begin q:=p; p:=p^.Next; End; If Timco Then Begin If p=First Then First:=p^.Next Else q^.Next=p^.Next; If p^.Next=NIL Then Last :=q; Dispose(p); End; End; End; { Xoa SV } (* *) Begin Clrscr; Writeln(‘ VI DU DANH SACH LIEN KET ‘); Writeln(‘ ===’); Repeat Menu(chon1); Case chon1 Of 1: TaoDS; 2: DuyetDS 3: Begin Repeat Themsv ; Write(‘Co tiep tuc khong (C/K) ?:’); Readln(Traloi); Until Upcase(Traloi)=’K’; 112
  62. End; 4: Begin Repeat XoaSV; Write(‘Co tiep tuc nua khong (C/K)? :’); Readln(Traloi); Until Upcase (Traloi)=‘K’; End; End; { Of Case } Until chon1 = 5; End. Câu hỏi – Bài tập Ch−ơng 10 1. Sử dụng hàm Radomize (Hàm khởi tạo bộ nhớ ngẫu nhiên) và hàm Random (Hàm tạo một số ngẫu nhiên trên đoạn [0,1]) để tạo một mảng ngẫu nhiên gồm 10000 phần tử. 2. Lập ch−ơng trình nhân hai ma trận A(m,n) và B(n,p) để đ−ợc ma trận tích C(m,p). Các mảng A,B,C đều khai báo d−ới dạng biến con trỏ. 3. Viết ch−ơng trình tạo một danh sách liên kết chứa các số nguyên nhập vào từ bàn phím. Từ đó viết thuật toán : a) Đếm xem danh sách có bao nhiêu nút. b) Tính giá trị trung bình của các phần tử trong danh sách. c) Xác định nút cuối cùng của danh sách đó. d) Xác định nút có giá trị lớn nhất của danh sách đó. e) Xác định nút có giá trị âm đầu tiên của danh sách đó (nếu có). f) Chèn một số nguyên X vào sau nút thứ n trong danh sách. g) Xoá 1 phần tử n trong danh sách, n là số nguyên cho tr−ớc. 4. Viết ch−ơng trình nhập vào một dãy số thực có số phần tử tuỳ ý và sắp xếp dãy số đó theo thứ tự tăng dần. 5. Viết ch−ơng trình nhập vào một dãy số thực đã đ−ợc sắp xếp theo thứ tự tăng dần (số phần tử tuỳ ý) và một số thực X. Viết ch−ơng trình chèn số X vào danh sách sao cho dãy số mới cũng có thứ tự tăng dần. 113
  63. 6. Viết ch−ơng trình nhập vào một danh sách các sinh viên (số sinh viên tuỳ ý), mỗi sinh viên có 2 tr−ờng : họ tên, tuổi. In ra danh sách đó theo thứ tự ng−ợc lại. 7. Hãy lập ch−ơng trình đọc vào hai dãy số và tổ chức chúng thành hai danh sách liên kết. Thực hiện các phép xử lí sau đây trên hai danh sách : a) Phần giao của 2 danh sách. b) Phần hợp của 2 danh sách. c) Hiệu của danh sách thứ nhất và danh sách thứ hai. Ghi chú : không cần phải tạo danh sách mới trong mỗi thuật toán. 8. Viết ch−ơng trình cho phép nhập vào 2 dãy số tăng dần và l−u vào 2 danh sách liên kết, trộn 2 danh sách trên bằng cách tạo ra một danh sách mới sao cho dãy số hợp thành cũng tăng dần. 9. Viết ch−ơng trình tạo ra 2 danh sách liên kết (tuỳ ý) và nối 2 danh sách đó lại thành 1 danh sách. 10. Viết ch−ơng trình nhập vào một dãy số và l−u trữ trong một danh sách liên kết sau đó xác định xem các phần tử danh sách có giá trị tăng dần hay không. 11. Viết ch−ơng trình để biểu diễn một số nguyên lớn (Ví dụ : 1234567891234567) thành một danh sách tuyến tính động. 12. Viết ch−ơng trình tính tổng của 2 số nguyên có độ lớn tuỳ ý. 13. Dùng cấu trúc dữ liệu để thực hiện tính n! mà không dùng đệ quy. 14. Một đa thức đã cho có thể đ−ợc biểu diễn d−ới dạng một danh sách tuyến tính động, trong đó mỗi nút của danh sách gồm 2 tr−ờng : * Tr−ờng chứa hệ số ai. * Tr−ờng chứa số mũ i (ai <> 0, ∀i). Hãy viết ch−ơng trình : a) Nhập vào 2 đa thức. b) Cộng 2 đa thức đó. c) Tính f(x) với x là 1 số cho tr−ớc. 114
  64. Chịu trách nhiệm nội dung: Ts. Nguyễn văn hòa Biên tập: Tổ công nghệ thông tin Phòng khảo thí - đảm bảo chất l−ợng giáo dục Đơn vị phát hành: trung tâm đào tạo từ xa - đại học huế 115