UBND TỈNH BÌNH ĐỊNH
TRƯỜNG CAO ĐẲNG NGHỀ QUY NHƠN
GIÁO TRÌNH
Môn học: CẤU TRÚC DỮ LIỆU VÀ GIẢI
THUẬT
NGHỀ: CÔNG NGHỆ THÔNG TIN
(ỨNG DỤNG PHẦN MỀM)
TRÌNH ĐỘ TRUNG CẤP NGHỀ - CAO ĐẲNG NGHỀ
Bình Định, năm 2014
UBND TỈNH BÌNH ĐỊNH
TRƯỜNG CAO ĐẲNG NGHỀ QUY NHƠN
GIÁO TRÌNH
Môn học: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
NGHỀ: CÔNG NGHỆ THÔNG TIN
(ỨNG DỤNG PHẦN MỀM)
TRÌNH ĐỘ TRUNG CẤP NGHỀ - CAO ĐẲNG NGHỀ
Ban hành kèm theo Quyết định số: /QĐ- ngày tháng năm 2014
của Hiệu trưởng trường Cao đẳng nghề Quy Nhơn
Bình Định, năm 2014
TUYÊN BỐ BẢN QUYỀN
Giáo trình này được biên soạn bởi giáo viên bộ môn Võ Thị Mỹ, khoa Công
nghệ thông tin, trường Cao đẳng nghề Quy Nhơn, sử dụng cho việc tham khảo và
giảng dạy nghề Công nghệ thông tin (ứng dụng phần mềm) tại trường Cao đẳng
nghề Quy Nhơn. Mọi hình thức sao chép, in ấn và đưa lên mạng Internet không
được sự cho phép của Hiệu trưởng trường Cao đẳng nghề Quy Nhơn là vi phạm
pháp luật.
MỤC LỤC
LỜI GIỚI THIỆU .......................................................................................... 1
CHƯƠNG 1 THIẾT KẾ VÀ PHÂN TÍCH GIẢI THUẬT ......................... 5
1.1. Mở đầu ............................................................................................ 5
1.2. Thiết kế giải thuật ............................................................................ 7
1.3. Phân tích giải thuật ........................................................................ 10
1.3.1. Phân tích tính đúng đắn .......................................................... 14
1.3.2. Phân tích tính đơn giản ........................................................... 14
1.4. Một số giải thuật cơ bản ................................................................ 14
1.4.1. Hoán vị hai phần tử ................................................................. 14
1.4.2. Tìm số lớn nhất, nhỏ nhất ....................................................... 15
1.4.3. Đệ quy ..................................................................................... 16
1.4.4. Chia để trị ................................................................................ 18
Câu hỏi và bài tập chương 1 ................................................................... 21
CHƯƠNG 2 DANH SÁCH LIÊN KẾT ..................................................... 23
2.1. Danh sách liên kết ......................................................................... 23
2.1.1. Định nghĩa một cấu trúc tự trỏ ................................................ 23
2.1.2. Khái niệm danh sách liên kết .................................................. 24
2.1.3. Định nghĩa cấu trúc dữ liệu kiểu danh sách liên kết đơn ........ 25
2.2. Các thao tác cơ bản trên danh sách liên kết đơn ........................... 25
Câu hỏi và bài tập chương 2 ................................................................... 34
CHƯƠNG 3 CÁC KIỂU DỮ LIỆU TRỪU TƯỢNG ............................... 35
3.1. Ngăn xếp ....................................................................................... 35
3.1.1. Khái niệm ................................................................................ 35
3.1.2. Cài đặt ngăn xếp...................................................................... 36
3.1.3. Một số ứng dụng của ngăn xếp ............................................... 41
3.2. Hàng đợi ........................................................................................ 43
3.2.1. Khái niệm ................................................................................ 44
3.2.2. Cài đặt hàng đợi ...................................................................... 44
3.2.3. Một số ứng dụng của hàng đợi ............................................... 47
Câu hỏi và bài tập chương 3 ................................................................... 49