UBND TỈNH LÂM ĐỒNG
TRƯỜNG CAO ĐẲNG ĐÀ LẠT
GIÁO TRÌNH
MÔN HỌC: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
NGÀNH/NGHỀ: CÔNG NGHỆ THÔNG TIN ( ỨNG DỤNG PHẦN MỀM)
TRÌNH ĐỘ: CAO ĐẲNG
Ban hành kèm theo Quyết định số: /QĐ-… ngày…….tháng….năm .........
…………........... của……………………………….
LƯU HÀNH NỘI BỘ
Đà Lạt, năm 2017
2
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
Để đáp ứng nhu cầu học tập của người học, chúng tôi đã tiến hành biên soạn giáo
trình cho môn học Cấu trúc dữ liệu và giải thuật. Tài liệu này được biên soạn theo đề
cương chi tiết môn học Cấu trúc dữ liệu và giải thuật theo chương trình đào tạo nghề
Công nghệ thông tin (Ứng dụng phần mềm) trình độ cao đẳng.
Mục tiêu của giáo trình nhằm giúp các bạn sinh viên chuyên ngành có một tài
liệu cô động dùng làm tài liệu học tập, nhưng chúng tôi cũng không loại trừ toàn bộ
các đối tượng khác tham khảo. Chúng tôi hi vọng người đọc sẽ tìm thấy được những
kiến thức bổ ích trong giáo trình này.
Trong phạm vi giao trình này, chúng tôi giới thiệu các kiến thức, kỹ năng phân
tích được các loại dữ liệu, giải thuật và kết hợp được dữ liệu và giải thuật. Kiến thức
và kỹ năng cài đặt các thuật toán sắp xếp và tìm kiếm. Kiến thức và kỹ năng cài đặt
các thuật toán, các cấu trúc dữ liệu: mảng, danh sách, danh sách liên kết.
Trong quá trình biên soạn, mặc dù đã cố gắng tham khảo nhiều tài liệu và giáo
trình khác nhưng tác giả không khỏi tránh được những thiếu sót và hạn chế. Tác giả
chân thành mong đợi những nhận xét, đánh giá và góp ý để cuốn giáo trình ngày một
hoàn thiện hơn.
Tài liệu này được thiết kế theo từng mô đun/ môn học thuộc hệ thống mô đun/môn
học để đào tạo hoàn chỉnh nghề Công nghệ thông tin (Ứng dụng phần mềm) trình độ
cao đẳng và được dùng làm Giáo trình cho học viên trong các khoá đào tạo, cũng có
thể được sử dụng cho đào tạo ngắn hạn hoặc cho các công nhân kỹ thuật, các nhà
quản lý và người sử dụng nhân lực tham khảo.
Đà Lạt, ngày 07 tháng 7 năm 2017
Tham gia biên soạn
1. Chủ biên Ngô Thiên Hoàng
2. Phạm Đình Nam
3. Trương Thị Thanh Thảo
4. Nguyễn Quỳnh Nguyên
5. Phan Ngọc Bảo
3
MỤC LỤC
Trang
GIÁO TRÌNH ................................................................................................................. 1
LỜI GIỚI THIỆU ........................................................................................................... 2
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 ................................................................................................. 6
1.3. Phân tích gải thuật............................................................................................... 9
1.4 Thiết kế và phân tích giải thuật và một số ví dụ ................................................. 11
1.4. Bài tập ................................................................................................................ 26
CHƯƠNG 2: CÁC KIỂU DỮ LIỆU CƠ SỞ ............................................................... 29
2.1. Các kiểu dữ liệu cơ bản ..................................................................................... 29
2.2 Kiểu dữ liệu có cấu trúc ...................................................................................... 43
2.3. Kiểu hợp ............................................................................................................. 51
2.4 Kiểu tập tin (file) ................................................................................................ 55
2.5. Các kiểu dữ liệu khác ......................................................................................... 67
2.6. Bài tập ............................................................................................................... 70
CHƯƠNG 3: MẢNG, DANH SÁCH VÀ CÁC KIỂU DỮ LIỆU TRỪU TƯỢNG .. 71
3.1 Mảng ................................................................................................................... 71
3.2. Danh sách liên kết ............................................................................................ 80
2.3. Các kiểu dữ liệu trừu tượng ........................................................................... 149
Bài tập ..................................................................................................................... 157
CHƯƠNG 4: SẮP XẾP.............................................................................................. 159
2.1. Sắp xếp kiểu chọn, chèn, nổi bọt ................................................................... 159
2.2. Sắp xếp bằng phương pháp trộn .................................................................... 170
2.3. Sắp xếp nhanh (Quick sort) ........................................................................... 174
Bài Tập: ................................................................................................................... 176
CHƯƠNG 5: TÌM KIẾM ........................................................................................... 178
5.1 Tìm kiếm tuần tự ............................................................................................... 178
5.2 Tìm kiếm nhị phân ............................................................................................ 179
Bài tập ..................................................................................................................... 181
TÀI LIỆU THAM KHẢO .......................................................................................... 182
4
GIÁO TRÌNH MÔ ĐUN/MÔN HỌC
Tên môn học: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Mã môn học: MH28
I. Vị trí, tính chất của môn học:
1. Vị trí: Môn học được bố trí sau khi sinh viên học xong các môn học/môn học Lập
trình căn bản.
2. Tính chất: Cấu trúc dữ liệu và giải thuật là môn học tự chọn, môn kỹ thuật cơ sở áp
dụng cho trình độ Cao đẳng Công nghệ thông tin (ứng dụng phần mềm).
II. Mục tiêu môn học:
1. Về kiến thức:
- Xác định được mối quan hệ giữa cấu trúc dữ liệu và giải thuật trong việc xây dựng
chương trình;
- Trình bày được ý nghĩa, cấu trúc, cách khai báo, các thao tác của các loại cấu trúc dữ
liệu: mảng, danh sách liên kết, các giải thuật cơ bản xử lý các cấu trúc dữ liệu đó;
2. Về kỹ năng:
- Xây dựng được cấu trúc dữ liệu và mô tả tường minh các giải thuật cho một số bài
toán ứng dụng cụ thể;
- Cài đặt được một số giải thuật trên ngôn ngữ lập trình C/ C++;
3. Về năng lực tự chủ và trách nhiệm:
- Co kha năng tư nghiên cư
u, tư hoc, tham khao tai liê
u liên quan đên môn ho
c đê vâ
n
du
ng vào hoa
t động hoc tâ
p.
- Vâ
n du
ng đươc cac kiên thư
c tư nghiên cư
u, hoc tâ
p va kiên thư
c, ky năng đa đươc
học đê hoan thiê
n cac kỹ năng liên quan đên môn hoc môt cach khoa hoc, đung quy
đi
nh
III. Nội dung môn học:
5
CHƯƠNG 1 THIẾT KẾ VÀ PHÂN TÍCH GIẢI THUẬT
Mã bài: MH 28.1
Mục tiêu:
- Xác định được mối quan hệ giữa cấu trúc dữ liệu và giải thuật;
- Xác định được tiến trình phân tích và thiết kế thuật toán;
- Trình bày được cách đánh giá độ phức tạp thuật toán;
- Xây dựng được một số giải thuật cơ bản;
- Viết tường minh một số giải thuật;
- Nghiêm túc, tỉ mỉ trong việc học và vận dụng vào làm bài tập.
1.1. Mở đầu
Hằng ngày chúng ta xử lý công việc theo một kế hoạch đã định sẵn bao gồm các
bước để thực hiện. Chẳng hạn, để in một văn bản viết tay chúng ta phải thực hiện hai
bước quan trọng: Gõ văn bản và In văn bản ra giấy, hai bước này không thể thay đổi
thứ tự được. Đây chính là ý tưởng về một giải thuật. Như vậy, giải thuật là một hệ
thống chặt chẽ và rõ ràng các quy tắc nhằm xác định một dãy các thao tác (các
bước) trên những đối tượng sao cho một số hữu hạn bước thực hiện các thao tác,
chúng ta sẽ đạt được mục tiêu định trước. Khi thiết kế một giải thuật, chúng ta phải
đảm bảo đạt được các đặc trưng của một giải thuật:
a) Tính xác định: Ở mỗi bước của giải thuật, các thao tác phải hết sức rõ ràng.
Không thể gây sự lẫn lộn, nhập nhằng, tuỳ tiện.
b) Tính hữu hạn dừng: Một giải thuật bao giờ cũng phải dừng lại sau một số hữu
hạn các bước. Có thể số lượng các bước là rất lớn.
c) Tính đúng đắn: Sau khi thực hiện và thuật toán dừng lại, chúng ta phải đạt được
kết quả yêu cầu.
d) Tính phổ biến: Thuật toán có thể giải bất kỳ bài toán nào trong cùng một lớp
các bài toán, có nghĩa là thuật toán có thể xử lý với các dữ liệu khác nhau.
e) Tính có đại lượng vào và ra: Khi bắt đầu thuật toán lúc nào cũng phải xác định
được đại lượng vào, thường được lấy từ tập xác định cho trước; Sau khi kết thúc,
thuật toán phải cho ra một hay một số đại lượng ra tuỳ theo chức năng mà thuật toán
đảm nhiệm.