ỦY BAN NHÂN DÂN TỈNH BR – VT
TRƯỜNG CAO ĐẲNG NGHỀ

GIÁO TRÌNH
MÔ ĐUN CẤU TRÚC DỮ LIỆU VÀ GIẢI 
THUẬT
NGHỀ CÔNG NGHỆ THÔNG TIN
TRÌNH ĐỘ CAO ĐẲNG 
Ban hành kèm theo Quyết định số: 01/QĐ­CĐN   ngày 04 tháng 01 năm 2016  
của Hiệu trưởng trường Cao đẳng nghề tỉnh Bà Rịa – Vũng Tàu


Bà Rịa – Vũng Tàu, năm 2016
TUYÊN BỐ BẢN QUYỀN
Tài liệu này thuộc loại sách giáo trình nên các nguồn thông tin có thể 
được phép dùng nguyên bản hoặc trích dùng cho các mục đích về đào tạo và 
tham khảo.
Mọi mục đích khác mang tính lệch lạc hoặc sử dụng với mục đích kinh  
doanh thiếu lành mạnh sẽ bị nghiêm cấm.


LỜI GIỚI THIỆU
Giáo trình cấu trúc dữ  liệu và giải thuật dùng cho học sinh hệ  Cao  
Đẳng và Trung cấp của nghề lập trình máy tính và hệ cao đẳng chuyên ngành 
công nghệ  thông tin  ứng dụng phần mềm trong trường Cao đẳng nghề  Tỉnh 
BR – VT. Nhằm cung cấp cho sinh viên các thuật toán tổng quát, danh sách 
liên kết, và các giải thuật sắp xếp, tìm kiếm. Từ  đó sinh viên sẽ  từng bước 
cải tiến thuật toán để xây dựng được những chương trình hiệu quả và có tính  
ứng dụng cao. Mục đích của giáo trình là trang bị  cho học viên những kiến 
thức và kỹ năng phân tích  xây dựng được thuật toán kết hợp với giải thuật
Để có thể nắm bắt các kiến thức học sinh cần  được trang bị các kiến 

3. Thiết kế và phân tích giải thuật 13
3.1. Thiết kế thuật toán. 13
3.2. Phân tích tính đúng đắn của giải thuật 13
3.3. Phân tích tính đơn giản 14
4. Một số ví dụ về thiết kế và phân tích giải thuật 14
BÀI 2
LÀM VIỆC VỚI CON TRỎ 17
1. Biến con trỏ 17
1.1. Khái niệm con trỏ ( pointer ) 17
1.3. Gán địa chỉ của biến cho biến con trỏ 18
1.4. Cấp phát vùng nhớ cho biến con trỏ 19
1.5. Giải phóng vùng nhớ cho biến con trỏ 19
1.6. Một số phép toán trên con trỏ 20
2. Con trỏ và mảng một chiều 21
3. Con trỏ và mảng nhiều chiều 22
BÀI 3
LÀM VIỆC VỚI KIỂU CẤU TRÚC 25
1. Khái niệm cấu trúc 25
2. Khai báo kiểu cấu trúc. 25
3. Truy nhập đến các thành phần trong biến cấu trúc 28
4. Nhập dữ liệu cho biến cấu trúc 28
BÀI 4
LÀM VIỆC VỚI KIỂU TẬP TIN 32
1. Khái niệm về tập tin 32
2. Các kiểu vào ra với tệp: 33
2.1. Khai báo biến tập tin 33
2.2. Mở tập tin 34
2.3. Đóng tập tin 35
2.4. Kiểm tra đến cuối tập tin hay chưa? 35
2.5. Di chuyển con trỏ tập tin về đầu tập tin - Hàm rewind() 36

2. Chèn một nút vào cuối danh sách 51
3. Chèn một nút vào vị trí bất kỳ 51
BÀI 9
XÓA PHẦN TỬ TRONG DANH SÁCH LIÊN KẾT 53
1. Xóa nút đầu danh sách 53
2. Xóa nút cuối danh sách 53
3. Hủy danh sách 54
BÀI 10
LÀM VIỆC VỚI NGĂN XẾP 56
1.4. Lấy một phần tử ra khỏi ngăn xếp. 58
1.5. Thêm một phần tử vào ngăn xếp. 58
2.3. Lấy một phần tử ra khỏi ngăn xếp. 59
2.4. Thêm một phần tử vào ngăn xếp. 60
2.5. Xóa phần tử ở ngăn xếp 60
BÀI 11
LÀM VIỆC VỚI HÀNG ĐỢI(QUEUE) 62
1. Biểu diễn hàng đợi dùng mảng: 63
2.4. Lấy phần tử ở ở đầu Queue 67


BÀI 12
SỬ DỤNG CÁC PHƯƠNG PHÁP SẮP XẾP 70
1. Định nghĩa bài toán sắp xếp: 70
2.3. Giải thuật: 71
3. Phương pháp sắp xếp nổi bọt 73
3.3. Giải thuật: 74
4. Phương pháp đổi chỗ trực tiếp 74
4.3. Giải thuật: 75
5. Phương pháp chèn trực tiếp( insertion sort) 77
5.3. Giải thuật: 78

Tên các bài trong mô đun

2

Giới   thiệu   cấu   trúc   dữ   liệu   và   giải 
thuật
Làm việc với con trỏ

3

Làm việc với kiểu cấu trúc

1

Thời 
gian

Hình thức 
giảng dạy

3

Tích hợp

5

Tích hợp

5



4

Tích hợp

 

Kiểm tra bài 5,6

1

 

7

Làm việc với danh sách liên kết

5

Tích hợp

8

Chèn phần tử trong danh sách liên kết

5

Tích hợp

9


Sử dụng các  phương pháp sắp xếp 
Sử dụng các phương pháp tìm kiếm 
Kiểm tra bài 12,13
Cộng

10
5
1
75

Tích hợp
Tích hợp
 
 

12
13
 
 


BÀI 1
GIỚI THIỆU CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Giới thiệu:
Giải thuật là cách phân tích 1 vấn đề, từ thực tiễn cho tới chương trình,  
cách thiết kế  một giải pháp cho vấn đề  theo cách giải quyết bằng máy tính. 
Tiếp theo, các phương pháp phân tích, đánh giá độ phức tạp và thời gian thực  
hiện giải thuật . Qua bài học này sẽ  giới thiệu một cách thật cụ  thể  về  cấu 
trúc dữ liệu và giải thuật.

dữ liệu để xử lý.
10


Dữ liệu có thể là dữ  liệu đưa vào (input data), dữ liệu trung gian hoặc  
dữ liệu đưa ra(output data). Do vậy, việc tổ chức để lưu trữ dữ liệu phục vụ 
cho chương trình có ý nghĩa rất quan trọng trong toàn bộ  hệ  thống chương  
trình. Việc xây dựng cấu trúc dữ liệu quyết định rất lớn đến chất lượng cũng  
như công sức của người lập trình trong việc thiết kế, cài đặt chương trình.
1.3. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật
Mối quan hệ giữa cấu trúc dữ liệu và Giải thuật có thể minh họa bằng đẳng 
thức:
Cấu trúc dữ liệu + Giải thuật = Chương trình
Như  vậy, khi đã có cấu trúc dữ  liệu tốt, nắm vững giải thuật thực hiện thì 
việc thể  hiện chương trình bằng một ngôn ngữ  cụ  thể  chỉ  là vấn đề  thời 
gian. Khi có cấu trúc dữ  liệu mà chưa tìm ra thuật giải thì không thể  có 
chương trình và ngược lại không thể  có giải thuật khi chưa có cấu trúc dữ 
liệu. Một chương trình máy tính chỉ có thể được hoàn thiện khi có đầy đủ cả 
Cấu trúc dữ liệu để lưu trữ dữ liệu và Giải thuật xử lý dữ  liệu theo yêu cầu 
của bài toán đặt ra.
2. Kiểu dữ liệu, mô hình dữ liệu, kiểu dữ liệu trừu tượng
2.1.Khái niệm về kiểu dữ liệu
Kiểu dữ liệu T có thể xem như là sự kết hợp của 2 thành phần:
­ Miền giá trị mà kiểu dữ liệu T có thể lưu trữ: V,
­ Tập hợp các phép toán để thao tác dữ liệu: O.
T = <V, O>
Mỗi kiểu dữ liệu thường được đại diện bởi một tên (định danh). Mỗi phần 
tử dữ liệu cókiểu T sẽ có giá trị trong miền V và có thể được thực hiện các 
phép toán thuộc tập hợpcác phép toán trong O.
Để lưu trữ các phần tử dữ liệu này thường phải tốn một số byte(s) trong bộ 

­ Kiểu chuỗi ký tự: Có kích thước tùy thuộc vào từng ngôn ngữ lập trình
Kiểu chuỗi ký tự thường được thực hiện với các phép toán: O = {+, &, <, >, 
<=, >=, =,Length, Trunc, …}
12


­ Kiểu luận lý: Thường có kích thước 1 byte
Kiểu luận lý thường được thực hiện với các phép toán: O = {NOT, AND, OR, 
XOR, <, >,<=, >=, =, …}
2.3. Kiểu dữ liệu trừu tượng
Kiểu dữ liệu trừu tượng là một mô hình toán học cùng với một tập hợp  
các phép toán trên nó. Có thể nói kiểu dữ liệu trừu tượng là một kiểu dữ liệu 
do chúng ta định nghĩa ở mức khái niệm (conceptual), nó chưa được cài đặt cụ 
thể bằng một ngôn ngữ lập trình. 
Khi cài đặt một kiểu dữ liệu trừu tượng trên một ngôn ngữ  lập trình cụ  thể,  
chúng ta phải thực hiện hai nhiệm vụ: 
­ Biểu diễn kiểu dữ  liệu trừu tượng bằng một cấu trúc dữ  liệu hoặc một  
kiểu dữ liệu trừu tượng khác đã được cài đặt.
­ Viết các chương trình con thực hiện các phép toán trên kiểu dữ  liệu trừu  
tượng mà ta thường gọi là cài đặt các phép toán.
3. Thiết kế và phân tích giải thuật
3.1. Thiết kế thuật toán.
Người ta thường dùng phương pháp chia nhỏ bài toán hay chiến thuật chia để 
trị để thiết kế giải thuật.
Nếu gọi bài toán là một modul chính thì ta chia modul chính thành các modul 
con rồi lại chia các modul con thành các modul con nhỏ hơn cho đến khi ta 
được các modul đã biết cách giải rồi. ­> Chiến thuật chia để trị
3.2. Phân tích tính đúng đắn của giải thuật
Ta phải chứng minh giải thuật là đúng
Người ta thường làm : Cho chương trình chạy thử với một bộ dữ liệu đã biết 

Đặt i=i+1 rồi quay b.3.
B5. Đưa ra Max  rồi kết thúc. 

14


­Ví dụ 2:  Thiết kế và phân tích giải thuật  giải phương trình bậc 2.
Input: Các hệ số a,b,c.
Ouput: Nghiệm của phương trình.
Yêu cầu phải có công thức tính Delta = b2 – 4ac.
Phân tích giải thuật như sau:
B1. Nhập vào các hệ số a,b,c
B2. Tính Delta = b2 – 4ac
B3. 
­ Nếu Delta > 0  nhảy đến B4.
­ Nếu Delta = 0  nhảy đến B4.
­ Nếu Delta 
địa chỉ kiểu float.
­ Muốn sử dụng được pointer, trước tiên phải có được địa chỉ của biến mà ta 
cần quan tâm bằng phép toán lấy địa chỉ & . Kết quả của phép lấy địa chỉ & 
17


sẽ là 1 phần tử hằng.
1.2.   Khai báo một biến con trỏ:
 Cú pháp: <Kiểu> * <Tên con trỏ>
 Ý nghĩa: Khai báo một biến có tên là Tên con trỏ dùng để chứa địa chỉ của 
các biến có
kiểu  dữ liệu
 Ví dụ 1: Khai báo 2 biến a,b có kiểu int và 2 biến pa, pb là 2 biến con trỏ 
kiểu int.
int a, b, *pa, *pb;
 Ví dụ 2: Khai báo biến f kiểu float và biến pf  là con trỏ float
float  f, *pf;
Ghi chú: Nếu chưa muốn khai báo kiểu dữ liệu mà con trỏ ptr đang chỉ đến, 
ta sử dụng:
void *ptr;
Sau đó, nếu ta muốn con trỏ ptr chỉ đến kiểu dữ liệu gì cũng được. Tác dụng 
của khai báo này là chỉ dành ra 2 bytes trong bộ nhớ để cấp phát cho biến con 
trỏ ptr. 
1.3. Gán địa chỉ của biến cho biến con trỏ 
Toán tử & dùng để định vị con trỏ đến địa chỉ của một biến đang làm việc. 
 Cú pháp: <Tên biến con trỏ>=&<Tên biến> 
­ Giải thích: Ta gán địa chỉ của biến Tên biến cho con trỏ Tên biến con trỏ. 
­ Ví dụ: Gán địa chỉ của biến a cho con trỏ pa, gán địa chỉ của biến b cho con 
trỏ pb. 
pa=&a; pb=&b; 

 Ý nghĩa: Giải phóng vùng nhớ được quản lý bởi con trỏ block. 
 Ví dụ: Ở ví dụ trên, sau khi thực hiện xong, ta giải phóng vùng nhớ cho 2 
biến con trỏ pa & pb: 
19


free(pa); 
free(pb);
1.6. Một số phép toán trên con trỏ 
  Phép gán con trỏ: Hai con trỏ cùng kiểu có thể gán cho nhau. 
Ví dụ: 
int a, *p, *a ; float *f; 
a = 5 ; p = &a ; q = p ; /* đúng */ 
f = p ; /* sai do khác kiểu */ 
Ta cũng có thể ép kiểu con trỏ theo cú pháp: 
(<Kiểu kết quả>*)<Tên con trỏ> 
Chẳng hạn, ví dụ trên được viết lại: 
int a, *p, *a ; float *f; 
a = 5 ; p = &a ; q = p ; /* đúng */ 
f = (float*)p; /* Đúng nhờ ép kiểu*/ 
 Cộng, trừ con trỏ với một số nguyên 
Ta có thể cộng (+), trừ (­) 1 con trỏ với 1 số nguyên N nào đó; kết quả trả về 
là 1 con trỏ. Con trỏ này chỉ đến vùng nhớ cách vùng nhớ của con trỏ hiện tại 
N phần tử. 
­ Ví dụ: Cho đoạn chương trình sau: 
int *pa; 
pa = (int*) malloc(20); /* Cấp phát vùng nhớ 20 byte=10 số nguyên*/ 
int *pb, *pc; 
pb = pa + 7; 
pc = pb ­ 3; 

  { 
printf(" a[%d] = " , i ) ; scanf( " %d ", p + i );
   }
/* sapxep tăng dan */
21


 for ( i = 0 ; i 
1. p = &i; 
2. q = i; 
3. p = &x; 
4. q = p; 
5. q = & x; 
Các phép gán không hợp lệ là:
a. 1,3,4,5
c.  1,2,4
b. 2,3
d. 2, 3,4
2.3. Lập trình thực hiện các công việc sau :
23


­ Nhập vào mảng một chiều  một dãy số nguyên a1,a2,a3…an 
­ Tính trung bình của các nguyên tử đã nhập vào
­ Tìm và in giá trị lớn nhất, nhỏ nhất của mảng
­ Xuất ra dãy các số chăn, số lẻ
Yêu cầu đánh giá
­ Biết được khai báo biến con trỏ và các phép toán trên con trỏ
­ Áp dụng các phép toán trên biến con trỏ vào các bài toán
­ Áp dụng được con trỏ vào mảng một chiều và mảng nhiều chiều
­ Viết được chương trình và chạy, kiểm tra được kết quả

24


BÀI 3 
LÀM VIỆC VỚI KIỂU CẤU TRÚC
Giới thiệu: