BỘ NÔNG NGHIỆP VÀ PHÁT TRIỂN NÔNG THÔN
TRƯỜNG CAO ĐẲNG CƠ GIỚI NINH BÌNH

GIÁO TRÌNH
MƠN HỌC: MH19_CẤU TRÚC DỮ LIỆU
VÀ GIẢI THUẬT
NGHỀ: LẬP TRÌNH MÁY TÍNH
TRÌNH ĐỘ: Cao đẳng/ trung cấp
Ban hành kèm theo Quyết định số:
/QĐ-…TCGNB ngày…….tháng….năm ....
của Hiệu trưởng Trường Cao Đẳng Cơ giới Ninh Bình

Ninh Bình

1


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.

2


Lời giới thiệu
Các kiến thức về cấu trúc dữ liệu (CTDL) và giải thuật đóng vai trị quan
trọng trong việc đào tạo nghề Lập trình máy tính. Sách này đựơc hình thành trên cơ
sở các bài giảng về CTDL và giải thuật mà tôi cùng các đồng nghiệp đã đọc nhiều
năm tại khoa Toán-Cơ-Tin học - Trường Đại học Khoa học Tự nhiên – Đại học

Quốc Gia Hà Nội; Khoa Công nghệ thông tin - Đại học Bách Khoa Hà Nội; Khoa
Công nghệ thông tin - Đại học Giao thông vận tải. Sách được biên soạn chủ yếu để
làm tài liệu tham khảo cho học sinh, sinh viên nghề Lập trình máy tính, nhưng nó
cũng rất bổ ích cho các độc giả khác cần có hiểu biết đầy đủ hơn về CTDL và giải
thuật.
Giáo trình này gồm bốn chương
Chương 1. Giới thiệu về cấu trúc dữ liệu và giải thuật
Chương 2. Kiểu dữ liệu nâng cao
Chương 3. Danh sách
Chương 4. Ngăn xếp và hàng đợi
Chương 5. Sắp xếp và tìm kiếm
Để biên soạn giáo trình này, chúng tơi đã tham khảo các tài liệu: Cấu trúc dữ
liệu và giải thuật, PTS Đinh Mạnh Tường; Lê Minh Hoàng, Cấu trúc dữ liệu và
giải thuật.
Giáo trình Cấu trúc dữ liệu và giải thuật đã được Hổi đồng thẩm định
Trường Cao đẳng nghề Cơ Giới Ninh Bình xét duyệt. Tuy nhiên trong quá trình
biên soạn khơng tránh khỏi những sai sót, rất mong được sự đóng góp quý báu
chân thành của bạn đọc.
Ninh Bình, ngày tháng năm 2018
Tham gia biên soạn:
1. Chủ biên Đoàn Xuân Luận
2. Phạm Thị Thoa
3. Nguyễn Anh Văn

3


Mục lục
Lời giới thiệu.............................................................................................................3
Mục lục......................................................................................................................4

Chương 1...................................................................................................................8
Giới thiệu cấu trúc dữ liệu và giải thuật....................................................................8
1. Mối liên hệ giữa cấu trúc dữ liệu và giải thuật.................................................9
1.1. Xây dựng cấu trúc dữ liệu..........................................................................9
1.2. Xây dựng giải thuật....................................................................................9
1.3. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật.......................................10
2. Kiểu dữ liệu và mơ hình dữ liệu.....................................................................10
2.1. Biểu diễn dữ liệu.......................................................................................10
2.3. Hệ kiểu của ngơn ngữ Pascal....................................................................14
2.4. Mơ hình dữ liệu và kiểu dữ liệu trừu tượng..............................................16
3. Thiết kế và giải thuật......................................................................................20
3.1. Các tiêu chuẩn đánh giá cấu trúc dữ liệu..................................................20
3.2. Đánh giá độ phức tạp của thuật toán........................................................21
Chương 2.................................................................................................................22
Các kiểu dữ liệu nâng cao........................................................................................22
1. Mảng...............................................................................................................22
2. Con trỏ............................................................................................................24
2.1. Con trỏ và địa chỉ......................................................................................24
2.2. Con trỏ và mảng một chiều.......................................................................26
2.2.2. Tên mảng là một hằng địa chỉ................................................................26
2.2.3. Con trỏ trỏ tới các phần tử của mảng một chiều....................................26
2.3. Con trỏ và mảng nhiều chiều....................................................................30
2.4. Kiểu con trỏ, kiểu địa chỉ, các phép toán trên con trỏ..............................32
3. Cấu trúc và hợp...............................................................................................39
3.1. Cấu trúc (struct)........................................................................................39
3.2. Kiểu union................................................................................................40
4. File..................................................................................................................41
4.1. Khái niệm về tệp tin..................................................................................41
4



4.2. Khai báo sử dụng tệp - một số hàm thường dùng khi thao tác trên tệp....43
Chương 3.................................................................................................................49
Danh sách................................................................................................................49
1. Các khái niệm.................................................................................................49
1.1. Khái niệm về danh sách............................................................................49
1.2. Các phép toán trên danh sách...................................................................49
2. Lưu tữ kế tiếp đối với danh sách tuyến tính...................................................51
2.1. Định nghĩa................................................................................................51
2.2. Danh sách liên kết đơn (Singly Linked List)............................................51
3. Lưu trữ móc nối đối với danh sách tuyến tính................................................76
3.1. Cấu trúc dữ liệu........................................................................................76
3.2. Các thao tác trên danh sách......................................................................78
Chương 4...............................................................................................................100
Ngăn xếp và hàng đợi............................................................................................100
1. Định nghĩa ngăn xếp (stack).........................................................................100
2. Lưu trữ stack bằng mảng..............................................................................102
2.1. Khởi tạo ngăn xếp...................................................................................102
2.2. Thêm (Đẩy) một phần tử vào ngăn xếp (Push).......................................102
2.3. Lấy nội dung một phần tử trong ngăn xếp ra để xử lý (Pop)..................103
2.4. Hủy ngăn xếp..........................................................................................104
3.Ví dụ về ứng dụng stack................................................................................104
4. Định nghĩa hàng đợi(Queue)........................................................................108
5. Lưu trữ queue bằng mảng.............................................................................110
5.1. Khởi tạo hàng đợi (Initialize).................................................................110
5.2. Thêm (Đưa) một phần tử vào hàng đợi (Add)........................................111
5.3. Lấy nội dung một phần tử trong hàng đợi ra để xử lý (Get)...................112
5.4. Hủy hàng đợi..........................................................................................113
6. Stack và queue móc nối................................................................................113
6.1. Stack móc nối.........................................................................................113

6.2. Queue móc nối........................................................................................116
Chương 5...............................................................................................................119
5


Sắp xếp và tìm kiếm..............................................................................................119
1. Giới thiệu về sắp xếp và tìm kiếm................................................................119
1.1. Giới thiệu về sắp xếp..............................................................................119
1.2. Giới thiệu về tìm kiếm............................................................................120
2. Các phương pháp sắp xếp.............................................................................121
2.1. Sắp xếp kiểu chọn (Selection sort).........................................................121
2.2. Thuật toán sắp xếp nổi bọt (bubble sort)................................................122
2.3. Thuật toán sắp xếp kiểu chèn (insertion sort).........................................122
2.4. Thuật toán sắp xếp kiểu phân đoạn (quick sort).....................................125
2.5. Thuật tốn sắp xếp trộn...........................................................................129
3. Các phương pháp tìm kiếm...........................................................................134
3.1. Tìm kiếm tuần tự (Sequential search).....................................................134
3.2. Tìm kiếm nhị phân (Binary search)........................................................134
TÀI LIỆU THAM KHẢO.....................................................................................136

6


MƠN HỌC CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Tên Mơn học: Cấu trúc dữ liệu và giải thuật
Mã môn học: MH19
Vị trí, tính chất, ý nghĩa và vai trị của mơn học:
- Vị trí mơn học: Mơn học này được học sau mơn học Tin học căn bản, Lập trình
căn bản.
- Tính chất mơn học: Mơn học này u cầu phải có tư duy logic và các kiến thức

về lập trình căn bản, lập trình hướng đối tượng.
- Ý nghĩa, vai trị của mơn học: Đây là mơn học cơ sở ngành của các ngành liên
quan đến công nghệ thông tin, cung cấp cho sinh viên các kiến thức cơ bản về
lập trình.
Mục tiêu của mơn học:
- Kiến thức:
+ Trình bày được mối liên hệ giữa cấu trúc dữ liệu và giải thuật; cách khai báo
và sử dụng các kiểu dữ liệu nâng cao;
+ Trình bày được các kỹ thuật ngăn xếp và hàng đợi, các thuật toán sắp xếp và
tìm kiếm, các loại danh sách liên kết.
- 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;
+ Cài đặt được các thuật tốn sắp xếp và tìm kiếm;
+ Cài đặt được các thuật toán trên các cấu trúc dữ liệu: mảng, danh sách, danh
sách liên kết.
- Thái độ:
+ Rèn luyện tính cẩn thận, tỉ mỉ, chính xác, sáng tạo, làm việc độc lập và theo
nhóm;
+ Rèn luyện kỹ năng lập trình;
+ Đảm bảo an tồn cho người và trang thiết bị.
Nội dung của môn học:
Số

Tên chương mục

Thời gian

7



TT
I

II

III

IV

IV

Tổng
số
Chương 1: Giới thiệu cấu trúc dữ liệu và
5
giải thuật
1. Mỗi liên hệ giữa cấu trúc dữ liệu và giải
1
thuật
2. Kiểu dữ liệu và mơ hình dữ liệu
2
3. Thiết kế và giải thuật
2
Chương 2: Kiểu dữ liệu nâng cao
20
1. Kiểu mảng
5
2. Con trỏ
5

3. Cấu trúc và hợp
5
4. File
5
Chương 3: Danh sách
20
1. Các khái niệm
5
2. Lưu trữ kế tiếp đối với danh sách tuyến
7
tính
3. Lưu trữ móc nối đối với danh sách tuyến
8
tính
Chương 4: Ngăn xếp và hàng đợi
20
1. Định nghĩa ngăn xếp (stack)
1
2. Lưu trữ stack bằng mảng
3
3.Ví dụ về ứng dụng stack
4
4. Định nghĩa hàng đợi(Queue)
2
5. Lưu trữ queue bằng mảng
5
6. Stack và queue móc nối
5
Chương 5: Sắp xếp và tìm kiếm
25

1. Giới thiệu về sắp xếp và tìm kiếm
3
2. Các phương pháp sắp xếp
10
3. Các phương pháp tìm kiếm
12
Cộng
90

Lý
thuyết
5

Thực
hành
0

Kiểm
tra
0

2
2
5
1
1
2
1
6
2

2

14
4
4
3
3
13
3
5

1

2

5

1

8
1
1
1
1
2
2
6
2
2
2

30

11

1

2
3
1
3
2
18
1
8
9
56

1
1

1

Chương 1
Giới thiệu cấu trúc dữ liệu và giải thuật
Mã chương: MH19_CH01
Giới thiệu:
Bài này giới thiệu về mối liên hệ giữa cấu trúc dữ liệu và giải thuật.
8

1

1

1
4


Mục tiêu:
- Trình bày được kiến thức cở bản về cấu trúc dữ liệu, giải thuật, kiểu dữ liệu, mơ
hình dữ liệu;
- Phân tích được giải thuật;
- Sử dụng được các phương pháp phân tích, thiết kế giải thuật;
- Rèn luyện tính cẩn thận, tỉ mỉ, chính xác, sáng tạo, thực hiện các thao tác an
tồn với máy tính.
Nội dung:
1. Mối liên hệ giữa cấu trúc dữ liệu và giải thuật
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 tồ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.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 tố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 tố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
tốn trên một ngơn ngữ cụ thể.
9


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ó Thuật giải 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 hồ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 và mơ hình dữ liệu
2.1. Biểu diễn dữ liệu
- Trong máy tính điện tử (MTĐT), các dữ liệu dù có bản chất khác nhau như thế
nào (số nguyên, số thực, hay xâu ký tự, ...), đều được biểu diễn dưới dạng nhị
phân. Mỗi dữ liệu được biểu diễn dưới dạng một dãy các số nhị phân 0 hoặc 1.
Về mặt kỹ thuật đây là cách biểu diễn thích hợp nhất, vì các giá trị 0 và 1 dễ
dàng được mã hoá bởi các phần tử vật lý chỉ có hai trạng thái. Chúng ta sẽ
khơng quan tâm đến cách biểu diễn này của dữ liệu, cũng như các cách tiến
hành các thao tác, các phép toán trên các dữ liệu được biểu diễn dưới dạng nhị
phân.

- Cách biểu diễn nhị phân của dữ liệu rất không thuận tiện đối với con người.
Việc xuất hiện các ngôn ngữ lập trình bậc cao (FORTRAN, BASIC, PASSCAL,
C ...) đã giải phóng con người khỏi những khó khăn khi làm việc với cách biểu
diễn trong máy của dữ liệu. Trong các ngơn ngữ lập trình bậc cao, các dữ liệu,
hiểu theo một nghĩa nào đó, là sự trìu tượng hố các tính chất của các đối tượng
trong thế giới hiện thực. Nói dữ liệu là sự trìu tượng hố từ thế giới hiện thực,
vì ta đã bỏ qua những nhân tố, tính chất mà ta cho là khơng cơ bản, chỉ giữ lại
những tính chất đặc trưng cho các đối tượng thuộc phạm vi bài tốn đang xét.
Chẳng hạn, vị trí của một đối tượng trong thực tiễn, được đặc trưng bởi cặp số
thực (x,y) (đó là toạ đoạ đê-các của một điểm trong mặt phẳng). Do đó, trong
ngơn ngữ Pascal, vị trí một đối tượng được biểu diễn bởi bản ghi gồm hai
10


trường tương ứng với hoành độ và tung độ của một điểm. Trong tốn học có các
khái niệm biểu diễn đặc trưng về mặt số lượng và các quan hệ của các đối tượng
trong thế giới hiện thực, đó là các khái niệm số nguyên, số thực, số phức, dãy,
ma trận, ... Trên cơ sở các khái niệm toán học này, người ta đã đưa vào trong
các ngôn ngữ lập trình bậc cao các dữ liệu kiểu nguyên, thực, phức, mảng, bản
ghi, ... Tuy nhiên do tính đa dạng của các bài toán cần xử lý bằng MTĐT, chỉ sử
dụng các kiểu dữ liệu có sẵn trong các ngơn ngữ lập trình bậc cao là chưa đủ để
mơ tả các bài toán. Chúng ta phải cần đến các cấu trúc dữ liệu. Đó là các dữ
liệu phức tạp, được xây dựng nên từ các dữ liệu đã có, đơn giản hơn bằng các
phương pháp liên kết nào đó.
- Để giải quyết một bài toán bằng MTĐT, ta cần xây dựng mơ hình dữ liệu mơ tả
bài tốn. Đó là sự trìu tượng hố các đặc trưng của các đối tượng thuộc phạm vi
vấn đề mà ta quan tâm, các mối quan hệ giữa các đối tượng đó. Dùng làm các
mơ hình dữ liệu trong tin học, chúng ta sẽ sử dụng các mơ hình tốn học như
danh sách, cây, tập hợp, ánh xạ, quan hệ, đồ thị, ... Mơ hình dữ liệu sẽ được
biểu diễn bởi các cấu trúc dữ liệu. Thơng thường một mơ hình dữ liệu có thể

được biểu hiện bởi nhiều cấu trúc dữ liệu khác nhau. Tuỳ từng ứng dụng, ta sẽ
chọn cấu trúc dữ liệu nào mà các thao tác cần thực hiện là hiệu quả nhất có thể
được.
2.2. Kiểu dữ liệu và cấu trúc dữ liệu
- Trong các ngơn ngữ lập trình bậc cao, các dữ liệu được phân lớp thành các lớp
dữ liệu dựa vào bản chất của dữ liệu. Mỗi một lớp dữ liệu được gọi là một kiểu
dữ liệu. Như vậy, một kiểu T là một tập hợp nào đó, các phần tử của tập được
gọi là các giá trị của kiểu. Chẳng hạn, kiểu integer là tập hợp các số nguyên,
kiểu char là một tập hữu hạn các ký hiệu. Các ngơn ngữ lập trình khác nhau có
thể có các kiểu dữ liệu khác nhau. Fortran có các kiểu dữ liệu là integer, real,
logical, complex và double complex. Các kiểu dữ liệu trong ngôn ngữ C là int,
float, char, con trỏ, struct..., Kiểu dữ liệu trong ngôn ngữ Lisp lại là các S-biểu
thức. Một cách tổng quát, mỗi ngôn ngữ lập trình có một hệ kiểu của riêng
mình. Hệ kiểu của một ngôn ngữ bao gồm các kiểu dữ liệu cơ sở và các phương
pháp cho phép ta từ các kiểu dữ liệu đã có xây dựng nên các kiểu dữ liệu mới.
11


- Khi nói đến một kiểu dữ liệu, chúng ta cần phải đề cập đến hai đặc trưng sau
đây:
1. Tập hợp các giá trị thuộc kiểu. Chẳng hạn, kiểu integer trong ngôn ngữ
Pascal gồm tất cả các số nguyên được biểu diễn bởi hai byte, tức là gồm các số
nguyên từ -32768 đến + 32767. Trong các ngôn ngữ lập trình bậc cao mỗi hằng,
biến, biểu thức hoặc hàm cần phải được gắn với một kiểu dữ liệu xác định. Khi
đó, mỗi biến (biểu thức, hàm) chỉ có thể nhận các giá trị thuộc kiểu của biến
(biểu thức, hàm) đó.
Ví dụ , nếu X là biến có kiểu boolean trong Pascal (var X : boolean) thì X chỉ
có thể nhận một trong hai giá trị true, false.
2. Với mỗi kiểu dữ liệu, cần phải xác định một tập hợp nào đó các phép tốn có
thể thực hiện được trên các dữ liệu của kiểu. Chẳng hạn, với kiểu real, các phép

tốn có thể thực hiện được là các phép tốn số học thông thường +, -, *, / , và
các phép toán so sánh = , < >, < , < =, >, > =.
- Thông thường trong một hệ kiểu của một ngơn ngữ lập trình sẽ có một số kiểu
dữ liệu được gọi là kiểu dữ liệu đơn hay kiểu dữ liệu phân tử (atomic).
- Chẳng hạn, trong ngôn ngữ Pascal, các kiểu dữ liệu integer, real, boolean , char
và các kiểu liệt kê được gọi là các kiểu dữ liệu đơn. Sở dĩ gọi là đơn, vì các giá
trị của các kiểu này được xem là các đơn thể đơn giản nhất khơng thể phân tích
thành các thành phần đơn giản hơn được nữa.
- Như đã nói, khi giải quyết các bài toán phức tạp, chỉ sử dụng các dữ liệu đơn là
không đủ, ta phải cần đến các cấu trúc dữ liệu. Một cấu trúc dữ liệu bao gồm
một tập hợp nào đó các dữ liệu thành phần, các dữ liệu thành phần này được
liên kết với nhau bởi một phương pháp nào đó. Các dữ liệu thành phần có thể là
dữ liệu đơn, hoặc cũng có thể là một cấu trúc dữ liệu đã được xây dựng. Có thể
hình dung một cấu trúc dữ liệu được tạo nên từ các tế bào (khối xây dựng), mỗi
tế bào có thể xem như một cái hộp chứa dữ liệu thành phần.
- Trong Pascal và trong nhiều ngôn ngữ thơng dụng khác có một cách đơn giản
nhất để liên kết các tế bào, đó là sắp xếp các tế bào chứa các dữ liệu cùng một
kiểu thành một dãy. Khi đó ta có một cấu trúc dữ liệu được gọi là mảng (array).
Như vậy, có thể nói, một mảng là một cấu trúc dữ liệu gồm một dãy xác định
12


các dữ liệu thành phần cùng một kiểu. Ta vẫn thường nói đến mảng các số
nguyên, mảng các số thực, mảng các bản ghi, ... Mỗi một dữ liệu thành phần
của mảng được gắn với một chỉ số từ một tập chỉ số nào đó. Ta có thể truy cập
đến một thành phần nào đó của mảng bằng cách chỉ ra tên mảng và chỉ số của
thành phần đó.
- Một phương pháp khác để tạo nên các cấu trúc dữ liệu mới, là kết hợp một số tế
bào (có thể chứa các dữ liệu có kiểu khác nhau) thành một bản ghi (record).
Các tế bào thành phần của bản ghi được gọi là các trường của bản ghi. Các bản

ghi đến lượt lại được sử dụng làm các tế bào để tạo nên các cấu trúc dữ liệu
khác. Chẳng hạn, một trong các cấu trúc dữ liệu hay được sử dụng nhất là mảng
các bản ghi.
- Còn một phương pháp quan trọng nữa để kiến tạo các cấu trúc dữ liệu, đó là sử
dụng con trỏ. Trong phương pháp này, mỗi tế bào là một bản ghi gồm hai phần
INFOR và LINK, phần INFOR có thể có một hay nhiều trường dữ liệu, cịn
phần LINK có thể chứa một hay nhiều con trỏ trỏ đến các tế bào khác có quan
hệ với tế bào đó. Chẳng hạn, ta có thể cài đặt một danh sách bởi cấu trúc dữ liệu
danh sách liên kết, trong đó mỗi thành phần của danh sách liên kết là bản ghi
gồm hai trường
type Cell = record
element : Item ;
next : ^Cell ;
end ;
- Ở đây, trường element có kiểu dữ liệu Item, một kiểu dữ liệu nào đó của các
phần tử của danh sách. Trường next là con trỏ trỏ tới phần tử tiếp theo trong
danh sách. Cấu trúc dữ liệu danh sách liên kết biểu diễn danh sách (a 1, a2,...., an)
có thể được biểu diễn như trong hình
a1

a2

an

13

.


Hình 1.1: Cấu trúc dữ liệu danh sách liên kết.

- Sử dụng con trỏ để liên kết các tế bào là một trong các phương pháp kiến tạo
các cấu trúc dữ liệu được áp dụng nhiều nhất. Ngoài danh sách liên kết, người
ta còn dùng các con trỏ để tạo ra các cấu trúc dữ liệu biểu diễn cây, một mơ
hình dữ liệu quan trọng bậc nhất.
- Trên đây chúng ta đã nêu ba phương pháp chính để kiến tạo các cấu trúc dữ
liệu. (Ở đây chúng ta chỉ nói đến các cấu trúc dữ liệu trong bộ nhớ trong, các
cấu trúc dữ liệu ở bộ nhớ ngoài như file chỉ số, B-cây sẽ được đề cập riêng.)
- Một kiểu dữ liệu mà các giá trị thuộc kiểu không phải là các dữ liệu đơn mà là
các cấu trúc dữ liệu được gọi là kiểu dữ liệu có cấu trúc. Trong ngôn ngữ
Pascal, các kiểu dữ liệu mảng, bản ghi, tập hợp, file đều là các kiểu dữ liệu có
cấu trúc.
2.3. Hệ kiểu của ngôn ngữ Pascal
- Pascal là một trong các ngơn ngữ có hệ kiểu phong phú nhất. Hệ kiểu của
Pascal chứa các kiểu cơ sở, integer, real, boolean, char và các quy tắc, dựa vào
đó ta có thể xây dựng nên các kiểu phức tạp hơn từ các kiểu đã có. Từ các kiểu
cơ sở và áp dụng các quy tắc, ta có thể xây dựng nên một tập hợp vô hạn các
kiểu. Hệ kiểu của Pascal có thể được định nghĩa định quy như sau :
Các kiểu cơ sở
1. Kiểu integer
2. Kiểu real
3. Kiểu boolean
4. Kiểu char
5. Kiểu liệt kê
Giả sử obj1, obj2,.... objn là các đối tượng nào đó. khi đó ta có thể tạo nên
kiểu liệt kê T bằng cách liệt kê ra tất cả các đói tượng đó.
type T = (obj1, obj2,...objn)

14



- Chú ý. Tất cả các kiểu đơn đều là các kiểu có thứ tự, tức là với hai giá trị bất kỳ
a và b thuộc cùng một kiểu, ta ln có a <= b hoặc a > = b. trừ kiểu real, các
kiểu cịn lại đều là kiểu có thứ tự đếm được.
6. Kiểu đoạn con

type T = min . max
- Trong đó min và max là cận dưới và cận trên của khoảng ; min và max là các
giá trị thuộc cùng một kiểu integer, char, hoặc các kiểu liệt kê, đồng thời min<
max. Kiểu T gồm tất cả các giá trị từ min đến max.
- Các phép tốn trong hệ kiểu Pascal
- Như đã nói với mỗi kiểu dữ liệu ta chỉ có thể thực hiện một số phép toán nhất
định trên các dữ liệu của kiểu. Ta khơng thể áp dụng một phép tốn trên các dữ
liệu thuộc kiểu này cho các dữ liệu có kiểu khác. Ta có thể phân tập hợp các
phép tốn trên các kiểu dữ liệu của Pascal thành hai lớp sau :
A. Các phép toán truy cập đến các thành phần của một đối tượng dữ liệu, chẳng
hạn truy cập đến các thành phần của một mảng, đến các trường của một bản
ghi.
+ Giả sử A là một mảng với tập chỉ số I, khi đó A[i] cho phép ta truy cập đến
thành phần thứ i của mảng. Còn nếu X là một bản ghi thì việc truy cập đến
trường F của nó được thực hiện bởi phép tốn X.F.
B. Các phép tốn kết hợp dữ liệu.
+ Pascal có một tập hợp phong phú các phép toán kết hợp một hoặc nhiều dữ
liệu đã cho thành một dữ liệu mới. Sau đây là một số nhóm các phép tốn
chính.
1. Các phép tốn số học. Đó là các phép tốn + , -, * , / trên các số thực ; các
phép toán +, - *, /, div, mod trên các số nguyên.
2. Các phép toán so sánh. Trên các đối tượng thuộc các kiểu có thứ tự (đó là các
kiểu cơ sở và kiểu tập), ta có thể thực hiện các phép toán so sánh =, < >, <, <=,

15



>, >=. Cần lưu ý rằng, kết quả của các phép toán này là một giá trị kiểu boolaen
(tức là true hoặc false).
3. Các phép tốn logic. Đó là các phép toán and, or, not được thực hiện trên hai
giá trị false và truc của kiểu boolean.
4. Các phép toán tập hợp. Các phép toán hợp, giao, hiệu của các tập hợp trong
pascal được biểu diễn bởi +, *, - tương ứng. Việc kiểm tra một đối tượng x có là
phần tử của tập A hay không được thực hiện bởi phép toán x in A. Kết quả của
phép toán này là một giá boolean.
2.4. Mơ hình dữ liệu và kiểu dữ liệu trừu tượng
- Để giải quyết một vấn đề trên MTĐT thông thường chúng ta cần phải qua một
số giai đoạn chính sau đây :
1. Đặt bài tốn
2. Xây dựng mơ hình
3. Thiết kế thuật tốn và phân tích thuật tốn
4. Viết chương trình
-

-

-

5. Thử nghiệm.
Chúng ta sẽ khơng đi sâu phân tích từng giai đoạn. Chúng ta chỉ muốn làm sáng
tỏ vai trị của mơ hình dữ liệu trong việc thiết kế chương trình. Xét ví dụ sau.
Ví dụ. Một người giao hàng, hàng ngày anh ta phải chuyển hàng từ một thành
phố đến một số thành phố khác rồi lại quay về thành phố xuất phát. Vấn đề của
anh ta là làm thế nào có được một hành trình chỉ qua mỗi thành phố một lần với
đường đi ngắn nhất có thể được.

Chúng ta thử giúp người giao hàng mơ tả chính xác bài tốn. Trước hết, ta cần
trả lời câu hỏi, những thông tin đã biết trong bài tốn người giao hàng là gì ? Đó
là tên của các thành phố anh ta phải ghé qua và độ dài các con đường có thể có
giữa hai thành phố. Chúng ta cần tìm cái gì ? Một hành trình mà người giao
hàng mong muốn là một danh sách các thành phố A1,A2...An+1 (giả sử có n
thành phố), trong đó các A1 (i=1,2,...,n+1) đều khác nhau, trừ An+1 = A1.
Với một vấn đề đặt ra từ thực tiễn, ta có thể mơ tả chính xác vấn đề đó hoặc các
bộ phận của nó (vấn đề con) bởi một mơ hình tốn học nào đó. Chẳng hạn, mơ
16


-

-

-

hình tốn học thích hợp nhất để mơ tả bài toán người giao hàng là đồ thị. Các
đỉnh của đồ thị là các thành phố, các cạnh của đồ thị là các đường nối hai thành
phố. Trọng số của các cạnh là độ dài các đường nối hai thành phố. Trong thuật
ngữ của lý thuyết đồ thị, danh sách các thành phố biểu diễn hành trình của
người giao hàng, là một chu trình qua tất cả các đỉnh của đồ thị. Như vậy, bài
toán người giao hàng được qui về bài tốn trong lý thuyết đồ thị. Tìm một chu
trình xuất phát từ một đỉnh qua tất cả các đỉnh cịn lại với độ dài ngắn nhất.
Bài tốn người giao hàng là một trong các bài toán đã trở thành kinh điển. Nó
dễ mơ hình hố, song cũng rất khó giải. Chúng ta sẽ quay lại bài toán này.
Cần lưu ý rằng, để tìm ra cấu trúc tốn học thích hợp với một bài toán đã cho,
chúng ta phải phân tích kỹ bài tốn để tìm ra câu trả lời cho các câu hỏi sau.
+ Các thông tin quan trọng của bài tốn có thể biểu diễn bởi các đối tượng tốn
học nào ?

+ Có các mối quan hệ nào giữa các đối tượng ?
+ Các kết quả phải tìm của bài tốn có thể biểu diễn bởi các khái niệm tốn
học nào.
Sau khi đã có mơ hình tốn học mơ tả bài tốn, một câu hỏi đặt ra là, ta phải
làm việc với mơ hình như thế nào để tìm ra lời giải của bài tốn ? Chúng ta sẽ
thiết kế thuật tốn thơng qua các hành động, các phép tốn thực hiện trên các
đối tượng của mơ hình.
Một mơ hình tốn học cùng với các phép tốn có thể thực hiện trên các đối
tượng của mơ hình được gọi là mơ hình dữ liệu. Chẳng hạn, trong mơ hình dữ
liệu đồ thị, trong số rất nhiều các phép tốn, ta có thể kể ra một số phép tốn sau
: tìm các đỉnh kề của mỗi đỉnh, xác định đường đi ngắn nhất nối hai đỉnh bất kỳ,
tìm các thành phần liên thơng, tìm các đỉnh treo,.. Về mặt toán học, danh sách
là một dãy hữu hạn n phần tử (a1, a2, ..., an). Trong mơ hình dữ liệu danh sách,
chúng ta cũng có thể thực hiện một tập hợp rất đa dạng các phép toán, chẳng
hạn như, xác định độ dài của danh sách, xen một phần tử mới vào danh sách,
loại một phần từ nào đó khỏi danh sách, sắp xếp lại danh sách theo một trật tự
nào đó, gộp hai danh sách thành một danh sách.

17


- Trở lại bài tốn người giao hàng. Có nhiều thuật tốn giải bài tốn này. Chẳng
hạn, ta có thể giải bằng phương pháp vét cạn : giả sử có n thành phố, khi đó mỗi
hành trình là một hốn vị của n-1 thành phố (trừ thành phố xuất phát), thành lập
(n-1)! hốn vị, tính độ dài của hành trình ứng với mỗi hốn vị và so sánh, ta sẽ
tìm được hành trình ngắn nhất. Ta cũng có thể giải bài toán bằng phương pháp
qui hoạch động (Phương pháp này sẽ được trình bày ở tập 2 của sách này). Sau
đây ta đưa ra một thuật toán đơn giản. Thuật tốn này tìm ra rất nhanh nghiệm
"gần đúng", trong trường hợp có đường đi nối hai thành phố bất kỳ. Giả sử G là
một đồ thị (Graph), V là tập hợp các đỉnh (Node), E là tập hợp các cạnh của nó.

Giả sử c(u,v) là độ dài (nguyên dương) của cạnh (u,v). Hành trình (Tour) của
người giao hàng có thể xem như một tập hợp nào đó các cạnh. Cost là độ dài
của hành trình. Thuật tốn được biểu diễn bởi thủ tục Salesperson.
procedure Salespersen (G : Graph ; var Tour : set of E ;
var cost : integer) ;
var

v, w : Node
U : set of V ;

begin
Tour : = [ ] ;
Cost : = 0 ;
v : = vo ; {vo - đỉnh xuất phát}
U : = V - [vo] ;
while

U < > [ ] do

begin
Chọn (v, w) là cạnh ngắn nhất với w thuộc U ;
Tour : = Tour + [(v, w)] ;
Cost : = Cost + c (v,w) ;
v :=w;
U : = U - [w] ;
18


end ;
Tour : = Tour + [(v,vo)] ;

Cost : = Cost + c(v,vo) ;
-

-

-

-

end;
Thuật toán Salesperson được xây dựng trên cơ sở mơ hình dữ liệu đồ thị và mơ
hình dữ liệu tập hợp. Nó chứa các thao tác trên đồ thị, các phép toán tập hợp.
Tư tưởng của thuật toán như sau. Xuất phát từ Tour là tập rỗng. Giả sử ta xây
dựng được đường đi từ đỉnh xuất phát v0 tới đỉnh v. Bước tiếp theo, ta sẽ thêm
vào Tour cạnh (v,w), đó là cạnh ngắn nhất từ v tới các đỉnh w không nằm trên
đường đi từ v0 tới v. Để có được chương trình, chúng ta phải biểu diễn đồ thị,
tập hợp bởi các cấu trúc dữ liệu. Sau đó viết các thủ tục (hoặc hàm) thực hiện
các thao tác, các phép toán trên đồ thị, tập hợp có trong thuật tốn.
Tóm lại, q trình giải một bài tốn có thể quy về hai giai đoạn kế tiếp như sau:
+ Xây dựng các mơ hình dữ liệu mơ tả bài tốn. Thiết kế thuật tốn bằng cách
sử dụng các thao tác, các phép toán trên các mơ hình dữ liệu.
+ Biểu diễn các mơ hình dữ liệu bởi các cấu trúc dữ liệu. Với các cấu trúc dữ
liệu đã lựa chọn, các phép toán trên các mơ hình dữ liệu được thể hiện bởi
các thủ tục (hàm) trong ngơn ngữ lập trình nào đó.
Tốn học đã cung cấp cho Tin học rất nhiều cấu trúc toán học có thể dùng làm
mơ hình dữ liệu. Chẳng hạn, các khái niệm toán học như dãy, tập hợp, ánh xạ,
cây, đồ thị, quan hệ, nửa nhóm, nhóm, otomat,...Trong các chương sau chúng ta
sẽ lần lượt nghiên cứu một số mơ hình dữ liệu quan trọng nhất, được sử dụng
thường xun trong các thuật tốn. Đó là các mơ hình dữ liệu danh sách, cây,
tập hợp. Với mỗi mơ hình dữ liệu chúng ta nghiên cứu các cách cài đặt nó bởi

các cấu trúc dữ liệu khác nhau. Trong mỗi cách cài đặt, một số phép tốn trên
mơ hình có thể được thực hiện dễ dàng, nhưng các phép toán khác có thể lại
khơng thuận tiện. Việc lựa chọn cấu trúc dữ liệu nào để biểu diễn mơ hình phụ
thuộc vào từng áp dụng.
Như đã nói, với mỗi mơ hình dữ liệu, chúng ta có thể thực hiện một tập hợp các
phép toán rất đa dạng, phong phú. Song trong nhiều áp dụng, chúng ta chỉ sử

19


dụng mơ hình với một số xác định các phép tốn nào đó. Khi đó chúng ta sẽ có
một kiểu dữ liệu trừu tượng.
- Như vậy, một kiểu dữ liệu trừu tượng (abstract data type) là một mơ hình dữ
liệu được xét cùng với một số xác định các phép tốn nào đó. Chẳng hạn, các
tập hợp chỉ xét với các phép toán : thêm một phần tử vào một tập đã cho, loại
một phần tử khỏi một tập hợp đã cho, tìm xem một phần tử đã cho có nằm trong
một tập hợp hay không, lập thành kiểu dữ liệu trừu tượng (KDLTT) từ điển
(dictionnaire).
- Còn KDLTT hàng (hàng đợi) là mơ hình dữ liệu danh sách cùng với hai phép
tốn chính là : thêm một phần tử mới vào một đầu danh sách, và loại một phần
tử ở một đầu khác của danh sách. Chúng ta sẽ nghiên cứu kỹ một số kiểu dữ
liệu trừu tượng quan trọng nhất : hàng, ngăn xếp (stack), từ điển, hàng ưu tiên.
Với mỗi KDLTT, các cấu trúc dữ liệu để biểu diễn nó sẽ được nghiên cứu.
Chúng ta cũng sẽ đánh giá hiệu quả của các phép toán trong từng cách cài đặt.
3. Thiết kế và giải thuật
3.1. Các tiêu chuẩn đánh giá cấu trúc dữ liệu
- Để đánh giá một cấu trúc dữ liệu chúng ta thường dựa vào một số tiêu chí sau:
- Phản ánh đúng thực tế : Đây là tiêu chuẩn quan trọng nhất, quyết định tính đúng
đắn của tồn bộ bài tốn. Cần xem xét kỹ lưỡng cũng như dự trù các trạng thái
biến đổi của dữ liệu trong chu trình sống để có thể chọn cấu trúc dữ liệu lưu trữ

thể hiện chính xác đối tượng thực tế.
- Ví dụ : Một số tình huống chọn cấu trúc lưu trữ sai :
+ Chọn một biến số nguyên int để lưu trữ tiền thưởng bán hàng (được tính
theo cơng thức tiền thưởng bán hàng = trị giá hàng * 5%), do vậy sẽ làm tròn
mọi giá trị tiền thưởng gây thiệt hại cho nhân viên bán hàng. Trường hợp
này phải sử dụng biến số thực để phản ánh đúng kết quả của cơng thức tính
thực tế.
+ Trong trường trung học, mỗi lớp có thể nhận tối đa 28 học sinh. Lớp hiện có
20 học sinh, mỗi tháng mỗi học sinh đóng học phí $10. Chọn một biến số
nguyên unsigned char ( khả năng lưu trữ 0 - 255) để lưu trữ tổng học phí
của lớp học trong tháng, nếu xảy ra trường hợp có thêm 6 học sinh được
20


nhận vào lớp thì giá trị tổng học phí thu được là $260, vượt khỏi khả năng
lưu trữ của biến đã chọn, gây ra tình trạng tràn, sai lệch.
+ Phù hợp với các thao tác trên đó: Tiêu chuẩn này giúp tăng tính hiệu quả của
đề án: việc phát triển các thuật tốn đơn giản, tự nhiên hơn; chương trình đạt
hiệu quả cao hơn về tốc độ xử lý.
- Ví dụ 1.1: Một tình huống chọn cấu trúc lưu trữ khơng phù hợp:
+ Cần xây dựng một chương trình soạn thảo văn bản, các thao tác xử lý
thường xảy ra là chèn, xoá sửa các ký tự trên văn bản. Trong thời gian xử lý
văn bản, nếu chọn cấu trúc lưu trữ văn bản trực tiếp lên tập tin thì sẽ gây khó
khăn khi xây dựng các giải thuật cập nhật văn bản và làm chậm tốc độ xử lý
của chương trình vì phải làm việc trên bộ nhớ ngồi. Trường hợp này nên
tìm một cấu trúc dữ liệu có thể tổ chức ở bộ nhớ trong để lưu trữ văn bản
suốt thời gian soạn thảo.
3.2. Đánh giá độ phức tạp của thuật toán
- Việc đánh giá độ phức tạp của một thuật tốn quả khơng dễ dàng chút nào. Ở
dây, chúng ta chỉ muốn ước lượng thời gian thực hiện thuận tốn T(n) để có thể

có sự so sánh tương đối giữa các thuật toán với nhau. Trong thực tế, thời gian
thực hiện một thuật tốn cịn phụ thuộc rất nhiều vào các điều kiện khác như
cấu tạo của máy tính, dữ liệu đưa vào, …, ở đây chúng ta chỉ xem xét trên mức
độ của lượng dữ liệu đưa vào ban đầu cho thuật toán thực hiện.
- Để ước lượng thời gian thực hiện thuật toán chúng ta có thể xem xét thời gian
thực hiện thuật tốn trong hai trường hợp:
+ Trong trường hợp tốt nhất: Tmin
+ Trong trường hợp xấu nhất: Tmax
+ Từ đó chúng ta có thể ước lượng thời gian thực hiện trung bình của thuật
toán: Tavg

21


Chương 2
Các kiểu dữ liệu nâng cao
Mã chương: MH19_CH02
Giới thiệu:
Bài này giới thiệu về các kiểu dữ liệu nâng cao trong cấu trúc dữ liệu và giải thuật.
Mục tiêu:
- Trình bày được các kiểu dữ liệu nâng cao;
- Vận dụng được các kiểu dữ liệu nâng cao để lập trình một số bài toán cụ thể
theo yêu cầu;
- Rèn luyện tính cẩn thận, tỉ mỉ, chính xác, tu duy sáng tạo, kỹ năng lập trình và
đảm bảo an tồn cho người và máy tính.
Nội dung:
1. Mảng
- Kiểu dữ liệu mảng là kiểu dữ liệu trong đó mỗi phần tử của nó là một tập hợp
có thứ tự các giá trị có cùng cấu trúc được lưu trữ liên tiếp nhau trong bộ nhớ.
Mảng có thể một chiều hay nhiều chiều. Một dãy số chính là hình tượng của

mảng 1 chiều, ma trận là hình tượng của mảng 2 chiều.
- Một điều đáng lưu ý là mảng 2 chiều có thể coi là mảng một chiều trong đó mỗi
phần tử của nó là 1 mảng một chiều. Tương tự như vậy, một mảng n chiều có
thể coi là mảng 1 chiều trong đó mỗi phần tử là 1 mảng n-1 chiều.
- Hình tượng này được thể hiện rất rõ trong cách khai báo của C.
- Mảng 1 chiều được khai báo như sau:
<Kiểu dữ liệu> <Tên biến>[<Số phần tử>];
- Ví dụ để khai báo một biến có tên a là một mảng nguyên 1 chiều có tối đa 100
phần tử ta phải khai báo như sau:
int a[100];
- Ta cũng có thể vừa khai báo vừa gán giá trị khởi động cho một mảng như sau:
int a[5] = (1, 7, -3, 8, 19);
- Trong trường hợp này C cho phép ta khai báo một cách tiện lợi hơn
int a[] = (1, 7, -3, 8, 19);
22


- Như ta thấy, ta không cần chỉ ra số lượng phần tử cụ thể trong khai báo. Trình
biên dịch của C sẽ tự động làm việc này cho chúng ta.
- Tương tự ta có thể khai báo một mảng 2 chiều hay nhiều chiều theo cú pháp
sau:
<Kiểu dữ liệu> <Tên biến>[<Số phần tử1>][<Số phần tử2>]...;
- Ví dụ, ta có thể khai báo:
int a[100][150];
hay
int a[][]={{1, 7, -3, 8, 19},{4, 5, 2, 8, 9},{21, -7, 45, -3, 4}};
(mảng a sẽ có kích thước là 3x5).
- Kiểu chuỗi ký tự:
+ Chuỗi ký tự là một trong các kiểu dữ liệu có cấu trúc đơn giản nhất và
thường các ngơn ngữ lập trình đều định nghĩa nó như một kiểu cơ bản. Do

tính thông dụng của kiểu chuỗi ký tự các ngôn ngữ lập trình ln cung cấp
sẵn một bộ các hàm thư viện các xử lý trên kiểu dữ liệu này. Đặc biệt trong
C thư viện các hàm xử lý chuỗi ký tự rất đa dạng và phong phú. Các hàm
này được đặt trong thư viện string.lib của C.
+ Chuỗi ký tự trong C được cấu trúc như một chuỗi liên tiếp các ký tự kết thúc
bằng ký tự có mã ASCII bằng 0 (NULL character). Như vậy, giới hạn chiều
dài của một chuỗi ký tự trong C là 1 Segment (tối đa chứa 65335 ký tự), ký
tự đầu tiên được đánh số là ký tự thứ 0.
+ Ta có thể khai báo một chuỗi ký tự theo một số cách sau đây:
char S[10]; //Khai báo một chuỗi ký tự S có chiều dài
// tối đa 10 (kể cả kí tự kết thúc)
char S[]="ABC";// Khai báo một chuỗi ký tự S có chiều
//
dài
bằng
chiều
dài
của
chuỗi
"ABC"
// và giá trị khởi đầu của S là "ABC"
char *S ="ABC";//Giống cách khai báo trên.
+ Trong ví dụ trên ta cũng thấy được một hằng chuỗi ký tự được thể hiện bằng
một chuỗi ký tự đặt trong cặp ngoặc kép “”.

23


+ Các thao tác trên chuỗi ký tự rất đa dạng. Sau đây là một số thao tác thông
dụng:

So sánh 2 chuỗi: strcmp
Sao chép 2 chuỗi: strcpy
Kiểm tra 1 chuỗi nằm trong chuỗi kia: strstr
Cắt 1 từ ra khỏi 1 chuỗi: strtok
Đổi 1 số ra chuỗi: itoa
Đổi 1 chuỗi ra số: atoi, atof, ...
Đổi 1 hay 1 số giá trị ra chuỗi: sprintf
Nhập một chuỗi: gets
Xuất một chuỗi: puts
2. Con trỏ
- Con trỏ là biến chứa địa chỉ của một biến khác. Con trỏ được sử dụng rất nhiều
trong C, một phần là do chúng đôi khi là cách duy nhất để biểu diễn tính tốn,
và phần nữa do chúng thường làm cho chương trình ngắn gọn và có hiệu quả
hơn các cách khác .
- Con trỏ đã từng bị coi như có hại chẳng kém gì lệnh goto do cách sử dụng
chúng đã tạo ra các chương trình khó hiểu. Điều này chắc chắn là đúng khi
người ta sử dụng chúng một cách lơn xộn và do đó tạo ra các con trỏ trỏ đến
đâu đó khơng biết trước được.
2.1. Con trỏ và địa chỉ
- Vì con trỏ chứa địa chỉ của đối tượng nên nó có thể xâm nhập vào đối tượng
gián tiếp qua con trỏ. Giả sử x là một biến kiểu int, và giả sử px là con trỏ được
tạo ra theo một cách nào đó.
- Phép tốn một ngơi & sẽ cho địa chỉ của đối tượng, nên câu lệnh : px=&x; sẽ
gán địa chỉ của biến x cho trỏ px, và px bây giờ được gọi là " trỏ tới biến x ".
Phép toán & chỉ áp dụng được cho các biến và phần tử bảng, kết cấu kiểu
&(x+1) và &3 là không hợp lệ. Lấy đại chỉ của biến register cũng là sai.
- Phép tốn một ngơi * coi là tốn hạng của nó là đại chỉ cần xét và thâm nhập tới
địa chỉ đó để lấy ra nội dung. Nếu biến y có kiểu int thì thì lệnh:
y=*px; sẽ gán giá trị của biến mà trỏ px trỏ tới. Vậy dãy lệnh :
24



-

-

-

-

-

px=&x;
y=*px;
sẽ gán giá trị của x cho y như trong lệnh :
y=x;
Các khai báo cho các biến con trỏ có dạng :
tên kiểu *tên con trỏ
Như trong ví dụ trên, ta khai báo con trỏ px kiểu int :
int *px;
Trong khai báo trên ta đã ngụ ý nói rằng đó là một cách tượng trưng, rằng tổ
hợp *px có kiểu int, tức là nếu px xuất hiện trong ngữ cảnh *px thì nó cũng
tương đương với biến có kiểu int.
Con trỏ có thể xuất hiện trong các biểu thức. Chẳng hạn, nếu px trỏ tới số
ngun x thì *px có thể xuất hiện trong bất kỳ ngữ cảnh nào mà x có thể xuất
hiện.
Ví dụ 2.1.
Lệnh
y=*px+1;
sẽ đặt y lớn hơn x một đơn vị.

Lệnh printf("%d",*px);
sẽ in ra giá trị hiện tại của x
Lệnh: d=sqrt((double) *px);
sẽ gán cho biến d căn bậc hai của x, giá trị này bị buộc phải chuyển sang double
trước khi được chuyền cho sqrt ( cách dùng hàm sqrt ).
Trong các biểu thức kiểu như :
y=*px+1;
phép tốn một ngơi * và & có mức ưu tiên cao hơn các phép toán số học, cho
nên biểu thức này lấy bất ký giá trị nào mà px trỏ tới, cộng với 1 rồi gán cho y.
Con trỏ cũng có thể xuất hiện bên vế trái của phép gán. Nếu px trỏ tới x thì sau
lệnh :
*px=0; x sẽ có giá trị bằng 0. Cũng tương tự các lệnh:
*px+=1;
(*px)++;
sẽ tăng giá trị của x lên 1 dơn vị.
25