Bài giảng Cấu trúc dữ liệu và giải thuật - ĐH Thương Mại

Bài giảng Cấu trúc dữ liệu và giải thuật gồm các nội dung chính được trình bày như sau: Tổng quan về giải thuật và Cấu trúc dữ liệu, một số cấu trúc dữ liệu cơ bản, cây và Cây tìm kiếm, một số giải thuật sắp xếp và tìm kiếm
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 - ĐH Thương Mại8/15/2017Giới thiệu học phầnSố tín chỉ: 3Mục tiêu: Cung cấpCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Các kiến thức cơ bản về cấu trúc dữ liệu và thuật toán Kỹ năng lựa chọn và xây dựng các cấu trúc dữ liệu vàthuật toán hợp lý12TMHDBộ môn: Tin họcKhoa Hệ thống Thông tin Kinh tế &Thương mại điện tử_TTài liệu tham khảoMGiới thiệu học phầnNội dung chính:R. Sedgevick, Algorithms Addison-Wesley, Bản dịchtiếng Việt: Cẩm nang thuật toán (tập 1, 2)Chương 1: Tổng quan về giải thuật và CTDLChương 2: Một số cấu trúc dữ liệu cơ bảnChương 3: Cây và Cây tìm kiếmChương 4: Một số giải thuật sắp xếp và tìm kiếmUĐỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuậtLê Minh Hoàng, Bài giảng chuyên đềHồ Sỹ Đàm, Cấu trúc dữ liệu và giải thuật3418/15/2017Chương 1. Tổng quan về giải thuật và CTDL1.1 Cấu trúc dữ liệu (Data Structures)1.1.1 Khái niệm chung1.1.2 Vai trò của CTDL1.1.3 Một số cấu trúc dữ liệu cơ bản1.1 Cấu trúc dữ liệu1.2 Giải thuật6TMHD5Ví dụM_T1.1.1 Khái niệm chungCây phả hệ:Mục tiêu của tin học?Dữ liệu là gì? Kiểu dữ liệu ?Khái niệm khác: CTDL là một dữ liệu phức hợp, gồmnhiều thành phần dữ liệu, mỗi thành phần hoặc là dữ liệucơ sở hoặc là một CTDL đã được xây dựng. Các thànhphần dữ liệu tạo nên một CTDL được liên kết với nhau theoÔng A lấy bà B có hai con trai C, D và một con gái E.Ông C kết hôn với cô F có hai con một trai G và một gái H.Ông D không lập gia đình.Cô E lấy ông I có hai gái K,L và một trai M.…UKhái niệm chung: CTDL là một cách thể hiện và tổ chứcdữ liệu trong máy tính sao cho nó được sử dụng một cáchcó hiệu quả nhất.một cách nào đó.7828/15/20171.1.2 Các vấn đề liên quan1.1.2 Vai trò của CTDLTầm quan trọng của việc lựa chọn CTDLCác tiêu chuẩn khi lựa chọn CTDL Tổ chức dữ liệu: dữ liệu vào/ra/trung gian Xây dựng giải thuậtCác cách cài đặt khác nhauThực hiện thao tác thuận lợi/khôngthuận lợi CTDL thay đổi  Thuật toán thay đổi CTDL phải biểu diễn được đầy đủ các thông tin củabài toán ( 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. Tiết kiệm tài nguyên.910TMHD Phù hợp với các thao tác của thuật toán (đặc biệt thaotác được sử dụng nhiều)  phát triển thuật toán đơngiản và đạt hiệu quả.Mảng (Array)MMảng (array)Bản ghi (record)/cấu trúc (struct)Tập hợp (set)Tệp (file)Xâu (string)….(danh sách liên kết, cây, bảng băm, …)U_T1.1.3 Một số cấu trúc dữ liệu cơ bản111238/15/20171.2 Giải thuật (Algorithm)Cấu trúc - Struct (structure)1.2.1 Khái niệm chung1.2.2 Ngôn ngữ diễn đạt giải thuật1.2.3 Thiết kế và phân tích giải thuật1.2.4 Giải thuật đệ quy14TMHD1315U Thuật toán là một dãy hữu hạn các bước đượcsắ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ầnthực hiện, để giải quyết một vấn đề.M_T1.2.1 Khái niệm chung1648/15/20171.2.1 Khái niệm chung1.2.2 Ngôn ngữ diễn đạt giải thuậtCác tính chất (đặc trưng) của thuật toán: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 quytắc của ngôn ngữ lập trìnhGiả ngôn ngữ: kết hợp giữ cú pháp của ngôn ngữlập trình và ngôn ngữ tự nhiênTính vào (input)Tính ra (output)Tính đơn định (xác định / đơn nghĩa)Tính đúng đắnTính dừng (tính kết thúc / tính đóng)Tính phổ dụngTính khả thi/hiệu quả1718TMHD_T1.2.2 Ngôn ngữ diễn đạt giải thuậtVí dụ:19Cách liệt kêBước 1. Nhập N và dãy a1, ..., anBước 2. Đặt Max = a1, i = 2;Bước 3. Nếu i > N thì đến Bước 5;Bước 4.4.1. Nếu ai > Max thì Max = ai.4.2. Đặt i=i+1 rồi quay bước 3;Bước 5. Đưa ra Max rồi kết thúc.U- Input: N nguyên dương, dãy a 1,..., an.- Output: Tìm Max của dãy đã cho.Ý tưởng:Giả thiết Max = a1. Với mỗi i, nếu ai > Max thì thay giátrị Max= ai.M1.2.2 Ngôn ngữ diễn đạt giải thuật205 ...