Bài giảng cấu trúc dữ liệu và giải thuật – Nguyễn Đức Hiển

Untitled

 

MỤC LỤC

TỔNG QUAN VỀTHUẬT TOÁN VÀ CẤU TRÚC DỮLIỆU

I.  CÁC BƯỚC CƠ BẢN KHI GIẢI QUYẾT BÀI TOÁN TIN HỌC

I.1.  Xác định bài toán

I.2.  Xác đinh cấu trúc dữ liệu

I.3.  Tìm thuật toán

I.4.  Lập trình

I.5.  Kiểm thử

I.6.  Tối ưu hoá chương trình

II.  DIỄN TẢ THUẬT TOÁN

II.1.  Dùng lưu đồ

II.2.  Dùng ngôn ngữ lập trình cụ thể

II.3.  Dùng ngôn ngữ giả

III.  THUẬT TOÁN ĐỆ QUI

III.1.  Khái niệm đệ qui

III.2.  Thuật toán đệ qui

III.3.  Hiệu lực của đệqui

III.4.  Thuật toán quay lui

IV.  ĐÁNH GIÁ THUẬT TOÁN

IV.1.  Phân tích thuật toán

IV.2.  Xác đinh độ phức tạp tính toán của thuật toán

DANH SÁCH

I.  KHÁI NIỆM DANH SÁCH

II.  BIỂU DIỄN DANH SÁCH TRÊN MÁY TÍNH

III.  MẢNG VÀ DANH SÁCH ĐẶC

III.1.  Cài đặt mảng

III.2.  Các thao tác trên danh sách

IV.  DANH SÁCH LIÊN KẾT

IV.1.  Danh sách nối đơn

IV.2.  Danh sách nối vòng

IV.3.  Danh sách nối kép

IV.4.  Đa danh sách

V.  NGĂN XẾP

V.1.  Định nghĩa ngăn xếp

V.2.  Cài đặt ngăn xếp bằng mảng

V.3.  Cài đặt ngăn xếp bằng danh sách liên kết đơn

V.4.  Ứng dụng ngăn xếp đểkhử đệ qui

VI.  HÀNG ĐỢI

VI.1.  Định nghĩa hàng đợi

VI.2.  Cài đặt hàng đợi bằng mảng

VI.3.  Cài đặt hàng đợi bằng danh sách liên kết đơn

CÂY

I.  MỘT SỐ KHÁI NIỆM VỀ CÂY

I.1.  Khái niệm

I.2.  Biểu diễn cây

I.3.  Duyệt cây

II.  CÂY NHỊ PHÂN

II.1.  Định nghĩa

II.2.  Cài đặt cây nhị phân

II.3.  Các phép duyệt cây nhị phân

III.  CÂY BIỂU DIỄN BIỂU THỨC

III.1.  Biểu diễn biểu thức dưới dạng cây

III.2.  Các ký pháp dùng cho biểu thức

III.3.  Một số thuật toán đối với biểu thức

IV.  CÂY TỔNG QUÁT

IV.1.  Cây K – phân.

IV.2.  Cây tổng quát

THUẬT TOÁN SẮP XẾP

I.  BÀI TOÁN SẮP XẾP

II.  MỘT SỐ THUẬT TOÁN SẮP XẾP ĐƠN GIẢN

II.1.  Sắp xếp kiểu chọn

II.2.  Sắp xếp kiểu nổi bọt

II.3.  Sắp xếp kiểu chèn

III.  SẮP XẾP KIỂU PHÂN ĐOẠN (QUICK SORT)

IV.  SẮP XẾP KIỂU VUN ĐỐNG

V.  MỘT SỐ THUẬT TOÁN KHÁC

V.1.  Phương pháp đếm

V.2.  Phương pháp dùng hàng đợi

V.3.  Phương pháp sắp xếp trộn

CÁC THUẬT TOÁN TÌM KIẾM

I.  BÀI TOÁN TÌM KIẾM

II.  TÌM KIẾM TUẦN TỰ

III.  TÌM KIẾM NHỊ PHÂN

IV.  PHÉP BĂM (HASH)

V.  CÂY TÌM KIẾM NHỊ PHÂN

V.1.  Định nghĩa

V.2.  Cài đặt cây tìm kiếm nhị phân

VI.  CÂY TÌM KIẾM CƠ SỐ (RADIX SEARCH TREE – RST)

BIỂU DIỄN ĐỒTHỊ

I.  MỘT SỐ KHÁI NIỆM

II.  CÁC CÁCH BIỂU DIỄN ĐỒ THỊ

II.1.  Biểu diễn đồ thị bằng ma trận kề

II.2.  Biểu diễn đồ thị bằng danh sách các đỉnh kề

III.  CÁC PHÉP DUYỆT ĐỒ THỊ (TRAVERSALS OF GRAPH)

III.1.  Duyệt theo chiều sâu (depth-first search)

III.2.  Duyệt theo chiều rộng (breadth-first search)

IV.  MỘT SỐ BÀI TOÁN TRÊN ĐỒ THỊ

IV.1.  Bài toán tìm đuờng đi ngắn nhất từmột đỉnh của đồthị

IV.2.  Tìm đường đi ngắn nhất giữa tất cảcác cặp đỉnh

TÀI LIỆU THAM KHẢO

 

Link mediafire- Bấm like để thấy link cũng như chia sẻ cho bạn bè mình

[like-gate]
http://www.mediafire.com/view/k505iifsfxlfaur/Bài_giảng_cấu_trúc_dữ_liệu_và_giải_thuật_-_Nguyễn_Đức_Hiển.pdf
[/like-gate]

Leave a Reply

Your email address will not be published. Required fields are marked *