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.
117 trang |
Chia sẻ: diunt88 | Lượt xem: 4662 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Kỹ thuật lập trình Pascal- Phan Huy Khánh, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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