Ngôn ngữ lập trình Pascal 2

Ngôn ngữ lập trình Pascal 2

Mục đích, yêu cầu

• Cung cấp kiến thức về NNLT Pascal với cấu trúc dữ liệu nâng cao.

• Sử dụng phần mềm Turbo Pascal lập trình giải các bài toán giúp cho việc học tập, nghiên cứu và giảng dạy.

Nội dung

C7: Kiểu Set (tập hợp)

C8: Kiểu Record (bản ghi)

C9: Kiểu File (tệp)

C10: Kiểu Pointer (con trỏ)

 

doc 32 trang Người đăng minh_thuy Lượt xem 1632Lượt tải 1 Download
Bạn đang xem 20 trang mẫu của tài liệu "Ngôn ngữ lập trình Pascal 2", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
NGÔN NGỮ LẬP TRÌNH PASCAL 2
(03 đơn vị học trình)
Mục đích, yêu cầu
Cung cấp kiến thức về NNLT Pascal với cấu trúc dữ liệu nâng cao.
Sử dụng phần mềm Turbo Pascal lập trình giải các bài toán giúp cho việc học tập, nghiên cứu và giảng dạy.
Nội dung
C7: 	Kiểu Set (tập hợp) 
C8: 	Kiểu Record (bản ghi) 
C9: 	Kiểu File (tệp) 
C10: 	Kiểu Pointer (con trỏ) 
Tài liệu tham khảo
Nguyễn Quý Khang, Kiều Văn Hưng, Bài tập Pascal (tập 1), NXB ĐHQG Hà Nội, 2002 (hoặc Bài tập Pascal, ĐHSP Hà Nội 2).
Quách Tuấn Ngọc, Ngôn ngữ lập trình Pascal, NXBGD, 1996.
Bùi Thế Tâm, Văn Văn Tuấn Dũng, Turbo Pascal 7.0, NXB Thống kê, 1996.
Hình thức thi, kiểm tra
Thi trắc nghiệm lý thuyết + Lập trình trên máy.
Chương 7
KIỂU SET (TẬP HỢP)
 KHÁI NIỆM VÀ KHAI BÁO
Khái niệm, biểu diễn tập hợp
· Kiểu tập hợp (set) trong Pascal là một tập của những dữ liệu thuộc một kiểu vô hướng đếm được (số nguyên, kí tự, logic, đoạn con, liệt kê).
Với TP, một tập hợp có số phần tử từ 0..256 và giá trị các số từ 0..255.
· Biểu diễn tập hợp: liệt kê các phần tử trong cặp ngoặc vuông.
[1, 2, 6, 9]	(số phần tử: 4)
['A', 'a'..'z']	(số phần tử: 27)
[]	(số phần tử: 0, tập rỗng)
Khai báo
· Khai báo kiểu tập hợp 
TYPE KieuTH = Set of KieuCS;
trong đó 
KieuTH: từ tự đặt xđ kiểu tập hợp;
KieuCS: 	kiểu dữ liệu của phần tử.
· Khai báo biến tập hợp 
Cách 1 (khai báo trực tiếp biến tập hợp) 
VAR BienTH : Set of KieuCS;
Cách 2 (khai báo gián tiếp) 
VAR BienTH : KieuTH;
(Tham số hình thức của CTC phải dùng 
 Cách 2)
VD 7.1 (khai báo kiểu, biến tập hợp)
TYPE	{Khai bao kieu tap hop}
SoNguyen = Set of Byte;
ChuHoa 	 = Set of 'A' .. 'Z';
VAR	{Khai bao bien tap hop}
so : SoNguyen;
chu : ChuHoa;
kt : Set of Char;
F Chú ý
Vị trí của các phần tử trong tập hợp không có ý nghĩa ([1, 2] = [2, 1]).
Dùng lệnh gán để thay đổi giá trị cho các biến tập hợp.
Không dùng lệnh Read và Write trực tiếp cho dữ liệu kiểu tập hợp.
TH := TH + [pt];	 {Thêm pt}
if pt in TH then Write(pt); {Viết pt}
 CÁC PHÉP TOÁN
Phép hợp (+), giao (*), hiệu (-), bao hàm (IN): giống như trong toán học.
A := [1, 3];	B := [2, 3, 4]
A + B = [1, 2, 3, 4];	A * B = [3];	
A - B = [1];	B - A = [2, 4];
2 in A à FALSE
Phép so sánh (=, , =): kết quả có kiểu logic (TRUE/FALSE).
A <= B có KQ là TRUE nếu A là tập con của B, trái lại KQ là FALSE.
A >= B có KQ là TRUE nếu A bao hàm tập B, trái lại KQ là FALSE.
F Không có phép so sánh trên kiểu tập hợp trong Pascal.
 VÍ DỤ
VD 7.2 (Phân loại kí tự) Lập trình nhập vào một kí tự. Kiểm tra xem kí tự đó chữ cái, chữ số hay kí tự khác?
Hướng dẫn: khai báo biến ch kiểu Char và 2 biến ChuCai, ChuSo kiểu tập hợp kí tự, rồi gán giá trị:
ChuCai := ['A'..'Z', 'a'..'z']
ChuSo := ['0'..'9']
Nếu ch in ChuCai thì viết "là chữ cái".
Nếu ch in ChuSo thì viết "là chữ số".
Nếu ... thì viết "kí tự khác".
VD 7.3 (Bán vé máy bay, BT 6.9, tr. 187) Một máy chứa tối đa 250 hành khách, với các ghế được đánh số 1, 2, ..., 250. Lập trình bán vé máy bay, yêu cầu hiện lên các số ghế còn trống để khách lựa chọn.
Hướng dẫn: Tạo tập V = [1..250] tương ứng với số ghế trên các vé và liệt kê chúng ra màn hình.
Dùng vòng lặp không xác định để nhập số ghế mà hành khách chọn. Một số ghế đã chọn thì số đó không còn trong V và trên màn hình.
Chương 8
KIỂU RECORD (BẢN GHI)
 KHÁI NIỆM VÀ KHAI BÁO
Khái niệm
· Kiểu bản ghi (Record) là một kiểu dữ liệu có cấu trúc gồm nhiều thành phần và được gọi là field - trường.
	Mỗi trường được đặt tên và các trường có thể có các kiểu dữ liệu khác nhau.
· Kiểu bản ghi dùng để mô tả các đối tượng có cùng một số thuộc tính mà các thuộc tính có thể có kiểu dữ liệu khác nhau.
Chẳng hạn, bảng kết quả thi TSĐH gồm thông tin về các thí sinh như: họ tên, SBD, ngày sinh, giới tính, điểm môn 1, 2, 3, ... mà các thông tin này thuộc các kiểu dữ liệu khác nhau.
Khai báo
· Khai báo kiểu bản ghi 
TYPE KieuBG = RECORD
 T1 : K1;
 ...
 Tn : Kn;
 END;
trong đó 
KieuBG: từ tự đặt xđ tên kiểu bản ghi;
T1, ... Tn: 	tên các trường;
K1, ... Kn: kiểu dữ liệu của các trường.
· Khai báo biến bản ghi 
Cách 1 (khai báo trực tiếp biến bản ghi) 
VAR BienBG : RECORD
 T1 : K1;
 ...
 Tn : Kn;
 END;
Cách 2 (khai báo gián tiếp) 
VAR BienBG : KieuBG;
(Tham số hình thức của CTC phải dùng 
 Cách 2)
VD 8.1 (khai báo kiểu, biến bản ghi)
TYPE	{Khai bao kieu ban ghi}
HSTS = RECORD
hoten : String[25];
sbd : String[8];
ngaysinh : String[10];
gt : Boolean;
mon1, mon2, mon3,
tong : Real;
KQ : String[10];
 END;
HSCB = RECORD
hoten : String[25];
ngaysinh : String[10];
chucvu : String[15];
Luong : Real;
Ghichu : String[10];
 END;
VAR	{Khai bao bien ban ghi}
ts : HSTS;
cb : HSCB;
sv : Record
hoten : String[25];
lop : String[5];
tuoi : Byte
dtb: Real;
 	 End;
 SỬ DỤNG RECORD
Lệnh gán 2 biến Record cùng kiểu
A := B;
Chỉ được phép truy nhập tới các trường của biến Record
BienBG.Truong
Các thao tác truy nhập:
Nhập: 	Readln(BienBG.Truong);
Xuất: 	Write(BienBG.Truong);
Gán trị: 	BienBG.Truong := ... ;
F Chú ý
Không dùng thủ tục Read, Readln, Write, Writeln cho một biến Record.
Write(bg);	{SAI !}
Readln(bg) 	{bg - biến Record}
Không dùng các phép toán số học, logic, so sánh (= , , >, >=, <, <=) đối với các biến Record.
VD 8.2 (Dùng sai đối với biến Record).
Type
 HSSV = record
 hoten:string[20];
 dtb:real;
 end;
var s1, s2: HSSV;
begin
 	s1.hoten:= 'Mot'; s1.dtb:= 1.1;
 	s2.hoten:= 'Hai'; s2.dtb:= 2.2;
 	if (s1=s2) then writeln('s1 = s2')
 	else
 	writeln('SV1 khac SV2!');
 	Readln;
end.
VD 8.3 (Khoảng cách giữa 2 điểm) Lập trình nhập vào toạ độ 2 điểm A(xA, yA), B(xB, yB) trong hệ toạ độ đềcác. Tính d(A, B).
Hướng dẫn: 
Khai báo 2 biến A, B kiểu Record với 2 trường x, y (kiểu thực).
Tính d(A, B) theo công thức:
Sqrt(Sqr(xA-xB) + Sqr(yA-yB))
VD 8.4 (Xếp loại học bổng) Lập trình nhập vào danh sách N sinh viên (N < 1000) với các thuộc tính họ tên, ngày sinh, lớp, điểm trung bình mở rộng, học bổng. Xếp loại học bổng cho các SV theo quy định hiện hành và in kết quả ra màn hình.
Hướng dẫn: 
Khai báo 1 biến SV kiểu mảng Record, mỗi phần tử của mảng lưu trữ thông tin cho một SV.
Nhập N và dùng lệnh FOR để nhập thông tin của mỗi SV gồm họ tên, ngày sinh, lớp, điểm trung bình mở rộng vào biến SV, đồng thời dùng lệnh IF để gán trị cho trường học bổng.
Dùng lệnh FOR để in DS ra màn hình.
Lệnh WITH ... DO
 WITH BienBG DO
 begin
	T1:= ...;
	Readln(T2);
	...
	Write(Tn);
 end;
à truy nhập đơn giản tới các trường (T1, ..., Tn) của biến bản ghi (BienBG).
VD 8.4 (tiếp) Lập trình dùng With ... do ...
 RECORD CÓ CẤU TRÚC THAY ĐỔI (Tham khảo [3], tr. 140)
Chương 9
KIỂU FILE (TỆP)
CẤU TRÚC VÀ PHÂN LOẠI TỆP
Khái niệm về tệp
· Tệp (File, tập tin, hồ sơ) dữ liệu là một tập hợp các dữ liệu có liên quan với nhau, có cùng kiểu được tổ chức thành dãy, và được lưu trữ ở bộ nhớ ngoài (đĩa, băng từ).
Mỗi ô là 1 phần tử của tệp
EOF
· Tệp dùng để lưu trữ dữ liệu: dữ liệu trong tệp được dùng nhiều lần và tồn tại cả khi kết thúc chương trình hay mất điện (khác với các kiểu mảng, xâu, bản ghi,...).
· Các loại tệp trong TP: tệp văn bản (TEXT file), tệp định kiểu (Typed file), tệp không định kiểu (Untyped file).
Khai báo kiểu và biến tệp
· Khai báo kiểu tệp
 TYPE
	KieuTep = FILE OF KieuPT;	
trong đó KieuTep là một từ tự đặt xác định kiểu tệp, KieuPT là kiểu dữ liệu của phần tử (Real, String, Array, Record, ... trừ kiểu file).
· Khai báo biến tệp
Cách 1: VAR	 BienTep : KieuTep;
Cách 2: VAR BienTep : FILE OF KieuPT;
VD 9.1 (khai báo kiểu, biến tệp)
TYPE	{Đinh nghia cac kieu tep}
FileInteger = FILE OF Integer;
FileReal = FILE OF Real;
HosoSV= RECORD
 hoten: String[25];
 lop: String[5];
 dtb: Real;
END;
FHosoSV = FILE OF HosoSV;
VAR	{Khai bao cac bien tep}
F1, F2: FileInteger;	 {tep cac so nguyen}
F3: FileReal;	 {tep cac so thuc}
g: FHosoSV; 	 {tep cac ban ghi}
F4: Text;	 {tep van ban}
F5: File;	 {tep khong đinh kieu}
F6: FILE OF Char; {tep cac ki tu}
Cấu trúc và phân loại tệp
· Các phần tử của ARRAY hay RECORD được truy nhập ngẫu nhiên thông qua tên biến và chỉ số / tên trường.
Một phần tử của tệp được truy nhập thông qua giá trị của một biến đệm (tampon variable). Biến đệm được dùng để đánh dấu vị trí truy nhập hay còn gọi là cửa sổ (window) của tệp.
· Có lệnh để di chuyển cửa sổ tệp sang vị trí khác (Reset, Seek, ...).
· Mỗi tệp có một dấu hiệu kết thúc tệp - EOF (End of File).
Hàm chuẩn EOF(f) trả về TRUE nếu cửa sổ ở vị trí dấu hiệu kết thúc tệp f, trái lại hàm trả về FALSE.
Mỗi ô là 1 phần tử của tệp
Chỉ số ptử
0
1
2
...
Cửa sổ tệp
Các ptử
EOF
· Phân loại tệp theo bố trí các phần tử và cách truy nhập tệp: tệp truy nhập tuần tự (sequential access), tệp truy nhập trực tiếp (direct access).
Tệp truy nhập tuần tự: việc đọc một phần tử bắt buộc phải tuần tự đi qua các phần tử trước đó. Ghi một phần tử phải ghi vào sau phần tử cuối tệp.
Tệp truy nhập trực tiếp: để đọc/ghi, có thể đặt cửa sổ vào phần tử bất kỳ thông qua chỉ số thứ tự của phần tử trong tệp.
Trong Pascal chuẩn chỉ có tệp truy nhập tuần tự.
Chú ý:
Sự giống/khác nhau giữa mảng và tệp
ARRAY
FILE
- Tập các dữ liệu cùng kiểu
- Chứa tạm trong RAM
- Truy nhập ngẫu nhiên đến các phần tử qua chỉ số
- Số phần tử xác định khi khai báo
- Tập các dữ liệu cùng kiểu
- Lưu trữ trên đĩa, băng từ
- Truy nhập ngẫu nhiên hay tuần tự đến các phần tử qua chỉ số
- Số phần tử không xác định khi khai báo
Biến tệp đại diện cho một tệp. Việc truy xuất dữ liệu trên tệp được thể hiện qua các lệnh với thông số là biến tệp.
9.2 CÁC THAO TÁC CƠ BẢN TRÊN TỆP
Mở tệp mới để ghi dữ liệu
· Mở tệp để ghi 
ASSIGN(BienTep, TenTep);
REWRITE(BienTep);
trong đó BienTep là một biến kiểu tệp; TenTep là một xâu kí tự xác định tên của tệp (quy tắc đặt tên tệp theo quy định của hệ điều hành).
VD 9.2 (mở tệp mới để ghi)
ASSIGN(f, ’HOSOSV.DAT’);
REWRITE(f);
Gán tên tệp HOSOSV.DAT cho biến tệp f, trên đĩa sẽ có tệp HOSOSV.DAT (ở thư mục hiện tại). 
Chú ý: 
Khi mới mở, tệp sẽ rỗng (chưa có phần tử nào).
Khi mở tệp, nếu trên đĩa đã có tệp trùng tên với tệp được mở thì dữ liệu tệp cũ sẽ mất.
· Ghi vào tệp với thủ tục WRITE 
WRITE(BienTep, b1, ..., bN);
trong đó BienTep là biến tệp đã được dùng để mở tệp; b1, ..., bN là các biến (có cùng kiểu thành phần của BienTep) cần ghi vào tệp.
VD 9.3 (ghi các số nguyên 28, 8, 2006 vào tệp SN.DAT)
ASSIGN(f, ’SN.DAT’);
REWRITE(f);
x:= 28, y:= 8; z:= 2006; {x,y,z - biến Integer}
WRITE(f, x, y, z); 	{Sai: WRITE(f,28,8,2006);}
28
8
2006
EOF
Cửa sổ tệp
· Đóng tệp 
CLOSE(BienTep);
trong đó BienTep là biến tệp đã được dùng để mở tệp. Việc đóng tệp đối với tệp mới tạo nhằm đảm bảo dữ liệu đã ghi không bị mất.
VD 9.4 Lập trình nhập vào số nguyên dương N < 1000, sau đó tạo tệp SN.DAT chứa N số nguyên ngẫu nhiên.
VD 9.5 Tạo tệp chứa 100 số nguyên dương đầu tiên (sử dụng CTC).
Biến tệp dùng làm tham số trong CTC bắt buộc phải là tham biến (khai báo có VAR ở trước).
Đọc dữ liệu từ một tệp đã có
· Mở tệp để đọc 
ASSIGN(BienTep, TenTep);
RESE ... í sinh theo SBD
In bảng kết quả thi (màn hình/máy in)
Thống kê kết quả thi
· Khai báo hằng, kiểu và biến
uses Crt;
const
 fn = 'HOSOTS.DAT';
type
 HosoTS = record
 hoten: String[25];
 sbd: String[8];
 mon1, mon2, mon3, tong: Real;
 kq: String[10];
 end;
 FHosoTS = file of HosoTS;
var
 f: FHosoTS;
· Chương trình chính
BEGIN {Main Program}
 Repeat
 ClrScr;
 Writeln('CHUONG TRINH TUYEN SINH DAI HOC');
 Writeln(' ------------------------------------');
 Writeln;
 Writeln(' 1. Nhap ho so thi sinh');
 Writeln(' 2. In danh sach phong thi');
 Writeln(' 3. Tinh toan va xet ket qua');
 Writeln(' 4. Xem ket qua thi theo SBD');
 Writeln(' 5. In bang ket qua thi');
 Writeln(' 6. Thong ke ket qua thi');
 Writeln(' 7. Thoat');
 Writeln;
 Write (' Ban chon viec nao 1/2/.../7 ? ');
 CASE ReadKey OF
 '1': NhapHS(f); '2': InDSPT(f); 	'3': Tinhtoan(f);
 '4': XemKQ(f); '5': InKQ(f); 	'6': Thongke(f);
 '7': begin
 Writeln;
 Write('An phim ENTER de thoat... ');
 	 Readln;
 Halt;
 end;
 END;
 Until FALSE;
END.
· Một số CTC
procedure NhapHS(var f: FHosoTS);
var
 ts: HosoTS; ht: String[25]; i: Word;
begin
 Assign(f, fn); {$I-} Reset(f); {$I+};
 {Neu tep chua co thi tao moi}
 if IOResult 0 then Rewrite(f); 
 ClrScr;
 Writeln('Nhap ho so, go ho ten trong de ket thuc !');
 i := FileSize(f) + 1;
 repeat
 Writeln('Thi sinh thu ', i);
 Write('Ho ten: '); Readln(ht);
 if ht '' then
 begin
 ts.hoten := ht;
 Write('So bao danh: '); Readln(ts.sbd);
 Write('Diem mon 1, mon 2, mon 3: ');
 Readln(ts.mon1, ts.mon2, ts.mon3);
 Seek(f, i-1); Write(f, ts);
 i := i+1;
 end;
 until ht = '';
 Close(f);
 Write(#10#13,'So ho so trong tep ', fn, ' la: ', i,
 	 '. An phim ENTER.');
 Readln;
end;
procedure InDSPT(var f: FHosoTS);
var ts, ts1, ts2: HosoTS; i, j, n: Word; pthi, stt: Byte;
begin
 {Sap xep theo ho ten thi sinh}
 Assign(f, fn); Reset(f); {fn='HOSOTS.DAT'}
 n:= FileSize(f);
 for i:= 0 to n - 2 do
 for j:= i+1 to n - 1 do begin
 Seek(f, i); Read(f,ts1); Seek(f, j); Read(f,ts2);
 if ts1.hoten > ts2.hoten then begin
 Seek(f, j); Write(f,ts1); Seek(f, i); Write(f,ts2);
 end;
 end;
 {In danh sach phong thi}
 ClrScr;
 Seek(f, 0); {Dua con tro ve dau tep}
 pthi:= 1; {So phong thi tu 1}
 while not Eof(f) do begin
 Writeln('DANH SACH THI SINH THI TSDH NAM ...');
 Writeln(' Phong thi so: ', pthi); Writeln;
 Writeln('+----+-------------------+-------+--------+-----------+');
 Writeln('|STT| Ho va ten |SoBD|Chu ki| Ghi chu |');
 Writeln('+----+-------------------+-------+--------+-----------+');
 stt := 1;
 while (stt < 18)and(not Eof(f)) do begin {In: stt < 41}
 Read(f, ts);
 With ts do
 Writeln('|', stt: 3, '|', hoten: 25, '|', sbd: 8,
 	 '|', #32:12, '|',#32:9,'|'); 
 Inc(stt);
 end;
 Inc(pthi);
 Write(#10#13,'An phim ENTER tiep tuc... '); Readln;
 end;
 Close(f);
end;
{Tinh tong diem va xet ket qua}
procedure Tinhtoan(var f: FHosoTS); 
var
 ts: HosoTS;
begin
 Assign(f, fn); Reset(f); {fn = 'HOSOTS.DAT'}
 while not Eof(f) do
 begin
 Read(f, ts);
 ts.tong:= ts.mon1 + ts.mon2 + ts.mon3;
 if ts.tong >= 22 then ts.kq:= 'DO' else ts.kq:= 'TRUOT';
 Seek(f, FilePos(f)-1); {Dua con tro tep ve vi tri cu}
 Write(f,ts);
 end;
 Write(#10#13, 'Hoan thanh tot dep. An phim ENTER... ');
 Readln;
end;
procedure InKQ(var f: FHosoTS);
var ts, ts1, ts2: HosoTS;
 i, j, n: Word; soto, stt: Byte;
begin
 Assign(f, fn); Reset(f); {fn = 'HOSOTS.DAT'}
 {Sap xep giam theo tong diem}
 n:= FileSize(f);
 for i:= 0 to n - 2 do
 for j:= i+1 to n - 1 do
 begin
 Seek(f, i); Read(f,ts1); Seek(f, j); Read(f,ts2);
 if ts1.tong < ts2.tong then
 begin
 Seek(f, j); Write(f,ts1); Seek(f, i); Write(f,ts2);
 end;
 end;
 {In danh sach ket qua thi}
 ClrScr;
 Seek(f, 0); {Dua con tro ve dau tep}
 soto:= 1; {So to tu 1}
 while not Eof(f) do
 begin
 Writeln('KET QUA THI TUYEN SINH DAI HOC ...');
 Writeln(' To so: ', soto);
 Writeln;
 Writeln('+----+ ------------------+--------+-------+------+-------+------+---------+');
 Writeln('|STT| Ho va ten | So BD|Mon1|Mon2|Mon3|Tong|Ghi chu|');
 Writeln('+----+ ------------------+--------+-------+------+-------+------+---------+');
 stt := 1;
 while (stt < 18) and (not Eof(f)) do
 begin
 Read(f, ts);
 With ts do
 Writeln('|',stt:3,'|',hoten:25,'|',sbd:8,'|',mon1:4:1,
 '|',mon2:4:1,'|', mon3:4:1,'|',tong:4:1,'|',#32:10, '|');
 Inc(stt);
 end;
 Inc(soto);
 Write(#10#13,'An phim ENTER tiep tuc... ');
 Readln;
 end;
 Close(f);
end;
Chương 9
KIỂU CON TRỎ VÀ BIẾN ĐỘNG
10.1 KHÁI NIỆM
Biến tĩnh và biến động
· Biến tĩnh được cấp phát vùng nhớ trong DataSegment (64KB - IMB PC), tồn tại cùng với khối chương trình mà nó được khai báo.
· Biến động được lưu trữ trong vùng nhớ Heap, khi cần có thể tạo ra để chứa dữ liệu, khi không cần có thể xoá.
Biến động không có tên và do con trỏ quản lý.
Biến con trỏ
· Biến con trỏ (Pointer variable): biến đặc biệt có kích thước 2 bytes, không dùng để chứa dữ liệu mà chứa địa chỉ của biến động.
· Biến con trỏ có 2 loại: định kiểu và không định kiểu.
Biến con trỏ không định kiểu sẽ có kiểu như biến con trỏ định kiểu mà nó được gán.
· NIL: giá trị hằng đặc biệt của biến con trỏ để báo con trỏ không trỏ vào đâu.
Có thể gán Nil cho bất kì biến con trỏ nào.
10.2 KHAI BÁO
Khai báo kiểu con trỏ
TYPE
	KieuCT = ^KieuDL;	
trong đó KieuCT - từ tự đặt xác định kiểu con trỏ, KieuDL - kiểu dữ liệu của biến động do biến con trỏ quản lý (Real, String, Array, Record, ...).
Khai báo biến con trỏ
Cách 1: VAR	 BienCT : KieuCT;
Cách 2: VAR BienCT : ^KieuDL;
VD 10.1 (khai báo kiểu, biến con trỏ)
TYPE	{Định nghĩa các kiểu con trỏ}
RealPtr 	= ^Real;
svPtr 	= ^HosoSV;
HosoSV= RECORD
 hoten: String[25];
 lop: String[5];
 dtb: Real;
END;
VAR	{Khai báo các biến con trỏ}
p: RealPtr; {biến con trỏ chứa đ/c biến động kiểu Real}
sv: svPtr; { ~ kiểu HosoSV}
p2: ^Char;	 { ~ kiểu Char}
p0: Pointer; {biến con trỏ không định kiểu}
 Thâm nhập vào biến động trỏ bởi p ta viết p^
2006.1011
p
p^
Biến con trỏ p (2 bytes) chứa địa chỉ của biến động p^ (6 bytes)
10.3 GÁN VÀ SO SÁNH CON TRỎ
Phép gán (:=)
VAR
p, q: ^Char; r: Pointer;
Ta có thể thực hiện phép gán:
p:= q; {q trỏ đến vùng nhớ nào,	 p trỏ đến vùng nhớ đó}
r:= p; {r trỏ đến vùng nhớ mà p trỏ, và r có kiểu của p}
 	q:= NIL; {q không trỏ vào đâu cả}
So sánh 2 con trỏ cùng kiểu
Chỉ có 2 phép so sánh = và với kiểu con trỏ.
Giá trị của biến con trỏ không thể đọc vào từ bàn phím hay in ra màn hình, máy in.
10.4 CÁC THỦ TỤC VÀ HÀM CHUẨN
Thủ tục New(p): Cấp phát bộ nhớ cho biến động trỏ bởi biến con trỏ p.
F Nếu dùng N lần NEW(p) liên tục thì có N biến động cùng kiểu, nhưng con trỏ p chỉ trỏ vào biến động tạo ra cuối cùng. Muốn truy nhập các biến động tạo ra trước đó, phải lưu trữ địa chỉ của chúng.
Thủ tục Dispose(p): Giải phóng bộ nhớ đã cấp cho biến động trỏ bởi p.
Thủ tục Mark(p): Đánh dấu địa chỉ cần giải phóng sau này.
Thủ tục Release(p): Xoá mọi biến động được tạo ra từ khi đánh dấu bởi Mark(p).
VD 10.2 (dùng New(p), Dispose(p), Mark(p), Release(p))
VAR	{Khai báo các biến con trỏ}
p, q, r, s: ^Real; {biến con trỏ chứa đ/c biến động kiểu Real}
t: Pointer;	 {con trỏ không định kiểu}
 BEGIN
New(p);
...
Mark(t);
...
New(q);
...
New(r);
...
Release(t);
...
END.
Thủ tục GetMem(p, n): Cấp phát n bytes cho biến động trỏ bởi p.
Thủ tục FreeMem(p, n): Xoá n bytes đã cấp bằng thủ tục Getmem(p, n).
Hàm Maxavail: Cho kích thước block cực đại các bytes liên tiếp chưa dùng Heap.
Hàm Memavail: Cho tổng số bytes còn rỗi trong Heap.
VD 10.3 Lập trình tạo n < 100 biến động có kiểu số nguyên. Tính tổng các số nguyên tố trong n số đó.
VAR	A: array[1..100] of ^Integer;
N, i: Byte; S: LongInt;
Function NTO(n: Integer): Boolean;
Var i: Integer;
Begin
NTO:= FALSE;
If n < 2 then Exit;
For i:= 2 to Trunc(Sqrt(n)) do
 If n mod i = 0 then Exit;
NTO:= TRUE;
End;
BEGIN
Write(‘n = ‘) ReadLn(n);
For i:= 1 to n do
Begin
New(a[i]);
Write(‘Nhap so thu ‘, i, ‘: ‘); Readln(a[i]^);
End;
{Tinh tong cac so nguyen to}
S:= 0;
For i:= 1 to n do
 If NTO(a[i]^) then S:= S + a[i]^;
Write(‘Tong cac so nguyen to : ‘, S); Readln;
END.
10.5 Danh sách liên kết đơn
Khái niệm
· Danh sách liên kết: cấu trúc dữ liệu thích hợp cho việc thêm, bớt, ghép nối các phần tử.
· Tổ chức: vùng liên kết của phần tử thứ i chứa địa chỉ của phần tử thứ i+1 hoặc ngược lại.
Mỗi phần tử của DSLK gồm 2 phần chính: vùng chứa dữ liệu (data) và vùng chứa địa chỉ của phần tử khác (link).
Data
Link
Data
Link
Data
Link
NIL
First
TYPE	{Khai báo kiểu DSLK đơn}
DataType	= ^Real;
PtrList	= ^Item;
Item = RECORD
Data: DataType;
Link: PtrList;
 END;
· Các loại DSLK đơn: FIFO (First In First Out) - hàng đợi (Queue), LIFO (Last In First Out) - ngăn xếp (Stack).
Các thao tác cơ bản
VAR	
First, Last, p, q: PtrList;
· Tạo DSLK đơn (FIFO): 
First:= NIL;	{khởi tạo DS}
Repeat
	New(p);
	{ ... nhập/gán giá trị cho p^}
p^.Link:= NIL;
if First = NIL then 	{DS rỗng}
begin
First:= p; Last:= p;
end
else Last^.Link:= p;
Last:= p;
...............
Until Ok;
· Duyệt DSLK đơn: 
p:= First;
While p NIL do
begin
{ ... xử lý p^}
p:= p^.Link;
end;
· Tìm kiếm một phần tử trong DS (key là khóa cần tìm)
OK:= False;
p:= First;
While (p NIL) and (not OK) do
if p^.Data = key then 
begin
OK:= True;
{ ... xử lý p^}
end
else p:= p^.Link;
· Thêm một phần tử vào DS 
Thêm p vào đầu DS
 	b1. Cho vùng liên kết của p trỏ vào First;
p^.Link:= First;
 	b2. Cho First trỏ vào p.
First:= p;
Thêm vào giữa/cuối DS (p là phần tử cần thêm, q phần tử đứng ngay trước p)
b1. Cho vùng liên kết của p trỏ vào vùng liên kết của q;
p^.Link:= q^.Link;
b2. Cho vùng liên kết của q trỏ vào p;
q^.Link:= p;
· Xóa một phần tử khỏi DS 
Xóa phần tử p ở đầu DS
if First NIL then
begin
 p:= First; First:= p^.Link;
 Dispose(p);
end;
Xóa phần tử p đứng ngay sau phần tử q
p:= q^.Link;
if p NIL then
begin
q^.Link:= p^.Link;
Dispose(p);
end;
Ứng dụng
VD 10.4 Lập trình sinh ngẫu nhiên DSLK đơn có n phần tử (n <= 1000), mỗi phần tử chứa một số nguyên có trị tuyệt đối < 2008.
In DS ra màn hình;
Tìm phần tử có giá trị bằng số nguyên x nhập từ bàn phím;
Thêm phần tử y vào vị trí k, với y và k nhập từ bàn phím;
Xoá khỏi DS các số chính phương;
Sắp xếp DS theo thứ tự tăng bằng cách thay đổi mối liên kết thay vì thay đổi giá trị.
TYPE
PtrList	= ^Item;
Item = RECORD
Data: Integer;
Link: PtrList;
 END;
VAR	
First: PtrList; 
· Thủ tục tạo DS (FIFO): 
Procedure TaoDS;
var p, Last: PtrList; N, i: Integer;
begin
 	Write(‘N = ‘); Readln(N);
Randomize;
First:= NIL;	{khoi tao DS}
i:= 1;
Repeat
	New(p);
	p^.Data:= Random(1003)–Random(1003);
p^.Link:= NIL;
if First = NIL then begin 	{DS rong}
First:= p; Last:= p;
end 
else Last^.Link:= p;
Last:= p;
Inc(i);
 Until i > N;
End;
VD 10.5 Lập trình giải bài toán tuyển sinh trong Mục 9.5.
10.6 DANH SÁCH LIÊN KẾT KÉP (tham khảo)

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

  • docOn_tap_Pascal_nang_cao.doc