Giáo trình Ngôn ngữ Lập trình - Nguyễn Văn Linh

Nội dung text: Giáo trình Ngôn ngữ Lập trình - Nguyễn Văn Linh

1. Th.s. NGUYỄN VĂN LINH NGÔN NGỮ LẬP TRÌNH Được biên soạn trong khuôn khổ dự án ASVIET002CNTT ”Tăng cường hiệu quả đào tạo và năng lực tự đào tạo của sinh viên khoa Công nghệ Thông tin - Đại học Cần thơ” ĐẠI HỌC CẦN THƠ - 12/2003
2. Ngôn ngữ lập trình Mục lục CHƯƠNG 0: TỔNG QUAN i 0.1 MỤC ĐÍCH YÊU CẦU i 0.2 ĐỐI TƯỢNG SỬ DỤNG i 0.3 NỘI DUNG CỐT LÕI i 0.4 KIẾN THỨC TIÊN QUYẾT ii 0.5 DANH MỤC TÀI LIỆU THAM KHẢO ii CHƯƠNG 1: MỞ ĐẦU 1 1.1 TỔNG QUAN 1 1.2 KHÁI NIỆM VỀ NGÔN NGỮ LẬP TRÌNH 1 1.3 VAI TRÒ CỦA NGÔN NGỮ LẬP TRÌNH 2 1.4 LỢI ÍCH CỦA VIỆC NGHIÊN CỨU NNLT 3 1.5 CÁC TIÊU CHUẨN ÐÁNH GIÁ MỘT NGÔN NGỮ LẬP TRÌNH TỐT 4 1.6 CÂU HỎI ÔN TẬP 7 CHƯƠNG 2: KIỂU DỮ LIỆU 8 2.1 TỔNG QUAN 8 2.2 ÐỐI TƯỢNG DỮ LIỆU 8 2.3 BIẾN VÀ HẰNG 10 2.4 KIỂU DỮ LIỆU 10 2.5 SỰ KHAI BÁO 13 2.6 KIỂM TRA KIỂU VÀ BIẾN ÐỔI KIỂU 14 2.7 CHUYỂN ÐỔI KIỂU 17 2.8 GÁN VÀ KHỞI TẠO 17 2.9 CÂU HỎI ÔN TẬP 20 CHƯƠNG 3: KIỂU DỮ LIỆU SƠ CẤP 22 3.1 TỔNG QUAN 22 3.2 ÐỊNH NGHĨA KIỂU DỮ LIỆU SƠ CẤP 22 3.3 SỰ ÐẶC TẢ CÁC KIỂU DỮ LIỆU SƠ CẤP 22 3.4 CÀI ÐẶT CÁC KIỂU DỮ LIỆU SƠ CẤP 23 3.5 KIỂU DỮ LIỆU SỐ 24 3.6 KIỂU LIỆT KÊ 27 3.7 KIỂU LOGIC 28 3.8 KIỂU KÝ TỰ 29 3.9 CÂU HỎI ÔN TẬP 29 CHƯƠNG 4: KIỂU DỮ LIỆU CÓ CẤU TRÚC 30 4.1 TỔNG QUAN 30 4.2 ÐỊNH NGHĨA KIỂU DỮ LIỆU CÓ CẤU TRÚC 30 4.3 SỰ ÐẶC TẢ KIỂU CẤU TRÚC DỮ LIỆU 30 4.4 SỰ CÀI ÐẶT CÁC CẤU TRÚC DỮ LIỆU 32 4.5 VÉCTƠ 34 4.6 MẢNG NHIỀU CHIỀU 36 4.7 MẨU TIN 39 4.8 MẨU TIN CÓ CẤU TRÚC THAY ÐỔI 41 4.9 CHUỖI KÝ TỰ: 45 4.10 CẤU TRÚC DỮ LIỆU CÓ KÍCH THƯỚC THAY ÐỔI 47 4.11 CON TRỎ 48 4.12 TẬP HỢP 50 4.13 TẬP TIN 52 4.14 CÂU HỎI ÔN TẬP 54 CHƯƠNG 5: KIỂU DO NGƯỜI DÙNG ÐỊNH NGHĨA 58 5.1 TỔNG QUAN 58 5.2 SỰ PHÁT TRIỂN CỦA KHÁI NIỆM KIỂU DỮ LIỆU 58
3. Ngôn ngữ lập trình Mục lục 5.3 TRỪU TƯỢNG HÓA 58 5.4 ÐỊNH NGHĨA KIỂU 60 5.5 CÂU HỎI ÔN TẬP 62 CHƯƠNG 6: CHƯƠNG TRÌNH CON 63 6.1 TỔNG QUAN 63 6.2 ÐỊNH NGHĨA CHƯƠNG TRÌNH CON 63 6.3 CƠ CHẾ GỌI CHƯƠNG TRÌNH CON 65 6.4 CHƯƠNG TRÌNH CON CHUNG 68 6.5 TRUYỀN THAM SỐ CHO CHƯƠNG TRÌNH CON 68 6.6 CÂU HỎI ÔN TẬP 70 CHƯƠNG 7: ÐIỀU KHIỂN TUẦN TỰ 71 7.1 TỔNG QUAN 71 7.2 KHÁI NIỆM ÐIỀU KHIỂN TUẦN TỰ 71 7.3 ÐIỀU KHIỂN TUẦN TỰ TRONG BIỂU THỨC 71 7.4 ÐIỀU KHIỂN TUẦN TỰ GIỮA CÁC LỆNH 75 7.5 SỰ NGOẠI LỆ VÀ XỬ LÝ NGOẠI LỆ 78 7.6 CÂU HỎI ÔN TẬP 80 CHƯƠNG 8: LẬP TRÌNH HÀM 81 8.1 TỔNG QUAN 81 8.2 NGÔN NGỮ LẬP TRÌNH HÀM 81 8.3 NGÔN NGỮ LISP 83 CHƯƠNG 9: LẬP TRÌNH LOGIC 95 9.1 TỔNG QUAN 95 9.2 GIỚI THIỆU VỀ LẬP TRÌNH LOGIC 95 9.3 NGÔN NGỮ PROLOG 96
4. Ngôn ngữ lập trình Tổng quan TỔNG QUAN MỤC ĐÍCH YÊU CẦU Mục đích của môn học Ngôn ngữ lập trình là cung cấp cho sinh viên một khối lượng kiến thức tương đối hoàn chỉnh về nguyên lí của ngôn ngữ lập trình. Cùng với môn học Tin học lí thuyết, Ngôn ngữ lập trình sẽ là môn học tiên quyết để học môn Trình biên dịch. Sau khi học xong môn học này, sinh viên cần: - Nắm được các khái niệm về đối tượng dữ liệu và kiểu dữ liệu. Các khía cạnh cần nghiên cứu khi đặc tả và cài đặt một kiểu dữ liệu. Vấn đề kiểm tra kiểu và chuyển đổi kiểu cũng cần được quan tâm. - Nắm được các kiểu dữ liệu sơ cấp và có cấu trúc. Với mỗi kiểu dữ liệu cần nắm định nghĩa, đặc tả và cách cài đặt kiểu dữ liệu. - Nắm được khái niệm trừu tượng hoá trong lập trình thể hiện trên hai khía cạnh là trừu tượng hoá dữ liệu bằng cách sử dụng các kiểu dữ liệu tự định nghĩa và trừu tượng hoá chương trình bằng cách chia chương trình thành các chương trình con. Vấn đề truyền tham số cho chương trình con cũng cần được lưu tâm. - Nắm được khái niệm điều khiển tuần tự, nguyên tắc điều khiển tuần tự trong biểu thức và giữa các câu lệnh. ĐỐI TƯỢNG SỬ DỤNG Môn học ngôn ngữ lập trình được dùng để giảng dạy cho các sinh viên năm thứ 4 chuyên ngành Tin học. NỘI DUNG CỐT LÕI Trong khuôn khổ 45 tiết, giáo trình được cấu trúc thành 9 chương Chương 1: Mở đầu. Chương này trình bày khái niệm về ngôn ngữ lập trình, lợi ích của việc nghiên cứu ngôn ngữ lập trình và các tiêu chuẩn để đánh giá một ngôn ngữ lập trình tốt. Chương 2: Kiểu dữ liệu. Chương này trình bày các khái niệm về đối tượng dữ liệu và kiểu dữ liệu; các phương pháp kiểm tra kiểu và chuyển đổi kiểu; Phép gán trị cho biến và sự khởi tạo biến. Chương 3: Kiểu dữ liệu sơ cấp. Chương này trình bày khái niệm về kiểu dữ liệu sơ cấp, sự đặc tả và nguyên tắc cài đặt một kiểu dữ liệu sơ cấp nói chung. Phần chủ yếu của chương trình bày một số kiểu dữ liệu sơ cấp phổ biến như các kiểu số, kiểu miền con, kiểu liệt kê, kiểu kí tự và kiểu logic. Chương 4: Kiểu dữ liệu có cấu trúc. Chương này trình bày khái niệm về kiểu dữ liệu có cấu trúc, sự đặc tả các thuộc tính, đặc tả phép toán, đặc biệt là phép toán lựa chọn một phần tử; các phương pháp lưu trữ một cấu trúc dữ liệu trong bộ nhớ và phương pháp lựa chọn phần tử. Nội dung chủ yếu của chương trình bày các cấu trúc cụ thể như mảng, mẩu tin, chuỗi ký tự, tập hợp Chương 5: Kiểu dữ liệu tự định nghĩa. Chương này trình bày về sự trừu tượng hoá, định nghĩa kiểu dữ liệu và sự tương đương của các kiểu dữ liệu được định nghã. i
5. Ngôn ngữ lập trình Tổng quan Chương 6: Chương trình con. Chương này trìn bày về sự định nghĩa và cơ chế gọi thực hiện chương trình con, các phương pháp truyền tham số cho chương trình con. Chương 7: Điều khiển tuần tự. Chương này trình bày các loại điều khiển tuần tự và vấn đề xử lý ngoại lệ. Chương 8: Lập trình hàm. Chương này trình bày khái niệm, bản chất của lập trình hàm và giới thiệu một ngôn ngữ lập trình hàm điển hình là LISP. Chương 9: Lập trình logic. Chương này trình bày khái niệm, bản chất của lập trình logic và giới thiệu một ngôn ngữ lập trình hàm điển hình là PROLOG. KIẾN THỨC TIÊN QUYẾT Để học tốt môn học ngôn ngữ lập trình cần phải có các kiến thức và kĩ năng lập trình căn bản. DANH MỤC TÀI LIỆU THAM KHẢO [1] Terrence W. Pratt, Marvin V. Zelkowitz; Programming Languages: Design and Implementation; Prentice-Hall, 2000. [2] Doris Appleby, Julius J. VandeKopple; Programming Languages; McGraw- Hill; 1997. [3] Ryan Stensifer; The Study of Programming Languages; Prentice Hall, 1995. [4] Maryse CONDILLAC; Prolog fondements et applications; BORDAS, Paris 1986. [5] Website về XLISP [6] Website về Turbo Prolog ii
6. Ngôn ngữ lập trình Chương I: Mở đầu CHƯƠNG 1: MỞ ĐẦU 1.1 TỔNG QUAN 1.1.1 Mục tiêu Sau khi học xong chương này, sinh viên cần phải nắm: - Khái niệm và phân loại các ngôn ngữ lập trình. - Vai trò của ngôn ngữ lập trình trong công nghệ phần mềm. - Lợi ích của việc nghiên cứu ngôn ngữ lập trình. - Các tiêu chuẩn để đánh giá ngôn ngữ lập trình. 1.1.2 Nội dung cốt lõi - Khái niệm về ngôn ngữ lập trình. - Vai trò của ngôn ngữ lập trình. - Lợi ích của việc nghiên cứu ngôn ngữ lập trình. - Các tiêu chuẩn để đánh giá một ngôn ngữ lập trình tốt. 1.1.3 Kiến thức cơ bản cần thiết Kiến thức và kĩ năng lập trình căn bản 1.2 KHÁI NIỆM VỀ NGÔN NGỮ LẬP TRÌNH Như chúng ta đã biết, máy tính bao gồm phần cứng là các thiết bị điện tử trong đó thông tin được biểu diễn dưới dạng số nhị phân và phần mềm bao gồm các chương trình được tạo ra bằng cách sử dụng các ngôn ngữ lập trình. Như vậy ngôn ngữ lập trình (NNLT) là ngôn ngữ dùng để viết các chương trình cho máy tính. Cũng như các ngôn ngữ thông thường, NNLT cũng có từ vựng, cú pháp và ngữ nghĩa. Theo tiến trình lịch sử phát triển, ngôn ngữ lập trình có thể được chia ra làm ba loại chủ yếu như sau: Ngôn ngữ máy (machine language): Là các chỉ thị dưới dạng nhị phân, can thiệp trực tiếp vào trong các mạch điện tử. Chương trình được viết bằng ngôn ngữ máy thì có thể được thực hiện ngay không cần qua bước trung gian nào. Tuy nhiên chương trình viết bằng ngôn ngữ máy dễ sai sót, cồng kềnh và khó đọc, khó hiểu vì toàn những con số 0 và 1. Hợp ngữ (assembly language): Hợp ngữ là một bước tiến vượt bậc đưa ngôn ngữ lập trình thoát ra khỏi ngôn ngữ máy khó hiểu. Ngôn ngữ này xuất hiện vào những năm 1950, nó được thiết kế để máy tính trở nên thân thiện hơn với người sử dụng. Hợp ngữ đưa ra khái niệm biến (variable), nhờ đó mà ta có thể gán một ký hiệu cho một vị trí nào đó trong bộ nhớ mà không phải viết lại địa chỉ này dưới dạng nhị phân mỗi lần sử dụng. Hợp ngữ cũng chứa vài "phép toán giả", tức là ta có thể biểu biễn mã phép toán dưới dạng phát biểu (hay còn gọi là câu lệnh) thay vì dưới dạng nhị phân. Các câu lệnh bao gồm hai phần: phần mã lệnh 1
7. Ngôn ngữ lập trình Chương I: Mở đầu (viết tựa tiếng Anh) chỉ phép toán cần thực hiện và phần tên biến chỉ địa chỉ chứa toán hạng của phép toán đó. Ðể máy thực hiện được một chương trình viết bằng hợp ngữ thì chương trình đó phải được dịch sang ngôn ngữ máy. Công cụ thực hiện việc dịch đó được gọi là Assembler. Ngôn ngữ cấp cao (High level language): Là ngôn ngữ được tạo ra và phát triển nhằm phản ánh cách thức người lập trình nghĩ và làm. Ngôn ngữ cấp cao rất gần với ngôn ngữ con người (Anh ngữ) nhưng chính xác như ngôn ngữ toán học. Nhờ ngôn ngữ cấp cao mà lĩnh vực lập trình trở nên phổ biến, rất nhiều người có thể viết được chương trình, và nhờ thế mà các phần mềm phát triển như vũ bão, phục vụ nhiều lĩnh vực của cuộc sống. Cùng với sự phát triển của các thế hệ máy tính, ngôn ngữ lập trình cấp cao cũng được phát triển rất đa dạng và phong phú, việc lập trình cho máy tính vì thế mà cũng có nhiều khuynh hướng khác nhau: lập trình cấu trúc, lập trình hướng đối tượng, lập trình logic, lập trình hàm Một chương trình viết bằng ngôn ngữ cấp cao được gọi là chương trình nguồn (source programs). Ðể máy tính "hiểu" và thực hiện được các lệnh trong chương trình nguồn thì phải có một chương trình dịch để dịch chương trình nguồn (viết bằng ngôn ngữ cấp cao) thành chương trình đích. Trong khuôn khổ tài liệu này, thuật ngữ ngôn ngữ lập trình dùng để chỉ ngôn ngữ lập trình cấp cao. 1.3 VAI TRÒ CỦA NGÔN NGỮ LẬP TRÌNH Ðể thấy rõ vai trò của ngôn ngữ lập trình trong công nghệ phần mềm chúng ta hãy xét các giai đoạn chủ yếu để xây dựng một phần mềm. Các giai đoạn đó bao gồm: - Xác định: Mục tiêu của giai đọan xác định là để hiểu rõ các yêu cầu của khách hàng. Kết quả của giai đọan này là mô hình thế giới thực được phản ánh thông qua một tài liệu đặc tả yêu cầu. - Phân tích: Mục tiêu của giai đoạn này là xác định chính xác hệ thống sẽ làm những gì theo quan điểm của người sử dụng. Kết quả của giai đoạn phân tích là một tài liệu đặc tả chức năng mô tả hệ thống sẽ có những chức năng gì. - Thiết kế: Mục tiêu của giai đọan thiết kế là xác định chính xác hệ thống sẽ làm việc như thế nào. Kết quả của giai đọan này là một tài liệu đặc tả thiết kế. Ðây là một tài liệu kỹ thuật mà những người thực hiện sẽ căn cứ vào đó mà tạo ra phần mềm. - Cài đặt: Là việc thực hiện cách giải quyết vấn đề đã được đề xuất bởi người thiết kế bằng một NNLT. Kết quả của giai đọan này là một hệ chương trình máy tính. - Tích hợp và kiểm thử hệ thống: Do các chuyên viên tin học thực hiện nhằm ghép nối các bộ phận của hệ thống và kiểm tra xem hệ thống có được thực hiện đúng theo thiết kế không. - Chấp nhận: Do các chuyên viên tin học cùng với khách hàng tiến hành nhằm xác nhận hệ thống chương trình bảo đảm các yêu cầu của người sử dụng. - Vận hành khai thác: Hệ thống được triển khai để sử dụng. 2
8. Ngôn ngữ lập trình Chương I: Mở đầu Ở trên chỉ trình bày một mô hình làm phần mềm, gọi là mô hình thác nước (water fall), ngoài ra còn có nhiều mô hình khác. Tuy nhiên trong tất cả các mô hình ấy đều phải có giai đoạn cài đặt. Trong đó NNLT đóng vai trò là một công cụ giúp con người thực hiện bước cài đặt này. Công cụ đó ngày càng được cải tiến hoàn thiện và có thể nói mọi tiến bộ trong tin học đều thể hiện ra trong NNLT. NNLT vừa là công cụ giúp các nhà tin học giải quyết các vấn đề thực tế nhưng đồng thời cũng là nơi mà những nghiên cứu mới nhất của tin học được đưa vào. Lĩnh vực này vừa mang tính truyền thống vừa mang tính hiện đại. 1.4 LỢI ÍCH CỦA VIỆC NGHIÊN CỨU NNLT Trước khi nghiên cứu về NNLT, chúng ta cần thảo luận xem vì sao các sinh viên tin học và các nhà lập trình chuyên nghiệp cần phải nắm các khái niệm tổng quát về NNLT. Việc nghiên cứu tốt NNLT sẽ đạt được các lợi ích như sau: 1.4.1 Cho phép lựa chọn một NNLT phù hợp với dự án thực tế Hiện nay có rất nhiều dự án công nghệ thông tin ứng dụng vào nhiều lĩnh vực khác nhau của cuộc sống. Do tính chất của từng dự án mà phần mềm có thể được cài đặt bằng các NNLT khác nhau. Với một vốn kiến thức rộng về NNLT, những người làm dự án có thể lựa chọn nhanh chóng một NNLT phù hợp với đề án thực tế. Chẳng hạn có thể lựa chọn ngôn ngữ lập trình Java cho các dự án lập trình truyền thông, hay hướng lập trình logic cho các dự án về trí tuệ nhân tạo. 1.4.2 Sử dụng một cách có hiệu quả các công cụ của ngôn ngữ Các ngôn ngữ nói chung đều cung cấp những công cụ đặc biệt để tạo ra các tiện ích cho lập trình viên, nhưng khi sử dụng chúng không đúng đắn có thể sẽ gây ra những sai lầm lớn. Một ví dụ điển hình là phép đệ quy (recursion) - một công cụ lập trình đặc biệt có hiệu lực trong nhiều ngôn ngữ. Khi sử dụng đệ quy một cách đúng đắn thì có thể cài đặt một giải thuật đẹp đẽ và có hiệu quả. Nhưng trong trường hợp khác nó có thể gây ra một sự lãng phí thời gian chạy máy rất lớn cho một giải thuật đơn giản. Ðiều này có thể tránh được nếu như lập trình viên có một sự hiểu biết sâu sắc về ngôn ngữ lập trình và các cài đặt bên trong nó. 1.4.3 Làm tăng vốn kinh nghiệm khi xây dựng các chương trình Nếu người lập trình đã có sự nghiên cứu một cách rộng rãi nhiều ngôn ngữ mà một trong chúng có cài đặt sẵn những công cụ nào đó thì anh ta có thể tự thiết lập những công cụ tương tự khi phải viết chương trình bởi một ngôn ngữ mà trong đó các công cụ như thế chưa được cài đặt. 1.4.4 Tạo sự dễ dàng để học một ngôn ngữ mới Mặc dù có nhiều NNLT khác nhau nhưng chúng đều có những nguyên tắc chung của NNLT. Rất nhiều ngôn ngữ có chung cú pháp (sai khác nhau chút ít về cách viết), có chung các kiểu dữ liệu (sai khác nhau chút ít về tên gọi). Việc nắm vững các nguyên lý cơ bản của NNLT sẽ là một điều kiện thuận lợi lớn để tiếp cận một cách nhanh chóng với một ngôn ngữ lập trình cụ thể mới. Thực tế cho thấy rằng với những người nắm vững NNLT, khi gặp một ngôn ngữ lập trình cụ thể mới, họ có thể vừa nghiên cứu ngôn ngữ mới này vừa áp dụng để lập trình giải quyết một bài toán theo yêu cầu. 3
9. Ngôn ngữ lập trình Chương I: Mở đầu 1.4.5 Tạo tiền đề để thiết kế một ngôn ngữ mới Việc thiết kế ngôn ngữ mới là một đòi hỏi của khoa học phát triển NNLT. Nếu chúng ta không nghiên cứu về NNLT thì không thể nào có kiến thức để xây dựng một ngôn ngữ mới. 1.5 CÁC TIÊU CHUẨN ÐÁNH GIÁ MỘT NGÔN NGỮ LẬP TRÌNH TỐT Những yếu tố sau tạo nên một ngôn ngữ tốt, nó cũng là những tiêu chuẩn để người lập trình đánh giá ngôn ngữ này tốt hơn ngôn ngữ kia khi lựa chọn một ngôn ngữ để sử dụng. Ngoài ra khi thiết kế một ngôn ngữ lập trình mới, ta cũng phải quan tâm đến các tiêu chuẩn này để có được một ngôn ngữ tốt. 1.5.1 Tính dễ đọc Tính dễ đọc của một NNLT là sự dễ dàng đọc hiểu một chương trình được viết bằng ngôn ngữ đó. Tính dễ đọc được đặc trưng bởi các thuộc tính sau: 1.- Sự giản dị. Một ngôn ngữ được gọi là có tính giản dị nếu ngôn ngữ đó có ít các thành phần cơ sở, tức là ít các yếu tố được định nghĩa trước. Các ngôn ngữ mà chúng ta có thể đạt được một phép toán bằng nhiều cách khác nhau thì không phải là một ngôn ngữ giản dị. Chẳng hạn trong ngôn ngữ C để tăng thêm một đơn vị cho biến count ta có thể sử dụng nhiều cách như count = count + 1, count += 1, count++ hoặc ++count. Các phép toán chồng (overload) cũng làm cho ngôn ngữ trở nên phức tạp. Chẳng hạn toán tử + có thể hiểu là cộng hai số nguyên, cộng hai số thực, hợp hai tập hợp hay ghép nối hai chuỗi ký tự 2.- Cấu trúc điều khiển. Các lệnh có cấu trúc cho phép viết các chương trình sáng sủa, dễ đọc, dễ hiểu. Chúng ta có thể nhận thấy điều này trong các ngôn ngữ thuộc thập niên 1960 như BASIC, FORTRAN trong đó do thiếu các cấu trúc điều khiển nên chương trình phải sử dụng nhiều lệnh GOTO, rất khó theo dõi để hiểu chương trình. Ta hãy so sánh hai đoạn chương trình in ra màn hình 10 số tự nhiên đầu tiên được viết bằng ngôn ngữ BASIC (không có lệnh cấu trúc FOR) và ngôn ngữ Pascal. Viết bằng BASIC Viết bằng Pascal 10 i=1; 20 IF i>10 THEN GOTO 60; FOR i:=1 TO 10 DO 30 PRINT i ; Writeln(i); 40 i=i+1; Writeln(‘In xong’); 50 GOTO 20; 60 PRINT “In xong”; 3.- Kiểu dữ liệu và cấu trúc dữ liệu. Xem xét kiểu dữ liệu và cấu trúc dữ liệu của một ngôn ngữ cũng góp phần đánh giá một ngôn ngữ có dễ đọc hay không. Chẳng hạn trong các ngôn ngữ không có kiểu dữ liệu logic thì phải sử dụng kiểu số để thay thế và do đó mà chương trình trở nên khó đọc. Ví dụ ta hay sử dụng biến found trong các chương trình tìm kiếm một phần tử x trong một mảng a gồm n phần tử. Nếu ngôn ngữ sử dụng có kiểu logic thì ta có thể gán cho found giá trị TRUE hoặc FALSE để biểu diễn trạng thái tìm thấy phần tử cần tìm hay không, ngược lại đối với các ngôn ngữ không có kiểu logic thì ta phải dùng kiểu số và gán cho found giá trị 1 hoặc 0. Ta hãy so sánh hai đoạn chương trình sau để xem đoạn chương trình nào dễ hiểu hơn. 4
10. Ngôn ngữ lập trình Chương I: Mở đầu found := 0; found := FALSE; i := 1; i := 1; While (i<=n)and (found=0) do While(i<=n)and(NOT found) do IF a[i]=x THEN found := 1 IF a[i]=x THEN found:= TRUE ELSE i := i+1; ELSE i:=i+1; 4.- Cú pháp. Cú pháp của ngôn ngữ có ảnh hưởng lớn đến sự dễ đọc hiểu của chương trình. Chúng ta xét một số thí dụ sau để thấy rõ vấn đề này. • Một số ngôn ngữ quy định độ dài tối đa của danh biểu quá ngắn, chẳng hạn trong FORTRAN 77 độ dài tối đa của danh biểu là 6, do đó tên biến nhiều khi phải viết tắt nên khó đọc hiểu. • Việc sử dụng từ khóa cũng góp phần làm cho ngôn ngữ trở nên dễ đọc. Chẳng hạn trong ngôn ngữ Pascal chỉ sử dụng một từ khóa end để kết thúc một khối, kết thúc một lệnh case hay kết thúc một lệnh hợp thành do đó chương trình trở nên khó đọc, trong khi Ada dùng các từ khóa end if để kết thúc lệnh if, end loop để kết thúc lệnh vòng lặp thì chương trình dễ đọc hơn. 1.5.2 Tính dễ viết Tính dễ viết của một ngôn ngữ là khả năng sử dụng ngôn ngữ đó để viết một chương trình cho một vấn đề nào đó một cách dễ dàng hay không. Thông thường các ngôn ngữ dễ đọc thì đều dễ viết. Tính dễ viết phải được xem xét trong ngữ cảnh của vấn đề mà ngôn ngữ được sử dụng để giải quyết. Theo đó không thế so sánh tính dễ viết của hai ngôn ngữ cho cùng một bài toán mà một trong hai được thiết kế để dành riêng giải quyết bài toán đó. Ví dụ để giải quyết bài toán quản trị dữ liệu, chúng ta không thể so sánh Pascal với một hệ quản trị cơ sở dữ liệu như Foxpro, Access hay Oracle. Sau đây là một số yếu tố quan trọng nhất ảnh hưởng tới tính dễ viết của ngôn ngữ. 1.- Sự giản dị. Nếu một ngôn ngữ có quá nhiều cấu trúc thì một số người lập trình sẽ không quen sử dụng hết tất cả chúng. Tốt nhất là có một số nhỏ các cấu trúc ban đầu và một quy tắc để kết hợp chúng thành các cấu trúc phức tạp hơn. 2.- Hỗ trợ cho trừu tượng. Một cách ngắn gọn, trừu tượng (abstraction) là khả năng để định nghĩa và sử dụng các cấu trúc hoặc các phép toán phức tạp theo cách thức mà nó cho phép bỏ qua các chi tiết. Một ví dụ về trừu tượng là chương trình con, từ chương trình gọi, chúng ta gọi chương trình con để thực hiện một tác vụ nào đó mà không cần biết các cài đặt chi tiết bên trong chương trình con đó. Thực chất trừu tượng hóa chính là làm cho chương trình sáng sủa hơn. 3.- Khả năng diễn đạt. Là những công cụ của ngôn ngữ mà người lập trình có thể sử dụng để diễn đạt giải thuật một cách dễ dàng. Nói cách khác, một ngôn ngữ có khả năng diễn đạt là ngôn ngữ cung cấp cho người lập trình những công cụ sao cho người lập trình có thể nghĩ sao thì viết chương trình như vậy. Chẳng hạn lệnh lặp FOR trong Pascal dễ sử dụng cho cấu trúc lặp với số lần lặp xác định hơn là lệnh WHILE. 5
11. Ngôn ngữ lập trình Chương I: Mở đầu 1.5.3 Ðộ tin cậy Ðộ tin cậy của một ngôn ngữ lập trình là khả năng của ngôn ngữ hỗ trợ người lập trình tạo ra các chương trình đúng đắn. Độ tin cậy được thể hiện bởi các đặc trưng sau: 1.- Kiểm tra kiểu. Là kiểm tra lỗi về kiểu của chương trình trong giai đoạn dịch hoặc trong khi thực hiện. Kiểm tra kiểu là một yếu tố quan trọng đảm bảo độ tin cậy của ngôn ngữ. Kiểm tra kiểu sẽ báo cho người lập trình biết các lỗi về kiểu và yêu cầu họ có các sửa chữa cần thiết để có một chương trình đúng. 2.- Xử lý ngoại lệ (Exception Handing). Là một công cụ cho phép chương trình phát hiện các lỗi trong thời gian thực hiện, tạo khả năng để sửa chữa chúng và sau đó tiếp tục thực hiện mà không phải dừng chương trình. 3.- Sự lắm tên (Aliasing): Khi có hai hay nhiều tên cùng liên kết tới một ô nhớ ta gọi là sự lắm tên. Chẳng hạn các biến con trỏ trong ngôn ngữ Pascal cùng trỏ đến một ô nhớ. Sự lắm tên có thể làm giảm độ tin cậy do người lập trình không kiểm soát được giá trị được lưu trữ trong ô nhớ. Hãy xét ví dụ sau trong Pascal Var p, q: ^integer; Begin New(p); p^ := 50; q:= p; {Cả q và p cùng trỏ đến một ô nhớ} writeln(p^, ‘ và ‘, q^); q^ := 20; writeln(p^, ‘ và ‘, q^); end; Kết quả thực hiện đoạn chương trình này là in ra hai dòng: 50 và 50 20 và 20 Trong khi nhiều người lầm tưởng hai dòng sẽ in ra là: 50 và 50 50 và 20 1.5.4 Chi phí Chi phí của một ngôn ngữ cũng thường được quan tâm như là một tiêu chuẩn để đánh giá ngôn ngữ. Chi phí ở đây phải được hiểu là cả tiền bạc và thời gian. Chi phí này bao gồm: - Chi phí đào tạo lập trình viên sử dụng ngôn ngữ. Chi phí này phụ thuộc vào sự giản dị của ngôn ngữ. - Chi phí cài đặt chương trình. Chi phí này phụ thuộc vào tính dễ viết của ngôn ngữ. - Chi phí dịch chương trình. - Chi phí thực hiện chương trình. - Chi phí bảo trì chương trình. 6
12. Ngôn ngữ lập trình Chương I: Mở đầu - Chi phí mua trình biên dịch 1.6 CÂU HỎI ÔN TẬP 1. Vai trò của ngôn ngữ lập trình trong công nghệ phần mềm là gì? 2. Nêu các lợi ích của việc nghiên cứu ngôn ngữ lập trình. 3. Nêu tên các tiêu chuẩn để đánh giá một ngôn ngữ lập trình tốt. 4. Nêu tên các yếu tố ảnh hưởng đến tính dễ đọc. 5. Nêu tên các yếu tố ảnh hưởng đến tính dễ viết. 6. Nêu tên các yếu tố ảnh hưởng đến độ tin cậy. 7. Thế nào là sự lắm tên? 8. Chi phí của ngôn ngữ lập trình bao gồm những chi phí nào? 7
13. Ngôn ngữ lập trình Chương II: Kiểu dữ liệu CHƯƠNG 2: KIỂU DỮ LIỆU 2.1 TỔNG QUAN 2.1.1 Mục tiêu Sau khi học xong chương này, sinh viên cần phải nắm: - Khái niệm về đối tượng dữ liệu, biến, hằng. - Khái niệm về kiểu dữ liệu. - Các phương pháp kiểm tra kiểu và biến đổi kiểu. 2.1.2 Nội dung cốt lõi - Các khái niệm về đối tượng dữ liệu, kiểu dữ liệu. - Sự khai báo các đối tượng dữ liệu trong chương trình. - Kiểm tra kiểu, biến đổi kiểu dữ liệu. - Vấn đề gán giá trị và khởi tạo biến. 2.1.3 Kiến thức cơ bản cần thiết Kiến thức và kĩ năng lập trình căn bản 2.2 ÐỐI TƯỢNG DỮ LIỆU 2.2.1 Khái niệm đối tượng dữ liệu Trong máy tính thực dữ liệu được lưu trữ ở bộ nhớ trong và bộ nhớ ngoài. Trong đó dữ liệu được tổ chức thành các bit, các byte hoặc word. Tuy nhiên trong máy tính ảo của một NNLT nào đó, dữ liệu có tổ chức phức tạp hơn với các mảng, ngăn xếp, số, chuỗi ký tự Người ta sử dụng thuật ngữ đối tượng dữ liệu (ÐTDL) để chỉ một nhóm của một hoặc nhiều mẩu dữ liệu trong máy tính ảo. Khác với tính chất tĩnh tương đối của các vùng nhớ trong máy tính thực, các ÐTDL và các mối liên hệ nội tại của chúng lại thay đổi một cách động trong quá trình thực hiện chương trình. 2.2.2 Các loại ÐTDL Xét về mặt cấu trúc thì người ta phân ÐTDL làm hai loại là ÐTDL sơ cấp và ÐTDL có cấu trúc hay cấu trúc dữ liệu. ÐTDL sơ cấp là một ÐTDL chỉ chứa một giá trị dữ liệu đơn. Hẳng hạn như một số, một kí tự, ĐTDL có cấu trúc hay cấu trúc dữ liệu là một tích hợp của các ÐTDL khác. Mỗi ĐTDL thành phần của ĐTDL có cấu trúc được gọi là một phần tử. Mỗi phần tử của cấu trúc dữ liệu có thể là một ÐTDL sơ cấp hay cũng có thể là một ÐTDL có cấu trúc khác. Ví dụ một chuỗi kí tự, một tập hợp các số, một véctơ, một ma trận, đều là các ĐTDL có cấu trúc. 8
14. Ngôn ngữ lập trình Chương II: Kiểu dữ liệu Xét về mặt nguồn gốc thì có thể phân ÐTDL làm hai loại: ÐTDL tường minh và ÐTDL ẩn. ÐTDL tường minh là một ÐTDL do người lập trình tạo ra chẳng hạn như các biến, các hằng, được người lập trình viết ra trong chương trình. ÐTDL ẩn là một ĐTDL được định nghĩa bởi hệ thống như các ngăn xếp lưu trữ các giá trị trung gian, các mẩu tin kích hoạt chương trình con, các ô nhớ đệm của tập tin Các ÐTDL này được phát sinh một cách tự động khi cần thiết trong quá trình thực hiện chương trình và người lập trình không thể truy cập đến chúng được. 2.2.3 Thuộc tính của ÐTDL Thuộc tính của một ĐTDL là một tính chất đặc trưng của ĐTDL đó. Mỗi ÐTDL có một tập hợp các thuộc tính để phân biệt ĐTDL này với ĐTDL khác. Các ĐTDL sơ cấp chỉ có một thuộc tính duy nhất là kiểu dữ liệu của đối tượng đó. Các ĐTDL có cấu trúc có thêm các thuộc tính nhằm xác định số lượng, kiểu dữ liệu của các phần tử và các thuộc tính khác. 2.2.4 Giá trị dữ liệu Giá trị dữ liệu (GTDL) của một ĐTDL sơ cấp có thể là một số, một ký tự hoặc là một giá trị logic tùy thuộc vào kiểu của ĐTDL đó. Mỗi GTDL thường được biểu diễn bởi một dãy các bit trong bộ nhớ của máy tính. Cần phân biệt hai khái niệm ÐTDL và GTDL. Một ÐTDL luôn luôn được biểu diễn bởi một khối ô nhớ trong bộ nhớ của máy tính trong khi một GTDL được biểu diễn bởi một dãy các bit. Khi nói rằng một ÐTDL A chứa một GTDL B có nghĩa là: khối ô nhớ biểu diễn cho A chứa dãy bit biểu diễn cho B. GTDL của một ĐTDL có cấu trúc là một tập hợp các GTDL của các phần tử của ĐTDL có cấu trúc đó. 2.2.5 Thời gian tồn tại Thời gian tồn tại (lifetime) của một ÐTDL là khoảng thời gian ĐTDL chiếm giữ bộ nhớ của máy tính. Thời gian này được tính từ khi ÐTDL được tạo ra cho đến khi nó bị hủy bỏ trong quá trình thực hiện chương trình. 2.2.6 Các mối liên kết Một ÐTDL có thể tham gia vào nhiều mối liên kết trong thời gian tồn tại của nó. Các liên kết quan trọng nhất là: • Sự liên kết của ÐTDL với một hoặc nhiều giá trị. Sự liên kết này có thể bị thay đổi bởi phép gán trị. • Sự liên kết của một ÐTDL với một hoặc nhiều tên được tham chiếu trong quá trình thực hiện chương trình. Các liên kết này được thiết lập bởi sự khai báo và thay đổi bởi việc gọi và trả chương trình con. 9
15. Ngôn ngữ lập trình Chương II: Kiểu dữ liệu • Sự liên kết của một ÐTDL với một số ÐTDL khác gọi là các hợp thành (component). Các liên kết này thường được biểu diễn bởi giá trị con trỏ và nó có thể bị thay đổi bởi việc thay đổi con trỏ. • Sự liên kết của một ÐTDL với ô nhớ trong bộ nhớ. Sự liên kết này thường không thể thay đổi một cách trực tiếp bởi người lập trình mà nó được thiết lập và có thể bị thay đổi bởi các thường trình (routine) quản lý bộ nhớ của máy tính ảo. 2.3 BIẾN VÀ HẰNG 2.3.1 Biến Biến là một ÐTDL được người lập trình định nghĩa và đặt tên một cách tường minh trong chương trình. Giá trị của biến có thể bị thay đổi trong thời gian tồn tại của nó. Tên biến được dùng để xác định và tham khảo tới biến. Trong các NNLT, tên biến thường được quy định dưới dạng một dãy các chữ cái, dấu gạch dưới và các chữ số, bắt đầu bằng một chữ cái và có chiều dài hữu hạn. 2.3.2 Hằng Hằng là một ÐTDL có tên và giá trị của hằng không thay đổi trong thời gian tồn tại của nó. Hằng trực kiện (literal constant) là một hằng mà tên của nó là sự mô tả giá trị của nó (chẳng hạn "27" là sự mô tả số thập phân của ÐTDL giá trị 27). Chú ý sự khác biệt giữa 2 giá trị 27. Một cái là một số nguyên được biểu diễn thành một dãy các bit trong bộ nhớ trong quá trình thực hiện chương trình và cái tên "27" là một chuỗi 2 ký tự "2" và "7" mô tả một số nguyên như nó được viết trong chương trình. 2.4 KIỂU DỮ LIỆU 2.4.1 Ðịnh nghĩa kiểu dữ liệu Kiểu dữ liệu là một tập hợp các ÐTDL và tập hợp các phép toán thao tác trên các ÐTDL đó. Mọi NNLT đều xây dựng cho mình một tập các kiểu dữ liệu nguyên thuỷ. Chẳng hạn ngôn ngữ LISP, kiểu dữ liệu chính là các cây nhị phân với các phép toán CAR, CDR và CONS còn đối với các ngôn ngữ cấp cao khác thì các kiểu dữ liệu nguyên thủy thường là: integer, real, character và boolean. Hơn nữa các ngôn ngữ còn cung cấp phương tiện cho phép người lập trình định nghĩa các kiểu dữ liệu mới. Kiểu dữ liệu trong ngôn ngữ được nghiên cứu trên hai phương diện khác nhau: Sự đặc tả và sự cài đặt kiểu dữ liệu. 2.4.2 Sự đặc tả kiểu dữ liệu Khi đặc tả một kiểu dữ liệu chúng ta thường quan tâm đến các thành phần cơ bản sau: • Các thuộc tính nhằm phân biệt các ÐTDL của kiểu. • Các giá trị mà các ÐTDL của kiểu có thể có. 10
16. Ngôn ngữ lập trình Chương II: Kiểu dữ liệu • Các phép toán có thể thao tác trên các ÐTDL của kiểu. Ví dụ, xét sự đặc tả kiểu dữ liệu mảng ta thấy: 1.- Các thuộc tính có thể bao gồm: số chiều, miền xác định của chỉ số đối với mỗi chiều và kiểu dữ liệu của các phần tử. 2.- Các giá trị có thể nhận của các phần tử mảng. 3.- Các phép toán có thể bao gồm: phép lựa chọn một phần tử mảng thông qua việc sử dụng chỉ số của phần tử đó, phép gán một mảng cho một mảng khác Phép toán Các phép toán thao tác trên các ÐTDL là một bộ phận không thể thiếu của kiểu dữ liệu. Khi nói đến kiểu dữ liệu mà chúng ta không quan tâm đến các phép toán là chưa hiểu đầy đủ về kiểu dữ liệu đó. Mà dường như khiếm khuyết này lại hay xẩy ra. Ví dụ khi nói đến kiểu integer trong ngôn ngữ Pascal, chúng ta chỉ nghĩ rằng đó là kiểu số nguyên, có các giá trị từ -32768 đến 32767, mà ít khi quan tâm đến các phép toán như +, -, *, hay nói chính xác hơn chúng ta cứ nghĩ các phép toán này là mặc nhiên phải có. Trong tin học không có cái gì tự nhiên mà có cả, mọi cái hoặc do chúng ta tự tạo ra hoặc sử dụng cái có sẵn do người khác đã tạo ra. Nhấn mạnh việc có mặt các phép toán trong kiểu dữ liệu là để lưu ý chúng ta khi định nghĩa một kiểu dữ liệu mới, phải trang bị cho nó các phép toán cần thiết. Có hai loại phép toán là các phép toán nguyên thủy được ngôn ngữ định nghĩa và các phép toán do người lập trình định nghĩa như là các chương trình con. Phép toán trong NNLT về phương diện lôgic là một hàm toán học: đối với một đối số (argument) đã cho nó có một kết quả duy nhất và xác định. Mỗi một phép toán có một miền xác định (domain) là tập hợp các đối số và một miền giá trị (range) là tập hợp các kết quả có thể tạo ra. Hoạt động của phép toán xác định kết quả được tạo ra đối với tập hợp bất kỳ các đối số đã cho. Giải thuật chỉ rõ làm thế nào để xác định kết quả đối với tập hợp bất kỳ các đối số đã cho là phương pháp phổ biến để xác định hoạt động của phép toán. Ngoài ra còn có những cách xác định khác chẳng hạn để xác định hoạt động của phép toán nhân chúng ta có thể cho một "bảng nhân" thay vì cho giải thuật của phép nhân hai số. Ðể chỉ rõ miền xác định của phép toán, số lượng, thứ tự và kiểu dữ liệu của các đối số, tương tự miền giá trị, số lượng, thứ tự và kiểu dữ liệu của các kết quả người ta thường sử dụng các ký hiệu toán học. Tên phép toán: Miền xác định -> Miền giá trị Trong đó Miền xác định = Kiểu đối số X Kiểu đối số X (Miền xác định là tập tích Đề-các của các kiểu đối số) Miền giá trị = Kiểu kết quả X Kiểu kết quả X (Miền giá trị là tập tích Đề-các của các kiểu kết quả) Khi nghiên cứu các phép toán trên các kiểu dữ liệu chúng ta cần lưu ý các vấn đề sau: 1.- Các phép toán không được xác định đầu vào một cách chắc chắn. 11
17. Ngôn ngữ lập trình Chương II: Kiểu dữ liệu Một phép toán được xác định trên nhiều hơn một miền xác định thường chứa đựng các lỗi. Ví dụ các phép toán số học có thể xác định trên nhiều tập hợp số khác nhau có thể gây ra sự tràn số hoặc một kết quả sai lệch mà ta không thể kiểm soát được. Ví dụ trong ngôn ngữ Pascal, phép cộng có thể xác định trên nhiều miền xác định khác nhau như integer, real, nên có thể có những kết quả sai lệch như trong ví dụ sau: var a, b : integer; begin {1} a:= 32767; {2} b:= 30000; {3} writeln(32767+30000); {4} writeln(a+b); end. Kết quả của chương trình trên là 62767 và -2769. Trong đó 62767 là kết quả của phép cộng 32767+30000. Đây là một kết quả đúng, do máy tính “hiểu” các số 32767 và 30000 là các số thực (real) và phép “+” trong lệnh {3} là “phép cộng các số thực”. Ngược lại -2769 là kết quả sai của phép toán a+b. Về mặt toán học thì kết quả của a+b là 62767, nhưng kết quả của chương trình máy tính lại là -2769! Sở dĩ chương trình máy tính (ngôn ngữ Pascal) lại có kết quả này là do hai biến a và b được khai báo là các biến thuộc kiểu integer nên phép “+” trong lệnh {4} được hiểu là “phép cộng các số nguyên”. Về nguyên tắc thì tổng a+b phải có giá trị thuộc kiểu integer nhưng do tập giá trị của kiểu integer là các số nguyên từ -32768 đến 32767 nên mới “sinh chuyện”. 2.- Các đối số ẩn Các phép toán trong chương trình thông thường sẽ được gọi với một tập hợp các đối số tường minh (explicit arguments). Tuy nhiên các phép toán có thể truy cập đến những đối số ẩn (implicit arguments) thông qua việc sử dụng các biến toàn cục hoặc tham chiếu các biến không cục bộ khác. Những đối số ẩn như thế sẽ gây khó khăn cho việc kiểm soát giá trị dữ liệu và do đó có thể ảnh hưởng đến kết quả của chương trình. Ví dụ: Var x: Integer; Procedure P; Begin x:= 0; End; Begin {1} x:=10; {2} P; {3} Writeln(x); End. Trong ví dụ trên, chương trình con P thực hiện việc giá trị 0 cho biến toàn cục x. Trong chương trình chính, mặc dù ta mới gán 10 cho x (lệnh 1), nhưng sau khi gọi thủ tục P (lệnh 2) thì ở lệnh 3, x lại có giá trị 0. Việc chương trình con sử dụng biến không cục bộ như vậy sẽ dễ gây ngộ nhận cho người lập trình rằng x có giá trị 10, đặc biệt khi thủ tục P được định nghĩa ở một đoạn nào đó, xa đoạn chương trình chính. 3.- Hiệu ứng lề 12
18. Ngôn ngữ lập trình Chương II: Kiểu dữ liệu Một phép toán có thể trả về một kết quả ẩn, và các kết quả ẩn như vậy sẽ gây ra hiệu ứng lề (side effect) làm thay đổi giá trị được lưu trữ của các ÐTDL khác mà người lập trình khó lòng kiểm soát. Các phép toán có thể gây nên hiệu ứng lề là phép gán (có trả về một giá trị) và các chương trình con mà tham số được truyền bằng quy chiếu. Chẳng hạn xét ví dụ sau trong Pascal: var m,n: integer; function f(var a: integer): integer; begin a := 2*a; f := 5; end; begin m := 10; n := m + f(m); writeln(n); readln; end. Với mọi số integer a hàm f luôn trả về một kết quả tường minh là 5 và một kết quả ẩn là 2a, chính kết quả ẩn này làm thay đổi giá trị của ÐTDL m do đó n sẽ có giá trị là 25 chứ không phải là 15 như chúng ta lầm tưởng. 2.4.3 Sự cài đặt kiểu dữ liệu Khi xét sự cài đặt kiểu dữ liệu ta phải quan tâm đến hai yếu tố sau: • Tổ chức lưu trữ giá trị dữ liệu của kiểu dữ liệu trong bộ nhớ của máy tính hay còn gọi là sự biểu diễn trong bộ nhớ. • Giải thuật thực hiện các phép toán thao tác trên các giá trị dữ liệu của kiểu. Hai yếu tố này liên quan chặt chẽ đến nhau, nói chính xác hơn là tuỳ thuộc vào cách thức tổ chức lưu trữ mà có các giải thuật thao tác tương ứng. 2.5 SỰ KHAI BÁO 2.5.1 Khái niệm khai báo Khai báo là một lệnh trong chương trình dùng để chuyển tới bộ dịch, thông tin về số lượng và kiểu của ÐTDL cần thiết trong quá trình thực hiện chương trình. Nhờ vị trí của khai báo trong chương trình, chẳng hạn đầu chương trình con, sự khai báo có thể chỉ rõ thời gian tồn tại của ÐTDL. Sự khai báo còn xác định sự liên kết của các ÐTDL với các tên của nó. Có hai loại khai báo là khai báo tường minh và khai báo ẩn. Khai báo tường minh là sự khai báo do người lập trình viết ra trong chương trình, như trong các khai báo của Pascal. Khai báo ẩn như trong trường hợp các ÐTDL được dùng một cách mặc nhiên mà không cần một sự khai báo tường minh nào. Ví dụ trong ngôn ngữ FORTRAN biến INDEX có thể dùng mà không cần khai báo tường minh và nó được trình biên dịch FORTRAN hiểu một cách mặc nhiên là một biến nguyên bởi vì tên của nó được bắt đầu bởi một trong các chữ cái từ I đến N. 13
19. Ngôn ngữ lập trình Chương II: Kiểu dữ liệu Ngôn ngữ lập trình được chia làm hai loại: ngôn ngữ khai báo, trong đó các ÐTDL phải được khai báo trước khi sử dụng và ngôn ngữ không khai báo, trong đó ÐTDL có thể sử dụng mà không cần phải khai báo. Với ngôn ngữ khai báo, ÐTDL sau khi đã khai báo phải sử dụng đúng như nó đã được khai báo, trong khi đối với ngôn ngữ không khai báo, một ÐTDL có thể sử dụng một cách tuỳ thích. Ðây là một trong những lý do làm cho ngôn ngữ không khai báo trở nên mềm dẻo hơn. 2.5.2 Mục đích của sự khai báo Việc khai báo có các mục đích quan trọng sau: • Chọn một tổ chức lưu trữ tốt nhất cho ÐTDL. Chẳng hạn trong ngôn ngữ Pascal để lưu trữ ngày trong tháng ta có thể khai báo biến ngay có kiểu là integer được lưu trữ trong bộ nhớ bởi 2 byte. Tuy nhiên trong một tháng chỉ có tối đa 31 ngày nên ta có thể khai báo biến ngay có kiểu miền con 1 31 được lưu trữ trong bộ nhớ chỉ với 1 byte. • Quản lý bộ nhớ: Sự khai báo cho phép xác định thời gian tồn tại của ÐTDL mà các chương trình quản lý bộ nhớ sử dụng để cấp phát và giải phóng bộ nhớ cho ÐTDL. • Các phép toán chung. Hầu hết các ngôn ngữ đều dùng các ký hiệu đặc biệt như "+" để chỉ một phép toán nào đó phụ thuộc vào kiểu dữ liệu của đối số. Ví dụ trong Pascal, "A+B" có nghĩa là "phép cọng các số nguyên" nếu A và B thuộc kiểu Integer, "phép cọng các số thực" nếu A và B thuộc kiểu real và là "phép hợp" nếu A và B thuộc kiểu tập hợp. Các phép toán như thế được gọi là các phép toán chung bởi vì nó không chỉ rõ một phép toán nhất định nào. Sự khai báo cho phép bộ dịch xác định một phép toán cụ thể được chỉ định bởi ký hiệu phép toán chung. Ví dụ trong Pascal, từ sự khai báo hai biến A và B, trình biên dịch sẽ xác định được phép toán cụ thể trong ba phép toán, theo đó nếu A, B là các biến integer thì "A+B" là phép cộng hai số nguyên, nếu A, B là hai biến real thì "A+B" là phép cộng hai số thực Ngược lại trong SNOBOL4 vì không có khai báo kiểu cho biến nên sự xác định phép "+" nào để thực hiện phải được làm tại thời điểm mà một phép "+" bị bắt gặp trong quá trình thực hiện chương trình. • Kiểm tra kiểu. Mục đích quan trọng nhất của việc khai báo là chúng cho phép kiểm tra kiểu của biến. Vì tính chất quan trọng của việc kiểm tra kiểu nên chúng ta sẽ xem xét nó trong mục sau. 2.6 KIỂM TRA KIỂU VÀ BIẾN ÐỔI KIỂU 2.6.1 Khái niệm kiểm tra kiểu Kiểm tra kiểu là kiểm tra xem kiểu thực nhận được của các đối số trong một phép toán có đúng với kiểu dữ liệu mà các đối số đó cần có hay không. Ví dụ trước khi thực hiện lệnh gán X := A * B việc kiểm tra phải được xác định đối với 2 phép toán nhân và phép gán. Trước hết phép nhân phải nhận được 2 tham số A, B có kiểu số, nếu cả A và B đúng là có kiểu số (chẳng hạn số nguyên) thì tiếp tục kiểm tra cho phép toán gán. Tích A*B sẽ là một số nguyên nên X cũng phải là một biến thuộc kiểu nguyên, nếu không đúng như vậy thì có sự sai kiểu. 14
20. Ngôn ngữ lập trình Chương II: Kiểu dữ liệu Kiểm tra kiểu có thể được tiến hành trong lúc chạy chương trình (kiểm tra kiểu động) hoặc trong lúc biên dịch chương trình (kiểm tra kiểu tĩnh). 2.6.2 Kiểm tra kiểu động Khái niệm: Kiểm tra kiểu động là kiểm tra kiểu được thực hiện trong khi thực hiện chương trình. Thông thường kiểm tra kiểu động được thực hiện một cách tức thì trước khi thực hiện một phép toán. Phương pháp thực hiện: Ðể kiểm tra kiểu động người ta phải lưu trữ thông tin về kiểu của mỗi một ÐTDL cùng với ĐTDL đó. Trước khi thực hiện một phép toán thông tin về kiểu của mỗi một đối số được kiểm tra. Nếu kiểu của các đối số là đúng thì phép toán sẽ được thực hiện và kiểu của kết quả sẽ được ghi lại để dùng kiểm tra cho các phép toán sau, ngược lại sẽ có một thông báo lỗi về kiểu . Ngôn ngữ sử dụng: Kiểm tra kiểu động được sử dụng trong các ngôn ngữ không khai báo như SNOBOL4, LISP, APL. Trong các ngôn ngữ này không có sự khai báo kiểu cho biến. Kiểu dữ liệu của các biến A và B trong biểu thức "A+B" có thể thay đổi trong quá trình thực hiện chương trình. Trong những trường hợp như vậy, kiểu của A và B phải được kiểm tra động tại mỗi lần phép cộng được gọi thực hiện. Trong các ngôn ngữ không khai báo, các biến đôi khi được gọi là không định kiểu vì chúng không có kiểu cố định. Ưu điểm: Ưu điểm chủ yếu của kiểm tra kiểu động là tính mềm dẻo trong khi viết chương trình: không yêu cầu khai báo kiểu và kiểu của ÐTDL có thể thay đổi trong quá trình thực hiện chương trình. Người lập trình không phải lo lắng về kiểu dữ liệu. Nhược điểm: Tuy nhiên kiểm tra kiểu động cũng có một số yếu điểm như sau: • Có khả năng bỏ sót lỗi về kiểu. Bởi vì việc kiểm tra động chỉ kiểm tra tại thời điểm thực hiện phép toán do đó các phép toán nằm trong nhánh chương trình không được thực hiện thì sẽ không được kiểm tra. Bất kỳ một nhánh chưa được kiểm tra nào đều có thể chứa các đối số có lỗi về kiểu và do đó các lỗi này có thể xuất hiện tại thời điểm sau đó. Ví dụ ta có một đoạn chương trình sau được viết trong một ngôn ngữ kiểm tra kiểu động: Nhập số a từ bàn phím; Nhập số b từ bàn phím; Nếu a > b Thì x := a + b Ngược lại x := a + “titi”; Nếu khi thực hiện đoạn chương trình này, người sử dụng luôn luôn nhập số a lớn hơn số b thì điều kiện a>b luôn luôn đúng nên không bao giờ chương trình 15
21. Ngôn ngữ lập trình Chương II: Kiểu dữ liệu thực hiện lệnh x := a + “titi” do đó không bao giờ phát hiện lỗi về kiểu: a là một số, không thể cộng với “titi” là một chuỗi. • Kiểm tra kiểu động đòi hỏi thông tin về kiểu phải được lưu giữ cho mỗi một ÐTDL trong quá trình thực hiện chương trình do đó yêu cầu về bộ nhớ phải lớn. • Kiểm tra kiểu phải được tiến hành tức thì trước mỗi khi thực hiện một phép toán nên tốc độ thực hiện chương trình chậm. 2.6.3 Kiểm tra kiểu tĩnh Khái niệm: Kiểm tra kiểu tĩnh là sự kiểm tra kiểu được thực hiện trong quá trình dịch chương trình. Phương pháp thực hiện: Theo nguyên tắc kiểm tra kiểu tĩnh, thông tin về kiểu của ÐTDL phải được cung cấp cho bộ dịch. Thông tin này một phần được cung cấp bởi phép khai báo của người lập trình và một phần bởi ngôn ngữ . Các thông tin bao gồm: • Ðối với mỗi một phép toán thì đó là số lượng, thứ tự và kiểu dữ liệu của đối số và kiểu của kết quả. Ðối với các phép toán nguyên thuỷ thì việc định nghĩa ngôn ngữ sẽ cung cấp các thông tin này còn đối với chương trình con thì người lập trình phải xác định một cách tường minh. • Ðối với mỗi một biến thì đó là kiểu của biến. • Ðối với mỗi một hằng, thì đó là kiểu của đối tượng dữ liệu hằng. Ngữ nghĩa của một hằng trực kiện sẽ chỉ ra kiểu của nó, chẳng hạn "2" là một số nguyên, "2.3" là một số thực. Kiểm tra kiểu tĩnh được thực hiện như sau: Thông qua đoạn đầu của chương trình, bộ biên dịch tập hợp thông tin từ sự khai báo trong chương trình vào trong bảng danh biểu (symbol table) nơi chứa thông tin về kiểu của các biến và chương trình con. Bộ biên dịch cũng sẽ có thông tin về các phép toán nguyên thuỷ được định nghĩa bởi ngôn ngữ, các hằng Khi gặp một phép toán thì phải tra trong bảng danh biểu để xác định kiểu của mỗi một đối số có hợp lệ hay không. Chú ý rằng nếu phép toán là phép toán chung như đã nói ở trên thì có thể có nhiều kiểu hợp lệ cho một đối số. Nếu kiểu của đối số là hợp lệ thì kiểu kết quả được xác định và bộ biên dịch ghi lại thông tin này để kiểm tra các phép toán sau. Ngôn ngữ sử dụng: Kiểm tra kiểu tĩnh thường được sử dụng trong các ngôn ngữ khai báo tức là khi viết chương trình, các biến phải được khai báo kiểu trước khi sử dụng như Pascal, C Ưu điểm: • Do phép kiểm tra kiểu tĩnh kiểm tra tất cả các phép toán có thể xuất hiện trong bất kỳ một lệnh nào của chương trình, tất cả các nhánh của chương trình đều được kiểm tra nên không thể có sự sót lỗi vê kiểu. 16
22. Ngôn ngữ lập trình Chương II: Kiểu dữ liệu • Mặt khác thông tin về kiểu không gắn với ÐTDL tại thời điểm thực hiện chương trình nên tiết kiệm được bộ nhớ và tăng tốc độ thực hiện chương trình. Nhược điểm: Yếu điểm chủ yếu của kiểm tra kiểu tĩnh là chương trình không mềm dẻo, người lập trình luôn phải lo lắng về việc sử dụng biến không đúng kiểu. 2.7 CHUYỂN ÐỔI KIỂU Trong quá trình kiểm tra kiểu, nếu có sự không tương thích giữa kiểu thực của đối số và kiểu đang được monng đợi của phép toán ấy thì có hai lựa chọn có thể: • Sự không tương thích kiểu bị báo lỗi hoặc • Một sự chuyển đổi kiểu tự động được thi hành để đổi kiểu của đối số thực tế thành kiểu đúng với yêu cầu. Chuyển đổi kiểu là một phép toán được định nghĩa như sau: Sự chuyển đổi: Kiểu1 -> Kiểu2 nghĩa là sự chuyển đổi lấy ÐTDL của một kiểu và sản sinh ra một ÐTDL "tương ứng" của một kiểu khác. Hầu hết các ngôn ngữ đều cung cấp hai phương pháp chuyển đổi kiểu: • Trang bị một tập hợp các hàm đã được xây dựng mà người lập trình có thể gọi trong chương trình để tạo ra sự chuyển đổi kiểu. Ví dụ Pascal trang bị hàm ROUND để đổi một ÐTDL số thực thành một đối tượng dữ liệu nguyên với giá trị bằng phần nguyên của số thực. • Như là một sự chuyển đổi tự động (còn gọi là ép kiểu) do ngôn ngữ thực hiện trong một số trường hợp không tương thích kiểu nào đó. Ví dụ trong Pascal các đối số của phép toán số học "+" có lẫn số thực và số nguyên hoặc khi gán một số nguyên cho một biến số thực thì số nguyên phải được đổi một cách tự động thành kiểu thực. Ðối với kiểm tra kiểu động thì sự chuyển đổi kiểu tự động được diễn ra tại điểm mà sự không tương thích kiểu được tìm thấy trong quá trình thực hiện chương trình. Ðối với sự kiểm tra kiểu tĩnh thì một mã phụ sẽ được xen vào trong chương trình đích dùng để gọi tới hàm biến đổi kiểu tại điểm thích hợp trong quá trình thực hiện. Chuyển đổi kiểu tự động giúp người lập trình khỏi mọi lo lắng về sự sai kiểu và tránh việc gọi tới một số lượng lớn các phép biến đổi kiểu tường minh trong chương trình. Tuy nhiên chúng ta nên tránh việc chuyển đổi kiểu bằng cách viết các phép toán đúng kiểu. Chẳng hạn trong lập trình thay vì viết lệnh x := 1 (với x là biến số thực) ta nên viết x := 1.0, với lệnh trước thì khi thực hiện phải có một sự chuyển đổi kiểu tự động còn với lệnh sau thì không cần nên thời gian thực hiện sẽ nhanh hơn. 2.8 GÁN VÀ KHỞI TẠO 2.8.1 Phép gán Gán trị cho biến là sự lưu trữ giá trị dữ liệu vào trong ô nhớ của biến đó. Gán trị là một phép toán cơ bản trong các NNLT. Nó dùng để thay đổi sự liên kết của giá trị với ÐTDL. 17
23. Ngôn ngữ lập trình Chương II: Kiểu dữ liệu Nói chung các ngôn ngữ khác nhau thì phép gán cũng khác nhau. Sự khác nhau đầu tiên là khác nhau về cú pháp, chẳng hạn ta có một số cú pháp lệnh gán như sau: A := B (Pascal hay Ada) A = B (C, C++, Fortran, PL/1 và SNOBOL4) MOVE B TO A (COBOL) A Void với sự hoạt động: Ðặt giá trị được chứa trong đối tượng dữ liệu Type1 thành bản sao của giá trị được chứa trong đối tượng dữ liệu Type2 và trả về một kết quả có kiểu void (có thể hiểu là không có kết quả trả về). Trong một số ngôn ngữ như C, C++ và LISP, phép gán trả về trực tiếp một kết quả là một bản sao của giá trị được gán. Chẳng hạn trong C, sự đặc tả phép gán là Phép gán (=) Type1 x Type2 -> Type3 với sự hoạt động: Ðặt giá trị được chứa trong đối tượng dữ liệu Type1 thành bản sao của giá trị được chứa trong đối tượng dữ liệu Type2 và tạo ra một ÐTDL mới Type3 chứa bản sao giá trị của Type2, trả về Type3 như là một kết quả. Vì phép gán trong Pascal không trả về một kết quả nên chúng ta chỉ sử dụng chức năng “gán trị” của nó mà thôi. Vì không có kết quả trả về nên mỗi một lệnh ta chỉ có thể viết một phép gán, chẳng hạn để gán giá trị 10 cho hai biến A và B ta phải viết hai lệnh B := 10; A := B; hoặc A := 10; B := 10; Ngược lại khi lập trình bằng ngôn ngữ C, vì phép gán có trả về một kết quả nên ta có thể viết: A = B = 10; Trong đó phép gán B =10 vừa thực hiện chức năng “gán trị” giá trị 10 cho B vừa trả về 1 giá trị để gán tiếp cho A. Giá trị được trả về như là một kết quả của phép gán B cho A bị bỏ qua vì lệnh không chứa một phép toán nào sau đó nữa. Phép gán trong ngôn ngữ C++ cũng có cùng cơ chế như trong C, vì vậy khi thiết kế toán tử gán cho một đối tượng nào đó (Overloading toán tử = trong khi xây dựng một lớp nào đó) ta phải viết: & operator= (const & Obj) { // Thực hiện việc gán dữ liệu; return *this; } Trong đó tên lớp là tên của lớp chúng ta đang định nghĩa. Phương thức này nhận vào một đối tượng Obj, thực hiện việc gán Obj cho đối tượng hiện hành và trả đối tượng hiện hành này về như một kết quả. Ví dụ ta tạo một class có tên là point để biểu diễn cho một điểm trong mặt phẳng được đặc trưng bởi hai tọa độ x và y. Trong chương trình ta muốn gán các điểm cho nhau, nên trong khi định nghĩa class point, ta phải định nghĩa toán tử gán. Cụ thể như sau: class point { 18
24. Ngôn ngữ lập trình Chương II: Kiểu dữ liệu float x; float y; public: point() {x=0.0 ; y=0.0;} // Phương thức xây dựng mặc nhiên point (float a, float b) {x=a; y=b;} // Phương thức xây dựng bình thường point & operator= (const point & p ) // Định nghĩa toán tử gán { x = p.x; y = p.y; // Gán dữ liệu return * this; } }; // term Sự khác nhau cuối cùng của phép gán là ở cách thức tiến hành gán trị. Xét lệnh gán của Pascal "A := B", ở Pascal cũng như một số ngôn ngữ khác, điều này có nghĩa là: "Gán bản sao của giá trị của biến B cho biến A". Bây giờ ta lại xét lệnh gán "A = B" của SNOBOL4. Trong SNOBOL4 thì nó có nghĩa là: "Tạo một biến tên A tham chiếu tới ÐTDL mà B đã tham chiếu". Trong SNOBOL4 cả A và B cùng trỏ tới một ÐTDL. Pascal A := B (Sao chép ÐTDL khi gán) Trước Sau 17.2 A: A: 8.4 8.4 8.4 B: B: SNOBOL4 A = B (Sao chép sự trỏ đến ÐTDL khi gán) Tr ướ c khi gán Sau khi gán 17.2 A: A: 8.4 8.4 B: B: Cách thực hiện lệnh gán của SNOBOL4 rõ ràng là đã tạo ra một sự lắm tên. 2.8.2 Sự khởi tạo biến Khởi tạo một biến là gán cho biến đó một giá trị đầu tiên. Một biến khi được tạo ra thì sẽ được cấp phát ô nhớ nhưng nó vẫn chưa được khởi tạo. Khi nó được gán một giá trị đầu tiên thì mới được khởi tạo. Các biến chưa được khởi tạo là nguồn gốc của các lỗi lập trình. Khi một biến được cấp phát ô nhớ mà chưa được khởi tạo thì trong ô nhớ của nó cũng có một giá trị ngẫu nhiên nào đó. Thường là một giá trị rác (Khi một ĐTDL nào trước đó đã bị hủy bỏ nhưng giá trị của ĐTDL này trong ô nhớ vẫn còn, giá trị này gọi là giá trị rác). Ðiều nguy hiểm là giá trị rác này vẫn là một giá trị hợp lệ. Vì thế chương trình có thể xử lý trên giá trị rác này một cách bình thường và chúng ta không thể kiểm sóat được kết quả xử lý đó. 19
25. Ngôn ngữ lập trình Chương II: Kiểu dữ liệu Vì tính chất nghiêm trọng như đã nói trên của biến chưa được khởi tạo, các ngôn ngữ lập trình có thể sử dụng các giải pháp sau để khắc phục: 1.- Nếu biến chưa được khở tạo thì sẽ có giá trị NULL: Khi một biến mới được tạo ra, ô nhớ cấp phát cho nó phải chứa một dãy các bit biểu diễn cho một giá trị “NULL”. Tùy thuộc vào kiểu của biến mà giá trị NULL này sẽ có một giá trị cụ thể, ví dụ nếu là biến số thì NULL là 0, nếu là biến chuỗi kí tự thì NULL là chuỗi rỗng, nếu biến là logic thì NULL là FALSE 2.- Khởi tạo biến ngay sau khi nó vừa được tạo ra là một cách lập trình tốt và trong một số ngôn ngữ mới đều cung cấp phương tiện để làm điều này một cách dễ dàng. Trong ngôn ngữ Pascal một biến được khởi tạo đồng thời với việc khai báo được gọi là biến có giá trị đầu hay còn gọi là hằng định kiểu. Ví dụ: const i:integer=10; a: ARRAY[1 3,1 2] Of Integer = ((11, 12), (21, 22), (31, 32)); var j:integer; begin writeln(i); i:= i+1; writeln(i); for i:=1 to 3 do begin for j:=1 to 2 do write(a[i,j]:5); writeln; end; end. 2.9 CÂU HỎI ÔN TẬP 1. Xét về mặt cấu trúc thì có các loại đối tượng dữ liệu nào? 2. Thế nào là một đối tượng dữ liệu sơ cấp? 3. Thế nào là một đối tượng dữ liệu có cấu trúc? 4. Đối tượng dữ liệu tường minh là gì? 5. Đối tượng dữ liệu ẩn là gì? 6. Kể tên các mối liên kết của đối tượng dữ liệu. 7. Thế nào là một biến? 8. Thế nào là một hằng? 9. Kiểu dữ liệu là gì? 10. Khi đặc tả một kiểu dữ liệu, chúng ta phải đặc tả những điều gì? 11. Cho ví dụ về một phép toán gây ra hiệu ứng lề. 12. Khi cài đặt một kiểu dữ liệu, chúng ta phải chỉ rõ những điều gì? 13. Mục đích của sự khai báo là gì? 14. Thế nào là kiểm tra kiểu? 15. Khi có sự không tương thích về kiểu thì chương trình dịch phải làm gì? 16. Kể tên các phương pháp kiểm tra kiểu. 20
26. Ngôn ngữ lập trình Chương II: Kiểu dữ liệu 17. Kiểm tra kiểu tĩnh được tiến hành trong lúc nào? 18. Kiểm tra kiểu động được tiến hành trong lúc nào? 19. Nêu các điểm mạnh của kiểm tra kiểu tĩnh. 20. Nêu các điểm yếu của kiểm tra kiểu tĩnh. 21. Nêu các điểm mạnh của kiểm tra kiểu động. 22. Nêu các điểm yếu của kiểm tra kiểu động. 23. Thông tin về kiểu trong kiểm tra kiểu tĩnh được lưu trữ ở đâu? 24. Thông tin về kiểu trong kiểm tra kiểu động được lưu trữ ở đâu? 25. Kiểm tra kiểu động được thực hiện trong ngôn ngữ nào? 26. Kiểm tra kiểu tĩnh được thực hiện trong ngôn ngữ nào? 27. Phép gán trị có trả về một kết quả không? 28. Thế nào là khởi tạo một biến? 29. Nếu trong một biểu thức có sử dụng một biến chưa được khởi tạo thì có thể đánh giá (định trị) được biểu thức đó không? 21
27. Ngôn ngữ lập trình Chương III: Kiểu dữ liệu sơ cấp CHƯƠNG 3: KIỂU DỮ LIỆU SƠ CẤP 3.1 TỔNG QUAN 3.1.1 Mục tiêu Sau khi học xong chương này, sinh viên cần phải nắm: - Khái niệm về kiểu dữ liệu sơ cấp. - Đặc tả và phương pháp cài đặt kiểu dữ liệu sơ cấp trong các ngôn ngữ lập trình. - Một số kiểu dữ liệu sơ cấp cụ thể như: kiểu số, ký tự, logic 3.1.2 Nội dung cốt lõi - Kiến thức tổng quan về kiểu dữ liệu sơ cấp. - Một vài kiểu dữ liệu sơ cấp: kiểu số, liệt kê, logic, ký tự. 3.1.3 Kiến thức cơ bản cần thiết Kiến thức và kĩ năng lập trình căn bản, kiến thức chương 2. 3.2 ÐỊNH NGHĨA KIỂU DỮ LIỆU SƠ CẤP Kiểu dữ liệu sơ cấp là một kiểu dữ liệu mà các ÐTDL của nó là các ÐTDL sơ cấp. Nói chung các ngôn ngữ lập trình đều có các kiểu dữ liệu sơ cấp sau: số nguyên (integer, int ), số thực (real, float, double ), ký tự (char, character ), logic (bool, boolean ) và kiểu liệt kê. 3.3 SỰ ÐẶC TẢ CÁC KIỂU DỮ LIỆU SƠ CẤP 3.3.1 Thuộc tính của kiểu dữ liệu sơ cấp Thuộc tính cơ bản nhất của bất kỳ một ÐTDL sơ cấp nào chính là kiểu dữ liệu của nó. Ðối với một số kiểu dữ liệu cụ thể thì có thể có thêm các thuộc tính bổ sung để đặc trưng cho kiểu đó. 3.3.2 Giá trị của kiểu dữ liệu sơ cấp Tập hợp các giá trị của một kiểu dữ liệu sơ cấp luôn là một tập hợp có thứ tự và có một giá trị nhỏ nhất và một giá trị lớn nhất. Chính nhờ tính chất có thứ tự của tập giá trị sơ cấp nên trong thao tác sắp xếp dữ liệu, khóa sắp xếp thường thuộc kiểu dữ liệu sơ cấp. Ví dụ kiểu dữ liệu integer là một tập hợp hữu hạn các số nguyên (dĩ nhiên là có thứ tự), từ một số nguyên nhỏ nhất đến một số nguyên lớn nhất. Số nguyên nhỏ nhất và số nguyên lớn nhất là các số nguyên tương ứng với các giá trị nguyên nhỏ nhất và lớn nhất có thể biểu diễn một cách thuận tiện trong bộ nhớ của máy tính. 22
28. Ngôn ngữ lập trình Chương III: Kiểu dữ liệu sơ cấp 3.3.3 Phép toán trên kiểu dữ liệu sơ cấp Do tập giá trị sơ cấp có thứ tự, nên trong tất cả các kiểu dữ liệu sơ cấp đều có các phép toán quan hệ. Ngoài ra còn có các phép toán nhận vào một số đối số thuộc kiểu sơ cấp và trả về một giá trị sơ cấp cùng kiểu. Tuy nhiên cần hết sức lưu ý rằng tập các giá trị sơ cấp có giá trị nhỏ nhất và giá trị lớn nhất, cho nên đôi khi giá trị trả về của phép toán không nằm trong giới hạn của tập giá trị sơ cấp, điều này sẽ gây ra sự sai sót trong chương trình. 3.4 CÀI ÐẶT CÁC KIỂU DỮ LIỆU SƠ CẤP 3.4.1 Tổ chức dữ liệu trong bộ nhớ Người ta thường sử dụng việc tổ chức dữ liệu dưới phần cứng của máy tính để biểu diễn cho các giá trị dữ liệu của kiểu dữ liệu sơ cấp. Lý do của việc lựa chọn này rất đơn giản: Nếu biểu diễn bộ nhớ của phần cứng được sử dụng thì các phép toán cơ bản trên dữ liệu của kiểu này có thể được thực hiện bởi các phép toán do phần cứng cung cấp. Mà các phép toán được thiết kế bởi phần cứng sẽ có tốc độ thực hiện nhanh. Ngược lại, nếu ta sử dụng sự biểu diễn bởi phần mềm thì phải sử dụng các phép toán mô phỏng bởi phần mềm mà tốc độ thực hiện sẽ chậm hơn. Tuy nhiên, việc sử dụng biểu diễn bởi phần cứng cũng có yếu điểm là tập các giá trị sẽ bị hạn chế. Ví dụ để biểu diễn một số nguyên trong bộ nhớ, ta có thể sử dụng hai phương pháp: 1.- Sử dụng cách biểu diễn một số nguyên của phần cứng, chẳng hạn sử dụng 16 bit để biểu diễn cho một số nguyên. Với phương pháp này thì ta có thể sử dụng luôn các phép tính số học trên số nguyên (+, -, *, DIV, MOD) đã được thiết kế cho phần cứng. Ưu điểm của phương pháp này là các phép tính số học có tốc độ thực hiện nhanh. Nhược điểm của phương pháp là tập giá trị các số nguyên chỉ có 65535 số (từ -32768 đến 32767). 2.- Sử dụng một cấu trúc dữ liệu nào đó để biểu diễn cho một số nguyên, chẳng hạn sử dụng một chuỗi kí tự, trong đó mỗi kí tự lưu trữ môt chữ số. Ưu điểm của phương pháp là tập các giá trị nguyên sẽ rất lớn (số các chữ số trong một nguyên có thể bằng chiều dài của chuỗi kí tự biểu diễn cho nó). Nhược điểm của phương pháp là chúng ta phải xây dựng các chương trình con để thực hiện các phép tính số học và dĩ nhiên tốc độ thực hiện của các chương trình con này sẽ chậm hơn các phép tính được xây dựng trong phần cứng. Các thuộc tính (chủ yếu là kiểu dữ liệu) của ÐTDL sơ cấp được xử lý bằng 2 cách chính như sau: 1.- Các thuộc tính của ÐTDL có thể được xác định trong khi biên dịch bởi trình biên dịch. Các thuộc tính này sẽ được lưu trữ trong bộ dịch của ngôn ngữ (chẳng hạn bảng danh biểu) và khi cần sẽ tìm lại các thuộc tính này để sử dụng. Ðó là phương pháp thông dụng trong các ngôn ngữ biên dịch như FORTRAN, C và Pascal, nơi mà tính hiệu quả của việc sử dụng bộ nhớ và tốc độ thực hiện chương trình là những mục tiêu trên hết. 23
29. Ngôn ngữ lập trình Chương III: Kiểu dữ liệu sơ cấp 2.- Các thuộc tính có thể được lưu trữ trong bộ mô tả như là một phần của ÐTDL tại thời gian thực hiện. Ðây là phương pháp thông dụng trong các ngôn ngữ thông dịch như LISP và SNOBOL4, nơi mà tính linh hoạt mềm dẻo là mục tiêu trước hết chứ không phải là tính hiệu quả. 3.4.2 Cài đặt phép toán Mỗi một phép toán thao tác trên các ÐTDL của một kiểu dữ liệu sơ cấp đã cho có thể được cài đặt bằng một trong 3 cách như sau: 1.- Như là một phép toán phần cứng trực tiếp, nếu sự biểu diễn bộ nhớ của ÐTDL là sự biểu diễn của phần cứng. Ví dụ nếu các số nguyên được lưu trữ bằng cách dùng biểu diễn phần cứng cho số nguyên thì các phép toán như phép cộng, trừ và các phép toán số học khác của số nguyên có thể được thực hiện bằng cách dùng các phép toán số học cho số nguyên đã được xây dựng trong phần cứng. 2.- Như là một thủ tục hoặc hàm thực hiện các phép toán. Ví dụ phép toán lấy căn bậc hai thông thường không được cung cấp một cách trực tiếp như là một phép toán trong phần cứng ngay cả khi các số được biểu diễn bằng sự biểu diễn của phần cứng và vì vậy nó được cài đặt như là một chương trình con tính căn bậc hai. Nếu các ÐTDL không được biểu diễn bằng sự biểu diễn xác định bởi phần cứng thì tất cả các phép toán phải được mô phỏng bởi phần mềm. 3.- Như là một chuỗi các dòng mã lệnh dùng để thực hiện phép toán như là một dãy các phép toán phần cứng. Ví dụ hàm lấy trị tuyệt đối của một số được định nghĩa là: ⎧ x nêu x ≥ 0 ABS(x) = ⎨ thường được cài đặt như là một chuỗi các mã lệnh: ⎩- x nêu x =0 thì bỏ qua chỉ thị kế tiếp 3.- Ðặt x = -x 4.- Lưu x vào bộ nhớ Trong đó mỗi một dòng mã lệnh được thực hiện bởi một phép toán trong phần cứng. 3.5 KIỂU DỮ LIỆU SỐ Hầu hết các ngôn ngữ lập trình đều có các kiểu dữ liệu số, nhưng các chi tiết của sự đặc tả và phép cài đặt các kiểu này có nhiều điểm khác nhau. Kiểu số nguyên và kiểu số thực là phổ biến nhất bởi vì chúng dựa một cách trực tiếp vào phần cứng của máy tính. 3.5.1 Số nguyên Sự đặc tả Đặc tả các thuộc tính: Một ÐTDL của kiểu số nguyên không có thuộc tính nào khác ngoài kiểu của nó. Đặc tả giá trị: Tập hợp các giá trị nguyên được xác định theo dạng là một tập hợp con có thứ tự hữu hạn của tập vô hạn các số nguyên đã được nghiên cứu trong toán học. 24
30. Ngôn ngữ lập trình Chương III: Kiểu dữ liệu sơ cấp Giá trị nguyên lớn nhất đôi khi được biểu diễn như là một hằng xác định. Ví dụ trong Pascal là hằng MaxInt. Miền giá trị của kiểu số nguyên là tập các số nguyên từ - MaxInt đến MaxInt. Giá trị MaxInt được lựa chọn phản ánh giá trị nguyên lớn nhất có thể biểu diễn được trong phần cứng. Ðặc tả các phép toán: Trên ÐTDL nguyên thường có các nhóm phép toán chính như sau: 1.- Các phép tính số học Các phép tính số học hai ngôi thường được định nghĩa là: Bin_Op: Integer x Integer -> Integer. Ở đây Bin_Op có thể là cộng (+), trừ (-), nhân (*), chia (/ hoặc DIV), lấy phần dư (MOD) hoặc một số phép toán tương tự khác. Các phép tính số học một ngôi được định nghĩa: Unary_Op : Integer -> Integer Ở đây Unary_Op có thể là âm (-), dương (+). Các phép toán số học phổ biến khác thường được chứa trong thư viện chương trình con. 2.- Các phép toán quan hệ Các phép toán quan hệ được định nghĩa là: Rel_Op : Integer x Integer -> Boolean Ở đây Rel_Op có thể là bằng, khác, nhỏ hơn, lớn hơn, nhỏ hơn hoặc bằng, lớn hơn hoặc bằng. Phép toán quan hệ so sánh hai giá trị dữ liệu đối số và trả về kết quả là một đối tượng dữ liệu logic (đúng hoặc sai). 3.- Gán trị Cũng như phép gán tổng quát, phép gán của số nguyên có thể trả về (với định nghĩa: Assignment : Intger x Integer -> Integer) hoặc không trả về một giá trị (với đinh nghĩa: Assignment : Integer x Intger -> Void) . Sự cài đặt Kiểu dữ liệu nguyên hầu hết được cài đặt một cách trực tiếp bằng cách dùng sự biểu diễn bộ nhớ được xác định bởi phần cứng và tập hợp các phép tính số học, các phép toán quan hệ nguyên thuỷ trong phần cứng cho các số nguyên. Thông thường sự biểu diễn này sử dụng một từ trong bộ nhớ hoặc một dãy các bytes để lưu trữ một số nguyên. Chẳng hạn ngôn ngữ Pascal đã sử dụng biểu diễn số nguyên bởi 1 từ (word) trong phần cứng của máy tính để biểu diễn cho một số integer. 3.5.2 Miền con của số nguyên Sự đặc tả Kiểu miền con của kiểu dữ liệu nguyên là một kiểu dữ liệu mà tập các giá trị của nó là một dãy các giá trị nguyên trong một khoảng giới hạn đã định. Các dạng khai báo sau thường được sử dụng: A : 1 10 (Pascal) 25
31. Ngôn ngữ lập trình Chương III: Kiểu dữ liệu sơ cấp A : Integer Range 1 10 (Ada) Như vậy về thuộc tính, kiểu miền con của kiểu số nguyên, có thuộc tính của kiểu số nguyên. Về giá trị, tập các giá trị của kiểu miền con được xác định rõ trong phép khai báo và cuối cùng, kiểu miền con cho phép sử dụng tập hợp phép toán như trong kiểu số nguyên bình thường. Sự cài đặt Kiểu miền con được cài đặt tương tự như cài đặt kiểu số nguyên. Lợi ích của việc sử dụng kiểu miền con Kiểu miền con có một ưu điểm nổi bật đó là kiểm tra kiểu tốt hơn kiểu số nguyên. Việc khai báo một biến kiểu miền con cho phép kiểm tra kiểu một cách nghiêm ngặt hơn khi thực hiện lệnh gán trị cho biến. Ví dụ để lưu trữ các tháng trong một năm ta có thể sử dung biến MONTH với khai báo kiểu miền con là MONTH: 1 12 thì lệnh gán MONTH := 0 là không hợp lệ và lỗi đó được tự động tìm thấy khi biên dịch. Nhưng nếu MONTH được khai báo là Integer thì lệnh gán trên là hợp lệ và lỗi chỉ có thể được tìm ra bởi người lập trình trong quá trình chạy thử. 3.5.3 Số thực dấu chấm động Sự đặc tả Tập hợp các giá trị thực dấu chấm động được xác định là một dãy số có thứ tự từ một số âm nhỏ nhất tới một số lớn nhất được xác định trong phần cứng của máy tính, nhưng các giá trị không được phân bố rời rạc đều trong giới hạn này. Các phép tính số học, các phép toán quan hệ, phép gán đối với số thực cũng giống như đối với số nguyên. Một số phép toán khác cũng được các ngôn ngữ trang bị như là các hàm, chẳng hạn: SIN : Real -> Real (Hàm SIN) COS : Real -> Real (Hàm COSIN) SQRT: Real -> Real (Hàm lấy căn bậc hai) MAX : Real x Real -> Real (Hàm lấy giá trị lớn nhất) Sự cài đặt Sự biểu diễn bộ nhớ cho kiểu dữ liệu thực dấu chấm động dựa trên cơ sở biểu diễn phần cứng trong đó một ô nhớ được chia thành một phần định trị (mantissa) và một số mũ (exponent). Các phép tính số học và các phép toán quan hệ trên kiểu số thực được hỗ trợ bởi phần cứng. Các phép toán khác phải được ngôn ngữ cài đặt như là các chương trình con. 26
32. Ngôn ngữ lập trình Chương III: Kiểu dữ liệu sơ cấp 3.6 KIỂU LIỆT KÊ 3.6.1 Đặt vấn đề Trong lập trình, có một điều phổ biến là một biến có thể lấy một hoặc một số nhỏ các giá trị. Chẳng hạn biến NGAY_TRONG_TUAN chỉ lấy 7 giá trị biểu diễn cho “chủ nhât”, “thứ hai”, “thứ ba”, ”thứ bảy”. Tương tự biến GIOI_TINH chỉ có hai giá trị biểu diễn là "nam" và "nữ". Trong các ngôn ngữ như FORTRAN hay COBOL một biến như vậy phải có kiểu số nguyên và các giá trị được biểu diễn bởi các số nguyên chẳng hạn "chủ nhật" được biểu diễn bởi số 1, "thứ hai" được biểu diễn bởi số 2, "nam" được biểu diễn bởi số 0 và "nữ" được biểu diễn bởi số 1. Chương trình sử dụng các giá trị này như là các số nguyên và người lập trình phải nhớ sự tương ứng giữa các giá trị nguyên với "nghĩa" của chúng trong ứng dụng. Quả thực đây là một điều bất tiện và dễ gây ra sai sót. Nhiều ngôn ngữ mới như Pascal hay Ada cho phép người lập trình tự đặt ra một kiểu dữ liệu bằng cách liệt kê ra một danh sách các giá trị của kiểu đó. Kiểu này gọi là kiểu liệt kê. 3.6.2 Sự đặc tả Người lập trình định nghĩa kiểu liệt kê bằng cách liệt kê ra một danh sách các tên trực kiện thông qua sự khai báo. Các tên trực kiện trong danh sách là các giá trị của kiểu và thứ tự của chúng cũng được xác định nhờ thứ tự chúng xuất hiện trong danh sách. Chẳng hạn, ta có khai báo biến trong Pascal: VAR NGAY_TRONG_TUAN : (Chu_nhat, Hai, Ba, Tu, Nam, Sau, Bay); Vì có nhiều biến có cùng một kiểu liệt kê được dùng trong một chương trình nên người ta thường định nghĩa một liệt kê như là một kiểu có tên, sau đó sử dụng nó để xác định kiểu cho nhiều biến như trong Pascal: TYPE NGAY = (Chu_nhat, Hai, Ba, Tu, Nam, Sau, Bay); sau đó khai báo biến: VAR NGAY_TRONG_TUAN, NGAY_LAM_VIEC: NGAY; Trong sự khai báo trên, các tên trực kiện như Chu_nhat, Hai, Ba, chính là các giá trị của kiểu và các giá trị này được sắp thứ tự như chúng đã được ghi ra, tức là Chu_nhat < Hai < Ba < < Bay. Chú ý rằng kiểu NGAY đã được định nghĩa thì có thể được dùng như một tên kiểu nguyên thuỷ (Integer chẳng hạn) và các hằng trực kiện như Chu_nhat, Hai, Ba, Tu, cũng được sử dụng như là các hằng trực kiện nguyên thuỷ (chẳng hạn "27"). Vì thế ta có thể viết: IF NGAY_TRONG_TUAN = Hai THEN Các phép toán cơ bản trong kiểu liệt kê là các phép toán quan hệ (bằng, nhỏ hơn, lớn hơn ), phép gán trị, phép toán cho giá trị đứng sau và giá trị đứng trước một giá trị trong dãy các hằng trực kiện của liệt kê. 27
33. Ngôn ngữ lập trình Chương III: Kiểu dữ liệu sơ cấp 3.6.3 Sự cài đặt Biểu diễn bộ nhớ cho một ÐTDL kiểu liệt kê thường là không phức tạp. Mỗi giá trị trong liệt kê được biểu diễn bằng một số nguyên 0, 1, 2, Ví dụ kiểu NGAY ở trên chỉ cần sử dụng 7 giá trị từ 0 đến 6, trong đó 0 biểu diễn cho Chu_nhat, 1 biểu diễn cho Hai, 2 biểu diễn cho Ba, Sự cài đặt các phép toán cơ bản cũng không phức tạp. Các phép quan hệ được cài đặt bằng cách sử dụng các phép toán quan hệ dưới phần cứng cho số nguyên như "=", " ", Phép toán lấy giá trị đứng sau một giá trị được cài đặt bằng cách lấy số nguyên biểu diễn cho giá trị đó cộng thêm 1 và có sự kiểm tra để thấy được kết quả không vượt quá giới hạn cho phép. Chẳng hạn để xác định giá trị sau Hai, ta lấy 1 (biểu diễn cho Hai) cộng với 1 được 2, mà 2 biểu diễn cho Ba, nên sau Hai là Ba, nhưng sau Bay thì không có giá trị nào vì tổng của 6 (biểu diễn cho Bay) với 1 được 7, vượt quá giới hạn cho phép của kiểu. Tương tự cho phép toán lấy giá trị đứng trước của một giá trị. 3.6.4 Lợi ích của việc sử dụng kiểu liệt kê Kiểu liệt kê được đưa vào trong ngôn ngữ lập trình nhằm để giải quyết vấn đề được nêu ra trong phần đặt vấn đề. Từ đó ta có thể thấy rõ việc sử dụng kiểu liệt kê làm cho chương trình sáng sủa, trực quan, người lập trình không còn phải nhớ “nghĩa” của giá trị số và do vậy chương trình sẽ có độ chính xác cao hơn. Nói cách khác, kiểu liệt kê làm tăng tính dễ đọc, tính dễ viết và độ tin cậy của ngôn ngữ. 3.7 KIỂU LOGIC Kiểu logic (bool, boolean hoặc logical) là kiểu dữ liệu phổ biến trong hầu hết các ngôn ngữ. 3.7.1 Sự đặc tả Kiểu dữ liệu logic gồm các ÐTDL có một trong hai giá trị đúng hoặc sai. Trong Pascal và Ada, kiểu dữ liệu logic được xem một cách đơn giản như là một liệt kê được định nghĩa bởi ngôn ngữ. BOOLEAN = (FALSE, TRUE) trong đó xác định các tên "FALSE" và "TRUE" cho các giá trị của kiểu và xác định thứ tự FALSE Boolean OR: Boolean X Boolean -> Boolean NOT: Boolean -> Boolean 3.7.2 Phép cài đặt Chỉ cần một bit của bộ nhớ để lưu trữ một đố tượng dữ liệu logic. Tuy nhiên vì các bit đơn có thể không có địa chỉ riêng trong bộ nhớ nên ta phải sử dụng một đơn vị nhớ có địa chỉ như là byte hoặc word do đó các giá trị FALSE và TRUE có thể được biểu diễn bằng hai cách khác nhau: 1.- Bit đặc trưng (thông thường là bit dấu của sự biểu diễn số) với 0 biểu diễn cho FALSE và 1 biểu diễn cho TRUE, các bits còn lại trong byte hoặc word sẽ bị bỏ qua. 28
34. Ngôn ngữ lập trình Chương III: Kiểu dữ liệu sơ cấp 2.- Sử dụng toàn bộ đơn vị nhớ để ghi giá trị zero (tất cả các bit đề bằng 0) biểu diễn cho FALSE còn giá trị khác zero biểu diễn cho TRUE. 3.8 KIỂU KÝ TỰ Hầu hết dữ liệu xuất và nhập đều có dạng ký tự và có sự chuyển đổi sang dạng dữ liệu khác trong quá trình nhập xuất. Chẳng hạn khi ta nhập một chữ số (hoặc một chuỗi chữ số) từ bàn phím vào một biến số trong chương trình thì đã có một sự chuyển đổi chữ số (chuỗi chữ số) thành số. Hay khi ta ghi một số ra máy in hoặc ra một tập tin văn bản thì đã có một sự chuyển đổi từ số thành chữ số (chuỗi chữ số). Tuy nhiên việc xử lý một số dữ liệu trực tiếp dưới dạng ký tự cũng cần thiết trong một số ứng dụng nào đó, chẳng hạn trong xử lý văn bản. Dữ liệu chuỗi ký tự có thể được cung cấp một cách trực tiếp thông qua kiểu chuỗi ký tự (như trong SNOBOL4, PL/1 và các ngôn ngữ mới khác) hoặc thông qua kiểu ký tự và chuỗi ký tự được xem như là một mảng các ký tự (như trong APL, Pascal và Ada. Chú ý Turbo Pascal đã có kiểu chuỗi ký tự). 3.8.1 Sự đặc tả Kiểu ký tự là một liệt kê được định nghĩa bởi ngôn ngữ tương ứng với một tập hợp ký tự chuẩn được cho bởi phần cứng và hệ điều hành như tập các ký tự ASCII chẳng hạn. Các phép toán trên dữ liệu ký tự bao gồm: các phép toán quan hệ, phép gán, và đôi khi có phép kiểm tra xem một ký tự có thuộc một lớp đặc biệt "chữ cái", "chữ số" hoặc lớp ký tự xác định nào đó. 3.8.2 Phép cài đặt Các giá trị dữ liệu hầu như luôn được cài đặt một cách trực tiếp bởi phần cứng và hệ điều hành. Do đó các phép toán quan hệ cũng được biểu diễn một cách trực tiếp bởi phần cứng. 3.9 CÂU HỎI ÔN TẬP 1. Nêu định nghĩa kiểu dữ liệu sơ cấp. 2. Tập các giá trị của một kiểu sơ cấp có đặc điểm gì? 3. Có phải các ngôn ngữ lập trình thường sử dụng biểu diễn trong phần cứng để biểu diễn cho kiểu số nguyên? 4. Ðể cài đặt các phép toán số học trên kiểu dữ liệu số nguyên, có phải người ta phải thiết lập các chương trình con trong ngôn ngữ? 5. Tại sao người ta lại sử dụng kiểu liệt kê? 6. Tại sao người ta lại sử dụng kiểu miền con? 29
35. Ngôn ngữ lập trình Chương IV: Kiểu dữ liệu có cấu trúc CHƯƠNG 4: KIỂU DỮ LIỆU CÓ CẤU TRÚC 4.1 TỔNG QUAN 4.1.1 Mục tiêu Sau khi học xong chương này, sinh viên cần phải nắm: - Khái niệm về kiểu dữ liệu có cấu trúc. - Đặc tả và phương pháp cài đặt kiểu dữ liệu có cấu trúc. - Các đặc tả, phương pháp tổ chức lưu trữ, cài đặt các phép toán của một số kiểu dữ liệu có cấu trúc như: vecto, mảng nhiều chiều, mẩu tin, chuỗi ký tự 4.1.2 Nội dung cốt lõi - Kiểu dữ liệu có cấu trúc. - Các đặc tả, phương pháp lưu trữ, hình thức truy xuất, cài đặt các phép toán của một số kiểu dữ liệu có cấu trúc. 4.1.3 Kiến thức cơ bản cần thiết Kiến thức và kĩ năng lập trình căn bản, kiến thức chương 2. 4.2 ÐỊNH NGHĨA KIỂU DỮ LIỆU CÓ CẤU TRÚC Kiểu dữ liệu có cấu trúc hay còn gọi là cấu trúc dữ liệu (CTDL) là một kiểu dữ liệu mà các ÐTDL của nó là các ÐTDL có cấu trúc. Như vậy CTDL là một tập hợp các ÐTDL có cấu trúc cùng với tập hợp các phép toán thao tác trên các ÐTDL đó. Các kiểu dữ liệu như mảng, mẩu tin, chuỗi, ngăn xếp (stacks), danh sách, con trỏ, tập hợp và tập tin là các CTDL. 4.3 SỰ ÐẶC TẢ KIỂU CẤU TRÚC DỮ LIỆU 4.3.1 Sự đặc tả các thuộc tính Các thuộc tính chủ yếu của CTDL bao gồm: Số lượng phần tử Số lượng các phần tử của một CTDL cho biết kích thước của CTDL, số lượng này có thể cố định hoặc thay đổi tuỳ loại CTDL. Một CTDL được gọi là có kích thước cố định nếu số lượng các phần tử không thay đổi trong thời gian tồn tại của nó. Ví dụ các kiểu mảng, mẩu tin là các CTDL có kích thước cố định. Một CTDL được gọi là có kích thước thay đổi nếu số lượng các phần tử thay đổi một cách động trong thời gian tồn tại của nó. Ví dụ ngăn xếp, danh sách, tập hợp, chuỗi ký tự và tập tin là các CTDL có kích thước thay đổi. Các phép toán cho phép thêm hoặc bớt các phần tử của cấu trúc làm thay đổi kích thước của cấu trúc. 30
36. Ngôn ngữ lập trình Chương IV: Kiểu dữ liệu có cấu trúc Kiểu của mỗi một phần tử Mỗi một phần tử của CTDL có một kiểu dữ liệu nào đó, ta gọi là kiểu phần tử. Kiểu phần tử có thể là một kiểu dữ liệu sơ cấp hoặc một CTDL. Các phần tử trong cùng một CTDL có thể có kiểu phần tử giống nhau hoặc khác nhau. Một CTDL được gọi là đồng nhất nếu tất cả các phần tử của nó đều có cùng một kiểu. Ví dụ mảng, chuỗi ký tự, tập hợp và tập tin là các CTDL đồng nhất . Một CTDL được gọi là không đồng nhất nếu các phần tử của nó có kiểu khác nhau. Ví dụ mẩu tin là CTDL không đồng nhất. Tên để dùng cho các phần tử được lựa chọn Ðể lựa chọn một phần tử của CTDL cho một xử lý nào đó người ta thường sử dụng một tên. Ðối với cấu trúc mảng, tên có thể là một chỉ số nguyên hoặc một dãy chỉ số; đối với mẩu tin, tên là một tên trường. Một số kiểu cấu trúc dữ liệu như ngăn xếp và tập tin cho phép truy nhập đến chỉ một phần tử đặc biệt (phần tử đầu tiên hoặc phần tử hiện hành). Số lượng lớn nhất các phần tử Ðối với CTDL có kích thước thay đổi như chuỗi ký tự hoặc ngăn xếp, đôi khi người ta quy định thuộc tính kích thước tối đa của cấu trúc để giới hạn số lượng các phần tử của cấu trúc. Tổ chức cấu trúc Tổ chức phổ biến nhất là một dãy tuần tự của các phần tử. Vector (mảng một chiều), mẩu tin, chuỗi ký tự, ngăn xếp, danh sách và tập tin là các CTDL có tổ chức kiểu này. Một số cấu trúc còn được mở rộng thành dạng "nhiều chiều" ví dụ mảng nhiều chiều, mẩu tin mà các phần tử của nó là các mẩu tin, danh sách mà các phần tử của nó là danh sách. 4.3.2 Các phép toán trên cấu trúc dữ liệu Một số các phép toán đặc thù của CTDL: Phép toán lựa chọn phần tử của cấu trúc Phép toán lựa chọn một phần tử là phép toán truy nhập đến một phần tử của CTDL và làm cho nó có thể được xử lý bởi một phép toán khác. Có hai loại lựa chọn: Lựa chọn ngẫu nhiên (hay còn gọi là lựa chọn trực tiếp) là sự lựa chọn một phần tử tùy ý của cấu trúc dữ liệu được truy nhập thông qua một cái tên. Ví dụ để lựa chọn một phần tử nào đó của mảng, ta chỉ ra chỉ số của phần tử đó, để lựa chọn một phần tử của mẩu tin ta sử dụng tên của phần tử đó. 31
37. Ngôn ngữ lập trình Chương IV: Kiểu dữ liệu có cấu trúc Lựa chọn tuần tự là sự lựa chọn trong đó phần tử được lựa chọn là một phần tử đứng sau các phần tử đã được lựa chọn khác theo tuần tự của việc xử lý hoặc là lựa chọn một phần tử đặc biệt nào đó. Ví dụ lựa chọn tuần tự các phần tử trong một tập tin hay lựa chọn một phần tử trên đỉnh của ngăn xếp. Các phép toán thao tác trên toàn bộ cấu trúc dữ liệu Là các phép toán có thể nhận các CTDL làm các đối số và sản sinh ra kết quả là các CTDL mới. Chẳng hạn phép gán một mẩu tin cho một mẩu tin khác hoặc phép hợp hai tập hợp. Thêm / bớt các phần tử Là các phép toán cho phép thêm vào CTDL hoặc loại bỏ khỏi CTDL một số phần tử. Các phép toán này sẽ làm thay đổi số lượng các phần tử trong một CTDL. Việc thêm vào hay loại bỏ một phần tử thường phải chỉ định một vị trí nào đó. Tạo / hủy CTDL Là các phép toán tạo ra hoặc xóa bỏ một CTDL. 4.4 SỰ CÀI ÐẶT CÁC CẤU TRÚC DỮ LIỆU 4.4.1 Biểu diễn bộ nhớ Sự biểu diễn bộ nhớ cho một CTDL bao gồm: - Bộ nhớ cho các phần tử của cấu trúc. - Bộ mô tả để lưu trữ một số hoặc tất cả các thuộc tính của cấu trúc. Có hai phương pháp để biểu diễn bộ nhớ là: Biểu diễn tuần tự Biểu diễn tuần tự là sự biểu diễn, trong đó CTDL được lưu trữ như một khối các ô nhớ liên tiếp nhau, bắt đầu bằng bộ mô tả sau đó là các phần tử. Ðây là phương pháp được dùng cho các CTDL có kích thước cố định hoặc có kích thước thay đổi nhưng đồng nhất. Chẳng hạn có thể dùng biểu diễn tuần tự để biểu diễn cho mảng, mẩu tin, Biểu diễn liên kết Biểu diễn liên kết là sự biểu diễn, trong đó CTDL được lưu trữ trong nhiều khối ô nhớ tại các vị trí khác nhau trong bộ nhớ, mỗi khối liên kết với khối khác thông qua một con trỏ gọi là con trỏ liên kết. Phương pháp này thường được sử dụng cho các CTDL có kích thước thay đổi. Chẳng hạn có thể dùng biểu diễn liên kết để biểu diễn cho danh sách, ngăn xếp, 32
38. Ngôn ngữ lập trình Chương IV: Kiểu dữ liệu có cấu trúc Bộ mô tả Bộ mô tả Phần tử Phần tử Phần tử Phần tử Phần tử Phần tử Biểu diễn tuần tự Biểu diễn liên kết 4.4.2 Cài đặt các phép toán trên cấu trúc dữ liệu Phép toán lựa chọn một phần tử là phép toán cơ bản nhất trong các phép toán trên CTDL. Như trên đã trình bày, có hai cách lựa chọn là lựa chọn ngẫu nhiên và lựa chọn tuần tự và hai cách biểu diễn bộ nhớ là biểu diễn tuần tự và biêu diễn liên kết. Vì vậy ở đây chúng ta sẽ xét cách thực hiện mỗi một phương pháp lựa chọn với mỗi một phương pháp biểu diễn bộ nhớ. Ðối với biểu diễn tuần tự Như trên đã trình bày, trong cách biểu diễn tuần tự, một khối ô nhớ liên tục sẽ được cấp phát để lưu trữ tòan bộ CTDL. Trong đó, vị trí đầu tiên của khối ô nhớ được gọi là địa chỉ cơ sở. Khoảng cách từ địa chỉ cơ sở đến vị trí của phần tử cần lựa chọn được gọi là độ dời của phần tử. Cách thức truy xuất, được cho bởi tên hoặc chỉ số của phần tử (chẳng hạn chỉ số của một phần tử của mảng), sẽ xác định cách tính độ dời của phần tử như thế nào. Để lựa chọn ngẫu nhiên một phần tử cần phải xác định vị trí thực của phần tử (tức là địa chỉ của ô nhớ lưu trữ phần tử đó) theo công thức: Vị trí thực của phần tử = Ðịa chỉ cơ sở + độ dời của phần tử. Lựa chọn tuần tự một dãy các phần tử của cấu trúc có thể theo các bước: - Ðể chọn phần tử đầu tiên ta dùng cách tính địa chỉ cơ sở cộng với độ dời như đã nói ở trên. 33
39. Ngôn ngữ lập trình Chương IV: Kiểu dữ liệu có cấu trúc - Ðối với các phần tử tiếp theo trong dãy, cộng kích thước của phần tử hiện hành với vị trí của phần tử hiện hành để được vị trí của phần tử kế tiếp. Ðối với biểu diễn liên kết Như trên đã trình bày, các khối ô nhớ trong biểu diễn liên kết được bố trí rời rạc nhau, khối này nối với khối kia bằng con trỏ và lúc đầu chỉ nắm được con trỏ tới khối đầu tiên. Do đó việc đi đến các khối luôn phải xuất phát từ khối đầu tiên. Để lựa chọn ngẫu nhiên một phần tử trong cấu trúc liên kết cần phải duyệt một dãy các khối, từ khối đầu tiên đến khối cần lựa chọn. Lựa chọn tuần tự một dãy các phần tử được thực hiện bằng cách lựa chọn phần tử đầu tiên như đã nói ở trên và sau đó từ phần tử hiện hành, duyệt theo con trỏ để đến phần tử kế tiếp. 4.5 VÉCTƠ 4.5.1 Định nghĩa véctơ Véctơ (còn gọi là mảng một chiều) là một CTDL bao gồm một số cố định các phần tử có kiểu giống nhau được tổ chức thành một dãy tuần tự các phần tử. Như vậy véctơ là một CTDL có kích thước cố định và đồng nhất. 4.5.2 Sự đặc tả và cú pháp Đặc tả thuộc tính của véctơ Các thuộc tính của một véctơ là: - Số lượng các phần tử, luôn được chỉ rõ bằng cách cho tập chỉ số. Tập chỉ số này thông thường được cho bởi một miền con các số nguyên, trong trường hợp đó, số lượng các phần tử bằng số nguyên cuối cùng - số nguyên đầu tiên + 1. Một cách tổng quát thì tập chỉ số có thể là kiểu liệt kê nào đó, trong trường hợp này, số lượng phần tử bằng số giá trị trong kiểu liệt kê. Cũng có những ngôn ngữ chỉ định rõ số lượng các phần tử như ngôn ngữ C chẳng hạn. - Kiểu dữ liệu của mỗi một phần tử, thường được viết rõ trong khai báo. - Chỉ số được sử dụng để lựa chọn mỗi một phần tử. Nếu tập chỉ số được cho bởi một miền con của tập các số nguyên thì số nguyên đầu tiên chỉ định phần tử đầu tiên số nguyên thứ 2 chỉ định phần tử thứ 2 Nếu tập chỉ số là một liệt kê thì giá trị đầu tiên trong liệt kê là chỉ số của phần tử đầu tiên. Nếu ngôn ngữ chỉ định rõ số lượng các phần tử thì 0 là chỉ số của phần tử đầu tiên. Khai báo véctơ trong Pascal là ARRAY [ ] OF . Ví dụ VAR a: ARRAY[1 10] OF real; Khai báo này xác định 1 véctơ a có 10 phân tử là các số real. Các phần tử này được lựa chọn bởi các chỉ số từ 1 đến 10. Miền giá trị của chỉ số không nhất thiết bắt đầu từ 1, ví dụ 34
40. Ngôn ngữ lập trình Chương IV: Kiểu dữ liệu có cấu trúc Var b: ARRAY [-5 10] OF integer; Với khai báo này thì b là một véctơ có 16 phần tử (10 – (-5) + 1 = 16). Các phần tử được lựa chọn nhờ các chỉ số từ -5 đến 10. Miền giá trị của chỉ số không nhất thiết là miền con của số nguyên, nó có thể là một liệt kê bất kỳ (hoặc 1 miền con của một liệt kê). Ví dụ: Type Ngay = (Chu_nhat, Hai, Ba, Tu, Nam, Sau, Bay); var c : ARRAY [Ngay] OF Integer ; Khai báo này xác đinh véctơ c có 7 phần tử là các số integer, các phần tử của c được lựa chọn nhờ các “chỉ số” từ Chu_nhat đến Bay. Khai báo véctơ trong ngôn ngữ C là [ ]. Ví dụ int d[10]; Khai báo này xác định véctơ d có 10 phần tử các số int, các phần tử này được lựa chọn nhờ các chỉ số từ 0 đến 9. Đặc tả các phép toán trên véctơ Các phép toán trên véctơ bao gồm: Phép toán lựa chọn một phần tử của véctơ là phép lấy chỉ số, được viết bằng tên của véctơ theo sau là chỉ số của phần tử được lựa chọn đặt trong cặp dấu []. Như vậy phép lựa chọn một phần tử của véctơ là phép lựa chọn trực tiếp. Ví dụ, với các khai báo trong các ví dụ thuộc phần đặc tả thuộc tính nói trên, Các phần tử của véctơ a được lựa chọn bằng cách viết a[1], a[2], , a[10]. Các phần tử của véctơ b được lựa chọn bằng cách viết b[-5], b[-4], , b[10]. Các phần tử của véctơ c được lựa chọn bằng cách viết c[Chu_nhat], c[Hai], , c[Bay]. Các phần tử của véctơ d được lựa chọn bằng cách viết d[0], d[1], , d[9]. Chỉ số có thể là một hằng hoặc một biến (nói chung là một biểu thức), ví dụ a[i] hay a[i+2]. Nhờ chỉ số là một biểu thức nên việc lập trình trở nên đơn giản hơn nhiều nhờ tính khái quát của chỉ số. Ví dụ để in ra giá trị của 10 phần tử trong véctơ a, thay vì ta phải viết 10 lệnh in các phần tử cụ thể theo kiểu writeln(a[1]); writeln(a[2]); writeln(a[3]); ta chỉ cần viết một lệnh for i:=1 to 10 do writeln(a[i]); Các phép toán khác trên véctơ bao gồm các phép toán tạo và hủy bỏ véctơ, gán hai véctơ cho nhau và các phép toán thực hiện như các phép toán số học trên từng cặp 2 véctơ có cùng kích thước. Chẳng hạn phép cộng 2 véctơ (cộng các phần tử tương ứng). Tùy thuộc vào ngôn ngữ mà các phép toán này có hoặc không có. 4.5.3 Cài đặt một véctơ Biểu diễn bộ nhớ Biểu diễn bộ nhớ tuần tự được sử dụng để biễu diễn cho một véctơ. 35
41. Ngôn ngữ lập trình Chương IV: Kiểu dữ liệu có cấu trúc Mô hình sau minh họa cho sự biểu diễn bộ nhớ của véctơ A : ARRAY[LB UB] OF . Ðịa chỉ cơ sở Véctơ A Kiểu dữ liệu LB Cận dưới của tập chỉ số Bộ mô tả UB Cận trên của tập chỉ số Kiểu phần tử Kiểu dữ liệu của phần tử E Kích thước mỗi phần tử A[LB] A[LB+1] Bộ nhớ cho các phần tử của véctơ A[UB] Khối ô nhớ để lưu trữ một véctơ có hai phần: bộ mô tả và bộ nhớ dành cho các phần tử của véctơ. Trong bộ mô tả lưu trữ kiểu dữ liệu của cấu trúc (véctơ A), cận dưới của tập chỉ số (LB - Lower Bound), cận trên của tập chỉ số (UB - Upper Bound), kiểu dữ liệu của phần tử và kích thước mỗi phần tử (E). Bộ nhớ dành cho các phần tử của véctơ lưu trữ liên tiếp các phần tử, từ phần tử đầu tiên (A[LB]) cho đến phần tử cuối cùng (A[UB]). Do các phần tử có cùng một kiểu nên các ô nhớ dành cho các phần tử có kích thước bằng nahu. Ðịa chỉ của ô nhớ đầu tiên trong khối gọi là địa chỉ cơ sở. Giải thuật thực hiện các phép toán Phép toán lựa chọn một phần tử được thực hiện bằng cách tính vị trí của phần tử cần lựa chọn theo công thức: Vị trí của phần tử thứ i = ∝ + D + (i - LB) * E Trong đó i là chỉ số của phần tử cần lựa chọn, ∝ là địa chỉ cơ sở của khối ô nhớ (địa chỉ word hoặc byte đầu tiên của khối ô nhớ dành cho véctơ) D là kích thước của bộ mô tả, LB là cận dưới của tập chỉ số và E là kích thước của mỗi một đối tượng dữ liệu thành phần (số word hoặc byte cần thiết để lưu trữ một phần tử). Nếu chỉ số là một giá trị của kiểu liệt kê chứ không phải số nguyên thì hiệu i-LB phải được tính toán một cách thích hợp (chẳng hạn sử dụng hiệu của hai số thứ tự tương ứng của i và LB trong liệt kê). Phép gán một véctơ cho một véctơ khác có cùng thuộc tính được thực hiện bằng cách sao chép nội dung trong khối ô nhớ biểu diễn véctơ thứ nhất sang khối ô nhớ biểu diễn véctơ thứ hai. Các phép toán trên toàn bộ véctơ được thực hiện bằng cách sử dụng các vòng lặp xử lý tuần tự các phần tử của véctơ. 4.6 MẢNG NHIỀU CHIỀU Ma trận (mảng hai chiều) được xem như là một véctơ của các véctơ. Một mảng 3 chiều được xem như là một véctơ của các ma trận 36
42. Ngôn ngữ lập trình Chương IV: Kiểu dữ liệu có cấu trúc 4.6.1 Sự đặc tả và cú pháp Đặc tả thuộc tính Mảng nhiều chiều tương tự như véctơ nhưng chỉ có một thuộc tính khác véctơ là mỗi một chiều phải có một tập chỉ số tương ứng. Chẳng hạn khai báo cho một mảng hai chiều có thể đươc viết dưới dạng ARRAY[LB1 UB1, LB2 UB2] OF Trong đó tập chỉ số 1 có các giá trị từ LB1 đến UB1, tập chỉ số 2 có các giá trị từ LB2 đến UB2. Như vậy số lượng các phần tử của mảng hai chiều sẽ là (UB1-LB1+1)*(UB2-LB2+1) Ví dụ sự khai báo của Pascal: M= array [1 3, -1 2] of Integer; Sự khai báo này cho ta thấy mảng M có hai chiều, chiều thứ nhất được xác định bởi tập chỉ số 1 3 và chiều thứ hai được xác định bởi tập chỉ số -1 2. Có thể xem đây là một ma trận có 3 dòng và 4 cột, như vậy sẽ có 12 phần tử, mỗi phần tử có thể lưu trữ một số integer. Đối với các mảng có số chiều nhiều hơn hai thì cách làm cũng tương tự như mảng hai chiều. Đặc tả phép toán Phép lựa chọn một phần tử được thực hiện bằng cách chỉ ra tên mảng và chỉ số của mỗi một chiều. Chẳng hạn để lựa chọn một phân tử của ma trận ta viết tên ma trận, theo sau là cặp chỉ số dòng, cột phân cách nhau bởi dấu phẩy và đặt trong cặp dấu [], ví dụ M[2,0]. Như vậy phép lựa chọn một phần tử của mảng nhiều chiều là phép lựa chọn trực tiếp. 4.6.2 Sự cài đặt Sự biểu diễn bộ nhớ Sự biểu diễn bộ nhớ đối với mảng nhiều chiều tương tự như sự biểu diễn bộ nhớ đối với véctơ. Nghĩa là cũng sử dụng sự biểu diễn tuần tự và khố ô nhớ được chia làm hai phần: bộ mô tả và bộ nhớ cho các phần tử. Bộ mô tả của mảng giống bộ mô tả của véctơ ngoại trừ mỗi một chiều có một cận dưới và cận trên của tập chỉ số của chiều đó. Trong bộ nhớ dành cho các phần tử ta cũng lưu trữ liên tiếp các phần tử theo một trật tự nào đó. Với ma trận, về mặt logic thì ma trận là một bảng gồm m dòng và n côt, mỗi một ô là một phần tử, nhưng bộ nhớ lại chỉ gồm các ô liên tiếp nhau, vì thế ta phải lưu trữ ma trận theo trật tự dòng hoặc theo trật tự cột. Lưu trữ theo trật tự dòng có nghĩa là trong bộ nhớ dành cho các phần tử ta lưu trữ tuần tự các phần tử trong dòng thứ nhất, tiếp đến là các phần tử trong dòng thứ hai cho đên dòng cuối cùng. 37
43. Ngôn ngữ lập trình Chương IV: Kiểu dữ liệu có cấu trúc Lưu trữ theo trật tự cột nghĩa là trong bộ nhớ dành cho các phần tử ta lưu trữ tuần tự các phần tử trong cột thứ nhất, tiếp đến là các phần tử trong cột thứ hai cho đến cột cuối cùng. Chẳng hạn với khai báo M: ARRAY [1 3,-1 2] OF Integer; ta có hình ảnh biểu diễn trong bộ nhớ như các hình sau: Cấu trúc logic của ma trận M Lưu trữ ma trận M theo trật tự dòng M[1,-1] M[1,0] M[1,1] M[1,2] Ma trận M Kiểu dữ liệu M[2,-1] M[2,0] M[2,1] M[2,2] LB1 (= 1) Cận dưới của tập chỉ số thứ nhất M[3,-1] M[3,0] M[3,1] M[3,2] Bộ mô tả UB1 (= 3) Cận trên của tập chỉ số thứ nhất LB2 (= -1) Cận dưới của tập chỉ số thứ hai UB2 (= 2) Cận trên của tập chỉ số thứ hai M[1,-1] M[1,0] Dòng thứ nhất Bộ nhớ cho M[1,1] Các phần tử M[1,2] M[2,-1] Dòng thứ hai M[2,0] M[3,2] Cấu trúc logic của ma trận M Lưu trữ ma trận M theo trật tự cột M[1,-1] M[1,0] M[1,1] M[1,2] Ma trận M Kiểu dữ liệu M[2,-1] M[2,0] M[2,1] M[2,2] LB1 (= 1) Cận dưới của tập chỉ số thứ nhất M[3,-1] M[3,0] M[3,1] M[3,2] Bộ mô tả UB1 (= 3) Cận trên của tập chỉ số thứ nhất LB2 (= -1) Cận dưới của tập chỉ số thứ hai UB2 (= 2) Cận trên của tập chỉ số thứ hai M[1,-1] M[2,-1] Cột thứ nhất Bộ nhớ cho M[3,-1] Các phần tử M[1,0] M[2,0] Cột thứ hai M[3,0] M[3,2] 38
44. Ngôn ngữ lập trình Chương IV: Kiểu dữ liệu có cấu trúc Giải thuật thực hiện phép toán Ðể thực hiện phép toán lựa chọn phần tử, ta sử dụng công thức tính vị trí của phần tử trong bộ nhớ. Với cách lưu trữ theo trật tự dòng của ma trận M, để tính vị trí của M[i,j], đầu tiên ta xác định số dòng cần nhảy qua: (i-LB1) nhân với độ dài của mỗi dòng để xác định vị trí bắt đầu của dòng thứ i và sau đó tìm vị trí thứ J trong dòng này như đối với 1 véctơ. Như vậy, vị trí của phần tử M[i,j] được tính bởi: Vị trí của M [i,j] = ∝ + D + (i-LB1) x S + (j-LB2) x E Trong đó: ∝ là địa chỉ cơ sở. D là độ lớn của bộ mô tả. S là độ lớn của mỗi dòng = (UB2 - LB2 +1) x E. LB1 là cận dưới của chỉ số thứ nhất. LB2,UB2 tương ứng là cận dưới và cận trên của chỉ số thứ hai. Tương tự ta có thể thành lập công thức tính vị trí của phần tử M[i,j] trong trường hợp ma trận M được tổ chức lưu trữ theo trật tự cột. Tổng quát hóa công thức này cho mảng nhiều chiều hơn là một điều đơn giản. 4.7 MẨU TIN 4.7.1 Định nghĩa mẩu tin Mẩu tin là một CTDL bao gồm một số cố định các phần tử có kiểu khác nhau. Như vậy, mẩu tin là một CTDL có kích thước cố định và không đồng nhất. Các phần tử của mẩu tin được gọi là các trường. 4.7.2 Sự đặc tả và cú pháp Đặc tả thuộc tính Các thuộc tính của một mẩu tin phải được chỉ rõ trong phép khai báo, chúng bao gồm: 1. Số lượng các phần tử. 2. Kiểu dữ liệu của các phần tử (Các phần tử có thể có kiểu khác nhau). 3. Mỗi phần tử được cho bởi tên phần tử (tên trường). Cú pháp khai báo mẩu tin của Pascal: Nhan_vien: RECORD Ma: Integer; {Mã nhân viên} Ho_ten: String[25]; Tuoi: Integer; {Tuổi} Luong: Real; {Hệ số lương} END Việc khai báo này đặc tả một mẩu tin có 4 phần tử của các kiểu Integer, Real và String. Mỗi phần tử có một tên: Ma, Ho_ten, Tuoi và Luong. Ðể chọn một phần tử của mẩu tin ta sử dụng tên của phần tử (trường) đó, chẳng hạn trong Pascal, Nhan_vien.Luong là để truy xuất tới phần tử Luong của mẩu tin Nhan_vien. 39
45. Ngôn ngữ lập trình Chương IV: Kiểu dữ liệu có cấu trúc Đặc tả phép toán Lựa chọn một phần tử là phép toán cơ bản cuả mẩu tin. Phép toán này được thực hiện bằng cách chỉ ra tên trực kiện của phần tử. Ví dụ để lựa chọn phần tử thứ 4 của mẩu tin Nhan_vien ta viết: Nhan_vien.Luong. Phép toán lựa chọn một phần tử của mẩu tin là sự lựa chọn trực tiếp. Mặc dù đều là lựa chọn trực tiếp, nhưng có khác biệt so với cách lựa chọn phần tử của véctơ. Điểm khác biệt ở đây là: đối với véctơ, ta có thể sử dụng giá trị của một biểu thức làm chỉ số, chẳng hạn VECTO[i+1], còn đối với mẩu tin thì bắt buộc phải chỉ rõ tên trực kiện, chứ không thể là biểu thức. Ngoài phép toán lựa chọn phần tử, phép gán các mẩu tin có cùng cấu trúc là một phép toán phổ biến được các ngôn ngữ đưa vào. Chẳng hạn Nhan_vien := InputRec trong đó InputRec có các thuộc tính giống hệt Nhan_vien. 4.7.3 Sự cài đặt Biểu diễn bộ nhớ Biểu diễn bộ nhớ tuần tự được sử dụng để lưu trữ một mẩu tin. Một khối liên tục các ô nhớ được dùng để lưu trữ cho một mẩu tin, trong khối đó, mỗi ô biểu diễn cho một trường. Có thể cũng cần sử dụng bộ mô tả riêng cho từng trường để lưu trữ thuộc tính của các trường đó. Do các trường có kiểu khác nhau nên ô nhớ dành cho chúng cũng có kích thước khác nhau. Giải thuật thực hiên phép toán Việc lựa chọn phần tử được thực hiện một cách dễ dàng vì tên trường được biết đến thông qua việc dịch chứ không phải được tính toán thông qua việc thực hiện như đối với véctơ. Việc khai báo mẩu tin còn cho phép xác định kích thước và vị trí của nó trong ô nhớ thông qua việc dịch. Kết quả là độ dời của phần tử bất kỳ có thể được tính thông qua việc dịch. Chẳng hạn với mẩu tin Nhan_vien, các phần tử của nó được lưu trữ trong bộ nhớ như sau: Vị trí của một phần tử bất kỳ được tính một cách dễ ← Ma 22901 dàng. Chẳng hạn Vị trí của Tuoi = α + Kích thước của Ma + Kích Nguyen Van A ← Ho_ten thước của Ho_ten. Trong đó α là địa chỉ cơ sở của khối ô nhớ biểu diễn 20 ← Tuoi cho Nhan_vien. Phép toán gán toàn bộ một mẩu tin cho một mẩu tin 2.18 ← Luong khác có cùng cấu trúc được thực hiện một cách đơn giản là copy nội dung khối ô nhớ biểu diễn cho mẩu tin thứ nhất sang khối ô nhớ biểu diễn cho mẩu tin thứ 2. 40
46. Ngôn ngữ lập trình Chương IV: Kiểu dữ liệu có cấu trúc 4.8 MẨU TIN CÓ CẤU TRÚC THAY ÐỔI 4.8.1 Ðặc tả và khai báo Trước hết ta xét ví dụ sau: Giả sử trong một xí nghiệp có hai loại công nhân là công nhân trong biên chế và công nhân hợp đồng. Ðối với công nhân trong biên chế thì lương sẽ được tính bằng số ngày công * mức lương tối thiểu * hệ số /20, những ngày nghỉ bảo hiểm xã hội, họ được trả lương bảo hiểm xã hội. Ngược lại công nhân hợp đồng chỉ được trả lương bằng số ngày công * đơn giá công nhật và họ không được trả lương bảo hiểm xã hội. Ta thấy, hai loại công nhân này có những thông tin chung là họ tên, số ngày công, tiền lương và loại công nhân (biên chế hay hợp đồng). Mỗi loại công nhân lại có các thông tin riêng. Đối với công nhân trong biên chế, ta cần thêm các thông tin: hệ số lương và số ngày nghỉ bảo hiểm xã hội. Đối với công nhân hợp đồng, ta cần thêm thông tin về đơn giá công nhật. Nếu sử dụng mẩu tin bình thường để lưu trữ thông tin về hai loại công nhân này, ta cần tất cả 7 trường để lưu trữ 4 thông tin chung và 3 thông tin riêng. Khối ô nhớ cần cấp phát phải đủ để lưu trữ cả 7 trường nhưng việc sử dụng khối ô nhớ lại bị dư, do đối với công nhân biên chế ta chỉ cần 6 trường, đối với công nhân hợp đồng ta chỉ cần 5 trường! Đặc tả thuộc tính Ðể giải quyết vấn đề lãng phí bộ nhớ, trong một số ngôn ngữ lập trình có một loại CTDL gọi là mẩu tin có cấu trúc thay đổi. Mỗi một cấu trúc sẽ có một số trường giống nhau cho mọi loại mẩu tin và một số trường khác nhau cho từng loại mẩu tin. Các trường giống nhau gọi là phần chung hay phần tĩnh, các trường khác nhau này gọi là phần động hay phần thay đổi của mẩu tin. Chẳng hạn đối với bài toán nêu trên thì mỗi công nhân được lưu trong một mẩu tin, có các trường thuộc phần chung đó là Ho_Ten, Ngay_Cong, Tien_Luong. Ngoài ra tùy thuộc vào loại công nhân là biên chế hay hợp đồng mà có các trường riêng. Ðối với công nhân trong biên chế ta cần thêm các trường He_So và Nghi_Bhxh để lưu trữ hệ số lương và số ngày nghỉ bảo hiểm xã hội. Ðối với công nhân hợp đồng ta chỉ cần thêm một trường là Gia_Cong_Nhat để lưu trữ giá công nhật cho mỗi người. Khai báo trong Pascal như sau: TYPE loai_cong_nhan = (bien_che,hop_dong); VAR Cong_Nhan : RECORD ho_ten: String[20]; ngay_cong: Real; luong: Real; CASE loai: loai_cong_nhan OF bien_che: (he_so: Real; nghi_bhxh:Real); hop_dong: 41
47. Ngôn ngữ lập trình Chương IV: Kiểu dữ liệu có cấu trúc (gia_cong_nhat: Real); END; Khai báo trên định nghĩa một mẩu tin có cấu trúc thay đổi. Mẩu tin luôn luôn có các trường Ho_Ten, Ngay_Cong, Luong và Loai. Khi giá trị của Loai = "bien_che" thì mẩu tin còn có các trường He_So và Nghi_Bhxh, trong khi đó nếu giá trị của Loai = "hop_dong" thì nó lại có trường Gia_Cong_Nhat. Đặc tả phép toán Phép toán lựa chọn các phần tử của mẩu tin có cấu trúc thay đổi cũng giống như mẩu tin bình thường. Chẳng hạn ta có thể sử dụng Cong_Nhan.Luong, Cong_Nhan.He_So hay Cong_Nhan.Gia_Cong_Nhat. Tuy nhiên các trường thuộc phần động chỉ tồn tại trong một thời điểm nhất định do đó khi chúng ta truy xuất tới một tên trường mà nó không tồn tại thì sẽ bị lỗi. Trường Loai trong ví dụ trên là rất quan trọng vì nó chỉ ra phần động nào của mẩu tin được sử dụng trong quá trình thực hiện chương trình. Người đọc có thể tham khảo ví dụ tương đối hoàn chỉnh viết bằng Pascal. uses crt; Const luong_toi_thieu = 290000; Type Loai_cong_nhan = (bien_che, hop_dong); Cong_nhan = Record ho_ten : String[20]; Ngay_cong : real; luong : real; Case loai: Loai_cong_nhan of bien_che: (He_so, so_ngay_nghi_BHXH : real); hop_dong: (don_gia: real); end; danh_sach_cong_nhan = Array[1 10] of cong_nhan; Var n : integer; ho_so : danh_sach_cong_nhan; {Nhập danh sách công nhân, và các thông tin liên quan đến lao động} Procedure Nhap (var ho_so: danh_sach_cong_nhan; var n: integer); Var i: integer; loaicn : char; Begin write('So cong nhan: '); readln(n); For i:=1 to n do with ho_so[i] do begin Writeln('Cong nhan ',i); Write('Ho va Ten: '); readln(ho_ten); Write('Loai cong nhan: A la bien che, B la hop dong '); 42
48. Ngôn ngữ lập trình Chương IV: Kiểu dữ liệu có cấu trúc readln(loaicn); If Upcase(loaicn) ='A' then loai := bien_che else loai := hop_dong; write('So ngay cong: '); readln(ngay_cong); if loai = bien_che then begin write('He so: '); readln(he_so); write('So ngay nghi bao hiem: '); readln(so_ngay_nghi_BHXH); end else begin write('Don gia hop dong: '); readln(don_gia); end; end; { with Ho_so[i] } end; {nhap} {Tính lương cho từng công nhân, theo công thức của từng loại công nhân} Procedure Tinh_luong (var ho_so: danh_sach_cong_nhan; n: integer); Var i : integer; luong_binh_quan: real; begin for i:=1 to n do with ho_so[i] do begin if loai = bien_che then begin {tính lương của công nhân biên chế} luong_binh_quan := he_so * luong_toi_thieu/20; luong := ngay_cong * luong_binh_quan + so_ngay_nghi_BHXH * luong_binh_quan*0.80; end else {tính lương của công nhân hợp đồng} luong := ngay_cong * don_gia; end; { with Ho_so[i] } end; {Tinh_luong } Procedure In_luong (ho_so: danh_sach_cong_nhan; n: integer); Var i : integer; begin for i:=1 to n do with ho_so[i] do begin Write(ho_ten:25); If loai = bien_che then write('Bien che':10) else write('Hop dong':10); write(ngay_cong:5:1); if loai = bien_che then begin write(he_so:5:1); write(so_ngay_nghi_BHXH:5:1); end else write(don_gia:10:2); writeln(luong:10:2); 43
49. Ngôn ngữ lập trình Chương IV: Kiểu dữ liệu có cấu trúc end; { with Ho_so[i] } end; { In_luong } begin {Chuong trinh chinh} nhap(ho_so,n); tinh_luong(ho_so,n); in_luong(ho_so,n); readln; end. 4.8.2 Cài đặt mẩu tin có cấu trúc thay đổi Biểu diễn bộ nhớ Biểu diễn tuần tự sẽ được sử dụng để biểu diễn cho một mẩu tin có cấu trúc thay đổi. Thông qua việc dịch, tổng bộ nhớ cần để lưu các phần tử của mỗi một phần động được xác định và bộ nhớ được cấp phát đủ để lưu trữ mẩu tin với phần động lớn nhất. Chẳng hạn với mẩu tin cong_nhan ta có mô hình lưu trữ như trong hình vẽ sau: Ho_ten → ← Ho_ten Ngay_cong → ← Ngay_cong Luong → ← Luong Loai → ← Loai He_so → ← Gia_cong_nhat Nghi_bhxh → ← Không sử dụng Công nhân biên chế Công nhân hợp đồng Vì khối ô nhớ đủ lớn để lưu trữ phần động lớn nhất nên có đủ chỗ cho bất kỳ một phần động nào nhưng đối với những phần động nhỏ hơn sẽ không sử dụng tới một số ô nhớ đã được cấp phát. Với mẩu tin có cấu trúc thay đổi, rõ ràng ta đã tiết kiệm được một số ô nhớ so với mẩu tin bình thường. Giải thuật thực hiện phép toán Lựa chọn một phần tử của phần động cũng giống như lựa chọn một phần tử bình thường, qua việc dịch thì độ dời của phần tử được lựa chọn sẽ được tính toán và qua việc thực hiện thì độ dời được cọng vào địa chỉ cơ sở của khối để xác định vị trí của phần tử. 44
50. Ngôn ngữ lập trình Chương IV: Kiểu dữ liệu có cấu trúc 4.9 CHUỖI KÝ TỰ: Chuỗi ký tự là cấu trúc dữ liệu bao gồm một dãy các ký tự. Như vậy, kiểu chuỗi ký tự là một kiểu đồng nhất, còn về kích thước thì có thể cố định hoặc thay đổi tùy theo ngôn ngữ. Kiểu dữ liệu chuỗi ký tự là một kiểu quan trọng mà hầu hết các ngôn ngữ đều có. 4.9.1 Ðặc tả và cú pháp: Đặc tả thuộc tính Tùy ngôn ngữ, có thể có 3 cách đặc tả đối với kiểu chuỗi ký tự: a/ Ðộ dài được khai báo cố định: Chuỗi ký tự có thể có độ dài (kích thước) cố định được khai báo trong chương trình. Mọi giá trị được gán cho đối tượng dữ liệu chuỗi đều có cùng độ dài như vậy. Khi một chuỗi thực được gán cho đối tượng dữ liệu mà độ dài của chuỗi thực khác độ dài được khai báo thì sẽ có sự điều chỉnh độ dài của chuỗi thực bằng cách cắt bớt các ký tự dư hoặc thêm vào các ký tự trắng để có được một chuỗi có độ dài đúng như khai báo. Ðây là kỹ thuật cơ bản được dùng trong COBOL trong đó từ khóa PICTURE được dùng để xác định số lượng ký tự, ví dụ: Last_Name PICTURE X(20) khai báo biến chuỗi ký tự Last_Name chứa một chuỗi 20 ký tự. Trong Pascal (chuẩn) kiểu dữ liệu chuỗi ký tự không có. Thay vào đó kiểu chuổi ký tự được biểu diễn như là một véctơ của các ký tự Last_Name: PACKED ARRAY [1 20] OF Char. b/ Ðộ dài thay đổi trong một giới hạn đã được khai báo: Chuỗi ký tự có thể có độ dài cực đại được khai báo trước trong chương trình nhưng giá trị thực của đối tượng dữ liệu được lưu trữ có thể là chuỗi có độ dài ngắn hơn, thậm chí có thể là chuỗi rỗng. Trong quá trình thực hiện độ dài của giá trị chuỗi của đối tượng dữ liệu có thể thay đổi, nó cũng sẽ bị cắt nếu vượt giới hạn đã khai báo. Ðây là kỹ thuật được dùng trong PL/1 (và cả trong Turbo Pascal). c/ Ðộ dài không giới hạn: Chuỗi ký tự có thể có độ dài bất kỳ và độ dài có thể thay đổi một cách động thông qua quá trình thực hiện. Ðây là kỹ thuật được dùng trong SNOBOL4. Trong ba phương pháp nói trên thì hai phương pháp đầu cho phép cấp phát bộ nhớ cho mỗi một đối tượng dữ liệu chuỗi được xác định tại thời gian dịch. Ðối vơi phương pháp thứ ba thì sử dụng cấp phát bộ nhớ động tại thời gian thực hiện. Các phương pháp khác nhau cũng đòi hỏi các phép toán khác nhau trên chuỗi. Sau đây là một số phép toán chủ yếu. Đặc tả phép toán Trên chuỗi ký tự, thường có các phép toán sau: a/ Phép ghép nối (concatennation) 45