Cấu trúc dữ liệu và giải thuật I - Bài 1

TỔNG QUAN VỀ GIẢI THUẬT VÀ CẤU TRÚC DỮ LIỆU Mục tiêu Giới thiệu vai trò của việc tổ chức dữ 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. Trừu tượng hoá dữ liệu Tổng quan về đánh giá độ phức tạp giải thuật
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật I - Bài 1 Bài 1 : TỔNG QUAN VỀ GIẢI THUẬT VÀ CẤU TRÚC DỮ LIỆU Mục tiêu  Giới thiệu vai trò của việc tổ chức dữ 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.  Trừu tượng hoá dữ liệu  Tổng quan về đánh giá độ phức tạp giả i thuật Nội dung Vai trò của Cấu trúc dữ liệu trong một đề án tin học  Trừu tượng hóa dữ liệu  Ðịnh nghĩa kiểu dữ liệu  Các kiểu dữ liệu cơ bản  Các kiểu dữ liệu có cấu trúc  Một số kiểu dữ liệu có cấu trúc cơ bản  Ðánh giá độ phức tạp giải thuật  Các bước phân tích thuật toán  Sự phân lớp các thuật toán  Phân tích trường hợp trung bình  Bài tập Bài tập lý thuyết  Bài tập thực hành  I. Vai trò của Cấu trúc dữ liệu trong một đề án tin học 1. Mối liên hệ giữa cấu trúc dữ liệu và giải thuật 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 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 nhất sao cho vừa có thể phản ánh chính xác các dữ 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 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 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 dao, 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 : Hình 1 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 dễ hiễu và đơn giản hơn. Ví dụ 1: 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 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ôn3 Môn4 SV 1 7 9 5 2 SV 2 5 0 9 4 SV 3 6 3 7 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ả 3(SV)*4(Môn) = 12 điểm số cần lưu trữ, do đó khai báo mảng result 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: Hình 2 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 result: bảngđiểm(dòng i, cột j) result[((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 sau bảngđiểm (dòng((i / số cột) +1), cột (i % số cột) ) result[ i ] Þ Với phương án này, thao tác xử lý được cài đặt như sau : //Xuất điểm số của tất cả sinh viên void XuatDiem() { const int so_mon = 4; int sv,mon; for (int i=0; i result[i]); } } Phương án 2 : Sử dụng mảng 2 chiều Khai báo mảng 2 chiều result có kích thước 3 dòng* 4 cột như sau : int result[3][4] ={{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 : Cột 0 Cột 1 Cột 2 Cột 3 Dòng 0 result[0][0] result[0][1] result[0][2] result[0][3] =7 =9 =5 =2 Dòng 1 result[1][0] result[1][1] result[1][2] result[1][3] =5 =0 =9 =4 ...