tailieunhanh - Cẩm nang thuật toán tập 1 part 2

Tham khảo tài liệu 'cẩm nang thuật toán tập 1 part 2', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 42 CÁC CẦU TRÚC Dữ LIỆU cơ BÀN Đặc trưng xác định của một kiểu dữ liệu trừu tượng là không có gì nằm bên ngoài các định nghĩa của CTDL và các thuật toán thao tác trên nó là có thể tham khảo được tới bất kỳ một thứ gi nằm bên trong ngoại trừ là qua các lênh gọi hàm và thù tục cho các thao tác cơ bản. Động cơ chính cho việc phát triển các kiểu đữ liệu trừu tượng đà như là một cơ chế dùng cho việc tổ chức các chương trình lớn. Chúng cung cấp một phương pháp để giới hạn kích thước và độ phức tạp của giao tiếp giữa cấc thuật toán có thể là phức tạp cùng các CTDL tương ứng với các chương trĩnh có thể là một số lượng lớn các chương trình mà nó dùng các thuật toán và CTDL. Đỉêu nãy khiến cho việc hiểu chương trình lớn một cách dê dàng hơn và làm cho việc thay đổi và nâng cấp các thuật toán cơ bân trở nên thuận tiện hơn. Các ngăn xếp và hang đợi là các ví dụ cổ điển vê các kiểu dư liệu trừu tượng hâu hết các chương trình chỉ cân dược quan tâm vè một vài thao tác cơ bản được định nghĩa tốt chứ không phải là các chi tiết vê các mối liên kết và các chỉ mục. Mảng và xâu liên kết dến lượt nó có thể được xem như là sự tinh chế của một kiểu dữ liêu trừu tượng cơ bân được gọi là xàu tuyến tính. Mòi cái trong chúng có thể hỗ trợ các thao tác như chèn xóa và truy xuất trên một cấu trúc cơ bân bên dưới gốm các phân tử có thứ tự tùân tự. Các thao tác này đủ để mô tả các thuật toán và sự trừu tượng hóa xâu tuyến tính có thể là hữu ích trong những chặng đâu cùa sự phát triển thuật toán. Nhưng như chúng ta đã thấy mối quan tâm cùa người lập trình là định nghĩa một cách cẩn thận các thao tác nào sẽ được dùng đối với các cài đạt khác nhau có thể có các đặc trưng vè hiệu nàng hoàn toàn khác nhau. Ví dụ việc dùng một xâu liên kết thay cho một mãng đối với sàng Eratosthenes sẽ là tôn kém vì tính hiẾu quả của thuật toán phụ thuộc vào khả năng đi từ bất kỳ một vị trì nào của mảng tói bất kỳ một vị trí khác của màng một cách nhanh chóng và việc dùng một màng thay vì một xâu liên kết cho bài toán