Kỹ thuật lập trình Pascal- Phan Huy Khánh

PGS.TS. PHAN HUY KHÁNH biên soạn 1 CHƯƠNG 1 Mở đầu I. Chương trình (program) Chương trình (CHTR) là dãy liên tiếp các lệnh (instructions, commands), hay các câu lệnh (statements). Chạy chương trình (run hay execute) là cho máy tính thực hiện lần lượt các lệnh của CHTR. Một CHTR đang chạy tạo ra một tiến trình (process). Các tiến trình thường có các tính chất sau : 1. Các lệnh của CHTR được thực hiện một cách tuần tự (sequantial), hết một lệnh lại thực hiện lệnh kế tiếp. 2. Một tiến trình luôn luôn có kết quả (result). Kết quả được đưa ra trong khi thực hiện CHTR hoặc sau khi đã thực hiện xong. Kết quả có thể đúng hoặc sai. Thông thường kết quả được in (print) ra trên giấy hoặc hiển thị (display) lên màn hình. 3. CHTR thường đòi hỏi dữ liệu (data). Các dữ liệu có thể được đưa vào trực tiếp trong khi chạy CHTR, hoặc từ các thiết bị ngoài như bàn phím (keyboard), đĩa từ (disk), băng từ (tape)..., nhưng cũng có thể đã đặt sẵn đâu đó trong CHTR. 4. Một số lệnh dùng để mô tả (declare) dữ liệu của CHTR. Trong một số ngôn ngữ, người lập trình (NLT) phải đặt các lệnh này ở phần đầu của CHTR để máy sử dụng ở phần sau. 5. Một số lệnh dẫn đến sự quyết định (decision) sẽ thực hiện nhóm lệnh nào tiếp theo. Ví dụ, khi giải một phương trình bậc 2, nếu biệt số Δ âm sẽ trả lời phương trình không có nghiệm thực, ngược lại, thực hiện các lệnh tính nghiệm thực. Thực tế, NLT không biết lúc chạy CHTR, biệt số Δ là âm, dương hay triệt tiêu ? 6. Một số lệnh được thực hiện lặp đi lặp lại nhiều lần. NLT có thể biết trước hoặc không biết trước số lần lặp. NLT cũng có thể ấn định việc lặp được bắt đầu như thế nào. II. Ngôn ngữ lập trình (programming language) II.1. Khái niệm về ngôn ngữ lập trình Ngôn ngữ lập trình (NNLT) là công cụ để con người giao tiếp với máy tính. Trong Tin học, lĩnh vực xây dựng và phát triển các ngôn NNLT luôn luôn đặt ra những vấn đề mới. Người ta thường chia ra hai loại NNLT : ngôn ngữ bậc thấp (low-level programming language) và ngôn ngữ bậc cao (high-level programming language). Ngôn ngữ bậc thấp gồm ngôn ngữ máy (machine language) và hợp ngữ (assembly language). Trong một CHTR viết bằng ngôn ngữ bậc thấp, mỗi câu lệnh chỉ tương ứng với một thao tác sơ cấp của bộ xử lý. Vì vậy, lập trình trên các ngôn ngữ bậc thấp rất phiền phức và dễ nhầm lẫn. 2 Kỹ thuật lập trình Pascal Ngôn ngữ bậc cao phỏng theo ngôn ngữ Toán học và gần gũi với ngôn ngữ tự nhiên. Lập trình trên các ngôn ngữ bậc cao thoải mái hơn và ít nhầm lẫn hơn do sử dụng những câu lệnh gần gũi với lời giải bài toán, dễ kiểm tra, dễ sửa, v.v... Hiện nay có rất nhiều ngôn ngữ bậc cao đã được phát triển, mỗi ngôn ngữ đặc trưng cho một phong cách, một trường phái lập trình. Việc chọn một NNLT nào đó phụ thuộc vào tính chất của bài toán đang giải và nhiều khi, phụ thuộc vào thói quen của NLT. Khi thực thi một CHTR viết trên một ngôn ngữ cấp cao, bộ xử lý phải chuyển đổi CHTR này sang dạng một CHTR bằng ngôn ngữ máy tương đương. Một CHTR thực hiện chức năng này gọi là chương trình dịch (compiler). CHTR viết trên một ngôn ngữ cấp cao được gọi là chương trình nguồn (source program). CHTR đã được dịch sang dạng ngôn ngữ máy tương đương được gọi là chương trình đích (object program). Máy thực hiện chương trình đích cùng với các dữ liệu nhập (input data) để cho ra kết quả. Khi chạy CHTR có thể gây ra lỗi (error). Lỗi sinh ra khi dịch được gọi là lỗi thời gian dịch (compile-time error). Lỗi sinh ra khi chạy CHTR được gọi là lỗi thời gian thực hiện (run-time error). Ngoài ra có thể có các lỗi do sai sót về thuật giải hoặc do sai sót về dữ liệu nhập. II.2. Các yếu tố của ngôn ngữ lập trình Các NNLT bậc cao được tạo thành từ ba yếu tố : bộ kí tự, bộ từ vựng và cú pháp. II.2.1. Bộ kí tự (Character Set) Gồm các kí tự được phép dùng trong ngôn ngữ. Các máy vi tính IBM và tương thích thường sử dụng các kí tự ASCII. Có thể hiểu bộ kí tự có vai trò như bảng chữ cái (alphabet) của một ngôn ngữ tự nhiên. CHTR dịch CHTR nguồn Máy tính Dữ liệu nhập CHTR đích Máy tính Dữ liệu kết quả Lỗi thời gian dịch Lỗi thời gian thực hiện Mở đầu 3 II.2.2. Bộ từ vụng (Vocabulary) Gồm các từ (word) hay đơn vị từ vựng (token) dùng để tạo thành câu lệnh và được phân loại tuỳ theo vai trò của chúng trong ngôn ngữ. Mỗi loại lại được chia ra thành các nhóm nhỏ hơn tuỳ theo chức năng. Ví dụ : Chương trình Pascal : Các đơn vị từ vựng : Program P; var ×, y : integer; begin Read(x); y:=x+2; write(y) end. Tên (Identifier) Read, Write, P, x, y Hằng (Constant) 2 Toán tử (Operator) +, := Dấu phân cách Program var : ( ) begin end. (Delimiter) II.2.3. Cú pháp (Syntax) Cú pháp của một NNLT quy định cách thức kết hợp các kí tự thành từ, kết hợp các từ thành câu lệnh đúng, kết hợp các câu lệnh đúng thành một chương trình hoàn chỉnh về mặt văn phạm (grammaire). Có thể hình dung cách kết hợp này giống cách đặt câu trong một ngôn ngữ tự nhiên. Thường người ta dùng sơ đồ cú pháp (syntax diagram) hoặc dạng chuẩn Backus-Naur (Backus-Naur Form) để biểu diễn cú pháp. II.3. Sơ đồ cú pháp II.3.1. Khái niệm Sơ đồ cú pháp dùng để mô tả một ngôn ngữ lập trình. Sơ đồ cú pháp giúp người sử dụng (NSD) hiểu được các dạng thức của các yếu tố cấu tạo nên một CHTR. Sơ đồ cú pháp được cấu tạo từ các phần tử sau : Khung tròn, hoặc ôval : chứa các ký hiệu kết thúc (termiral symbol) là những ký hiệu cụ thể, có ý nghĩa và có mặt chính xác trong CHTR. Ví dụ : program, begin, end... Khung chữ nhật : chứa các ký hiệu không kết thúc (non-terminal symbol) là những khái niệm được định nghĩa qua những ký hiệu kết thúc và/hoặc không kết thúc khác. Ví dụ : identifier (tên), program (chương_trình), file_name (tên tệp)... Đường nối : là các đường có mũi tên để chỉ thứ tự xuất hiện của các phần tử khung tròn, hay chữ nhật. Ví dụ : Tên trong các NNLT thường có sơ đồ cú pháp như sau : Từ đó có thể xây dựng các tên đúng như : Delta, x1, x2, Sqrt, bánkính v.v... Trái lại, các chuỗi kí tự sau đây đều không phải là tên : tên chữ số chư chữ A ... Z a ... z số 0 ... 9 4 Kỹ thuật lập trình Pascal 1A bắt đầu bằng số, β, π không thuộc bộ kí tự, bán kính có dấu cách ở giữa, v.v.... Chú ý các dấu tiếng việt được thêm vào cho dễ hiểu mà không đưa vào CHTR khi thao tác trên máy. II.3.2. Cách đọc sơ đồ cú pháp Đọc theo đường nối có mũi tên. Nếu gặp ký hiệu không kết thúc (khung vuông) thì tiếp tục đọc ở sơ đồ cú pháp của nó. Ví dụ : Đọc sơ đồ cú pháp của tên : bắt đầu bằng một chữ cái, sau đó có thể là các chữ cái, các chữ số (đường nối mũi tên có thể tạo thành vùng lặp). II.3.3. Đánh giá về sơ đồ cú pháp Sơ đồ cú pháp tuy là phương tiện tốt để là quen với ngôn ngữ lập trình nhưng sơ đồ cú pháp không mô tả được đầy đủ ngữ pháp của một ngôn ngữ lập trình. Ví dụ :  không thể hiện được sự kiện các biến, các hằng số cùng cấp không được trùng tên.  không mô tả được các nhãn (label) là số có thể từ 0 đến 9999, tuy có thể mô tả được nhưng rất rắc rối. II.4. Dạng BNF Dạng BNF mô tả một văn phạm dưới dạng các định nghĩa. Mỗi định nghĩa gồm hai vế đặt cách nhau một ký hiệu đặc biệt, vế trái là một ký hiệu không kết thúc, còn vế phải là một dãy ký hiệu có thể vừa có ký hiệu không kết thúc, vừa có ký hiệu kết thúc. Dạng BNF thường dùng các kí tự quy ước như sau : Ký hiệu Ý nghĩa ::= hoặc → hoặc = { } [ ] | được định nghĩa là (đặt giữa hai vế trái phải) chuỗi của 0 hay nhiều mục liệt kê hoặc 0 hoặc 1 mục liệt kê mục liệt kê được thay thế hoặc (theo ngĩa loại trừ) Ví dụ : Tên được mô tả dưới dạng BNF như sau : = { | } = ‘A’ | ... | ‘Z’ | ‘a’ | ... | ‘z’ = ‘0’ | ... | ‘9’ Mở đầu 5 III. Lập trình (programming) Ngôn ngữ lập trình mới chỉ là công cụ để NSD điều khiển máy theo ý muốn, còn việc sử dụng công cụ này như thế nào cho có hiệu quả thì lại tuỳ thuộc vào kỹ thuật lập trình của mỗi người. Lập trình là việc viết chương trình trên một ngôn ngữ lập trình cụ thể nào để giải quyết một vấn đề nào đó. Để lập trình, phải trãi qua 4 bước : 1. Phân tích vấn đề cần giải quyết : Nội dung vấn đề là gì ? Phải làm gì ? 2. Xây dựng thuật giải và cấu trúc dữ liệu để giải quyết vấn đề (làm như thế nào ?). Công thức của Niclaus Wirth : Algorithms + Data Structures = Programs Nghĩa là : Thuật giải + Cấu trúc dữ liệu = Chương trình. 3. Viết chương trình trên một ngôn ngữ đã lựa chọn, ví dụ Turbo Pascal. 4. Chạy thử chương trình, sửa sai, hoàn thiện, cài đặt và đem vào ứng dụng. III.1. Phân tích vấn đề Có nhiều phương pháp phân tích vấn đề. Thường sử dụng phương pháp phân tích từ trên xuống (Top-Down Analysis). Nội dung phương pháp là chia vấn đề cần giải quyết thành các vấn đề nhỏ hơn, mỗi vấn đề đó lại được tiếp tục chia thành các vấn đề nhỏ hơn nữa, v.v... cho đến khi đó là những công việc đơn giản và dễ giải quyết. Ví dụ : Phân tích bài toán cộng hai phân số để đưa về bài toán tìm ước số chung lớn nhất của hai số nguyên. Để cộng hai phân số, trước tiên cần ước lược chúng (ƯLPS), sau đó quy đồng mẫu số (QĐMS). Cộng hai tử số của hai phân số đã quy đồng để được tử số. Lấy mẫu số chung. việc 1.1 việc 1.2 việc 3 việc 2 việc 1 vấn đề việc 1.2.3 việc 1.2.2 việc 1.2.1 . . . 6 Kỹ thuật lập trình Pascal Việc ước lược phân số được đưa về tìm ước số chung lớn nhất của tử số và mẫu số. Để quy đồng mẫu số, cần tìm bội số chung nhỏ nhất (BSCNN). Việc tìm bội số chung nhỏ nhất của hai số lại được đưa về tìm ước số chung lớn nhất của chúng : BSCNN(b’, d’) = b’ * d’ / ƯSCLN(b’,d’). Để tìm ước số chung lớn nhất, sử dụng thuật giải Euclide. III.2. Thuật giải (Algorithm) III.2.1. Khái niệm về thuật giải Thuật giải, hay còn gọi là thuật giải (giải thuật), là tập hợp đặc trưng các trình tự logic và toán học đơn giản, được xác định rõ ràng, để theo đó giải quyết một vấn đề với một số bước nhất định. Cũng có thể định nghĩa thuật giải là cách giải quyết bài toán bằng các bước cụ thể theo trình tự nhất định và phải kết thúc sau hữu hạn bước. Ví dụ : Sau đây là thuật giải tìm số lớn nhất Max trong 3 số a, b, c. Bước 1 : Đọc vào 3 số a, b, c. Bước 2 : Cho a là số lớn nhất : Max = a. Bước 3 : So sánh Max với b, nếu Max nhỏ thua b thì Max lấy giá trị b : Max = b. Bước 4 : So sánh Max với c, nếu Max nhỏ thua c thì Max lấy giá trị c : Max = c. Bước 5 : In kết quả là Max. Có thể hình dung việc tìm Max qua các biểu thức dạng hàm như sau : Max (a, b, c) = Max(Max (a, b), c), trong đó : Max ( a, b) = if a>b then a else b Có thể hiểu thuật giải là phương pháp giải một bài toán bằng cách chia nhỏ bài toán đó thành những thao tác đơn giản, dễ thực hiện và có trình tự hợp lý. Các bước để làm một món ăn, để sắp xếp đồ vật theo thứ tự, để giải một phương trình toán học, v.v... đều có thể coi là những thuật giải. Không thể có trình tự thực hiện giống nhau cho mọi thuật giải. Một thuật giải phải thoả mãn ba điều kiện sau đây : a⎯b + c⎯d a” ⁄ M + b” ⁄ M ƯSCLN(b’, d’) BSCNN(b’, d’) QĐMS(a’ ⁄ b’, c’⁄d’) ƯSCLN(a/b) ƯSCLN(c/d) ƯLPS(a ⁄ b) ƯLPS(c ⁄ d) Mở đầu 7 1. Các thao tác có tính khả thi (thực hiện được trên máy) và có trình tự xác định. 2. Mỗi thao tác phải cụ thể, rõ ràng và chỉ được hiểu theo một nghĩa duy nhất. 3. Thuật giải phải kết thúc sau một số hữu hạn bước. Việc giải quyết một bài toán có thể có nhiều thuật giải khác nhau. Mỗi thuật giải lại có thể có hiệu quả như nhau cho một lớp các bài toán. Ví dụ, có nhiều thuật giải để sắp xếp một daỹ số theo thứ tự tăng dần. Tuy nhiên, với mỗi thuật giải sắp xếp, có thể áp dụng cho một dãy số bất kỳ (độ lớn bất kỳ của mỗi số và số lượng bất kỳ các số phải sắp xếp). Cần phân biệt thuật giải với một số thuật ngữ gần gũi với thuật giải như kịch bản văn nghệ, cách sử dụng một đồ vật, chương trình hành động, v.v... III.2.2. Các công cụ để trình bày thuật giải Có hai công cụ phổ biến : lưu đồ và ngôn ngữ giả. a. Lưu đồ (Flowchart) Lưu đồ hay sơ đồ khối là sơ đồ chứa các hình ký hiệu đại diện cho các thao tác cần phải làm. Trong sơ đồ, các hình được nối với nhau bởi các mũi tên chĩ trình tự thực hiện các thao tác. Lưu đồ gồm các hình cơ bản sau : Đánh dấu bắt đầu và kết thúc thuật giải Nhập / xuất dữ liệu Xử lý (tính toán) dữ liệu Quyết định rẽ nhánh Các hướng rẽ nhánh hoặc 8 Kỹ thuật lập trình Pascal Ví dụ 1 : Sơ đồ khối thuật giải tìm số lớn nhất trong 3 số a, b, c : Ví dụ 2 : Giải phương trình bậc hai : Max = c Max = b Max = a Đọc a, b, c Bắt đầu Max < b Sai Sai Đúng Đúng Kết thúc In Max Max < c x1 = (-b - SQRT(Δ))/2/a x1 = (-b - SQRT(Δ))/2/a In x1, x2 In x1.2 Phương trình vô nghiệm Δ = b*b - 4*a*c x1.2 = -b/2/a Đọc a, b, c Bắt đầu D < 0 Đúng Sai Đúng Sai Kết thúc D = 0 Mở đầu 9 b. Ngôn ngữ giả (Pseudo-Language) Ngôn ngữ giả (giả định) là sự kết hợp giữa ngôn ngữ tự nhiên với một ngôn ngữ lập trình nào đó sẽ được chọn để viết chương trình. Ngôn ngữ giả sử dụng các cấu trúc điều khiển của ngôn ngữ lập trình nhưng không gò bó về mặt cú pháp như ngôn ngữ lập trình. Sau đây là một số quy định của ngôn ngữ giả : Bộ kí tự là tập kí tự ASCII và các chữ cái có dấu tiếng Việt để tiện theo dõi. Bộ từ vựng được xây dựng bằng cách ghép các kí tự thuộc tập hợp kí tự và bắt đầu phải bằng chữ. Có hai loại từ : − Từ khoá (Keyword) là từ dành riêng để chỉ một lệnh (một thao tác). Trong phần đầu giáo trình, các từ khoá được in chữ đậm để dễ phân biệt. Ví dụ : Program, begin, end... − Tên là từ do NSD tự đặt. Tên xác định địa chỉ của một vùng nhớ chứa dữ liệu trong bộ nhớ trong. Kiểu dữ liệu (Data Type) chỉ định một lớp các giá trị dữ liệu mà máy có thể xử lý. Gồm các kiểu cơ sở thường gặp : − Kiểu nguyên (Integer) là các số nguyên thông thường. − Kiểu thực (Real) là các số thực thông thường. − Kiểu chuỗi hay xâu (String) là dãy từ 0 đến n kí tự bất kỳ được đặt giữa hai dấu nháy đơn. Ví dụ : ‘This is a string’, ‘Đại học Đà nẵng, 17A Lê Duẩn’, ‘ ‘ (chuỗi rỗng). − Kiểu logic, hay luận lý, chỉ gồm hai giá trị True (1) và False (0). Hằng, biến và hàm đặc trưng bởi tên gọi, kiểu dữ liệu và giá trị. − Hằng (Constant) là đại lượng không đổi trong quá trình thực hiện CHTR. − Biến (Variable) là đại lượng thay đổi trong quá trình thực hiện CHTR. − Hàm (Function) là một CHTR con đã được lập sẵn và ược đặt tên, khi cần chỉ việc gọi tên, cung cấp tham đối để trả về một giá trị. Trong ngôn ngữ giả có sử dụng các dòng chú thích (Comment) đặt giữa hai dấu {} hoặc cặp dấu (* *) nhằm mục đích dễ theo dõi, không có tác dụng gì đối với các lệnh của thuật giải. 10 Kỹ thuật lập trình Pascal Ví dụ : Sử dụng ngôn ngữ giả, có thể viết lại các thuật giải trên như sau : Program TìmMaxCủa3Số begin Đọc (a, b, c) Max = a if Max < b then Max = b if Max < c then Max = c In (Max, ‘ là số lớn nhất’) end { TìmMaxCủa3Số } Program GiảiPhươngTrìnhBậc2 begin Đọc (a, b, c) Delta = b*b - 4*a*c if Delta < 0 then In (‘Phương trình vô nghiệm.’) else if Delta = 0 then x1_2 = -b/2/a In (‘Phương trình có nghiệm kép x = ’, x1_2) else begin x1 = (-b + SQRT(Delta))/2/a x2 = (-b - SQRT(Delta))/2/a In (‘Phương trình có hai nghiệm :’) In (‘x1 = ‘, x1) ; In (‘x2 = ‘, x2) end end { GiảiPhươngTrìnhBậc2 } Mở đầu 11 III.2.3. Các lệnh dùng trong thuật giải Các lệnh trong thuật giải có hai loại :  các lệnh không mang tính điều khiển, ví dụ lệnh gán và các lệnh vào - ra dữ liệu.  các lệnh điều khiển sự thi hành chương trình, gọi là các cấu trúc điều khiển (Control Structure). Các cấu trúc điều khiển mô tả trật tự các thao tác hay các lệnh mức thấp hơn cần phải thực hiện. a. Lệnh gán Lệnh gán (Assignement) có dạng : := Dấu := là dấu gán bằng của Pascal, tuy nhiên có thể viết =, hoặc ←. Bên trái dấu gán chỉ có thể là một tên biến . Bên phải dấu gán là một biểu thức . Máy tính giá trị của biểu thức và gán cho biến, giá trị cũ của của biến bị xoá. Nếu trong biểu thức có các tên biến khác xuất hiện thì các biến này phải có giá trị trước khi thực hiện phép gán. Ví dụ : n := 0 Delta := b*b - 4*a*c HọTên := ‘Nguyễn Văn Quang’ ĐiềuKiện := (TổngĐiểm >= 15) And (MãNgành = ‘401’) Để hoán đổi nội dung hai biến a và b cho nhau (a chứa nội dung của b, b chứa nội dung của a), dùng một biến trung gian t theo một trong hai cách như sau : t := a ; a := b ; b := t hoặc t := b ; b := a ; a := t (Nếu cả a và b đều là dữ liệu số thì có thể không cần dùng biến trung gian !). b. Các cấu trúc điều khiển cơ bản Cấu trúc điều khiển Lưu đồ tương đương Mô tả 1 Tuần tự (Sequential) begin S1 . . . Sn end Là lệnh ghép, thực hiện tuần tự các lệnh S1, S2, ... , Sn S1 . . . Sn 12 Kỹ thuật lập trình Pascal Cấu trúc điều khiển Lưu đồ tương đương Mô tả 2 Rẽ nhánh (Branching) - Rẽ nhánh đủ if ĐK then S1 else S2 Nếu điều kiện ĐK thoả mãn (đúng) thì thực hiện lệnh S1. Nếu ĐK không thoả mãn (sai) thì thực hiện S2. 3 - Rẽ nhánh thiếu if ĐK then S Nếu ĐK đúng thì thực hiện S. Nếu ĐK sai thì không làm gì cả. 4 Lựa chọn (Selection) case ĐK1 : S1 ĐK2 : S2 . . . ĐKn : Sn endcase Nếu ĐK1 đúng thì thực hiện S1. Nếu không, nếu ĐK2 đúng thì thực hiện S2. v.v... Cuối cùng, nếu ĐKn đúng thì thực hiện Sn. Nếu không thì thôi. 5 Cấu trúc lặp (Iteration) Kiểm tra điều kiện trước khi thực hiện vòng lặp : while ĐK do S Khi ĐK còn đúng thì còn thực hiện S. Khi ĐK sai thì dừng. 6 Lặp với kiểm tra điều kiện sau khi thực hiện xong thân vòng lặp : do S until ĐK Còn thực hiện S khi ĐK còn chưa thoả mãn (sai). Ít nhất lặp được một lần. Dừng khi ĐK đúng. ĐK ? Đúng Sai S2 S1 ĐK ? Đúng Sai S ĐK ? Đúng Sai S ĐK ? Đúng Sai S S1 . . . . . . S2 Sn ĐK1 ? Đúng Sai Đúng Đúng Sai ĐK2 ? ĐKn ? Mở đầu 13 III.3. Cấu trúc dữ liệu Như đã thấy, thuật giải chỉ phản ánh các thao tác cần xử lý, còn đối tượng để xử lý trên máy lại là dữ liệu (Data). Dữ liệu biểu diễn các thông tin cần thiết cho bài toán, gồm các dữ liệu đưa vào, các dữ liệu đưa ra và các dữ liệu tính toán trung gian. Dữ liệu và thuật giải có mối quan hệ với nhau : nói đến thuật giải là nói đến thuật giải đó tác động lên dữ liệu nào. Còn nói đến dữ liệu là nói đến dữ liệu ấy cần được tác động bởi thuật giải nào để đưa đến kết quả mong muốn. Bản thân các dữ liệu thường có mối quan hệ với nhau. Cách tổ chức dữ liệu sao cho phù hợp với bài toán cần giải quyết chính là vai trò của lĩnh vực cấu trúc dữ liệu (Data Structure). Cấu trúc dữ liệu liên quan đến ba vấn đề : kiểu dữ liệu, các phép tóan tác động lên dữ liệu và cách biểu diễn dữ liệu trong bộ nhớ của máy tính. III.3.1. Kiểu dữ liệu Mỗi NNLT thường có hai kiểu dữ liệu : kiểu dữ liệu cơ sở và kiểu dữ liệu có cấu trúc. Kiểu dữ liệu cơ sở có thể là kiểu số, kiểu kí tự và kiểu logic. Tuỳ theo bài toán mà kiểu dữ liệu nào thì được sử dụng. Từ kiểu dữ liệu cơ sở, người ta xây dựng các kiểu dữ liệu phức tạp hơn bằng cách liên kết chúng lại với nhau theo một cấu trúc nào đó. Ví dụ, trong hầu hết các NNLT đều có cấu trúc mảng (Array) là một dãy các phần tử dữ liệu có cùng kiểu và có số lượng ấn định. Mỗi phần tử của mảng có thể là kiểu cơ sở nhưng cũng có thể là kiểu có cấu trúc. Cấu trúc kiểu bản ghi (Record) là sự mở rộng của khái niệm mảng. Mỗi bản ghi gồm nhiều thành phần, mỗi thành phần còn gọi là một trường (Field) có kiểu dữ liệu xác định khác nhau. Ví dụ, trong quản lý cán bộ, có thể hình dung mỗi bản ghi mô tả một cán bộ gồm các trường Họ_tên, Ngày_sinh, Lương_cơ_bản, v.v... Trường Họ_tên có kiểu kí tự ; trường Ngày_sinh lại là một kiểu bản ghi được định nghĩa gồm 3 trường Ngày, Tháng và Năm cùng kiểu số nguyên ; trường Lương_cơ_bản có kiểu số thực. Chính vì sự phong phú của c