Giáo trình Tiếng Anh chuyên ngành Khoa học máy tính: Phần 2 – KS. Châu Văn Trung
270
12 MB
6
40
4.3 (
16 lượt)
27012 MB
Nhấn vào bên dưới để tải tài liệu
Đang xem trước 10 trên tổng 270 trang, để tải xuống xem không thiếu hãy nhấn vào bên trên
Chủ đề tương quan
Tài liệu tương tự
Nội dung
3 65
Chương 6: Mảng và Chuỗi
CHAPTER
*
Arrays and Strings
6
M ảng và ch u ỗ i
MỤC ĐÍCH YÊU CẨU
Sau khi học xong chương này, các Dạn sẽ nắm vững các khái n iệm về
mảng và chuỗi, các phương pháp xử lý m ảng và ”huỗi trong các ngôn
ngữ lập trìn h C/C++, V isual B asic và Java, với các nội dung cụ th ể
sau đây:
♦
Introduction to arrays
♦
Giới thiệu sơ lược về m ảng
♦
Arrays in Visual Basic
+
Các mảng trong Visual basic
♦
Arrays in C/C++ and Java
+
Các mảng trong C/C ++ và Java
♦
Searching
+
Tìm kiêm
♦
Sorting
+
Sắp xếp thứ tự
Ngoài ra, ở cuối chương còn zỏ phần bài tập có lời g iải, bài tập bổ
sung và đáp án Ìihằm giúp các bọn thực h àn h và áp dụng m ột cách
hiệu quả vào công việc thực tế.
/
366
Chapter 6: Arrays anơ strings
CHỦ DIỂM 6.1
INTRODUCTION TO ARRAYS
G i ó i thiệu sơ lược về mảnq
An a r r a y is a group of memory locations all of the same type that have
the same name. Previously, in a program to calculate employee pay, the
user would type in the employee number, the pay rate, and the number of
hours worked. There would be one variable to hold each piece of informa
tion as shown in Fig. 6-1, i-nd then the gross pay would be calculated.
employeeNum
101
hourly Rate
6.25
hours Worked
grossPay
40
Fig. 6-1 Individual variables for payroll.
If th e re w ere m ore th a n one em ployee, th e p ro g ram could have a
loop for th e u ser to type in th e in form ation in to th e sam e variables
for th e second em ployee and calculate th a t p e rso n ’s gross pay, then
th e th ird, and so forth. However, a problem would a ris e if the em
ployer w anted to have a re p o rt co n tain in g a lis t of th e w eekly pay for
all th e em ployees, th e average pay for th e w eek, an d th e n a list of all
th e em ployees who received above th e average pay. T he average could
not be calculated until all th e em ployees’ in fo rm atio n was submitted.
In o r d e i’to com pare each p erso n ’s pay to th e av erag e, all th e infor
m ation would need to be e n tered a second tim e.
Oane solution to this problem would be to have a different variable for
each employee, as shown in Fig. 6-2. Each person’s pay could be compared
to the average. This would be possible if there were only two or three
employees, but completely im practical to declare separate variables for
twenty or a hundred or a thousand employees.
The solution to this problem is to use an array. Arrays allow the storing
and m anipulating of large amounts of data. Three arrays are declared, one
to hold all the employee numbers, another for all the hourly rates and a
third for all the hours worked, as shown in Fig. 6-3. The information is
entered in such a way th a t the employee whose num ber is in box 2 receives
the rate in box 2 and worked the number of hours in box 2. Each person’s
gross pay is calculated and the average is found. Each person’s data is still
in memory and can quickly be examined to produce the list of people with
pay above the average.
367
Chương 6: Mảng và Chuỗi
employeeNuml
1 101
hourlyRatel
16251
1725I
ran
hoursWorkedl
grossPayl
1401
1381
FI
□
11
11
employeeNum2
hourlyRate2
hoursWorked2
grossPay2
11021
11031
hourlyRate3
hoursWorked3
grossPay3
employecNum3
Fig- 6-2 Individual variables íor three em ployees.
employeeNums
101
[01
102
[1]
103
[2]
104
[3]
105
[41
[n- 1 ]
hourlyRates
6.25
[0]
6.55
[1]
7.25
[2]
7.15
[3]
6.25
[4]
[n-11
hoursWorked
40
[0]
38
[1]
42
[2]
40
[3]
37
[4]
In-1]
gross Pay
[0]
[1]
[2]
[3]
[4]
ln-11
Fig. 6-3 Array variables for any number (n) of employees.
6.1.1 M a n ip u la tin g A rra y s – x ử lý các mảng
The entire array is declared once and known by one name. W hen it is
declared, the exact num ber of memory locations to be set aside is speci
fied. All the locations m ust contain data of the same type. Each e lem en t,
or individual memory location in the array, is accessible through the use
of its s u b s c r i p t or in d e x n u m b e r. F o r e x a m p le, in F ig. 6-3
em ployeeN um s[3] r e fe rs to th e e le m e n t in box n u m b e r 3 of th e
employeeNums array w hich contains “104,” or hourlyRates[4] would ac
cess the elem ent in box 4 of the hourlyRates array which contains “6.25.”
The subscripts usually begin with 0.
Input and output for an array is accom plished through the use of
loops. Each tim e through the loop a different box in the array is filled or
printed.
368
Chapter 6: Arrays and Strings
EXAM PLE 6.1 Pseudocode for a loop to f i l l or p rin t an array of n items
would look like this:
loop from lev = 0 to lev = n -1 where n is the total number of items in the array
input or output arrayllcv]
end loop
EXAM PLE 6.2 Most other processing of arrays also entails loops. One com
mon example is to calculate the sum of all the items in an integer array.
Pseudocode for summing an array would look like this:
set the sum to 0 before the loop starts
loop from lev = 0 to lev = n -1 where n is the total number of items in the array
add the arrayllcv] to the running sum
end loop
Specific processing of arrays in Visual Basic, c, C++, and Java is dem
onstrated later in th is chapter. Each language handles them in a slightly
different way. However, in all languages the program m er must be careful
not to try to process past the end of the array. For example, if there are 10
item s in the array called grossPay, located in boxes [0] through [9], a
statem ent including grossPay[20] would cause serious problems because
there is no memory location with th a t designation.
6.12 M u lti-D im e n s io n A rra y s – Các m ản g da c h iể u
Regular single-dimension arrays are good for processing lists of items.
Sometimes, however, two-dimensional arrays are necessary.
mySales
[0]
[1]
[2]
[3]
250
350
220
210
300
325
315
310
IẵL
325
400
210
295
Fig. 6-4 T w o-dim ensional array for sales.
E XAM PLE 6.3 A sales representative m ight have a report of th e sales for
each m onth of each quarter, as shown in Fig. 6-4. The rows [0] through
[3] rep resen t th e four quarters of the year. The columns [0] through [2]
represent the th ree m onths in each quarter. Each elem ent of th e array is
Chương 6: Mảng và Chuỗi
369
accessed through two subscripts, one for th e row and one for th e column,
in that order. For example, in Fig. 6-4 the contents of en try mySales[l][2]
IS “400.”
Two-dimensional arrays follow the rules of single-dimension arrays. The
array is declared specifying the number of memory locations desired by
stating the number of rows and the number of columns. Each item in the
array must contain the same type of data. The entire array has one name
and each elem ent is accessible through the use of its row and column
numbers.
Most processing of these arrays is accomplished through the use of nested
loops, one for the row and one for the column.
EXAMPLE 6.4 The pseudocode for printing a two-dimensional array looks
like this:
loop from row = 0 to row = n -1 where n is the number of rows in the array
loop from col = 0 to col = m -1 where m is the number of columns in the array
print out array[row][col]
end col loop
end row loop
Arrays -of more than two dimensions are possible, but rarely used. See
Solved Problems 6.4 and 6.5 at the end of the chapter for an example.
6.1.3 S trin g s – A S p e cia l K in d o f A rra y – C h uỗ i – Một kiểu mảng đặc biệt
The array examples we have seen so far have been numeric. It is also
possible to m anipulate arrays of characters. These arrays, usually called
strings, are a special type.of array because they are used so frequently. An
array of strings is implemented as a two-dimensional array of characters.
EXAMPLE 6.5 Draw single-dimension arrays to contain the following strings:
“JOAN,” “CHICAGO,” and “MAY” In addition, draw a two-dimensional a r
ray to contain the strings: “corn,” “w heat,” and “rye.”
The result is shown in Fig. 6-5.
370
Chapter 6: Arrays and String
myName
1
[01
J
1
[21
[11
o
1
[31
A
!
N
m
H
[21
1
1
[31
c
[1]
A
[21
Y
myCity
1
toi
C –
M
«nd string 1
M
LSI
G
161
o
13]
n
4]
end String
t
[51
A
m
1 and string 1
month
10]
1
M
[31
end string
grains
[01
[0]
c
m
w
[11
0
h
r
y
[21
[2]
r
e
e
a
end string
end string
F ig. 6-5 Strings in one and tw o dim ensions.
Each language implements and m anipulates strings differently. Usually
special kinds of processing commands are available. Many require some
indication of w here the string ends, as shown in th e previous example.
The following sections explain the use of arrays in specific languages. In
each of these languages we have considered the following topics: declaring
arrays, m anipulating arrays, two-dimensional arrays, strin g processing,
and arrays as param eters to functions.
HƯỚNG DẪN ĐỌC HIEU CHỦ DIEM 6.1 ____________________
6.1. G IỚ I T H IỆ U VỂ M ẢN G
Một m ảng là m ột nhóm các vị trí trong bộ nhớ có cùng kiểu và cùng
tên. Trước đây trog một chương trình đ ể tính số tiền p hải chi trả cho
nhân viên người dùng cần phải gõ nhập mã số của nhân viên, số
tiền chi trả và số giờ làm việc. Sẽ có một biến đ ể g iữ mỗi mảng
thông tin như m inh họa trong hình 6.1, rồi sau đó số tiền chi trả gộp
được tính toán.
employeeNum
hourlyRate
hoursWorked
grossPay
101
H ìn h 6.1 Các biến riêng biệt dành cho chi trả lương
__________________________________________ J
371
Chương 6: Mảng và Chuỗi
Nếu có nhiều nhăn viên thì chương trình có th ề có một vòng lặp
dành cho người dùng đ ể gõ nhập thông tin vào các biến giống nhau
dành cho người công nhăn thứ hai rồi tính khoảng tiền gộp mà
người dó nhận được, sau đó đến người thứ ba v,v…. Tuy nhiên, một
bài toán nảy sinh là nếu người chủ muốn có một bảng báo cáo có
chứa danh sách chi trả hàng tuần đối với tất cả các nhăn viên, mức
chi trả trung binh mỗi tuần mộtdanh sách tất cả các nhân viên nhận
số tiền bên trẽn mức chi trả trung bình. S ố tiền trung bình không
thể dược tính toán đến khi tất cả các nhăn viên được nhập xong. Để
so sánh mức nhận tiền của mỗi người với mức trung bình, tất cả
thông tin cần phải được nhập vào lần thứ hai.
Một giải pháp cho vấn đề này đó là bạn phải có một biến khác dành
cho mỗi nhăn viên như m inh họa trong hình 6.2. Mỗi khoảng chi trả
cho nhân viên phải được so sánh với giá trị trung bình. Điều này sẽ
có thể thực hiện được nếu chỉ có hai hoặc ba nhân viẽn, nhưng nó
hoàn toàn không thực tế khi bạn khai báo các biến riêng biệt dành
cho khoảng 20 hoặc 100 hoặc 1000 nhân viên.
Có một giải pháp cho vấn đề này đó là sử dụng một mảng. Các mảng
cho phép lưu trữ cách xử lý một lượng dữ liệu lớn. Ba mảng dược
khai báo, một d ể giữ tất cả các sô nhân viên, một dùng cho tẩtcả các
định mức chi trả theo giờ và thứ ba là dành cho tất cả giờ làm việc
như minh họa trong hình 6.3. Thông tin được nhập vào theo một
cách thức sao cho nhân viên có một con sô’ định danh nằ m trong ô 2
thì nhận được định mức lương trong ô 2. và hoạt động sô giờ nằm
trong ô 2. Mỗi khoản tiền chi trả gộp của cá nhânsẽ được tính toán
và tìm giá trị trung bình. Mỗi dữ liệu cá nhân vẫn nằm trong bộ nhớ
và có th ể nhanh chóng được xem xét tạo nên một danh sách những
người có mức chi trả bên trẽn mức trung binh.
hoursWorkedl
employeeNuml
hourlyRatel
I 101 1
1 625 1
1 40 1
bourlyRate2
hoursWorked2
employeeNunứ
1 102 1
1 725 1
employeeNum3
hourlyRale3
1 103 1
1 655 1
B
hoursWorkcd3
H
grossPayl
1
1
grossPay2
1
1
grossPay3
1
H ìn h 6.2 Các biến riêng biệt dành cho ba nhân viên
1
372
Chapter 6: Arrays and Stringt
employeeNums
101
10]
102
[11
103
[2]
104
[31
105
[41
ln-11
houriyRates
6.25
[0]
6.55
[11
7.25
[2]
7.15
[31
6.25
[41
in-11
hoursWorked
40
[0]
38
[1]
42
12]
40
[31
37
[41
ln-11
grossPay
[0}
[1]
[2]
[3]
[4]
[n-ề1]
H ìn h 6.3 Biến mảng dành cho bất cứ số nhăn viên nào.
6.1.1 X ử lỷ các m ả n g
Mảng tổng th ể sẽ được khai báo một lần và được biết dưới một tẽn.
Lúc được khai báo, sô chính xác của các vị trí bộ nhớ sẽ được xác lập
ở nơi được chỉ định. Tất cả vị trí phải có chứa dữ liệu cùng kiểu. Mỗi
yếu tố (element) hoặc vị trí bộ nhớ riêng biệt trong m ảng phải dược
thông qua việc sử dụng chỉ số hoặc số subscript. Ví dụ, trong hình
6.3, employeeNums[3] ám chỉ đến những yểu tố trong ô số 3 của
mảng employeeNUms có chứa “104”, hoặc hourlyRates[4] sẽ truy cập
yếu tố trong ô 4 với m ảng hourlyRates có chứa “6.25″. Các chi số
thường bắt dầu bằng số 0.
Dữ liệu nhập vào và xuấtra dành cho một m ảng được hoàn thành
thông qua việc sử dụng các vòng lặp. Mỗi lần thông qua vòng lặp có
m ột ô khác nhau trong mảng được điền vào hoặc được in.
V I D Ụ 6.1 Tạo mã giả cho một vòng lặp đ ể điền hoặc in một mảng
n hạng mục như dưới đây.
loop from lev = 0 to lev = n -1 where n is the tctal number of items in the arrm
input or out-put array[lev]
end loop
V I D Ụ 6.2 Hầu hết việc xử lý các m ảng củng chi tiết hóa các vòng
lặp. Một ví dụ p h ổ biến đó là tính tổng của tất cả các hạng mục trong
một m ảng nguyên. Lập mã giả d ể tính tổng một m ảng như dưới
đây.
set the sum to 0 before the loop starts
loop from lev = 0 to lev = n -1 where n is the total number of items in the array
add the arrayDcv] to the running sum
end loop
373
IChương 6: Máng và Chuỗi
Quy trình xử lý chuyên biệt của các mảng trong Visual Basic, C++ và
Java được m inh họa về sau trong chương này. Mỗi ngôn ngữ sẽ xù lý
chúng theo một cách thức hơi khác nhau. Tuy nhiên, trong tất cả các
ngôn ngữ người lập trình phải cẩn thận không được xử lý vượt quá sô
cuối của mảng. Ví dụ, nếu có 10 hạng mục trong một mảng được gọi
là grossPay, được đặt trong các 6 từ [0] đến [9], m ột câu lệnh
grossPay[20] sẽ xảy ra các vấn đề bởi vì chúng không có trong vị trí
nhớ với sư thiết kế.
6.1.2 Các m ản g n hiều ch iều (nhiều th ứ nguyên)
Các mảng một chiều bình thường thì tốt cho việc xử lý danh sách các
hạng mục. Tuy nhiên, đôi khi vẩn cần đến các m ảng hai chiều.
mySales
[0]
[11
[2]
[31
250
350
220
210
300
325
315
310
I2L
325
400
210
295
H ìn h 6.4 M ảng hai chiều cho việc kinh doanh
V í D Ụ 6.3 Một người đại diện bán hàng có th ể có một bản báo cáo về
việc kinh doanh hàng tháng của mỗi quý, như m inh họa trong hình
6.4. Các hàng từ [0] đến [3] đại diện cho 4 quý trong năm. các cột từ
[0] đến [12] đại diện cho 3 tháng trong mỗi quý. Mỗi thành phần
của mảng được tiếp cận thông qua 2 chl số, một chỉ số cho hàng và
một chi số cho cột theo thứ tự. Ví dụ, ở hình 6.4, nội dung cùa
mySales[lJ[2] nhập vào là 400.
Các máng hai chiều tuân theo quy tác của các màng một chiều. Màng này
dược khai báo bàng các xác định số vị trí nhớ mong muốn khi khai báo số
hàng hay số cột. Toàn bộ màng có một tên và mỗi thành phần có thể tiếp cận
được bàng cách dùng số hàng và số cột của nó.
Phần lớn quy trình xử lý mảng được thực hiện bàng cách sử dụng các
vòng lặp lồng, m ột vòng lặp cho hàng và một vòng lặp cho cột.
V Í D Ụ 6.4 Mã giả đ ể in một mảng hai chiều có dạng như sau:
loop from row = 0 to row = n -1 where n is the number of rows in the array
loop from col = 0 to col = m -1 where m is the number of columns in the array
p rin t out array[row][col]
end col loop
end row loop
374
Chapter 6.ểArrays and Strings
Cũng có th ể có khả năng nhiều han hai chiểu nhưng rắt ít được sù
dụng đ ể xem ví dụ.. Xem phần các bài tập có lời giải 6.4 và 6.5 ở cuối
chương
6.1.3 Các ch u ỗi – M ột lo ạ i m ản g d ặ c b iệ t
Các ví dụ về mảng mà chúng ta đã xem xét là những con số. Ngoài
ra ta vẫn có th ể xử lý các mảng ký tự. N hững m ảng này thường được
gọi là các chuỗi, đây là một loại mảng đặc biệt bài vì chúng được
dùng thường xuyên. Một máng các chuỗi được thực thi dưới dạng một
m ảng các ký tự hai chiểu.
VI D Ụ 6.5 Hãy vẽ các mảng mộtchiều có chứa các chuỗi sau đây:
JO A N ”, “CHICAGO”, và “M AY”. Bên cạnh đó, hãy vẽ một mảng hai
chiều có chứa các chuỗi “corn”, wheat”, và “rye”.
Kết quả được m inh họa trong hình 6.5
myNam e
[01
[11
0
[2]
A
C
[1]
H
[2]
I
month
[0]
1
M
[1]
A
[2]
[0]
11]
[2]
toi
c
w
r
1
J
myCity
[01
1
I
I
[3]
N
[4]
I •rid string 1
[31
C
4]
A
[5]
G
[6]
°
[3]
n
a
0
[5]
•ndrtrtng
t
•nd string
m
•nd string 1
[3]
üü
grains
[1 ]
0
h
y
Í21
r
e
e
and string
H ình 6.5 Các chuỗi một chiều và hai chiểu
Mỗi ngôn ngữ thực thi và xử lý các chuỗi theo một cách thức khác
nhau. Thông thường các loại lệnh xử lý đặc biệt đều có sản. Có nhiều
loại yẽu cầu m ột vài chỉ định nơi mà chuỗi phải kết thúc như minh
họa ở ví dụ trước đây.
Phần sau đây giải thích cách dùng các m ảng theo các ngôn ngữ đặc
biệt. Trong mỗi một ngôn ngữ này chúng ta phải xem xét các chủ
điểm sau đây: khai báo mảng, xử lý mảng, các m ảng hai chiều, xử lý
chuỗi và các m ảng được chọn làm tham sô cho các hàm..
Source: https://khoinganhcntt.com
Category: NGÀNH TUYỂN SINH