Giáo trình cấu trúc dữ liệu part 2

Tham khảo tài liệu giáo trình cấu trúc dữ liệu part 2, công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Giáo trình cấu trúc dữ liệu part 2Cấu trúc dữ liệu Chương I: Mở đầu if có cạnh nối giữa v và w found=1; else w= đỉnh kế tiếp trong newclr; } if found==0 { Đánh dấu v đã được tô màu; Thêm v vào Newclr; } v= đỉnh chưa tô màu kế tiếp trong G; } } 4. Tóm tắt Từ những thảo luận trên chúng ta có thể tóm tắt các bước tiếp cận với một bài toán baogồm: 1. Mô hình hoá bài toán bằng một mô hình toán học thích hợp. 2. Tìm giải thuật trên mô hình này. Giải thuật có thể mô tả một cách không hình thức, tức là nó chỉ nêu phương hướng giải hoặc các bước giải một cách tổng quát. 3. Phải hình thức hoá giải thuật bằng cách viết một thủ tục bằng ngôn ngữ giả, rồi chi tiết hoá dần (mịn hoá) các bước giải tổng quát ở trên, kết hợp với việc dùng các kiểu dữ liệu trừu tượng và các cấu trúc điều khiển trong ngôn ngữ lập trình để mô tả giải thuật. Ở bước này, nói chung, ta có một giải thuật tương đối rõ ràng, nó gần giống như một chương trình được viết trong ngôn ngữ lập trình, nhưng nó không phải là một chương trình chạy được vì trong khi viết giải thuật ta không chú trọng nặng đến cú pháp của ngôn ngữ và các kiểu dữ liệu còn ở mức trừu tượng chứ không phải là các khai báo cài đặt kiểu trong ngôn ngữ lập trình. 4. Cài đặt giải thuật trong một ngôn ngữ lập trình cụ thể (Pascal,C,...). Ở bước này ta dùng các cấu trúc dữ liệu được cung cấp trong ngôn ngữ, ví dụ Array, Record,... để thể hiện các kiểu dữ liệu trừu tượng, các bước của giải thuật được thể hiện bằng các lệnh và các cấu trúc điều khiển trong ngôn ngữ lập trình được dùng để cài đặt giải thuật.Tóm tắt các bước như sau: 17 TrangCấu trúc dữ liệu Chương I: Mở đầu Mô hình toán học Kiểu dữ liệu trừu tượng Cấu trúc dữ liệu Giải thuật không hình thức Chương trình ngôn ngữ giả Chương trình Pascal, C,...II. KIỂU DỮ LIỆU TRỪU TƯỢNG (ABSTRACT DATA TYPE -ADT) 1. Khái niệm trừu tượng hóa Trong tin học, trừu tượng hóa nghĩa là đơn giản hóa, làm cho nó sáng sủa hơn và dễ hiểuhơn. Cụ thể trừu tượng hóa là che đi những chi tiết, làm nổi bật cái tổng thể. Trừu tượng hóacó thể thực hiện trên hai khía cạnh là trừu tượng hóa dữ liệu và trừu tượng hóa chương trình. 2. Trừu tượng hóa chương trình Trừu tượng hóa chương trình là sự định nghĩa các chương trình con để tạo ra các phéptoán trừu tượng (sự tổng quát hóa của các phép toán nguyên thủy). Chẳng hạn ta có thể tạora một chương trình con Matrix_Mult để thực hiện phép toán nhân hai ma trận. Sau khiMatrix_mult đã được tạo ra, ta có thể dùng nó như một phép toán nguyên thủy (chẳng hạnphép cộng hai số). Trừu tượng hóa chương trình cho phép phân chia chương trình thành các chương trìnhcon. Sự phân chia này sẽ che dấu tất cả các lệnh cài đặt chi tiết trong các chương trình con.Ở cấp độ chương trình chính, ta chỉ thấy lời gọi các chương trình con và điều này được gọilà sự bao gói. Ví dụ như một chương trình quản lý sinh viên được viết bằng trừu tượng hóa có thể là: void Main() { Nhap( Lop); Xu_ly (Lop); Xuat (Lop); } Trong chương trình trên, Nhap, Xu_ly, Xuat là các phép toán trừu tượng. Chúng che dấubên trong rất nhiều lệnh phức tạp mà ở cấp độ chương trình chính ta không nhìn thấy được.Còn Lop là một biến thuộc kiểu dữ liệu trừu tượng mà ta sẽ xét sau. Chương trình được viết theo cách gọi các phép toán trừu tượng có lệ thuộc vàocách cài đặt kiểu dữ liệu không? 18 TrangCấu trúc dữ liệu Chương I: Mở đầu 3. Trừu tượng hóa dữ liệu Trừu tượng hóa dữ liệu là định nghĩa các kiểu dữ liệu trừu tượng Một kiểu dữ liệu trừu tượng là một mô hình toán học cùng với một tập hợp các phép toán(operator) trừu tượng được định nghĩa trên mô hình đó. Ví dụ tập hợp số nguyên cùng vớicác phép toán hợp, giao, hiệu là một kiểu dữ liệu trừu tượng. Trong một ADT các phép toán có thể thực hiện trên các đối tượng (toán hạng) không chỉthuộc ADT đó, cũng như kết quả không nhất thiết phải thuộc ADT. Tuy nhiên phải có ítnhất một toán hạng hoặc kết quả phải thuộc ADT đang xét. ADT là sự tổng quát hoá của các kiểu dữ liệu nguyên thuỷ. Để minh hoạ ta ...