Bài giảng Kỹ thuật lập trình - Chương 3: Mảng, chuỗi và hàm

LOGO
Chương III
Mảng, Chuỗi và Hàm
COMPANY LOGO
www.themegallery.com
Nội dung chính
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 2
3.1. Mảng
3.2. Chuỗi
3.3. Mảng chuỗi
3.4. Hàm
3.5. Đệ quy
3.6. Hàm và mảng dữ liệu
3.7. Tổ chức chương trình
COMPANY LOGO
www.themegallery.com
3.1 Mảng
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 3
Mảng là tập hợp các phần tử có cùng kiểu dữ liệu được 
sắp xếp liền kề nhau trong bộ nhớ.
A. Mảng một chiều
Cú pháp khai báo:
• [số thành phần] ; // không khởi tạo
• [số thành phần] = { dãy giá trị } ; 
/* có khởi tạo */
• [ ] = { dãy giá trị } ; // có khởi tạo
Cách sử dụng: Để chỉ thành phần thứ i (hay chỉ số i) của một
mảng ta viết tên mảng kèm theo chỉ số trong cặp ngoặc vuông [].
Mảng A A[0] A[1] A[2] A[3] A[4] A[5] A[6]
COMPANY LOGO
www.themegallery.com
Ví dụ: Tìm phần tử nhỏ nhất của mảng một chiều
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 4
#include
using namespace std;
int main()
{
float a[100], min;// a chứa tối đa 100 số
int i, n;
cout> n;
for (i = 0; i<n; i++) 
{ cout>a[i] ; }
min = a[0];
for (i = 1; i<n; i++) 
if (a[i] < min) min = a[i];
cout << "So be nhat la " << min << '\n';
}
COMPANY LOGO
www.themegallery.com
3.1 Mảng
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 5
B. Mảng nhiều chiều
Để thuận tiện trong việc biểu diễn các loại dữ liệu phức
tạp như ma trận hoặc các bảng biểu có nhiều chỉ tiêu, C++ đưa ra
kiểu dữ liệu mảng nhiều chiều. Tuy nhiên, việc sử dụng mảng
nhiều chiều rất khó lập trình vì vậy trong mục này chúng ta chỉ
bàn đến mảng hai chiều.
COMPANY LOGO
www.themegallery.com
3.1 Mảng
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 6
Hình bên minh họa mảng
2 chiều với 3 dòng và 4 cột.
Thực chất trong bộ nhớ,
tất cả 12 phần tử của mảng
được sắp liên tiếp theo từng
dòng của mảng như minh hoạ
trong hình dưới đây.
0 1 2 3
0 A[0][0] A[0][1] A[0][2] A[0][3]
1 A[1][0] A[1][1] A[1][2] A[1][3]
2 A[2][0] A[2][1] A[2][2] A[2][3]
A[0][0] A[0][1] A[0][2] A[0][3] A[1][0] A[1][1] A[1][2] A[1][3] A[2][0] A[2][1] A[2][2] A[2][3]
Dòng 0 Dòng 1 Dòng 2
COMPANY LOGO
www.themegallery.com
Mảng hai chiều
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 7
Cú pháp khai báo:
 [m][n] ;
– m, n là số hàng, số cột của mảng.
– Kiểu thành phần là kiểu của m*n phần tử trong mảng.
– Trong khai báo cũng có thể được khởi tạo bằng dãy các dòng
giá trị, các dòng cách nhau bởi dấu phẩy, mỗi dòng được bao
bởi cặp ngoặc {} và toàn bộ giá trị khởi tạo nằm trong cặp
dấu {}.
Sử dụng: Để truy nhập phần tử của mảng ta sử dụng tên mảng
kèm theo 2 chỉ số chỉ vị trí hàng và cột của phần tử. Các chỉ số
này có thể là các biểu thức thực, khi đó C++ sẽ tự chuyển kiểu
sang nguyên.
COMPANY LOGO
www.themegallery.com
Ví dụ: Tìm phần tử nhỏ nhất của mảng hai chiều
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 8
#include
using namespace std;
int main()
{
float a[100][100], min;// a chứa tối đa 10000 số
int i, j, m, n;
cout> m>> n;
for (i = 0; i<m; i++)
for (j = 0; j<n; j++)
{ cout>a[i][j]; }
min = a[0][0];//Gán min bằng phần tử đầu tiên
for (i = 1; i<n; i++)
for (j = 0; j < n; j++)
if (a[i][j] < min) min = a[i][j];
cout << "So be nhat la " << min << '\n';
}
COMPANY LOGO
www.themegallery.com
3.2 Chuỗi
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 9
Chuỗi hay xâu kí tự là một mảng các kí tự bất kì được kết thúc
bằng kí tự ‘\0’.
Hình vẽ trên minh hoạ 3 xâu, mỗi xâu được chứa trong mảng kí tự
có độ dài tối đa là 8. Nội dung xâu thứ nhất là “TINHOC" có độ dài
thực tế là 6 kí tự, chiếm 7 ô trong mảng (thêm ô chứa kí tự kết thúc '\0').
Xâu thứ hai có nội dung “TIN" với độ dài 3 (chiếm 4 ô) và xâu cuối
cùng biểu thị một xâu rỗng (chiếm 1 ô).
Chú ý : Mảng kí tự được khai báo với độ dài 8 tuy nhiên các xâu
có thể chỉ chiếm một số kí tự nào đó trong mảng này và tối đa là 7 kí tự.
0 1 2 3 4 5 6 7
T I N H O C \0
T I N \0 H O C \0
\0 T I H O C \0
COMPANY LOGO
www.themegallery.com
3.2 Chuỗi
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 10
Khai báo chuỗi:
char [độ dài] ; // không khởi tạo
char [độ dài] = xâu kí tự ; // có khởi tạo
char [] = xâu kí tự ; // có khởi tạo
‒ Độ dài mảng là số kí tự tối đa có thể có trong xâu. Độ dài thực sự
của xâu chỉ tính từ đầu mảng đến dấu kết thúc xâu (không kể dấu kết
thúc xâu ‘\0’). Do vậy trong khai báo độ dài của mảng cần phải khai
báo thừa ra một phần tử.
‒ Cách khai báo thứ hai có kèm theo khởi tạo xâu, đó là dãy kí tự đặt
giữa cặp dấu nháy kép.
‒ Cách khai báo thứ 3 tự chương trình sẽ quyết định độ dài của mảng
bởi xâu khởi tạo (bằng độ dài xâu + 1).
Ví dụ:
char thang[] = "Muoi hai" ; // độ dài mảng = 9
COMPANY LOGO
www.themegallery.com
3.2 Chuỗi
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 11
Cách sử dụng: Sử dụng tương tự như mảng các giá trị số
Nhập chuỗi với hàm cin.getline(s, n);
Ví dụ:
#include
using namespace std;
int main()
{
char hoten[25];
cout<< "Nhap vao ho ten:\n";
cin.getline(hoten, 24);
cout << "Xin chao: " <<hoten<< '\n';
}
COMPANY LOGO
www.themegallery.com
Một số hàm xử lý chuỗi trong #include
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 12
• strcpy(s, t) ;
Hàm sẽ sao chép toàn bộ nội dung của xâu t (kể cả kí tự kết thúc
xâu ‘\0’) vào cho xâu s. Để sử dụng hàm này cần đảm bảo độ dài của
mảng s ít nhất cũng bằng độ dài của mảng t. Trong trường hợp ngược lại
kí tự kết thúc xâu sẽ không được ghi vào s và điều này có thể gây treo
máy khi chạy chương trình.
Ví dụ: #include
#include
using namespace std;
int main()
{
char s[10], t[10];
strcpy(t,"Face");// được, gán "Face" cho t
strcpy(s,t);// được, sao chép t sang s
cout << s << " to " << t<<'\n'; // in ra: Face to Face
}
COMPANY LOGO
www.themegallery.com
Một số hàm xử lý chuỗi trong #include
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 13
• strncpy(s, t, n) ;
Sao chép n kí tự của t vào s. Hàm này chỉ làm nhiệm vụ sao
chép, không tự động gắn kí tự kết thúc xâu cho s. Do vậy NSD
phải thêm lệnh đặt kí tự '\0' vào cuối xâu s sau khi sao chép xong.
Ví dụ: #include
#include
using namespace std;
int main()
{
char s[15], t[20] = "Tin hoc dai cuong";
strncpy(s, t, 3); // copy 3 kí tự "Tin" vào s
s[3]=' '; //Gán kí tự khoảng trống cho s[3]
strncpy(s+4, t+8, 9); //copy "dai cuong" vào s từ vị trí thứ 4
s[13] = '\0'; // kết thúc xâu s
cout <<"Chuoi s la: " << s<<'\n'; //Xuất ra “Tin dai cuong”
}
COMPANY LOGO
www.themegallery.com
Một số hàm xử lý chuỗi trong #include
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 14
• strcat(s, t);
Nối một bản sao của t vào sau s (thay cho phép +). Hiển nhiên
hàm sẽ loại bỏ kí tự kết thúc xâu s trước khi nối thêm t. Việc nối
sẽ đảm bảo lấy cả kí tự kết thúc của xâu t vào cho s (nếu s đủ chỗ)
vì vậy NSD không cần thêm kí tự này vào cuối xâu.
Ví dụ: #include
#include
using namespace std;
int main()
{
char a[100] = "Nam", b[4] = "Bac";
strcat(a, " va ");
strcat(a, b);
cout << a; //Sẽ xuất ra “Nam va Bac”
}
COMPANY LOGO
www.themegallery.com
Một số hàm xử lý chuỗi trong #include
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 15
• strncat(s, t, n);
Nối bản sao n kí tự đầu tiên của xâu t vào sau xâu s. Hàm tự
động đặt thêm dấu kết thúc xâu vào s sau khi nối xong.
Tương tự, có thể sử dụng cách viết strncat(s, t+k, n) để nối n
kí tự từ vị trí thứ k của xâu t cho s.
• strcmp(s, t);
Hàm so sánh 2 xâu s và t (thay cho các phép toán so sánh).
Giá trị trả lại là hiệu 2 kí tự khác nhau đầu tiên của s và t. Từ đó,
nếu s1 < s2 thì hàm trả lại giá trị âm, bằng 0 nếu s1==s2, và
dương nếu s1 > s2. Trong trường hợp chỉ quan tâm đến so sánh
bằng, nếu hàm trả lại giá trị 0 là 2 xâu bằng nhau và nếu giá trị trả
lại khác 0 là 2 xâu khác nhau.
COMPANY LOGO
www.themegallery.com
Một số hàm xử lý chuỗi trong #include
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 16
• strncmp(s, t, n) ;
Giống hàm strcmp(s, t) nhưng chỉ so sánh tối đa n kí tự đầu
tiên của hai xâu.
• strcmpi(s, t) ;
Như strcmp(s, t) nhưng không phân biệt chữ hoa, thường.
• strupr(s);
Hàm đổi xâu s thành in hoa, và cũng trả lại xâu in hoa đó.
• strlwr(s);
Hàm đổi xâu s thành in thường, kết quả trả lại là xâu s.
• strlen(s) ;
Hàm trả giá trị là độ dài của xâu s.
COMPANY LOGO
www.themegallery.com
3.3 Mảng chuỗi
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 17
Mảng chuỗi là mảng trong đó các phần tử của nó là một chuỗi.
Cú pháp khai báo :
Trong đó : kích_thước là số lượng phần tử tối đa của mảng,
độ_dài_chuỗi là kích thước của các phần tử.
Để truy cập đến các phần tử ta chỉ cần viết tên mảng kèm chỉ số
của nó ở trong cặp dấu [] đầu tiên.
char Tên_mảng[Kích_thước][độ_dài_chuỗi];
COMPANY LOGO
www.themegallery.com
Ví dụ về mảng chuỗi
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 18
#include
using namespace std;
int main()
{
char Sinh_vien[10][25]; //Mảng Sinh_vien gồm 10 chuỗi
int i;
for( i=0; i<10; i++)
{
cout<<"Nhap vao ho va ten sinh vien thu " <<i+1<<" :\n";
cin.getline(Sinh_vien[i], 24);//Nhập tối đa 24 kí tự cho chuỗi Sinh_vien[i]
}
cout<<"Danh sach sinh vien vua nhap la: \n";
for( i=0; i<10; i++)
cout<<"Sinh vien thu "<<i+1<<": "<<Sinh_vien[i]<<"\n";
}
COMPANY LOGO
www.themegallery.com
3.4 Hàm
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 19
 Định nghĩa hàm:
Hoặc :
Lưu ý: C không cho phép các hàm lồng nhau, nghĩa là phần
định nghĩa của hàm này phải độc lập hoàn toàn với hàm khác.
Kiểu_trả_về tên_hàm (kiểu và danh_sách_tham_số)
{
/* thân hàm */
Các_câu_lệnh ;
return giá_trị ;
}
#define Tên_hàm(Các_tham_số) Biểu_thức_Giá_trị
COMPANY LOGO
www.themegallery.com
3.4 Hàm
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 20
 Khai báo nguyên mẫu hàm : Khai báo nguyên mẫu hàm sẽ
cung cấp cho trình biên dịch mô tả về một hàm sẽ được định
nghĩa ở một vị trí nào đó trong chương trình:
 Gọi hàm:
 Trong danh_sách_đối_số không đưa ra kiểu dữ liệu của đối
số. Nếu hàm cần truyền nhiều đối số thì chúng phải tách nhau bởi
dấu phẩy. Nếu đối số là mảng thì chỉ cần ghi tên mảng.
Kiểu_trả_về tên_hàm (kiểu và danh_sách_tham_số);
Tên_hàm (danh_sách_đối_số) ;
COMPANY LOGO
www.themegallery.com
Ví dụ 1: Định nghĩa và gọi hàm tính giai thừa
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 21
#include
using namespace std;
long factorial(int n); //Khai báo nguyên mẫu cho hàm factorial
int main()
{
cout<<"6! = "<<factorial(6); //Gọi hàm factorial với tham số là 6
}
long factorial(int n)//Định nghĩa hàm factorial với 1 tham số nguyên n
{
long p=1, i;
if(n>=0) // Chỉ tính giai thừa cho số không âm
{ for( i=2; i<=n; i++) p*= i;
return p; //Trả về cho hàm factorial giá trị bằng p
}
else cout<< "Khong tinh duoc giai thua so am";
}
COMPANY LOGO
www.themegallery.com
Ví dụ 2: Hàm tính giá trị lớn nhất của 3 số
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 22
#include
using namespace std;
#define max(a,b,c) a>b?(a>c?a:c):(b>c?b:c)
int main()
{
int x, y, z, t;
cout<<"Nhap vao 3 so nguyen:\n";
cin>>x>>y>>z;
cout<<"So lon nhat trong ba so vua nhap la: ";
t=max(x,y,z); //Gọi hàm max
cout<< t;
}
COMPANY LOGO
www.themegallery.com
3.5 Đệ quy
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 23
 Hàm đệ quy là hàm mà từ một điểm trong thân của nó có thể
gọi tên hàm của chính nó.
 Cấu trúc tổng quát của hàm đệ qui thường như sau:
if (trường hợp cơ sở)
{
trình bày cách giải // giả định đã có cách giải
}
else // trường hợp tổng quát
{
Gọi lại hàm với tham đối "bé" hơn
}
COMPANY LOGO
www.themegallery.com
Ví dụ 1: Hàm đệ quy tính UCLN của 2 số
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 24
#include
using namespace std;
int UCLN(int a, int b)
{
if(a==b)return a; //Trường hợp cơ sở
if(a>b)return UCLN(a-b, b); //Thuật toán Euclid
if(a<b)return UCLN(a, b-a);
}
int main()
{
int x, y, uc;
cout>x>>y;
cout<<"UCLL cua 2 so "<<x<<" va "<<y<<" la: "<< UCLN(x,y);
}
COMPANY LOGO
www.themegallery.com
Ví dụ 2: Tính số hạng thứ n của dãy Fibonaci
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 25
#include
using namespace std;
int Fibo(int n)
{
if(n==1)return 0;//Phần tử đầu tiên bằng 0
if(n==2)return 1;//Phần tử thứ 2 bằng 1
if(n>2)return Fibo(n-1)+ Fibo(n-2);
//Phần tử thứ n bằng tổng của (phần tử thứ n-1) và (phần tử thứ n-2)
}
int main()
{
cout<<"Phan tu thu 7 cua day Fibonacci la: "; cout<<Fibo(7);
cout<<"\n8 phan tu dau tien cua day Fibonacci la:\n";
for(int i=1; i<=8; i++)
cout<<Fibo(i)<<"\t";
}
COMPANY LOGO
www.themegallery.com
3.6 Hàm và mảng dữ liệu
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 26
#include // Ví dụ minh họa hàm và mảng một chiều
using namespace std;
void sort(int a[], int size) //Hàm sắp xếp mảng tăng dần
{
int i, j, t;
for(i=0; i<size-1; i++)
for(j=i+1; j<size; j++)
if(a[i]>a[j]) //Nếu phần tử a[i]>a[j] ( a[j] - Các phần tử sau a[i])
{ t=a[i]; a[i]=a[j]; a[j]=t; } //hoán đổi a[i] cho a[j]
}
int main()
{
int a[8]={1,5,2,9,8,7,0,3}; sort(a,8); // Sắp xếp mảng a tang dần
for(int i=0; i<8; i++) cout<<a[i]<<"\t";
}
COMPANY LOGO
www.themegallery.com
3.6 Hàm và mảng dữ liệu
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 27
#include// Ví dụ minh họa hàm và mảng hai chiều
using namespace std;
int MAX(int a[][50], int row, int col) //row và col là số hàng và cột của mảng
{
int i, j, mc =a[0][0];//biến mc gán bằng phần tử đầu tiên của mảng
for(i=0;i<row;i++)
for(j=0;j<col;j++)
if(a[i][j]>mc) mc=a[i][j];
return mc; //Trả về mc (chính là giá trị lớn nhất của mảng) cho hàm MAX
}
int main()
{
int b[][50]={{2,15},{21,8},{16,-3}};// Số cột phải bằng 50 – như trong MAX
cout<<"Phan tu lonn nhat cua mang la: "<<MAX(b,3,2);
// Mảng b truyền vào hàm MAX với số hàng là 3, số cột là 2
}
COMPANY LOGO
www.themegallery.com
3.7 Tổ chức chương trình
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 28
 Các loại biến và phạm vi
 Biến cục bộ
 Biến ngoài hay biến toàn cục
 Biến với mục đích đặc biệt
 Biến hằng và từ khóa const
 Biến tĩnh và từ khóa static
 Biến thanh ghi và từ khóa register
 Biến ngoài và từ khóa extern
 Các chỉ thị tiền xử lý
 Chỉ thị bao hàm tệp #include
 Chỉ thị macro #define
 Chỉ thị #ifdef và #ifndef
COMPANY LOGO
www.themegallery.com
Bài tập chương III
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 29
Viết chương trình giải các bài tập sau ( nên dùng hàm) :
Bài 1. Nhập dữ liệu cho dãy số nguyên gồm n phần tử (n<=50).
A. Xác định số phần tử là số chẵn mà lớn hơn 30 trong mảng
B. Tìm giá trị nhỏ nhất trong mảng và số lần xuất hiện của nó
C. Sắp xếp mảng tăng dần
D. Xóa tất cả các phần tử có giá trị bằng x ở trong mảng
E. Chèn vào mảng phần tử y sao cho mảng vẫn tăng dần.
Bài 2. Nhập dữ liệu cho 2 ma trận số nguyên A và B đều gồm m
hàng n cột.
A. Xuất từng ma trận và ma trận tổng A+B
B. Tìm phần tử lớn nhất trên từng ma trận và trên cả 2 ma trận
C. Tổng các phần tử trên ma trận nào là lớn hơn
D. Sắp xếp ma trận A tăng dần, ma trận B giảm dần
COMPANY LOGO
www.themegallery.com
Bài tập chương III
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 30
Bài 4. Nhập dữ liệu cho xâu kí tự str[100]
A. Xuất ra màn hình xâu str
B. Xâu str có bao nhiêu kí tự và trong đó bao nhiêu kí tự là số
C. Loại bỏ các kí tự không phải là chữ hoặc không phải khoảng
trống trong xâu str
D. Đổi chữ thường trong xâu str thành chữ in hoa
E. Chèn vào xâu str một xâu str2 khác vào vị trí bất kì trong str.
Bài 5. Nhập dữ liệu cho mảng chuỗi A gồm n sinh viên (n<=50).
A. Xuất các chuỗi trong A ra màn hình
B. Tìm xem trong A có bao nhiêu người có họ là “Nguyen”
C. Dựa vào họ hãy sắp xếp A tăng dần (a z).
D. Xuất ra màn hình tên của các sinh viên dưới dạng chữ in hoa.
COMPANY LOGO
www.themegallery.com
Bài tập chương III
Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 31
Bài 6. Viết hàm đệ qui tính n!
A. Tính tổ hợp chập k của n phần tử ( Nếu tồn tại)
B. Tính hệ số của số hạng thứ k trong khai triển nhị thức Newton 
của : ( + )
C. Xuất ra tất cả các hệ số của khai triển nhị thức ở câu B trên
D. Xuất ra màn hình tam giác Pascal
Bài 7. Viết hàm đệ qui tính số fibonaci thứ n. 
A. Xuất ra n phần tử đầu tiên của dãy Fibonacci
B. Xuất ra màn hình k phần tử chẵn đầu tiên của dãy Fibonacci
C. Xuất ra phần tử lẻ thứ m của dãy Fibonacci
( Cho dãy Fibonacci: 0,1, 1, 2, 3, 5, 8, 13, 21,.)
Bài 8. Tính: với n dấu căn33331 ...S
LOGO
www.themegallery.com