Đ
Đạ
ại H
i Họ
ọc Sư Ph
c Sư Phạ
ạm Tp. H
m Tp. Hồ
ồCh
Chí
íMinh
Minh
Chương 4: DANH SÁCH LIÊN KẾT
C
CẤ
ẤU TR
U TRÚ
ÚC D
C DỮ
ỮLI
LIỆ
ỆU 1
U 1
2
Nội dung
1. Đặt vấn đề - ctdl động, tại sao?
2. Con trỏ và kiểu dữ liệu động
3. Cấu trúc và con trỏ
4. Định nghĩa danh sách liên kết
5. Các phép toán trên danh sách liên kết
6. Sắp thứ tự trên danh sách liên kết
7. Danh sách liên kết kiểu FIFO và LIFO
8. Một số ứng dụng của danh sách liên kết
3
1. Đặt vấn đề - ctdl động, tại sao?
•Nhu cầu thực tế về kiểu dữ liệu:
struct NGUOI
{char hoten[30];
int soCMND;
NGUOI cha,me;
};
Khi khai báo một kiểu dữ liệu thì NNLT thường yêu cầu kiểu dữ liệu
phải được xác định kích thước rõ ràng. Với nhu cầu trên
không
thể tính kích thước rõ ràng cho kiểu dữ liệu người.
CTDL động giải quyết
được vấn đề này. Nó giải
quyết như thế nào?
4
1. Đặt vấn đề - ctdl động, tại sao?
Biến tĩnh trong NNLT
•Vùng nhớ của kiểu dữ liệu
tĩnh sẽ được sinh ra khi ta
khai báo biến và mất đi
khi ra khỏi phạm vi khai
báo hoặc khi chương trình
kết thúc đối với các biến
toàn cục.
•Biến tĩnh trong chương
trình không thay đổi được
cấu trúc hay độ lớn trong
khi thực thi.
Nhu cầu thực tế
•Có nhiều biến tĩnh không
cần sử dụng nữa nhưng
nó vẫn tồn tại và chiếm
bộ nhớ cho đến khi
chương trình hủy nó đi
theo đúng cơ chế của biến
tỉnh
gây lãng phí bộ
nhớ.
•Trong chu kỳ sống của
một số đối tượng dữ liệu
có thể thay đổi về cấu
trúc, độ lớn như: danh
sách học viên có thể tăng
lên hoặc giảm xuống
bất hợp lý.
Vấn đề về hiệu quả sử dụng bộ nhớ
CTDL động giải quyết
được vấn đề này. Nó
giải quyết như thế
nào?
5
1. Đặt vấn đề - ctdl động, tại sao?
•Tổng kích thước vùng nhớ dành cho tất
cả các biến tĩnh chỉ là 64kb (1 segment
bộ nhớ)
•Nhu cầu thực tế: cần nhiều bộ nhớ hơn
CTDL động giải quyết
được vấn đề này. Nó
giải quyết như thế nào?
Hạn chế về kích thước bộ nhớ cho các biến tĩnh
6
2. Con trỏ và kiểu dữ liệu động
•Biến không động
•Kiểu con trỏ
•Biến động
7
2. Con trỏ và kiểu dữ liệu động
8
2. Con trỏ và kiểu dữ liệu động
a. Biến không động
Được khai báo tường minh.Tồn tại trong phạm vi
khai báo.
Đượccấpphátbộnhớtrongvùngdữliệuhoặctrong
ngăn xếp.
Kích thước không đổi trong suốt quá trình sống
Biến sẽ có một định danh gắn với vùng nhớ đã được
cấp phát, và được truy xuất trực tiếp thông qua định
danh đó.
Ví dụ:
int x;
char a[100];
9
b. Kiểu con trỏ
Biến con trỏ là biến dùng để lưu địa chỉ của một đối
tượng dữ liệu khác.
Cho trước kiểu T=<V,O>. Kiểu con trỏ Tp chỉ đến
các phần tử có kiểu Tđược định nghĩa:
Tp=<Vp,Op>
Vp = {{Các địa chỉ có thể lưu trữ đối tượng kiểu T},
NULL}
Op= {Các thao tác tác động lên biến con trỏ kiểu T}
10
Ví dụ:
int *n;
int *a = new int[4];
int data[4];
char *b;
char c[10];
student *st;
hay
typedef student *pStudent;
pStudent st;
11
Các thao tác cơ bản trên kiểu con trỏ
Khi biến con trỏ p lưu địa chỉ của biến x, ta nói “p
trỏ đến x”
int *p;
int x=5;
p=&x;
cout<<*p; //cout<<x;
Truy xuất nội dung của một đối tượng do p trỏ
đến.
int *a = new int;
*a = 5;
cout<<*a;
12
Gán địa chỉ của một vùng nhớ vào con trỏ p.
p = <địa chỉ>;
p = <địa chỉ> + <giá trị nguyên>
ví dụ:
int a[3] = {1,2,3}
int *p,*q;
p = &a[0]; //int *p = a;
q = a + 1;
*q = 5;
cout<<*q;
13
c. Biến động
Biến không được khai báo tường minh
Có thể được cấp phát và giải phóng do người dùng yêu cầu.
Biến động không hoạt động theo nguyên tắc phạm vi
Vùng nhớ của biến được cấp phát trong Heap
Kích thước của vùng nhớ có thể thay đổi trong quá trình sống.
Do không có định danh khi khai báo nên ta sẽ dùng con trỏ để
trỏ đến vùng nhớ được cấp phát.
Hai thao tác cơ bản của biến động là tạo và hủy một biến động
do con trỏ p trỏ đến.
14
Thao tác tạo và hủy biến động
Cấp phát bộ nhớ:
void* malloc(size) trả về con trỏ chỉ đến vùng nhớ với
kích thước được cấp phát là size
void* calloc(n,size) trả về con trỏ chỉ đến vùng nhớ
được cấp phát gồm n phần tử, mỗi phần tử kích thước
là size
Dùng toán tử new
Hủy biến động:
free(p); dùng để hủy vùng nhớ được cấp phát bởi
malloc hoặc calloc do p trỏ tới.
delete p; dùng để hủy vùng nhớ được cấp phát bởi
hàm new mà con trỏ p trỏ tới.
15
Ví dụ
int* p1, p2;
p1 = (int*)malloc(sizeof(int));
*p1 = 5;
p2 = (int*)calloc(10,sizeof(int));
*(p2+3)=5;
free(p1);
free(p2);
int *p3 = new int[4];
*p3 = 1; //p3[0]=1;
p3[2]=5;
delete p3;
16
2. Con trỏ và kiểu dữ liệu động
17
2. Con trỏ và kiểu dữ liệu động
18
2. Con trỏ và kiểu dữ liệu động
19
2. Con trỏ và kiểu dữ liệu động
int x;
int *p, *q;
p=&x;
q=&x;
20
2. Con trỏ và kiểu dữ liệu động