1
3.1. Kiểu dữ liệu con trỏ
3.2. Danh sách liên kết (link list)
3.3. Danh sách liên kết ñơn
3.4. Sắp xếp danh sách
3.5. Các cấu trúc ñặc biệt của danh sách liên kết ñơn
3.5.1. Stack
3.5.2. Hàng ñợi (Queue)
3.6. Bài tập
1
Chương 3:
CẤU TRÚC DỮ LIỆU ðỘNG
Khoa KTCN Trường ðH KTKT B.Dương
© Dương Thành Phết-www.thayphet.net
2
3.1. Kiểu Dữ Liệu Con Trỏ
© Dương Thành Phết-www.thayphet.net
Khoa KTCN Trường ðH KTKT B.Dương
3.1.1. Biến không ñộng
3.1.2. Kiểu con trỏ
3.1.3. Biến ñộng
3
© Dương Thành Phết-www.thayphet.net
Khoa KTCN Trường ðH KTKT B.Dương
Dùng ñề lưu trữ những ñối tượng dữ liệu ñược sử
dụng không có nhu cầu thay ñổi và kích thước, số
lượng . . .
• ðược khai báo tường minh
• Tồn tại trong phạm vi khái báo
• Kích thước không thay ñổi trong suốt quá trình sống
Ví dụ:

p=&<tên biến>
-Truy xuất nội dung của ñối tượng do p trỏ ñến
*p
6
© Dương Thành Phết-www.thayphet.net
Khoa KTCN Trường ðH KTKT B.Dương
c. Ví dụ:
void main()
{
int a,b,*pa,*pb;
a=2;
b=3;
cout<<"\nGia tri cua bien a="<<a;
cout<<"\nGia tri cua bien b="<<b;
pa=&a;
pb=&b;
cout<<"\nDia chi cua o nho con tro pa tro toi="<<pa;
cout<<"\nDia chi cua o nho con tro pb tro toi="<<pb;
cout<<"\nNoi dung cua o nho con tro pa tro toi="<<*pa;
cout<<"\nNoi dung cua o nho con tro pb tro toi="<<*pb;
*pa=20; /* Thay doi giá tr cua *pa*/
*pb=20; /* Thay doi giá tri cua *pb*/
cout<<"\nGia tri moi cua bien a="<<a;
cout<<"\nGia tri moi cua bien b="<<b;
}
7
© Dương Thành Phết-www.thayphet.net
Khoa KTCN Trường ðH KTKT B.Dương
Trong trường hợp, tại thời ñiểm biên dịch không thể xác
ñịnh trước kích thước chính xác của ñối tượng dữ

new do p trỏ tới
10
© Dương Thành Phết-www.thayphet.net
Khoa KTCN Trường ðH KTKT B.Dương
Ví dụ:
//Trong C
int* p1, p2;
//Cấp phát vùng nhớ cho 1 biến ñộng kiểu int
p1 = (int*)malloc(sizeof(int));
//ðặt giá trị 5 cho biến ñộng p1
p1* = 5;
//Cấp phát biến ñộng kiểu mảng 10 p.tử kiểu int
p2 = (int*)calloc(10, sizeof(int));
//ðặt giá trị 0 cho phần tử thứ 4 của mảng p2
(p2+3)* = 0;
free(p1); free(p2);
//Trong C++
int* p;
p=new int;
delete p;
11
3.2. Danh Sách Liên Kết
© Dương Thành Phết-www.thayphet.net
Khoa KTCN Trường ðH KTKT B.Dương
3.2.1. Ðịnh nghĩa
3.2.2. Các hình thức tổ chức danh sách
12
© Dương Thành Phết-www.thayphet.net
Khoa KTCN Trường ðH KTKT B.Dương
3.2.1. Ðịnh nghĩa

Cách biểu diễn này cho phép truy xuất ngẫu nhiên,
ñơn giản và nhanh chóng ñến một phần tử bất kỳ
trong danh sách, nhưng lại hạn chế về mặt sử
dụng bộ nhớ bị lãng phí.
15
© Dương Thành Phết-www.thayphet.net
Khoa KTCN Trường ðH KTKT B.Dương
Mối liên hệ giữa các phần tử thể hiện tường minh:
 Mỗi phần tử ngoài các thông tin còn chứa một liên
kết (ñịa chỉ) ñến phần tử kế trong danh sách nên
còn ñược gọi là danh sách móc nối.
 Với hình thức này các phần tử trong danh sách
không cần phải lưu trữ kế cận trong bộ nhớ nên
khắc phục ñược các khuyết ñiểm của hình thức tổ
chức mảng, nhưng việc truy xuất ñến một phần tử
ñòi hỏi phải thực hiện truy xuất qua một số phần tử
khác.
16
© Dương Thành Phết-www.thayphet.net
Khoa KTCN Trường ðH KTKT B.Dương
Có các kiểu tổ chức liên kết giữa các phần tử.
 Danh sách liên kết ñơn
 Danh sách liên kết kép
 Danh sách liên kết vòng
17
3.3. Danh Sách Liên Kết ðơn
© Dương Thành Phết-www.thayphet.net
Khoa KTCN Trường ðH KTKT B.Dương
3.3.1. Tổ chức danh sách ñơn theo cách cấp phát liên kết
3.3.2. Các thao tác cơ bản trên danh sách ñơn

};
typedef struct SinvienNode SVNode;
20
© Dương Thành Phết-www.thayphet.net
Khoa KTCN Trường ðH KTKT B.Dương
Nếu biết ñược ñịa chỉ của phần tử ñầu tiên trong danh
sách ñơn thì có thể dựa vào thông tin pNext của nó ñể
truy xuất ñến phần tử thứ 2, thứ 3 ðể quản lý một
xâu ñơn chỉ cần biết ñịa chỉ phần tử ñầu xâu. Con trỏ
Head dùng ñể lưu trữ ñịa chỉ phần tử ñầu xâu
Khai báo:
NODE *pHead;
Ðể tiện lợi, có thể sử dụng thêm một con trỏ pTail giữ
ñịa chỉ phần tử cuối xâu.
Khai báo:
NODE *pTail;
21
© Dương Thành Phết-www.thayphet.net
Khoa KTCN Trường ðH KTKT B.Dương
3.3.2. Các thao tác cơ bản trên danh sách ñơn
22
© Dương Thành Phết-www.thayphet.net
Khoa KTCN Trường ðH KTKT B.Dương
Các ñịnh nghĩa, Khởi tạo danh sách LK ðơn:
struct tNode{
int key;
tNode *pnext;
};
typedef struct tNode *Node;
void Khoitao(List &L){

Thut toán :
Bắt ñầu:
Nếu Danh sách rỗng Thì
B11 : Head = new_elelment;
B12 : Tail = Head;
Ngược lại
B21 : new_ele ->pNext = Head;
B22 : Head = new_ele ;
void Themdau(List &L, Node *p){
if(L.pHead==NULL)
L.pHead=L.pTail=p;
else {
p->pNext=L.pHead;
L.pHead=p;
}
}
25
© Dương Thành Phết-www.thayphet.net
Khoa KTCN Trường ðH KTKT B.Dương
void Nhap(List &L)
{
int x;
Node *p;
Khoitao(L);
do
{
cout<<"Nhap gia tri vao danh sach (Nhap 0 ket thuc): ";
cin>>x;
if(x==0)
break;