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

CHƯƠNG 3

KIỂU DỮ LIỆU CẤU TRÚC

Nội dung chương này tập trung trình bày các vấn đề liên quan đến kiểu dữ liệu có cấu trúc trong
C++:

• Định nghĩa một cấu trúc

• Sử dụng một cấu trúc bằng các phép toán cơ bản trên cấu trúc

• Con trỏ cấu trúc, khai báo và sử dụng con trỏ cấu trúc

• Mảng các cấu trúc, khai báo và sử dụng mảng các cấu trúc

• Một số kiểu dữ liệu trừu tượng khác như ngăn xếp, hàng đợi, danh sách liên kết.

3.1 ĐỊNH NGHĨA CẤU TRÚC

Kiểu dữ liệu có cấu trúc được dùng khi ta cần nhóm một số biến dữ liệu luôn đi kèm với nhau.
Khi đó, việc xử lí trên một nhóm các biến được thực hiện như trên các biến cơ bản thông thường.

3.1.1 Khai báo cấu trúc

Trong C++, một cấu trúc do người dùng tựđịnh nghĩa được khai báo thông qua từ khoá struct:

struct <Tên cấu trúc>{

<Kiểu dữ liệu 1> <Tên thuộc tính 1>;

<Kiểu dữ liệu 2> <Tên thuộc tính 2>;

…

<Kiểu dữ liệu n> <Tên thuộc tính n>;

};

Trong đó:

• struct: là tên từ khoá để khai báo một cấu trúc, bắt buộc phải có khi định nghĩa cấu trúc.

• Tên cấu trúc: là tên do người dùng tựđịnh nghĩa, tuân thủ theo quy tắc đặt tên biến trong
C++. Tên này sẽ trở thành tên của kiểu dữ liệu có cấu trúc tương ứng.

• Thuộc tính: mỗi thuộc tính của cấu trúc được khai báo như khai báo một biến thuộc kiểu
dữ liệu thông thường, gồm có kiểu dữ liệu và tên biến tương ứng. Mỗi khai báo thuộc tính
phải kết thúc bằng dấu chấm phẩy “;” như một câu lệnh C++ thông thường.

Ví dụ, để quản lí nhân viên của một công ty, khi xử lí thông tin về mỗi nhân viên, ta luôn phải xử
lí các thông tin liên quan như:

• Tên

• Tuổi

• Chức vụ

• Lương

Do đó, ta sẽ dùng cấu trúc để lưu giữ thông tin về mỗi nhân viên bằng cách định nghĩa một cấu
trúc có tên là Employeee với các thuộc tính như sau:
struct Employeee{

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

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

char role[20]; // Chức vụ của nhân viên

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

};

Lưu ý:

• Cấu trúc chỉ cần định nghĩa một lần trong chương trình và có thểđược khai báo biến cấu
trúc nhiều lần. Khi cấu trúc đã được định nghĩa, việc khai báo biến ở lần khác trong
chương trình được thực hiện như khai báo biến thông thường:

<Tên cấu trúc> <tên biến 1>, <tên biến 2>;

Ví dụ, sau khi đã định nghĩa cấu trúc Employeee, muốn có biến myEmployeee, ta khai
báo như sau:

Employee myEmployeee;

3.1.2 Cấu trúc lồng nhau

Các cấu trúc có thểđược định nghĩa lồng nhau khi một thuộc tính của một cấu trúc cũng cần có
kiểu là một cấu trúc khác. Khi đó, việc định nghĩa cấu trúc cha được thực hiện như một cấu trúc
bình thường, với khai báo về thuộc tính đó là một cấu trúc con:

struct <Tên cấu trúc cha>{

<Kiểu dữ liệu 1> <Tên thuộc tính 1>;

// Có kiểu cấu trúc

<Kiểu cấu trúc con> <Tên thuộc tính 2>;

…

<Kiểu dữ liệu n> <Tên thuộc tính n>;

};

Ví dụ, với kiểu cấu trúc Employee, ta không quan tâm đến tuổi nhân viên nữa, mà quan tâm đến
ngày sinh của nhân viên. Vì ngày sinh cần có các thông tin luôn đi với nhau là ngày sinh, tháng
sinh, năm sinh. Do đó, ta định nghĩa một kiểu cấu trúc con cho kiểu ngày sinh:

struct Date{

int day;

int month;

int year;

};

khi đó, cấu trúc Employee trở thành:

struct Employee{

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

Date birthDay; // Ngày sinh của nhân viên

char role[20]; // Chức vụ của nhân viên

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

};
Lưu ý:

• Trong định nghĩa các cấu trúc lồng nhau, cấu trúc con phải được định nghĩa trước cấu trúc
cha đểđảm bảo các kiểu dữ liệu của các thuộc tính của cấu trúc cha là tường minh tại thời
điểm nó được định nghĩa.

3.1.3 Định nghĩa cấu trúc với từ khoá typedef

Để tránh phải dùng từ khoá struct mỗi khi khai báo biến cấu trúc, ta có thể dùng từ khóa typedef
khi định nghĩa cấu trúc:

typedef struct {

<Kiểu dữ liệu 1> <Tên thuộc tính 1>;

<Kiểu dữ liệu 2> <Tên thuộc tính 2>;

…

<Kiểu dữ liệu n> <Tên thuộc tính n>;

} <Tên kiểu dữ liệu cấu trúc>;

Trong đó:

• Tên kiểu dữ liệu cấu trúc: là tên kiểu dữ liệu của cấu trúc vừa định nghĩa. Tên này sẽ
được dùng như một kiểu dữ liệu thông thường khi khai báo biến cấu trúc.

Ví dụ, muốn có kiểu dữ liệu có cấu trúc nhân viên, có tên là Employee, ta dùng từ khoá typedef
đểđịnh nghĩa cấu trúc như sau:

typedef struct {

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

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

char role[20]; // Chức vụ của nhân viên

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

} Employee;

Khi đó, muốn có hai biến là myEmployee1 và myEmployee2 có kiểu cấu trúc Employee, ta chỉ
cần khai báo như sau mà không cần từ khoá struct:

Employee myEmployee1, myEmployee2;

Trong ví dụ khai báo lồng cấu trúc Employee, dùng từ khoá typedef cho kiểu Date:

typedef struct {

int day;

int month;

int year;

} Date;

cấu trúc Employee trở thành:

typedef struct {

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

Date birthDay; // Ngày sinh của nhân viên

char role[20]; // Chức vụ của nhân viên

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

} Employee;


• Khi không dùng từ khoá typedef, tên cấu trúc (nằm sau từ khoá struct) được dùng để khai
báo biến. Trong khi đó, khi có từ khoá typedef, tên kiểu dữ liệu cấu trúc (dòng cuối cùng
trong định nghĩa) mới được dùng để khai báo biến.

• Khi dùng từ khoá typedef thì không thể khai báo biến đồng thời với định nghĩa cấu trúc.

3.2 THAO TÁC TRÊN CẤU TRÚC

Các thao tác trên cấu trúc bao gồm:

• Khai báo và khởi tạo giá trị ban đầu cho biến cấu trúc

• Truy nhập đến các thuộc tính của cấu trúc

3.2.1 Khởi tạo giá trị ban đầu cho cấu trúc

Khởi tạo biến có cấu trúc đơn

Biến cấu trúc được khai báo theo các cách sau:

<Tên kiểu dữ liệu cấu trúc> <tên biến>;

Ngoài ra, ta có thể khởi tạo các giá trị cho các thuộc tính của cấu trúc ngay khi khai báo bằng các
cú pháp sau:

<Tên kiểu dữ liệu cấu trúc> <tên biến> = {

<giá trị thuộc tính 1>,

<giá trị thuộc tính 2>,

…

<giá trị thuộc tính n>

};

Trong đó:

• Giá trị thuộc tính: là giá trị khởi đầu cho mỗi thuộc tính, có kiểu phù hợp với kiểu dữ
liệu của thuộc tính. Mỗi giá trị của thuộc tính được phân cách bằng dấu phẩy “,”.

Ví dụ, với định nghĩa cấu trúc:

typedef struct {

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

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

char role[20]; // Chức vụ của nhân viên

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

} Employee;

thì có thể khai báo và khởi tạo cho một biến như sau:

Employee myEmployee1 = {

“Nguyen Van A”,

27,

“Nhan vien”,

300f

};

Khởi tạo các biến có cấu trúc lồng nhau

Trong trường hợp các cấu trúc lồng nhau, phép khởi tạo cũng thực hiện như thông thường với
phép khởi tạo cho tất cả các cấu trúc con.

Ví dụ với khai báo cấu trúc như sau:

typedef struct {

int day;

int month;

int year;

} Date;

và:

typedef struct {

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

Date birthDay; // Ngày sinh của nhân viên

char role[20]; // Chức vụ của nhân viên

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

} Employee;

Thì khai báo và khởi tạo một biến có kiểu Employee có thể thực hiện như sau:

Employee myEmployee1 = {

“Nguyen Van A”,

{15, 05, 1980}, // Khởi tạo cấu trúc con

“Nhan vien”,

300f

};

3.2.2 Truy nhập đến thuộc tính của cấu trúc

Việc truy nhập đến thuộc tính của cấu trúc được thực hiện bằng cú pháp:

<Tên biến cấu trúc>.<tên thuộc tính>

Ví dụ, với một biến cấu trúc kiểu Employee đơn:

Employee myEmployee1 = {

“Nguyen Van A”,

27,

“Nhan vien”,

300f

};

ta có thể truy xuất như sau:

cout << myEmployee1.name; // hiển thị ra “Nguyen Van A”

myEmployee1.age += 1; // Tăng số tuổi lên 1

Đối với kiểu cấu trúc lồng nhau, phép truy nhập đến thuộc tính được thực hiện lần lượt từ cấu trúc
cha đến cấu trúc con.

Ví dụ, với một biến cấu trúc kiểu Employee lồng nhau:
34


Employee myEmployee1 = {

“Nguyen Van A”,

{15, 05, 1980},

“Nhan vien”,

300f

};

ta có thể truy xuất như sau:

cout << myEmployee1.name; // hiển thị ra “Nguyen Van A”

myEmployee1.birthDay.day = 16; // Sửa lại ngày sinh thành 16

myEmployee1.birthDay.month = 07; // Sửa lại tháng sinh thành 07

Chương trình 3.1a minh hoạ việc tạo lập và sử dụng cấu trúc Employee đơn, không dùng từ khoá
typedef.

Chương trình 3.1a

#include<stdio.h>

#include<conio.h>

#include<string.h>

struct Employee{

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

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

char role[20]; // Chức vụ của nhân viên

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

};

/* Khai báo khuôn mẫu hàm */

void Display(Employee myEmployee);

void Display(Employee myEmployee){

cout << “Name: ” << myEmployee.name << endl;

cout << “Age: ” << myEmployee.age << endl;

cout << “Role: ” << myEmployee.role << endl;

cout << “Salary: ” << myEmployee.salary << endl;

return;

}

void main(){

clrscr();

// Hiển thị giá trị mặc định

Employee myEmployee =
{“Nguyen Van A”, 27, “Nhan vien”, 300f};

cout << “Thông tin mặc định:” << endl;

Display(myEmployee);

// Thay đổi giá trị cho các thuộc tính

cout << “Name: ”;

cin >> myEmployee.name;

cout << “Age: ”;

cin >> myEmployee.age;

cout << “Role: ”;

cin >> myEmployee.role;

cout << “Salary: ”;

cin >> myEmployee.salary;

cout << “Thông tin sau khi thay đổi:” << endl;

Display(myEmployee);

return;

}

Chương trình 3.1b minh hoạ việc tạo lập và sử dụng cấu trúc Employee lồng nhau, có dùng từ
khoá typedef.

Chương trình 3.1b

#include<stdio.h>

#include<conio.h>

#include<string.h>

typedef struct {

int day;

int month;

int year;

} Date;

typedef struct {

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

Date birthDay; // Ngày sinh của nhân viên

char role[20]; // Chức vụ của nhân viên

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

} Employee;

/* Khai báo khuôn mẫu hàm */

void Display(Employee myEmployee);


void Display(Employee myEmployee){

cout << “Name: ” << myEmployee.name << endl;

cout << “Birth day: ” << myEmployee.birthDay.day << “/”

<< myEmployee.birthDay.month << “/”

<< myEmployee.birthDay.year << endl;

cout << “Role: ” << myEmployee.role << endl;

cout << “Salary: ” << myEmployee.salary << endl;

return;

}

void main(){

clrscr();

// Hiển thị giá trị mặc định

Employee myEmployee =

{“Nguyen Van A”, {15, 5, 1980}, “Nhan vien”, 300f};

cout << “Thông tin mặc định:” << endl;

Display(myEmployee);

// Thay đổi giá trị cho các thuộc tính

cout << “Name: ”;

cin >> myEmployee.name;

cout << “Day of birth: ”;

cin >> myEmployee.birthDay.day;

cout << “Month of birth: ”;

cin >> myEmployee.birthDay.month;

cout << “Year of birth: ”;

cin >> myEmployee.birthDay.year;

cout << “Role: ”;

cin >> myEmployee.role;

cout << “Salary: ”;

cin >> myEmployee.salary;

cout << “Thông tin sau khi thay đổi:” << endl;

Display(myEmployee);

return;

}

3.3 CON TRỎ CẤU TRÚC VÀ MẢNG CẤU TRÚC

3.3.1 Con trỏ cấu trúc

Con trỏ cấu trúc là một con trỏ trỏđến địa chỉ của một biến có kiểu cấu trúc. Cách khai báo và sử
dụng con trỏ cấu trúc được thực hiện như con trỏ thông thường.

Khai báo con trỏ cấu trúc

Con trỏ cấu trúc được khai báo theo cú pháp:

<Tên kiểu cấu trúc> *<Tên biến>;

Ví dụ, với kiểu khai báo cấu trúc:

typedef struct {

int day;

int month;

int year;

} Date;

và:

typedef struct {

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

Date birthDay; // Ngày sinh của nhân viên

char role[20]; // Chức vụ của nhân viên

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

} Employee;

thì ta có thể khai báo một con trỏ cấu trúc như sau:

Employee *ptrEmployee;

Lưu ý:

• Cũng như khai báo con trỏ thông thường, dấu con trỏ “*” có thể nằm ngay trước tên biến
hoặc nằm ngay sau tên kiểu cấu trúc.

Cũng giống con trỏ thông thường, con trỏ cấu trúc được sử dụng khi:

• Cho nó trỏđến địa chỉ của một biến cấu trúc

• Cấp phát cho nó một vùng nhớ xác định.

Gán địa chỉ cho con trỏ cấu trúc

Một con trỏ cấu trúc có thể trỏđến địa chỉ của một biến cấu trúc có cùng kiểu thông qua phép gán:

<Tên biến con trỏ> = &<Tên biến thường>;

Ví dụ, khai báo và phép gán:

Employee *ptrEmployee, myEmployee;

ptrEmployee = &myEmployee;

sẽđưa con trỏ ptrEmployee trỏđến địa chỉ của biến cấu trúc myEmployee.
Cấp phát b ộ nhớđộng cho con trỏ cấu trúc

Trong trường hợp ta muốn tạo ra một con trỏ cấu trúc mới, không trỏ vào một biến cấu trúc có sẵn
nào, để sử dụng con trỏ mới này, ta phải cấp phát vùng nhớ cho nó. Cú pháp cấp phát vùng nhớ
cho con trỏ cấu trúc:

<Tên biến con trỏ> = new <Kiểu cấu trúc>;

Ví dụ, cấu trúc Employee được khai báo bằng từ khoá typedef, ta có thể cấp phát vùng nhớ cho
con trỏ cấu trúc như sau:

Employee *ptrEmployee;

ptrEmployee = new Employee;

hoặc cấp phát ngay khi khai báo:

Employee *ptrEmployee = new Employee;

Sau khi cấp phát vùng nhớ cho con trỏ bằng thao tác new, khi con trỏ không được dùng nữa, hoặc
cần trỏ sang một địa chỉ khác, ta phải giải phóng vùng nhớ vừa được cấp phát cho con trỏ bằng
thao tác:

delete <Tên biến con trỏ>;

Ví dụ:

Employee *ptrEmployee = new Employee;

…

// Thực hiện các thao tác trên con trỏ

…

delete ptrEmployee;

Lưu ý:

• Thao tác delete chỉđược thực hiện đối với con trỏ mà trước đó, nó được cấp phát bộ nhớ
động thông qua thao tác new:

Employee *ptrEmployee = new Employee;

delete ptrEmployee; //đúng

mà không thể thực hiện với con trỏ chỉ trỏđến địa chỉ của một biến cấu trúc khác:

Employee *ptrEmployee, myEmployee;

ptrEmployee = &myEmployee;

delete ptrEmployee; //lỗi

Truy nhập thu ộc tính của con trỏ cấu trúc

Thuộc tính của con trỏ cấu trúc có thểđược truy nhập thông qua hai cách:

Cách 1:

<Tên biến con trỏ> -> <Tên thuộc tính>;

Cách 2:

(*<Tên biến con trỏ>).<Tên thuộc tính>;

Ví dụ, thuộc tính tên nhân viên của cấu trúc Employee có thểđược truy nhập thông qua hai cách:

Employee *ptrEmployee = new Employee;

cin >> ptrEmployee -> name;

hoặc:
in >> (*ptrEmployee).name;

Lưu ý:

• Trong cách truy nhập thứ hai, phải có dấu ngoặc đơn “()” quanh tên con trỏ vì phép toán
truy nhập thuộc tính “.” có độưu tiên cao hơn phép toán lấy giá trị con trỏ “*”.

• Thông thường, ta dùng cách thứ nhất cho đơn giản và thuận tiện.

Chương trình 3.2 cài đặt việc khởi tạo và hiển thị nội dung của một con trỏ cấu trúc.

Chương trình 3.2

#include<stdio.h>

#include<conio.h>

#include<string.h>

typedef struct {

int day;

int month;

int year;

} Date;

typedef struct {

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

Date birthDay; // Ngày sinh của nhân viên

char role[20]; // Chức vụ của nhân viên

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

} Employee;

/* Khai báo khuôn mẫu hàm */

void InitStruct(Employee *myEmployee);

void Display(Employee *myEmployee);

void InitStruct(Employee *myEmployee){

myEmployee = new Employee;

cout << “Name: ”;

cin >> myEmployee->name;

cout << “Day of birth: ”;

cin >> myEmployee->birthDay.day;

cout << “Month of birth: ”;

cin >> myEmployee->birthDay.month;

cout << “Year of birth: ”;

cin >> myEmployee->birthDay.year;

cout << “Role: ”;

cin >> myEmployee->role;

cout << “Salary: ”;


cin >> myEmployee->salary;

}

void Display(Employee myEmployee){

cout << “Name: ” << myEmployee->name << endl;

cout << “Birth day: ” << myEmployee->birthDay.day << “/”

<< myEmployee->birthDay.month << “/”

<< myEmployee->birthDay.year << endl;

cout << “Role: ” << myEmployee->role << endl;

cout << “Salary: ” << myEmployee->salary << endl;

return;

}

void main(){

clrscr();

Employee *myEmployee;

InitStruct(myEmployee);

Display(myEmployee);

return;

}

3.3.2 Mảng cấu trúc

Khi cần xử lí nhiều đối tượng có dùng kiểu dữ liệu cấu trúc, ta có thể sử dụng mảng các cấu trúc.
Vì một mảng một chiều là tương đương với một con trỏ có cùng kiểu. Do đó, có thể khai báo
mảng theo hai cách: Khai báo mảng tĩnh như thông thường hoặc khai báo mảng động thông qua
con trỏ.

Khai báo mảng tĩnh các cấu trúc

Khai báo mảng tĩnh các cấu trúc theo cú pháp:

<Tên kiểu cấu trúc> <Tên biến mảng>[<Số phần tử mảng>];

Ví dụ:

Employee employees[10];

là khai báo một mảng tên là employees gồm 10 phần tử có kiểu là cấu trúc Employee.

Khai báo mảng động các cấu trúc

Khai báo một mảng động các cấu trúc hoàn toàn tương tự khai báo một con trỏ cấu trúc cùng kiểu:

<Tên kiểu cấu trúc> *<Tên biến>;

Ví dụ, khai báo:

Employee *employees;

vừa có thể coi là khai báo một con trỏ thông thường có cấu trúc Employee, vừa có thể coi là khai
báo một mảng động các cấu trúc có kiểu cấu trúc Employee.
Tuy nhiên, cách cấp phát bộ nhớđộng cho mảng các cấu trúc khác với một con trỏ. Đây là cách
để chương trình nhận biết ta đang dùng một con trỏ cấu trúc hay một mảng động có cấu trúc. Cú
pháp cấp phát bộ nhớ cho mảng động như sau:

<Tên biến mảng> = new <Kiểu cấu trúc>[<Số lượng phần tử>];

Ví dụ, khai báo:

Employee *employees = new Employee[10];

sẽ cấp phát bộ nhớ cho một mảng động employees có 10 phần tử kiểu cấu trúc Employee.

Truy nhập đến phần tử của mảng cấu trúc

Việc truy nhập đến các phần tử của mảng cấu trúc được thực hiện như truy cập đến phần tử của
mảng thông thường. Ví dụ muốn truy nhập đến thuộc tính tên nhân viên phần tử nhân viên thứ i
trong mảng cấu trúc, ta viết như sau:

Employee *employees = new Employee[10];

employees[i].name;

Chương trình 3.3 cài đặt việc khởi tạo một mảng các nhân viên của một phòng trong một công ty.
Sau đó, chương trình sẽ tìm và in ra thông tin về nhân viên có lương cao nhất và nhân viên có
lương thấp nhất trong phòng.

Chương trình 3.3

#include<stdio.h>

#include<conio.h>

#include<string.h>

typedef struct {

int day;

int month;

int year;

} Date;

typedef struct {

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

Date birthDay; // Ngày sinh của nhân viên

char role[20]; // Chức vụ của nhân viên

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

} Employee;

/* Khai báo khuôn mẫu hàm */

void InitArray(Employee *myEmployee, int length);

Employee searchSalaryMax(Employee *myEmployee, int length);

Employee searchSalaryMin(Employee *myEmployee, int length);

void Display(Employee myEmployee);

void InitArray(Employee *myEmployee, int length){

myEmployee = new Employee[length];

for(int i=0; i<length; i++){

cout << “Nhan vien thu ” << i << endl;

cout << “Name: ”;

cin >> myEmployee[i].name;

cout << “Day of birth: ”;

cin >> myEmployee[i].birthDay.day;

cout << “Month of birth: ”;

cin >> myEmployee[i].birthDay.month;

cout << “Year of birth: ”;

cin >> myEmployee[i].birthDay.year;

cout << “Role: ”;

cin >> myEmployee[i].role;

cout << “Salary: ”;

cin >> myEmployee[i].salary;

}

return;

}

Employee searchSalaryMax(Employee *myEmployee, int length){

int index = 0;

int maxSalary = myEmployee[0].salary;

for(int i=1; i<length; i++)

if(myEmployee[i].salary > maxSalary){

maxSalary = myEmployee[i].salary;

index = i;

}

return myEmployee[index];

}

Employee searchSalaryMin(Employee *myEmployee, int length){

int index = 0;

int minSalary = myEmployee[0].salary;

for(int i=1; i<length; i++)

if(myEmployee[i].salary < minSalary){

minSalary = myEmployee[i].salary;

index = i;

}

return myEmployee[index];

}

void Display(Employee myEmployee){

cout << “Name: ” << myEmployee.name << endl;

cout << “Birth day: ” << myEmployee.birthDay.day << “/”

<< myEmployee.birthDay.month << “/”

<< myEmployee.birthDay.year << endl;

cout << “Role: ” << myEmployee.role << endl;

cout << “Salary: ” << myEmployee.salary << endl;

return;

}

void main(){

clrscr();

Employee *myEmployee, tmpEmployee;

int length = 0;

cout << “So luong nhan vien: ”;

cin >> length;

// Khởi tạo danh sách nhân viên

InitArray(myEmployee);

// Nhân viên có lương cao nhất

tmpEmployee = searchSalaryMax(myEmployee, length);

Display(tmpEmployee);

// Nhân viên có lương thấp nhất

tmpEmployee = searchSalaryMin(myEmployee, length);

Display(tmpEmployee);

// Giải phóng vùng nhớ

delete [ ] myEmployee;

return;

}

3.4 MỘT SỐ KIỂU DỮ LIỆU TRỪU TƯỢNG

Nội dung phần này tập trung trình bày việc cài đặt một số cấu trúc dữ liệu trừu tượng, bao gồm:

• Ngăn xếp (stack)

• Hàng đợi (queue)

• Danh sách liên kết (list)
3.4.1 Ngăn xếp

Ngăn xếp (stack) là một kiểu danh sách cho phép thêm và bớt các phần tửở một đầu danh sách,
gọi là đỉnh của ngăn xếp. Ngăn xếp hoạt động theo nguyên lí: phần tử nào được đưa vào sau, sẽ
được lấy ra trước.

Định nghĩa cấu trúc ngăn xếp

Vì ta chỉ cần quan tâm đến hai thuộc tính của ngăn xếp là:

• Danh sách các phần tử của ngăn xếp

• Vị trí đỉnh của ngăn xếp

nên ta có thểđịnh nghĩa cấu trúc ngăn xếp như sau (các phần tử của ngăn xếp có kiểu int):

typedef SIZE 100;

typedef struct {

int top; // Vị trí của đỉnh

int nodes[SIZE]; // Danh sách các phần tử

} Stack;

Tuy nhiên, định nghĩa này tồn tại một vấn đề, đó là kích thước (SIZE) của danh sách chứa các
phần tử là tĩnh. Do đó:

• Nếu ta chọn SIZE lớn, nhưng khi gặp ứng dụng chỉ cần một số ít phần tử cho ngăn xếp thì
rất tốn bộ nhớ.

• Nếu ta khai báo SIZE nhỏ, thì khi gặp bài toán cần ngăn xếp có nhiều phần tử, ta sẽ không
thêm được các phần tử mới vào, chương trình sẽ có lỗi.

Để khắc phục hạn chế này, ta có thể sử dụng bộ nhớđộng (mảng động thông qua con trỏ) để lưu
danh sách các phần tử của ngăn xếp. Khi đó, định nghĩa cấu trúc ngăn xếp sẽ có dạng như sau:

typedef struct {

int top; // Vị trí của đỉnh

int *nodes; // Danh sách các phần tử

} Stack;

Ta sẽ sử dụng định nghĩa này trong các chương trình ứng dụng ngăn xếp.

Các thao tác trên ngăn xếp

Đối với các thao tác trên ngăn xếp, ta quan tâm đến hai thao tác cơ bản:

• Thêm một phần tử mới vào đỉnh ngăn xếp, gọi là push.

• Lấy ra một phần tử từđỉnh ngăn xếp, gọi là pop.

Khi thêm một phần tử mới vào ngăn xếp, ta làm các bước như sau:

1. Số phần tử trong ngăn xếp cũ là (top+1). Do đó, ta cấp phát một vùng nhớ mới để lưu
được (top+1+1) = (top+2) phần tử.

2. Sao chép (top+1) phần tử cũ sang vùng mới. Nếu danh sách ban đầu rỗng (top = -1) thì
không cần thực hiện bước này.

3. Thêm phần tử mới vào cuối vùng nhớ mới

4. Giải phóng vùng nhớ của danh sách cũ

5. Cho danh sách nodes trỏ vào vùng nhớ mới.

Chương trình 3.4a cài đặt thủ tục thêm một phần tử mới vào ngăn xếp.

Chương trình 3.4a

void push(Stack *stack, int node){

int *tmpNodes = new int[stack->top + 2];// Cấp phát vùng nhớ mới

stack->top ++; // Tăng chỉ số của node đỉnh

for(int i=0; i<stack->top; i++) // Sao chép sang vùng nhớ mới

tmpNodes[i] = stack->nodes[i];

tmpNodes[stack->top] = node; // Thêm node mới vào đỉnh

delete [] stack->nodes; // Giải phóng vùng nhớ cũ

stack->nodes = tmpNodes; // Trỏ vào vùng nhớ mới

return;

}

Khi lấy ra một phần tử của ngăn xếp, ta làm các bước như sau:

• Kiểm tra xem ngăn xếp có rỗng (top = -1) hay không. Nếu không rỗng thì thực hiện các
bước tiếp theo.

• Lấy phần tửởđỉnh ngăn xếp ra

• Cấp phát một vùng nhớ mới có (top+1) -1 = top phần tử

• Sao chép top phần tử từ danh sách cũ sang vùng nhớ mới (trừ phần tửởđỉnh).

• Giải phóng vùng nhớ cũ

• Cho con trỏ danh sách trỏ vào vùng nhớ mới.

• Trả về giá trị phần tửởđỉnh đã lấy ra.

Chương trình 3.4b cài đặt thủ tục lấy một phần tử từ ngăn xếp.

Chương trình 3.4b

int pop(Stack *stack){

if(stack->top < 0){ // Kiểm tra ngăn xếp rỗng

cout << “Stack is empty!” << endl;

return 0;

}

int result = stack->nodes[stack->top];// Lưu giữ giá trị đỉnh

int *tmpNodes = new int[stack->top];// Cấp phát vùng nhớ mới

for(int i=0; i<stack->top; i++) // Sao chép sang vùng nhớ mới

tmpNodes[i] = stack->nodes[i];

stack->top --; // Giảm chỉ số của node đỉnh

delete [ ] stack->nodes; // Giải phóng vùng nhớ cũ

stack->nodes = tmpNodes; // Trỏ vào vùng nhớ mới

return result; // Trả về giá trị node đỉnh
}

Áp dụng

Ngăn xếp được sử dụng trong các ứng dụng thoả mãn nguyên tắc: cái nào đặt vào trước sẽđược
lấy ra sau. Chương trính 3.4c minh hoạ việc dùng ngăn xếp đểđảo ngược một xâu kí tựđược nhập
vào từ bàn phím.

Chương trình 3.4c

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

typedef struct {

int top; // Vị trí node đỉnh

int *nodes; // Danh sách phần tử

} Stack;

/* Khai báo nguyên mẫu hàm */

void init(Stack *stack);

void push(Stack *stack, int node);

int pop(Stack *stack);

void release(Stack *stack);

void init(Stack *stack){

stack = new Stack; // Cấp phát vùng nhớ cho con trỏ

stack->top = -1; // Khởi tạo ngăn xếp rỗng

}

void push(Stack *stack, int node){

int *tmpNodes = new int[stack->top + 2];// Cấp phát vùng nhớ mới

stack->top ++; // Tăng chỉ số của node đỉnh

for(int i=0; i<stack->top; i++) // Sao chép sang vùng nhớ mới

tmpNodes[i] = stack->nodes[i];

tmpNodes[stack->top] = node; // Thêm node mới vào đỉnh

delete [] stack->nodes; // Giải phóng vùng nhớ cũ

stack->nodes = tmpNodes; // Trỏ vào vùng nhớ mới

return;

}

int pop(Stack *stack){

if(stack->top < 0){ // Kiểm tra ngăn xếp rỗng
cout << “Stack is empty!” << endl;

return 0;

}

int result = stack->nodes[stack->top];// Lưu giữ giá trị đỉnh

int *tmpNodes = new int[stack->top];// Cấp phát vùng nhớ mới

for(int i=0; i<stack->top; i++) // Sao chép sang vùng nhớ mới

tmpNodes[i] = stack->nodes[i];

stack->top --; // Giảm chỉ số của node đỉnh

delete [] stack->nodes; // Giải phóng vùng nhớ cũ

stack->nodes = tmpNodes; // Trỏ vào vùng nhớ mới

return result; // Trả về giá trị node đỉnh

}

void release(Stack *stack){

delete [ ] stack->nodes; // Giải phóng vùng danh sách

delete stack; // Giải phóng con trỏ

return;

}

void main(){

clrscr();

Stack *stack;

init(stack); // Khởi tạo ngăn xếp

char strIn[250];

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

cout << “Nhap chuoi: ”;

cin >> strIn;

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

push(stack, strIn[i]);

while(stack->top > -1) // Lấy ra từ ngăn xếp

cout << pop(stack);

release(stack); // Giải phóng bộ nhớ

return;

}

3.4.2 Hàng đợi

Hàng đợi (queue) cũng là một cấu trúc tuyến tính các phần tử. Trong đó, các phần tử luôn được
thêm vào ở một đầu, gọi là đầu cuối hàng đợi, và việc lấy ra các phần tử luôn được thực hiện ở
đầu còn lại, gọi là đầu mặt của hàng đợi. Hàng đợi hoạt động theo nguyên lí: phần tử nào được
đưa vào trước, sẽđược lấy ra trước.


Định nghĩa cấu trúc hàng đợi

Hàng đợi có các thuộc tính:

• Một danh sách các phần tử có mặt trong hàng đợi.

• Chỉ số của phần tửđứng đầu của danh sách (front).

• Chỉ số phần tử cuối của danh sách (rear).

Nếu dùng cấu trúc tĩnh đểđịnh nghĩa, hàng đợi có cấu trúc như sau:

typedef SIZE 100;

typedef struct {

int front, rear; // Vị trí của đỉnh đầu, đỉnh cuối

int nodes[SIZE]; // Danh sách các phần tử

} Queue;

Nếu dùng bộ nhớđộng để lưu giữ hàng đợi, thì phần tử front luôn là phần tử thứ 0 của danh sách.
Và rear sẽ bằng độ dài danh sách trừđi 1. Cấu trúc động của hàng đợi:

typedef struct {

int front, rear; // Vị trí của đỉnh đầu, đỉnh cuối

int *nodes; // Danh sách các phần tử

} Queue;

Thao tác trên hàng đợi

• Thêm một phần tử vào cuối hàng đợi

• Lấy một phần tửở vị trí đầu của hàng đợi

Thao tác thêm một phần tử vào cuối hàng đợi với bộ nhớđộng được thực hiện tương tự với ngăn
xếp. Chương trình 3.5a cài đặt thủ tục thêm một phần tử vào cuối hàng đợi động.

Chương trình 3.5a

void insert(Queue *queue, int node){

int *tmpNodes = new int[queue->rear + 2];// Cấp phát vùng nhớ mới

queue->rear ++; // Tăng chỉ số của node đuôi

if(queue->front == -1) // Nếu hàng đợi cũ rống

queue->front = 0; // thì cập nhật front

for(int i=0; i<queue->rear; i++) // Sao chép sang vùng nhớ mới

tmpNodes[i] = queue->nodes[i];

tmpNodes[queue->rear] = node; // Thêm node mới vào đuôi

delete [ ] queue->nodes; // Giải phóng vùng nhớ cũ

queue->nodes = tmpNodes; // Trỏ vào vùng nhớ mới

return;

}

Thao tác lấy ra một phần tửđầu của hàng đợi thực hiện theo các bước:

1. Kiểm tra tính rỗng (front = rear = -1) của hàng đợi. Nếu không rỗng mới thực hiện tiếp

2. Lấy phần tử nodes[0] ra.

3. Sao chép danh sách còn lại sang vùng nhớ mới

4. Giải phóng vùng nhớ cũ

5. Đưa danh sách trỏ vào vùng nhớ mới

6. Trả về giá trị phần tử lấy ra

Chương trình 3.5b cài đặt thủ tục lấy ra một phần tử của hàng đợi động.

Chương trình 3.5b

int remove(Queue *queue){

if((queue-front < 0)||(queue-rear < 0)){// Kiểm tra hàng đợi rỗng

cout << “Queue is empty!” << endl;

return 0;

}

// Lưu giữ giá trị phần tử đầu

int result = queue->nodes[queue->front];

int *tmpNodes;

if(queue->rear > 0){ // Nếu có hơn 1 phần tử

tmpNodes = new int[queue->rear];// Cấp phát vùng nhớ mới

for(int i=0; i<queue->rear; i++)// Sao chép sang vùng nhớ mới

tmpNodes[i] = queue->nodes[i];

}else // Nếu chỉ có 1 phần tử

queue->front --; // Hàng đợi thành rỗng

queue->rear --; // Giảm chỉ số của node đuôi

delete [ ] queue->nodes; // Giải phóng vùng nhớ cũ

queue->nodes = tmpNodes; // Trỏ vào vùng nhớ mới

return result; // Trả về giá trị node đầu

}

Áp dụng

Hàng đợi được áp dụng trong các bài toán cần cơ chế quản lí cái nào vào trước sẽđược lấy ra
trước. Chương trình 3.5c minh hoạ cơ chế quản lí tiến trình đơn giản nhất của hệđiều hành: các
tiến trình được quản lí theo mã tiến trình, khi xuất hiện, tiến trình được đưa vào cuối của một hàng
đợi. Khi nào CPU rảnh thì sẽ lấy tiến trình đầu hàng đợi ra để thực hiện.

Chương trình 3.5c

#include<stdio.h>

#include<conio.h>

typedef struct {

int front, rear; // Vị trí của đỉnh đầu, đỉnh cuối

int *nodes; // Danh sách các phần tử

} Queue;

/* Khai báo các nguyên mẫu hàm */

void init(Queue *queue);

void insert(Queue *queue, int node);

int remove(Queue *queue);

void travese(Queue *queue);

void release(Queue *queue);

void init(Queue *queue){

queue = new Queue; // Cấp phát bộ nhớ cho con trỏ

queue->front = -1; // Khởi tạo danh sách rỗng

queue->rear = -1;

return;

}

void insert(Queue *queue, int node){

int *tmpNodes = new int[queue->rear + 2];// Cấp phát vùng nhớ mới

queue->rear ++; // Tăng chỉ số của node đuôi

if(queue->front == -1) // Nếu hàng đợi cũ rống

queue->front = 0; // thì cập nhật front

for(int i=0; i<queue->rear; i++) // Sao chép sang vùng nhớ mới

tmpNodes[i] = queue->nodes[i];

tmpNodes[queue->rear] = node; // Thêm node mới vào đuôi

delete [] queue->nodes; // Giải phóng vùng nhớ cũ

queue->nodes = tmpNodes; // Trỏ vào vùng nhớ mới

return;

}

int remove(Queue *queue){

if((queue-front < 0)||(queue-rear < 0)){// Kiểm tra hàng đợi rỗng

cout << “Queue is empty!” << endl;

return 0;

}

// Lưu giữ giá trị phần tử đầu

int result = queue->nodes[queue->front];

int *tmpNodes;

if(queue->rear > 0){ // Nếu có hơn 1 phần tử

tmpNodes = new int[queue->rear];// Cấp phát vùng nhớ mới

for(int i=0; i<queue->rear; i++)// Sao chép sang vùng nhớ mới

tmpNodes[i] = queue->nodes[i];

}else // Nếu chỉ có 1 phần tử


queue->front --; // Hàng đợi thành rỗng

queue->rear --; // Giảm chỉ số của node đuôi

delete [ ] queue->nodes; // Giải phóng vùng nhớ cũ

queue->nodes = tmpNodes; // Trỏ vào vùng nhớ mới

return result; // Trả về giá trị node đầu

}

void travese(Queue *queue){

if(queue->front < 0){ // Khi danh sách rỗng

cout << “Danh sach rong!” << endl;

return;

}

for(int i=queue->front; i<=queue.rear; i++)

cout << queue->nodes[i] << “ ”;// Liệt kê các phần tử

cout << endl;

return;

}

void release(Queue *queue){

if(queue->front > -1) //Nếu danh sách không rỗng thì

delete [ ] queue->nodes; //giải phóng vùng nhớ của danh sách

delete queue; //Giải phóng vùng nhớ của con trỏ

}

void main(){

clrscr();

Queue *queue;

init(queue); // Khởi tạo hàng đợi

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;

insert(queue, maso);

break;

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

cout << “Tien trinh duoc thuc hien: ” <<
remove(queue) << endl;

break;

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

cout<<“Cac tien trinh dang o trong hang doi la:”

<<endl;

travese(queue);

break;

}while(function != ‘5’);

release(queue); // Giải phóng hàng đợi

return;

}

3.4.3 Danh sách liên kết

Danh sách liên kết là một kiểu dữ liệu bao gồm một dãy các phần tử có thứ tự, các phần tử có
cùng cấu trúc dữ liệu, ngoại trừ node đầu tiên của danh sách là node lưu thông tin về danh sách.
Có hai loại danh sách liên kết:

• Danh sách liên kết đơn: mỗi node có một con trỏ trỏđến node tiếp theo trong danh sách

• Danh sách liên kết kép: mỗi node có hai con trỏ, một trỏ vào node trước, một trỏ vào node
tiếp theo trong danh sách.

Trong phần này sẽ trình bày danh sách liên kết đơn. Danh sách liên kết kép được coi như là một
bài tập mở rộng từ danh sách liên kết đơn.

Định nghĩa danh sách đơn

Mỗi node của danh sách đơn chứa dữ liệu của nó, đồng thời trỏđến node tiếp theo trong danh
sách, cấu trúc một node như sau:

struct simple{

Employee employee; // Dữ liệu của node có kiểu Employee

struct simple *next; // Trỏ đến node kế tiếp

};

typedef struct simple SimpleNode;

Node đầu của danh sách đơn có cấu trúc riêng, nó không chứa dữ liệu như node thường mà chứa
các thông tin:

• Số lượng node trong danh sách (không kể bản thân nó – node đầu)

• Con trỏđến node đầu tiên của danh sách

• Con trỏđến node cuối cùng của danh sách

Do vậy, cấu trúc node đầu của danh sách đơn là:
typedef struct{

int nodeNumber; // Số lượng các node

SimpleNode *front, *rear;// Trỏ đến node đầu và cuối danh sách

} SimpleHeader;

Các thao tác trên danh sách liên kết đơn

Các thao tác cơ bản trên danh sách đơn bao gồm:

• Chèn thêm một node vào vị trí thứ n trong danh sách

• Loại ra một node ở vị trí thứ n trong danh sách

Việc chèn thêm một node vào vị trí thứ n trong danh sách được thực hiện theo các bước:

1. Nếu n<=0, chèn vào đầu. Nếu n>số phần tử của danh sách, chèn vào cuối. Trường hợp
còn lại, chèn vào giữa.

2. Tìm node thứ n: giữ vết của hai node thứ n-1 và thứ n.

3. Tạo một node mới: cho node thứ n-1 trỏ tiếp vào node mới và node mới trỏ tiếp vào node
thứ n.

Chương trình 3.6a cài đặt thủ tục chèn một node vào vị trí thứ n của danh sách.

Chương trình 3.6a

void insert(SimpleHeader *list, int position, int value){

SimpleNode *newNode = new SimpleNode;

newNode->value = value;

if(position <= 0){ // Chèn vào đầu ds

newNode->next = list->front; // Chèn vào trước node đầu

list->front = newNode; // Cập nhật lại node đầu ds

if(list->nodeNumber == 0) // Nếu ds ban đầu rỗng thì

list->rear = newNode; // node đuôi trùng với node đầu

}else if(position >= list->nodeNumber){// Chèn vào cuối ds

list->rear->next = newNode; // Chèn vào sau node cuối

list->rear = newNode; // Cập nhật lại node cuối ds

if(list->nodeNumber == 0) // Nếu ds ban đầu rỗng thì

list->front = newNode; // node đầu trùng node đuôi

}else{ // Chèn vào giữa ds

SimpleNode *prev = list->front, *curr = list->front;

int index = 0;

while(index < position){ // tìm node n-1 và n

prev = curr;

curr = curr->next;

index++;

}

newNode->next = curr; // chèn vào trước node n

prev->next = newNode; // và chèn vào sau node n-1

}
list->nodeNumber++; // Cập nhật số lượng node

return;

}

Việc xoá một node ở vị trí thứ n trong danh sách được thực hiện theo các bước:

1. Nếu n<0 hoặc n>số phần tử của danh sách, không xoá node nào.

2. Tìm node thứ n: giữ vết của ba node thứ n-1, thứ n và thứ n+1.

3. Cho node thứ n-1 trỏ tiếp vào node thứ n+1, xoá con trỏ của node thứ n.

4. Trả về node thứ n.

Chương trình 3.6b cài đặt thủ tục xoá một node ở vị trí thứ n của danh sách.

Chương trình 3.6b

SimpleNode* remove(SimpleHeader *list, int position){

if((position < 0)||(position >= list->nodeNumber))

return NULL; // Không xoá node nào cả

SimpleNode* result;

if(position == 0){ // Xoá node đầu

result = list->front; // Giữ node cần xoá

list->front = list->front->next;// Cập nhật node đầu

if(list->nodeNumber == 1) // Nếu ds chỉ có 1 node thì

list->rear = list->front;// Cập nhật node cuối ds

}else if(position == list->nodeNumber – 1){

result = list->rear; // Giữ node cần xoá

SimpleNode *curr = list->front;

while(curr->next != list->rear)

curr = curr->next; // Tìm node trước của node cuối

curr->next = NULL; // Xoá node rear hiện tại

list->rear = curr; // Cập nhật node cuối ds

}else{

SimpleNode *prev = list->front, *curr = list->front;

int index = 0;

while(index < position){ // Tìm node n-1 và n

prev = curr;

curr = curr->next;

index++;

}

result = curr; // Giữ node cần xoá

prev->next = curr->next; // Cho node n-1 trỏ đến node n+1

}

list->nodeNumber --; // Cập nhật số lượng node

return result; // Trả về node cần xoá
}

Áp dụng

Chương trình 3.6c minh hoạ việc dùng danh sách liên kết đơn để quản lí nhân viên văn phòng với
các thông tin rất đơn giản: tên, tuổi và tiền lương của mỗi nhân viên.

Chương trình 3.6c

#include<stdio.h>

#include<conio.h>

#include<string.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;

struct simple{

Employee employee; // Dữ liệu của node

struct simple *next; // Trỏ đến node kế tiếp

};

typedef struct simple SimpleNode;

typedef struct{

int nodeNumber; // Số lượng các node

SimpleNode *front, *rear; // Trỏ đến node đầu và cuối ds

} SimpleHeader;

/* Khai báo các nguyên mẫu hàm */

void init(SimpleHeader *list);

void insert(SimpleHeader *list, int position, Employee employee);

SimpleNode* remove(SimpleHeader *list);

void travese(SimpleHeader *list);

void release(SimpleHeader *list);

void init(SimpleHeader *list){

list = new list; // Cấp phát bộ nhớ cho con trỏ

list->front = NULL; // Khởi tạo danh sách rỗng

list->rear = NULL;
list->nodeNumber = 0;

return;

}

void insert(SimpleHeader *list, int position, Employee employee){

SimpleNode *newNode = new SimpleNode;

newNode->employee = employee;

if(position <= 0){ // Chèn vào đầu ds

newNode->next = list->front; // Chèn vào trước node đầu

list->front = newNode; // Cập nhật lại node đầu ds

if(list->nodeNumber == 0) // Nếu ds ban đầu rỗng thì

list->rear = newNode; // node đuôi trùng với node đầu

}else if(position >= list->nodeNumber){// Chèn vào cuối ds

list->rear->next = newNode; // Chèn vào sau node cuối

list->rear = newNode; // Cập nhật lại node cuối ds

if(list->nodeNumber == 0)// Nếu ds ban đầu rỗng thì

list->front = newNode; // node đầu trùng node đuôi

}else{ // Chèn vào giữa ds

SimpleNode *prev = list->front, *curr = list->front;

int index = 0;

while(index < position){// tìm node n-1 và n

prev = curr;

curr = curr->next;

index++;

}

newNode->next = curr; // chèn vào trước node n

prev->next = newNode; // và chèn vào sau node n-1

}

list->nodeNumber++; // Cập nhật số lượng node

return;

}

SimpleNode* remove(SimpleHeader *list, int position){

if((position < 0)||(position >= list->nodeNumber))

return NULL; // Không xoá node nào cả

SimpleNode* result;

if(position == 0){ // Xoá node đầu

result = list->front; // Giữ node cần xoá

list->front = list->front->next;// Cập nhật node đầu

if(list->nodeNumber == 1) // Nếu ds chỉ có 1 node thì

list->rear = list->front;// Cập nhật node cuối ds

}else if(position == list->nodeNumber – 1){

result = list->rear; // Giữ node cần xoá


SimpleNode *curr = list->front;

while(curr->next != list->rear)

curr = curr->next;// Tìm node trước của node cuối

curr->next = NULL; // Xoá node rear hiện tại

list->rear = curr; // Cập nhật node cuối ds

}else{

SimpleNode *prev = list->front, *curr = list->front;

int index = 0;

while(index < position){// Tìm node n-1 và n

prev = curr;

curr = curr->next;

index++;

}

result = curr; // Giữ node cần xoá

prev->next = curr->next;// Cho node n-1 trỏ đến node n+1

}

list->nodeNumber --; // Cập nhật số lượng node

return result; // Trả về node cần xoá

}

void travese(SimpleHeader *list){

if(list->nodeNumber <= 0){ // Khi danh sách rỗng

cout << “Danh sach rong!” << endl;

return;

}

SimpleNode *curr = list->front;

while(curr != NULL){

cout << curr->employee.name << “ ”

<< curr->employee.age << “ “

<< curr->employee.salary << endl;// Liệt kê các phần tử

curr = curr->next;

}

return;

}

void release(SimpleHeader *list){

SimpleNode* curr = remove(list, 0);

while(curr != NULL){

delete curr; //Giải phóng vùng nhớ của node

curr = remove(list, 0);

}

delete list; //Giải phóng vùng nhớ của con trỏ

}
void main(){

clrscr();

SimpleHeader *list;

init(list); // Khởi tạo ds

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;

insert(list, position, employee);

break;

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

int position;

cout << “Vi tri can xoa: ”;

cin >> position;

SimpleNode* result = remove(list, position);

if(result != NULL){

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

cout << “Ten: ” << result->employee.name

<< endl;

cout << “Tuoi: ” << result->employee.age

<< endl;

cout << “Luong: ”

<< result->employee.salary << endl;

}

break;

case ‘3’: // Duyệt ds

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

travese(list);

break;

}while(function != ‘5’);

release(list); // Giải phóng ds

r