Tài liệu Giáo trình Kỹ thuật lập trình 2

MỤC LỤC

Mục lục 1

Lời nói đầu 3

Chương 1 Một số kỹ thuật – phong cách lập trình tốt 4

1.1 Cách đặt tên cho biến hàm 4

1.2 Phong cách viết mã nguồn 6

1.3 Tối ưu sự thực thi mã nguồn 8

Chương 2 Kỹ thuật đệ quy 16

2.1 Kỹ thuật đệ quy 16

2.2 Xây dựng một chương trình đệ quy 20

2.3 Các ví dụ đệ quy 21

2.4 Khử đệ quy 27

2.4.1 Tìm hiểu cơ chế thực hiện hàm đệ quy 27

2.4.2 Các trường hợp khử đệ quy đơn giản 29

2.4.3 Khử đệ quy dùng stack 31

Chương 3 Bài toán liên quan tổ hợp 37

3.1 Phương pháp sinh (kế tiếp) 37

3.1.1 Bài toán sinh dãy nhị phân độ dài n 37

3.1.2 Bài toán liệt kê tập con k phần tử 39

3.1.3 Bài toán liệt kê các hoán vị 42

3.2 Thuật toán quay lui (Back Tracking) 45

3.2.1 Thuật toán quay lui liệt kê dãy nhị phân n 47

3.2.2 Thuật toán quay lui liệt kê tập con k phần tử 48

3.2.3 Thuật toán quay lui liệt kê hoán vị n phần tử 50

3.2.4 Bài toán sắp xếp quân Hậu 51

3.2.5 Bài toán mã đi tuần 57

Chương 4 Tìm kiếm và Sắp xếp 63

4.1 Tìm kiếm 63

4.1.1 Mô tả bài toán tìm kiếm trong tin học 63

4.1.2 Tìm kiếm tuyến tính 64

4.1.3 Tìm kiếm nhị phân 65

4.1.4 Kết luận 67

4.2 Bài toán sắp xếp 67

4.3 Một số phương pháp sắp xếp cơ bản 67

4.3.1 Phương pháp chọn 67

4.3.2 Phương pháp sắp xếp nổi bọt 68

4.3.3 Phương pháp sắp xếp chèn 68

4.3.4 Phương pháp đổi chỗ trực tiếp 69

4.3.5 Phương pháp ShellSort 73

4.3.6 Phương pháp phân đoạn QuickSort 76

4.3.7 Phương pháp cơ số RadixSort 80

Chương 5 Stack - Queue 84

5.1 Giới thiệu Stack – ngăn xếp 84

5.1.1 Cài đặt Stack dùng CTDL mảng 85

5.1.2 Các ứng dụng stack 87

5.1.3 Các ví dụ minh họa 88

5.2 Giới thiệu Queue – hàng đợi 103

5.2.1 Cài đặt Queue dùng CTDL mảng 105

5.2.2 Các ứng dụng Queue 106

BÀI TẬP 114

TÀI LIỆU THAM KHẢO 121