GIAO TRINH CAU TRUC DU LIEU & GIAI THUAT

GIÁO TRÌNH

CẤU TRÚC DỮ LIỆU










- 2003 -

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
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 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:


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:

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



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]
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<12; i++)
{ sv = i/somon;
mon=i % somon;
printf(“Điểm môn %d của SV %d là: %d”, mon, sv,
diem[i]);
}
}
Phương án 2: Sử dụng mảng hai chiều
Khai báo mảng 2 chiều diem có kích thước 3 cột * 4 dòng 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:

cột 0
cột 1
cột 2

Dòng 0
diem[0][0]=8
diem[0][1]=6
diem[0][2]=4

Dòng 1
diem[1][0]=9
diem[1][1]=5
diem[1][2]=3

Dòng 2
diem[2][0]=6
diem[2][1]=7
diem[2][2]=2

Dòng 3
diem[3][0]=5
diem[3][1]=6
diem[3][2]=5

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 for(int j=0; j printf(“Điểm môn %d của SV %d là: %d”, j, i,
diem[i][j]);
}

Nhận xét:
Ta có thể thấy rằng phương án 2 cung cấp một cấu trúc dữ liệu phù hợp với dữ liệu thực tế hơn phương án 1, do đó giải thuật xử lý trên cấu trúc dữ liệu của phương án 2 cũng đơn giản và tự nhiên hơn.

2- Các tiêu chuẩn đánh giá cấu trúc dữ liệu:
Qua phần trên ta đã thấy được vai trò và tầm quan trọng của việc lưa chọn một phương án tổ chức dữ liệu thích hợp trong một chương trình hay một đề án tin học. Một cấu trúc dữ liệu tốt phải thoả mãn các tiêu chuẩn 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 toàn bộ bài toá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ố 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 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à đủ.
Để 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}
Oc = {lấy mã ASCII của ký tự, biến đổi ký tự thường thành ký tự hoa…}
– Giả sử