🔙 Quay lại trang tải sách pdf ebook Cấu trúc dữ liệu và thuật toán Ebooks Nhóm Zalo Ck!oÔỖoỐ681 68 G NGHĨA TÝ CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN ■ NGUYÊN ỌC LIỆU I PGS. TS. HOÀNG NGHĨA TÝ CẤU TRÚC Dữ LIỆU■ VÀ THUẬT TOÁN ■ (Tái bản) NHA xuẩt bản xây d ự n g HÀ NỘI-2014 LỜI NÓI Đ Ầ U Cấu trúc dữ liệu và thuật toán là môn học cơ sở ngành của ngành công nghệ thông tin. Chúng ta hãy hình dung một tòa nhủ có phần nền móng, phin tường cột (kết cấu chịu lực) và những phần khác còn lại, nếu plĩần kết cấu chịu lực không vững thì tòa nhà không thể vững được. Môn "Cấu trúc dữ liệu và thuật toán" chính là môn học thuộc phần rường cột, phẩn kết cấu chịu lực đó của tòa nhà "Công nghệ thông tin". Khi học môn học nà) đòi hỏi sinh viên phải có đầu óc tư duy logic toán học để hiểu thuật toáĩ, đồng thời phải có kỹ năng lập trình để diễn đạt sơ đồ thuật toán thành cứu lệnh. Có thể sơ đổ thuật toán vẽ hết cả một trang giấy nhưng chuyển sang lập trình chỉ có vài dòng; có thể sơ đồ thuật toán trình bày theo kiểu kiểm tra điều kiện để riếp tục ngay ở đầu nhưng khi chuyển sang lập trình có thể dùng các câu lệnh có cấu trúc điều khiển lặp với kiểu kiểm tra điều kiện trước hoặc sa u ... Giáo trình "Cấu trúc dữ liệu và thuật toán" này được xuất bản lần đầu năm 2006, do Nhà xuất bản Xây dựng ấn hành. Từ đó đến nay thời lượng cũng như kết cấu môn học đã có nhiều thay đổi. Ớ Trường Đại học Xây dựng từ năm 2009 môn "Cấu trúc dữ liệu và thuật toán" đã được tách thành hai học phần là "Nhập môn Cấu trúc clữ liệu và thuật toán" và "Cấu trúc dữ liệu và thuật toán nâng cao" veri mỗi học phần có 2 tín chỉ. Lý do là vì trong Khoa Công nghệ thông tin có nhiêu chuyên ngành khác nhíiu, có chuyên ngành chỉ cần học một học phần, có chuyên ngành cần phii học cả hai học phần. Dể đáp ứng sự thay đổi trên, trong mấy năm qua tác giả đã biên soạn lụi đê cương chi tiết cho từng học phần và nội dung chương mục tương ứnị, đã viết lại một số chương trình cho một số thuật toán, trình bày lại một số sơ đồ thuật toán (hoán vị ma trận thưa, danh sách liên kết, sắp xếp theo kiểu chèn..), viết thêm một sô' nội dung cho học phần Cấu trúc dữ liệu và thuật toán nâng cao (kiến thức nâng cao về con trỏ, đệ quy, 3 duyệt cây nhị phân, file mỡ, file text, danh sách liên kết, danh sách Hên kết vòng và liên kết đôi...). Với thời lượng 2 tín chỉ, nội dung học phần "Nhập môn Cấu trúc dữ liệu và thuật toán" sẽ được trình bày ở chương 1, chương 2, các mục 3.1, 3.2, 3.3 của chương 3, riêng các mục 3.3 đến 3.8 chỉ dừng ở các kiến thức cơ bản, chương4, chương 5, chương 7 (mục 7.1, 7.2, 7.3), chương 8 (mục 8.1,8 2). Với thời lượng 2 tín chỉ, nội dung học phần "Cấu trúc dữ liệu và thuật toán nâng cao" sẽ à phần mở rộng, nâng cao trong các mục 3.3 đến 3.8 của chương 3, chương 6, chương 7 (mục 7.4, 7.5), chương 8 (mục 8.3), chương 9. Ngoài những phần lý thuyết và chương trình ví dụ, trong tài liệu còn giới thiệu một sô'chương trình tổng hợp, giúp cho bạn đọc tìm hiểu sâu hơn các thuật toán đã trình bày. Đây thực chất là một sô' kết quả của nhiều năm nghiên cứu và giảng dạy công nghệ thông tin cũng như hướng dẫn sinh viên của tác giả: chương trình quàn lý tiền lương được soạn lại trên cơ sở phần mềm tính lương cho Phòng Tài vụ trường ĐHXD những năm 1990, chương trình sơ đồ mạng được viết từ những năm 1980-1981 chạy trên máy tính Minsk-32, chương trình quy hoạch động là diễn giải thuật toán cùa đê tài 'Thiết k ế tối ưu kết cấu mặt đường mềm nhiều lớp" được tiến hành một cách nung nấu kiên trì trong những năm 1975-1977, chương trình quản lý thi trắc nghiệm là một phần của đề tài "Xảy dựng Ngân hàng đề thi và phần mềm phục vụ thi trắc nghiêm môn Tin học đại cương" năm 2001. Quyển sách này được dùng làm giáo trình cho học viên, sinh viên ngành công nghệ thông tin và các ngành khác có học các môn tin học ứng dụng. Tác giả rất cảm ơn sinh viên và đồng nghiệp trong quá trình làm việc, giúp phát sinh ỷ tưởng hoàn thiện giáo trình, tuy đã rất c ố gắng nhưng không thể tránh khỏi thiếu sót. Rất mong nhận được góp ỷ của độc giả đ ể lần tái bàn sau sách được hoàn thiện hơn. Mọi góp ý xin gửi về Bộ môn Công nghệ phần mềm, Khoa Công nghệ thông tin Trường đại học Xây dựng Hà Nội. Tác giả 4 Phẩn I CẤU TRÚC DỮ LIỆU Chương 1 NHẬP MÔN CẤU TRÚC DỮ LIỆU 1.1. KHÁI NIỆM CẤU TRÚC DỬ LIỆU Thuật toán và cấu trúc dữ liệu được coi là môn học cốt lõi của ngành Công nghệ thông tin. Niklaus Wirth - tác giả cuốn "Cấu trúc dữ liệu + Giải thuật = Chương trình" đã phân tích tầm quan trọng của cấu trúc dữ liệu và thuật toán. Chương trình là những mô tả cụ thổ của các thuật toán trừu tượng dựa vào những biểu diễn và cấu trúc dữ liệu đặc biệt. Chương trình và dữ liệu không thể tách rời nhau được. Dữ liệu được xử lý bởi chương trình, cần được tổ chức thành các cấu trúc sao cho nó phản ánh mối quan hệ giữa các mục dữ liệu và cho phép xử lý dữ liệu có hiệu quả. 1.1.1. Dữ liệu ở dạng mã máy và ý nghĩa của chúng Trong máy tính các giá trị dữ liệu được lưu trữ dưới dạng các bit, là các sô' ở hộ đếm nhị phân (0 và 1 ). Các bit được tổ chức thành các nhóm gọi là các Từ máy (word), tức là mỗi word chứa một số cố định các bít. Độ dài của word thay đổi theo loại máy tính (máy 16 bit hay 32 bít). Các Từ máy này được đánh địa chỉ bắt đầu từ 0, vì vậy có thể truy cập vào một word bất kỳ theo địa chỉ của nó. Khi ở dạng một dãy bít, nó có thể biểu diễn nhiều ý nghĩa khác nhau. Trong từng ngôn ngữ lập trình cụ thể, người lập trình sẽ biểu diễn các dãy bít này dưới dạng các cấu trúc xác định, cho phép xử lý và diễn đạt được các dữ liệu. 5 Những khái niệm quan trọng liên quan đến dữ liệu là Kiểu dữ liệu, Cấu trúc dữ liệu, Cấu trúc dữ liệu tĩnh, Cấu trúc dữ liệu động. 1.1.2. Kiểu dữ liệu Các kiểu dữ liệu trong Pascal như integer, real, char, boolean, byte được gọi là kiểu dữ liệu đơn giản vì chúng là các dữ liệu không phân chia được nữa (gọi là các nguyên tử - atom). Tuy vậy chúng có thể được xem là có cấu trúc dữ liệu mà việc cài đặt chúng sử dụng các word như là cấu trúc lưu trữ cùng với các thuật toán để thực hiện những phép tính thích hợp cho từng kiểu. Khái niệm kiểu dữ liệu rất quan trọng, nó xác định tập hợp giá trị mà biến có thể nhận. Mô tả kiểu sẽ quy định loại giá trị của biến và cung cấp cho chương trình dịch nhũng thông tin cần thiết. Tương ứng vói mỗi kiểu, mỗi dãy bít sẽ có một ý nghĩa riêng. Kiểu dữ liệu còn quy định những phép toán có thể thực hiện được đối vói các dữ liệu. Mỗi ngôn ngữ lập trình định nghĩa một tập các kiểu dữ liệu nguyên thuỷ, vô hướng của riêng nó, ví dụ, trong ngôn ngữ Pascal đó là Integer, real, boolean, char; trong ngôn ngữ c đó là Int, float, char... Kiểu dữ liệu có các đặc điểm: + Một kiểu dữ liệu sẽ xác định tập hợp giá trị mà một hằng trị (const) hay một biến sẽ nhận giá trị thuộc miền đó; + Kiểu của một giá trị được chỉ định bởi một hằng trị (const), biến hoặc biểu thức có thể suy ra từ dạng của nó hoặc từ khai báo mà không cần phải tiến hành quá trình tính toán. + Mỗi tác tử hay hàm có biến với kiểu định sẵn và cho ra kết quả cũng có kiểu định sẵn. Nếu một tác tử nhận một số biến có kiểu khác nhau (ví dụ phép cộng + dùng hai số nguyên hay thực) thì kiểu của kết quả được xác định theo quy tắc riêng của ngôn ngữ. Các kiểu integer, real, char, boolean, có thể biểu diễn bời xâu các bít. Sau đây ta xét một số kiểu dữ liệu điển hình trong Pascal. a) D ữ liệu kiểu nguyên - integer Dữ liệu kiểu integer được lưu trữ trong các từ máy. Như vậy độ dài của từ máy giới hạn phạm vi của các sô' nguyên lưu trữ được. Số nguyên lớn 6 nhất lưu trữ được trong một từ máy 8 bit là 27 - 1 = 127, trong từ máy 16 bit là 2 15- 1 = 32767, trong một từ máy 32 bit là 231 - 1 = 2.147.483.647. b) Dữ liệu kiểu thực - Real Một số thực bất kỳ có thể biểu diễn bầng tổng các số với mũ của 2: x= ga,x 2' i = - m trong đó a¡ = 0 hoặc 1. Có hai cách lull số thực: dấu chấm tĩnh (fixed point) và dấu chấm động (floating point). Ví dụ 110.101 (6.625) hay 0.110101 X 23. Số thực dấu chấm động trong ô nhớ được biểu diễn thành 2 thành phần: một phần của từ máy được dùng để lưu trữ một số cố định các bít của phần định trị, phần khác lưu trữ phần mũ. . c) Dữ liệu kiểu ký tự - char Máy lưu trữ dữ liệu kỷ tự dựa trên cơ sỏ gán mã số cho mỗi ký tự. Các ký tự được biểu diễn bằng mã nhị phân, mỗi từ máy 16 bít chia thành hai byte, mỗi byte lưu trữ một ký tự dưới dạng nhị phân. Ký tự được mã hoá theo ASCII (American Standard Code for information Interchange - Bộ mã chuẩn cùa Mỹ dùng để trao đổi thông tin) hay EBCDIC (Extended Binary Code Decimal Interchange Code - Mã BCD mở rộng). Phép toán phổ biến cho các ký tự là SO lựa tuần tự (collating sequence). Vi dụ: kỹ tự A trong bảng mâ ASCII có mã là 65, ký tự B irong bảng mã ASCII có mã là 66. Khi đó phép SO sánh A>B sẽ cho kết quả sai. d) D ữ liệu kiểu logic - Boolean Mỗi giá trị logic được biểu diễn bởi một chữ số ở hệ đếm nhị phân là 0 hoặc 1. Trong các ngôn ngữ thông dụng có 4 phép toán logic là AND, OR, NOT, XOR. Trên đây nhắc lại một số kiểu dữ liệu cơ bản, có trong mọi hệ thống máy tính, trong mọi loại ngôn ngữ lập trình. 7 Việc xác định kiểu dữ liệu là rất quan trọng, nó giải nghĩa cho một xâu bit dữ liệu và xác định các phép toán được sử dụng. Tương ứng với mỗi kiểu dữ liệu chỉ có một số phép toán được áp dụng, ví dụ trong ngôn ngữ Pascal: . Vối kiểu Integer chỉ dùng các phép: +, *, /, A, mod, div Với kiểu Real dùng các phép: +, *, / , A ; Với kiểu Boolean dùng các phép: and, or, not, xor Với kiểu Char dùng các phép: +, concat. 1.1.3. Cấu trúc dữ liệu - Data Structure Định nghĩa: Cấu trúc dữ liệu là cách thức tổ chức dữ liệu trong bộ nhớ máy tính. Trong các loại cấu trúc dữ liệu, người ta phân chia ra cấu trúc đơn giản, cấu trúc phức tạp, cấu trúc tĩnh, cấu trúc động. - Cấu trúc dữ liệu đơn giản: là các kiểu dữ liệu nguyên thuỷ được định nghĩa trong các ngôn ngữ lập trình, ví dụ như Integer, Real, Boolean, Char trong ngôn ngữ Pascal; Int, Float, Char trong ngôn ngữ c. Trong thực tế, có những bài toán mà cách tổ chức dữ liệu đom giản không đáp ứng được, đòi hỏi phải tổ chức phức tạp hơn, ví dụ như một d ã y s ố , m ộ t d a n h sách các d ữ liệ u , V.V'... - Cấu trúc dữ liệu tĩnh: là cách tổ chức mà kích thưốc của các phần tử dữ liệu là cô' định, cấu trúc cũng cố định trong khi chương trình dịch làm việc. Trong ngôn ngữ Pascal, các kiểu array, kiểu dữ liệu liệt kê, hay các kiểu nguyên thuỷ như Integer, Real, ... - Cấu trúc dữ liệu động: là cách tổ chức mà có thể thay đổi cả kích thước và cấu trúc của các dữ liệu. Các dữ liệu động này được sinh ra trong quá trình chương trình thực hiện. Chúng không được thể hiện khi dịch chương trình, và thường được sử dụng con trỏ để tạo ra dữ liệu động. Ngoài các khái niệm trên, để phục vụ cho việc học tập, nghiên cứu và triển khai các ứng dụng, người ta còn chia ra: Cấu trúc dữ liệu tuyến tính, cấu trúc dữ liệu phi tuyến. Những cấu trúc mà khi xử lý được tiến hành ở dạng một dãy liên tục các dữ liệu thì được nhóm gộp vào loại tuyến tính, ví dụ như array, stack, queue, list đcm giản. Những cấu trúc còn lại được gọi chung là phi tuyến. 8 1.2. CÁC MÔ HÌNH D ữ LIỆU Để đảm bảo hiệu quả các quá trình xử lý thông tin cần phải tổ chức dữ liệu cho phù hợp. Mô hình hoá dữ liệu phải phản ánh được thế giới hiện thực một cách tốt nhất và phải cài đặt được trong máy tính. Từ Data (dữ liệu) có xuất xứ từ thuật ngữ "datum" tiếng Hy Lạp có nghĩa là "sự kiện". Tuy nhiên không phải bao giờ dữ liệu cũng tương ứng với một sự kiện cụ thể nào đó, hiện diện trong thế giới thực. Chúng ta gọi dữ liệu là mô tả của một hiên tượng bất kỳ (hay là một ý tưởng) mà đáng giá để biểu diễn nó và xác định nó chính xác. Từ xa xưa con người đã sử dụng nhiều loại phương tiện khác nhau để ghi nhận các sự kiện, ý tưởng: đá, giấy,... thông thường dữ liệu (các sự kiện - Data) và diễn giải nó (ngữ nghĩa - semantic) được ghi cùng nhau vì ngôn ngữ tự nhiên khá tinh tế, phong phú để biểu diễn hiện tượng, sự kiện. Khi ta nói " dung lượng đĩa cứng 40MB" thì ở đây 40 là dữ liệu, còn ngữ nghĩa "dung lượng MB". Trong một sô' trường hợp thì dữ liệu và ngữ nghĩa (semantic) bị tách rời (ví dụ: bảng giờ tàu - diễn giải ở bên trên, còn phía dưới là giờ chạy của các tàu ở các tuyến đường). Trong tin học .thì dữ liệu và ngữ nghĩa càng bị phân tách. Trong bộ nhớ của máy tính điện tử, người ta chỉ làm việc với dữ liệu, không để ý đến ngữ nghĩa, phần ngữ nghĩa của dữ liệu bản thân người lập trình phải ngầm hiểu, lưu giữ ở bộ nhớ riêng. Thường trong chương trình phải ghi chú về ý nghĩa của các loại dữ liệu, thiếu ghi chú này thì dữ liệu chỉ là các dãy bit đơn thuần. Sự linh hoạt của biểu diễn dữ liệu đạt được nhờ hai phương pháp: - Có nhiều cách nhìn khác nhau đối với cùng một đối tượng dữ liệu; - Biểu diễn đồng nhất hoá các dữ liệu khác nhau. Ví dụ: với đối tượng là Con ngưcrì, ta có hai cách tiếp cận: Theo phương pháp thứ nhất: cùng một đối tượng con người, nhung trong danh sách lớp học đó là họ tên sinh viên, trong bài toán xét lên lương đó là họ tên cán bộ công nhân viên, trong quản lý bệnh viện đó là họ tên bệnh nhân... Theo phương pháp thứ hai, ta có thể coi mọi người từ Giám đốc, trưởng phó phòng, đến nhân viên... đều là cán bộ công nhân viên. 9 Đó chính là những lý do dẫn đến cần phải trừu tượng hoá dữ liệu. Phương tiện để biểu diễn dữ liệu gọi là Các mô hình dữ liệu (Data model). Mô hình dữ liệu là phương tiện để trừu tượng hoá dữ liệu, cho khả năng nhìn thấy "rừng" (nội dung thông tin của dữ liệu) chứ khổng chỉ "từng cây riêng rẽ" (các giá trị riêng lẻ của dữ liệu). Mô hình dữ liệu cho khả nãng biểu diễn một phần ngữ nghĩa (sematic) của dữ liệu. Mô hình dữ liệu xác định các quy tắc mà theo đó sẽ cấu trúc hoá dữ liệu. Tập hợp các dữ liệu mà có cấu trúc tương ứng với một sơ đồ dữ liệu nhất định thì gọi là một cơ sở dữ liệu. Những mô hình dữ liệu cơ bản đã được nghiên cứu nhiều là: - Mô hình phân cấp (thứ bậc - Hierarchical Model) - Mô hình mạng lưới (Network Model) - Mô hình quan hộ (Relational Model) - Mô hình đối tượng/quan hệ (Object/Relational Model) - Mô hình hướng đối tượng (Object - Oriented Model - Mô hình nửa cấu trúc (Semistructured Model) - Mô hình hiệp hội (Associative Model) - Mô hình thực thể - thuộc tính - giá trị (Entity - Attibute - Value (EAV) Model) - Mô hình ngữ cảnh (Context Model). Dưói đầy ta sẽ xem xét một số mô hình, thứ tự được trình bày theo mức độ phổ dụng. 1.2.1. Mò hình quan hệ - Relational Model Mô hình dữ liệu quan hê do Edgar F. Codd đề xướng những năm I960. Edgar F. ’Ted" Codd sinh ngày 23 tháng 8 năm 1923 ở Portland, Dorset, nước Anh. Õng tất nghiệp Khoa Toán và Hoá học ở Đại học Exeter, Oxford. Năm 1948 chuyển đến New York làm việc cho Công ty máy tính IBM với tư cách là lập trình viên phần thuật toán. Năm 1952 Ông chuyển đến Ottawa - năm 1962 lại quay về Mỹ và làm hằng Tiến sỹ Khoa học Máy tính à Trường Đại học Michigan ở Ann Arbor. Năm 1964, Õng chuyển đến làm việc ỞTrung tâm nghiên cứu Almadén của Hăng IBM â San Jose California. Những năm 1960, 1970 Ông nghiên cứu lý thuyết vê' cấu trúc dữ liệu. Năm 1970, Ông cho 10 (lă/ìiỊ bài báo nổi tiến í> "Mô hình dữ liệu quan hệ cho các Ngân hàng dữ liệu cỡ lớn - A Relational Model of Data for Large Shared Data Banks". E.F.Codcl có rất nhiều đónq góp cho ngành Công m>hệ thông tin, nhiều hệ quàn trị dữ liệu nổi tiếng hiện nay như Oracle, FoxPro,... đều xuất phát từ lỷ thuyết của Ồng. Người ta đã lấy tên Õng đặt clio một dạng chuẩn dữ liệu: Dạng chuẩn Boyce Coíld. Õng được nhận ẹiải thưởng Turing năm 1981. Ediịar F. Codd mất n íỊày 18 tháng 4 năm 2003 tại Williams Island, Bang Florida, Mỹ, thọ 79 tuổi). Edgar F. Codd Phương tiện duy nhất để cấu trúc hoá dữ liệu trong mô hình quan hệ là quan hệ (Relation). Các quan hệ được hiểu theo ý nghĩa của toán tập hợp và được thể hiện dưới dạng các bảng. Mô hình dữ liệu dựa trên các quan hệ và được biểu diễn bằng các bảng lần đầu tiên được E.F. Codd đề xướng trong tài liệu "A relational model of Data for large shared Data banks". Commun. ACM, 13, p.377-387. Một quan hệ được định nghĩa như sau: Cho các tập hợp D/, D:, D„ (không nhất thiết phải khác nhau), khi đó R là một quan hệ, được cho trên các tập hợp này, nếu R- là một tập hợp các corteges n-địa phương hay đơn giản là tập hợp các corteges mù trong mỗi cortege đó phấn tử thứ nhất thuộc Dị, phần tử thứ hai thuộc Tập hợp DI gọi là các Domen cùa R. Sô'n được gọi là bậc cùa R, sô' lượng corteges lã lực lượng cùa R. Mô hình dữ liệu quan hộ là dạng mô hình bảng - mỗi bảng là một quan hệ. Mờ rộng cơ sở dữ liệu quan hệ là tập hợp các bảng. Các cột của bảng gọi là các thuộc tính, mỗi hàng của bảng tương ứng với một cortege của quan hệ. Để quản lý một cơ sở dữ liệu cần xây dựng một hệ quản trị. Trong các hệ quản trị cơ sở dữ liệu quan hệ, các thuộc tính còn được gọi là các trường - field; các hàng là các bản ghi - record. Ví dụ: Có 5 bảng - hổ sơ thí sinh, báo danh-phách, phachl-dieml, phach2-diem2, phach3-diem3. 11 Hó sơ thí sinh Báo danh phách Sỗ BD Họ tèn Ngày sinh Đối tượng SỐ BD Phachl Phach2 Phach3 Phach1-diem1 Phach2-diem2 Phach3-diem3 Phachl Điểm 1 Phach2 Điểm 2 Phach3 Điểm 3 Mỗi thí sinh có 1 sô' báo danh duy nhất. Mỗi số báo danh chỉ có duy nhất một phách mônl, một phách môn 2, một phách môn 3. Cả 3 số phách của 1 số báo danh không được trùng nhau. Mỗi phách 1 có 1 điểm môn 1, mỗi phách 2 có 1 điểm môn 2, mổi phách 3 có 1 điểm môn 3. Từ các bảng này ta sẽ kết nối và truy xuất ra được kết quả thi tuyển của từng thí sinh, đảm bảo không nhầm lẫn. Các thao tác cơ bản đối với mô hình dữ liệu quan hệ là: - Trích dữ liệu từ quan hệ để tạo một quan hệ mới theo điều kiện - Cập nhật thông tin - Chèn, xóa các trường - Chèn, xóa các bản ghi - Sắp xếp các trường theo một trật tự nào đó - Tìm kiếm thông tin theo các điều k iệ n Hiộn nay, các hệ cơ sở dữ liệu được phổ cập phẩn lớn được thiết kế theo mô hình quan hệ, nổi bật là FOXPRO, ACCESS, ... Các hệ,quản trị đi kèm theo là Visual Foxpro, Visual Basic, các ngôn SQL... 12 1.2.2. Mô hình mạng lưới Trong thực tế, có nhiều bài toán có thể mô phỏng dưới dạng một mô hình có nhiều mối quan hệ ngang dọc kiểu mạng lưới. Năm 1971, Hội nghị về các ngôn ngữ Hệ thống Dữ liệu (The Conference on Data Systems Languages - CONDASYL) đã định nghĩa mô hình mạng lưới. Cơ sờ để mô hình hóa mạng lưới là cấu trúc tập hợp. Một tập hợp bao gồm 1 kiểu bản ghi chủ, 1 tên tập hợp, và 1 kiểu bản ghi thành viên. Kiểu bản ghi thành viên (mức con) có thể tham gia trong nhiều tập hợp, nghĩa là cho phép có nhiều bản ghi ở mức trên (mức cha). Đến lượt mình, bản ghi chủ cũng có thể là bản ghi thành viên hay bản ghi con trong các tập hợp khác. Mô hình dữ liệu kiểu mạng CONDASYL dựa trên lý thuyết tập hợp của Toán học. Hai khái niệm quan trọng ở đây là bản ghi và mối liên hệ. Các kiểu bản ghi dùng để biểu diễn bảng các kiểu đối tượng. Ví dụ: Để xây dựng phần mềm quản lý hệ thống các bệnh viện, ta dùng mô hình mạng lưới để mô tả. Một sơ đồ dữ liệu cấu trúc mạng như sau: 13 Mỗi bản ghi có các trường dữ liệu riêng: - Bệnh viện (mã bệnh viện, chức năng điều trị, địa chì, điện thoại, sô' lượng giường) - Phòng điều trị (mã phòng, chức năng điều trị, số lượng giường) - Người làm việc (sốhiệu, họ tên, chức vụ, ca trực, mức lương) - Bác sĩ (số hiệu, số đăng ký) - Bệnh nhân (số đăng ký, số giường, họ tên, địa chỉ, ngày sinh, nam/nữ, tên bệnh điều trị) - Chẩn đoán (m ã chẩn đoán, kiểu chẩn đoán, mức trầm trọng, và phòng ngừa) - Bệnh viện - phòng xét nghiệm (mã bệnh viện, số liệu phòng xét nghiệm) - Phòng xét nghiệm (số hiệu phòng xét nghiệm, tên gọi, địa chỉ và điện thoại) - Xét nghiệm (mã xét nghiệm, kiểu, ngày ấn định, giờ ấn định, sô phương án, tình trạng) Trong sơ đồ dữ liệu kiểu mạng, có kiểu bản ghi chủ và bản ghi phụ thuộc (thành viên) ví dụ: Bệnh viện là bản ghi chủ và Phòng điều trị - phụ thuộc. Hệ quản trị dữ liệu dạng mạng được cài đặt nổi tiếng là Condasyl Data Base Task Group (DBTG) (1971). 1.2.3. Mô hình phán cấp - thứ bậc (Hierarchical model) Trong mô hình phân cấp dữ liệu được tổ chức dạng cây, cũng là một dạng của mô hình có kiểu đổ thị vối các đỉnh là các bảng. Hệ quản trị dữ liệu dạng phân cấp nổi tiếng nhất là họ IMS (Information Management System/Virtual Storage) khi xây dựng dự án đổ bô lên mặt trăng (Apollo) của Mỹ trong những năm 1960 - 1970. Trong sơ đồ phân cấp, toán đổ cậu trúc là một cây được sắp trật tự (hình 1.1). Hình 1.1 14 - Bệnh viện (mã bệnh viện, tên, địa chỉ, điện thoại, sô giường) - Phòng xét nghiêm (sô hiệu phòng xét nghiệm, tên gọi, địa chỉ, điện thoại) - Phòng điều trị (mã phòng, tên gọi, sô giường) - Nhân viên (sốhiệu nhân viên, họ tên, chức vụ) - Bệnh nhân (sốđủng kỷ, sô'giường, họ tên, địa chi, ngày sinh, nam/nữ, bệnh án) - Bác sỹ (sổliiệu bác sỹ, họ tên, chuyên môn). Trong sơ đổ này có bản ghi cha, bản ghi con. Dữ liệu là 1 dãy các bản ghi, mỗi bản ghi chứa các trường giá trị. Mô hình dữ liệu sẽ tập hợp tất cả các thành phần dữ liệu thành các bản ghi. Các kiểu bản ghi này tương đương các bảng trong mô hình dữ liệu quan hệ, mỗi bản ghi riêng rẽ tương đương 1 dòng trong bảng. Để tạo các quan hệ giữa các kiểu bản ghi, mô hình thứ bậc dùng quan hệ - Cha - Con. 1.2.4. Mỏ hình Đỏi tượng/Quan hệ Đây là một sự mở rộng của các Hộ thống quản trị dữ liệu dạng đối tượng - quan hệ (ORDBMSs), chúng cho phép lưu trữ thêm đối tượng mới vào hệ thống quan hệ trong trung tâm của các hệ thống thông tin hiện đại. Những tiện ích mới này đã cho phép tích hợp việc quản lý các cơ sờ dữ liệu truyền thống, các đối tượng phức tạp như các dãy thời gian, các dữ liệu về vũ trụ, các dữ liệu đa phương tiện như âm thanh, hình ảnh, phim, các applets (là những chương trình viết bằng ngôn ngữ Java mà có thể nhúng vào trang HML). Bằng các phương pháp tổ hợp, đóng gói với các cấu trúc dữ liệu, một máy chủ ORDBMS có thể thực hiện các thao tác xử lý dữ liệu phiíc tạp đối vứi các dữ liệu đa phương tiện hay các đối tượng phức tạp khác. Mô hình đối tượng/quan hệ đã tích hợp các ưu việt của mô hình dữ liệu dạng quan hệ và tính mềm dẻo của mô hình định hướng đối tượng. Kỹ sư thiết kế cơ sờ dữ liệu có thể làm việc với cấu trúc dạng bảng dữ liệu quen thuộc và với ngôn ngữ định nghĩa dữ liệu DDL (Data Definition Language) khi xử lý các khả năng quản lý đối tượng mới. Những ngôn ngữ xử lý ORDBMS là các ngôn ngữ quen thuộc như SQL, các ODBC (Open Data Base Connectivity), JDBC (Java Data Base Connectivity). 15 1.2.5. Mô hình định hướng đôi tượng Hệ Cơ sở dữ liệu định hướng đối tượng OODB (Object-Oriented Data Base) là tổ hợp của hệ thống ngôn ngữ lập trình hướng đối tượng và hệ thống lưu trữ dữ liệu. Sức mạnh của OODB có được nhờ việc ít phải xử lý dữ liệu đang lưu trữ cũng như dữ liệu được truyền đến hay dữ liệu đang xử lý trong các chương trình. Trong Hệ quản trị Cơ sở dữ liệu quan hệ, các cấu trúc dữ liệu phức tạp được trải ra thành các bảng dữ liệu hoặc kết hợp các bảng lại theo cấu trúc bộ nhớ, ngược lại, trong hệ quản trị dữ liệu đối tượng không thực hiện việc lưu trữ hay khôi phục các đối tượng liên kết trong của trang web hay trong mô hình thứ bậc. Với sự sắp xếp 1-1 giữa các đối tượng của ngôn ngữ lập trình hướng đối tượng với các đối tượng của cơ sỏ dữ liệu sẽ có 2 lợi ích hơn SO với các cách lưu trữ khác: nó cho phép thực hiện việc quản lý các đối tượng hoàn hảo hơn, đồng thời nó cho phép quản lý tốt hơn các quan hệ phức tạp giữa các đối tượng. Những tính ưu việt này của hệ quản trị cơ sở dữ liệu hướng đối tượng đã làm cho nó hỗ trợ tích cực hơn cho các phần mềm ứng dụng như phần mềm phân tích rủi ro tài chính của công ty, phần mềm dịch vụ viễn thông, cấu trúc tài liệu WEB, hệ thống tự động hoá thiết kế và sản xuất, v.v... 1.2.6. Mô hình nửa cấu trúc Trong mô hình dữ liệu nửa cấu trúc, thông tin thường được liên kết với một sơ đổ mà nó chỉ tường minh thông qua bản thân dữ liệu, đôi khi còn gọi là "tự mô tả". Trong cơ sở dữ liệu loại này, không có sự phân biệt rõ ràng giữa dữ liệu và sơ đồ, mức độ cấu trúc của dữ liệu phụ thuộc vào phán mém ứng dụng. 1.2.7. Mô hình dữ liệu liên kết Mô hình dữ liệu liên kết chia các vật thể của thế giới thực mà dữ liệu của chúng được ghi dưối 2 dạng: các thực thể - đó là các đối tượng tồn tại một cách rời rạc, độc lập; các mối liên kết - là những thứ tồn tại phụ thuộc vào một hay nhiều vật thể khác. Một cơ sở dữ liệu liên kết bao gồm 2 cấu trúc dữ liệu: - Một tập các phần tử, mỗi phần tử có một tên ký hiệu riêng - ID, một tên và một kiểu. 16 - Một tập các liên kết, mỗi liên kết có một ký hiệu riêng - ID, kèm theo 3 ID thể hiện 3 đối tượng khác là đối tượng nguồn, động từ, đòi tượng đích (kết quả). Một trong 3 ID này cũng có thể là liên kết hay là phần tử. Ngoài các mô hình dữ liệu trên, hiện có thêm 2 mô hình mới là Mô hình Thực thể - Thuộc tính - Giá trị (EAV) và mô hình dữ liệu ngữ cảnh - Context Model). 17 Chương 2 CẤU TRÚC D ữ LIỆU TUYẾN TÍNH 2.1. MẢNG - ARRAYS 2.1.1. Khái niệm mảng Mảng là một dãy các phần tử dữ liệu cùng kiểu, được đặt chung 1 tên mảng và các phần tử được phân biệt bởi các chỉ số. Phép toán cơ bản đối với mảng là truy nhập trực tiếp đến các phần tử của mảng để xử lý, lưu trữ hay đọc ra. Vì vậy mảng phải có một số cố định các phần tử, phải được sắp thứ tự. Truy nhập trực tiếp là đến thẳng phần tử dữ liệu, không theo một tuần tự nào, vì vậy thời gian truy nhập trực tiếp đến một phẩn tử bất kỳ là như nhau. Mảng có tên mảng và danh sách chỉ số. Mảng phải được khai báo ở phần khai báo đầu chương trình. Trong Pascal khai báo mảng có dạng tổng quát như sau: Type = Array[] of ; Vi dụ: Const n = 50; Type mang = array [ 1 ..n] of integer; Var A, B: mang; Từ khai báo mảng, bộ dịch sẽ dành vùng bộ nhó cho mảng kể từ một địa chỉ cơ sở (base address). Gọi cơ sở (A) là địa chỉ cơ sở cho mảng A, khi đó địa chỉ của phần tử thứ a, sẽ là: Cơ sở (A) + (i-1).- Nếu 1 phần tử mảng là 1 số nguyên, lưu trong bộ nhớ bằng một từ máy - word, thì địa chỉ cùa phần tử mảng chính là địa chỉ của từ máy đó. 18 Nếu một mảng số thực, mỗi phần tử được lưu trong hai từ máy thì việc tính địa chỉ đê truy nhập phần tử mảng phải theo công thức: Cơsỏ (B) + (i-1).2 Địa chì Vùng nhớ Phẩn tử của mảng Cơsỏ + 0 Cơsở + 1 + 2 + 3 + 4 + 5 + 6 + 7 ¡31 B2 B3 B4 Tổng quát: nếu mỗi phần từ mảng cần k từ máy thì phần tử thứ i của mảng được bắt đầu ở địa chỉ Cơ sở (B) + (i-1 )k. Trên đây là trường hợp chì số là đoạn con các số nguyên. - K hi cliỉ sô'là kiểu thứ tụ chữ cái: Ví dụ: Type Mang = array ['A'.. 'Z'] of integer; Var M: mang; Chu: char; Mỗi phần tử mảng M được chứa trong một từ máy. Khi đó, xác định phán tứ máng M[chuJ như sau: I = ord (chu) - ord('A')+l Và địa chỉ của M[chu] là: Cơsở (M) + (i-1 ) = Cơ sở (M) + ord(chu) - ord ('A') - Mảng nhiêu chiều: Các ngôn ngữ bậc cao cho phép sử dụng mảng nhiều chiểu. Trong Pascal không giới hạn số chiều của mảng: Array [, , ... ] of 19 Ví dụ: Mô tả kích thước một đối tượng không gian 3 chiều (chẳng hạn các kích thước đồ gỗ: tủ, giường...): KT = array[1..10, 1..10, 1.. 10] of real; 2.1.2. Các trường hợp đặc biệt của mảng a) M ảng của mảng Trong Pascal có thể sử dụng mỗi phần tử mảng lại là một mảng. Ví dụ: Const Cao =10; Dai = 10; Rong = 10; Type mang_cao = array [l..cao] of real; Mang_dai = array[l..dai] of mang_cao; kichthuoc = array [L.rong] of mang_dai; Trong các bài toán thực tế, hay dùng nhất là mảng hai chiều. Dữ liệu của các mảng được lim trữ trong các tử máy (vvord). Trong bộ nhớ máy tính các từ máy được sắp xếp một cách trình tự, tuyến tính, một chiều. Vì vậy chúng ta cần phải biểu diễn được sự tương đương của mảng dữ liệu một chiều trong cấu trúc dữ liệu với mảng 2 chiều của chương trình. Giả sử có mảng: ‘11 a ,2 a 13 a 14 •21 a 22 * 2 3 3 2 4 l3 l a 32 a 3 3 a 34 '41 a 42 a 43 a 44 20 Mảng này được lưu trữ trong bộ nhớ bắt đầu từ địa chỉ coso(A), gọi là Địa chỉ cơ sở của màng, các phần tử được bố trí theo hàng: a ị! ap a13 a14 a->| a34 a4| ... a44. Khi đó, địa chỉ của phần tử đầu của hàng thứ i được xác định theo công thức: Địa chỉ của phần tử aH = coso(A) + (i-1) X 4 Và địa chi của phần tử ay trong hàng này sẽ là: Cosờ (A) + (i-1) X 4 + (j-l) ư u khuyết điểm của mảng: - Ưu điểm: cho phép tạo các danh sách và tìm kiếm dễ dàng: mảng được sắp thứ tự. - Khuyết điểm: khi khai báo mảng, phải chỉ ra kích thưốc tối đa song khi sử dụng có thể dùng không hết, vì vậy sử dụng mảng thường lãng phí một số ô nhớ. b) M ảng là ma trận thua (Sparse matrices) Trong các ngành kỹ thuật, ma trận thưa được sử dụng tương đối phổ biến, nó phù hợp để mô phỏng các bài toán kỹ thuật, đặc biệt trong ngành Xây dựng và Cơ khí. Có nhiều loại ma trận thưa, sau đây ta sẽ xét một số kiểu điển hình. - Kiểu 1. Các phần tử bằng 0 nằm trên đường chéo chính - ta gọi là ma trận tam giác dưới, hoặc các phần tử bằng 0 nằm dưới đưòng chéo chính - ta gọi là ma trận tam giác trên. a u a l2 3 ln a n0 ... . 0 0 a 2 2 ■ a 2 n a 21 &22 0 0 0 0 a 33 • ■ a 3n a 3 l a 32 a 3 3 • • 0 0 0 0 .^ n n a „l a n2 a n3 ^ n n - Kiểu 2. Ma trận băng: Có các băng khác không: ma trận vuông trong đó các phần tử khác không nằm trên băng dựa theo đường chéo chính. 21 - Kiểu 3: Ma trận thưa: Thưa không theo quy luật nào Để xử lý ma trận thưa thường dùng cách sau đây: Nhập theo một bảng có 3 cột và (q+1) hàng, ở đây q là số phần tử khác không. Hàng thứ nhất là m, n, q (số hàng, số cột, số phần tử khác 0 của ma trận ban đầu). Những hàng tiếp theo là vị trí hàng cột của a[i, j] * 0 và giá trị của phần tử a[i, j] (i, j, ): m n q ij a[i.j]*0 Ví dụ: Cho ma trận thưa A có 7 hàng 6 cột, có 9 phần tử khác 0: 1 2 3 4 5 6 1 '23 0 0 0 46 33 2 0 14 8 0 0 0 3 0 0 0 9 0 0 4 0 0 0 0 0 0 5 85 0 0 0 0 0 6 0 0 -37 0 0 0 7 0 5 0 0 0 0 ị 22 Ta nhập theo mảng 10 hàng 3 cột: [1 7 6 9 [2 1 1 23 [3 1 5 46 [4 1 6 33 [5 2 2 14 [6 2 3 8 [7 3 4 9 [8 5 1 85 [9 6 3 -37 [10 7 2 5 c) Các phép toán với ma trận thưa * Hoán vị ma trận: khi hoán vị, ta chuyển hàng thành cột và nguợc lại. b[ij] = a[ji] khi i * j ; b[ij] = a[ji] khi i = j 1 2 3 B[1 6 7 9 B[2 1 1 23 B[3 1 5 85 B[4 2 2 14 B[5 2 7 5 b Íó 3 2 8 B[7 3 6 -37 B[8 4 3 9 B[9 5 1 46 B[10 6 1 33 * Thuật toán hoán vị ma trận thưa: Có thể hoán vị ma trận thưa theo một số cách. - Thuật toán 1: 1. Tìm tất cả các phần tử ở cột 1 cho vào hàng 1. 23 2. Tim tất cả các phần tử ở cột 2 cho vào hàng 2 q. Tiếp tục cho đến hết Như vậy, ta sẽ hoán vị giá trị ở cột 1 (giá trị I) và cột 2 (giá trị J), sau đó sắp xếp lại ma trận theo trật tự tăng dần cột 1 (sắp xếp theo cột). „ Thuật toán 2: Ngay từ đầu ta đã xem xét và sắp xếp luôn trật tự các phần tử của mảng kết quả. Chương trình sau đây thể hiện thuật toán dạng 1 ở trên, program hvmt_thua; var m,n,i,j,k,q:integer; aluu,b:aưay[1..50,1..3] of integer; tg: integer; begin writeln('Nhap ma tran A'); write('So hang(m) :');readln(m); write('So cot (n) :');readln(n); write('So phan tu khac 0 (q) :');readln(q); aluu[ 1,1 ]:=m;aluu[ 1,2]:=n;aluu[ 1,3] :=q; for i:=2 to q+1 do begin write('a]uu[',i,'l]=');readln(aluu[i,l]); write('aluu[',i,'2]= ’);readln(aluu[i,2]); write('aluu[',i,'3= ');readln(aluu[i,3]); end; Writeln(’ hoan vi ma tran :'); Writeln('Doi cot 1 <->2 :'); b[ 1, l]:=n;b[ 1,2] :=m;b[ 1,3] :=q; For i:=2 to q+1 do begin b[i,l] := aluu[i,2]; b[i,2] := aluu[i, 1 ]; 24 b[i,3] := aluu[i,3]; end; Writeln('Sap xep lai ma tran B theo cot 1:'); For i:=2 to q do For j:=i+l to q+1 do If b[i,l] > b[j,l] then For k:=l to 3 do begin tg:=b[i,k]; b[i,k]:=b[j,k]; b[j,k]:=tg end; Writeln('Hien ket qua hoan vi : '); for i:=l to q+1 do begin for j:= l to 3 do write('l ',b[i,j],' I ') ; writeln end; readln; End. * Nhân 2 ma trận thưa: Phép nhân ma trận có thể làm biến đổi tính chất "thưa" cùa ma trận kết quả. - Tích hai ma trận thưa chưa chắc đã là ma trận thưa '1 0 0' '1 1 r '1 1 f 1 0 0 X 0 0 0 = 1 1 1 1 0 0 1 0 0 1 1 1 * Cộng hai ma trận thưa: Phép cộng hai ma trận thưa cũng có thể làm cho ma trận kết quả trở thành ma trận không thưa, tuỳ theo dạng ma trận thưa mà ta xử lý: 25 Ví dụ: Đối với ma trận tam giác trên, khi đưa ra kết quả ta viết: for i:=l to n do for j:= l to n do if abs(i-j) >1 then Cl[i,j] := (ị) else if abs (i-j) <=1 then begin Cl[ij]:=C[ij-(i-2)]; Write(Cl[i,j]:8:2); end; 2.2. NGĂN XẾP - STACKS 2.2.1. Khái niệni Ngăn xếp là một cấu trúc dữ liệu trừu tượng, xử lý theo kiểu vào sau ra trước (last in first out - LIFO) nó là một danh sách hay một dãy bản ghi trong đó mỗi phép toán thêm vào hay bớt đi đều thực hiện ờ một đầu gọi là đỉnh ngăn xếp. Ví dụ kiểu ngăn xếp: 1. Chuyển đổi cơ số 2. Xếp chồng dĩa và lấy ra dùng 3. Gọi và kết thúc các thủ tục Các phép toán cơ bản liên quan đến ngăn xếp là: 1. Create(S) - Tạo s như là stack rỗng; 2. Add(i, S) - Thêm phần tử i vào s và cho stask mói; Stack 3. Delete(S) - Bớt đi phần từ ỏ đỉnh ngăn xếp và tạo stask mới; 4. Top(S) - Tìm và lấy ra phần tử đỉnh ngăn xếp không rỗng 5. IsEmpty(s) - Cho giá trị true nếu s rỗng hay false nếu không rỗng. Xét bài toán đổi một số ở hệ đếm cơ số 10 sang hệ 2 theo cách sử dụng ngăn xếp. 1. Nhập sô' cần dịch đổi, tạo một ngăn xếp rỗng. 2. Khi mà số <> 0 thì làm các việc: a) Tính Số dư: = Số mod 2; 26 b) Nhớ lấy số dư (gửi số dư vào đỉnh ngăn xếp); c) Thay số bằng giá trị phần nguyên của phép chia nguyên của số cho 2 (So: = so div 2). 3. Hiện kết quả: lần lượt hiện các ô nhớ chứa số dư, đi ngược từ cuối đến đầu, sẽ được biểu diễn hệ 2 của sô' thập phân ban đầu. Để làm việc này, trước hết kiểm tra, nếu ngăn xếp không rỗng thì: a) Lấy sô' dư từ đinh ngăn xếp; b) Hiện lên màn hình số dư vừa lấy. Ta có thể biểu diễn theo sơ đổ sau: Phép chia 2 — = 1 2 dư 1 2 Ngăn xếp [ĨỊ đỉnh dưO đỉnh dưO đỉnh dư 1 dinh dư 1 đỉnh stackỊl] stack[2] stack[3] stack[4] stack[5] 27 Cách đơn giản nhất để thể hiện stack là sử dụng mảng 1 chiều, chẳng hạn ký hiệu stack[l..n]. Phần tử đầu tiên (hay là đáy ngăn xếp) là stack[l], phần tử thứ 2 là stack[2], phần tử thứ i là stack[i]. Ta dùng 1 biến top để chỉ phần tử ỏ đỉnh ngăn xếp. 2.2.2. Sử dụng mảng và bản ghi để cài đạt ngăn xếp Theo cách làm trên, khi thêm phần tử ở đỉnh ngăn xếp thì phải dịch chuyển các phần tử ở phía dưối đỉnh xuống 1 vị trí; khi lấy 1 phần tử thì phải dịch chuyển các phần tử lên 1 vị trí, điều này làm mất thời gian. Để khắc phục, ta sẽ lật ngược ngăn xếp, coi phần tử đầu tiên, stack[l] sẽ là đáy ngăn xếp, dùng thêm 1 biến phụ top để lưu phần tử ỏ đỉnh ngăn xếp. Ta sẽ dùng 1 mảng để lưu trữ các phần tử của ngăn xếp. Cách lưu này dẫn đến việc cần sử dụng bản ghi: Kiểu ngăn xếp Top phần tử Max Ngăn xếp Khi đó ta có thể sử dụng ngăn xếp để viết các chương trình với một sô' khai báo như sau: Const n = <1 số nguyên xác định>; Type Kieu_Ptu = <1 kiểu dữ liệu xác định>; Day_NganXep = array[l..n| of Kieu_Ptu; Kieu_NganXep = record Top:0..n; Phantu: Day_NganXep; end; Ví dụ bài toán đổi cơ số 10 sang cơ sô' 2: program doicoso; uses dos; eonst stacklimit=50; 28 type Kieu_Ptu=integer; Day_NganXep=array[l..stacklimit] of Kieu_Ptu; Kieu_NganXep=record top:0..stacklimit; phantu: Day_NganXep; end; var so,sodu:integer; stack:Kieu_NganXep; traloi:char; procedure thietlap(var stack :Kieu_NganXep); begin stack.top := 0 end; function IsEmpty(stack :Kieu_NganXep):boolean; begin IsEmpty := (stack.top = 0) end ; procedure Top(var stack :Kieu_NganXep; var Item: Kieu_Ptu); Begin if IsEmpty(stack) then halt else with stack do begin Item := Phantu[top]; top := top -1 end End; procedure Them(var stack :Kieu_NganXep;Item : Kieu_Ptu); begin if stack.top = stackLimit then halt else with stack do begin top := top + 1; phantu[top] := Item end end; Begin (* chuong trinh chinh *) repeat write('Dua vao so can doi :');readln(so); thietlap(stack); while so <> 0 do begin sodu := so mod 2; them(stack,sodu); so := so div 2 end; writeln('Bieu dien CO so 2 while not IsEmpty(stack) do begin top(stack,sodu); write(sodu:l) end; readln; write('Co lam tiep khong ?(Y/N)');readln(traloi); until not(upcase(traloi)='Y') end. 2.2.3. Thư viện chứa các thao tác cơ bản trên ngăn xếp Để sử dụng các thao tác cơ bản trên ngăn xếp như những hàm mẫu, ta tạo thư viện Stack.tpu như sau: Gõ tệp Stack.pas này và lưu vào thư mục C:\tp\units: UNIT STACK; INTERFACE TYPE StackElement=integer;(* có thể thay đổi*) PointerType=AStackNode; StackNode=record Du_Lieu:StackElement; Next:PointerType; end; StackType= PointerType; Procedure CreateS(Var Stack : StackType); Function EmptyS(Stack : StackType):Boolean; Procedure Pop(Var Stack:StackType;var ItemiStackElement); Procedure Push(Var Stack:StackType; Item:StackElement); IMPLEMENTATION Procedure CreateS(Var Stack : StackType); (*Tạo ngăn xếp rỗng*) Begin Stack := Nil end; Function EmptyS(Stack : StackType):Boolean; Begin EmptyS := (Stack = Nil) end ; Procedure Push(Var Stack:StackType;Item:StackElement); (*Đẩy item vào ngăn xếp*) Var TempPtr :PointerType; Begin New(TempPtr); TempPtrA.Du_Lieu := Item; TempPtrA.Next := Stack; Stack := TempPtr; End; Procedure Pop(Var Stack:StackType; Var Item:StackElement); (* Lấy item ra từ đỉnh ngăn xếp Stack*) Var TempPtr :PointerType; (* TempPtr - con trỏ tạm thời chi đến nút đỉnh Stack *) Begin IF EmptyS(Stack) Then halt Else Begin Item := StackA.Du_Lieu ; TempPtr := Stack; Stack := StackA.Next; Dispose (TempPtr); End ; End(*pop*); END. 31 Sau đó khởi động Turbo Pascal, mở tệp Stack.pas, chọn menu dịch chương trình - Compile. Chú ý chọn Destination => Disk. Kết quả dịch sẽ cho tệp Stack.tpu. 2.3. HÀNG ĐỢI - QUEUE 2.3.1. Khái niệm Trong thực tế ta gặp nhiều trường hợp phải xử lý thông tin theo kiểu phải xếp hàng: xếp hàng chờ giải quyết công văn giấy tờ, xếp hàng vào làm thủ tục ờ Cảng hàng không, xếp hàng mua hàng hoá tại Cửa hàng... Ai đến trước được giải quyết, phục vụ trưóc, ai vào sau được phục vụ sau (First in - First out. FIFO), khác với Stack là vào sau - ra trước (LIFO). Như vậy, Hàng đợi là một danh sách dữ liệu, trong đó các phép chèn, thêm phần tử được thực hiện ở một đầu danh sách (Front), còn các phép xoá được thực hiện ở đầu kia (điểm cuối - Rear). A Đầu (Front) (Head) B c D E Cuối (Rear) (Tail) Các nhiệm vụ tính toán, in ấn được xếp hàng chờ đợi xử lý do hệ điều hành quàn lý là một ví dụ về hàng đại được ắp dụng trong tiến trình xử lý của máy tính. Các phép toán cơ bản khi xử lý hàng đợi là: CreateQ(Q): Khởi tạo hàng đợi; AddQ(i, Q): Thêm phần tử i vào cuối hàng đợi; DeleteQ(Q): Lấy ra khỏi đầu hàng đợi một phần tử; IsEmptyQ(Q): xác định hàng đợi có rỗng không; Front(Q): Cho phần tử đầu hàng đợi. 32 Hàng đợi khá giống ngăn xếp, chúng ta có thể dùng mảng để cài đặt hàng đợi. Ngoài một mảng d[l..n] cần dùng thêm 2 biến fro n t (đầu hàng) và rear (cuối hàng). front luôn chỉ phần tử đầu tiên của hàng đợi mà có thể lấy ra được, còn rear luôn chỉ vị trí cuối cùng, nơi có thể thêm vào một phần tử. 1) front rear Hàng đợi rỗng, mới khởi tạo xong front = rear = 0 2) Đưa công việc J, vào hàng đợi: d[l] front = 0 rear = 1 3) Công việc J2 vào hàng đợi: d[l] d[2] J h J, front = 0Lrear = 2 4) Công việc J3 vào hàng đợi: d[l] d[2] d[3] h h J, J front = 0 L rear = 3 33 5) Công việc J, ra khỏi hàng đợi: h h front = 1 JL rear = vào hàng đợi: 1 J’ h J4L front = 1 rear = 4 7) Công việc Jt ra khỏi hàng đợi: J, front = 2Lrear = 4 Trong cấu trúc này, mỗi lần lấy một công việc ra khỏi hàng đợi là phải dịch sang trái 1 vị trí. Ta có thể mô tả lại cách biểu diễn trên như sau: • • Q[ ] [2] [3] [4] [5] [6] Giải thích front rear 0 0 Màng đợi ròng Khởi tạo Q 0 1 J| h - * Q 0 2 h h j2 -> q 0 3 h h h j3 ^ q 1 3 h h J| ra khỏi Q 1 4 J 2 h h j4 -> q 2 4 h h J2 ra khòi Q 34 Với sơ đổ này ta có thể cài đặt mảng cho hàng đợi như sau: - Thủ tục thiết lập hàng đợi. Procedure CREATEQ(var Q: aưay[l..n] of item ; I n là const] front, rear: 0..n; Begin front: = 0; rear: = 0 end; - Kiểm tra hàng có rỗng không: Function ISEMPTY(Q); Begin ISEMPTY: = ( front = rear); End; - Cho phần tử ở đầu cùa hàng đợi: Procedure FRONT(Q); Begin if ISEMPTY then Halt Else front: = front +1 End; - Thủ tục thêm phẩn tử vào hàng đợi: Procedure ADDQ(item: Kieu_Ptu); Begin if rear = n then Writeln(' Hàng đầy '); rear: = rear +1; QỊrear]: = item; End; - Lấy phần tử ra khỏi hàng đợi: Procedure DELETEQ(var item: Kieu_Ptu); Begin if front = rear then (* Hàng rỗng*) Halt; front: = front +1; Item: = Q[rear]; End; 35 2.3.2. Thư viện hàng đợi Để tạo thư viện Queue.tpu ta cũng làm như đối với Stack. Gõ tệp Queue.pas sau đó lưu vào thư mục C:\tp\units. UNIT QUEUE; NTERFACE TYPE QueueElement=integer;(* có thể thay đổi*) QueuePtr=AQueueNode; QueueNode=record DuJLieu: QueueElement; NextiQueuePtr; end; QueueType= record front,Rear :QueuePtr; end; Procedure CreateQ(Var Queue : QueueType); Function EmptyQ(Queue : QueueTyf)e):Boolean; Procedure AddQ(Var Queue:QueueType;Item:QueueElement); Procedure RemoveQ(Var Queue:QueueType; Var Item:QueueElement); IMPLEMENTATION Procedure CreateQ(Var Queue : QueueType); Begin Queue.Front := Nil; Queue.Rear := Nil; end; Function EmptyQ(Queue : QueueType):Boolean; Begin EmptyQ := (Queue.Front = Nil) and (Queue.Rear = Nil) end ; Procedure AddQ(Var Queue:QueueType;Item:QueueElement); Var Pt :QueuePtr; Begin New(Pt); PtA.Du_Lieu := Item; With Queue Do If EmptyQ(Queue) Then 36 Begin Front := Pt; Rear := Pt End Else Begin RearA.Next := Pt; Rear := Pt end; End; Procedure RemoveQ(Var Queue:QueueType; Var Item:QueueElement); Var Pt :QueuePtr; Begin IF EmptyQ(Queue) Then WritelnC Hang doi rong ') Else WITH Queue DO Begin Item := FrontA.Du_Lieu ; Pt := Front ; IF Front o Rear THEN Front := FrontA.Next Else Begin Front := Nil; Rear := Nil end; Dispose(Pt); End ;(* WITH *) End(*REMOVEQ*); END. Sau đó vào Turbo Pascal, chọn menu dịch - compile, cho tệp kết quả là Queue.tpu, chú ý để Destination là Disk. Chú ý: 1. Trong các thư viện Stack.pas và Queue.Pas có sử dụng các biến con irỏ (P) và biến dông của COI1 trỏ (p*) sí xét ở phần sau. 2. Dùng mảng để lun trữ hàng đợi cũng sẽ gặp trở ngại khi thêm phần tử mói, cả hàng phải dịch chuyển sang phía trái, sang phải, tính lại địa chỉ các phần tử. Ví dụ áp dụng: Dùng các phép toán cơ bản trên hàng đợi và ngăn xếp để viết thủ tục đảo ngược các phần tử của hàng đợi. Bài giải: (* Giả thiết đã tạo 2 thư viện Stack.tpu và Queue.tpu *) Uses STACK,QUEUE; 37 Procedure TaoHangDoi(var Q:QueueType); var i: integer; begin CreateQ(Q); Writeln('Dua vao cac so nguyen While not eoln Do begin read(i);AddQ(Q,i) end; readln; end; Var Q:QueueType; S:StackType; x: Integer; Begin TaoHangDoi(Q); CreateS(S); While not EmptyQ(Q) Do begin RemoveQ(Q.x); Push(S,x) end; While not EmptyS(S) Do begin Pop(S,x);AddQ(Q,x);write(x,'') end; readln; end. 2.4. DANH SÁCH - LIST 2.4.Ỉ. Khái niệm Ngăn xếp và hàng đợi là những trường hợp đặc biệt của danh sách. Một danh sách là 1 dãy hữu hạn (có thể rỗng) các phần tử. Những thao tác đối vói danh sách bao gồm: 1. Tạo một danh sách rỗng 2. Xác định danh sách có rỗng không 3. Duyệt, xử lý các phần tử thuộc danh sách 4. Thêm phẩn tử mới vào danh sách 5. Xoá một phẩn tử từ danh sách Có thể khai báo danh sách như sau: Const Max = ; 38 Type Kieu_Ptu = < kiểu dữ liệu>; DanhSach_Day = array[l..Max] of Kieu_Ptu; Kieu_Dsach = Record Size :0... Max; Phan_tu : DanhSach_Day; End; Var L ist: Kieu_Dsach; Các thao tác 1, 2, 3 đối với danh sách thì đơn giản. Đối với các thao tác chèn xoá các phần tử thì cần thực hiện các thủ tục dịch chuyển các phần tử. - Thủ tục chèn một phần tử (Item) vào sau 1 vị trí xác định ịpos) Procedure Insert(var List: Kieu_Dsach; Item: Kieu_Ptu; pos: integer); Var i: integer; Begin If ListfulI(List) then Halt Else With List Do Begin For i:= size to Pos+1 do Phan_tu [i+1] := Phan_tu[i]; Phan_tu[Pos+l] := Item; size := size +1; End: End; - Thù tục xóa phần tử Procedure Delete(var List: Kieu_Dsach; Pos: integer); (* Xoá Item ở vị trí Pos *) var i:integer; Begin If ListEmpty(List) Then halt Else With List do 39 Begin size :=size-1; For i:= Pos to Size do Phan_tu[i]:= Phan_tu[i+11 end; End; 2.4.2. Ví dụ áp dụng danh sách Ví dụ: Xét bài toán cộng 2 đa thức thưa: A=2aj x' = 5x970 + 12x400 + 7 B = £ b j xj= x l5 + 8x3+ 1 Ta tổ chức dữ liệu như sau: a đầu a cuối b đầu b cuối Hệ số S ố mũ \ 5 12 7 1 8 1 970 400 0 15 3 0 biến free chứa C| = a,x' + bịX1 Để viết chương trình, ta tổ chức đa thức là một mảng các nút, môi nút có 2 trường là hệ sô' - coef - và sô' mũ - exp. Dữ liệu được bố trí trong mảng lần lượt hết đa thức A rồi đến đa thức B. Thêm thông tin về địa chỉ chứa hệ số của số hạng đẩu tiên của đa thức A, hệ số của sô' hạng cuối cùng của đa thức Á, tương tự, hệ số đầu của B, cuối của B, đầu của c, và thêm 1 biến free lưu địa chỉ ô tự do. Chương trình như sau: Const maxterm =100; Type Node = record co e f: integer; exp: 0..maxint; end; varterm : array[l..maxterm] of node; ij,n,free:integer; aB,aE,bB,bE,cB,cE: integer; function compare(a,b : integer): char; begin 40 if a < b then compare := '<’ else if a=b then compare := '=' else compare := ’> '; end; Procedure Newterm(c:integer;hs:integer); label 9999; begin if free > maxterm then begin write(' too many terms '); goto 9999 end; term[free].coef :=c; term[free].exp :=hs; free := free+1; 9999: end; procedure add(aBegin,aEnd,bBegin,bEnd: integer; var cBegin,cEnd: integer); var i,j,free:integer; crinteger; Begin i:=aBegin; j:=bBegin;cBegin:= free; While (i <= aEnd) and (j <= bEnd) do case compare(Term[i].exp,term[j].exp) of '=':begin c:=term[i].coef+term[j].coef; if c <> 0 then Newterm(c,term[i].exp); i:=i+l;j:=j+l end; begin Newieim(ierm|j]xoef,tenii[j].exp); j:=j+l end; '> ': begin Newterm(term[i].coef,teriTi[i].exp); i:=i+l end; end;(* case & while *) { Nếu hết B chỉ còn A (x)} While i <= aEnd Do begin Newterm(term[i].coef,term[i].exp); i:=i+l end; ị Nếu hết A(x) chỉ còn B(x) Ị While j <= bEnd do begin Newterm(term[j].coef,term[j].exp); j:=j+l end; cEnd := free+l; end; (* Chuong trinh chinh *) Begin write('Cho so luong terms );readln(n); for i:=l to n do begin write(' cho cac he SO ');readln(term[i].coef) end; for i:=l to n do begin write(' cho SO mu ',i,':');readln(tenn[i].exp)end; write('nhap aBegin,aEnd,bBegin,bEnd,cBegin,free readln(aB,aE,bB,bE,cB,free); add(aB,aE,bB,bE,cB,cE); writeln('hien ket qua for i:=7 to 11 do write(term[i].coef:4,T);writeln; for i:=7 to 11 do write(term[i].exp:4,T);writeln; readln; end. 2.5. BÀI TẬP 2.5.1. Bài tập về mảng 1. Ma trận tam giác dưới là một ma trận vuông, trong đó các phần từ khác ộ chỉ có thể nằm dưới đường chéo chính và các phần tử của đường chéo chính (tức là A[i, j] = 0 nếu i y2) f(xi. y,) f(x„y„) x 2 f(x2, y,) f(x„ y2) f(x2. yj) f(x2y„) X, f(X|, y ,) f(Xị. y2) f(X ị. yj) f(Xi,y„) xm f(xm, y,) X 3f(xm, yj) f(xm, y„) 43 Yêu cầu viết chương trình để: a) Lưu bảng trên vào 1 tộp trên đĩa từ; b) Khi nhập 1 cặp giá trị (x, y) thì sẽ cho kết quả hàm f(x, y) theo cách tính sau: + Nếu X trùng với X, y trùng với y¡ (i từ 1 đến m, j từ 1 đến n) thì kết quả là: f(x¡, y¡) + Nếu X trùng với Xị và y nằm trong khoảng từ y¡ đến yi+l thì kết quả là: (f(Xị, yj) + f(x¡, yjt,)) / 2 + Nếu y trùng với y¡ và X nằm trong khoảng từ X, đến xi+| thì kết quả là: (f(x¡, y¿) + f(xi+1, yj))/2 + Nếu X nằm trong khoảng từ X; đến xi+| và y nằm trong khoảng từ y¡ đến yi+| thì kết quả là: (f(x¡, y ) + f(x¡, yj+1) + (f(x¡, Y j) + f(x¡+|, yj))/4 6. Viết chương trình kiểm tra một ma trận vuông đã cho trước có phải là: + Ma trân tam giác trên không? + Ma trận tam giác dưới không? + Ma trận 3 vệt không? 2.5.2. Bài tập về ngăn xếp 1. Dùng kiểu dữ liệu ngăn xếp viết chương trình đổi một sô' nguyên cơ số 10 sang cơ sô' 2. 2. Với một số nguyên n >1 cho trước, sô' nguyên nhỏ nhất d (d >1) chia hết bởi n là 1 sô' nguyên tố. Ta có thể tìm được các thừa sô' nguyên tô' của n bằng cách trước hết tìm d rồi thay thế n bởi thương sô' n chia cho d và lặp lại thao tác này cho đến khi n = 1. Dùng kiểu dữ liệu ngăn xếp viết chương trình xác định các thừa sô' nguyên tố này và hiển thị chúng theo thứ tự giảm dần. Ví dụ: n = 3960 sẽ phân tích thành 11x5x3x3x2x2x2. 44 2.5.3. Bài tập về hàng đợi Dùng cho các phép toán cơ bản trên hàng đợi ISEMPTYQ, CREATEQ, ADDQ, REMOVEQ để: 1. Lấy ra các phần tử ỏ cuối hàng đợi nhưng để lại nguyên nội dung hàng đợi; 2. Thêm phần tử vào đầu hàng đợi. 2.5.4. Hài tập về danh sách Ghép nối, hoàn thiện và chạy thử nghiệm chương trình đối với ví dụ đã cho. 45 Chưưng 3 CẤU TRÚC D ữ LIỆU PHI TUYẾN 3.1. BẢN GHI - RECORD 3.1.1. Khái niệm bản ghi Xét bài toán: viết chương trình quản lý sinh viên, thông tin về một sinh viên gồm có: mã số sinh viên, họ tên, ngày sinh, quê quán, kết quả học tập,... những thông tin này có thể có các kiểu dữ liệu khác nhau: mã số là kiểu nguyền - integer hoặc có thể biểu diễn dưới dạng xâu, chuỗi ký tự - string, họ tên thường là chuỗi ký tự - string, ngày sinh có thể là dạng chuỗi hay dạng số nguyên, quề quán - dạng chuỗi ký tự, kết quả học tập - kiểu số thực - real.... Với các dữ liệu không thuần nhất này không thể tổ chức trong một mảng kiểu array. Để xử lý những thông tin dạng này, trong Pascal dùng một kiểu dữ liệu có cấu trúc là record - bàn ghi. Ta có thể định nghĩa record là một phiếu tin về một đối tượng, mỗi record chứa một số thành phần dữ liệu đặc trưng cho đối tượng đó, gọi là các trường, mỗi trường đều có một tên và kiểu dữ liệu riêng. Bản ghi là kiểu dữ liệu phức tạp, không tuyến tính. Bản thân record không có tên. Ví dụ 3.1: Một số đối tượng trong các bài toán quản lý có thể tổ chức dữ liệu theo kiểu bản ghi: - Hồ sơ nhân sự: họ tên, số nhà, tuổi, nghể nghiệp, nơi công tác, lương,...; - Địa chỉ: họ tên, số nhà, phố, quận, thành phô', nước; - Cuốn sách thư viện: tên sách, chuyên ngành, tác giả, năm xuất bản, tập mấy, ký hiệu; - Sinh viên: họ tên, lớp, khoa, khoá, điểm, học bổng. - Thiết bị: mã thiết bị, tên thiết bị, nhãn hiệu, năm sản xuất, nước sản xuất, giá, ngày đưa vào sử dụng, nơi sừ dụng, tình trạng... 46 3.1.2. Khai báo kiểu record Để sử dụng bản ghi trong chương trình, bản ghi phải được khai báo ở phần đầu chương trình. Trong Pascal, bản ghi phải được khai báo kiểu ờ phần khai báo type với từ khoá record, tiếp theo là các tên trường và tên kiểu của chúng, kết thúc bởi từ khoá end. Dạng tổng quát khai báo kiểu record là: Type R = Record :; :; end; Ví dụ 3.2: Viết khai báo record cho một số dữ liệu trong ví dụ 3.1. Type Type hosons = record dia_chi = record hoten: string [25]; hoten: string [25]; tuoi: integer; sonha: string [10]; nghe: (moc, ren, xay, co khi); pho: string [10]; donvi: string [30]; quequan: string [60]; luong: real; thanhpho: string [25]; end; end; Trong những dữ liệu có cấu trúc phức tạp, một bán ghi có thể có nhiêu cảp, nghĩa là trường cùa nó lại là một bản ghi. Ví dụ 3.3: Bản ghi hồ sơ nhân sự có trường Lịch sử lương, mà bản thân no lại là một bản ghi chứa các trường Thâm niên, Ngày lên lương cuối cùng, Mức lương hiện nay, Khen thưởng kỷ luật. Mô tả bản ghi này như sau: Type luong = record thamnien: integer; ngayll: string[8]; 47 mucluong: real; kyluat: integer; end; hosons = record hoten: string [25]; tuoi: integer; donvi: string [30]; lichslg: luong; end; Sau khi khai báo kiểu bản ghi bằng Type, trong phần khai báo biến var những biến nào có kiểu bản ghi tương ứng thì ta khai báo tên kiểu bản ghi đó. Trong trường hợp tổng quát, khai báo kiểu bản ghi có dạng: var v l, v2,..., vN: ; Ví dụ 3.4: Hai biến lylichl, lylich2 có kiểu hosons, khi đó ta khai báo: Var lylichl, lylich2: hosons; 3.1.3. Truy nhập bản ghi Với bản ghi có thể đọc hay viết giá trị - truy nhập các trường của nó. Việc truy nhập bản ghi được thực hiện bời cách viết: cbiến kiểu bản ghi>. Ví dụ 3.5: Tổ chức danh mục chủng loại sản phẩm bê tông theo kiểu record như sau: Type Sanpham = record THUTU: integer; TENSF: string[15]; XIMANG: real; SAT: real; GIASAT: real; GIAXIMANG: real; end; 48 var COTVUONG, ONGNUOC, PANEL: Sanpham; Begin (*Chương trình chính*) COTVUONG.XIMANG : = 0.45; COTVUONG.GIAXIMANG : = 35500.0; COTVUONG.SAT: = 10.72; end; Trong ví dụ này ta dùng phép gán := để đưa giá trị vào các trường của record cotvuong. Cũng có thể đọc dữ liệu vào từ bàn phím cho bản ghi bời lệnh read. Ví dụ 3.6: Đọc dữ liệu vào cho các trường của bản ghi trong ví dụ 3.4: write('Ho va ten:'); readln(LYLICHl.HOTEN); write(Tuoi:'); readln(LYLICHl.TUOI); vvriteOMuc luong:'); readln(LYLICHl.LICHSLG.MUCLUONG); Để ý là trong lệnh: readln(LYLICH 1 .LICHSLG.MUCLUONG); Biến MUCLUONG là một trưòng của bản ghi LICHSLG, mà LICHSLG là một trường của bản ghi LYLICH1. Trong ví dụ 3.4 hai bản ghi lylichl và lylich2 có cùng kiểu bản ghi HOSONS, chúng được gọi là các biến record trùng kiểu. Các biến record trùng kiểu có thể sao chép cho nhau bằng lệnh gán. Đối với hai biến lylichl và lylich2 ta có thể viết: LYLICH1: = LYLICH2; Khi lệnh này thực hiện, từng trưòng của record LYLICH1 được gán giá trị của trường tương ứng của LYLICH2. Ngoài phép gán, hai biến record cùng kiểu còn có thể SO sánh = hoặc <>. Biến bản ghi có thể dùng làm tham số hình thức hay thực sự trong chương trình con. Chúng có thể được tổ chức thành mảng array. 49 Ví dụ 3.7: Khai báo kiểu bản ghi cho bài toán quản lý thiết bị. Type MANGTB = record {mảng thiết b ị) TENVTTB: stringt 15]; {tên vật t thiết bị) NUOCSX: string[ 15]; NGAYNHAP: string[8]; GIATRI: real; DONVISD: string[20]; TINHTRANG: string[15]; end; var OTO, QUATDIEN, ONAP, MAYDHOAI: array[1.. 15] of MANG TB; 3.1.4. Câu lệnh with Truy nhập bản ghi theo cách trên đây phải viết lặp lại nhiều lần tên bản ghi trước mỗi tên trường. Để tránh việc viết lặp lại này, trong PASCAL sử dụng câu lệnh with (với), có cú pháp: Wỉth do Begin ; ; end; Như vậy, tên biên bán ghi chí viết một lấn sau từ khoá with, trong vòng lặp do ... end không cần viết lại nó nữa. V í dụ 3.8: Một bản ghi VATTU có các trường TENVT, NUOCSX, NGAYNHP, giatri, donvisd, tinhtrang, ta sẽ đưa dữ liệu vào từ bàn phím như sau: With VATTU do Begin write('Ten vat tu'); readln (TENVT); write('nuoc san xuat'); readln (NUOCSX); 50 write('Ngay nhap kho'); readln (NGAYNHP); write(’Gia tri'); readln (GIATRI); write('Don vi su dung'); readln (DONVISD); write('Tinh trang'); readln (TINHTRANG); end; Đôi với bàn ghi nhiều thứ bậc: Roi| n i ^11 ^1m câu lệnh with được tổ chức lồng nhau: With R1 do With R2 do With RN do s Đơn giản hơn, ta có thể viết lại các lệnh with lồng nhau dưới dạng: with R l, R2,..., Rn do S; 3.1.5. Bản ghi có cáu trúc thay đổi Cấu trúc của bản ghi là các trường với tên, kiểu dữ liệu và kích thước của trường dữ liệu. Những bản ghi vừa xét trên có cấu trúc cố định, không thay đối. Nếu bản ghi có vài chục trường, mà trong dó chỉ một số trường sử dụng cho một nhóm đối tượng này, một số trường khác cho một nhóm khác, thì tổ chức cố định rất lãng phí bộ nhớ. Chẳng hạn, tổ chức tệp kết quả học tập của sinh viên trong một học kỳ, với nhiều môn học, trong đó: - Ngành cầu: Mố cầu (MC), Nguyên lý thiết kế cầu (NLTKC), Kết cấu thép (KCT), Tin học ứng dụng (TUD), Tiếng Anh (TA), Thi công cầu (TCC). - Ngành Đường: Thiết kế đường (TKD), Sức bền vật liệu (SBVL), Trắc địa (TDIA), Địa chất công trình (DIACHAT), Tin học ứng dụng (TUD), Giáo dục quốc phòng 4 (QP4); 51 - Ngành Xây dựng dân dụng và Công nghiệp: Cơ lý thuyết (CLT), Toán cao cấp (TOAN), Sức bền vật liệu (SBVL), Kết cấu bê tông cốt thép (BTCT), Kỹ thuật thi công (KTTC), Dự toán công trình (DUTOAN), Tin học ứng dụng (TUD); - Ngành kiến trúc: Vẽ kỹ thuật (VKT), Kiến trúc dân dụng (KTDD), Nguyên lý thiết kế kiến trúc (NLTK), Cấu tạo kiến trúc (CTKT), Toán (TOAN), Triết học (TRIET); - Ngành Công trình Thuỷ: Cơ học chất lỏng (CCL), Hình học hoạ hình (HHOA), Toán cao cấp (TOAN), Tin học ứng dụng (TUD), Sức bền vật liệu (SBVL), Kỹ thuật thi công (KTTC); Với cách tổ chức bản ghi có cấu trúc thay đổi hay bản ghi có cấu trúc động, có thể giải quyết được vấn đề phức tạp này. Bản ghi có cấu trúc thay đổi được chia làm hai phần: phần cố định và phần biến đổi. Phần biến đổi chi được là một trường và để ở cuối (tiếng Anh gọi là trường đuôi - tag fied), đặt trong từ khoá case... of. Tùy theo trường hợp (case) trường đuôi nhận giá trị nào thì nó sẽ cấu trúc tương ứng. Dạng tổng quát của bản ghi cấu trúc thay đổi: Type = ; = record I phần cấu trúc cố định Ị case ctrưòng thay đổi> : of : ; end; Trong đó danh sách trường tuỳ thuộc vào giá trị cụ thể trong danh sách kiểu, .dấu ( ) bao danh sách trường là bắt buộc kể cả khi nó rỗng. V í dụ 3.9 Type CLASSE = (CAU, DG, TL, KD, MAY, KT); DSMONHOC = record 52 case MONHOC: CLASSE of CAU: (MC, NLTKC, KCT, TUD, TA, TCC); DG: (TKD, SBVL, TDIA, d ia c h a t , TUD, QP4); XD: (CLT, TOAN, SBVL, BTCT, KTTC, DUTOAN, TUD); KD: (VKT, KTDD, NLTK, CTKT, TOAN, TRIET); CTT: (CCL, HHOA, TOAN, TUD, SBVL, KTTC); end; Trong bản ghi có cấu trúc thay đổi, phần cố định có thể vắng (như trong ví dụ trên) nghĩa là bản ghi chỉ có một trưòng thay đổi. Bản thân trường thay đổi này lại là một bản ghi mà trong đó có thể chứa một bản ghi thay đổi khác. Bản ghi có cấu trúc thay đổi rất tiện lợi, thay vì một bản ghi có chứa vài chục môn học ta chi cần dùng bản ghi biến đổi có số lượng môn học giống như trên thực tế, thường mỗi học kỳ sinh viên học không quá 8 môn. 3.2. KIỂU D ữ LIỆU TỆP 3.2.1. Khái niệm tệp Tệp là một khái niệm quan trọng của Công nghệ thông tin. Tệp là tập hợp các dữ liệu được tổ chức theo một cách xác định. Cần phân biệt tệp chương trình và tệp dữ liệu. Tệp chương trình là tập hợp các câu lệnh tệp, tạo thành một phần mểm, thực hiện các công việc xử lý thông tin, tệp dữ liệu là tập hợp dữ liệu. Trong giáo trình này tìm hiểu cách thức lưu trữ và xử lý tệp dữ liệu. Tộp dữ liệu có cấu trúc thống nhất là tệp được tạo thành từ các bản ghi có cùng cấu trúc, ngoài ra còn có tệp tạo thành từ các bản ghi không cùng cấu trúc. Việc tổ chức tộp và cách truy nhập tệp gắn bó với nhau và được gọi chung là phương pháp truy nhập tệp. Chủ yếu có hai phương pháp truy nhập tệp: tuần tự và trực tiếp. - Truy nhập tuần tự: trong phương pháp này tệp được tổ chức và truy nhập một cách tuẩn tự, thao tác với tệp phải bắt đầu từ đầu tệp, xong phần tử trước mới đến phần tử sau. - Truy nhập trực tiếp hay ngẫu nhiên: là phương pháp thao tác với các phần tử tệp theo địa chỉ bất kỳ, không theo tuần tự. 53 Ví dụ 3.10: Khi xét một danh sách lên lương, theo truy nhập tuần tự thì phải duyệt hết từ đầu đến cuối, theo truy nhập trực tiếp thì ta có thể lúc đầu chỉ duyệt những ngưòi đạt một sô' tiêu chuẩn nào đó, nếu còn chỉ tiêu thì mới xét thêm. Trong Pascal chỉ xét các tệp tuần tự với các phần tử (bản ghi) cùng kiểu dữ liệu. Trong một số cài đặt cụ thể, khác Pascal chuẩn, xét thêm truy nhập trực tiếp. Để nhận biết hết tệp khi xử lý tuần tự, trong Pascal có hàm EOF(f) (End of File - kết thúc tệ p ),/là tên biến tệp; hàm này có giá trị false khi chưa hết tệp, true khi hết tệp. Trong phần này, nói tệp có nghĩa là tệp tuần tự, khi có việc với tệp trực tiếp sẽ nói riêng. Tuỳ theo cách cấu trúc dữ liệu của tệp mà tệp được phân thành các loại: tệp mã, tệp văn bàn và tệp không định kiểu. - Tệp mã: là tệp mà thông tin của nó được lưu dưới dạng mã 0 và 1. Mỗi phần tử của tệp được tự động đánh số thứ tự từ 0 trở đi. Muốn truy cập vào một phần tử nào đó ta có thể duyệt tuần tự đưa cửa sổ đi qua các phần tử trước đó hoặc chuyển thẳng tới sô' thứ tự. Nhò vậy ta có thể sửa chữa nội dung của tệp thuận tiện. - Tệp văn bản: là tệp, dữ liệu được lưu trữ dưới dạng mã ASCII và xếp theo dòng với tín hiệu kết thúc dòng EOLN (End of Line). Độ dài mỗi dòng có thể thay đổi khác nhau. Muốn truy cập vào phần tử nào đó phải tiến hành tuần tự. Muốn ghi hay thêm một phần tử vào tệp ta cần phải đặt cửa sổ vào vị ưí cuối tệp. - Tệp không định kiểu: Jà kiểu tệp đặc biệt được định nghĩa ra trong Turbo Pascal. Trong khi khai báo tệp này người dùng không khai báo kiểu dữ liệu của các thành phần trong tệp. Tệp được tổ chức theo kiểu nào, sẽ có cách khai báo theo kiểu đó. 3.2.2. Khai báo tệp mã Tệp sử dụng trong chương trình phải được khai báo. Có khai báo kiểu tệp và khai báo biến tệp. Khai báo kiểu tệp mã có dạng: Type = file of ; 54 Trong đó kiểu phần tử có thể là integer, real, char, boolean, kiểu liệt kê, kiểu miền con, kiểu record, array, set (tập hợp). Sau phần khai báo kiểu ta khai báo biến var. Var : < tên kiểu tệp>; Ví dụ 3.11: Xét ví dụ tổ chức ba kiểu tệp: kiểu số nguyên, kiểu số thực và kiểu record. Những tệp số điện thoại là tệp kiểu số nguyên, tệp dữ liệu về lương có kiểu số thực, tệp hổ sơ sinh viên có kiểu bản ghi. Type KIEUNGUYEN = file of integer; KIEUTHUC = file of real; BANGHI = file of record HOTEN: string[25]; LOP: string! 10]; DIEM: real; HOCBONG: real; end; Var SODT: KIEUNGUYEN; SOLUONG: KIEUTHUC; HOSOSV: BANGHI; Chú ỷ: Sinh viên cần phân biệt tên biến tệp và tên kiểu tệp. Trong ví dụ trên. SODT. SOLUONG. HOSOSV là tên biến tệp. còn KIEUNGUYEN, KIEUTHUC, BANGHI là tên kiểu tệp. Ví dụ 3.12: Ta có thể tổ chức tệp trong đó các phần tử là mảng aưay và bản ghi record: Type DSLOP = file of record HOTEN = array[1..20] of char; HANHKIEM = char; MON1, MON2, MON3, DTB: real; end (*hết của record*); 55 MUCDTB = file of array [1.. 5] of real; Var K51, K52, K53, K54, K55: DSLOP; MHOCBONG: MUCDTB; TENTEP: string[8]; Trong ví dụ này danh sách lớp của các khoá 51, 52, 53, 54, 55 được tổ chức thành các tệp có kiểu dslop, mỗi phần tử là một bản ghi với các trường hoten, hanhkiem, m onl, mon2, mon3, dtb. 3.2.3. Các thao tác với tệp mã Những thao tác với tệp gồm có: 1. Mở tộp để chuẩn bị ghi dữ liệu lên tệp. 2. Mở tộp để đọc dữ liệu từ tệp. 3. Tiến hành ghi dữ liệu lên tệp. 4. Đọc dữ liệu từ tệp. 5. Đóng tệp. Bao giờ cũng phải đóng tệp ngay sau khi đã xử lý xong phẩn tử cuối cùng của tệp để bảo vệ dữ liệu. Khi đã có tệp trên đĩa từ, mờ tệp này có ý nghĩa là thiết lập sự làm việc giữa chương trình và bộ nhớ ngoài, nơi lưu trữ tệp, cho phép ta làm việc được với tệp (như sao chép, ghi, xoá,..). Đóng tệp là máy sẽ hoàn tất công việc vối tệp, cắt kênh không cho liên hộ với nó nữa. Nếu một tệp chưa có trên dĩa, khi tạo nó lần đầu tiên cũng tương đương với việc mở nó. 3.2.3.1. Thủ tục rewrite - M ở tệp mới đế ghi dữ liệu vào Muốn tạo lập, mở tệp ra ta dùng hai thủ tục Assign và Rewrite. Cú pháp: ASSIGN (, ’ ’); REWRITE (); Trong đó: + Tên biến tệp: là tên biến tộp được khai báo trong phần type và var; + Tên tệp: tên tệp là tên đặt ở thiết bị nhớ ngoài, tên tệp phải để trong cặp nháy đơn và ghi đầy đủ tên đường dẫn thư mục, trong trường hợp 56 không có tên đường dẫn thư mục thì được ngầm hiểu là tệp mới tạo sẽ để trong thư mục chứa chương trình chính của phần mềm, đối với Turo Pascal, thư mục đó là C:\TFNBIN. Thủ tục rewrite sẽ chuẩn bị một tệp để viết dữ liệu vào, nếu tệp đã tồn tại thì sẽ được xoá rỗng trừ dấu hiệu kết thúc tệp EOF. V í dụ 3 .1 3 : Tạo tệp HOSO.DAT để viết dữ liệu vào ở trên ổ đĩa D:\TP, ta viết: Begin write (' Hay go tu ban phim: D:\TP\HOSO.DAT '); readln (TENTEP); assign (K58, TENTEP); rewrite (k58); End; Khi đã khai báo biến tệp, ta đã ngầm hình thành một biến đệm tệp (file buffer variable) và một bộ chỉ định (indicator) ứng với nó. Biến đệm tệp có kiêu cùng kiểu với kiểu phần tử của tệp. Tại mỗi thời điểm chỉ có thể làm việc với một phần tử của tệp, thông qua biến đệm này, bộ chỉ định có chức năng chỉ ra vị trí cùa phần tử tộp. Chúng ta có thể hình dung một tệp T có d ã y các phần tử X, y , z,... với các biến đệm tệp và bộ chỉ định như sau: pt1. pt2.......... X y z .............eof bô ch! đinh (biến đệm tệp) Kết hợp hai chức năng nhó độm và chỉ vị trí, người ta ký hiệu biến đệm là: cbiến đệm tệp> = t Chẳng hạn, biến tệp là HI thi biến đệm tương ứng là H lT, nếu biến tệp là HS thì biến đệm là H st. Khi thủ tục rewrite bắt đầu làm việc, xoá rỗng tệp sẽ chỉ vào ký hiệu kết thúc tệp EOF. 57 3.2.3.2. Thủ tục write - ghi (viết) dữ liệu vào tệp - Cú pháp: Write (, x); - Chức nâng: Viết giá trị biểu thức X vào tệp đã được mở với . Ví dụ 3.14: Một tệp HS trước và sau khi thực hiện thủ tục write có thể hình dung như sau: Trước khi ___ I____ I_______________________________________________I________thực hiện thù tục Viết vào Sau khi V thực hiện Viết vào ____ I___ I_____________________________I I , write(HS, y) V í dụ 3.15: Cho tên tệp GTGT.DAT, kiểu integer. Viết các giá trị n! với n từ 1 đến 15 cho các phần từ tệp. Program giatriGT; Var i, v: integer; T: file of integer; Begin assign (T, 'GTGT.DAT); rewrite (t); V: = 1; for I: = 1 to 15 do begin V: = v*i; write (T, V) end; close (T); End. 3.2.3.3. Đóng tệp - Cú pháp: Close (); 58 - Chức năng: đóng tệp đã làm viộc xong, ở ví dụ trên đã sử dụng lệnh này đóng tệp T. 3.2.3.4. M ỏ tệp đã tổn tại - reset -C ú pháp: ASSIGN (, ’’); RESET (); Khi tệp đã tồn tại, thủ tục reset sẽ thiết lập trạng thái sẩn sàng làm viộc với nó, đưa vị trí đọc về đầu tệp. Ta có thể hình dung tệp T sau khi mở bởi reset: eof T đọc Ví dụ 3.16: assign(t, 'GTGT.DAT); reset(t); Giải thích ví dụ: Mở tệp giai thừa GTGT.DAT để trong thư mục hiện thời của Turbo Pascal. 3.2.3.5. Thủ tục đọc dữ liệu từ tệp - read - Cú pháp: READ (, v); - Chức năng: Sao chép giá trị phần tử hiện thời của tệp cho biến V , sau đó đưa vị trí đọc dịch sang phần tử kế tiếp. Kiểu phần tử của tộp phải trùng vối kiểu của biến V. Ta có thể hình dung tệp T trưóc và sau khi thực hiện read như sau: Trước: T đọc Sau: Î đọc 59 Khi biến V là một danh sách, việc đọc tệp sẽ tiến hành cho đến khi hết tệp hoặc hết danh sách. Dùng điều kiện kiểm tra kết thúc tệp eof ở đây là cần thiết. Các phần tử của tệp được đọc một cách tuần tự, hết phần tử trước mới đến phần tử sau. V í dụ 3 .1 7: program TICH; Var TEPNGUYEN : file of integer; i, j: integer; Begin Assign (TEPNGUYEN, 'TICHSN.DAT); reset (TEPNGUYEN); I: = 1; while not (eof(TEPNGUYEN) and MAXINT > I do Begin read (TEPNGUYEN, J); I: = I*J end; writeln ('TICH = I); Close (TEPNGUYEN); readln end. Trong ví dụ này dùng điều kiện (MAXINT > 1) để dừng tính toán khi i vượt quá khả năng lưu trữ số nguyên trong máy. Người ta phân biệt các tệp ngoài và tệp trong. Tệp ngoài tổn tại độc lập, không phụ thuộc vào chương trình. Chúng có thể được đưa vào chương trình với tư cách là tham số ờ đầu chương trình. Thông thường tộp ngoài để ở đĩa mềm hay đĩa cứng. Tệp được sinh ra và sử dụng trong quá trình chương trình làm việc gọi là tệp trong. Tên của nó có thể xuất hiện ờ đầu chương trình nếu nó có liên hệ với thiết bị ngoại vi. 60 Khi chương trình kết thúc, các tệp trong cũng bị xoá vì vậy chúng còn được gọi là các tệp tạm thời (temporary file) hay các tệp vết (scratch). Thòng thường các tệp trong được sử dụng trong các chương trình con procedure hay function. Đối với các tệp tuần tự trong PASCAL, trong cùng một thời điểm không thể vừa đọc ra vừa viết vào, vì vậy khi xử lý, tối thiểu cần phải tạo ra hai tệp, một để đọc ra, một để viết vào. Ở những thời điểm chạy chương trình khác nhau, có thể thay đổi vai trò của hai tệp này cho nhau. 3.2.3.6. M ột sô thủ tục xử lý tệp mã + Tim vị trí của phần tử tệp. Cú pháp: seek (, N); Trong đó N là số nguyên, chỉ phần tử ờ vị trí N và đưa con trỏ biến đệm tệp về đó để cập nhật. Bằng lệnh seek, ta có thể truy nhập không tuần tự vào một tệp tuần tự. + Đếm số phần tử của tệp. Cú pháp: filesize(); Kết quả sẽ cho một số nguyên dương, khi tệp rỗng sẽ cho kết quả 0. + Xác định vị trí hiện thòi của biến đệm tệp. Cú pháp: filepos(); Kết quả sẽ cho một số nguyên dương, khi tệp rỗng sẽ cho kết quả là 0. + Xoá tệp trên đĩa từ. Cú p/icíp: Erasc(); + Đổi tên tệp Cú pháp: Rename(, ); Thủ tục này sẽ đổi tên tệp cũ tương ứng với tên biến tệp thành tên mới là . không được trùng với tên tệp đã có trong thư mục đang làm việc. + Hàm xoá bỏ chế độ không kiểm tra lỗi khi làm việc với tệp Cú pháp: IORESULT Hàm này không có tham số, kết quả cho một giá trị nguyên bằng 0. 61 3.2.4. Tệp văn bản - TEXT 3.2.4.1. Khái niệm Tệp văn bản là tệp đặc biột trong Pascal, nó chứa các bản ghi có thể có độ dài khác nhau, mỗi bản ghi là một dòng, mỗi dòng có ký tự kết thúc là EOL. Ví dụ 3.18: Nội dung một tệp văn bản đơn giản: HOANG BAC eol AN eol 02/10/75 eol HA NOI 3.2.4.2. Khai báo tệp văn bản Cú pháp: Type = Text; Var : ; Hoặc khai báo trực tiếp: Var : Text; Ví dụ 3.19: a) Type NS = Text; SL = Text; Var b) Var Nhan_su: NS; SoLuong: SL; Nhan_su, SoLuong: Text; 3.2.4.3. Các thao tác với tệp văn bản Những thao tác với tệp Text là write, writeln, read, readln, eoln. Những thủ tục này có thể làm việc với các kiểu dữ liệu đơn giản như char, string, integer, real, boolean. * Ghi dữ liệu vào tệp văn bản Sau khi mở tộp để ghi ra, ta có thể tiến hành ghi dữ liệu lên tệp, mỗi phần tử tệp là một dòng, mỗi dòng có ký hiệu EOL để ngăn cách. 62 Cú pháp câu lệnh đối với tệp văn bản có phần khác với tệp mã: 1. WRITE (, ); 2. WRITELN (, ); 3. WRITELN (); + Thủ tục W RITE (, ); máy sẽ xác định giá trị biểu thức, rồi ghi vào tệp theo trình tự từ trái qua phải. + Thủ tục W RITELN (cbiến tệp>, ); cũng hoạt động giống như Write nhưng sau khi ghi xong giá trị của biểu thức cuới cùng máy đưa thêm dấu hiệu hết dòng (EOL) vào tệp. + Thủ tục W RITELN (cbiến tệp>); Chèn thêm dấu hiệu hết dòng vào tệp. Dấu hiệu hết dòng là một cặp ký tự điểu khiển CR (Catriage Return - quay vé đầu dòng) và LF (Line Feed - nhảy dòng). * Đọc dữ liệu từ tệp văn bàn - Cú pháp: 1. READ (, ); 2. READLN (, ); 3. READLN (); Ớ đây danh sách biến có thể có nhiều biến, chúng được ngăn cách nhau bằng dấu phẩy. Kiểu dữ liệu của các biến không nhất thiết phải giống nhau. + Thủ tục READ (, ); sẽ đọc các giá trị của tệp, rồi gán giá trị đọc được cho các biến đã chỉ ra trong câu lệnh, dọc xong không xuống dòng. + Thủ tục READLN (, ); sẽ đọc các giá trị của tệp, rồi gán kết quả đọc được cho biến trong câu lệnh. Sau khi đọc xong giá trị cho biến cuối cùng, cửa sổ tệp tự động chuyển đến đầu dòng dưới, bỏ qua mọi giá trị còn thừa của dòng đến EOL. + Thủ tục READLN (); đưa cửa sổ tệp sang đầu dòng tiếp theo mà không đọc gì cả. * Hùm kiểm tra kết thúc dòng Cú pháp: eoln(); 63 Hàm này cho kết quả false khi chưa kết thúc dòng. Chú ý: - Với tệp văn bản không thể dùng thủ tục SEEK hoặc hàm F1LESIZE hoặc hàm FILEPOS để tìm vị trí phần tử, đ ể đếm kích thước tệp, để xác đinh vị trí biến đệm tệp. Song, ta có thể dùng các hàm sau: + SEEKEOLN (): Xúc định xem cửa sổ tệp có ở vào vị trí cuối dòng không. Giá trị của hàm là true hoặc false. Trước khi kiểm tra EOLN nó nhảy qua các dấu cách và dấu Tab. + SEEKEOF (): Xúc định xem cửa sô' tệp có à vào vị trí cuối tệp không. Giá trị của hàm lả true hoặc false. Trước khi kiểm tra EOF nó nhảy qua các dấu cách và dấu Tab và dấu cách dòng. Ví dụ 3.20: Program Filetext; Uses crt, dos; Var tepgoc, tepkq: Text; Bien, tiep: char; V, tentep, tepmoi: string[12]; Begin Clrscr; W rite(‘Nhap ten tep goc:’);Readln(teníep); Assign(tepgoc, tentep); Rewrite(tepgoc); Repeat Write(‘Nhap thong tin vao tep goc:’);Readln(v); Writeln(tepgoc, v); Write(‘Co Nhap tiep khong(c/k):’);Readln(tiep); Until upcase(tiep) = ’K’; Close(tepgoc); Write(‘Nhap ten tep goc:’);Readln(tentep); Assign(tepgoc, tentep); Reset(tepgoc); 64 While not eof(tepgoc) do Begin While not eoln(tepgoc) do Begin Read(tepgoc, bien); Writeln(bien:12); End; End; Close(tepgoc); Readln End. V í dụ 3 .2 1: Sử dụng bản ghi và tệp chương trình quản lý vật tư: Program quanly vattu; Type vttb = record Matb:integer; Tentb:string[20]; Nuocsx:string[15]; Namsx: integer; Giatri:real; Soluong: integer; Noisd:string[25]; Tinhtrang:string[10]; End; Mang = array[1..100] of vttb; Var I, j, n, m :integer; Bfile:text; Hstb:mang; Matimánteger; Ten:string] 15]; Procedure nhap; Begin Write(‘Nhap so loai thiet b i: ‘);readln(n); For i: = 1 to n do With hstb[i] do Begin Write(‘Ma thiet bi thu I, ’ : ‘);readln(matb); Write(‘Ten thiet bi thu \ I, ’ : *);readln(tentb); Write(‘Nuoc san x u at: ‘);readln(nsxb); Write(‘Gia tr i: ‘);readln(giatri); Write(‘So luong thiet b i: *);readln(soluong); Write(‘Noi su dung : ‘);readln(nsd); Write(‘Tinh trang : *);readln(tinhtrang); End; Assign(bfile, ’hstb.dat’); Rewrite(bfile); Writeln(bfile, n); For i: = 1 to n do with hstb[i] do Begin Writeln(bfile, matb); Writeln(bfile, tentb); Writeln(bfile, nsx); Writeln(bfile, giatri); Writeln(bfile, soluong); Writeln(bfile, noisd); Writeln(bfile, tinhtrang); End; Close(bfile); End; 66 Procedure ds_vttb; Begin Assign(bfile, ’hstb.dat’); Reset(bfile); Writeln(bfile, n); Writeln(n); For i: = 1 to n do with hstb[i] do Begin Read(bfile, matb); Read(bfile, tentb); Read(bfile, nsx); Read(bfile, giatri); Read(bfile, soluong); Read(bfile, noisd); Read(bfile, tinhtrang); Writeln(matb, tentb, nsx, giatri, soluong, noisd, tinhtrang); End; Close(bfile); Procedure timkiem; Begin W rite(‘Nhap ma thiet bi can tim :’);readln(matb); For i: = 1 to 11 do If hstb[i].matb = matim then With hstbfi] do Begin Writeln(‘ma thiet bimatb); W riteln(‘Ten thiet bi: ‘, tentb); W riteln(‘Nuoc san x u a t:’, nsx); W riteln(‘Gia tri :’, giatri); W riteln(‘So luong :’, soluong); 67 Writeln(‘Noi su dung noisd); W riteln(‘Tinh trang tinhtrang); End; Readln End; Begin ( chương trình chính ) Nhap; Ds_vttb; Timkiem End. 3.3. KIỂU DỬLIỆU TẬP HỢP 3.3.1. Tập hợp và khai báo kiểu tập hợp Trong toán học ta đã biết tập hợp gồm những phần tử có cùng một số tính chất nào đó, ví dụ tập các số tự nhiên, tập các số thực, tập các số nguyên, tập các chữ cái. Một tập không có phẩn tử nào gọi là tập trống, ký hiệu là 0 . Trong Công nghệ thông tin sử dụng tập hợp như là một loại dữ liệu có cấu trúc, được hợp thành từ những phần tử có cùng kiểu dữ liệu vô hướng (integer, char, boolean, liệt kê, byte, miền con) trừ kiểu thực real không đếm được. Sô' lượng phần tử cực đại trong tập hợp tuỳ thuộc vào từng cài đặt cụ thể, ví dụ Turbo Pascal con số đó là 256. Khi sử dụng dữ liệu kiểu tập hợp thì phải định nghĩa kiểu tập hợp cho chúng. Kiểu dữ liệu vô hướng của các phần tử của nó phải được xác định qua khai báo type kiểu dữ liệu tập hợp hoặc khai báo trực tiếp trong phần var. 3.3.1.1. Khai báo kiểu tập hợp Cú pháp: Type = set of ; 68 Khai báo này đã gán cho tên kiểu tập hợp một miền giá trị xác định - là một tập hợp các phần tử, mỗi phần tử có kiểu dữ liệu đã viết trong câu lệnh. Tên kiểu tập hợp này sẽ được dùng trong khai báo biến var. Cũng như các kiểu dữ liệu khác, trong khai báo biến var có thể có khai báo trực tiếp kiểu dữ liệu cho tên biến kiểu tập hợp. 3.3.1.2. V í dụ Ví dụ 3.22: Một số khai báo kiểu tập hợp. Type MAU = (BLUE, BLACK, RED, WHITE); (các màu sắc) NGAY = (HAI, BA, TU, NAM, SAU, BAY); {thứ trong tuần} NGUYEN = set of 0..256; {tập các số nguyên Ị Var p, Q: NGUYEN; WORKDAY : set of NGAY ; ( tập các ngày làm việc I COLOR: set of MAU; {tập các màu sắc Ị CHUSO: set of 0..9; (tập các chữ số) Biểu diễn tập hợp này thiết lập một tập hợp trong PASCAL được thực hiện bằng cách biểu diễn liệt kê hay biểu diễn miển con, đặt trong cặp ngoặc vuông (đừng nhầm với dấu ngoặc vuông trong phần DOS). Ví dụ 3.23: [ ] (tập trống), [...256] (tập các sô' nguyên từ 0, 1,256) [true, false] (tập giá trị logic) [T, 'y', 'x'] (tập hợp các chữ từ i đến n và hai chữ y, x) [XANH, DO, TIM, VANG, TRANG, DEN] (tập các màu). 3.3.2. Các phép toán đối vói dữ liệu kiểu tập hợp Đối với các dữ liệu kiểu tập hợp có các phép toán gán tập hợp, hợp (+), giao (*), hiộu (-) hai tập hợp và các phép tính quan hệ, phép thuộc về (in). Ta lần lượt xét chúng. 69 3.3.2.1. Phép gán Cú pháp: X: = E; Trong đó X là biến kiểu tập hợp, E.là biểu thức tập hợp, các phần tử của E và tập X phải cùng kiểu cơ sở. Ví dụ 3.24: Cho p, Q là biến tập hợp kiểu nguyên từ 0 đến 256 trong ví dụ 3.22, khi đó có thể gán P: = [18..60]; Q: = [50]; Đối với các biến khác: WORKDAY: = [HAI, BA]; COLOR: = [BLACK]; Tập rỗng có thể gán cho mọi biến tập có kiểu vô hướng bất kỳ. 3.3.2.2. Các phép hợp, tuyển (giao), hiệu (+, * , -) Ba phép này giống như trong lý thuyết tập hợp. Nếu A và B là hai tập hợp cùng kiểu thì: A + B là một tập hợp gồm những phần tử thuộc A hoặc thuộc B; A * B là một tập hợp gồm những phần từ thuộc đổng thời A và B; A - B là một tập hợp gồm những phần tử thuộc A nhưng không thuộc B. Ví dụ 3.25: Cho A: = [1, 3, 5, 7, 9, 10]; B: = [2, 4, 6, 8, 10, 20]; Khi đó A + B sẽ là [ 1 ..20]; A * B sẽ là [10]; A - B là [1, 3, 5 ,7 ,9 ], 3.3.2.3. Các phép tính quan hệ Các phép toán quan hệ đối với các tập hợp hay biểu thức tập hợp cho kết quả kiểu boolean. Nếu E là biểu thức tập hợp, A và B là hai tập cùng kiểu thì: E in A cho true nếu E thuộc A, ngược lại là false; A = B cho true nếu A trùng (bằng) B, ngược lại false; A o B cho true nếu hai tập A và B khác nhau, ngược lại false; A< = B cho true nếu A là tập con của B, ngược lại false; A> = B cho true nếu B là tập con của A, ngược lại false. Ví dụ 3.26: Viết chương trình tìm tất cả các số nguyên tố của 100 số tự nhiên đầu tiên. Program SNTO; Const N = 100; Type THOP = set of 2..N. Var NI .NEXT: integer; SNTOl, STN: THOP; Begin STN: = [2..N]; SNTOl: = [1]; NEXT: = 2; While STN <>[ ] do Begin NI := NEXT; While NI < = N do Begin STN: = STN - [Nl]; N l: = NI + NEXT end; SNTOl: = SNTOl + [NEXT]; Repeat NEXT : = NEXT + 1 Until (NEXT in STN) or (NEXT>N) End, (Viết số nguyên tố*) for N 1: = 1 to N do if NI in vSNTOl then write (Nl); writeln end. Sừ dụng kiểu dữ liêu tập hợp rất tiộn lợi khi diễn đạt các mệnh đề tính toán. Trong ví dụ sau đây, thay vì một loạt phép tính kiểm tra xem ký tự đưa vào từ bàn phím có phải là chữ cái không: If (KT = 'A') or (KT = 'B') or.... or (KT = 'Z') then ; Ta chỉ cần viết: If KT in 'A'..'Z' then ; 71 Ví dụ 3.27: Program nhapDat; Var KT : char; Error: boolean; X: set of Begin write ('Dua vao ky tu:'); readln (KT); Repeat Error: = false; If not (KT in X) then Error: = true; Write ('Dua vao ky tu:'); readln (KT); While K T o " do Begin if not (KT in ['A'-.'Z', ’O'..'9']) Then Error: = true; Write ( Dua vao ky tu:1); readln (KT); End; Writeln; If Eưor then writeln ('Vao sai'); Write ('Nhap vao ky tu:'); readln (KT) Until KT = ” End. 3.4. CON TRỎ VÀ CẤU TRÚC DỮLIỆU ĐỘNG 3.4.1. Khái niệm Dùng con trỏ với các thủ tục new, dispose sẽ cho khả năng cấp phát và giải phóng các vùng nhớ cho các biến trong khi thực hiện chương trình, không cần giới hạn kích thưóc của vùng lưu trữ. Những dữ liệu được xác định trước bởi khai báo tên trong chương trình và tổn tại trong suốt quá trình chương trình thực hiện gọi là dữ liệu tình. Dữ liệu mà có thể được sinh ra và mất đi trong quá tnnh thực hiện chương trình gọi là dữ liệu động. Việc truy nhập dữ liệu động phải thông qua một biến con trỏ, trỏ tới bộ nhớ của biến động (dynamic variable). Ở mỗi thời điểm tính toán, sẽ có một vùng nhớ nào đó liên kết với biến động này, ngược lại đối với 72 biến tĩnh, vùng nhớ liên kết với nó được cấp phát khi dịch chương trình và cố định trong quá trình thực hiện chương trình. Ký hiệu p là biến kiểu con trỏ, p* sẽ là biến động, chứa giá trị dữ liệu ờ vùng nhớ mà con trỏ p chỉ đến. Chúng ta có thể mô tả con trỏ như sau: Bộ nhớ: Con trỏ p 1000 1001 1002 1000 Trong sơ đổ trên, con trỏ p có giá trị là 1000 - là địa chỉ của ô nhớ mà chứa nội dung của biến động PA. Trong thực tế chúng ta ít quan tâm đến địa chỉ thực của con trỏ p (trong ví dụ trên, là địa chỉ ô nhớ có giá trị 1000) mà chỉ là nội dung của nó, tức là địa chỉ của biến động PA (tó giá trị 1000). Khi con trỏ chưa được định nghĩa hay rỗng thì biến động PA là chưa được xác định. Đối vói con trỏ có thể thực hiện các phép gán và các phép SO sánh =, < >. Phép so sánh =, < > dùng để SO sánh hai con trỏ xem chúng có trỏ đến cùng một địa chỉ hay không hoặc chúng có rỗng hay không. Các phép SO sánh sau là hợp lộ: P1 = P2; P l o N i l ; - Đối với biến động PA Phép gán là gán nội dung dữ liệu: P1A : = P2A; 73 — P1A — * p2A Việc tạo ra biến động cũng như xoá nó đi để giải phóng bộ nhớ được tiến hành nhờ các thủ tục NEW và DISPOSE đã có sẵn của Turbo Pascal. Để truy nhập vào các biến động, được tiến hành nhờ có các biến con trỏ (Pointer Variable). Các biến con trỏ được định nghĩa giống như các biến tĩnh trong phần khai báo ở đầu chương trình. Nó sẽ được dùng để chứa địa chỉ của các biến động. 3.4.2. Khai báo con trỏ, biến động 3.4.2.1. Khai báo con trỏ Kiểu con trỏ là một kiểu trỏ đến (chỉ đến) một vùng chứa dữ liệu của các biến động, các biến này có thể có các kiểu dữ liệu như đã học như Integer, Real, Char, Boolean, String, Array, Record... Để phân biệt vói kiểu dữ liệu tĩnh, kiểu con trỏ có dấu A đúng trưóc. Ví dụ: AInteger, AReal, AChar, ABoolean, AString, AArray, ARecord... Giống như các kiểu dữ liệu đã xét, trong chương trình nếu có sử dụng kiểu con trỏ, nó phải được khai báo như các kiểu dữ liệu khác bằng lệnh TYPE như sau: TYPE = A; VAR ; Trong đó: - Tên kiểu con trỏ: là tên được đặt theo qui tắc đặt tên của ngôn ngữ Pascal. - Kiểu dữ liệu: là một trong các kiểu dữ liệu như Integer, Real, Char, Boolean, R ecord... - Dấu A : đứng trước kiểu dữ liệu để chỉ đó là kiểu con trỏ. Ví dụ: Cần khai báo 4 kiểu con trỏ có tên là IntPtr, CharPtr, RecPtr và DcPtr: 74 Type IntPtr = AInteger; CharPtr = AChar; RecPtr = ARecord Hoten : String[25]; HSLuong:Real; NamCongtac:Integer End; DcPtr = ADiaChi; (Kiểu DiaChi được khai báo sau Ị DiaChi = Record SoNha: String[10]; DuongPho: String[25]; ThanhPho: String[15| End; Var a, b: IntPtr; c, d: CharPtr; e, f: RecPtr; g, h: DcPtr; Chú ýĩ Turbo Pascal cho phép khai báo kiểu con trỏ trước khi khai báo kiểu của dữ liệu hoặc kiểu của biến động (Xem ví dụ trên DcPtr). * Có thể khai háo trực tiếp: V ar a, b: "Integer; c, d: AChar; E, f: ARecord Hoten : String[25]; HSLuong:Real; NamCongtac:Integer End; G, h: ADiaChi; |Con trỏ khai báo trước khai báo DiaChi Ị DiaChi = Record 75 SoNha: StringPO]; DuongPho: String[25]; ThanhPho: String[15] End; 3.4.2.2. Biến động và truy nhập biến động Cho p là biến kiểu con trỏ, p7' sẽ là biến động. Để truy cập vào một biến động có địa chỉ nằm trong biến con trỏ ta dùng dấu A đứng liền sau tên của biến con trỏ. Ví dụ: aA, bA, CA, dA, eA, fA, gA và hA. Thông qua khai báo, chương trình dịch sẽ cấp phát vùng nhớ cho các biến con trỏ để truy nhập vào biến động ở ví dụ trên như sau: - Biến con trỏ a, b chứa địa chi của biến động aA, 0a; là các vùng nhó chứa số nguyên. - Biến con trỏ c, d sẽ chứa địa chỉ của biến động CA, dA; là các vùng nhớ chứa ký tự. - Biến con trỏ e, f sẽ chứa địa chỉ của biến động eA, fA; là các vùng nhớ chứa dữ liệu kiểu bản ghi. - Biến con trỏ g, h sẽ chứa địa chỉ của biến động gA, hA. Đó là các vùng nhớ chứa dữ liệu kiểu bản ghi. * Chú ỷ: Để truy nhập vào biến con trỏ kiểu mảng ta phải viết dấu A sau tên biến mảng nhưng trước chỉ số, ví dụ: aA[i]. Ngược lại, để truy nhập đến mảng các con trỏ ta phải viết dấu A sau chỉ số, ví dụ: b[i]A. (Xem ví dụ phần sau). 3.4.2.3. Cấp phát vùng nhớ cho con trỏ Trước khi muốn truy cập đến một biến động, ta phải tiến hành cấp phát vùng nhớ cho con trỏ của nó bằng thủ tục NEW như sau: - Cú pháp: NEW(p); Với p là con trỏ. - Tác dụng: Nhờ có lệnh trên, chương trình sẽ tạo ra một vùng nhớ có kiểu và kích thước tuỳ theo kiểu và kích thước đã khai báo của p. Sau đó ta mới có thể truy cập vào biến động bằng cách kèm theo dấu A sau biến. Nếu trong một chương trình ta dùng n lần New(p) liên tiếp, thì máy sẽ tạo ra n con trỏ có cùng một kiểu. Khi đó, con trỏ p luôn trỏ tới biến động PA. -V í dụ: Xem ví dụ ờ phần dưới. 76 3.4.2.4. Giải phóng vùng nhớ của con trỏ -Tác dụng: Sau khi làm việc xong, một con trỏ không được dùng tới nữa, ta có thể giải phóng nó để thu hồi lại ô nhó nó chiếm dụng dành cho công việc khác. Muốn vậy ta phải dùng thủ tục DISPOSE như sau: - Cú pháp: DISPOSE(p); với p là con trỏ. -V í dụ: Xem ví dụ ở phần dưới. 3.4.3. Các thao tác đòi vói biến con trỏ 3.4.3.1. Phép gán (: = ) -V í dụ: Var pl, p2 : AInteger; Begin P1: = P2; Lệnh gán này sẽ làm cho hai con trỏ P1 và P2 cùng chỉ đến một vùng chứa dữ liệu: Trước khi gán: Sau khi gán: 3.4.3.2. So sánh hai biến con trỏ cùng kiểu Ta chỉ có thể SO sánh hai biến con trỏ cùng kiểu bằng các phép SO sánh = (bằng) và <> (khác). - Vi dụ: if a = b then Writeln(‘a bằng b’); 3.4.3.3. Hằng con trỏ N IL Nil là một giá trị hằng đặc biệt dành cho biến con trỏ để báo con trỏ không chỉ vào đâu cả. Nếu ta gán hằng Nil này cho một biến con trỏ thì có nghĩa biến đó không chỉ vào đâu cả. - Vi dụ: a: = Nil; { a không chỉ vào địa chỉ nào } 77 3.4.3.4. Chú ỷ: - Các giá trị của biến con trỏ không thể đọc từ bàn phím bằng thủ tục Read và Readln cũng như không thể đưa ra màn hình hoặc máy in bằng thủ tục Write và Writeln. - Ví dụ: Cần nhập và in các giá trị cho biến con trỏ kiểu bản ghi. Program ban_ghi_dong; uses crt; Type kbg = Record Ma_CB: Integer; ht:string[25]; DonVi:string[5]; HesoLg:real End; Var HsCb:array[1..20] of Akbg; i,n: integer; Begin Clrscr; Write('N= ');Readln(n); Writeln(’Nhap so lieu vao mang dong:'); For i:=l to n do Begin New(HsCb[i]); Write('Ma_CB[',i,']= ');Readln(HsCb[i]A.Ma_CB); WriteCHo ten = ’);Readln(HsCb[i]A.ht); Write(’Don Vi ');Readln(HsCb[i]A.DonVi); WriteC HesoLg = ');Readln(HsCb[i]A.HesoLg); Dispose(HsCb[i]); end; Writeln('Dua du lieu mang dong ra man hinh:'); Writeln('------------------------------------------------------------------'); Writeln(': Ma_CB : Ho ten : DonVi :He so Luong:'): Writeln(':------------:------------------------:----------:---------------- 78 For i:=1 to n do Begin Write(HsCb[i]A.Ma_CB:4); Write(HsCb[i]A.ht:25); Write(HsCb[i]A.DonVi:7); Write(HsCb[i]A.HesoLg:8:l); Writeln; end; Writeln(':-----:...................................:----- :............... Readln; End. 3.4.4. Một sô vấn đề mở rộng, đi sâu đối vói con trỏ 3.4.4.1. N hũng kiến thức náng cao về con trỏ - Cần phân biệt sự khác nhau giữa biến thông thường và biến kiểu con trỏ. Trong kỹ thuật lập trình, con trỏ là khái niệm tương đối trừu tượng và khó hiểu đối với sinh viên. Thông thưòng sinh viên chỉ quen với các tên biến cụ thé, khi viết c:= a+b thì họ hình dung a, b là 2 giá trị cụ thể và sẽ cho c một giá trị cụ thể, là tổng của 2 số a, b. Khi a và b là 2 biến con trỏ thì a trỏ về địa chỉ chứa giá trị aA; b trỏ vể địa chỉ chứa giá trị bA nên phép cộng a+b không hợp lệ nữa (không được cộng 2 con trỏ). Phép cộng aA+bA sẽ là tổng của 2 số ở tại địa chỉ mà a và b trỏ đến. - Giá trị thực sự của con trỏ ? Giá trị thực sự của con trỏ là địa chì ô nhớ mà sẽ chứa dữ liệu của biến động ứng với con trỏ, còn địa chỉ của bản thân con trỏ thì do chương trình dịch quyết định, bản thân người lập trình không cần quan tâm. 3.4.4.2. Những khác biệt trong cách sử dụng con trỏ trong các ngôn ngữ c , c ** và Pascal - Trong khai báo: 79 Trong Pascal Trong c và c*+ Type = A; Var :; :A; Trong đó có thể là integer, real, char, boolean, record... Ví dụ: Var intPtr : AInteger; - Trong khởi tạo giá trị cho con trỏ: * ; Trong đó có thể là int, char, vọid, double, long, struct, kiểu lớp, kiểu hàm... Ví dụ : int *a, *b ; * Trong Pascal Trong c và c 1"1' Trong Pascal, khai báo biến con trỏ chỉ mới cung cấp thông tin về tên biến và kiểu dữ liệu con trỏ. Để khởi tạo con trỏ dùng thủ tục: New(tên biến con trỏ) cấp phát vùng nhớ cho nó. Khi không dùng con trỏ nữa thì sử dụng thủ tục: Dispose() để thu hồi lại bộ nhớ của nó. - Trong sử dụng con trỏ: - Con trỏ được khởi tạo và khời gán đồng thời bằng lệnh gán ; - Sử dụng thủ tục New và Delete để cấp phát và thu hồi bộ nhớ đối vái con trỏ: = New ; Delete ; - Việc lấy địa chi cùa một biên đế gán giá trị cho con trỏ có thể dùng toán tử một rigôi &, ví dụ: Int m, n = 10, *p; p = &n; M = *p; Mục đích sử dụng con trỏ trong Pascal và c, c** đều giống nhau, đều quan tâm đến biến động của con trỏ, chỉ khác ờ cách viết. Trong Pascal, 80