Bài giảng Ngôn ngữ lập trình - Chương 4: Kiểu dữ liệu có cấu trúc - Nguyễn Văn Linh

Nguyễn Văn Linh - Programing Language - Chapter 1 
1 
NGÔN NGỮ LẬP TRÌNH 
 45 tiết = 3 đơn vị học trình 
 Giảng viên: Nguyễn Văn Linh 
 E-mail: nvlinh@ctu.edu.vn 
 Tel: (84) (71) 831301 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
2 
CHƯƠNG 4:KIỂU DỮ LIỆU CÓ CẤU TRÚC 
Định nghĩa kiểu dữ liệu có cấu trúc. 
Sự đặc tả kiểu dữ liệu có cấu trúc. 
Sự cài đặt các cấu trúc dữ liệu. 
Vectơ (mảng một chiều). 
Mảng nhiều chiều. 
Mẩu tin và mẩu tin có cấu trúc thay đổi. 
Chuỗi ký tự. 
Cấu trúc dữ liệu có kích thước thay đổi (Danh sách, Con trỏ, Tập hợp, Tập tin). 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
3 
ĐỊNH NGHĨA 
Kiểu dữ liệu có cấu trúc hay còn gọi là CTDL là kiểu dữ liệu mà các ÐTDL có cấu trúc. Như vậy CTDL là một tập các ÐTDL có cấu trúc và tập các phép toán trên các ÐTDL đó. 
Các CTDL thông dụng: Mảng, chuỗi ký tự, mẩu tin, ngăn xếp, con trỏ, tập tin... 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
4 
SỰ ĐẶC TẢ 
Thuộc tính: 
Số lượng phần tử. 
Kiểu của các phần tử. 
Tên của phần tử. 
Kích thước tối đa. 
Tổ chức phần tử. 
Phép toán: 
Lựa chọn phần tử. 
Phép toán trên toàn cấu trúc. 
Thêm/bớt phần tử, tạo/hủy cấu trúc. 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
5 
ĐẶC TẢ THUỘC TÍNH 
Số lượng phần tử: Kích thước cố định, kích thước thay đổi. 
Kiểu phần tử: Đồng nhất và không đồng nhất. 
Tên của phần tử: Chỉ số, tên trường. 
Kích thước tối đa: Số lượng lớn nhất các phần tử. 
Tổ chức phần tử: Một dãy các phần tử. 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
6 
ĐẶC TẢ PHÉP TOÁN 
Phép toán lựa chọn một phần tử: Chọn trực tiếp và chọn tuần tự. 
Phép toán trên toàn cấu trúc: Gán. 
Thêm / Bớt phần tử: Làm thay đổi kích thước. 
Tạo / Hủy cấu trúc. 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
7 
SỰ CÀI ĐẶT 
Biểu diễn bộ nhớ: 
Biểu diễn tuần tự. 
Biểu diễn liên kết. 
Cài đặp phép toán chọn một phần tử: 
Chọn trực tiếp trong biểu diễn tuần tự. 
Chọn tuần tự trong biểu diễn tuần tự . 
Chọn trực tiếp trong biểu diễn liên kết. 
Chọn tuần tự trong biểu diễn liên kết. 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
8 
BIỂU DIỄN BỘ NHỚ 
Biểu diễn tuần tự 
Biểu diễn liên kết 
Bộ mô tả 
Phần tử 
Phần tử 
Bộ mô tả 
Phần tử 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
9 
CÀI ĐẶT PHÉP TOÁN 
Chọn trực tiếp trong biểu diễn tuần tự: Vị trí phần tử = địa chỉ cơ sở + độ dời. 
Chọn tuần tự trong biểu diễn tuần tự: Xác định vị trí phần tử đầu tiên. Vị trí phần tử tiếp theo = Vị trí phần tử hiện hành + Kích thước phần tử hiện hành. 
Lựa chọn trong biểu diễn liên kết: Duyệt từ đầu danh sách. 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
10 
VÉCTƠ (MẢNG MỘT CHIỀU) 
Định nghĩa: Là CTDL có kích thước cố định và đồng nhất. 
Đặc tả: 
Số lượng phần tử: Tập chỉ số. 
Kiểu của tất cả các phần tử. 
Tên phần tử: Chỉ số của phần tử. 
Phép tóan lựa chọn một phần tử: Chọn trực tiếp bằng cách chỉ ra chỉ số của phần tử. Chỉ số là giá trị của biểu thức. 
Phép toán gán. 
Ví dụ: V : ARRAY[1..10] OF REAL 
11 
CÀI ĐẶT VÉCTƠ (1) 
Tổ chức lưu trữ: Biểu diễn tuần tự. 
Véc tơ A 
LB 
UB 
Kiểu phần tử 
E 
A[ LB] 
A[UB] 
Địa chỉ cơ sở 
Bộ mô tả 
Các phần tử 
Kiểu dữ liệu 
Cận dưới tập chỉ số 
Cận trên tập chỉ số 
Kích thước mỗi PT 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
12 
CÀI ĐẶT VÉCTƠ (2) 
Phép toán lựa chọn 1 phần tử: 
Vị trí phần tử thứ i = + D + (i – LB)* E 
 là địa chỉ cơ sở. 
D là kích thước bộ mô tả. 
Phép toán gán: Copy khối ô nhớ. 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
13 
MẢNG NHIỀU CHIỀU 
Đặc tả: Mỗi chiều có một tập chỉ số. 
Cài đặt: Biểu diễn bộ nhớ tuần tự, các phần tử được lưu trũ kế tiếp nhau, nhưng có 2 cách lưu: 
Các phần tử được lưu theo trật tự dòng: Hết dòng này đến dòng khác. 
Các phần tử được lưu theo trật tự cột: Hết cột này đến cột khác. 
14 
BIỂU DIỄN MA TRẬN M [1..3,-1..2] OF INTEGER 
Cận trên tập chỉ số 1 
Cận dưới tập chỉ số 2 
Cận trên tập chỉ số 2 
Ma trận M 
LB1 (=1) 
UB1 (=3) 
LB2 (=-1) 
UB2 (=2) 
M[1,-1] 
M[1,0] 
M[1,1] 
M[1,2] 
M[3,2] 
Địa chỉ cơ sở 
Bộ mô tả 
Các phần tử 
Kiểu dữ liệu 
Cận dưới tập chỉ số 1 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
15 
CHỌN MỘT PHẦN TỬ CỦA MA TRẬN 
Vị trí của phần tử M[i,j] được tính theo công thức: 
Vị trí M[i,j] = + D + (i-LB1)*S + (j-LB2)*E 
 là địa chỉ cơ sở. 
D là kích thước bộ mô tả. 
S là kích thước 1 dòng = (UB2-LB2+1)*E. 
E là kích thước một phần tử. 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
16 
MẨU TIN 
Định nghĩa: Là CTDL có kích thước cố định và không đồng nhất. 
Đặc tả: 
Số lượng phần tử (trường). 
Tên của mỗi phần tử. 
Kiểu của mỗi phần tử. 
Phép toán chọn phần tử: Sử dụng tên PT. 
Phép gán. 
Ví dụ: 
Nhan_vien: Record 
	Ma: Integer; 
	Ho_ten: string[25]; 
	Tuoi: Integer; 
	Luong: Real; 
End. 
17 
CÀI ĐẶT MẨU TIN 
Bộ nhớ tuần tự:Một khối ô nhớ liên tục để lưu trữ cả mẩu tin. Mỗi trường được lưu trong một khối. Mỗi khối có thể có bộ mô tả riêng. 
Ví dụ: Nhan_vien 
22901 
Nguyễn Văn A 
20 
2.18 
Vị trí phần tử = + Tổng kích thước các phần tử trước đó. 
Ví dụ: Vị trí Tuoi = + Kích thước Ma + Kích thước Ho_ten 
Ma 
Ho_ten 
Tuoi 
Luong 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
18 
MẨU TIN CÓ CẤU TRÚC THAY ĐỔI 
Bài toán. 
Định nghĩa. 
Cài đặt. 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
19 
MẨU TIN CÓ CẤU TRÚC THAY ĐỔI (BÀI TOÁN) 
Ví dụ: Một xí nghiệp có hai loại công nhân: Biên chế và hợp đồng. 
Lương công nhân biên chế = Số ngày công * múc lương tối thiểu * Hệ số /20. 
Những ngày nghỉ bảo hiểm xã hội, họ được trả lương bảo hiểm. 
Lương công nhân hợp đồng = Số ngày công * đơn giá công nhật. 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
20 
ĐỊNH NGHĨA MẨU TIN CÓ CẤU TRÚC THAY ĐỔI 
Mỗi mẩu tin bao gồm hai phần: Phần tĩnh và phần động. 
Phần tĩnh gồm các trường mà tất cả các thể hiện đều có. 
Phần động sẽ có các trường khác nhau tùy theo từng thể hiện. 
Trong phần tĩnh phải có một trường dùng để phân biệt các thể hiện. 
Phép toán lựa chọn một phần tử tương tự như mẩu tin bình thường. 
21 
VÍ DỤ 
TYPE 
 Loai_Cong_Nhan = (bien_che,hop_dong); 
VAR 
 Cong_Nhan : RECORD 
 Ho_Ten: String[20]; 
 Ngay_Cong: Real; 
 Luong: Real; 
 CASE loai: Loai_Cong_Nhan OF 
 bien_che: 
 (He_So: Real; 
 Nghi_bhxh:Real); 
 hop_dong: 
 (Gia_Cong_Nhat: Real); 
 END; 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
22 
CÀI ĐẶT MẨU TIN CÓ CẤU TRÚC THAY ĐỔI 
Ho_Ten 
Ngay_Cong 
Luong 
Loai 
Gia_Cong_nhat 
Không sử dụng 
Ho_Ten 
Ngay_Cong 
Luong 
Loai 
He_So 
Nghi_BHXH 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
23 
CHUỖI KÝ TỰ 
Đặc tả thuộc tính. 
Đặc tả phép tóan. 
Cài đặt chuỗi ký tự. 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
24 
ĐẶC TẢ THUỘC TÍNH CHUỖI KÝ TỰ 
Đặc tả thuộc tính: Có ba phương pháp: 
Độ dài khai báo cố định. 
Độ dài thay đổi trong một giới hạn đã được khai báo. 
Độ dài không giới hạn. 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
25 
ĐẶC TẢ PHÉP TOÁN CHUỖI KÝ TỰ 
Đặc tả phép toán: 
Phép ghép chuỗi. 
Các phép toán quan hệ. 
Lấy chuỗi con của một chuỗi bằng cách chỉ ra ký tự đầu tiên và ký tự cuối cùng. 
Định dạng nhập - xuất. 
Chọn chuỗi con bằng cách so mẫu. 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
26 
CÀI ĐẶT CHUỖI KÝ TỰ (1) 
Độ dài khai báo cố định: Sử dụng một véctơ của các ký tự để lưu trữ một chuỗi 
Ví dụ chuỗi được khai báo có độ dài 12 nhưng chuỗi thực là “EINSTEIN”. Thì phải thêm vào 4 ký tự trắng để có độ dài 12. 
E I N S T E I N 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
27 
CÀI ĐẶT CHUỖI KÝ TỰ (2) 
Độ dài thay đổi trong giới hạn đã khai báo: Sử dụng một véctơ để lưu trữ một chuỗi và có bộ mô tả lưu cả độ dài được khai báo và độ dài thực. 
Ví dụ chuỗi được khai báo có độ dài 12 nhưng chuỗi thực là “EINSTEIN”. Sẽ có 4 ô không sử dụng. 
12 8 E I N S T E I N 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
28 
CÀI ĐẶT CHUỖI KÝ TỰ (3) 
Độ dài không cố định: Sử dụng biểu diễn liên kết có bộ mô tả lưu trữ độ dài thực của chuỗi. 
Ví dụ chuỗi cần lưu trữ là “EINSTEIN”. 
8 
E 
I 
N 
S 
E 
I 
N 
T 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
29 
CẤU TRÚC DỮ LIỆU CÓ KÍCH THƯỚC THAY ĐỔI 
Định nghĩa: Là CTDL có số phần tử thay đổi một cách động trong quá trình thực hiện chương trình. 
Một số cấu trúc điển hình: 
Danh sách. 
Ngăn xếp. 
Hàng đợi. 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
30 
CON TRỎ 
Cấp phát tĩnh, cấp phát động và con trỏ. 
Đặc tả. 
Ví dụ. 
Cài đặt. 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
31 
CON TRỎ (Cấp phát ...) 
Cấp phát tĩnh: 
Trong khi dịch. 
Nhờ khai báo biến, bộ dịch sẽ dành sẵn ô nhớ đủ để lưu trữ. 
Tự động giải phóng. 
Sử dụng nhờ tên biến 
Không tối ưu. 
Cấp phát động: 
Trong khi thực hiện. 
Người lập trình chủ động cấp phát và giải phóng. 
Sử dụng thông qua địa chỉ. 
Cần có biến con trỏ để lưu trữ địa chỉ. 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
32 
ĐẶC TẢ CON TRỎ 
Con trỏ tham chiếu đến các ĐTDL có kiểu cụ thể. 
Con trỏ tham chiếu đến các ĐTDL có kiểu bất kỳ. 
Phép toán cấp phát ô nhớ động và trả địa chỉ về cho con trỏ. 
Phép toán truy xuất tới ĐTDL được cấp phát động. 
Phép toán giải phóng ô nhớ. 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
33 
VÍ DỤ VỀ CON TRỎ (1) 
Con trỏ tham chiếu đến các ĐTDL có kiểu cụ thể 
Type 
	Sinh_vien = Record 
	Ho_ten : String[25]; 
	Tuoi : Byte; 
	End; 
Var	p : ^Sinh_vien; q : ^Integer; 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
34 
VÍ DỤ VỀ CON TRỎ (2) 
Begin 
	New(p); 
	p^.Ho_ten:= ‘Nguyen Van A’; 
	p^.tuoi := 20; 
	Writeln(p^.Ho_ten, ‘ ‘, p^.tuoi); 
	Dispose(p); 
	New(q); q^ := 3547; 
End. 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
35 
VÍ DỤ VỀ CON TRỎ (3) 
Con trỏ tham chiếu đến các ĐTDL có kiểu bất kỳ 
Type 
	Sinh_vien = Record 
	Ho_ten : String[25]; 
	Tuoi : Byte; 
	End; 
Var 	p : pointer ; 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
36 
VÍ DỤ VỀ CON TRỎ (4) 
Begin 
	GetMem(p, SizeOf(Sinh_vien)); 
	{................ } 
	FreeMem(p, SizeOf(Sinh_Vien)); 
	GetMem(p, SizeOf(Integer)); 
	{................. } 
	FreeMem(p, SizeOf(Integer)); 
End. 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
37 
CÀI ĐẶT CON TRỎ 
Địa chỉ tuyệt đối: Giá trị con trỏ là địa chỉ thực của khối ô nhớ cấp phát động. Phương pháp này thường dùng cho con trỏ tham chiếu đến một ĐTDL có kiểu cụ thể. 
Địa chỉ tương đối: Giá trị con trỏ là độ dời của khối ô nhớ cấp phát động. Địa chỉ của khối ô nhớ = địa chỉ cơ sở + giá trị con trỏ (độ dời). 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
38 
TẬP HỢP 
Đặc tả. 
Cài đặt tập hợp bằng véctơ bit. 
Cài đặt tập hợp bằng bảng băm. 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
39 
ĐẶC TẢ TẬP HỢP 
CTDL đồng nhất và có kích thước thay đổi; Không quan tâm đến thứ tự các phần tử; Giá trị các phần tử khác nhau. 
Phép toán kiểm tra một giá trị có thuộc một tập hợp? 
Thêm, Bớt phần tử. 
Hợp, giao và hiệu của hai tập hợp. 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
40 
CÀI ĐẶT TẬP HỢP BẰNG VECTO BIT 
Một tập hợp được biểu diễn bởi một véctơ các bit 0 hoặc 1. 
Phép kiểm tra. 
Phép Thêm và Bớt. 
Phép Hợp, Giao và Hiệu 
Ưu điểm: dễ dàng cài đặt. 
Nhược điểm: Không gian nhỏ. 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
41 
CÀI ĐẶT TẬP HỢPBẰNG BẢNG BĂM 
Tập hợp là một bảng băm mở. 
Phép kiểm tra. 
Phép Thêm và Bớt. 
Phép Hợp, Giao và Hiệu 
Ưu điểm: cài đặt cho tập hợp bất kỳ, các phép kiểm tra, thêm, bớt dễ thực hiện. 
Nhược điểm: khó thực hiện các phép hợp, giao, hiệu . 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
42 
TẬP TIN 
Tập tin tuần tự 
Tập tin văn bản. 
Tập tin truy xuất trực tiếp 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
43 
TẬP TIN TUẦN TỰ 
Đặc tả: một dãy tuyến tính các phần tử có cùng kiểu. Ðộ dài của tập tin là không giới hạn. Kiểu phần tử có thể là kiểu sơ cấp hoặc kiểu cấu trúc có kích thước cố định như mảng hoặc mẩu tin 
Mode read, mode write, con trỏ tập tin. 
Phép toán: open, read, write, EOF, close 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
44 
CÀI ĐẶT TẬP TIN TUẦN TỰ 
Hệ điều hành. 
Giao tiếp giữa bộ nhớ trong và bộ nhớ ngoài thông qua buffer. 
Nguyễn Văn Linh - Programming Languages - Chapter 4 
45 
CÁC LOẠI TẬP TIN KHÁC 
Tập tin văn bản: Tập tin tuần tự đặc biệt, các phần tử là kí tự. 
Tập tin truy xuất trực tiếp: Có thể nhẩy đến truy xuất phần tử bất kỳ.