CHƯƠNG 1 TONG QUAN Vé GIAI THUẬT VÀ CẤU TRÚC DỮ LIỆU. Mục tiêu 2 Giới thiệu vai trò của việc tổ chức đữ liệu trong một để án tin học. #“ Mối quan hệ giữa giải thuật và cấu trúc dữ liệu. '#' Các yêu câu tổ chức cấu trúc dữ liệu 'ˆ Khái niệm kiểu dữ liệu_cấu trúc dữ liệu *# Tổng quan vẻ đánh giá độ phức tạp giải thuật 1.
VAI TRÒ CỦA CẤU TRÚC DỮ LIỆU TRONG MỘT bE AN TIN HOC + Thực hiện một để án tin học là chuyển bài toán thực tế thành bài toán có thể giải quyết trên máy tính. 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 những đối tượng đó. Vì thế, để 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 thành phần dữ liệu thực tế đa dang, 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 nhất sao cho vừa có thể phản ánh chính xác các đữ liệu thực tế này, 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 edu trúc dữ liệu cho bài toán.
Xây dựng các thao tác xử lý đữ 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 thi hành để 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. + Tuy nhiên 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. 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. Để 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 đao, vì đậu sẽ văng ra ngoài) 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 các đ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ệ chặt chẽ với nhau, được thể hiện qua công thức : 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 vật tự, giải thuật cũng đễ hiểu và đơn giản hơn. Ví dụ 1: Một chương trình quản lý điểm thỉ của sinh viên cẩn lưu trữ các điểm số của 3 sinh viên.
Do mỗi sinh viên có 4 điểm số ứng với 4 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 | Môn 4 SV1 vỉ 9 5 2 sv2 5 0 9 4 sv3 6 x ? 4 Chỉ xét thao tác xử lý là xuất điểm số các môn 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ả 3SV)*4(Môn) = 12 điểm số cẩn lưu trữ, do đó khai báo mắng resu)t như sau : int result {12} = {7, 9 5, 2, 5, 0, 9, 4, 6, 3, 7, 4}; khi đó trong mảng result' các phần tử sẽ được lưu trữ như sau: z[Ƒs|s|z|z|o|9 sw 2 bo Và truy xuất. điểm số môn j của sinh viên ¡ - 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 result: bảngđiểm(dòng i, cộtJ) => resul((-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 sau result i] = bảngđiểm (dong((i / số cột) +1), cột (i % số cột) ) Với phương án này, thao tác xử lý được cài đặt như sau : void t XuatDiem() - ⁄/Xuất điểm số của tất cả sinh viên const int so mon = 4; int sv,mon; for (int i=0; i<12; i+) ( sv = i/so_mon; mon = ¡ $ so non; rint£ (*Điểm môn %d của sv %d là:%d”, mon, sv, zesu1t[1)); } Phương án 2 : Sử dụng mảng 2 chiều Khai báo mảng 2 chiều result c6 kích thước 3 dòng* 4 cột như sau: int result(31(4] =({ 7, 9 5, 2), (5, 0, 9, 4}, (6, 3,7, 4 112 khi đó trong mảng result các phần tử sẽ được lưu trữ như sau : Dòng 0 Sano =7| Sai] =9 result{012] =ð |result[0][3) =2 Dòng 1 |result[1(0) =5 |result[1](1] =0 [result{112] =9|result[11{3) =4 Đồng 2 |result[21(0] =6 | result[2)(1] =3 |resultL2]{2] =7 |result[21(3] =4.
Và truy xuất điểm số mônj của sinh viên ¡ - là phần tử tại (dòng ¡, cột j) trong bảng - cũng chính là phẩn tử nằm ở vị trí (dòng ¡, cột j) trong mảng 8 bảngđiểm(dòng icộtj) => resul[ ¡]U] 'Với phương án này, thao tác xử lý được cài đặt như sau : void XuatDiem() //Xuat điểm số của tất cả sinh viên { int so_mon = 4, so_sv for ( int i=0; i<so_svs i+) for ( int j=0; iSso mon; 4+) print£ (*Điểm môn %d của sv %d là: %d“, j„ i, result {i} {3])7 Y NHẬN XÉT ©ó thể thấy rõ phương án 2 cung cấp một cấu trúc lưu trữ phù hợp với dữ liệu thực tế hơn phương án 1, và do vậy 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, tự nhiên hơn. CÁC TIÊU CHUẨN ĐÁNH GIÁ CẤU TRÚC DỮ LIỆU Do tắm quan trong đã được trình bày trong phần 1.1, nhất thiết phải chú trọng đến việc lựa chọn một phương án tổ chức dữ liệu thích hợp cho để án. Một cấu trúc dữ liệu tốt phải thỏa 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ữ 9 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 = tri 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. 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 nhận vào lớp thì giá trị tổng học phf 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 uó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 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 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 10 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 ở bộ nhớ trong để lưu trữ văn bản suốt thời gian soạn thảo. lưu ý F Đối với mỗi ứng dụng , cẢn chú ý đến thao tác nào được sử dụng nhiều nhất để lựa chọn cấu trúc dữ liệu cho thích hợp. * Tiết kiệm tài nguyên hệ thống: Cấu trúc đữ 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ó 2 loại tài nguyên cẩn lưu tâm nhất : CPU và bộ nhớ. Tiêu chuẩn này nên cân nhắc tùy 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ì khi chọn cấu trúc đữ liệu yếu tố tiết kiệm thời gian xử lý phải đặt nặng hơn tiêu chuẩn sử dụng tối ưu bộ nhớ, và ngược lại.
Ví dụ : Một số tình huống chọn cấu trúc lưu trữ lãng phí: - Sử dụng biến int (2 bytes) để lưu trữ một giá trị cho biết. tháng biện hành. Biết rằng tháng chỉ có thể nhận các giá trị từ 1-12, nên chỉ cần sử dụng kiểu char _ (1 byte) là đủ. - Để lưu trữ danh sách học viên trong một lớp, sử dụng mảng 50 phần tử (giới hạn số học viên trong lớp tối đa là 50).
Nếu số lượng học viên thật sự ít hơn 50, 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ụ xâu liên kết - sẽ được bàn đến trong các chương. KIỂU DỮ LIỆU Máy tính thực sự chỉ có thể lưu trữ đữ liệu ở dạng nhị phân thô. Nếu muốn phản ánh được dữ liệu thực tế đa dạng và phong phú,cẩn phải xây dựng những phép ánh xạ, những qui 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 đử liệu.
Như đã phân tích ở phần 1.1, 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.