Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật
Trang: 3
Chương 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
1.1. Tầm quan trọng của cấu trúc dữ liệu và giải thuật trong một
đề án tin học
1.1.1. Xây dựng cấu trúc dữ liệu
Có thể nói rằng không có một chương trình máy tính nào mà không có dữ liệu để xử lý.
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.1.2. Xây dựng giải thuật
Khái niệm giải thuật hay thuật giải mà nhiều khi còn được gọi là thuật toán dùng để chỉ
phương pháp hay cách thức (method) để giải quyết vần đề. Giải thuật có thể được minh
họa bằng ngôn ngữ tự nhiên (natural language), bằng sơ đồ (flow chart) hoặc bằng mã
giả (pseudo code). Trong thực tế, giải thuật thường được minh họa hay thể hiện bằng
mã giả tựa trên một hay một số ngôn ngữ lập trình nào đó (thường là ngôn ngữ mà
người lập trình chọn để cài đặt thuật toán), chẳng hạn như C, Pascal, …
Khi đã xác đònh được cấu trúc dữ liệu thích hợp, người lập trình sẽ bắt đầu tiến hành
xây dựng thuật giải tương ứng theo yêu cầu của bài toán đặt ra trên cơ sở của cấu trúc
dữ liệu đã được chọn. Để giải quyết một vấn đề có thể có nhiều phương pháp, do vậy
sự lựa chọn phương pháp phù hợp là một việc mà người lập trình phải cân nhắc và tính
toán. Sự lựa chọn này cũng có thể góp phần đáng kể trong việc giảm bớt công việc
của người lập trình trong phần cài đặt thuật toán trên một ngôn ngữ cụ thể.
1.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ó

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ợp
cá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ộ nhớ, số
byte(s) này gọi là kích thước của kiểu dữ liệu.
1.3.2. Các kiểu dữ liệu cơ sở
Hầu hết các ngôn ngữ lập trình đều có cung cấp các kiểu dữ liệu cơ sở. Tùy vào mỗi
ngôn ngữ mà các kiểu dữ liệu cơ sở có thể có các tên gọi khác nhau song chung quy
lại có những loại kiểu dữ liệu cơ sở như sau:
- Kiểu số nguyên: Có thể có dấu hoặc không có dấu và thường có các kích thước sau:
+ Kiểu số nguyên 1 byte
+ Kiểu số nguyên 2 bytes
+ Kiểu số nguyên 4 bytes
Kiểu số nguyên thường được thực hiện với các phép toán: O = {+, -, *, /, DIV, MOD, <,
>, <=, >=, =, …}
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật
Trang: 5
- Kiểu số thực: Thường có các kích thước sau:
+ Kiểu số thực 4 bytes
+ Kiểu số thực 6 bytes
+ Kiểu số thực 8 bytes
+ Kiểu số thực 10 bytes
Kiểu số thực thường được thực hiện với các phép toán: O = {+, -, *, /, <, >, <=, >=, =, …}
- Kiểu ký tự: Có thể có các kích thước sau:
+ Kiểu ký tự byte
+ Kiểu ký tự 2 bytes
Kiểu ký tự thường được thực hiện với các phép toán: O = {+, -, <, >, <=, >=, =, ORD,
CHR, …}
- 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 = {+, &, <, >, <=, >=, =,

4. Liệt kê các kiểu dữ liệu cơ sở, các kiểu dữ liệu có cấu trúc trong C, Pascal?
5. Sử dụng các kiểu dữ liệu cơ bản trong C, hãy xây dựng cấu trúc dữ liệu để lưu trữ
trong bộ nhớ trong (RAM) của máy tính đa thức có bậc tự nhiên n (0 ≤ n ≤ 100) trên
trường số thực (a
i
, x
∈
R):
Với cấu trúc dữ liệu được xây dựng, hãy trình bày thuật toán và cài đặt chương trình để
thực hiện các công việc sau:
- Nhập, xuất các đa thức.
- Tính giá trò của đa thức tại giá trò x
0
nào đó.
- Tính tổng, tích của hai đa thức.
6. Tương tự như bài tập 5. nhưng đa thức trong trường số hữu tỷ Q (các hệ số a
i
và x là
các phân số có tử số và mẫu số là các số nguyên).
7. Cho bảng giờ tàu đi từ ga Saigon đến các ga như sau (ga cuối là ga Hà nội):
TÀU ĐI S2 S4 S6 S8 S10 S12 S14 S16 S18 LH2 SN2

HÀNH TRÌNH 32 giờ 41 giờ 41 giờ 41 giờ 41 giờ 41 giờ 41 giờ 41 giờ 41 giờ 27giờ 10g30

SAIGON ĐI 21g00 21g50 11g10 15g40 10g00 12g30 17g00 20g00 22g20

13g20 18g40

MƯƠNG MÁN 2g10 15g21 19g53 14g07 16g41 21g04 1g15 3g16 17g35 22g58


nào đó tại một ga G
0
nào đó.
∑
=
=
n
i
i
i
xaxfn
0
)(
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật
Trang: 7
- Xuất ra giờ đến các ga của một tàu T
0
nào đó.
- Xuất ra giờ các tàu đến một ga G
0
nào đó.
- Xuất ra bảng giờ tàu theo mẫu ở trên.
Lưu ý:
- Các ô trống ghi nhận tại các ga đó, tàu này không đi đến hoặc chỉ đi qua mà
không dừng lại.
- Dòng “HÀNH TRÌNH” ghi nhận tổng số giờ tàu chạy từ ga Saigon đến ga Hà nội.
8. Tương tự như bài tập 7. nhưng chúng ta cần ghi nhận thêm thông tin về đoàn tàu khi
dừng tại các ga chỉ để tránh tàu hay để cho khách lên/xuống (các dòng in nghiêng
tương ứng với các ga có khách lên/xuống, các dòng khác chỉ dừng để tránh tàu).
9. Sử dụng kiểu dữ liệu cấu trúc trong C, hãy xây dựng cấu trúc dữ liệu để lưu trữ trong