Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Các khái niệm cơ bản về Cấu trúc dữ liệu và giải thuật

Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Các khái niệm cơ bản về Cấu trúc dữ liệu và giải thuật. Chương này có nội dung trình bày về: khái niệm, các vấn đề liên quan của cấu trúc dữ liệu và giải thuật; một số cấu trúc dữ liệu cơ bản; ngôn ngữ diễn đạt giải thuật; thiết kế và phân tích giải thuật;... Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Các khái niệm cơ bản về Cấu trúc dữ liệu và giải thuật 8/4/2020 BÀI GIẢNG ĐIỆN TỬ HP:CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Số TC: 3 Bộ môn: Tin học Cấu trúc dữ liệu và giải thuật 1 Giới thiệu học phần Số tín chỉ: 3 (36,9) Mục tiêu: Cung cấp: ▪ Một số khái niệm cơ bản về giải thuật và cấu trúc dữ liệu; vai trò của cấu trúc dữ liệu và giải thuật (CTDL và GT) trong hệ thống thông tin (HTTT); Một số cấu trúc dữ liệu cơ bản bao gồm: Mảng (Array), Danh sách (List), Danh sách liên kết (Linked List), Ngăn xếp (Stack) và Hàng đợi (Queue), và Cây (Tree) Cấu trúc dữ liệu và giải thuật 2 1 8/4/2020 Giới thiệu học phần Nội dung chính: Chương 1: Các khái niệm cơ bản về CTDL & GT (6t) Chương 2: Mảng và danh sách (12t) Chương 3: Cây (12t) Chương 4: Một số giải thuật sắp xếp và tìm kiếm (15t) Cấu trúc dữ liệu và giải thuật 3 Tài liệu tham khảo ❖Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật, NXB ĐHQGHN, 2008 ❖Nguyễn ĐÌnh Hóa, Cấu trúc dữ liệu và giải thuật, 2008, NXB ĐHQGHN ❖Lê Minh Hoàng, Bài giảng chuyên đề ❖https://www.tutorialspoint.com/data_structures_algorit hms/ ❖https://www.e- reading.club/bookreader.php/138793/Advanced_C.pdf. Cấu trúc dữ liệu và giải thuật 4 2 8/4/2020 Chương 1. Các khái niệm cơ bản về CTDL & GT 1.1 Cấu trúc dữ liệu 1.2 Giải thuật Cấu trúc dữ liệu và giải thuật 5 1.1 Cấu trúc dữ liệu (Data Structures) 1.1.1 Khái niệm chung 1.1.2 Các vấn đề liên quan 1.1.3 Một số cấu trúc dữ liệu cơ bản Cấu trúc dữ liệu và giải thuật 6 3 8/4/2020 1.1.1 Khái niệm chung ❖Mục tiêu của tin học? ❖Dữ liệu là gì? →Kiểu dữ liệu ? (kiểu cơ sở/ kiểu có cấu trúc phức tạp) ❖Khái niệm chung: CTDL là một cách thể hiện và tổ chức dữ liệu trong máy tính sao cho nó được sử dụng một cách có hiệu quả nhất. ❖Khái niệm khác: CTDL là một dữ liệu phức hợp, gồm nhiều thành phần dữ liệu, mỗi thành phần hoặc là dữ liệu cơ sở hoặc là một CTDL đã được xây dựng. Các thành phần dữ liệu tạo nên một CTDL được liên kết với nhau theo một cách nào đó. Cấu trúc dữ liệu và giải thuật 7 1.1.2 Các vấn đề liên quan Tầm quan trọng của việc lựa chọn CTDL ▪ Tổ chức dữ liệu : dl vào/ra/trung gian ▪ Xây dựng giải thuật →Các cách cài đặt khác nhau →Thực hiện thao tác thuận lợi/khôngthuận lợi →CTDL thay đổi → Thuật toán thay đổi Cấu trúc dữ liệu và giải thuật 8 4 8/4/2020 1.1.2 Các vấn đề liên quan Các tiêu chuẩn khi lựa chọn CTDL ▪ CTDL phải biểu diễn được đầy đủ các thông tin của bài toán. (in/out) → phản ánh đúng thực tế ▪ Cài đặt được trên máy tính và ngôn ngữ lập trình đang sử dụng ▪ Phù hợp với các thao tác của thuật toán (đặc biệt thao tác được sử dụng nhiều) → phát triển thuật toán đơn giản và đạt hiệu quả. ▪ Tiết kiệm tài nguyên Cấu trúc dữ liệu và giải thuật 9 1.1.3 Một số cấu trúc dữ liệu cơ bản ❖Mảng (array) ❖Bản ghi (record)/cấu trúc (struct) ❖Tập hợp (set) ❖Tệp (file) ❖Xâu (string) ❖….(bảng băm, danh sách liên kết) Cấu trúc dữ liệu và giải thuật 10 5 8/4/2020 1.2 Giải thuật (Algorithm) 1.2.1 Khái niệm chung 1.2.2 Ngôn ngữ diễn đạt giải thuật 1.2.3 Thiết kế và phân tích giải thuật 1.2.4 Giải thuật đệ quy Cấu trúc dữ liệu và giải thuật 11 1.2.1 Khái niệm chung ❖Thuật toán là một dãy hữu hạn các bước được sắp xếp theo một trật tự xác định, mỗi bước mô tả chính xác các phép toán hoặc hành động cần thực hiện, để giải quyết một vấn đề. ❖Thuật toán là một dãy hữu hạn các thao tác, sắp xếp theo một trật tự xác định, sau khi thực hiện, từ Input ta nhận được Output cần tìm. Cấu trúc dữ liệu và giải thuật 12 6 8/4/2020 1.2.1 Khái niệm chung ❖Các tính chất (đặc trưng) của thuật toán: ▪ Tính vào (input) ▪ Tính ra (output) ▪ Tính đơn định (xác định / đơn nghĩa) ▪ Tính đúng đắn ▪ Tính dừng (tính kết thúc / tính đóng) ▪ Tính phổ dụng ▪ Tính khả thi/hiệu quả Cấu trúc dữ liệu và giải thuật 13 1.2.2 Ngôn ngữ diễn đạt giải thuật ❖Cách liệt kê: liệt kê các bước cần thực hiện ❖Sơ đồ khối: sử dụng các hình khối oval, chữ nhật, hình thoi và mũi tên,… ❖Ngôn ngữ lập trình: dùng các ký hiệu và các quy tắc của ngôn ngữ lập trình Cấu trúc dữ liệu và giải thuật 14 7 8/4/2020 1.2.2 Ngôn ngữ diễn đạt giải thuật Ví dụ: - Input:N nguyên dương, dãy a 1,..., an. - Output : Tìm Ma ...