Cấu trúc dữ liệu - Chương 1: Tổng quan

Thực hiện một đề án tin học là chuyển bài toán thực tế thành bài toán có thể giải quyết trên máy tính. Một bài toán thực tế bất kỳ đều bao gồm dữ liệu và các yêu cầu xử lý trên dữ liệu đó để xây dựng một mô hình tin học phản ánh được bài toán thực tế cần chú trọng đến hai vấn đề:Tổ chức biểu diễn các đối tượng thực
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu - Chương 1: Tổng quanMôn: CẤU TRÚC DỮ LIỆU NỘI DUNG MÔN HỌC Chương 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU & GIẢI THUẬT Chương 2: KỸ THUẬT TÌM KIẾM (SEARCHING) Chương 3: KỸ THUẬT SẮP XẾP (SORTING) Chương 4: DANH SÁCH (LIST) Chương 5: CÂY (TREE) Chương 6: ÔN TẬP - KIỂM TRA (REVIEW – TEST) 2 TÀI LIỆU HỌC TẬP [1] Giáo trình & Bài Giảng Cấu trúc dữ liệu & Giải thuật – Trường CDCN4. [2] Bài giảng & Bài thực hành CTDL - Trường CDCN4. 3 TÀI LIỆU THAM KHẢO [1] Cấu trúc dữ liệu, Nguyễn Trung Trực, Trường DHBK – DHQG TP.HCM. [2] Giáo trình Cấu trúc dữ liệu 1, Trần Hạnh Nhi – Dương Anh Đức, Trường DHKHTN – DHQG TP.HCM. [3] Algorithms + Data Structures = Programs, N.Wirth, Prentice Hall, 1976. [4] Data Structures and Algorithms, Alfred V.Aho - John E.Hopcroft – Jeffrey D.Ullman, Addison-Wesley Publishing Company. [5] Algorithms (Second Edition), Robert Sedgewick, Addison-Wesley Publishing Company. 4Môn: CẤU TRÚC DỮ LIỆUChương 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 3 tiết LT 5 NỘI DUNG CHƯƠNG 11.1 Tầm quan trọng của cấu trúc dữ liệu trong một đề án tin học1.2 Các tiêu chuẩn đánh giá cấu trúc dữ liệu1.3 Các kiểu dữ liệu Khái niệm kiểu dữ liệu Các kiểu dữ liệu cơ sở Các kiểu dữ liệu có cấu trúc Kiểu dữ liệu con trỏ Kiểu tập tinBÀI TẬP 6 1.1 Tầm quan trọng của CTDL & giải thuật Thực hiện một đề án tin học là chuyển bài toán thực t ế thành bài toán có thể giải quyết trên máy tính. Một bài toán thực tế bất kỳ đều bao gồm dữ liệu và các yêucầu xử lý trên dữ liệu đó để xây dựng một mô hình tin học phảnánh được bài toán thực tế cần chú trọng đến hai vấn đề: Tổ chức biểu diễn các đối tượng thực tế: Mô hình tinhọc của bài toán, cần phải tổ chức sao cho vừa phản ánh chính xác dữ liệu thực tế,  vừa dễ dàng dùng máy tính để x ử lý.  xây dựng cấu trúc dữ liệu.  Xây dựng các thao tác xử lý d ữ liệu : Từ những yêu cầuthực tế, cần tìm ra các giải thuật tương ứng để xác định trình tựcác thao tác máy tính phải thi hành để cho ra kết qu ả mongmuốn  đây là bước xây dựng giải thuật cho bài toán. 7 1.1 Tầm quan trọng của CTDL & giải thuật* Mối quan hệ giữa cấu trúc dữ liệu và giải thuậtCấu trúc dữ liệu + Giải thuật = Chương trình Khi có cấu trúc dữ liệu tốt và giải thuật phù hợp thì xây dựng chương trình chỉ phụ thuộc thời gian. Một chương trình máy tính chỉ hoàn thiện khi có đầy đủ cấu trúc dữ liệu và giải thuật. 8 1.2 Các tiêu chuẩn đánh giá CTDLMột cấu trúc dữ liệu tốt phải thỏa mãn: Phản ánh đúng thực tế: Cần xem xét kỹ lưỡng cũng như dự trù các trạng thái biến đổi của dữ liệu trong chu trình sống để có thể chọn CTDL lưu trữ thể hiện chính xác đối tượng thực tế. Phù hợp với các thao tác trên đó: Tăng tính hiệu quả của đề án, việc phát triển các thuật toán đơn giản, tự nhiên hơn => chương trình đạt hiệu quả cao hơn về tốc độ xử lý. Tiết kiệm tài nguyên hệ thống: CTDL chỉ nên sử dụng tài nguyên hệ thống vừa đủ để đảm nhiệm được chức năng của nó. Loại tài nguyên cần quan tâm là : CPU và bộ nhớ. 9 1.2 Các tiêu chuẩn đánh giá CTDL (tt)Đánh giá độ phức tạp của thuật toán Là công việc ước lượng thời gian thực hiện của thuật toán để so sánh tương đối các thuật toán với nhau Trong thực tế, thời gian thực hiện còn phụ thuộc cấu hình máy, dữ liệu đưa vào, … Để ước lượng thời gian thực hiện thuật toán xem xét 2 trường hợp Trường hợp tốt nhất: Tmin  Trường hợp xấu nhất: Tmax  Với Tmin và Tmax  thời gian thực hiện trung bình của thuật toán Tavg 10 1.3 Các kiểu dữ liệu Máy tính chỉ có thể lưu trữ dữ liệu ở dạng nhị phân. Nếu muốn phản ánh được dữ liệu đa dạng, thì cần phải xây dựng những phép ánh xạ, những qui tắc tổ chức phức tạp che lên tầng dữ liệu nhị phân thô sơ. Nhằm đưa ra những khái niệm logic về hình thức lưu trữ khác nhau đựoc gọi là kiêu dữ liệu. Các kiểu dữ liệu cơ sở  Các kiểu dữ liệu có cấu trúc  Kiểu dữ liệu con trỏ  Kiểu tập tin  11 1.3 Các kiểu dữ liệu (tt)Định nghĩa kiểu dữ liệuKiểu dữ liệu T được xác định bởi một bộ , với: V: tập các giá trị hợp lệ mà một đối tượng kiểu T có ...