61520370-ky-thuat-lap-trinh-pascal

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.

PGS.TS. PHAN HUY KHÁNH biên soạn

1

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.
Dữ liệu nhập

CHTR nguồn
CHTR dịch
Máy tính
CHTR đích
Máy tính

Dữ liệu kết quả

Lỗi thời gian thực hiện

Lỗi thời gian dịch

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.

3

Mở đầu

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 :
số
tên

chư

chữ

số
A ... Z

a ... z

0 ... 9

chữ
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 :

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
được
định nghĩa là (đặt giữa hai vế trái phải)
::= hoặc → hoặc =
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’

5

Mở đầu

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ấn đề
việc 2

việc 1
việc 1.1

việc 1.2

việc 1.2.1

việc 1.2.2

việc 3
...
việc 1.2.3

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.

6

Kỹ thuật lập trình Pascal

a⎯ + c⎯
b
d
ƯLPS(a ⁄ b)
ƯLPS(c ⁄ d)
ƯSCLN(a/b)
ƯSCLN(c/d)

QĐMS(a’ ⁄ b’, c’⁄d’)

a” ⁄ M + b” ⁄ M

BSCNN(b’, d’)

ƯSCLN(b’, d’)
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 :

7

Mở đầu

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
hoặc

Các hướng rẽ nhánh

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 :
Bắt đầu
Đọc a, b, c
Max = a
Max < b

Sai

Đúng
Max = b
Sai
Max < c
Đúng
Max = c
In Max
Kết thúc
Ví dụ 2 :
Giải phương trình bậc hai :
Bắt đầu
Đọc a, b, c
Δ = b*b - 4*a*c

Đúng

Sai
Sai

D<0

Đúng

D=0

x1.2 = -b/2/a

x1 = (-b - SQRT(Δ))/2/a
x1 = (-b - SQRT(Δ))/2/a

In x1.2

In x1, x2
Kết thúc

Phương trình vô nghiệm

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 }

11

Mở đầu

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
1

Tuần tự (Sequential)
begin
S1
...
Sn
end

Lưu đồ tương đương
S1
...

Sn

Mô tả
Là lệnh ghép, thực hiện tuần tự
các lệnh S1, S2, ... , Sn

12

Kỹ thuật lập trình Pascal

Cấu trúc điều khiển
2 Rẽ nhánh (Branching)
- Rẽ nhánh đủ
if ĐK
then S1
else
S2

Lưu đồ tương đương
Đúng

ĐK ?

Sai

S1

3 - Rẽ nhánh thiếu
if ĐK then S

S2

ĐK ?
Đúng

Sai

S

4 Lựa chọn (Selection)
case
ĐK1 : S1
ĐK2 : S2
...
ĐKn : Sn
endcase

Sai

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

ĐK1 ?

Đúng

ĐK2 ?

S1
S2
...

...

Sai
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

Đúng

Đúng
Sn

ĐKn ?

ĐK ?
Đúng

Sai

Mô tả
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.

Nếu ĐK đúng thì
thực hiện S.
Nếu ĐK sai thì
không làm gì cả.

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.
Khi ĐK còn đúng thì còn
thực hiện S.
Khi ĐK sai thì dừng.

S

S
Sai

ĐK ?
Đúng

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.

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ác bài toán thực tiễn mà máy tính phải giải quyết trên những
dữ liệu phi số (Non-numerical) có cấu trúc đa dạng.

III.3.2. Các phép tóan trên dữ liệu
Với mỗi cấu trúc, cần phải xây dựng các phép toán trên đó : phép tạo lập hay huỷ bỏ một
cấu trúc, phép truy cập vào từng phần tử của cấu trúc để xem hay sửa đổi, phép bổ sung hay
loại bỏ một phần tử của cấu trúc, v.v... Cấu trúc dữ liệu khác nhau thì phép toán tương ứng
cũng khác nhau. Có thể một phép toán nào đó có tác dụng đối với cấu trúc này nhưng lại
không có tác dụng đối với cấu trúc khác.
Ví dụ, phép truy cập vào một phần tử của cấu trúc dữ liệu kiểu mảng khác với phép truy
cập vào một phần tử của cấu trúc dữ liệu kiểu bản ghi, có thể cộng dồn các phần tử của một
mảng dữ liệu kiểu số nhưng không thể cộng dồn các phần tử của một mảng dữ liệu kiểu bản
ghi, v.v...
Như vậy, mỗi khi xây dựng một cấu trúc dữ liệu thì đồng thời phải xây dựng các phép
toán kèm theo. Đây là hai mặt của một vấn đề.

14

Kỹ thuật lập trình Pascal

III.3.3. Biểu diễn dữ liệu
Mỗi cấu trúc đều có cách biểu diễn trong máy khác nhau gọi là cấu trúc lưu trữ (Storage
Structure). Có sự khác nhau giữa cấu trúc dữ liệu và cấu trúc lưu trữ tương ứng. Cùng một
cấu trúc dữ liệu có thể có nhiều cấu trúc lưu trữ và cùng một cấu trúc lưu trữ có thể có nhiều
cấu trúc dữ liệu.
Ví dụ, cùng cấu trúc ma trận - bảng dữ liệu gồm nhiều hàng nhiều cột - có thể có hai cấu
trúc lưu trữ khác nhau : hoặc lưu trữ theo hàng (hết hàng nọ đến hàng kia), hoặc lưu trữ theo
cột (hết cột nọ đến cột kia). Ngược lại, một dãy dữ liệu lưu trữ liên tiếp trong bộ nhớ có thể
tương ứng với cấu trúc mảng, hoặc cấu trúc ma trận, v.v...
Cấu trúc lưu trữ có hai dạng : dạng lưu trữ ngoài cho các thiết bị nhớ phụ (bộ nhớ ngoài)
và dạng lưu trữ trong đối với bộ nhớ trong.

15

Mở đầu

CHƯƠNG 2

Các kiểu dữ liệu cơ sở của Turbo Pascal
Kiểu dữ liệu trong Pascal cho phép xác định tập hợp các giá trị mà các hằng, biến và hàm
có thể có hoặc do kết quả của các phép tính hoặc hàm.
Khai báo kiểu :
type
T = AnyType;
...
T = AnyType;
Trong đó T là tên kiểu (identifier), AnyType là kiểu bất kỳ được định nghĩa từ một trong
9 lớp kiểu sau đây : ordinal, real, string, array, set, record, file, object, pointer.
Có 7 kiểu thứ tự tiền định nghĩa (ordinal predefined) là : Shortint, Integer, Longint, Byte,
Word (5 kiểu số nguyên), Boolean và Char. Hai kiểu do NSD tự định nghĩa là kiểu liệt kê
(enumerated) và kiểu miền con (subrange).
Số các giá trị khác nhau của kiểu T là bản số (cardinality) của T, người ta thường ký hiệu
Card (T).
Khai báo một biến x có kiểu dữ liệu là T được viết : x : T .
Ví dụ :
Var x : Real;
type
Simple
ordinal

pointer
real

enumerated char integer boolean

record

structured
array

file

set

string

subrange

I. Các kiểu Ordinal
I.1.

Kiểu số nguyên

Các số nguyên có thể âm hoặc dương, độ lớn phụ thuộc máy. Nếu n là một số nguyên, thì
n phải thoả mãn bất đẳng thức :
− (maxint + 1) ≤ n ≤ maxint

16

Kỹ thuật lập trình Pascal

Trong đó, maxint là trị nguyên lớn nhất máy có thể biểu diễn được. Trong Turbo Pascal,
có hai hằng chuẩn là MaxInt = 32 767 và MaxLongint = 2 147 483 647.
Các kiểu ordinal nguyên như sau :
Type
Range
Size
Shortint
-128..127
8-bit
Integer
-32768..32767
16-bit
Longint
-2147483648..2147483647
32-bit
Byte
0..255
8-bit
Word
0..65535
16-bit
Các phép toán : + - * div nhận kết quả nguyên.
Nếu m, n là các số nguyên :
m - n < (m div n) * n ≤ m và (m div n) * n + (m mod n) = m

I.2.

Kiểu logic Boolean

Kiểu Boolean chỉ có hai giá trị là false, true, được định nghĩa như sau :
type Boolean = (False, True);
Trong một biểu thức, các phép quan hệ := <> > < >= <= IN
trả về giá trị Boolean.
Ví dụ : Giả sử x = 5, y = 7, z = 10 là các số nguyên và :
Var p, q : boolean;
ta có các phép gán :
p := (x = y) ;
{ p = false }
q := (x < y) and (y < z)
{ q = true }

I.3.

Kiểu kí tự Char

Kiểu Char gồm các kí tự ASCII. Hai hàm chuẩn kiểu Char là Ord và Chr :
Ord(x): Longint;
Chr(x: Byte): Char;
có tính chất sau :
Ord (Char(i)) = i
nếu Char(i) xác định, i nguyên
Char(Ord(c)) = C
Ví dụ :
Uses Printer;
begin
{ Send form feed to printer }
WriteLn(Lst, Chr(12));
end.
Hai biểu thức đặc biệt :
f(c) = Ord(c) − Ord('0')
g(i) = Char(i + Ord('0'))

vị trí của C trong các chữ số
chữ số thứ i

f ('4') = Ord(‘4’) − Ord(‘0’) = 52 − 48 = 4,
g (7) = Char(7 + Ord(‘0’)) = Char(55) = '7'
f và g là hai hàm ngược của nhau :
f(g(i)) = i
i = 0..9
g(f(c)) = c
c = '0'..'9'
Ví dụ :

Các kiểu dữ liệu cơ sở của Turbo Pascal

I.4.

17

Bảng các hàm chuẩn
gtrị
Integer

Real

đối

Integer
pred
succ
abs
sqr
sin
cos
arctan
ln
exp
sqrt

Boolean

odd

Char

chr

Real

Boolean

Char

trunc
round

ord

ord

File

sin
cos
arctan
ln
exp
sqrt
sqr
abs
pred
succ

eof
eoln
pred
succ

II. Kiểu số thực Real
Trong một CHTR Pascal, biến thực (real variable) được dùng để lưu trữ các giá trị thực.
Tuỳ theo máy mà miền giá trị (range) bị hạn chế như tập các số nguyên.
Khi giải quyết các bài toán khoa học, có thể tồn tại những số rất bé hoặc rất lớn, ví dụ,
trọng lượng của một electron là :
0.000 000 000 000 000 000 000 000 000 091 095 600 gram
Dạng khoa học (dạng mũ) của số này là 9.10956 × 10−28 gram. Trong ngôn ngữ Pascal,
số này có dạng 9.10956E−28.
Turbo Pascal có 5 kiểu số thực như sau :
Type
Range
Digits
Bytes
real
2.9e-39..1.7e38
11-12
6
single
1.5e-45..3.4e38
7-8
4
double
5.0e-324..1.7e308
15-16
8
extended
3.4e-4932..1.1e4932
19-20
10
comp
-9.2e18..9.2e18
19-20
8
Mỗi biến thực được xác định bởi hai yếu tố : miền giá trị và độ chính xác (precision).
Miền giá trị cho biết độ lớn của số được lưu trữ. Độ chính xác cho biết số số lẻ có ý nghĩa
sau dấu chấm thập phân.

18

Kỹ thuật lập trình Pascal

III. Các phép toán (Operators)
Các phép toán của Turbo Pascal như sau :
Op.

Integer

Real

String

Set

+
*
/
DIV
MOD

Addition
Subtraction
Multiplication

Addition
Subtraction
Multiplication
Division

Concatenation

Union
Difference
Intersection

NOT
AND
OR
XOR
SHL
SHR

Division
Modulo
Integer
Bitwise negation
Bitwise AND
Bitwise inclusive OR
Bitwise exclusive OR
Bitwise shift-left
Bitwise shift-right

Boolean
Logical negation
Logical AND
Logical inclusive OR
Logical exclusive OR

Các phép quan hệ sau đây trả về giá trị Boolean :
Op.

Tên gọi

Kiểu dữ liệu so sánh

=
<>
<
>
<=
>=

Equal
Not equal
Less than
Greater than
Less than or equal
Greater than or equal

IN

Member of

Ordinal, real, string, set, pointer
Ordinal, real, string, set, pointer
Ordinal, real, string
Ordinal, real, string
Ordinal, real, string, set
Ordinal, real, string, set
Giá trị trả về của phép IN
True nếu toán hạng bên trái (kiểu ordinal) là một phần
tử của toán hạng bên phải (kiểu tập hợp)
False nếu không

⎯
Tính căn bậc hai của một số dương (s = √ n) theo phương pháp Newton không sử
dụng hàm sqrt().
Nội dung phương pháp :
Nếu gọi s là giá trị gần đúng của căn bậc hai của n thì :
Ví dụ :

(n ⁄ s + s) ⁄ 2
là giá trị gần đúng hơn của n. Quá trình tính toán dừng lại khi đạt tới độ chính xác ε cần
thiết. Giả sử chọn ε = 10 − 6, khi đó :
n
s2

− 1 <

ε

Các kiểu dữ liệu cơ sở của Turbo Pascal

19

{ Chương trình đọc vào một số và in ra giá trị căn bậc hai gần đúng tương ứng cho đến
khi đọc vào số 0 }
Program Tính_căn_bậc_2;
Uses Crt;
Const epsilon = 10E-6;
Var n, s : real;
begin
repeat
write(’Dọc vào một số n = ’);readln(n);
if n<0 then writeln(’#7Vào sai dữ liệu !’)
else begin
s:=1;
repeat s:=(n/s+s)/2
until abs(n/sqr(s)-1)< epsilon;
writeln(’Căn bậc hai = ’, s:14:6)
end
until n = 0;
readln
end. {Tính_căn_bậc_2 }

IV. Kiểu vô hướng liệt kê và kiểu miền con
IV.1. Kiểu vô hướng liệt kê (Enumerated Scalar Type)
Kiểu vô hướng liệt kê được định nghĩa là tập hợp các hằng có thể gán cho các biến thuộc
loại vô hướng liệt kê :
Type T = (C1, C2, ..., Cn) ;
Các Ci, với i = 1..n được sắp xếp theo thứ tự tự nhiên. T không là kiểu số và không có
cấu trúc. Card(T) = n, Ci ≠ Cj nếu i ≠ j.
Ví dụ :
Type
Màu = (đỏ, dacam, vàng, lục, lam, chàm, tím);
Sex = (male, female);
Boolean = (false, true);
Var
m1, m2 : Màu;
s : Sex;
Nếu không cần tên kiểu T, có thể khai báo trực tiếp :
Var x1, ..., xm : (C1, C2, ..., Cn) ;
Ví dụ :
Var m1, m2 : (đỏ, dacam, vàng, lục, lam, chàm, tím);
Từ ví dụ trên có thể xây dựng phép gán :
m1 := tím; m2 := đỏ; s := female;
Kiểu liệt kê là đếm được. Ta cũng có hai hàm pred (x), succ (x) xác định bởi :
(Ci < Cj) ≡ (i
Succ(Ci) = Ci+1

Pred(Cj) = Ci−1

20

Kỹ thuật lập trình Pascal

Hàm Ord (x) cho vị trí của x trong T. Vị trí đầu tiên của kiểu liệt kê có giá trị 0.
Ta có :
Ord (đỏ) = 0,
Ord(false)=0
Ord(male) = 0.
Ord (vàng) = 2,
Ord(true)=1
Ord(female) = 1.
Các biến kiểu liệt kê được dùng trong các vòng lặp có tham biến. Ví dụ :
{ xử_lý là một đoạn chương trình xử lý nào đó }
for m1= đỏ to tím do xử_lý;
Chú ý rằng lệnh trên không thể thay thế bởi vòng lặp kiểm tra điều kiện trước while..do
như sau :
m1 := đỏ;
while m1 <= tím do begin
xử_lý;
m1 := Succ(m1); { lệnh này gây ra lỗi khi chạy }
end;

IV.2. Kiểu miền con (Sub-range type)
Kiểu miền con được định nghĩa bởi hai hằng là cận trên (upper bound) và cận dưới
(lower bound)của các giá trị thuộc kiểu này.
Type T = min .. max ;
min và max là cận dưới và cận trên tương ứng (hay là hai giới hạn) của kiểu miền con T,
thoả mãn bất đẳng thức min ≤ max.
Nếu không cần tên kiểu T, có thể khai báo trực tiếp :
Var x1, ..., xm : min .. max ;
Ví dụ :
Type
year = 1990..1999;
letter = 'A' .. 'Z';
tuổi = 1..200;
Nếu có :
Var y : year ;
l : letter ;
t : tuổi;
thì y:=1995; l:= 'Q' ; t:= 5;
là hợp lệ.
Còn y:= 2001; l:= “a” ; t:= 205;
là không hợp lệ.
Tất cả các hàm dùng cho các kiểu ordinal đều có thể sử dụng cho kiểu miền con tương
ứng. Giá trị trả về của hàm không nhất thiết phải nằm trong các cận của kiểu tham đối. Ví dụ
giá trị của sqr(t) có thể vượt quá cận trên 200.
Các thủ tục Read và Write có thể có tham đối kiểu miền con kiểu nguyên hay kiểu kí tự.
Kiểu miền con thường được dùng để kiểm tra tự động các cận giá trị cho phép, tránh gây ra
sai sót khi lập trình.
Vi dụ 1 : tính số ngày của tháng bất kỳ trong năm.