Giáo trình Cấu trúc dữ liệu và giải thuật (HCMUTE)

LÊ VĂN VINH

GIÁO TRÌNH

CẤU TRÚC DỮ LIỆU
VÀ GIẢI THUẬT

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT
THÀNH PHỐ HỒ CHÍ MINH
*******************

ThS. LÊ VĂN VINH

NHÀ XUẤT BẢN ĐẠI HỌC QUỐC GIA
THÀNH PHỐ HỒ CHÍ MINH
2

LỜI NÓI ĐẦU
Cấu trúc dữ liệu và giải thuật là một trong những khối kiến thức
cơ sở trong chương trình đào tạo cử nhân ngành Công nghệ Thông tin
của Khoa Công nghệ Thông tin, Trường Đại học Sư phạm Kỹ thuật
Thành phố Hồ Chí Minh. Khối kiến thức này giúp cho người học hiểu
biết về các kiểu dữ liệu trừu tượng cơ bản thường được sử dụng khi xây
dựng chương trình trên máy tính, cách hiện thực và áp dụng các kiểu dữ
liệu đó trong thực tế.
Nội dung của giáo trình này bao gồm 6 chương bao quát hầu hết
các vấn đề cốt lõi của môn học. Nội dung trong mỗi chương được trình
bày theo trình tự: trình bày các khái niệm, các kiến thức cơ bản trước,
tiếp theo là nêu những ví dụ minh họa để người đọc dễ dàng tiếp cận lý
thuyết mới và sau cùng là cài đặt giải thuật bằng ngôn ngữ lập trình cụ
thể. Cuối mỗi chương đều có bài tập để người đọc tự kiểm tra và củng cố
lại kiến thức của mình.
Rất mong nhận được những ý kiến đóng góp của các đồng nghiệp
và các bạn sinh viên để bài giảng ngày càng hoàn thiện hơn. Mọi ý kiến
đóng góp xin vui lòng gửi theo địa chỉ email: [email protected].

3

MỤC LỤC
LỜI NÓI ĐẦU ........................................................................................... 3
MỤC LỤC ................................................................................................. 4
Chƣơng 1 .................................................................................................. 9
TỔNG QUAN ............................................................................................ 9
1.1.

GIẢI QUYẾT BÀI TOÁN TRÊN MÁY TÍNH ......................... 9

1.1.1.

Xác định yêu cầu của bài toán ............................................. 9

1.1.2.

Xây dựng cấu trúc dữ liệu.................................................... 9

1.1.3.

Thiết kế giải thuật .............................................................. 10

1.1.4.

Cài đặt chƣơng trình .......................................................... 10

1.1.5.

Kiểm lỗi và sửa lỗi chƣơng trình ....................................... 10

1.2.

KIỂU DỮ LIỆU TRỪU TƢỢNG ............................................. 11

1.3.

ĐÁNH GIÁ ĐỘ PHỨC TẠP CỦA GIẢI THUẬT .................. 11

1.4.

BÀI TẬP CHƢƠNG 1 .......................................
...

...
=NULL)
{
NODE*q = p
p=p-next
q-next=NULL
if (q-info pivot-info)
AddLast(myList1, q)//Thêm vào cuối danh sách
1
else
AddLast(myList2, q)//Thêm vào cuối danh sách
2
}
//Gọi đệ quy sắp xếp cho các danh sách con
QuickSort(myList1)
QuickSort(myList2)
//Ghép nối danh sách 1 + pivot
if (!IsEmptyList(myList1))
{
myList.Head=myList1.Head
myList1.Tail-next=pivot
}
else
111

myList.Head=pivot
//Ghép nối pivot + danh sách 2
pivot-next=myList2.Head
if (!IsEmptyList(myList2))
myList.Tail=myList2.Tail
else
myList.Tail=pivot
}
//Liệt kê nội dung các phần tử
void PrintList(LINKEDLIST myList)
{
for(NODE*p=myList.Headp!=NULLp=p-next)
coutp-info
}
void main()
{
LINKEDLIST myList
InitList(myList)
NODE*p1=Node(3)
NODE*p2=Node(4)
NODE*p3=Node(5)
NODE*p4=Node(25)
NODE*p5=Node(15)
//Thêm các phần tử vào đầu
AddFirst(myList,p1)
AddFirst(myList,p2)
AddFirst(myList,p4)
cout\\nThem phan tu vao dauendl
PrintList(myList)
//Thêm các phần tử vào cuối
AddLast(myList,p3)
AddLast(myList,p5)
cout\\nThem phan tu vao cuoiendl
112

PrintList(myList)
//Hủy phần tử đầu
RemoveFirst(myList)
cout\\nHuy phan tu dauendl
PrintList(myList)
//Hủy phần tử cuối
RemoveLast(myList)
cout\\nHuy phan tu cuoiendl
PrintList(myList)
//Sắp xếp danh sách
QuickSort(myList)
cout\\nSap xep danh sachendl
PrintList(myList)
}

113

Giáo trình
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
ThS. LÊ VĂN VINH
NHÀ XUẤT BẢN
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
Khu Phố 6, Phường Linh Trung, Quận Thủ Đức, TPHCM
Số 3, Công trường Quốc tế, Quận 3, TP Hồ Chí Minh
ĐT: 38239171 – 38225227 - 38239172
Fax: 38239172
Email: [email protected]
PHÒNG PHÁT HÀNH NHÀ XUẤT BẢN
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
Số 3 Công trường Quốc tế - Quận 3 – TPHCM
ĐT: 38239170 – 0982920509 – 0913943466
Fax: 38239172 – Website: www.nxbdhqghcm.edu.vn

Chịu trách nhiệm xuất bản:
NGUYỄN HOÀNG DŨNG
Chịu trách nhiệm nội dung:
HUỲNH BÁ LÂN
Tổ chức bản thảo và chịu trách nhiệm về tác quyền
TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT TP. HCM
Biên tập:
NGUYỄN HUỲNH
Sửa bản in:
THÙY DƯƠNG
Trình bày bìa
TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT TP. HCM
Mã số ISBN: 978-604-73-1690-8

Số lượng 300 cuốn khổ 16 x 24cm.
Số đăng ký kế hoạch xuất bản: 126-2013/CXB/165-07/ĐHQGTPHCM. Quyết
định xuất bản số: 164 ngày 05/09/2013 của Nhà xuất bản ĐHQGTPHCM.
In tại Công ty TNHH In và Bao bì Hưng Phú.
Nộp lưu chiểu quý IV năm 2013.

ISBN: 978-604-73-1690-8

9 786047 316908