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

8/15/2017<br /> <br /> Giới thiệu học phần<br /> Số tín chỉ: 3<br /> Mục tiêu: Cung cấp<br /> <br /> CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT<br /> <br />  Các kiến thức cơ bản về cấu trúc dữ liệu và thuật toán<br />  Kỹ năng lựa chọn và xây dựng các cấu trúc dữ liệu và<br /> thuật toán hợp lý<br /> <br /> 1<br /> <br /> 2<br /> <br /> TM<br /> <br /> H<br /> <br /> D<br /> <br /> Bộ môn: Tin học<br /> Khoa Hệ thống Thông tin Kinh tế &<br /> Thƣơng mại điện tử<br /> <br /> _T<br /> <br /> Tài liệu tham khảo<br /> <br /> M<br /> <br /> Giới thiệu học phần<br /> Nội dung chính:<br /> <br /> R. Sedgevick, Algorithms Addison-Wesley, Bản dịch<br /> tiếng Việt: Cẩm nang thuật toán (tập 1, 2)<br /> <br /> Chương 1: Tổng quan về giải thuật và CTDL<br /> Chương 2: Một số cấu trúc dữ liệu cơ bản<br /> Chương 3: Cây và Cây tìm kiếm<br /> Chương 4: Một số giải thuật sắp xếp và tìm kiếm<br /> <br /> U<br /> <br /> Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật<br /> Lê Minh Hoàng, Bài giảng chuyên đề<br /> <br /> Hồ Sỹ Đàm, Cấu trúc dữ liệu và giải thuật<br /> <br /> 3<br /> <br /> 4<br /> <br /> 1<br /> <br /> 8/15/2017<br /> <br /> Chƣơng 1. Tổng quan về giải thuật và CTDL<br /> <br /> 1.1 Cấu trúc dữ liệu (Data Structures)<br /> 1.1.1 Khái niệm chung<br /> 1.1.2 Vai trò của CTDL<br /> 1.1.3 Một số cấu trúc dữ liệu cơ bản<br /> <br /> 1.1 Cấu trúc dữ liệu<br /> 1.2 Giải thuật<br /> <br /> 6<br /> <br /> TM<br /> <br /> H<br /> <br /> D<br /> 5<br /> <br /> Ví dụ<br /> <br /> M<br /> <br /> _T<br /> <br /> 1.1.1 Khái niệm chung<br /> <br /> Cây phả hệ:<br /> <br /> Mục tiêu của tin học?<br /> Dữ liệu là gì? Kiểu dữ liệu ?<br /> <br /> Khái niệm khác: CTDL là một dữ liệu phức hợp, gồm<br /> nhiều thành phần dữ liệu, mỗi thành phần hoặc là dữ liệu<br /> cơ sở hoặc là một CTDL đã được xây dựng. Các thành<br /> phần dữ liệu tạo nên một CTDL được liên kết với nhau theo<br /> <br /> Ông A lấy bà B có hai con trai C, D và một con gái E.<br /> Ông C kết hôn với cô F có hai con một trai G và một gái H.<br /> Ông D không lập gia đình.<br /> Cô E lấy ông I có hai gái K,L và một trai M.<br /> …<br /> <br /> U<br /> <br /> Khái niệm chung: CTDL là một cách thể hiện và tổ chức<br /> dữ liệu trong máy tính sao cho nó đƣợc sử dụng một cách<br /> có hiệu quả nhất.<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> một cách nào đó.<br /> <br /> 7<br /> <br /> 8<br /> <br /> 2<br /> <br /> 8/15/2017<br /> <br /> 1.1.2 Các vấn đề liên quan<br /> <br /> 1.1.2 Vai trò của CTDL<br /> Tầm quan trọng của việc lựa chọn CTDL<br /> <br /> Các tiêu chuẩn khi lựa chọn CTDL<br /> <br />  Tổ chức dữ liệu: dữ liệu vào/ra/trung gian<br />  Xây dựng giải thuật<br /> Các cách cài đặt khác nhau<br /> Thực hiện thao tác thuận lợi/khôngthuận lợi<br />  CTDL thay đổi  Thuật toán thay đổi<br /> <br />  CTDL phải biểu diễn được đầy đủ các thông tin của<br /> bài toán ( phản ánh đúng thực tế).<br />  Cài đặt được trên máy tính và ngôn ngữ lập trình<br /> đang sử dụng.<br /> <br />  Tiết kiệm tài nguyên.<br /> <br /> 9<br /> <br /> 10<br /> <br /> TM<br /> <br /> H<br /> <br /> D<br /> <br />  Phù hợp với các thao tác của thuật toán (đặc biệt thao<br /> tác được sử dụng nhiều)  phát triển thuật toán đơn<br /> giản và đạt hiệu quả.<br /> <br /> Mảng (Array)<br /> <br /> M<br /> <br /> Mảng (array)<br /> Bản ghi (record)/cấu trúc (struct)<br /> Tập hợp (set)<br /> Tệp (file)<br /> Xâu (string)<br /> ….(danh sách liên kết, cây, bảng băm, …)<br /> <br /> U<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> _T<br /> <br /> 1.1.3 Một số cấu trúc dữ liệu cơ bản<br /> <br /> 11<br /> <br /> 12<br /> <br /> 3<br /> <br /> 8/15/2017<br /> <br /> 1.2 Giải thuật (Algorithm)<br /> <br /> Cấu trúc - Struct (structure)<br /> <br /> 1.2.1 Khái niệm chung<br /> 1.2.2 Ngôn ngữ diễn đạt giải thuật<br /> 1.2.3 Thiết kế và phân tích giải thuật<br /> 1.2.4 Giải thuật đệ quy<br /> <br /> 14<br /> <br /> TM<br /> <br /> H<br /> <br /> D<br /> 13<br /> <br /> 15<br /> <br /> U<br /> <br />  Thuật toán là một dãy hữu hạn các bước được<br /> sắp xếp theo một trật tự xác định, mỗi bước mô<br /> tả chính xác các phép toán hoặc hành động cần<br /> thực hiện, để giải quyết một vấn đề.<br /> <br /> M<br /> <br /> _T<br /> <br /> 1.2.1 Khái niệm chung<br /> <br /> 16<br /> <br /> 4<br /> <br /> 8/15/2017<br /> <br /> 1.2.1 Khái niệm chung<br /> <br /> 1.2.2 Ngôn ngữ diễn đạt giải thuật<br /> <br /> Các tính chất (đặc trƣng) của thuật toán:<br /> <br /> Cách liệt kê: liệt kê các bước cần thực hiện<br /> Sơ đồ khối: sử dụng các hình khối oval, chữ nhật,<br /> hình thoi và mũi tên,…<br /> Ngôn ngữ lập trình: dùng các ký hiệu và các quy<br /> tắc của ngôn ngữ lập trình<br /> Giả ngôn ngữ: kết hợp giữ cú pháp của ngôn ngữ<br /> lập trình và ngôn ngữ tự nhiên<br /> <br /> Tính vào (input)<br /> Tính ra (output)<br /> Tính đơn định (xác định / đơn nghĩa)<br /> Tính đúng đắn<br /> Tính dừng (tính kết thúc / tính đóng)<br /> Tính phổ dụng<br /> Tính khả thi/hiệu quả<br /> <br /> 17<br /> <br /> 18<br /> <br /> TM<br /> <br /> H<br /> <br /> D<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> _T<br /> <br /> 1.2.2 Ngôn ngữ diễn đạt giải thuật<br /> <br /> Ví dụ:<br /> <br /> 19<br /> <br /> Cách liệt kê<br /> Bước 1. Nhập N và dãy a1, ..., an<br /> Bước 2. Đặt Max = a1, i = 2;<br /> Bước 3. Nếu i > N thì đến Bước 5;<br /> Bước 4.<br /> 4.1. Nếu ai > Max thì Max = ai.<br /> 4.2. Đặt i=i+1 rồi quay bước 3;<br /> Bước 5. Đưa ra Max rồi kết thúc.<br /> <br /> U<br /> <br /> - Input: N nguyên dương, dãy a 1,..., an.<br /> - Output: Tìm Max của dãy đã cho.<br /> Ý tưởng:<br /> Giả thiết Max = a1. Với mỗi i, nếu ai > Max thì thay giá<br /> trị Max= ai.<br /> <br /> M<br /> <br /> 1.2.2 Ngôn ngữ diễn đạt giải thuật<br /> <br /> 20<br /> <br /> 5<br /> <br />