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

Tổng quan về thuật toán và cấu trúc dữ liệu, thuật toán sắp xếp, các thuật toán tìm kiếm, biểu diễn đồ thị là những nội dung chính trong "Bài giảng Cấu trúc dữ liệu và giải thuật - Nguyễn Đức Hiển". Đây là tài liệu tham khảo dành cho các bạn đang học chuyên ngành Công nghệ thông tin.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật - Nguyễn Đức Hiển ĐẠI HỌC ĐÀ NẴNG TRƯỜNG CAO ĐẲNG CÔNG NGHỆ THÔNG TIN BÀI GIẢNG CẤU TRÚC DỮ LIỆU VÀ GIẢI THẬT NGUYÃÙN ÂÆÏC HIÃØN ÂAÌ NÀÔNG − 2007 4 Cấu trúc dữ liệu và Giải thuật MỤC LỤC MỤC LỤC................................................................................................................................................................. 4 TỔNG QUAN VỀ THUẬT TOÁN VÀ CẤU TRÚC DỮ LIỆU ............................................................................ 6 I. CÁC BƯỚC CƠ BẢN KHI GIẢI QUYẾT BÀI TOÁN TIN HỌC .............................................................. 6 I.1. Xác định bài toán ............................................................................................................................... 6 I.2. Xác đinh cấu trúc dữ liệu ................................................................................................................... 6 I.3. Tìm thuật toán .................................................................................................................................... 7 I.4. Lập trình............................................................................................................................................. 8 I.5. Kiểm thử ............................................................................................................................................. 9 I.6. Tối ưu hoá chương trình .................................................................................................................. 10 II. DIỄN TẢ THUẬT TOÁN.......................................................................................................................... 11 II.1. Dùng lưu đồ...................................................................................................................................... 11 II.2. Dùng ngôn ngữ lập trình cụ thể ....................................................................................................... 12 II.3. Dùng ngôn ngữ giả........................................................................................................................... 13 III. THUẬT TOÁN ĐỆ QUI ....................................................................................................................... 16 III.1. Khái niệm đệ qui .............................................................................................................................. 16 III.2. Thuật toán đệ qui ............................................................................................................................. 16 III.3. Hiệu lực của đệ qui .......................................................................................................................... 18 III.4. Thuật toán quay lui .......................................................................................................................... 19 IV. ĐÁNH GIÁ THUẬT TOÁN ................................................................................................................. 20 IV.1. Phân tích thuật toán ......................................................................................................................... 20 IV.2. Xác đinh độ phức tạp tính toán của thuật toán ................................................................................ 22 DANH SÁCH.......................................................................................................................................................... 26 I. KHÁI NIỆM DANH SÁCH....................................................................................................................... 26 II. BIỂU DIỄN DANH SÁCH TRÊN MÁY TÍNH ........................................................................................ 27 III. MẢNG VÀ DANH SÁCH ĐẶC........................................................................................................... 27 III.1. Cài đặt mảng .................................................................................................................................... 27 III.2. Các thao tác trên danh sách............................................................................................................. 27 IV. DANH SÁCH LIÊN KẾT ..................................................................................................................... 30 IV.1. Danh sách nối đơn ........................................................................................................................... 31 IV.2. Danh sách nối vòng.......................................................................................................................... 34 IV.3. Danh sách nối kép ............................................................................................................................ 37 IV.4. Đa danh sách.................................................................................................................................... 39 V. NGĂN XẾP ............................................................................................................................................... 39 V.1. Định nghĩa ngăn xếp ........................................................................................................................ 39 V.2. Cài đặt ngăn xếp bằng mảng.......................................................... ...