tài liệu giáo khoa chuyên tin (quyển 2)

tài liệu giáo khoa chuyên tin (quyển 2) trình bày kiểu dữ liệu trừu tượng và cấu trúc dữ liệu; đồ thị chuyên đề nhà xuất bản giáo dục việt nam phát hành,... mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
tài liệu giáo khoa chuyên tin (quyển 2) Hå sÜ ®µm (Chñ biªn) ®ç ®øc ®«ng – lª minh hoµng – nguyÔn thanh hïng tµi liÖu gi¸o khoa chuyªn tin quyÓn 2 Nhµ xuÊt b¶n gi¸o dôc viÖt nam C«ng ty Cæ phÇn dÞch vô xuÊt b¶n Gi¸o dôc Hµ Néi - Nhµ xuÊt b¶n Gi¸o dôc ViÖt Nam gi÷ quyÒn c«ng bè t¸c phÈm. 349-2009/CXB/43-644/GD 2 M4 sè : 8I746H9 LỜI NÓI ðẦU Bộ Giáo dục và ðào tạo ñã ban hành chương trình chuyên tin học cho các lớp chuyên 10, 11, 12. Dựa theo các chuyên ñề chuyên sâu trong chương trình nói trên, các tác giả biên soạn bộ sách chuyên tin học, bao gồm các vấn ñề cơ bản nhất về cấu trúc dữ liệu, thuật toán và cài ñặt chương trình. Bộ sách gồm ba quyển, quyển 1, 2 và 3. Cấu trúc mỗi quyển bao gồm: phần lí thuyết, giới thiệu các khái niệm cơ bản, cần thiết trực tiếp, thường dùng nhất; phần áp dụng, trình bày các bài toán thường gặp, cách giải và cài ñặt chương trình; cuối cùng là các bài tập. Các chuyên ñề trong bộ sách ñược lựa chọn mang tính hệ thống từ cơ bản ñến chuyên sâu. Với trải nghiệm nhiều năm tham gia giảng dạy, bồi dưỡng học sinh chuyên tin học của các trường chuyên có truyền thống và uy tín, các tác giả ñã lựa chọn, biên soạn các nội dung cơ bản, thiết yếu nhất mà mình ñã sử dụng ñể dạy học với mong muốn bộ sách phục vụ không chỉ cho giáo viên và học sinh chuyên PTTH mà cả cho giáo viên, học sinh chuyên tin học THCS làm tài liệu tham khảo cho việc dạy và học của mình. Với kinh nghiệm nhiều năm tham gia bồi dưỡng học sinh, sinh viên tham gia các kì thi học sinh giỏi Quốc gia, Quốc tế Hội thi Tin học trẻ Toàn quốc, Olympiad Sinh viên Tin học Toàn quốc, Kì thi lập trình viên Quốc tế khu vực ðông Nam Á, các tác giả ñã lựa chọn giới thiệu các bài tập, lời giải có ñịnh hướng phục vụ cho không chỉ học sinh mà cả sinh viên làm tài liệu tham khảo khi tham gia các kì thi trên. Lần ñầu tập sách ñược biên soạn, thời gian và trình ñộ có hạn chế nên chắc chắn còn nhiều thiếu sót, các tác giả mong nhận ñược ý kiến ñóng góp của bạn ñọc, các ñồng nghiệp, sinh viên và học sinh ñể bộ sách ñược ngày càng hoàn thiện hơn . Các tác giả 3 4 Chuyên ñề 6 KIỂU DỮ LIỆU TRỪU TƯỢNG VÀ CẤU TRÚC DỮ LIỆU Kiểu dữ liệu trừu tượng là một mô hình toán học với những thao tác ñịnh nghĩa trên mô hình ñó. Kiểu dữ liệu trừu tượng có thể không tồn tại trong ngôn ngữ lập trình mà chỉ dùng ñể tổng quát hóa hoặc tóm lược những thao tác sẽ ñược thực hiện trên dữ liệu. Kiểu dữ liệu trừu tượng ñược cài ñặt trên máy tính bằng các cấu trúc dữ liệu: Trong kỹ thuật lập trình cấu trúc (Structural Programming), cấu trúc dữ liệu là các biến cùng với các thủ tục và hàm thao tác trên các biến ñó. Trong kỹ thuật lập trình hướng ñối tượng (ObjectOriented Programming), cấu trúc dữ liệu là kiến trúc thứ bậc của các lớp, các thuộc tính và phương thức tác ñộng lên chính ñối tượng hay một vài thuộc tính của ñối tượng. Trong chương này, chúng ta sẽ khảo sát một vài kiểu dữ liệu trừu tượng cũng như cách cài ñặt chúng bằng các cấu trúc dữ liệu. Những kiểu dữ liệu trừu tượng phức tạp hơn sẽ ñược mô tả chi tiết trong từng thuật toán mỗi khi thấy cần thiết. 1. Danh sách 1.1. Khái niệm danh sách Danh sách là một tập sắp thứ tự các phần tử cùng một kiểu. ðối với danh sách, người ta có một số thao tác: Tìm một phần tử trong danh sách, chèn một phần tử vào danh sách, xóa một phần tử khỏi danh sách, sắp xếp lại các phần tử trong danh sách theo một trật tự nào ñó v.v… Việc cài ñặt một danh sách trong máy tính tức là tìm một cấu trúc dữ liệu cụ thể mà máy tính hiểu ñược ñể lưu các phần tử của danh sách ñồng thời viết các ñoạn chương trình con mô tả các thao tác cần thiết ñối với danh sách. 5