Cấu trúc dữ liệu (Data Structures) - Chương 1

Nội dung: - Vai trò của CTDL - Tiêu chuẩn đánh giá - Một vòng bộ nhớ - Trừu tượng hóa dữ liệu
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu (Data Structures) - Chương 1 Cấu Trúc Dữ Liệu (Data Structures) Phan Mạnh Thường LOGO 04/12/09 Thông tin về môn học Thời lượng •   Số tiết lý thuyết : 45 •   Số tiết thực hành : 30 Điều kiện •   Nắm vững ngôn ngữ C •   Các khái niệm lập trình cơ bản Mục tiêu Cung cấp các kiến thức cơ bản về •   Các cấu trúc lưu trữ dữ liệu •   Các thuật toán xử lý 12/04/09 www.lhu.edu.vn Thông tin về môn học Tài liệu tham khảo 1. Trần Hạnh Nhi và Dương Anh Đức, Giáo Trình Cấu Trúc Dữ Liệu, CĐ Công  Nghệ Thông Tin TP. HCM, 2003.  2. Chủ biên: Hoàng Kiếm, Giáo trình cấu trúc dữ liệu, ĐH KHTN, 1996.  3. Niclaus Wirth, bản dịch Algorithms+Data structures, NXB Thống Kê, 1981.  4. Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật, NXB Khoa học Kỹ Thuật, 1996.  5. Nguyễn Quốc Cường và Hoàng Đức Hải, Cấu trúc dữ liệu + Giải Thuật =  Chương Trình, NXB Giáo Dục, 1995.  6. Đinh Mạnh Tường, Cấu trúc dữ liệu và giải thuật, NXB Giáo dục, 1998 7. Nguyễn Trung Trực, Cấu trúc dữ liệu, ĐH Kỹ thuật, 1995 12/04/09 www.lhu.edu.vn Nội dung môn học Chương 1: Giới thiệu tổng quan 2 Chương 2: Các cấu trúc dữ liệu cơ bản 3 Chương 3: Cấu trúc lưu trữ ngoài 4 Chương 04: Cấu trúc dữ liệu động 5 Chương 05: Bảng băm 5 Chương 06: Cấu trúc cây 5 Chương 07: Đồ thị 12/04/09 www.lhu.edu.vn Thông tin về môn học Đánh giá Gồm 3 cột điểm: • Điểm chuyên cần (10%): điểm danh buổi học (Lưu ý: nghỉ quá 30% số tiết bị cấm thi) • Điểm kiểm tra (30%): bài tập, seminar • Điểm thi (60%): làm bài thi giấy 12/04/09 www.lhu.edu.vn Chương 1 Giới thiệu tổng quan Nội dung 1 Vai trò của CTDL 2 Tiêu chuẩn đánh giá 3 Một vòng bộ nhớ 4 Trừu tượng hóa dữ liệu Chương 1 Giới thiệu tổng quan Vai trò của CTDL  Khi giải quyết một bài toán thực tế bằng máy tính cần quan tâm đến:  Tổ chức lưu trữ dữ liệu (CTDL)  Phương pháp xử lý dữ liệu (Thuật toán) Niclaus Wirth CTDL + Thuật toán = Chương trình 12/04/09 www.lhu.edu.vn Chương 1 Giới thiệu tổng quan Vai trò của CTDL  Một CTDL được đánh giá theo các tiêu chuẩn:  Phản ánh đúng dữ liệu thực tế  Phù hợp với các thao tác xử lý trên đó  Tiết kiệm tài nguyên hệ thống 12/04/09 www.lhu.edu.vn Chương 1 Giới thiệu tổng quan Một vòng quanh bộ nhớ  Mọi dữ liệu trên máy tính đều ở dạng nhị phân  Bộ nhớ là nơi lưu trữ dữ liệu và các lệnh xử lý, bộ nhớ gồm:  RAM  Cache memory  Persistent storage Tốc độ truy xuất: Cache>>RAM>> Persistent storage  12/04/09 www.lhu.edu.vn Chương 1 Giới thiệu tổng quan Một vòng quanh bộ nhớ  Đơn vị lưu trữ trong bộ nhớ là Byte  Bộ nhớ chính gồm nhiều byte (ô nhớ), mỗi ô được đánh địa chỉ gọi là địa chỉ bộ nhớ (Memory Address) Kiểu số nguyên 2 bytes (int) 12/04/09 www.lhu.edu.vn Chương 1 Giới thiệu tổng quan Trừu tượng hóa dữ liệu  Dữ liệu trong thực tế rất đa dạng  Trừu tượng hóa dữ liệu giúp ánh xạ một nhóm byte thành một kiểu dữ liệu (Data Type)  Kiểu dữ liệu T được xác định bởi một bộ trong đó :  V (Values): tập các giá trị hợp lệ mà một đối tượng kiểu T có thể lưu trữ  O (Operations): tập các thao tác xử lý có thể thi hành trên đối tượng kiểu T 12/04/09 www.lhu.edu.vn Chương 1 Giới thiệu tổng quan Trừu tượng hóa dữ liệu Ví du:  Giả sử có kiểu dữ liệu mẫu tự = với  Vc = { a-z,A-Z}  Oc = { lấy mã ASCII của ký tự, biến đổi ký tự thường thành ký tự hoa…}  Giả sử có kiểu dữ liệu số nguyên = với  Vi = { -32768..32767}  Oi = { +, -, *, /, %} 12/04/09 www.lhu.edu.vn Chương 1 Giới thiệu tổng quan Trừu tượng hóa dữ liệu  Các thuộc tính của 1 kiểu dữ liệu bao gồm:  Tên kiểu dữ liệu  Miền giá trị  Kích thước lưu trữ  Tập các toán tử tác động lên kiểu dữ liệu 12/04/09 www.lhu.edu.vn Chương 1 Giới thiệu tổng quan Trừu tượng hóa dữ liệu Thông thường, các kiểu dữ liệu cơ bản bao gồm :  Kiểu có thứ tự rời rạc: số nguyên, ký tự, logic, liệt kê, miền con …  Kiểu không rời rạc: số thực 12/04/09 www.lhu.edu.vn Chương 1 Giới thiệu tổng quan Trừu tượng hóa dữ liệu Các kiểu dữ liệu cơ bản trong ngôn ngữ C Tên kiểu Kthước Miền giá trị Ghi chú C ...