Bài giảng Cấu trúc dữ liệu cung cấp kiến thức và rèn luyện kỹ năng thực hành cấu trúc dữ liệu cho sinh viên. Bài giảng gồm có 4 chương như sau: Chương I khái niệm liên quan đến cấu trúc dữ liệu, chương II các kiểu dữ liệu trừu tượng cơ bản, chương III cây (tree), chương IV bảng băm (hash table). Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết. | BỘ GIAO THÔNG VẬN TẢI TRƢỜNG ĐẠI HỌC HÀNG HẢI BỘ MÔN KHOA HỌC MÁ Y TÍ NH KHOA CÔNG NGHỆ THÔNG TIN BÀI GIẢNG CẤU TRÚC DỮ LIỆU TÊN HỌC PHẦN CẤU TRÚC DỮ LIỆU MÃ HỌC PHẦN 17207 TRÌNH ĐỘ ĐÀO TẠO ĐẠI HỌC CHÍNH QUY DÙNG CHO SV NGÀNH CÔNG NGHỆ THÔNG TIN HẢI PHÒNG - 2008 MỤC LỤC CHƢƠNG 1. CÁC KHÁI NIỆM MỞ ĐẦU . 1 . Giải thuật và cấu trúc dữ liệu. . 1 . Cấu trúc dữ liệu và các vấn đề liên quan. . 1 . Ngôn ngữ diễn đạt giải thuật. . 2 . Kiểu dữ liệu cấu trúc dữ liệu kiểu dữ liệu trừu tƣợng. 3 CHƢƠNG 2. CÁC KIỂU DỮ LIỆU TRỪU TƢỢNG CƠ BẢN . 6 2. 1. Ngăn xế p - Stack . 6 Khái niệm . 6 Các thao tác của ngăn xếp . 6 Ví dụ về hoạt động của một stack . 7 Cài đặt stack bằng mảng . 7 Ứng dụng của stack . 10 . Hàng đợi - Queue . 12 Khái niệm . 12 Các thao tác cơ bản của một hàng đợi . 13 Cài đặt hàng đợi sử dụng mảng . 13 Ví dụ về hoạt động của hàng đợi với cài đặt bằng mảng vòng tròn . 16 Ứng dụng của hàng đơ ̣i . 16 . Danh sách liên kế t Linked list . 17 Đinḥ nghiã . 17 Các thao tác trên danh sách liên kế t . . 17 Cài đặt danh sách liên kết sử dụng con trỏ . 18 Các kiểu danh sách liên kết khác . 25 Mô ̣t số ví du ̣ sƣ̉ du ̣ng cấ u trúc danh sách liên kế t . 26 . Cài đặt stack và queue bằng con trỏ . 26 . Bài tập áp dụng . 26 CHƢƠNG 3. CÂY TREE . . 28 . Đinh ̣ nghĩa. 28 . Đồ thị Graph . 28 . Cây tree . 29 . Cây tìm kiế m nhi ̣phân Binary Search Tree - BST . 31 . Đinḥ nghiã . 31 . Khởi ta ̣o cây rỗng . 32 . Chèn thêm một nút mới vào cây . 32 . Xóa bỏ khỏi cây một nút . 33 . Tìm kiếm trên cây . 34 . Duyê ̣t cây . 35 . Cài đặt cây BST . 36 cân bằng AVL . 39 CHƢƠNG 4. BẢNG BĂM HASH TABLE . 54 4. 1. Định nghĩa bảng băm . 54 nghĩa . 54 thƣớc của bảng băm . 55 . Phân loại . 55 phép toán trên bảng băm . 57
