giáo trình ngôn ngữ lập trinh C ++ <phần 9>

CHƯƠNG 7

MỘT SỐ LỚP QUAN TRỌNG

Nội dung chương này tập trung trình bày một số lớp cơ bản trong C++:

• Lớp vật chứa (Container)

• Lớp tập hợp (Set)

• Lớp chuỗi kí tự (String)

• Lớp ngăn xếp (Stack) và hàng đợi (Queue)

• Lớp danh sách liên kết (Lists)

7.1 LỚP VẬT CHỨA

Lớp vật chứa (Container) bao gồm nhiều lớp cơ bản của C++: lớp Vector, lớp danh sách (List) và
các kiểu hàng đợi (Stack và Queue), lớp tập hợp (Set) và lớp ánh xạ (Map). Trong chương này sẽ
trình bày một số lớp cơ bản của Container là: Set, Stack, Queue và List

7.1.1 Giao diện của lớp Container

Các lớp cơ bản của Container có một số toán tử và phương thức có chức năng giống nhau, bao
gồm:

• ==: Toán tử so sánh bằng

• <: Toán tử so sánh nhỏ hơn

• begin(): Giá trị khởi đầu của con chạy iterator

• end(): Giá trị kết thúc của con chạy iterator

• size(): Số lượng phần tửđối tượng của vật chứa

• empty(): Vật chứa là rỗng

• front(): Phần tử thứ nhất của vật chứa

• back(): Phần tử cuối của vật chứa

• []: Toán tử truy nhập đến phần tử của vật chứa

• insert(): Thêm vào vật chứa một (hoặc một số) phần tử

• push_back(): Thêm một phần tử vào cuối vật chứa

• push_front(): Thêm một phần tử vào đầu vật chứa

• erase(): Loại bỏ một (hoặc một số) phần tử khỏi vật chứa

• pop_back(): Loại bỏ phần tử cuối của vật chứa

• pop_front(): Loại bỏ phần tửđầu của vật chứa.

Ngoài ra, tuỳ vào các lớp cụ thể mà có một số toán tử và phương thức đặc trưng của lớp đó. Các
toán tử và phương thức này sẽđược trình bày chi tiết trong nội dung từng lớp tiếp theo.

7.1.2 Con chạy Iterator

Iterator là một con trỏ trỏđến các phần tử của vật chứa. Nó đóng vai trò là một con chạy cho phép
người dùng di chuyển qua từng phần tử có mặt trong vật chứa. Mỗi phép tăng giảm một đơn vị
của con chạy này tương ứng với một phép dịch đến phần tử tiếp theo hay phần tử trước của phần
tử hiện tại mà con chạy đang trỏ tới.

Khai báo con chạy

Cú pháp chung để khai báo một biến con chạy iterator như sau:

Tên_lớp<T>::iterator Tên_con_chạy;

Trong đó:

• Tên lớp: là tên của lớp cơ bản ta đang dùng, ví dụ lớp Set, lớp List…

• T: là tên kiểu lớp của các phần tử chứa trong vật chứa. Kiểu có thể là các kiểu cơ bản
trong C++, cũng có thể là các kiểu phức tạp do người dùng tựđịnh nghĩa.

• Tên con chạy: là tên biến sẽđược sử dụng làm biến chạy trong vật chứa.

Ví dụ:

Set<int>::iterator iter;

là khai báo một biến con chạy iter cho lớp tập hợp (Set), trong đó, các phần tử của lớp vật chứa có
kiểu cơ bản int. Hoặc:

List<Person>::iterator iter;

là khai báo một biến con chạy iter cho lớp danh sách (List), trong đó, các phần tử có kiểu lớp do
người dùng tựđịnh nghĩa là Person.

Sử dụng con chạy

Con chạy được sử dụng khi cần duyệt lần lượt các phần tử có mặt trong vật chứa. Ví dụ sau sẽ in
ra các phần tử có kiểu int của một tập hợp:

Set<int> mySet; // Khai báo một đối tượng của lớp Set,

// các phần tử có kiểu int

Set<int>::iterator i; // Khai báo con chạy của lớp Set,

// các phần tử có kiểu int

… // Thêm phần tử vào

for(i=mySet.begin(); i<mySet.end(); i++)

cout << mySet[i] << “ ”;

Lưu ý:

• Biến con chạy phải được khởi đầu bằng phương thức begin() và kết thúc bằng phương
thức end() của đối tượng cần duyệt tương ứng.

• Một con chạy có thểđược sử dụng nhiều lần cho nhiều đối tượng nếu chúng có cùng kiểu
lớp vật chứa và các phần tử của chúng cũng cùng kiểu.

7.2 LỚP TẬP HỢP

Lớp tập hợp (Set) chứa các phần tử có cùng kiểu, không phân biệt thứ tự giữa các phần tử nhưng
lại phân biệt giữa các phần tử: các phần tử là khác nhau từng đôi một. Muốn sử dụng lớp tập hợp,
phải có chị thịđầu tệp:

#include<set.h> // Thư viện riêng của lớp tập hợp

hoặc:

#include<stl.h> // Thư viện chung cho các lớp vật chứa

7.2.1 Hàm khởi tạo

Lớp tập hợp có ba kiểu khởi tạo chính:

• Khởi tạo không tham số:

Set<T> Tên_đối_tượng;

• Khởi tạo bằng một mảng các đối tượng phần tử:

Set<T> Tên_đối_tượng(T*, chiều_dài_mảng);

• Khởi tạo bằng một đối tượng thuộc lớp tập hợp khác:

Set<T> Tên_đối_tượng(Set<T>);

Trong đó:

• T: là tên kiểu của các phần tử của tập hợp. Kiểu này có thể là kiểu cơ bản của C++, cũng
có thể là các kiểu cấu trúc (struct) hoặc lớp (class) do người dùng tựđịnh nghĩa.

Ví dụ:

Set<int> mySet;

là khai báo một đối tượng mySet của lớp tập hợp, mySet khởi đầu chưa có phần tử nào, các phần
tử của đối tượng này có kiểu cơ bản int. Hoặc:

Person *myPerson = new Person[10]; // Khởi tạo mảng đối tượng

Set<Person> mySet(myPerson, 10); // Khai báo tập hợp

là khai báo một đối tượng mySet của lớp tập hợp, có 10 phần tử tương ứng với các phần tử trong
mảng động myPerson, các phần tử có kiểu lớp Person.

7.2.2 Toán tử

Các toán tử trên lớp tập hợp là tương ứng với các toán tử số học trên tập hợp thông thường: OR
“|”, AND “&”, XOR “^” và phép trừ “-”.

Phép toán “|” và “|=”

Phép toán này trả về phép hợp (OR) của hai đối tượng của lớp tập hợp, kết quả cũng là một đối
tượng của lớp tập hợp:

<Đối_tượng_1> = <Đối_tượng_2> | <Đối_tượng_3>;

<Đối_tượng_1> |= <Đối_tượng_2>;

Ví dụ, mySet1 chứa hai phần tử kiểu int {1,2}, mySet2 chứa ba phần tử kiểu int {2,3,4}, và:

mySet3 = mySet1 | mySet2;

thì mySet3 sẽ chứa các phần tử kiểu int là {1,2,3,4}.
Phép toán “&” và “&=”

Phép toán này trả về phép giao (AND) giữa hai đối tượng tập hợp, kết quả cũng là một đối tượng
tập hợp:

<Đối_tượng_1> = <Đối_tượng_2> & <Đối_tượng_3>;

<Đối_tượng_1> &= <Đối_tượng_2>;

Ví dụ, mySet1 chứa hai phần tử kiểu int {1,2}, mySet2 chứa ba phần tử kiểu int {2,3,4}, và:

mySet3 = mySet1 & mySet2;

thì mySet3 sẽ chứa các phần tử có kiểu int là {2}.

Phép toán “^” và “^=”

Phép toán này trả về phép hợp ngoại (XOR) giữa hai đối tượng tập hợp, kết quả cũng là một đối
tượng tập hợp:

<Đối_tượng_1> = <Đối_tượng _2> ^ <Đối_tượng_3>;

<Đối_tượng_1> ^= <Đối_tượng_2>;

Ví dụ, mySet1 chứa hai phần tử kiểu int {1,2}, mySet2 chứa ba phần tử kiểu int {2,3,4}, và:

mySet3 = mySet1 ^ mySet2;

thì mySet3 sẽ chứa các phần tử có kiểu int là {1,3,4}.

Phép toán “-” và “-=”

Phép toán này trả về phép hiệu (loại trừ) giữa hai đối tượng tập hợp, kết quả cũng là một đối
tượng tập hợp:

<Đối_tượng_1> = <Đối_tượng_2> - <Đối_tượng_3>;

<Đối_tượng_1> -= <Đối_tượng_2>;

Ví dụ, mySet1 chứa hai phần tử kiểu int {1,2}, mySet2 chứa ba phần tử kiểu int {2,3,4}, và:

mySet3 = mySet1 - mySet2;

thì mySet3 sẽ chứa các phần tử có kiểu int là {1}.

7.2.3 Phương thức

Lớp tập hợp có một số phương thức cơ bản sau:

• Thêm một phần tử vào tập hợp

• Loại một phần tử khỏi tập hợp

• Tìm kiếm một phần tử trong tập hợp

Thêm một phần tử vào tập h ợp

Có hai cú pháp để thêm một phần tử vào tập hợp:

pair<iterator, bool> insert(T&);

iterator insert(<Vị trí con chạy>, T&);

Trong đó:
• Phương thức thứ nhất thêm một phần tử vào tập hợp, nếu phần tửđã có mặt trong tập hợp,
trả về false và vị trí con chạy của phần tửđó. Nếu phần tử chưa tồn tại, trả về true và vị trí
con chạy của phần tử mới thêm vào.

• Phương thức thứ hai cũng thêm vào một phần tử, nhưng chỉ kiểm tra xem phần tửđã tồn
tại hay chưa bắt đầu tự vị trí con chạy được chỉ ra trong biến <vị trí con chạy>. Phương
thức này trả về vị trí con chạy của phần tử mới thêm vào (nếu thành công) hoặc vị trí của
phần tửđã có mặt.

Ví dụ, mySet là một tập hợp kiểu int:

mySet.insert(10);

sẽ thêm một phần tử có giá trị 10 vào tập hợp.

Lưu ý:

• Do tuân thủ theo lí thuyết tập hợp, nên khi chèn vào tập hợp nhiều lần với cùng một giá trị
phần tử. Trong tập hợp chỉ tồn tại duy nhất một giá trị phần tửđó, không được trùng lặp.

Loại một phần tử khỏi tập h ợp

Có ba cú pháp để loại bỏ phần tử khỏi tập hợp:

int erase(T&);

void erase(<vị trí con chạy>);

void erase(<vị trí bắt đầu>, <vị trí kết thúc>);

Trong đó:

• T: là tên kiểu các phần tử của tập hợp.

• Phương thức thứ nhất xoá phần tử có giá trịđược chỉ rõ trong tham sốđầu vào.

• Phương thức thứ hai loại bỏ phần tửở vị trí của con chạy được xác định bởi tham sốđầu
vào.

• Phương thức thứ ba loại bỏ một số phần tử nằm trong phạm vi từ <vị trí bắt đầu> cho đến
<vị trí kết thúc> của con chạy.

Ví dụ, mySet là một tập hợp các phần tử có kiểu int:

mySet.erase(10);

sẽ xoá phần tử có giá trị 10, hoặc:

mySet.erase((Set<int>::iterator)10);

sẽ xoá phần tửở vị trí thứ 10 trong tập hợp, hoặc:

mySet.erase(mySet.begin(), mySet.end());

sẽ xoá toàn bộ các phần tử hiện có của tập hợp mySet.

Tìm kiếm một phần tử trong tập h ợp

Có hai cú pháp để tìm kiếm một phần tử trong tập hợp:

iterator find(T&);

int count(T&);

Trong đó:

• Phương thức thứ nhất tìm phần tử có giá trị xác định bởi tham sốđầu vào, kết quả là vị trí
con chạy của phần tửđó.

• Phương thứ thứ hai chỉđể kiểm tra xem phần tử có xuất hiện trong tập hợp hay không: trả
về 1 nếu có mặt, trả về 0 nếu không có mặt.

Ví dụ, mySet là một tập hợp các phần tử có kiểu int:

Set<int>::iterator index = mySet.find(10);

cout << index;

sẽ hiển thị vị trí con chạy của phần tử có giá trị 10 trong tập hợp mySet.

7.2.4 Áp dụng

Chương trình 7.1 minh hoạ một số thao tác trên một tập hợp các phần tử có kiểu char: thêm phần
tử, loại bỏ phần tử, duyệt các phần tử.

Chương trình 7.1

#include<stdio.h>

#include<conio.h>

#include<set.h>

void main(){

clrscr();

Set<char> mySet;

int function;

do{

clrscr();

cout << “CAC CHUC NANG:” << endl;

cout << “1: Them mot phan tu vao tap hop” << endl;

cout << “2: Loai bo mot phan tu khoi tap hop” << endl;

cout << “3: Xem tat ca cac phan tu cua tap hop” << endl;

cout << “5: Thoat!” << endl;

cout << “=====================================” << endl;

cout << “Chon chuc nang: ” << endl;

cin >> function;

switch(function){

case ‘1’: // Thêm vào

char phantu;

cout << “Ki tu them vao: ”;

cin >> phantu;

mySet.insert(phantu);

break;

case ‘2’: // Loại ra

char phantu;

cout << “Loai bo ki tu: ” << endl;

cin >> phantu;

mySet.erase(phantu);

break;

case ‘3’: // Duyệt

cout<<“Cac phan tu cua tap hop la:”<<endl;

Set<char>::iterator i;

for(i=mySet.begin(); i<mySet.end(); i++)

cout << mySet[i] << “ ”;

break;

}while(function != ‘5’);

return;

}

7.3 LỚP CHUỖI

Lớp chuỗi (String) cũng là một loại lớp chứa, nó chứa một tập các phần tử là một dãy các kí tự có
phân biệt thứ tự, các phần tử không nhất thiết phải phân biệt nhau. Muốn sử dụng lớp String, cần
thêm vào chỉ thịđầu tệp:

#include <string.h>

7.3.1 Hàm khởi tạo

Lớp String có ba hàm khởi tạo chính:

• Hàm khởi tạo không tham số:

String <tên biến>;

• Hàm khởi tạo từ một string khác:

String <tên biến>(const String &);

• Hàm khởi tạo từ một mảng các kí tự:

String <tên biến>(char*, <chiều dài mảng>);

Ví dụ:

String myStr;

là khai báo một chuỗi myStr chưa có phần tử nào (rỗng). Hoặc:

String myStr(“hello!”);

là khai báo một chuỗi myStr có các phần tử theo thứ tự là {‘h’, ’e’, ’l’, ’l’, ’o’, ’!’}. Hoặc:

char* myChar = new char[10];

String myStr(myChar, 10);

là khai báo một chuỗi myStr có 10 phần tử tương ứng với các kí tự trong mảng myChar.

Lưu ý:

• Trong trường hợp khởi tạo bằng một chuỗi khác, ta có thể truyền vào một đối số có kiểu
cơ bản khác, trình biên dịch sẽ tựđộng chuyển đối sốđó sang dạng string.

Ví dụ:

String myStr(12);
thì chuỗi myStr sẽ chứa hai phần tử kí tự{‘1’, ’2’}. Hoặc:

String myStr(15.55);

thì chuỗi myStr sẽ chứa năm phần tử kí tự {‘1’, ’5’, ’.’, ’5’, ’5’}.

7.3.2 Toán tử

Lớp String có các toán tử cơ bản là:

• Phép gán chuỗi

• Phép cộng chuỗi

• Phép so sánh chuỗi

• Phép vào/ra

Phép gán chuỗi “=”

Cú pháp phép gán chuỗi là tương tự cú pháp gán các đối tượng cơ bản:

<Tên biến 1> = <Tên biến 2>;

Ví dụ:

String s1(12), s2;

s2 = s1;

thì chuỗi s2 cũng chứa hai phần tử như s1 {‘1’, ‘2’}.

Lưu ý:

• Có thể gán trực tiếp các đối tượng cơ bản cho chuỗi:

String myStr = 12; // myStr có hai phần tử {‘1’, ‘2’}

• Nhưng phép gán lại có độưu tiên thấp hơn phép toán học:

String myStr = 12+1.5; // tương đương myStr = 13.5

Phép cộng chuỗi “+” và “+=”

Phép cộng chuỗi sẽ nối chuỗi thứ hai vào sau chuỗi thứ nhất, kết quả cũng là một chuỗi:

<Tên biến 1> = <Tên biến 2> + <Tên biến 3>;

<Tên biến 1> += <Tên biến 2>;

Ví dụ:

String s1(12), s2(3);

s1+= s2;

thì s1 sẽ có ba phần tử kí tự {‘1’, ‘2’, ‘3’}.

Phép so sánh chuỗi

Các phép so sánh chuỗi đều là các phép toán hai ngôi, trả về kết quảở dạng bool (true/false):

• Phép so sánh lớn hơn “>”: chuỗi_1 > chuỗi_2;

• Phép so sánh lớn hơn hoặc bằng “>=”: chuỗi_1 >= chuỗi_2;

• Phép so sánh nhỏ hơn “<”: chuỗi_1 < chuỗi_2;

• Phép so sánh nhỏ hơn hoặc bằng “<=”: chuỗi_1 <= chuỗi_2;
• Phép so sánh bằng “==”: chuỗi_1 == chuỗi_2;

• Phép so sánh khác (không bằng) “!=”: chuỗi_1 != chuỗi_2;

Lưu ý:

• Phép so sánh chuỗi thực hiện so sánh mã ASCII của từng kí tựở hai chuỗi theo thứ tự
tương ứng cho đến khi có sự khác nhau đầu tiên giữa hai kí tự.

• Phép so sánh là phép so sánh dựa trên từđiển, có phân biệt chữ hoa và chữ thường.

Ví dụ:

“12” < “a”; // có giá trị đúng

“a” <= “A”; // có giá trị sai

Phép vào/ra

• Phép xuất ra “<<”: cout << biến_chuỗi;

• Phép nhập vào “>>”: cin >> biến_chuỗi;

Ví dụ:

String s(“hello!”);

cout << s;

sẽ in ra màn hình dòng chữ “hello!”.

7.3.3 Phương thức

Lớp chuỗi có một số phương thức cơ bản:

• Lấy chiều dài chuỗi

• Tìm một chuỗi con

• Thêm một chuỗi con

• Xoá một chuỗi con

• Chuyển kiểu kí tự

Lấy chiều dài chuỗi

Cú pháp:

<biến_chuỗi>.length();

trả về chiều dài của chuỗi (số lượng phần tử kí tự trong chuỗi).

Ví dụ:

String s(“hello!”);

cout << s.length();

sẽ in ra màn hình độ dài chuỗi s là 6.

Tìm một chuỗi con

Cú pháp:

<biến_chuỗi>.find(<Chuỗi con>, <Vị trí bắt đầu>, <Kiểu so khớp>);

Trong đó:

• Tham số thứ nhất là chuỗi con cần tìm.

• Tham số thứ hai là vị trí để bắt đầu tìm, mặc định là bắt đầu tìm từ phần tử có chỉ số 0.

• Tham số thứ ba chỉ ra cách so khớp có phân biệt chữ hoa với chữ thường: SM_IGNORE
là không phân biệt, SM_SENSITIVE là có phân biệt.

• Phương thức này trả về kết quả dạng bool, tương ứng là có tìm thấy hay không.

Ví dụ:

s.find(“12”, 0, SM_IGNORE);

sẽ tìm trong chuỗi s xem có sự xuất hiện của chuỗi “12” hay không, vị trí bắt đầu tìm là 0, với
cách tìm không phân biệt chữ hoa chữ thường.

Thêm một chuỗi con

Cú pháp:

<biến_chuỗi>.insert(<vị trí chèn>, <chuỗi con>);

Trong đó:

• Tham số thứ nhất là vị trí chỉ số mà tại đó, chuỗi con sẽđược chèn vào

• Tham số thứ hai là chuỗi con cần chèn, chuỗi con này cũng có thể là một kí tự.

Ví dụ:

s.insert(0, “12”);

sẽ chèn vào đầu chuỗi s một chuỗi con có hai phần tử “12”.

Xoá một chuỗi con

Cú pháp:

<biến_chuỗi>.delete(<vị trí bắt đầu>, <độ dài chuỗi xoá>);

Trong đó:

• Tham số thứ nhất là vị trí bắt đầu xoá chuỗi con

• Tham số thứ hai là độ dài chuỗi con bị xoá, giá trị mặc định là 1.

Ví dụ:

s.delete(0, 2);

sẽ xoá hai kí tựđầu của chuỗi s.

Chuyển kiểu kí tự

• Đổi chuỗi thành các kí tự hoa: <biến_chuỗi>.toUpper();

• Đổi chuỗi thành các kí tự thường: <biến_chuỗi>.toLower();

Ví dụ:

s.toUpper(); // chuyển chuỗi s thành kí tự hoa

s.toLower(); // chuyển chuỗi s thành kí tự thường

7.3.4 Áp dụng

Chương trình 7.2 minh hoạ một số thao tác cơ bản trên lớp chuỗi, có sử dụng thư viện lớp chuỗi
chuẩn của C++: cộng thêm một chuỗi, chèn thêm một chuỗi con, xoá một chuỗi con, tìm một
chuỗi con…

Chương trình 7.2

#include<stdio.h>

#include<conio.h>

#include<string.h>

void main(){

clrscr();

String myStr;

int function;

do{

clrscr();

cout << “CAC CHUC NANG:” << endl;

cout << “1: Cong them mot chuoi” << endl;

cout << “2: Chen them mot chuoi” << endl;

cout << “3: Xoa di mot chuoi” << endl;

cout << “4: Tim mot chuoi con” << endl;

cout << “5: Chuyen thanh chu hoa” << endl;

cout << “6: Chuyen thanh chu thuong” << endl;

cout << “7: Xem noi dung chuoi” << endl;

cout << “8: Xem chieu dai chuoi” << endl;

cout << “9: Thoat!” << endl;

cout << “=====================================” << endl;

cout << “Chon chuc nang: ” << endl;

cin >> function;

switch(function){

case ‘1’: // Thêm vào cuối

String subStr;

cout << “Chuoi them vao: ”;

cin >> subStr;

myStr += subStr;

break;

case ‘2’: // Chèn vào chuỗi

String subStr;

int position;

cout << “Chuoi them vao: ”;

cin >> subStr;

cout << “Vi tri chen:”;

cin >> position;
myStr.insert(position, subStr);

break;

case ‘3’: // Xoá đi một chuỗi con

int position, count;

cout << “Vi tri bat dau xoa:”;

cin >> position;

cout << “Do dai xoa:”;

cin >> count;

myStr.delete(position, count);

break;

case ‘4’: // Tìm chuỗi con

String subStr;

int position;

cout << “Chuoi con can tim:”;

cin >> subStr;

cout << “Vi tri bat dau tim:”;

cin >> position;

if(myStr.find(position, subStr))

cout << “Co xuat hien!” << endl;

else

cout << “Khong xuat hien!” << endl;

break;

case ‘5’: // Chuyển thành chữ hoa

myStr.toUpper();

cout << myStr << endl;

break;

case ‘6’: // Chuyển thành chữ thường

myStr.toLower();

cout << myStr << endl;

break;

case ‘7’: // Duyệt

cout << “Noi dung chuoi:” << endl;

cout << myStr << endl;

break;

case ‘8’: // Duyệt

cout << “Chieu dai chuoi:”

<< myStr.length() << endl;

break;

}while(function != ‘9’);

return;

}
7.4 LỚP NGĂN XẾP VÀ HÀNG ĐỢI

7.4.1 Lớp ngăn xếp

Lớp ngăn xếp (stack) cũng là một loại lớp vật chứa, nó chứa các phần tử cùng kiểu, không bắt
buộc phải phân biệt nhau nhưng có phân biệt về thứ tự: các thao tác thêm phần tử và lấy phần tử
ra đều được thực hiện ở một đầu ngăn xếp. Phần tử nào được thêm vào trước thì sẽ bị lấy ra sau.

Muốn dùng lớp Stack phải dùng chỉ thịđầu tệp:

#include<stack.h>

Hàm khởi tạo

Lớp Stack có hai cách khởi tạo:

• Khởi tạo không tham số:

Stack<T> biến_ngăn_xếp;

• Khởi tạo bằng một ngăn xếp khác, có cùng kiểu phần tử:

Stack<T> biến_ngăn_xếp(Stack<T>);

Trong đó:

• T: là kiểu của các phần tử chứa trong ngăn xếp. T có thể là các kiểu cơ bản, cũng có thể là
các kiểu phức tạp do người dùng tựđịnh nghĩa.

Ví dụ:

Stack<int> myStack;

là khai báo một biến myStack, chứa các phần tử có kiểu cơ bản int.

Toán tử

Lớp Stack chỉ dùng đến các toán tử gán “=” và toán tử so sánh bằng “==”:

• Phép gán “=”:

<ngăn xếp 1> = <ngăn xếp 2>;

Dùng để gán hai đối tượng ngăn xếp.

• Phép so sánh bằng “==”:

<ngăn xếp 1> == <ngăn xếp 2>;

Dùng để kiểm tra xem hai đối tượng ngăn xếp có bằng nhau hay không. Kết quả trả về có
kiểu bool (true/false).

Phương thức

• Thêm một phần tử:

<biến ngăn xếp>.push(T);

sẽ thêm một phần tử có kiểu T vào đỉnh ngăn xếp.

• Loại một phần tử:

<biến ngăn xếp>.pop();

sẽ trả về phần tửđang nằm ởđỉnh ngăn xếp.

• Kiểm tra tính rỗng:
<biến ngăn xếp>.empty();

sẽ trả về kết quả kiểu bool, tương ứng với trạng thái của ngăn xếp có rỗng hay không.

• Kích thước ngăn xếp:

<biến ngăn xếp>.size();

sẽ trả về số lượng các phần tử hiện đang có mặt trong ngăn xếp.

Áp dụng

Trong phần này, ta sẽ viết lại chương trình 3.4c đã được minh hoạ trong phần viết về cấu trúc
ngăn xếp (chương 3). Nhưng thay vì phải định nghĩa cấu trúc ngăn xếp, ta dùng lớp ngăn xếp của
thư viện C++: đảo ngược một xâu kí tựđược nhập vào từ bàn phím.

Chương trình 7.3

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<stack.h>

void main(){

clrscr();

Stack<char> myStack;

char strIn[250];

cout << “Nhap chuoi: ”;

cin >> strIn; // Nhập chuỗi kí tự từ bàn phím

for(int i=0; i<strlen(strIn); i++) // Đặt vào ngăn xếp

myStack.push(strIn[i]);

while(!myStack.empty()) // Lấy ra từ ngăn xếp

cout << myStack.pop();

return;

}

7.4.2 Lớp hàng đợi

Lớp hàng đợi (queue) cũng là một loại lớp vật chứa, nó chứa các phần tử cùng kiểu, không bắt
buộc phải phân biệt nhau nhưng có phân biệt về thứ tự: các thao tác thêm phần tửđược thực hiện
ở một đầu, các thao tác lấy phần tử ra được thực hiện ở một đầu còn lại của hàng đợi. Phần tử nào
được thêm vào trước thì sẽ bị lấy ra trước.

Muốn dùng lớp Queue phải dùng chỉ thịđầu tệp:

#include<queue.h>

Hàm khởi tạo

Lớp Queue có hai cách khởi tạo:

• Khởi tạo không tham số:

Queue<T> biến_hàng_đợi;

• Khởi tạo bằng một hàng đợi khác, có cùng kiểu phần tử:

Queue<T> biến_hàng_đợi(Queue<T>);

Trong đó:

• T: là kiểu của các phần tử chứa trong hàng đợi. T có thể là các kiểu cơ bản, cũng có thể là
các kiểu phức tạp do người dùng tựđịnh nghĩa.

Ví dụ:

Queue<int> myQueue;

là khai báo một biến myQueue, chứa các phần tử có kiểu cơ bản int.

Toán tử

Lớp Queue chỉ dùng đến các toán tử gán “=” và toán tử so sánh bằng “==”:

• Phép gán “=”:

<hàng đợi 1> = <hàng đợi 2>;

Dùng để gán hai đối tượng hàng đợi.

• Phép so sánh bằng “==”:

<hàng đợi 1> == <hàng đợi 2>;

Dùng để kiểm tra xem hai đối tượng hàng đợi có bằng nhau hay không. Kết quả trả về có kiểu
bool (true/false).

Phương thức

• Thêm một phần tử:

<biến hàng đợi>.push(T);

sẽ thêm một phần tử có kiểu T vào cuối hàng đợi.

• Loại một phần tử:

<biến hàng đợi>.pop();

sẽ trả về phần tửđang nằm ởđỉnh đầu hàng đợi.

• Kiểm tra tính rỗng:

<biến hàng đợi>.empty();

sẽ trả về kết quả kiểu bool, tương ứng với trạng thái của hàng đợi có rỗng hay không.

• Kích thước hàng đợi:

<biến hàng đợi>.size();

sẽ trả về số lượng các phần tử hiện đang có mặt trong hàng đợi.

Áp dụng

Trong phần này, ta sẽ cài đặt lại chương trình trong phần cấu trúc hàng đợi (chuơng 3). Nhưng
thay vì phải tựđịnh nghĩa cấu trúc hàng đợi, ta dùng lớp Queue của thư viện C++ để mô phỏng
chương trình quản lí tiến trình của hệđiều hành.


Chương trình 7.4

#include<stdio.h>

#include<conio.h>

#include<queue.h>

void main(){

clrscr();

Queue<int> myQueue;

int function;

do{

clrscr();

cout << “CAC CHUC NANG:” << endl;

cout << “1: Them mot tien trinh vao hang doi” << endl;

cout << “2: Dua mot tien trinh trinh vao thuc hien” << endl;

cout<<“3: Xem tat ca cac tien trinh trong hang doi”<< endl;

cout << “5: Thoat!” << endl;

cout << “========================================” << endl;

cout << “Chon chuc nang: ” << endl;

cin >> function;

switch(function){

case ‘1’: // Thêm vào hàng đợi

int maso;

cout << “Ma so tien trinh vao hang doi: ”;

cin >> maso;

myQueue.push(maso);

break;

case ‘2’: // Lấy ra khỏi hàng đợi

cout << “Tien trinh duoc thuc hien: ” <<
myQueue.pop() << endl;

break;

case ‘3’: // Duyệt hàng đợi

Queue<int>::iterator i;

for(i=myQueue.begin(); i<myQueue.end(); i++)

cout << myQueue[i] << “ ”;

break;

}while(function != ‘5’);

return;

}

7.5 LỚP DANH SÁCH LIÊN KẾT

Lớp danh sách liên kết (List) cũng là một kiểu lớp vật chứa, nó chứa các phần tử cùng kiểu, có
tính đến thứ tự. Muốn sử dụng lớp List của thư viện C++, phải khai báo chỉ thịđầu tệp:

#include<list.h> // Dành riêng cho lớp List

hoặc:

#include<stl.h> // Dùng chung cho các lớp vật chứa

7.5.1 Hàm khởi tạo

Lớp List có ba kiểu khởi tạo:

• Khởi tạo không tham số:

List<T> biến_danh_sách;

• Khởi tạo tử một danh sách cùng kiểu:

List<T> biến_danh_sách(List<T>);

• Khởi tạo từ một mảng các phần tử:

List<T> biến_danh_sách(T* <Mảng phần tử>, int <chiều dài mảng>);

Trong đó:

• T: là kiểu của các phần tử chứa trong danh sách liên kết. T có thể là các kiểu cơ bản, cũng
có thể là các kiểu phức tạp do người dùng tựđịnh nghĩa.

Ví dụ:

List<int> myList;

sẽ khai báo một danh sách liên kết myList, các phần tử của nó có kiểu cơ bản int.

7.5.2 Toán tử

Toán tử gán “=”

Cú pháp:

<danh sách 1> = <danh sách 2>;

sẽ copy toàn bộ các phần tử của <danh sách 2> vào <danh sách 1>.

Toán tử so sánh bằng “==”

Cú pháp:

<danh sách 1> = <danh sách 2>;

sẽ trả về một giá trị kiểu bool, tương ứng với việc hai danh sách này có bằng nhau hay không.
Việc so sánh được tiến hành trên từng phần tửở vị trí tương ứng nhau.

Lưu ý:

• Ngoài ra còn có các phép toán so sánh khác cũng có thể thực hiện trên danh sách: <, >,
<=, >=, !=.
7.5.3 Phương thức

Thêm một phần tử vào danh sách

Cú pháp:

<biến danh sách>.insert(<vị trí chèn>, <phần tử>);

<biến danh sách>.push_front(<phần tử>);

<biến danh sách>.push_back(<phần tử>);

Trong đó:

• Phương thức thứ nhất chèn một phần tử vào một vị trí bất kì của danh sách, vị trí chèn
được chỉ ra bởi tham số thứ nhất.

• Phương thức thứ hai chèn một phần tử vào đầu danh sách

• Phương thức thứ ba chèn một phần tử vào cuối danh sách.

Ví dụ:

List<int> myList;

myList.push_front(7);

sẽ chèn vào đầu danh sách myList một phần tử có giá trị là 7.

Xoá đi một phần tử

Cú pháp:

<biến danh sách>.erase(<vị trí xoá>);

<biến danh sách>.pop_front();

<biến danh sách>.pop_back();

Trong đó:

• Phương thức thứ nhất xóa một phần tửở một vị trí bất kì của danh sách, vị trí xoá được
chỉ ra bởi tham số thứ nhất.

• Phương thức thứ hai xoá một phần tửởđầu danh sách

• Phương thức thứ ba xoá một phần tửở cuối danh sách.

Ví dụ:

List<int> myList;

cout << myList.pop_front();

sẽ in ra màn hình phần tửđầu của danh sách myList.

Kiểm tra tính rỗng của danh sách

Cú pháp:

<biến danh sách>.empty();

trả về giá trị bool, tương ứng với trạng thái hiện tại của biến danh sách là rỗng hay không.

Xem kích thước danh sách

Cú pháp:

<biến danh sách>.size();

Ví dụ:
cout << myList.size();

sẽ in ra màn hình kích cỡ (số lượng các phần tử) của danh dách.

Xem nội dung một phần tử

Cú pháp:

<biến danh sách>.get();

<biến danh sách>.next();

Trong đó:

• Phương thức thứ nhất trả về phần tửở vị trí hiện tại của con chạy

• Phương thức thứ hai trả về phần tử tiếp theo, và con chạy cũng di chuyển sang phần tửđó.

Ví dụ:

List<int> myList;

cout << myList.get();

sẽ in ra màn hình nội dung phần tử thứ nhất của danh sách myList.

7.5.4 Áp dụng

Trong phần này, ta cài đặt lại chương trình 3.6c đã được trình bày trong phần cấu trúc danh sách
liên kết (chương 3). Nhưng thay vì tự tạo danh sách liên kết, ta dùng lớp List trong thư viện của
C++ để quản lí nhân viên văn phòng.

Chương trình 7.5

#include<stdio.h>

#include<conio.h>

#include<string.h>

#include<list.h>

typedef struct{

char name[25]; // Tên nhân viên

int age; // Tuổi nhân viên

float salary; // Lương nhân viên

} Employee;

void main(){

clrscr();

List<Employee> myList;

int function;

do{

clrscr();

cout << “CAC CHUC NANG:” << endl;

cout << “1: Them mot nhan vien” << endl;

cout << “2: Xoa mot nhan vien” << endl;

cout << “3: Xem tat ca cac nhan vien trong phong” << endl;
cout << “5: Thoat!” << endl;

cout << “=======================================” << endl;

cout << “Chon chuc nang: ” << endl;

cin >> function;

switch(function){

case ‘1’: // Thêm vào ds

int position;

Employee employee;

cout << “Vi tri can chen: ”;

cin >> position;

cout << “Ten nhan vien: ”;

cin >> employee.name;

cout << “Tuoi nhan vien: ”;

cin >> employee.age;

cout << “Luong nhan vien: ”;

cin >> employee.salary;

myList.insert(position, employee);

break;

case ‘2’: // Lấy ra khỏi ds

int position;

cout << “Vi tri can xoa: ”;

cin >> position;

Employee result = myList.erase(position);

if(result != NULL){

cout << “Nhan vien bi loai: ” endl;

cout << “Ten: ” << result.name << endl;

cout << “Tuoi: ” << result.age << endl;

cout << “Luong: ” << result.salary << endl;

}

break;

case ‘3’: // Duyệt ds

cout << “Cac nhan vien cua phong:” << endl;

Employee result = myList.front();

do{

cout << result.name << “ ”

<< result.age << “ ”

<< result.salary << endl;

result = myList.next();

}while(result != NULL);

break;

}while(function != ‘5’);

return;

}
cout << “5: Thoat!” << endl;

cout << “=======================================” << endl;

cout << “Chon chuc nang: ” << endl;

cin >> function;

switch(function){

case ‘1’: // Thêm vào ds

int position;

Employee employee;

cout << “Vi tri can chen: ”;

cin >> position;

cout << “Ten nhan vien: ”;

cin >> employee.name;

cout << “Tuoi nhan vien: ”;

cin >> employee.age;

cout << “Luong nhan vien: ”;

cin >> employee.salary;

myList.insert(position, employee);

break;

case ‘2’: // Lấy ra khỏi ds

int position;

cout << “Vi tri can xoa: ”;

cin >> position;

Employee result = myList.erase(position);

if(result != NULL){

cout << “Nhan vien bi loai: ” endl;

cout << “Ten: ” << result.name << endl;

cout << “Tuoi: ” << result.age << endl;

cout << “Luong: ” << result.salary << endl;

}

break;

case ‘3’: // Duyệt ds

cout << “Cac nhan vien cua phong:” << endl;

Employee result = myList.front();

do{

cout << result.name << “ ”

<< result.age << “ ”

<< result.salary << endl;

result = myList.next();

}while(result != NULL);

break;

}while(function != ‘5’);

return;

}

HƯỚNG DẪN TRẢ LỜI CÂU HỎI VÀ BÀI TẬP

Chương 1

Chương 2

1. c và e.

2. a và d.

3. c.

4. b.

5. c.

6. c.

7. d.

8. b và c.

9. b.

10. c.

11. d.

12. c.

13. d.

Chương 3

1. a.

2. c.

3. a.

4. b.

5. b và d.

6. Gợi ý:

struct Subject{

char subject[20];

float note;

};

Hoặc:

typedef struct {

char subject[20];

float note;

}Subject;

7. Gợi ý:

typedef struct {

char name[20];
int age;

char class[20];

Subject* subjects;

char type[20];

}Student;

Chương 4

1. a.

2. b.

3. c.

4. a.

5. a.

6. b.

7. c.

8. d.

9. a.

10. b.

11. c.

Chương 5

1. a và c.

2. b.

3. d.

4. a, b và c.

5. c.

6. b và c.

7. b và c.

8. b, d và e.

9. c và d.

10. a và d.

11. a, b, c và d.

12. Gợi ý (từ bài 12 đến bài 17):

class Employee{

char* name;

int age;

float salary;

public:

Employee();

Employee(char* nameIn=””, int ageIn=18, float
salaryIn=100);

void setName(char*);

char* getName();

void setAge(int);

int getAge();

void setSalary(float);

float getSalary();

void show();

~Employee();

};

Chương 6

1. b.

2. d.

3. c.

4. b, d và f.

5. b và d.

6. d.

7. a, b, c và d.

8. a và c.

9. d.

10. d.

11. b.

12. b.

13. c và d.

14. a, b, c và d.

15. c và d.

16. b và c.

17. Gợi ý (từ bài 17 đến bài 25):

class Human{

char* name;

int age;

int sex;

public:

Human();

Human(char*, int, int);

void setName(char*);

char* getName();

void setAge(int);

int getAge();

void setSex(int);
int getSex();

void show();

~Human();

};

class Person: public virtual Human{

char* address;

char* phone;

public:

Person();

Person(char*, int, int, char*, char*);

void setAddress(char*);

char* getAddress();

void setPhone(char*);

char* getPhone();

void show();

~Person();

};

class Worker: public virtual Human{

int hour;

float salary;

public:

Worker();

Worker(int, float);

void setHour(int);

int getHour();

void setSalary(float);

float getSalary();

void show();

};

class Employee: public Person, public Worker{

char* position;

public:

Employee();

Employee(char*, int, int, char*, char*, int, float,
char*);

void setPosition(char*);

char* getPosition();

void virtual show();

~Employee();

};

Chương 7

2. Gợi ý
oid main(){

clrscr();

Set<Car> mySet;

int function;

do{

clrscr();

cout << “CAC CHUC NANG:” << endl;

cout << “1: Them mot phan tu vao tap hop” << endl;

cout << “2: Loai bo mot phan tu khoi tap hop” << endl;

cout << “3: Xem tat ca cac phan tu cua tap hop” << endl;

cout << “5: Thoat!” << endl;

cout << “===========================================” << endl;

cout << “Chon chuc nang: ” << endl;

cin >> function;

switch(function){

case ‘1’: // Thêm vào

Car car = new Car();

cout << “O to them vao: ” << endl;

cout << “Toc do: ”;

int speed;

cin >> speed;

car.setSpeed(speed);

cout << “Nhan hieu:”;

char[] mark;

cin >> mark;

car.setMark(mark);

float price;

cout << “Gia xe:”;

cin >> price;

car.setPrice(price);

mySet.insert(car);

break;

case ‘2’: // Loại ra

Set<Car>::iterator index;

cout << “Loai bo xe o vi tri: ”;

cin >> index;

if(index >= mySet.begin())&&(index < mySet.end())

mySet.erase(mySet[index]);

break;

case ‘3’: // Duyệt

cout<<“Cac phan tu cua tap hop la:”<<endl;

Set<char>::iterator i;

for(i=mySet.begin(); i<mySet.end(); i++){

cout << mySet[i].getSpeed() << “ ”;

cout << mySet[i].getMark() << “ ”;

cout << mySet[i].getPrice() << “ ”;

break;

}while(function != ‘5’);

return;

}

5. Gợi ý

void main(){

clrscr();

List<Car> myList;

int function;

do{

clrscr();

cout << “CAC CHUC NANG:” << endl;

cout << “1: Them mot xe o to” << endl;

cout << “2: Xoa mot xe o to” << endl;

cout << “3: Xem tat ca cac o to” << endl;

cout << “5: Thoat!” << endl;

cout << “=======================================” << endl;

cout << “Chon chuc nang: ” << endl;

cin >> function;

switch(function){

case ‘1’: // Thêm vào ds

int possition;

Car car = new Car();

cout << “Vi tri can chen: ”;

cin >> possition;

cout << “Toc do: ”;

int speed;

cin >> speed;

car.setSpeed(speed);

cout << “Nhan hieu:”;

char[] mark;

cin >> mark;

car.setMark(mark);

float price;

cout << “Gia xe:”;

cin >> price;

car.setPrice(price);

myList.insert(possition, car);

break;

case ‘2’: // Lấy ra khỏi ds

int possition;

cout << “Vi tri can xoa: ”;

cin >> possition;

Car result = myList.erase(possition);

if(result != NULL){

cout << “O to bi loai: ” endl;

cout<<“Toc do:”<<result.getSpeed()<<endl;

cout << “Nhan hieu: ” << result.getMark()

<< endl;

cout<<“Gia: ”<<result.getPrice()<<endl;

}

break;

case ‘3’: // Duyệt ds

cout << “Cac o to hien co:” << endl;

Car result = myList.front();

do{

cout << result.getSpeed() << “ ”

<< result.getMark() << “ ”

<< result.getPrice() << endl;

result = myList.next();

}while(result != NULL);

break;

}while(function != ‘5’);

return;

}