4/25/2010
1
Chương 7.
Bài 1. Dynamic allocation,
Single linked list
ĐỖ BÁ LÂM
ViỆN CNTT&TT, TRƯỜNG ĐHBK HÀ NỘI
2
Nội dung
1. Cấp phát bộ nhớ động (Dynamic Allocation)
1.1. Khái niệm
1.2. Hàm malloc
1.3. Hàm free
2. Single linked list
2.1. Tổng quan
2.2. Các thao tác cơ bản
2.3. Bài tập
1.1. Khái niệm
Cấp phát động (dynamic) ? cố định (fix)
Ví dụ
Mảng có kích thước cố định, lưu trữ một số
lượng phần tử đã biết trước.
Kích thước mảng đã biết ở thời điểm dịch,
không thể thay đổi
Bạn có luôn luôn biết số phần tử thực sự mà
một mảng cần lưu?
=> Cấp phát động >< cấp phát cố định
3
4/25/2010
2
1.2. Hàm malloc
Cú pháp
void * malloc(unsigned int nbytes);
Cấp phát động nBytes trong bộ nhớ
Thành công: trả về con trỏ -trỏ tới vùng nhớ
được cấp phát.
Không thành công: NULL
Luôn kiểm tra xem việc cấp phát có thành công
hay không
Thư viện stdlib.h
4
1.2. Hàm malloc
Ép kiểu (chuyển kiểu) – casing
Hàm malloc
void * malloc(unsigned int nbytes);
Ép sang một kiểu khác bởi malloc trả về void*
Ví dụ
p = (int *) malloc (n*sizeof(int));
cấp phát một vùng nhớ chứa n số int
5
1.3. Hàm free
free()
void free(void *);
Giải phóng vùng nhớ được cấp phát
Ví dụ:
free(ptr);
Nếu ptr không trỏ tới vùng nhớ nào được cấp
phát bởi malloc sẽ gây lỗi run-time
Luôn giải phóng vùng nhớ nếu không sử dụng
nữa
6
4/25/2010
3
Ví dụ
Ví dụ 1. Nhập từ bàn phím một mảng các số
nguyên với số phần tử cũng được nhập từ bàn
phím. Hiển thị các phần tử trong mảng
Ví dụ 2. Xây dựng hàm với tham số hai xâu kí
tự. Hàm trả về một con trỏ trỏ tới xâu ghép từ
hai xâu trên.
7
Hướng dẫn
Ví dụ 1.
scanf(“%d”,&n);
p = (int *) malloc(sizeof(int) * n);
Ví dụ 2.
n1 = strlen (str1);
n2 = strlen (str2);
str = (char *) malloc(sizeof(char) * (n1+n2+1));
strcpy
8
2. Danh sách liên kết đơn
2.1. Tổng quan
2.1.1. Khái niệm
2.1.2. Thành phần của một nút
2.1.3. Con trỏ đầu - head
9
4/25/2010
4
2. Danh sách liên kết đơn
2.2. Các thao tác cơ bản
2.2.1. Khai báo danh sách
2.2.2. Cấp phát bộ nhớ cho một nút
2.2.3. Thêm một nút vào sau nút hiện tại
2.2.4. Loại bỏ nút đầu tiên trong danh sách
2.2.5. Duyệt danh sách
2.2.6. Giải phóng danh sách
10
1 nút
Là một cấu trúc dữ liệu xác định bao gồm một
tập tuần tự các “nút” (node) chứa dữ liệu
Trong mỗi nút có một liên kết đến nút kế tiếp
„A‟ „b‟ „C‟ „Z‟ X
...
2.1.1. Khái niệm
11
2.1.2. Thành phần của một nút
Mỗi nút gồm có:
Thành phần dữ liệu -data: Chứa dữ liệu của
nút (số nguyên, số thực, ký tự hay cấu trúc...)
Thành phần liên kết – next: Con trỏ trỏ đến
nút kế tiếp trong danh sách
„C‟
data:
Ký tự „C‟ Con trỏ
12
4/25/2010
5
2.1.2. Thành phần của một nút
Đặc biệt:
Đối với nút cuối cùng trong danh sách:
•next = NULL
„A‟ „b‟ „C‟ „Z‟ X
...
next = NULL
13
2.1.3. Con trỏ đầu - head
Để xác định một danh sách liên kết đơn ta dùng
một con trỏ trỏ đến nút đầu tiên trong danh sách –
Con trỏ đầu (head)
Khi danh sách rỗng: head = NULL
„A‟ „b‟ „C‟ „Z‟ X
...
head
14
B1. Định nghĩa cấu trúc một “nút”:
struct node {
dataType data; // dataType: int, char…
struct node *next;
};
B2. Khai báo con trỏ đầu:
struct node *head;
B3. Khởi tạo danh sách:
head = NULL;
2.2.1. Khai báo danh sách
15