Giáo trình Cấu trúc dữ liệu và giải thuật - CĐ Nghề Công Nghiệp Hà Nội

(NB) Giáo trình gồm 7 chương, đề cập đến những kiến thức cơ bản về cấu trúc dữ liệu và các giải thuật có liên quan. Từng chương trong giáo trình cũng cố gắng gắn kết và phát triển nội dung có liên quan ở các môn học trước hay ở các chương trong giáo trình với nhau, giúp sinh viên nâng cao về kỹ thuật lập trình, về chọn cấu trúc dữ liệu phù hợp và xây dựng các giải thuật giải các bài toán cơ bản.
Nội dung trích xuất từ tài liệu:
Giáo trình Cấu trúc dữ liệu và giải thuật - CĐ Nghề Công Nghiệp Hà Nội TRƯỜNG CAO ĐẲNG NGHỀ CÔNG NGHIỆP HÀ NỘI Chủ biên: Vũ Thị Kim Phượng Đồng tác giả: Nguyễn Thị Nhung GIÁO TRÌNHCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT (Lưu hành nội bộ) Hà Nội năm 2012 Tuyên bố bản quyền Giáo trình này sử dụng làm tài liệu giảng dạy nội bộtrong trường cao đẳng nghề Công nghiệp Hà Nội Trường Cao đẳng nghề Công nghiệp Hà Nội không sửdụng và không cho phép bất kỳ cá nhân hay tổ chức nào sửdụng giáo trình này với mục đích kinh doanh. Mọi trích dẫn, sử dụng giáo trình này với mục đíchkhác hay ở nơi khác đều phải được sự đồng ý bằng văn bảncủa trường Cao đẳng nghề Công nghiệp Hà Nội 0 LỜI NÓI ĐẦU Giáo trình “Cấu trúc dữ liệu và giải thuật” biên soạn dựa theo đề cươngchương trình môn học Cấu trúc dữ liệu và giải thuật thuộc chương trình đàotạo Cao đẳng nghề Quản trị mạng của trường Cao đẳng nghề Công nghiệp Hànội, ban hành năm 2011, với số tiết là 90h. Giáo trình gồm 7 chương, đề cập đến những kiến thức cơ bản về cấu trúcdữ liệu và các giải thuật có liên quan. Từng chương trong giáo trình cũng cốgắng gắn kết và phát triển nội dung có liên quan ở các môn học trước hay ởcác chương trong giáo trình với nhau, giúp sinh viên nâng cao về kỹ thuật lậptrình, về chọn cấu trúc dữ liệu phù hợp và xây dựng các giải thuật giải các bàitoán cơ bản. Giáo trình cố gắng trình bày để phục vụ cho đối tượng sinh viên nămthứ hai vừa học qua một ngôn ngữ lập trình. Trong mỗi chương đều có ví dụdiễn giải làm rõ những định nghĩa, khái niệm và đặc biệt với mỗi giải thuậtđều có mô tả và cài đặt giải thuật hoặc ví dụ áp dụng. Cuối mỗi chương lànhững câu hỏi về lý thuyết và bài tập ở mức độ dễ, vừa, giúp sinh viên củngcố kiến thức. Cùng với giáo trình này, giáo viên có thể yêu cầu sinh viên tự đọc mộtsố phần, như vậy sẽ có nhiều thời gian giảng kỹ những phần chính, khó hoặcluyện được nhiều bài tập. Bên cạnh đó cũng giúp sinh viên rèn luyện khả năngtự học của bản thân. Nhóm tác giả chân thành cảm ơn những đồng nghiệp trong khoa Côngnghệ thông tin trường Cao đẳng nghề Công nghiệp Hà nội đã tham gia xâydựng đề cương chi tiết giáo trình, đọc bản thảo và đóng góp những ý kiến quýbáu. Nhóm tác giả mong muốn nhận được những ý kiến đóng góp của bạnđọc để nâng cao chất lượng giáo trình cho lần tái bản sau. Mọi ý kiến đóng góp xin gửi về: Vũ Thị Kim Phượng Email: vkphuong2010@gmail.com Hà Nội, ngày..... tháng....năm 2012 Tham gia biên soạn giáo trình 1. Vũ Thị Kim Phượng – Chủ biên 2. Nguyễn Thị Nhung – Thành viên 1 MỤC LỤC MỤC TIÊU CỦA MÔN HỌC ............................................................ 6 NỘI DUNG CỦA MÔN HỌC ........................................................... 6 CHƯƠNG 1:TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢITHUẬT ................................................................................................................. 9 1. Khái niệm cấu trúc dữ liệu và giải thuật, cấu trúc lưu trữ và cấu trúc dữ liệu. ............................................................................................ 9 1.1. Khái niệm cấu trúc dữ liệu và giải thuật...................................... 9 1.2. Cấu trúc dữ liệu và cấu trúc lưu trữ........................................... 12 2. Cấu trúc dữ liệu............................................................................ 12 2.1. Các kiểu dữ liệu cơ bản ............................................................ 12 2.2. Các kiểu dữ liệu cấu trúc .......................................................... 13 2.3. Các kiểu dữ liệu trừu tượng ...................................................... 15 2.4. Các tiêu chuẩn đánh giá cấu trúc dữ liệu ................................... 15 2.5. Các thao tác cơ bản trên một cấu trúc dữ liệu ........................... 15 3.Giải thuật và đánh giá độ phức tạp của giải thuật ........................ 16 3.1. Giải thuật .................................................................................. 16 3.2. Biểu diễn giải thuật ................................................................... 16 3.2.1. Bằng ngôn ngữ tự nhiên .................................................... 16 3.2.2. Bằng lưu đồ giải thuật ....................................................... 17 3.2.3. Bằng ngôn ngữ diễn đạt giải thuật (mã giả) ....................... 18 3.3. Một số đặc trưng của giải thuật ................................................. 19 3.4. Đ ...