-p[o0pppppp744444444444444444444/
ĐẠI HỌC CÔNG NGHỆ GIAO THÔNG VẬN TẢI
CẤU TRÚC DỮ LIỆU VÀ
GIẢI THUẬT
(Lưu hành nội bộ)
Chủ biên: ThS. Hoàng Thế Phương
Hà Nội, 2019
MỤC LỤC
Chương 1: Các khái niệm cơ bản .....................................................................................
4
1.1. Các thành phần cơ bản của ngôn ngữ lập trình C ...............................................
4
1.1.1. Tập ký tự .............................................................................................................
4
1.1.2. Từ khóa ...............................................................................................................
4
1.1.3. Tên ......................................................................................................................
5
1.1.4. Kiểu dữ liệu ........................................................................................................
6
1.1.5. Hằng ....................................................................................................................
9
1.1.6. Biến: ..................................................................................................................
15
1.2. Các khái niệm cơ b
ản về giải thuật .....................................................................
16
1.2.1. Khái niệm về giải thuật và c
ấu trúc dữ liệu ......................................................
16
1.2.2. Cấu trúc dữ liệu và các vấn đề li
ên quan ..........................................................
17
1.2.3. Di
ễn đạt giải thuật .............................................................................................
19
1.3. Phân tích và thiết kế giải thuật ............................................................................
24
1.3.1. Từ bài toán đến chương trình ............................................................................
24
1.3.2. Phân tích, thiết kế giải thuật .............................................................................
30
Chương 2. Các thành phần cơ bản và cấu trúc điều khiển chương trình .................. 36
2.1. Các lệnh vào ra dữ liệu .........................................................................................
36
2.1.1. Các hàm vào ra chuẩn .......................................................................................
36
2.1.2. Đưa kết quả lên màn hình .................................................................................
38
2.1.3. Vào dữ liệu từ bàn phím ...................................................................................
43
2.2. Biểu thức ................................................................................................................
48
2.2.1. Khái niệm ..........................................................................................................
48
2.2.2. Lệnh gán và biểu thức: ......................................................................................
48
2.2.3. Các phép toán....................................................................................................
49
2.2.4. Chuyển đổi kiểu giá trị : ...................................................................................
55
2.3. Cấu trúc cơ bản của chương trình.......................................................................
58
2.3.1. Lời chú thích .....................................................................................................
58
2.3.2. Lệnh và khối lệnh : ...........................................................................................
59
2.3.3. Lưu đồ thuật toán ..............................................................................................
62
1
2.3.4. Cấu trúc cơ bản của chương trình: ....................................................................
64
2.3.5. Quy tắc khi viết chương trình ...........................................................................
66
2.4. Cấu trúc điều kiện if .............................................................................................
67
2.4.1. Lệnh if-else : .....................................................................................................
67
2.4.2. Lệnh else-if : ....................................................................................................
70
2.5. Cấu trúc rẽ nhánh switch…case ..........................................................................
72
2.6. Cấu trúc lặp for : ...................................................................................................
76
2.7. Cấu trúc lặp while .................................................................................................
81
2.7.1. Cấu trúc while ...................................................................................................
81
2.7.2. Cấu trúc do-while..............................................................................................
84
2.8. Câu lệnh nhảy ........................................................................................................
86
2.8.1. Lệnh nhảy không điều kiện - toán tử goto: .......................................................
86
2.8.2. Câu lệnh break: .................................................................................................
88
2.8.3. Câu lệnh continue .............................................................................................
89
Chương 3. Hàm và con trỏ ..............................................................................................
92
3.1. Hàm ........................................................................................................................
92
3.1.1. Khái niệm, khai báo hàm ..................................................................................
92
3.1.2. Cách tổ chức hàm .............................................................................................
92
3.1.3. Cách truyền tham số khi gọi hàm .....................................................................
96
3.2. Con trỏ ..................................................................................................................
105
3.2.1. Con trỏ và địa chỉ ............................................................................................
105
3.2.2. Con trỏ và mảng một chiều .............................................................................
108
3.2.3. Con trỏ và mảng nhiều chiều ..........................................................................
114
3.2.4. Các phép toán trên con trỏ ..............................................................................
117
3.2.5. Mảng con trỏ ...................................................................................................
120
3.2.6. Con trỏ tới hàm ...............................................................................................
123
Chương 4. Cấu trúc dữ liệu ..........................................................................................
128
4.1. Mảng và danh sách ..............................................................................................
128
4.1.1. Các khái niệm .................................................................................................
128
4.1.2. Cấu trúc lưu trữ mảng .....................................................................................
130
2
4.1.3. Danh sách tuyến tính
...............................................................................................................
132
4.2. Ngăn xếp
..............................................................................................................................................
139
4.2.1. Định nghĩa ngăn xếp
...............................................................................................................
139
4.2.2. Lưu trữ ngăn xếp
.......................................................................................................................
139
4.2.3. Ứng dụng của ngăn xếp
.........................................................................................................
144
4.3. Hàng đợi
..............................................................................................................................................
146
4.3.1. Định nghĩa hàng đợi
................................................................................................................
146
4.3.2. Lưu trữ hàng đợi
.......................................................................................................................
147
4.4. Cây
..........................................................................................................................................................
152
4.4.1. Các khái niệm
.............................................................................................................................
152
4.4.2. Cây nhị phân
...............................................................................................................................
153
4.4.3. Cây tổng quát
.............................................................................................................................
157
4.5. Đồ thị
.....................................................................................................................................................
162
4.5.1. Các khái niệm
.............................................................................................................................
162
4.5.2. Biểu diễn đồ thị
.........................................................................................................................
164
4.5.3. Phép duyệt một đồ thị
.............................................................................................................
167
4.5.4. Áp dụng
........................................................................................................................................
171
Chương 5. Giải thuật sắp xếp và tìm kiếm
....................................................................................
173
5.1. Sắp xếp
.................................................................................................................................................
173
5.1.1. Đặt vấn đề
....................................................................................................................................
173
5.1.2. Sắp xếp chọn trực tiếp
............................................................................................................
173
5.1.3. Sắp xếp chèn trực tiếp
............................................................................................................
176
5.1.4. Sắp xếp đổi chỗ trực tiếp
.......................................................................................................
180
5.1.5. Sắp xếp trộn
................................................................................................................................
184
5.2. Tìm kiếm
.............................................................................................................................................
187
5.2.1. Bài toán tìm kiếm
.....................................................................................................................
187
5.2.2. Tìm kiếm tuần tự
......................................................................................................................
188
5.2.3. Tìm kiếm nhị phân
...................................................................................................................
191
3
Chương 1: Các khái niệm cơ bản
1.1. Các thành phần cơ bản của ngôn ngữ lập trình C
1.1.1. Tập ký tự
Mọi ngôn ngữ lập trình đều được xây dựng từ một bộ ký tự nào đó. Các ký tự
được nhóm lại theo nhiều cách khác nhau để tạo nên các từ. Các từ lại được liên kết với
nhau theo một qui tắc nào đó để tạo nên các câu lệnh. Một chương trình bao gồm nhiều
câu lệnh và thể hiện một thuật toán để giải một bài toán nào đó. Ngôn ngữ C được xây
dựng trên bộ ký tự sau :
26 chữ cái hoa : A B C .. Z
26 chữ cái thường : a b c .. z
10 chữ số : 0 1 2 .. 9
Các ký hiệu toán học : + - * / = ( )
Ký tự gạch nối : _
Các ký tự khác : . , : ; [ ] {} ! \ & % # $ ...
Dấu cách (space) dùng để tách các từ. Ví dụ chữ VIET NAM có 8 ký tự, còn
VIETNAM chỉ có 7 ký tự.
Chú ý :
Khi viết chương trình, ta không được sử dụng bất kỳ ký tự nào khác ngoài các ký
tự trên.
Ví dụ như khi lập chương trình giải phương trình bậc hai ax
2
+bx+c=0 , ta cần tính
biệt thức Delta= b
2
- 4ac, trong ngôn ngữ C không cho phép dùng ký tự, vì vậy ta
phải dùng ký hiệu khác để thay thế.
1.1.2. Từ khóa
Từ khoá là những từ được sử dụng để khai báo các kiểu dữ liệu, để viết các
toán tử và các câu lệnh. Bảng dưới đây liệt kê các từ khoá của TURBO C :
asm break case cdecl
char const continue
default
do double else enum
extern far float for
4