Lập trình C++ - Chương 5: Mảng, con trỏ, tham chiếu

*); 
 Với định nghĩa trên của Compare thì hàm strcmp hoặc có thể được gọi trực 
tiếp hoặc có thể được gọi gián tiếp thông qua Compare. Ba lời gọi hàm sau là 
tương đương: 
strcmp("Tom", "Tim"); // gọi trực tiếp 
(*Compare)("Tom", "Tim"); // gọi gián tiếp 
Compare("Tom", "Tim"); // gọi gián tiếp (ngắn gọn) 
 Cách sử dụng chung của con trỏ hàm là truyền nó như một đối số tới một 
hàm khác; bởi vì thông thường các hàm sau yêu cầu các phiên bản khác nhau 
của hàm trước trong các tình huống khác nhau. Một ví dụ dễ hiểu là hàm tìm 
Chapter 5: Mảng, con trỏ, và tham chiếu 68 
kiếm nhị phân thông qua một mảng sắp xếp các chuỗi. Hàm này có thể sử 
dụng một hàm so sánh (như là strcmp) để so sánh chuỗi tìm kiếm ngược lại 
chuỗi của mảng. Điều này có thể không thích hợp đối với tất cả các trường 
hợp. Ví dụ, hàm strcmp là phân biệt chữ hoa hay chữ thường. Nếu chúng ta 
thực hiện tìm kiếm theo cách không phân biệt dạng chữ sau đó một hàm so 
sánh khác sẽ được cần. 
 Như được trình bày trong Danh sách 5.8 bằng cách để cho hàm so sánh 
một tham số của hàm tìm kiếm, chúng ta có thể làm cho hàm tìm kiếm độc 
lập với hàm so sánh. 
Danh sách 5.8 
1 
 2 
3 
 4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
int BinSearch (char *item, char *table[], int n, 
 int (*Compare)(const char*, const char*)) 
{ 
 int bot = 0; 
 int top = n - 1; 
 int mid, cmp; 
 while (bot <= top) { 
 mid = (bot + top) / 2; 
 if ((cmp = Compare(item,table[mid])) == 0) 
 return mid; // tra ve chi so hangg muc 
 else if (cmp < 0) 
 top = mid - 1; // gioi hạn tim kiem toi nua thap hon 
 else 
 bot = mid + 1; // gioi han tim kiem toi nua cao hon 
 } 
 return -1; // khong tim thay 
} 
Chú giải 
1 Tìm kiếm nhị phân là một giải thuật nổi tiếng để tìm kiếm thông qua một 
danh sách các hạng mục đã được sắp xếp. Danh sách tìm kiếm được biểu 
diễn bởi table – một mảng các chuỗi có kích thước n. Hạng mục tìm kiếm 
được biểu thị bởi item. 
2 Compare là con trỏ hàm được sử dụng để so sánh item với các phần tử của 
mảng. 
7 Ở mỗi vòng lặp, việc tìm kiếm được giảm đi phân nữa. Điều này được 
lặp lại cho tới khi hai đầu tìm kiếm giao nhau (được biểu thị bởi bot và 
top) hoặc cho tới khi một so khớp được tìm thấy. 
9 Hạng mục được so sánh với mục ở giữa của mảng. 
10 Nếu item khớp với hạng mục giữa thì trả về chỉ mục của phần sau. 
11 Nếu item nhỏ hơn hạng mục giữa thì sau đó tìm kiếm được giới hạn tới 
nữa thấp hơn của mảng. 
14 Nếu item lớn hơn hạng mục giữa thì sau đó tìm kiếm được giới hạn tới 
nữa cao hơn của mảng.. 
Chapter 5: Mảng, con trỏ, và tham chiếu 69 
16 Trả về -1 để chỉ định rằng không có một hạng mục so khớp. 
 Ví dụ sau trình bày hàm BinSearch có thể được gọi với strcmp được truyền 
như hàm so sánh như thế nào: 
char *cities[] = {"Boston", "London", "Sydney", "Tokyo"}; 
cout << BinSearch("Sydney", cities, 4, strcmp) << '\n'; 
Điều này sẽ xuất ra 2 như được mong đợi. 
5.7. Tham chiếu 
Một tham chiếu (reference) là một biệt hiệu (alias) cho một đối tượng. Ký 
hiệu được dùng cho định nghĩa tham chiếu thì tương tự với ký hiệu dùng cho 
con trỏ ngoại trừ & được sử dụng thay vì *. Ví dụ, 
double num1 = 3.14; 
double &num2 = num1; // num2 là một tham chiếu tới num1 
định nghĩa num2 như là một tham chiếu tới num1. Sau định nghĩa này cả hai 
num1 và num2 tham khảo tới cùng một đối tượng như thể chúng là cùng biến. 
Cần biết rõ là một tham chiếu không tạo ra một bản sao của một đối tượng mà 
chỉ đơn thuần là một biệt hiệu cho nó. Vì vậy, sau phép gán 
num1 = 0.16; 
cả hai num1 và num2 sẽ biểu thị giá trị 0.16. 
 Một tham chiếu phải luôn được khởi tạo khi nó được định nghĩa: nó là 
một biệt danh cho cái gì đó. Việc định nghĩa một tham chiếu rồi sau đó mới 
khởi tạo nó là không đúng luật. 
double &num3; // không đúng luật: tham chiếu không có khởi tạo 
num3 = num1; 
 Bạn cũng có thể khởi tạo tham chiếu tới một hằng. Trong trường hợp 
này, một bản sao của hằng được tạo ra (sau khi bất kỳ sự chuyển kiểu cần 
thiết nào đó) và tham chiếu được thiết lập để tham chiếu tới bản sao đó. 
int &n = 1; // n tham khảo tới bản sao của 1 
Lý do mà n lại tham chiếu tới bản sao của 1 hơn là tham chiếu tới chính 1 là 
sự an toàn. Bạn hãy xem xét điều gì sẽ xảy ra trong trường hợp sau: 
int &x = 1; 
++x; 
int y = x + 1; 
1 ở hàng đầu tiên và 1 ở hàng thứ ba giống nhau là cùng đối tượng (hầu hết 
các trình biên dịch thực hiện tối ưu hằng và cấp phát cả hai 1 trong cùng một 
vị trí bộ nhớ). Vì thế chúng ta mong đợi y là 3 nhưng nó có thể chuyển thành 
Chapter 5: Mảng, con trỏ, và tham chiếu 70 
4. Tuy nhiên, bằng cách ép buộc x là một bản sao của 1 nên trình biên dịch 
đảm bảo rằng đối tượng được biểu thị bởi x sẽ khác với cả hai 1. 
 Việc sử dụng chung nhất của tham chiếu là cho các tham số của hàm. 
Các tham số của hàm thường làm cho dễ dàng kiểu truyền-bằng-tham chiếu, 
trái với kiểu truyền-bằng-giá trị mà chúng ta sử dụng đến thời điểm này. Để 
quan sát sự khác nhau hãy xem xét ba hàm swap trong Danh sách 5.9. 
Danh sách 5.9 
1 
 2 
3 
 4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
void Swap1 (int x, int y) // truyền bằng trị (đối tượng) 
{ 
 int temp = x; 
 x = y; 
 y = temp; 
} 
void Swap2 (int *x, int *y) // truyền bằng địa chỉ (con trỏ) 
{ 
 int temp = *x; 
 *x = *y; 
 *y = temp; 
} 
void Swap3 (int &x, int &y) // truyền bằng tham chiếu 
{ 
 int temp = x; 
 x = y; 
 y = temp; 
} 
Chú giải 
1 Mặc dù Swap1 chuyển đối x và y, điều này không ảnh hưởng tới các đối 
số được truyền tới hàm bởi vì Swap1 nhận một bản sao của các đối số. 
Những thay đổi trên bản sao thì không ảnh hưởng đến dữ liệu gốc. 
7 Swap2 vượt qua vấn đề của Swap1 bằng cách sử dụng các tham số con trỏ 
để thay thế. Thông qua giải tham khảo (dereferencing) các con trỏ Swap2 
lấy giá trị gốc và chuyển đổi chúng. 
13 Swap3 vượt qua vấn đề của Swap1 bằng cách sử dụng các tham số tham 
chiếu để thay thế. Các tham số trở thành các biệt danh cho các đối số 
được truyền tới hàm và vì thế chuyển đổi chúng khi cần. 
 Swap3 có thuận lợi thêm, cú pháp gọi của nó giống như Swap1 và không 
có liên quan đến định địa chỉ (addressing) hay là giải tham khảo 
(dereferencing). Hàm main sau minh họa sự khác nhau giữa các lời gọi hàm 
Swap1, Swap2, và Swap3. 
int main (void) 
{ 
 int i = 10, j = 20; 
 Swap1(i, j); cout << i << ", " << j << '\n'; 
 Swap2(&i, &j); cout << i << ", " << j << '\n'; 
Chapter 5: Mảng, con trỏ, và tham chiếu 71 
 Swap3(i, j); cout << i << ", " << j << '\n'; 
} 
Khi chạy chương trình sẽ cho kết quả sau: 
10, 20 
20, 10 
20, 10 
5.8. Định nghĩa kiểu 
Typedef là cú pháp để mở đầu cho các tên tượng trưng cho các kiểu dữ liệu. 
Như là một tham chiếu định nghĩa một biệt danh cho một đối tượng, một 
typedef định nghĩa một biệt danh cho một kiểu. Mục đích cơ bản của nó là để 
đơn giản hóa các khai báo kiểu phức tạp khác như một sự trợ giúp để cải 
thiện khả năng đọc. Ở đây là một vài ví dụ: 
typedef char *String; 
typedef char Name[12]; 
typedef unsigned int uint; 
Tác dụng của các định nghĩa này là String trở thành một biệt danh cho char*, 
Name trở thành một biệt danh cho một mảng gồm 12 char, và uint trở thành 
một biệt danh cho unsigned int. Vì thế: 
String str; // thì tương tự như: char *str; 
Name name; // thì tương tự như: char name[12]; 
uint n; // thì tương tự như: unsigned int n; 
 Khai báo phức tạp của Compare trong Danh sách 5.8 là một minh họa tốt 
cho typedef: 
typedef int (*Compare)(const char*, const char*); 
int BinSearch (char *item, char *table[], int n, Compare comp) 
{ 
 //... 
 if ((cmp = comp(item, table[mid])) == 0) 
 return mid; 
 //... 
} 
typedef mở đầu Compare như là một tên kiểu mới cho bất kỳ hàm với nguyên 
mẫu (prototype) cho trước. Người ta cho rằng điều này làm cho dấu hiệu của 
BinSearch đơn giản hơn. 
Chapter 5: Mảng, con trỏ, và tham chiếu 72 
Bài tập cuối chương 5 
5.1 Định nghĩa hai hàm tương ứng thực hiện nhập vào các giá trị cho các phần tử 
của mảng và xuất các phần tử của mảng: 
void ReadArray (double nums[], const int size); 
void WriteArray (double nums[], const int size); 
5.2 Định nghĩa một hàm đảo ngược thứ tự các phần tử của một mảng số thực: 
void Reverse (double nums[], const int size); 
5.3 Bảng sau đặc tả các nội dung chính của bốn loại hàng của các ngũ cốc điểm 
tâm. Định nghĩa một mảng hai chiều để bắt dữ liệu này: 
 Sơ Đường Béo Muối 
Top Flake 12g 25g 16g 0.4g 
Cornabix 22g 4g 8g 0.3g 
Oatabix 28g 5g 9g 0.5g 
Ultrabran 32g 7g 2g 0.2g 
Viết một hàm xuất bảng này từng phần tử một. 
5.4 Định nghĩa một hàm để nhập vào danh sách các tên và lưu trữ chúng như là 
các chuỗi được cấp phát động trong một mảng và một hàm để xuất chúng: 
void ReadNames (char *names[], const int size); 
void WriteNames (char *names[], const int size); 
 Viết một hàm khác để sắp xếp danh sách bằng cách sử dụng giải thuật sắp 
xếp nổi bọt (bubble sort): 
void BubbleSort (char *names[], const int size); 
 Sắp xếp nổi bọt liên quan đến việc quét lặp lại danh sách, trong đó trong khi 
thực hiện quét các hạng mục kề nhau được so sánh và đổi chỗ nếu không theo 
thứ tự. Quét mà không liên quan đến việc đổi chỗ chỉ ra rằng danh sách đã 
được sắp xếp thứ tự. 
5.5 Viết lại hàm sau bằng cách sử dụng tính toán con trỏ: 
char* ReverseString (char *str) 
{ 
 int len = strlen(str); 
 char *result = new char[len + 1]; 
 for (register i = 0; i < len; ++i) 
 result[i] = str[len - i - 1]; 
 result[len] = '\0'; 
 return result; 
} 
Chapter 5: Mảng, con trỏ, và tham chiếu 73 
5.6 Viết lại giải thuật BubbleSort (từ bài 5.4) sao cho nó sử dụng một con trỏ hàm 
để so sánh các tên. 
5.7 Viết lại các mã sau bằng cách sử dụng định nghĩa kiểu: 
void (*Swap)(double, double); 
char *table[]; 
char *&name; 
usigned long *values[10][20]; 
Chapter 5: Mảng, con trỏ, và tham chiếu 74