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

Hå sÜ ®µm (Chñ biªn)<br /> ®ç ®øc ®«ng – lª minh hoµng – nguyÔn thanh hïng<br /> <br /> tµi liÖu gi¸o khoa<br /> <br /> chuyªn tin<br /> quyÓn 2<br /> <br /> Nhµ xuÊt b¶n gi¸o dôc viÖt nam<br /> <br /> 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<br /> gi÷ quyÒn c«ng bè t¸c phÈm.<br /> <br /> 349-2009/CXB/43-644/GD<br /> 2<br /> <br /> M4 sè : 8I746H9<br /> <br /> LỜI NÓI ðẦU<br /> Bộ Giáo dục và ðào tạo ñã ban hành chương trình chuyên tin học cho các<br /> lớp chuyên 10, 11, 12. Dựa theo các chuyên ñề chuyên sâu trong chương trình<br /> 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ơ<br /> bản nhất về cấu trúc dữ liệu, thuật toán và cài ñặt chương trình.<br /> 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<br /> 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;<br /> 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<br /> 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<br /> tính hệ thống từ cơ bản ñến chuyên sâu.<br /> 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<br /> 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,<br /> 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<br /> 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<br /> 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<br /> cho việc dạy và học của mình.<br /> Với kinh nghiệm nhiều năm tham gia bồi dưỡng học sinh, sinh viên tham gia<br /> 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,<br /> 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<br /> ðô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<br /> 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<br /> khi tham gia các kì thi trên.<br /> 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<br /> 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<br /> ñọc, các ñồng nghiệp, sinh viên và học sinh ñể bộ sách ñược ngày càng hoàn<br /> thiện hơn .<br /> Các tác giả<br /> <br /> 3<br /> <br /> 4<br /> <br /> Chuyên ñề 6<br /> <br /> KIỂU DỮ LIỆU TRỪU TƯỢNG<br /> VÀ CẤU TRÚC DỮ LIỆU<br /> 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<br /> 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ữ<br /> 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<br /> 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<br /> các cấu trúc dữ liệu: Trong kỹ thuật lập trình cấu trúc (Structural<br /> 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<br /> 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<br /> 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<br /> của ñối tượng.<br /> 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<br /> 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<br /> 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<br /> cần thiết.<br /> <br /> 1. Danh sách<br /> 1.1. Khái niệm danh sách<br /> 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,<br /> 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ử<br /> 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<br /> danh sách theo một trật tự nào ñó v.v…<br /> 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ể<br /> 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<br /> chương trình con mô tả các thao tác cần thiết ñối với danh sách.<br /> <br /> 5<br /> <br />