CHƯƠNG I : TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ THUẬT GIẢI
CHƯƠNG II : MỘT SỐ THUẬT TOÁN TÌM KIẾM VÀ SẮP XẾP
CHƯƠNG III : DANH SÁCH LIÊN KẾT - NGĂN XẾP VÀ HÀNG ĐỢI
CHƯƠNG IV : CÂY
I. KIỂU CON TRỎ
1. Giới Thiệu Kiểu Dữ Liệu Con Trỏ
25N A M 4
int andy = 25
Địa chỉ ô nhớ
Nội dung ô nhớ
Bộ nhớ
b = 4
char name[10] = “NAM”
2 5 7 9
2 5 7 9 4 8 9
int a[6]
char ten[100]
I. KIỂU CON TRỎ
1. Giới Thiệu Kiểu Dữ Liệu Con Trỏ
25
a = 25
Con trỏ là biến lưu địa chỉ của biến khác
c = *pa
I. KIỂU CON TRỎ
1. Giới Thiệu Kiểu Dữ Liệu Con Trỏ
a b
pa = &a
pa
b = a
25
c

25
andy = 25
ted = &andy
25
6442
6442
andy =
&andy =
ted =
&ted =
*ted =
I. KIỂU CON TRỎ
1. Giới Thiệu Kiểu Dữ Liệu Con Trỏ
andy ted
25
6442
6442
8444
25
*P
25
andy
Một số hạn chế có thể gặp phải khi sử dụng các biến tĩnh:

Cấp phát ô nhớ dư, gây ra lãng phí ô nhớ.

Cấp phát ô nhớ thiếu, chương trình thực thi bị lỗi.
Để tránh những hạn chế trên, ngôn ngữ C++ cung cấp cho ta một loại biến đặc biệt gọi là biến động với các đặc
điểm sau:


Chỉ phát sinh trong quá trình thực hiện chương trình chứ không phát sinh lúc bắt đầu chương trình.

Khi chạy chương trình, kích thước của biến, vùng nhớ và địa chỉ vùng nhớ được cấp phát cho biến có thể
thay đổi.

Sau khi sử dụng xong có thể giải phóng để tiết kiệm chỗ trong bộ nhớ.
Tuy nhiên các biến động không có địa chỉ nhất định nên ta không thể truy cập đến chúng được. Vì thế, ngôn ngữ C+
+ lại cung cấp cho ta một loại biến đặc biệt nữa để khắc phục tình trạng này, đó là biến con trỏ (pointer) với các đặc
điểm:

Biến con trỏ không chứa dữ liệu mà chỉ chứa địa chỉ của dữ liệu hay chứa địa chỉ của ô nhớ chứa dữ liệu.

Kích thước của biến con trỏ không phụ thuộc vào kiểu dữ liệu, luôn có kích thước cố định là 2 byte.
I. KIỂU CON TRỎ
1. Giới Thiệu Kiểu Dữ Liệu Con Trỏ

Toán tử lấy địa chỉ (&)
Ví dụ :
int a;
int *p;
p = &a;

Toán tử tham chiếu (*)
Ví dụ :
int a, b;
int *p;
a = 2;
p = &a;
b = *p;
I. KIỂU CON TRỎ

1. Giới Thiệu Kiểu Dữ Liệu Con Trỏ
Cú pháp: <Kiểu> * <Tên con trỏ>
Ý nghĩa: Khai báo một biến có tên là <Tên con trỏ> con trỏ dùng để chứa
địa chỉ của các biến có kiểu <Kiểu>
Ví dụ 1:
Khai báo 2 biến a, b có kiểu int và 2 biến pa, pb là 2 biến con trỏ kiểu int
int a, b, *pa, *pb;
Ví dụ 2:
Khai báo biến f kiểu float và biến pf là con trỏ float
float f, *pf;
I. KIỂU CON TRỎ
2. Khai báo biến Con Trỏ
char *ted = “hello”
h e l l o \0
5441
5441
ted [4]
*(ted + 4)
ted
I. KIỂU CON TRỎ
2. Khai báo biến Con Trỏ
Ví dụ:
int a;
float b;
int *pa;
float *pb;
pa = &a;
pb = &b;
Lưu ý: ví dụ sau đây không đúng do không tương thích kiểu:
int a;

float *pb;
pb = &a;
I. KIỂU CON TRỎ
2. Các thao tác trên Con Trỏ
2.1 Gán địa chỉ của biến cho biến con trỏ (Toán tử &)
I. KIỂU CON TRỎ
2. Các thao tác trên Con Trỏ
2.2 Nội dung của ô nhớ con trỏ chỉ tới (Toán tử *)
Ví dụ:
int x = 100;
int y;
int *ptr;
ptr = &x;
y = *ptr; cout << x << “ ” << y << “\n”;
*ptr = 3; cout << x << “ ” << y << “\n”;
Việc thực hiện các phép tính số học với con trỏ hơi khác so với các kiểu
dữ liệu số nguyên khác, trước hết chỉ phép cộng và phép trừ được phép
dùng. Nhưng kết quả cộng trừ phụ thuộc vào kích thức dữ liệu mà biến
con trỏ trỏ tới
char chiếm 1byte, int chiếm 2 byte, long chiếm 4 byte
Ví dụ
char *mychar
int *myint
long *mylong
mychar++
myint++
mylong++
mychar : 1000
myint : 2000
mylong : 3000

I. KIỂU CON TRỎ
2. Các thao tác trên Con Trỏ
2.3 Các phép tính số học với pointer
#include <iostream.h>
void main()
{
int value1 = 5, value2 = 15;
int *mypointer;
mypointer = &value1;
*mypointer = 10;
mypointer = &value2;
*mypointer = 20;
cout << “Value 1 = ” << value1 << “Value 2 = ” << value2;
}
Value 1 = 10 Value 2 = 20
I. KIỂU CON TRỎ
2. Các thao tác trên Con Trỏ
2.3 Các phép tính số học với pointer
#include <iostream.h>
void main()
{
int value1 = 5, value2 = 15;
int *p1, *p2;
p1 = &value1;
p2 = &value2;
*p1 = 10;
*p2 = *p1;
p1 = p2;
*p1 = 20;
cout << “Value 1 = ” << value1 << “Value2 = ” << value2;

}
Value 1 = 10 Value 2 = 20
I. KIỂU CON TRỎ
2. Các thao tác trên Con Trỏ
2.3 Các phép tính số học với pointer
#include <iostream.h>
void main()
{
int a[5]; int *p;
int i;
p = a;
*p = 6;
p++; *p=4;
p = &a[2]; *p = 9;
p = a+3; *p = 2;
p = a; *(p+4) = 7;
for (i = 0; i < 5;i++)
cout << a[i]; << “, ”;
}
I. KIỂU CON TRỎ
2. Các thao tác trên Con Trỏ
2.3 Các phép tính số học với pointer
6, 4, 9, 2, 7
I. KIỂU CON TRỎ
3. Cấp phát vùng nhớ cho biến con trỏ
<pointer > = new <kieu cau truc>
delete < pointer >
Ví dụ: Giả sử ta có khai báo
struct node
{

int info;
node *pNext;
};
node *p;
p = new node;
delete p;
II. DANH SÁCH LIÊN KẾT ĐƠN
1. Khái niệm

Cấu trúc danh sách liên kết là cấu trúc động, việc cấp phát nút và giải
phóng nút trên danh sách xảy ra khi chương trình đang chạy. Ta thường
cấp phát nút cho danh sách liên kết bằng biến động.

Các phần tử sẽ được cấp phát vùng nhớ trong quá trình thực thi
chương trình, do đó chúng có thể nằm rải rác ở nhiều nơi khác nhau trong
bộ nhớ (phân bố không liên tục).
II. DANH SÁCH LIÊN KẾT ĐƠN
1. Khái niệm
NULL
pFirst
II. DANH SÁCH LIÊN KẾT ĐƠN
1. Khái niệm

pFirst là con trỏ chỉ đến phần tử đầu tiên của danh sách.

Phần tử cuối của danh sách liên kết với vùng liên kết có nội dung NULL.

Mỗi nút của danh sách có trường info chứa nội dung của nút và trường
pNext là con trỏ chỉ đến nút kế tiếp trong danh sách.
pNextinfo

32 1FF60 66
1FF90
1FF60
66
00000
1FF901FF30
II. DANH SÁCH LIÊN KẾT ĐƠN
2. Các đặc tính

Cấu trúc DSLK là cấu trúc động, các nút được cấp phát hoặc giải phóng
khi chương trình đang chạy.

DSLK rất thích hợp khi thực hiện các phép toán trên danh sách thường bị
biến động. Trong trường hợp xoá hay thêm phần tử trong DSLK thì ta không
dời các phần tử đi như trong mảng mà chỉ việc hiệu chỉnh lại trường pNext tại
các nút đang thao tác. Thời gian thực hiện các phép toán thêm vào và loại bỏ
không phụ thuộc vào số phần tử của DSLK.
Hạn chế của Danh Sách Liên Kết :

Vì mỗi nút của DSLK phải chứa thêm trường pNext nên DSLK phải
tốn thêm bộ nhớ.

Tìm kiếm trên DSLK không nhanh vì ta chỉ được truy xuất tuần tự từ
đầu danh sách.
II. DANH SÁCH LIÊN KẾT ĐƠN
2. Các đặc tính
II. DANH SÁCH LIÊN KẾT ĐƠN
3. Khai báo và khởi tạo
struct node
{

int info;
node *pNext;
};
// Khai báo biến First quản lý DSLK:
node *pFirst;
//Khởi tạo DSLK:
pFirst = NULL;
pFirst
NULL
II. DANH SÁCH LIÊN KẾT ĐƠN
4. Các phép toán trên danh sách liên kết
4.1 Khởi tạo danh sách

Initialize: Khởi tạo một DSLK. Ban đầu DSLK chưa có phần tử.
void Initialize (node* &pFirst)
{
pFirst = NULL;
}

NewNode( ): cấp phát một nút cho DSLK. Hàm NewNode trả về địa chỉ của nút
vừa được cấp phát.
node* NewNode ( )
{
node *p;
p = new node;
return (p);
}
InsertFirst( ): thêm một nút có nội dung x vào đầu DSLK.
void InsertFirst (node* &pFirst, int x)
{

node *p;
p = new node;
p->info = x;
p->pNext = pFirst;
pFirst = p;
}
II. DANH SÁCH LIÊN KẾT ĐƠN
4. Các phép toán trên danh sách liên kết
4.2 Thêm vào đầu danh sách
NULL
pFirst
x
II. DANH SÁCH LIÊN KẾT ĐƠN
4. Các phép toán trên danh sách liên kết
4.2 Thêm vào đầu danh sách

p
x

p
x
p