CHƯƠNG 4: KIỂU DỮ LIỆU CÓ CẤU TRÚC

Nội dung chương 4 gồm: Đị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).
Nội dung trích xuất từ tài liệu:
CHƯƠNG 4: KIỂU DỮ LIỆU CÓ CẤU TRÚC 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 1 ̣ ̃ĐINH NGHIA 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 2SỰ ĐẶ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 3ĐẶ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 4ĐẶ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 5SỰ 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 6BIỂU DIỄN BỘ NHỚ Biểu diễn tuần tự  Biểu diễn liên kết Bộ mô tả Bộ mô tả Phần tử Phần tử Phần tử Nguyễn Văn Linh - Programming Languages - Chapter 4 7CÀ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 8VÉ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 Nguyễn Văn Linh - Programming Languages - Chapter 4 9CÀI ĐẶT VÉCTƠ (1) Tổ chức lưu trữ: Biểu diễn tuần tự. Địa chỉ cơ sở Véc tơ A Kiểu dữ liệu LB Cận dưới tập chỉ Bộ mô tả UB số Cận trên tập chỉ Kiểu phần tử số E Kích thước mỗi PT A[ LB] Các phần tử A[UB] 10CÀ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 11MẢ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. Nguyễn Văn Linh - Programming Languages - Chapter 4 12BIỂU DIỄN MA TRẬNM[1..3,-1..2] OF INTEGER Địa chỉ cơ sở Ma trận M Kiểu dữ liệu LB1 (=1) Cận dưới tập chỉ số Bộ mô tả UB1 (=3) 1 Cận trên tập chỉ số LB2 (=-1) 1 Cận dưới tập chỉ số UB2 (=2) 2 Cận trên tập chỉ số ...