Bài giảng Cấu trúc dữ liệu và giải thuật (2016): Phần 1

Bài giảng Cấu trúc dữ liệu và giải thuật (2016): Phần 1 trình bày khái niệm và định nghĩa cơ bản về cấu trúc dữ liệu và giải thuật; Một số mô hình thuật toán kinh điển ứng dụng trong Công nghệ Thông tin; Trình bày về các kỹ thuật sắp xếp và tìm kiếm; Các kiểu dữ liệu tuyến tính (ngăn xếp, hàng đợi và danh sách liên kết);... Mời các bạn cùng tham khảo để nắ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 và giải thuật (2016): Phần 1 HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG KHOA CÔNG NGHỆ THÔNG TIN 1 -----------------  ---------------- BÀI GIẢNGCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Biên soạn : TS. NGUYỄN DUY PHƯƠNG Hà Nội, tháng 12/2016 LỜI NÓI ĐẦU Cấu trúc dữ liệu là phương pháp biểu diễn các đối tượng ở thế giới thực thành dữliệu được tổ chức, lưu trữ trên máy tính để phục vụ quá trình xử lý và khai thác thông tinmột cách hiệu quả. Thuật toán được hiểu là phương pháp xử lý thông tin hay dữ liệu đượcbiểu diễn bởi các cấu trúc dữ liệu một cách nhanh nhất. Sự kết hợp giữa cấu trúc dữ liệuvà thuật toán trên cấu trúc dữ liệu đem lại hiệu quả cao trong xây dựng ứng dụng. Chínhvì lý do này, Cấu trúc dữ liệu và giải thuật được xem là môn học bắt buộc mang tính chấtkinh điển của các ngành Công nghệ thông tin và Điện tử Viễn thông. Tài liệu giảng dạymôn Cấu trúc dữ liệu và giải thuật được xây dựng dựa trên nội dung chương trình khungđã được Học Viện Công Nghệ Bưu Chính Viễn Thông ban hành. Tài liệu được trình bày thành 6 chương. Trong đó, Chương 1 trình bày khái niệm vàđịnh nghĩa cơ bản về cấu trúc dữ liệu và giải thuật. Chương 2 trình bày một số mô hìnhthuật toán kinh điển ứng dụng trong Công nghệ Thông tin. Chương 3 trình bày về các kỹthuật sắp xếp và tìm kiếm. Chương 4 trình bày về các kiểu dữ liệu tuyến tính (ngăn xếp,hàng đợi và danh sách liên kết). Chương 5, 6 trình bày về các cấu trúc dữ liệu rời rạc(cây, đồ thị). Đối với với mỗi cấu trúc dữ liệu, tài liệu tập trung trình bày bốn nội dungcơ bản: định nghĩa, biểu diễn, thao tác và ứng dụng của cấu trúc dữ liệu. Ứng với mỗithuật toán, tài liệu trình bày bốn nội dung cơ bản: biểu diễn, đánh giá, thử nghiệm và càiđặt thuật toán. Trong mỗi phần của tài liệu, chúng tôi cố gắng trình bày ngắn gọn trực tiếp vào bảnchất của vấn đề, đồng thời cài đặt các thuật toán bằng ngôn ngữ lập trình C++ nhằm đạtđược ba mục tiêu chính cho người học: làm chủ được các phương pháp biểu diễn dữ liệu,nâng cao tư duy phân tích, thiết kế, đánh giá thuật toán và kỹ thuật lập trình bằng thuậttoán. Mặc dù đã rất cẩn trọng trong quá trình biên soạn, tuy nhiên tài liệu không tránhkhỏi những thiếu sót và hạn chế. Chúng tôi rất mong được sự góp ý quí báu của tất cả bạnđọc. Hà nội, tháng 12 năm 2016 MỤC LỤCLỜI NÓI ĐẦU ............................................................................................................................................................... 2MỤC LỤC ......................................................................................................................................................................iDANH MỤC CÁC BẢNG ...........................................................................................................................................ivDANH MỤC CÁC HÌNH ...........................................................................................................................................viCHƯƠNG 1. GIỚI THIỆU CHUNG ............................................................................................................................7 1.1. Kiểu và cấu trúc dữ liệu ......................................................................................................................................7 1.1.1. Kiểu dữ liệu .................................................................................................................................................7 1.1.2. Biến............................................................................................................................................................ 10 1.2. Thuật toán và một số vấn đề liên quan ............................................................................................................. 11 1.3. Biểu diễn thuật toán .......................................................................................................................................... 12 1.4. Độ phức tạp thời gian của thuật toán ................................................................................................................ 13 1.4.1. Khái niệm độ phức tạp thuật toán .............................................................................................................. 14 1.4.2. Một số qui tắc xác định độ phức tạp thuật toán ......................................................................................... 15 1.4.3. Một số dạng hàm được dùng xác định độ phức tạp thuật toán................................................................... 16 1.5. Độ phức tạp của các cấu trúc lệnh ............................................. ...