GIÁO TRÌNH
CẤU TRÚC DỮ LIỆU
- 2003 -
Giáo trình Cấu trúc dữ liệu
Lời nói đầu
Cấu trúc dữ liệu là môn học chính yếu của chuyên
ngành Công nghệ thông tin, là kiến thức nền tảng cho
những người lập trình. Nhằm xây dựng một giáo trình
vừa đảm bảo tính chuẩn mực của sách giáo khoa, vừa đáp
ứng nhu cầu thực hành của chuyên viên. Chúng tôi đã
tham khảo nhiều tài liệu giá trị của các tác giả trong và
ngoài nước nhằm cung cấp kiến thức về môn học Cấu
trúc dữ liệu một cách có hệ thống, nhiều vấn đề được
minh hoạ trực quan và hướng dẫn theo từng bước lập
trình cụ thể cho học viên.
Mặc dù rất nhiều cố gắng nhưng chắc chắn không
thể tránh được thiếu sót. Chúng tôi rất mong nhận được
các ý kiến đóng góp để giáo trình ngày càng được hoàn
thiện.
Nhóm biên soạn
2
Giáo trình Cấu trúc dữ liệu
Chương 1: CÁC CẤU TRÚC DỮ LIỆU CƠ BẢN
VÀ GIẢI THUẬT
1- Vai trò của cấu trúc dữ liệu:
Xây dựng một đề án tin học thực chất là chuyển
bài toán thực tế thành một bài toán có thể giải quyết trên
máy tính. Mà một bài toán thực tế bất kỳ đều bao gồm các
đối tượng dữ liệu và các yêu cầu xử lý trên các đối tượng
đó. Như vậy, để xây dựng một mô hình tin học phản ánh
được bài toán thực tế cần chú trọng đến hai vấn đề:
Tổ chức biểu diễn các đối tượng thực tế:
Các đối tượng dữ liệu thực tế rất đa dạng, phong
phú và thường chứa đựng những quan hệ nào đó với nhau,
do đó trong mô hình tin học của bài toán, cần phải tổ
chức, xây dựng các cấu trúc thích hợp sao cho vừa có thể
phản ánh chính xác các dữ liệu thực tế đó, vừa có thể dễ
dàng dùng máy tính để xử lý. Công việc này được gọi là
xây dựng cấu trúc dữ liệu cho bài toán.
Xây dựng các thao tác xử lý dữ liệu:
Từ những yêu cầu xử lý thực tế, cần tìm ra các
giải thuật tương ứng để xác định trình tự các thao tác máy
tính phải tác động lên dữ liệu để cho ra kết quả mong
muốn, đây là bước xây dựng giải thuật cho bài toán.
Trên thực tế khi giải quyết một bài toán trên máy
tính chúng ta thường có khuynh hướng chỉ chú trọng đến
việc xây dựng giải thuật mà quên đi tầm quan trọng của
việc tổ chức dữ liệu trong bài toán. Cần nhớ rằng: Giải
3
Giáo trình Cấu trúc dữ liệu
thuật phản ánh các phép xử lý, còn đối tượng xử lý của
giải thuật lại là dữ liệu, chính dữ liệu chứa đựng các
thông tin cần thiết để thực hiện giải thuật. Vì vậy để xác
định được giải thuật phù hợp cần phải biết nó tác động
đến loại dữ liệu nào (ví dụ để làm nhuyễn các hạt đậu,
người ta dùng cách xay chứ không băm bằng dao, vì đậu
sẽ văng ra ngoài và sẽ mất thời gian hơn nhiều) và khi
chọn lựa cấu trúc dữ liệu cũng cần phải hiểu rõ những
thao tác nào sẽ tác động đến nó (ví dụ để biểu diễn điểm
số của sinh viên người ta dùng số thực thay vì chuỗi ký tự
vì còn phải thực hiện thao tác tính trung bình từ những
điểm số đó). Như vậy trong một đề án tin học, giải thuật
và cấu trúc dữ liệu có mối quan hệ với nhau, chúng được
thể hiện qua công thức nổi tiếng của nhà toán học người
Thụy sĩ Niklaus Wirth - là tác giả của ngôn ngữ lập trình
Pascal như sau:
Cấu trúc dữ liệu + Giải thuật = Chương
trình
Với một cấu trúc dữ liệu đã chọn, sẽ có những
giải thuật tương ứng, phù hợp. Khi cấu trúc dữ liệu thay
đổi thường giải thuật cũng phải thay đổi theo để tránh
việc xử lý gượng ép, thiếu tự nhiên trên một cấu trúc
không phù hợp. Hơn nữa, một cấu trúc dữ liệu tốt sẽ giúp
giải thuật xử lý trên đó có thể phát huy tác dụng tốt hơn,
vừa đáp ứng nhanh vừa tiết kiệm tài nguyên, đồng thời
giải thuật cũng dễ hiểu và đơn giản hơn.
Ví dụ: một chương trình quản lý điểm thi của sinh
viên cần lưu trữ các điểm số của 4 sinh viên. Do mỗi sinh
viên có 3 diểm số ứng với 3 môn học khác nhau nên dữ
liệu có dạng bảng như sau:
4
Giáo trình Cấu trúc dữ liệu
Sinh viên Môn 1 Môn 2 Môn 3
SV1 8 6 4
SV2 9 5 3
SV3 6 7 2
SV4 5 6 5
Chỉ xét thao tác xử lý là xuất điểm số các môn học
của từng sinh viên. Giả sử có các phương án tổ chức lưu
trữ sau:
Phương án 1: Sử dụng mảng một chiều
Có tất cả 4(sv) x 4(môn) = 12 điểm số cần lưu trữ,
do đó khai báo mảng diem như sau:
int diem [12] = { 8 6 4
9 5 3
6 7 2
5 6 5 };
Khi đó trong mảng diem các phần tử sẽ được lưu trữ như
sau:
8 6 4 9 5 3 6 7 2 5 6 5
SV1 SV2 SV3 SV4
Và truy xuất điểm số môn j của sinh viên i – (là
phần tử tại dòng i, cột j trong bảng) - phải sử dụng một
công thức xác định chỉ số tương ứng trong mảng diem:
bảngđiểm(dòng i, cột j) => diem[((i-1)*số cột) +j]
5
Giáo trình Cấu trúc dữ liệu
Ngược lại, với một phần tử bất kỳ trong mảng,
muốn biết đó là điểm số của sinh viên nào, môn gì, phải
dùng công thức xác định như sau:
diem[i] => diem[((i-1)*số cột) + j]
ở phương án này, thao tác xử lý được cài đặt như sau:
void indiem()
{ const int somon = 3;
int sv, mon;
for (int i=0; i Giáo trình Cấu trúc dữ liệu
Như vậy truy xuất điểm số môn j của sinh viên i là
phần tử tại dòng i cột j trong bảng – cũng chính là phần
tử nằm ở vị trí dòng i cột j trong mảng.
bảngđiểm(dòng i, cột j) => diem[i][j]
ở phương án này, thao tác xử lý được cài đặt như sau:
void indiem()
{ int somon = 3, sosv = 4;
for (int i=0; i Giáo trình Cấu trúc dữ liệu
đổ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ố trường hợp chọn cấu trúc dữ liệu
sai:
Chọn một số nguyên int để lưu trữ điểm trung
bình của sinh viên (được tính theo công thức trung
bình cộng của các môn học có hệ số), như vậy sẽ
làm tròn mọi điểm số của sinh viên gây ra việc
đánh giá sinh viên không chính xác qua điểm số.
Trong 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ế cũng như phản ảnh chính xác kết quả học tập
của sinh viên.
Trong trường phổ thông, một lớp có 50 học sinh,
mỗi tháng đóng quỹ lớp 1.000 đồng. Nếu chọn một
biến số kiểu unsigned int (khả năng lưu trữ 0 –
65535) để lưu trữ tổng tiền qũy của lớp học trong
tháng, nếu xảy ra trường hợp trong hai tháng liên
tiếp không có chi hoặc tăng tiền đóng quỹ của mỗi
học sinh lên 2.000 đồng thì tổng qũy lớp thu được
là 100.000 đồng, vượt khỏi khả năng lưu trữ của
biến đã chọn, gây nên tình trạng tràn, sai lệnh. Như
vậy khi chọn biến dữ liệu ta phải tính đến các
trường hợp phát triển của đại lượng chứa trong
biến để chọn liệu dữ liệu thích hợp. Trong trường
hợp trên ta có thể chọn kiểu long (có kích thước 4
bytes, khả năng lưu trữ là -2147483648
2147483647) để lưu trữ tổng tiền quỹ lớp.
Phù hợp với các thao tác xử lý : tiêu chuẩn này
giúp tăng tính hiệu quả của đề án: phát triển các thuật
8
Giáo trình Cấu trúc dữ liệu
toá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ụ: một số trường hợp chọn cấu trúc dữ liệu
không phù hợp
Khi 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ớ ngoà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 có thể tổ chức ở bộ nhớ
trong để lưu trữ văn bản suốt thời gian soạn thảo.
Tiết kiệm tài nguyên hệ thống: cấu trúc dữ liệu
chỉ nên sử dụng tài nguyên hệ thống vừa đủ để đảm
nhiệm được chức năng của nó. Thông thường có hai loại
tài nguyên cần lưu tâm nhất là CPU và bộ nhớ. Tiêu
chuẩn này nên cân nhắc tuỳ vào tình huống cụ thể khi
thực hiện đề án. Nếu tổ chức sử dụng đề án cần có
những xử lý nhanh thì chọn cấu trúc dữ liệu có yếu tố
tiết kiệm thời gian xử lý ưu tiên hơn tiêu chuẩn sử dụng
tối ưu bộ nhớ, và ngược lại.
Ví dụ: một số trường hợp chọn cấu trúc dữ liệu
gây lãng phí
Sử dụng biến int (2 bytes) để lưu trữ một giá trị
thông tin về ngày trong tháng. Vì một tháng chỉ có
thể nhận các giá trị từ 1-31 nên chỉ cần sử dụng
biến char (1 byte) là đủ.
9
Giáo trình Cấu trúc dữ liệu
Để lưu trữ danh sách nhân viên trong công ty mà sử
dụng mảng 1000 phần tử. Nếu số lượng nhân viên
thật sự ít hơn 1000 (bị giảm hoặc biên chế không
đủ) thì gây lãng phí. Trường hợp này cần có một
cấu trúc dữ liệu linh động hơn mảng – ví dụ danh
sách liên kết.
3- Khái niệm về kiểu dữ liệu:
Máy tính chỉ có thể lưu trữ dữ liệu ở dạng nhị
phân sơ cấp. Để phản ảnh được dữ liệu thực tế đa dạng
và phong phú, cần phải xây dựng các phép ánh xạ, những
quy tắc tổ chức phức tạp che lên tầng dữ liệu thô, nhằm
đưa ra những khái niệm logic về hình thức lưu trữ khác
nhau thường được gọi là kiểu dữ liệu. Như đã phân tích ở
mục trước, giữa hình thức lưu trữ dữ liệu và các thao tác
xử lý trên đó có quan hệ mật thiết với nhau. từ đó có thể
đưa ra một định nghĩa cho kiểu dữ liệu như sau:
3.1- Định nghĩa kiểu dữ liệu
Kiểu dữ liệu T được xác định bởi một bộ ,
với:
V: tập các giá trị hợp lệ mà một đối tượng
kiểu T có thể lưu trữ.
O: tập các thao tác xử lý có thể thi hành trên
đối tượng kiểu T.
Ví dụ: – Giả sử có kiểu dữ liệu mẫu tự = với
Vc = {a-z, A-Z}
10
Giáo trình Cấu trúc dữ liệu
Oc = {lấy mã ASCII của ký tự, biến đổi ký tự
thường thành ký tự hoa…}
– Giả sử có kiểu dữ liệu số nguyên = với
Vi = {–32768 .. 32767}
Oi = {+, – , *, /, %}
Như vậy, muốn sử dụng một kiểu dữ liệu cần
nắm vững cả nội dung dữ liệu được phép lưu trữ và các
xử lý tác động trên đó.
Các thuộc tính của một kiểu dữ liệu bao gồm:
• Tên kiểu dữ liệu
• Miền giá trị
• Kích thước lưu trữ
• Tập các toán tử tác động lên kiểu dữ liệu
3.2- Các kiểu dữ liệu cơ bản
Các loại dữ liệu cơ bản thường là các loại dữ liệu
đơn giản, không có cấu trúc. Chúng thường là các giá trị
vô hướng như các số nguyên, số thực, các ký tự, các giá
trị logic, … Các loại dữ liệu này do tính thông dụng và
đơn giản của nó, thường được các ngôn ngữ lập trình cấp
cao xây dựng sẵn như một thành phần của ngôn ngữ để
giảm nhẹ công việc cho người lập trình. Chính vì vậy đôi
khi người ta còn gọi chúng là các kiểu dữ liệu định sẵn.
Thông thường, các kiểu dữ liệu cơ bản gồm:
• Kiểu có thứ tự rời rạc: số nguyên, ký tự,
logic, liệt kê, miền con, …
• Kiểu không rời rạc: số thực
11
Giáo trình Cấu trúc dữ liệu
Tùy ngôn ngữ lập trình, các kiểu dữ liệu định nghĩa
sẵn có thể khác nhau đôi chút. Với ngôn ngữ C, các kiểu
dữ liệu này chỉ gồm số nguyên, số thực, ký tự. Và theo
quan điểm của C, kiểu ký tự thực chất cũng là kiểu số
nguyên về mặt lưu trữ, chỉ khác về cách sử dụng. Ngoài
ra, giá trị logic ĐÚNG (TRUE) và giá trịc logic SAI
(FALSE) được biểu diễn trong C như là các giá trị nguyên
khác zero và zero. Trong khi đó PASCAL định nghĩa tất cả
các kiểu dữ liệu cơ sở đã liệt kê ở trên và phân biệt chúng
một cách chặt chẽ. Trong giáo trình này sử dụng ngôn ngữ
C để minh hoạ.
Các kiểu dữ liệu định sẵn trong C gồm:
Tên kiểu Kthướ Miền giá trị Ghi chú
c
char 1 byte -128...127 Có thể dùng như số
nguyên 1 byte có
dấu hoặc kiểu ký
tự
unsign char 1 byte 0...255 số nguyên 1 byte
không dấu
int 2 bytes -32768...32767
unsigned 2 byte 0..65355 gọi tắt là unsign
int
long 4 bytes -232 ... 231-1
unsigned 4 bytes 0 ... 232-1
long
float 4 bytes 3.4E-38 … giới hạn chỉ trị
3.4E38 tuyệt đối. Các giá
trị Giáo trình Cấu trúc dữ liệu
nghĩa
double 8 bytes1.7E-3.8 …
1.7E3.8
long double 10 bytes 3.4E-4932 …
1.1E4932
Một số lưu ý:
Kiểu char trong C có thể dùng theo hai cách:
số nguyên một byte hoặc ký tự.
Trong C không định nghĩa kiểu logic (boolean)
mà xem một số nguyên khác không là TRUE và
giá trị 0 là FALSE khi cần xét các giá trị logic.
Như vậy trong C thực chất chỉ có 2 loại dữ liệu
cơ bản là số nguyên và số thực.
Trong C các số nguyên có thể được thể hiện
trong 3 hệ cơ số là hệ thập lục phân, hệ thập
phân và hệ bát phân.
3.3- Các kiểu dữ liệu có cấu trúc
Các kiểu dữ liệu cơ sở rất thô sơ, đơn giản và
không phản ánh được các đối tượng tự nhiên cũng như
đầy đủ yếu tố của sự vật thực tế, do đó dẫn đến nhu cầu
phải xây dựng các kiểu dữ liệu mới dựa trên việc tổ
chức, liên kết các thành phần dữ liệu có kiểu dữ liệu cơ
sở đã được định nghĩa. Những kiểu dữ liệu được xây
dựng như thế gọi là kiểu dữ liệu có cấu trúc. Hầu hết các
ngôn ngữ lập trình đều cài đặt sẵn một số kiểu có cấu
trúc cơ bản như mảng chuỗi, tập tin, bản ghi (struct trong
13
Giáo trình Cấu trúc dữ liệu
C hay record trong Pascal),… và cung cấp cơ chế cho lập
trình viên tự định nghĩa kiểu dữ liệu mới.
Ví dụ: Để mô tả một đối tượng nhân viên, cần
quan tâm đến các thông tin sau:
- Mã nhân viên : chuỗi ký tự
- Tên nhân viên: chuỗi ký tự
- Ngày sinh : kiểu ngày tháng năm
- Nơi sinh : chuỗi ký tự
- Lương căn bản: số nguyên
để mô tả thông tin điểm thi ta dùng kiểu dữ liệu cơ sở:
long luongcb;
Các thông tin khác đòi hỏi phải dùng kiểu có cấu trúc sau:
char manv[10];
char tennv[30];
char noisinh[50];
Để thể hiện thông tin về ngày tháng năm sinh cần
phải xây dựng một kiểu bản ghi:
typedef struct tagDate{
char ngay;
char thang;
char nam;
} date;
Từ trên, ta có thể xây dựng kiểu dữ liệu thể hiện
thông tin về một nhân viên:
typedef struct tagNhanVien{
char manv[10];
14
Giáo trình Cấu trúc dữ liệu
char tennv[30];
date ngaysinh;
char noisinh[50]
long luongcb;
}
Giả sử đã có cấu trúc phù hợp để lưu trữ một nhân
viên, nhưng thực tế lại cần quản lý nhiều nhân viên, lúc
đó nảy sinh nhu cầu xây dựng kiểu dữ liệu mới. Mục tiêu
của việc nghiên cứu cấu trúc dữ liệu chính là tìm những
phương cách thích hợp để tổ chức, liên kết dữ liệu, hình
thành các kiểu dữ liệu có cấu trúc từ những kiểu dữ liệu
đã được định nghĩa.
3.4- Một số kiểu dữ liệu có cấu trúc cơ bản
a. 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 luôn cung
cấp sẵn một bộ các hàm thư viên xử lý trên kiểu dữ liệu
này. 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 (chứa tối đa 65535) ký
tự, ký tự đầu tiên được đánh số thứ tự 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:
15
Giáo trình Cấu trúc dữ liệu
char s[10]; // khai báo một chuỗi ký tự có chiều dài
// tối đa là 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
Ở ví dụ trên ta thấy rằng một hằng chuỗi ký tự
được thể hiện bằng một chuỗi ký tự đặt trong cặp dấu
nháy kép.
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 một từ ra khỏi một chuỗi strok
Đổi 1 số ra chuỗi itoa
Đổi 1 chuỗi ra số atoi, atof
Đổi 1 hay một số giá trị ra chuỗi sprintf
Nhập một chuỗi gets
Xuất một chuỗi puts
b. Kiểu mảng (array):
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,
thường đượ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ể
16
Giáo trình Cấu trúc dữ liệu
coi là mảng 1 chiều trong đó mỗi phần tử là 1 mảng n-1
chiều.
Trong C mảng 1 chiều được khai báo như sau:
[];
Ví dụ để khai báo một mảng a chứa tối đa 50 số
nguyên ta khai báo như sau:
int a[50];
Ta 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] = {3,5,7,-9,16};
Trong trường hợp trên C cho phép ta khai báo một
cách tiện lợi hơn như sau:
int a[] = {3,5,7,-9,16};
Như trên ta thấy không cần chỉ ra số lượng phần
tử cụ thể trong khai báo. Trình biên dịch sẽ tự động là
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:
[][];
Ví dụ ta có thể khai báo:
int a[50][40];
hay
int a[][] = { {1,5,6,-7,4},
{-8,9,-2,5,3},
{4,-6,7,3,1} }
17
Giáo trình Cấu trúc dữ liệu
(mảng a sẽ có kích thước là 3x5)
c. Kiểu cấu trúc (struct):
Kiểu cấu trúc là kiểu dữ liệu mà trong đó mỗi
phần tử của nó là tập hợp các giá trị có thể khác cấu trúc.
Kiểu mẫu tin cho phép chúng ta mô tả các đối tượng có
cấu trúc phức tạp.
Khai báo tổng quát của kiểu struct như sau:
typedef struct {
;
;
…
}[];
Ví dụ để khai báo thông tin về một sinh viên ta
có thể khai báo một kiểu dữ liệu như sau:
struct tagNhanVien
{ char MaSo[5];
char HoTen[30];
int NamSinh;
char GioiTinh;
char DiaChi[50];
}
Kiểu cấu trúc bổ sung nhiều thiếu sót của kiểu
mảng, giúp ta có khả năng thể hiện các đối tượng đa
dạng của thế giới hiện thực vào trong máy tính một cách
dễ dàng, chính xác hơn.
d. Kiểu Union:
18
Giáo trình Cấu trúc dữ liệu
Kiểu u nion là một dạng cấu trúc dữ liệu
đặc biệt của ngôn ngữ C. Nó rất giống với kiểu cấu trúc.
Chỉ khác một điều, trong kiểu union, các trường được
phép dùng chung một vùng nhớ, ta có thể truy xuất dưới
các dạng khác nhau.
Khai báo tổng quát của kiểu union như sau:
typedef union {
;
;
;
…
}[];
Ví dụ: ta có thể định nghĩa kiểu số như sau:
typedef union tagNumber {
int i;
long l;
} Number;
Việc truy xuất đến một trường trong union được
thực hiện hoàn toàn giống như trong struct. Giả sử có
biến n kiểu Number. Khi đó, n.i là một số kiểu int còn n.l
là một số kiểu long, nhưng cả hai đều dùng chung một
vùng nhớ, Vì vậy, khi ta gán: n.i = 0xfd03;
thì giá trị của n.i cũng bị thay đổi (n.i sẽ bằng 3)
Việc dùng kiểu union rất có lợi khi cần khai báo
các cấu trúc dữ liệu mà nội dung của nó thay đổi tùy
19
Giáo trình Cấu trúc dữ liệu
trạng thái. Ví dụ để mô tả các thông tin về một nhân viên
ta có thể khai báo một kiểu dữ liệu như sau:
struct tagNhanVien
{ char HoTen[30];
int NamSinh;
char NoiSinh[50];
char GioiTinh; //0: Nữ, 1: Nam
char DiaChi[50];
char Ttgd; //0: Không có gia đình, 1: Có gia đình
union { char tenVo[30];
char tenChong[30];
}
} NhanVien;
4- Đánh giá độ phức tạp của giải thuật:
Hầu hết các bài toán đều có nhiều thuật toán khác
nhau để giải quyết chúng. Như vậy, làm thế nào để chọn
được sự cài đặt tốt nhất? Đây là một lĩnh vực được quan
tâm nghiên cứu nhiều trong khoa học máy tính. Chúng ta
sẽ khảo sát các kết quả nghiên cứu mô tả các tính năng
của các thuật toán cơ bản cũng như so sánh các thuật toán
đồng thời cũng sẽ khảo sát hướng dẫn tổng quát về phân
tích thuật toán.
Khi nói đến hiệu quả của một thuật toán, người ta
thường quan tâm đến chi phí cần dùng để thực hiện nó.
Chi phí này thể hiện qua việc sử dụng tài nguyên như bộ
nhớ, thời gian sử dụng CPU, … Ta có thể đánh giá thuật
toán bằng phương pháp thực nghiệm thông qua việc cài
20
Copyright by webtailieu.net