LỜI NÓI ĐẦU
Sách này trình bày các cấu trúc dữ liệu (CTDL) và thuật toán. Các kiến thức về CTDL và thuật toán đóng vai trò quan trọng trong việc đào tạo cử nhân tin học. Sách này đựơc hình thành trên cơ sở các bài giảng về CTDL và thuật toán mà tôi đã đọc nhiều năm tại khoa Toán-Cơ-Tin học và khoa Công nghệ thông tin Đại học khoa học tự nhiên, Đại học quốc gia Hà nội. Sách được viết chủ yếu để làm tài liệu tham khảo cho sinh viên các Khoa Công nghệ thông tin, nhưng nó cũng rất bổ ích cho các độc giả khác cần có hiểu biết đầy đủ hơn về CTDL và thuật toán.
Chúng tôi mô tả các CTDL và các thuật toán trong ngôn ngữ Pascal, vì Pascal là ngôn ngữ được nhiều người biết đến và là ngôn ngữ được sử dụng nhiều để trình bày thuật toán trong sách báo.
Sách này gồm hai phần. Phần 1 nói về các CTDL, phần 2 nói về thuật toán. Nội dung của phần 1 gồm các chương sau đây. Chương 1 trình bày các khái niệm cơ bản về thuật toán và phân tích thuật toán. Chương 2 trình bày các khái niệm CTDL, mô hình dữ liệu, kiểu dữ liệu trừu tượng (DLTT). Chương 3 trình bày các mô hình dữ liệu, danh sách và các phương pháp cài đặt danh sách (bởi mảng và bởi CTDL danh sách liên kết). Hai kiểu DLTT đặc biệt quan trọng là hàng và ngăn xếp (stack) cũng được xét trong chương này. Chương này cũng trình bày một số ứng dụng của danh sách, hàng, ngăn xếp trong thiết kế thuật toán. Chương 4 trình bày mô hình dữ liệu cây, các phương pháp cài đặt cây, cây nhị phân, cây tìm kiếm nhị phân và cây cân bằng. Chương 5 nói về mô hình dữ liệu tập hợp, các phương pháp cài đặt tập hợp, từ điển và cài đặt từ điển bởi bảng băm, hàng ưu tiên và cài đặt hàng ưu tiên bởi heap. Chương 6 đề cập đến phương pháp cài đặt các dạng bảng khác nhau. Các CTDL ở bộ nhớ ngoài (file băm, file chỉ số, B-cây) được trình bày trong chương 7.
Tác giả
TS Đinh Mạnh Tường
NỘI DUNG SÁCH
Chương I: Thuật toán và phân tích thuật toán
- Thuật toán
- Khái niệm thuật toán.
- Biểu diễn thuật toán.
- Các vấn đề liên quan đến thuật toán.
- Phân tích thuật toán
- Tính hiệu quả của thuật toán.
- Tại sao lại cần thuật toán có hiệu quả.
- Đánh giá thời gian thực hiện thuật toán như thế nào.
- Ký hiệu ô lớn và đánh giá thời gian thực hiện thuật toán bằng ký hiệu ô lớn.
- Các qui tắc đánh giá thời gian thực hiện thuật toán.
- Phân tích một số thuật toán.
Chương II: Kiểu dữ liệu, cấu trúc dữ liệu và mô hình dữ liệu
- Biểu diễn dữ liệu.
- Kiểu dữ liệu và cấu trúc dữ liệu.
- Hệ kiểu của ngôn ngữ Pascal.
- Mô hình dữ liệu và kiểu dữ liệu trừu tượng.
Chương III: Danh sách
- Danh sách.
- Cài đặt danh sách bởi mảng.
- Tìm kiếm trên danh sách.
- Vấn đề tìm kiếm.
- Tìm kiếm tuần tự.
- Tìm kiếm nhị phân.
- Cấu trúc dữ liệu danh sách liên kết.
- Danh sách liên kết.
- Các phép toán trên danh sách liên kết.
- So sánh hai phương pháp.
- Các dạng danh sách liên kết khác.
- Danh sách vòng tròn.
- Danh sách hai liên kết.
3.6. Ứng dụng danh sách.
- Stack
- Cài đặt stack bởi mảng.
- Cài đặt stack bởi danh sách liên kết.
- Giá trị của một biểu thức.
- Hàng.
- Hàng.
- Cài đặt hàng bởi mảng.
- Cài đặt hàng bởi mảng vòng tròn.
- Cài đặt hàng bởi danh sách liên kết.
Chương IV: Cây
- Cây và các khái niệm về cây.
- Các phép toán trên cây.
- Các phép toán cơ bản trên cây.
- Đi qua cây(Diệt cây).
- Cài đặt cây.
- Biểu diễn cây bằng danh sách các con của mỗi đỉnh.
- Biểu diễn cây bằng con trưởng và em liền kề của mỗi đỉnh.
- Biểu diễn cây bởi cha của mỗi đỉnh.
- Cây nhị phân.
- Cây tìm kiếm nhị phân.
- Thời gian thực hiện các phép toán trên cây tìm kiếm nhị phân.
- Cây cân bằng.
- Thời gian thực hiện các phép toán trên cây cân bằng.
Chương V: Tập hợp
- Tập hợp và các phép toán tập hợp.
- Cài đặt tập hợp.
- Cài đặt tập hợp bởi vecto bit.
- Cài đặt tập hợp bởi danh sách.
- Từ điển.
- Cấu trúc dữ liệu bảng băm. Cài đặt từ điển bởi bảng băm.
- Bảng băm mở.
- Bảng băm đóng.
- Phân tích và đánh giá các phương pháp băm.
- Hàng ưu tiên.
- Heap và cài đặt hàng ưu tiên bởi heap.
Chương VI: Bảng
- Kiểu dữ liệu trừu tượng bảng.
- Cài đặt bảng.
- Bảng chữ nhật.
- Bảng tam giác và bảng răng lược.
- Bảng thưa thớt.
- Trò chơi đời sống.
Chương VII: Các cấu trúc dữ liệu ở bộ nhớ ngoài.
- Mô hình tổ chức dữ liệu ở bộ nhớ ngoài.
- File băm.
- File có chỉ số.
- B-cây.
Các bạn bấm để tải file ebook sách này nhé: Tải về.
Nosomovo
