Bài viết này dành cho các bạn đã quen với ngôn ngữ lập trình Pascal và C, muốn chuyển sang sử dụng C++ để giải các bài tập tin học. Nếu chỉ mới biết Pascal, các bạn nên đọc loạt bài ‘Từ Pascal đến C’ trước.
Do kiến thức về C++ cũng còn chưa chuyên sâu, nên tác giả sẽ đi vào những ví dụ cụ thể, cần thiết để làm bài hơn là những lý giải chi tiết về C++.
Giới thiệu
Ngôn ngữ
C++ là một ngôn ngữ lập trình rất mạnh. C++ hỗ trợ cả lập trình cấu trúc (structural, như Pascal) và lập trình hướng đối tượng (như Java, C#).
Nhược điểm thường gặp khi dùng C++ để giải bài tập đó là chương trình C++ khó gỡ rối, vì chưa có một phần mềm hỗ trợ gỡ rối nào đủ mạnh. GNU C++ cũng biên dịch chậm hơn so với C#.
Trình biên dịch
Trình biên dịch dùng trong các kỳ thi và Online Judge đó là G++, một trình biên dịch mã nguồn mở cho ngôn ngữ C++.
Để tận dùng công cụ gỡ rối, đôi khi các bạn cần dùng trình biên dịch Visual C++ (msvc) của Microsoft. Trình biên dịch này so với G++ có một vài điểm khác biệt cần lưu ý khi giải bài tập. Nhưng nhìn chung, có thể dùng chương trình viết cho VC++ để nộp bài mà không gây ra lỗi biên dịch nào đáng kể.
IDE
Microsoft Visual Studio từ phiên bản 2005 hỗ trợ việc gỡ rối C++ tốt hơn nhiều so với các IDE khác.
Trong trường hợp không có VS, trong các kỳ thi, trên hệ điều hành Windows thường sử dụng Dev-C++:
http://jaist.dl.sourceforge.net/sourceforge/dev-cpp/devcpp-4.9.9.2_setup.exe
Dev-C++ hỗ trợ việc debug/gỡ rối kém hiệu quả, và dự án mã nguồn mở này đến nay cũng không được phát triển thêm nữa.
Trên hệ điều hành Linux, một giải pháp phù hợp là RHIDE. Tuy nhiên, khi sử dụng RHIDE bạn phải thiết lập các thông số sao cho giao diện không bị các lỗi về phím nóng, phải cài đặt hệ thống debug,…
(Do không sử dụng Linux nhiều nên nếu bạn nào biết giải pháp tốt để làm bài C++ cho Linux xin vui lòng cho tác giả biết!)
STL
Sức mạnh của C++ đến từ STL, viết tắt của Standard Template Libary, một thư viện lớn các class và thủ tục chuẩn cho C++. Các trình biên dịch mới như G++ và VS đều hỗ trợ tốt STL.
Lập trình
Tên thư viện
Tên thư viện trong C++ thường không có đuôi .h như C nữa (mặc dù bạn vẫn có thể sử dụng). Để dùng một thư viện cũ của C, bạn cần bỏ đuôi .h và thêm chữ cái c vào phía trước. Ví dụ:
C:
#include <stdio.h>
#include <string.h>
C++
#include <cstdio>
#include <cstring>
Namespace
Namespace chẳng qua là một nơi để chứa các thủ tục, class cùng có một điểm chung nào đó tránh việc trùng tên và cũng làm việc lập trình dễ quản lý hơn. Khi sử dụng thư viện chuẩn STL, namespace là std. Vì vậy ta thường thêm dòng:
using namespace std;
để tránh việc việc lại namespace khi phải dùng các thủ tục, class.
Ví dụ: để đọc dữ liệu, ta viết
:
Khi không khai báo dòng lệnh trên
std::cin >> n;
Khi đã khai báo dòng lệnh trên
cin >> n
Thư viện
Các thư viện C++ thường dùng khi giải bài tập:
- iostream: để đọc và ghi dữ liệu với đối tượng cin, cout, cách đọc ghi dữ liệu của C++
- string: để dùng đối tượng chuỗi của C++
- algorithms: chứa các thuật toán hữu ích như sort, binary search, next_permutation, max, min...
- vector: kiểu hướng đối tượng thay thế cho mảng
- set: kiểu tập hợp
- map: bảng (khóa, giá trị) được cài đặt bằng cây cân bằng hoặc bảng băm, rất hiệu quả
- sstream: thường dùng để chuyển số sang chuỗi và ngược lại
Các thư viện cũ của C thường dùng:
- cstdio: đọc và ghi dữ liệu với các lệnh scanf, printf,...
- cstring: các hàm xử lý trên kiểu chuỗi (char*) của C
- cmath: các hàm toán học
C++/C
Khi viết chương trình C++, hầu như bạn có thể dùng mọi yếu tố trong ngôn ngữ C. Do đó bạn có thể lựa chọn đọc ghi dữ liệu sử dụng cstdio hay iostream, sử dụng đối tượng string hay char* cho chuỗi, hoặc thậm chí sử dụng cả hai loại trong một chương trình.
Nhìn chung, các phương pháp cũ của C có tốc độ nhanh hơn, tuy nhiên các đối tượng của C++ lại giúp lập trình dễ dàng và sáng sủa hơn.
Số nguyên 64 bit
Kiếu số nguyên 64 bit cho G++ (tương đương với int64 của Free Pascal) ký hiệu là long long.
Ví dụ:
long long a;
Đọc ghi dữ liệu với iostream
Thông thường, khi giải những bài cần đọc ghi khối lượng dữ liệu lớn, bạn nên sử dụng scanf và printf vì thời gian chạy sẽ tốt hơn. Thậm chí nếu đã quen dùng thì cách nhập xuất với C này cũng đủ sử dụng cho mọi bài tập.
Tuy nhiên với các bài có khối lượng đọc/ghi dữ liệu không đáng kể, iostream của C++ là lựa chọn tốt vì rất dễ sử dụng.
Có hai đối tượng chính mà bạn sẽ sử dụng, đó là cin và cout.
cin: đọc dữ liệu từ thiết bị chuẩn (bàn phím)
cout: ghi dữ liệu ra thiết bị chuẩn (màn hình)
Trong trường hợp muốn đọc, ghi dữ liệu ra file, các bạn cần khai báo đè các thiết bị chuẩn, bằng cách thêm các dòng lệnh sau ở đầu chương trình:
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
cin hoạt động với toán tử >>, cout hoạt động với toán tử <<. Bạn có thể coi cin là bàn phím, cout là màn hình, chiều của mũi tên là chiều đi của dữ liệu.
Ví dụ:
long long a;
cin >> a;
string s;
cin >> s;
cin hoạt động với cả string của C++ và mảng char của C, nghĩa là đoạn chương trình sau vẫn chạy đúng:
char s[100];
cin >> s;
Một chương trình đơn giản, đọc một chuỗi và in ra màn hình:
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s;
cin >> s;
cout << s;
return 0;
}
Lưu ý: khác với lệnh read, hay readln của Pascal, việc đọc chuỗi bằng cin sẽ dừng lại khi bắt gặp khoảng trắng. Nghĩa là khi chạy chương trình trên nếu nhập vào “Free Pascal”, màn hình sẽ chỉ xuất hiện chuỗi “Free”.
Để đọc cả một dòng trong input, dùng lệnh getline:
string s;
getline(cin, s);
Việc in dữ liệu với cout khá dễ dàng. Để in ký tự xuống dòng bạn có thể dùng chỉ thị endl. Ví dụ:
cout << 5 << endl << “ioitrain”;
sẽ in ra kết quả
5
ioitrain
Lưu ý, cout không hỗ trợ tốt trong trường hợp cần in số thực với độ chính xác một số chữ số thập phân. Trong trường hợp này, bạn cần dùng printf.
Ví dụ:
printf(“%.2lf”, &x); sẽ in ra số thực x với 2 chữ số thập phân
Chuỗi
Chuỗi (string) là đối tượng rất thường được sử dụng trong C++. Một string có thể chứa số ký tự tùy ý.
Để sử dụng string, bạn cần khai báo thư viện với dòng lệnh
#include <string>
string s=”ioitrain”;
- Xác định ký tự tại vị trí i (vị trí được tính từ 0)
char c=s[i];
int l=s.length();
- Chuỗi con bắt đầu tự ví trí i, có độ dài k
string p=s.substr(i, k);
- Đảo ngược một chuỗi: dùng hàm reverse của thư viện algorithm:
string p=reverse(s.begin(), s.end());
- So sánh hai chuỗi: có thể dùng các toán tử >, <, =,... như Pascal.
- Nối chuỗi: có thể dùng toán tự + như Pascal
string p=s+”.info/”+s;
Sử dụng chuỗi trong C
Chuỗi trong C liên quan rất nhiều đến con trỏ. Khi bạn đã quen sử dụng con trỏ, bạn có thể vận dùng vào xử lý chuỗi hiệu qủa hơn so với trong Pascal.
Một chuỗi trong C đơn giản là một mảng kí tự. Dòng sau đây khai báo một mảng có thể lưu giữ một chuỗi lên đến 99 kí tự.
char str[100];
Mảng str lưu giữ kí tự như sau: str[0] là kí tự đầu của mảng, str[1] là kí tự thứ hai, v.v.. Nhưng tại sao một mảng 100 phần tử lại chỉ lưu được có 99 kí tự. Bởi vì C dùng null-terminated strings, nghĩa là kết thúc một chuỗi luôn được đánh dấu bởi kí tự có mã ASCII là 0 (kí tự null), được kí hiệu trong C là ‘\0’
Lọai chuỗi này rất khác so với strings trong Pascal. Trong Pascal, mỗi string là một mảng kí tự, trong đó dành ra một byte để lưu giữ số kí tự chứa trong mảng. Cấu trúc này cho phép Pascal thuận lợi hơn khi cần biết độ dài của chuỗi. Pascal chỉ cần trả về giá trị đã lưu giữ, trong khi C cần phải đếm kí tự cho đến khi nó gặp ‘\0’. Nghĩa là C sẽ chậm hơn Pascal nhiều trong một số trường hợp, nhưng trong một số trường hợp khác nó lại nhanh hơn, như chúng ta sẽ thấy trong ví dụ dưới đây.
Tất cả các hàm hỗ trợ xử lý chuỗi đều được đặt trong thư viện <string.h> (trên một số hệ thống là <strings.h>). Bởi vì C bản thân nó không hỗ trợ các công cụ xử lý strings, do đó bạn sẽ cảm thấy hơi bất tiện trong việc viết mã. Ví dụ, trong Pascal, muốn copy một chuỗi sang một chuỗi khác, bạn làm rất dễ dàng như sau:
program samp;
var s1,s2:string;
begin
s1:='hello';
s2:=s1;
end.
Trong C, như đã biết, chúng ta không thể đơn giản gán một mảng cho một mảng khác, mà phải copy từng phần tử. Thư viên string chứa hàm strcpy cho phép bạn làm điều này. Đọan mã sau cho thấy cách sử dụng hàm strcpy để copy chuỗi:
#include <string.h>
void main()
{
char s1[100],s2[100];
strcpy(s1,"hello"); /* copy "hello" vào s1 */
strcpy(s2,s1); /* copy s1 vào s2 */
}
Hàm strcpy được sử dụng khi bạn cần khởi tạo một chuỗi. Một khác biệt nữa giữa Pascal và C là so sánh chuỗi. Trong Pascal, so sánh chuỗi được xây dựng ngay trong cơ sở ngôn ngữ (các tóan tử <, >, =, v.v... làm việc với chuỗi) . Còn trong C, bạn phải dùng hàm strcmp trong thư viện string, so sành hai chuỗi và trả về một số nguyên cho biết kết qủa so sánh. Kết qủa bằng 0 nghĩa là hai chuỗi bằng nhau, bằng giá trị âm nghĩa là s1 < s2, bằng giá trị dương nghĩa là s1 > s2. Trong Pascal, đọan mã như sau:
program samp;
var s1,s2:string;
begin
readln(s1);
readln(s2);
if s1=s2 then
writeln('bằng nhau')
else if (s1<s2) then
writeln('s1 bé hơn s2')
else
writeln('s1 lớn hơn s2');
end.
Đây là đọan mã tương đương trong C:
#include <stdio.h>
#include <string.h>
void main()
{
char s1[100],s2[100];
gets(s1);
gets(s2);
if (strcmp(s1,s2)==0)
printf("bằng nhau\n");
else if (strcmp(s1,s2)<0)
printf("s1 bé hơn s2\n");
else
printf("s1 lớn hơn s2\n");
}
Một số hàm thông dụng khác trong thư viện string là strlen, trả về độ dài của chuỗi; strcat nối hai chuỗi. Bạn có thể tham khảo thêm phần help của Turbo C. Lưu ý rằng nhiều khả năng xử lý chuỗi của Pascal, như copy, delete, pos, v.v... không có trong C. Do đó bạn cần phải tự xây dựng một số hàm xử lý chuỗi cho riêng mình. Hãy bắt đầu với việc viết lại hàm strlen. Sau đây là một cách viết mã theo phong cách các bạn đã quen dùng với Pascal:
int strlen(char s[])
{
int x;
x=0;
while (s[x] != '\0')
x=x+1;
return(x);
}
Hầu hết các lập trình viên C không thích cách tiếp cận này bởi vì nó có vẻ kém hiệu qủa. Thay vào đó, họ thường dùng cách tiếp cận dựa trên con trỏ:
int strlen(char *s)
{
int x=0;
while (*s != '\0')
{
x++;
s++;
}
return(x);
}
Bạn có thể viết gọn lại như sau:
int strlen(char *s)
{
int x=0;
while (*s++)
x++;
return(x);
}
Có lẽ một chuyên gia về C còn có thể làm đọan mã trên ngắn hơn nữa.
Tuy nhiên thực tế khi chạy và so sánh ba chương trình trên, bạn sẽ thấy thời gian thực hiện của chúng như nhau hoặc sai khác rất nhỏ. Điều đó có nghĩa là, bạn nên viết mã theo bất kì cách nào mã bạn thấy dễ hiểu nhất. Con trỏ thông thường làm chương trình chạy nhanh hơn, nhưng hàm strlen trên lại không thuộc về trường hợp đó.
Chúng ta hãy tiếp tục với hàm strcopy:
strcpy(char s1[],char s2[])
{
int x;
for (x=0; x<=strlen(s2); x++)
s1[x]=s2[x];
}
Lưu ý dấu <= bởi vì đọan mã cần copy cả kí tự ‘\0’. Một điều nữa là đọan mã này rất kém hiệu qủa, bởi vì hàm strlen được gọi lại mỗi khi bạn lặp lại vòng for. Để giải quyết vấn đề này, bạn có thể dùng đọan mã dưới đây:
strcpy(char s1[],char s2[])
{
int x,len;
len=strlen(s2);
for (x=0; x<=len; x++)
s1[x]=s2[x];
}
Còn đây là phiên bản sử dụng con trỏ:
strcpy(char *s1,char *s2)
{
while (*s2 != '\0')
{
*s1 = *s2;
s1++;
s2++;
}
}
Bạn có thể viết ngắn hơn nữa:
strcpy(char *s1,char *s2)
{
while (*s2)
*s1++ = *s2++;
}
Thậm chí bạn có thể viết là while(*s1++=*s2++); Lần này, khi chạy thử, bạn sẽ thấy phiên bản thứ nhất chạy rất chậm, trong khi đó phiên bản thứ ba và thứ tư nhanh hơn so với phiên bản thứ hai. Trong trường hợp này, con trỏ thực sự hiệu qủa.
Sử dụng con trỏ đối với chuỗi đôi khi tạo ra hiệu qủa rõ rệt về tốc độ. Ví dụ giả sử bạn muốn lọai bỏ khỏang trắng ở đầu trong một chuỗi. Trong Pascal, bạn thường phải sử dụng hàm delete như sau:
program samp;
var s:string;
begin
readln(s);
while (s[1] <> ' ') and (length(s)>0) do
delete(s,1,1);
writeln(s);
end;
Đọan mã trên kém hiệu qủa bởi vì nó dời tòan bộ mảng kí tự đi một vị trí mỗi khi tìm thấy một khỏang trắng ở đầu chuỗi. Cách tốt hơn là như sau:
program samp;
var s:string;
x:integer;
begin
readln(s);
x:=0;
while (s[x+1] <> ' ') and (x<length(s)) do
x:=x+1;
delete(s,1,x);
writeln(s);
end;
Với kỹ thuật trên, mỗi kí tự chỉ cần dịch chuyển một lần. Trong C, thậm chí bạn có thể không cần phải dịch chuyển kí tự nào như sau:
#include <stdio.h>
#include <string.h>
void main()
{
char s[100],*p;
gets(s);
p=s;
while (*p==' ')
p++;
printf("%s\n",p);
}
Đọan mã này nhanh hơn nhiều so với Pascal, đặc biệt đối với những chuỗi dài.
Thực hành nhiều sẽ giúp bạn học được thêm những thủ thuật với chuỗi.
Những chuỗi hằng
Bạn hãy thử hai đọan chương trình sau:
Đọan 1:
{
char *s;
s="hello";
printf("%s\n",s);
}
Đọan 2:
{
char s[100];
strcpy(s,"hello");
printf("%s\n",s);
}
Hai đọan mã trên đưa ra cùng một kết qủa, nhưng cách họat động của chúng hòan tòan khác nhau. Trong đọan 2, bạn không thể viết s=”hello”;. Để hiểu sự khác nhau, bạn cần phải biết họat động của bảng chuỗi hằng (string constant table) trong C.
Khi chương trình được thực thi, trình biên dịch tạo ra một file object, chứa mã máy và một bảng chứa tất cả các chuỗi hằng khai báo trong chương trình. Trong đọan 1, lệnh s=”hello”; xác định rằng s chỉ đến địa chỉ của chuỗi hello trong bảng chuỗi hằng. Bởi vì chuỗi này nằm trong bảng chuỗi hằng, và là một bộ phận trong mã exe, nên bạn không thể thay đổi được nó. Bạn chỉ có thể dùng nó theo kiểu chỉ-đọc (read-only).
Trong đọan 2, chuỗi hello cũng tồn tại trong bảng chuỗi hằng, do đó bạn có thể copy nó vào mảng kí tự tên là s. Bởi vì s không phải là một con trỏ, lệnh s=”hello”; sẽ không làm việc.
Lưu ý khi sử dụng String với lệnh malloc
Giả sử bạn viết đọan chương trình sau:
void main()
{
char *s;
s=(char *) malloc (100);
s="hello";
free(s);
}
Đọan mã trên biên dịch được, nhưng nó tạo ra một lỗi “segmentation fault” ngay ở dòng free. Bởi vì lệnh malloc tạo ra một khối bộ nhớ 100 bytes và trỏ s vào đó, nhưng dòng s=”hello”; lại trỏ s đến một chuỗi trong bảng chuỗi hằng, còn khối bộ nhớ 100 bytes bị bỏ qua. Do đó lệnh free gặp lỗi vì không thể giải phóng một khối bộ nhớ trong khu vực mã exe.
Đọan mã đúng phải là như sau:
void main()
{
char *s;
s=(char *) malloc (100);
strcpy(s,"hello");
free(s);
}
Kết luận
Đến đây, hy vọng các bạn có thể dùng C để giải quyết được những bài tóan tin học như đối với Pascal. Trong khuôn khổ bài viết này chỉ trình bày được một số nội dung cơ bản mà các bạn thường hay phải dùng khi giải tóan; thông qua những đối chiếu, so sánh với Pascal, là ngôn ngữ lập trình mà các bạn đã biết. Ngày nay, C cũng như C++ là những ngôn ngữ đựoc sử dụng nhiều nhất do tính hiệu qủa rất cao; mong rằng bài viết sẽ giúp các bạn tìm hiểu thêm về chúng.