Bài giảng Cấu trúc dữ liệu - ĐH Hàng Hải VN

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.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu - ĐH Hàng Hải VN 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ỆUTÊN HỌC PHẦN : CẤU TRÚC DỮ LIỆUMÃ HỌC PHẦN : 17207TRÌNH ĐỘ ĐÀO TẠO : ĐẠI HỌC CHÍNH QUYDÙNG CHO SV NGÀNH : CÔNG NGHỆ THÔNG TIN HẢI PHÒNG - 2008 MỤC LỤCCHƢƠNG 1. CÁC KHÁI NIỆM MỞ ĐẦU .............................................................................. 1 1.1. Giải thuật và cấu trúc dữ liệu. ......................................................................................... 1 1.2. Cấu trúc dữ liệu và các vấn đề liên quan. ....................................................................... 1 1.3. Ngôn ngữ diễn đạt giải thuật. .......................................................................................... 2 1.4. Kiểu dữ liệu, cấu trúc dữ liệu, kiểu dữ liệu trừu tượng................................................... 3CHƢƠ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 2.1.1 Khái niệm .................................................................................................................. 6 2.1.2 Các thao tác của ngăn xếp ......................................................................................... 6 2.1.3 Ví dụ về hoạt động của một stack ............................................................................. 7 2.1.4 Cài đặt stack bằng mảng ............................................................................................ 7 2.1.5 Ứng dụng của stack ................................................................................................. 10 2.2. Hàng đợi - Queue .......................................................................................................... 12 2.2.1 Khái niệm ................................................................................................................ 12 2.2.2 Các thao tác cơ bản của một hàng đợi ..................................................................... 13 2.2.3 Cài đặt hàng đợi sử dụng mảng ............................................................................... 13 2.2.4 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 2.2.5 Ứng dụng của hàng đơ ̣i ........................................................................................... 16 2.3. Danh sách liên kế t – Linked list .................................................................................... 17 2.3.1 Đinḥ nghiã ............................................................................................................... 17 2.3.2 Các thao tác trên danh sách liên kế t . ....................................................................... 17 2.3.3 Cài đặt danh sách liên kết sử dụng con trỏ .............................................................. 18 2.3.4 Các kiểu danh sách liên kết khác ............................................................................. 25 2.3.5 Mô ̣t số ví du ̣ sử du ̣ng cấ u trúc danh sách liên kế t .................................................... 26 2.3.6. Cài đặt stack và queue bằng con trỏ ....................................................................... 26 2.4. Bài tập áp dụng ............................................................................................................. 26CHƢƠNG 3. CÂY (TREE). ..................................................................................................... 28 3.1. Đinh ̣ nghĩa..................................................................................................................... 28 3.1.1. Đồ thị (Graph) ........................................................................................................ 28 3.1.2. Cây (tree) ................................................................................................................ 29 3.3. Cây tìm kiế m nhi ̣phân (Binary Search Tree - BST) .................................................... 31 3.3.1. Đinḥ nghiã .............................................................................................................. 31 3.3.2. Khởi ta ̣o cây rỗng ................................................................................................... 32 3.3.3. Chèn thêm một nút mới vào cây ............................................................................. 32 3.3.4. Xóa bỏ khỏi cây một nút ........................................................................................ 33 3.3.5. Tìm kiếm trên ...