Xem mẫu
- 11/07/2020
Khoa Công Nghệ Thông Tin
Chương 1
DANH SÁCH
1
Mở đầu
Kiến thức cần thiết khi tìm hiểu về chương 1,
một số CTDL cơ bản:
- CTDL là gì? Giải thuật là gì? Kiểu dữ liệu cơ
bản, dữ liệu lưu trữ trong máy tính; Kiểu dữ
liệu trong ngôn ngữ C++;
- Các kiến thức về cơ sở lập trình & kỹ thuật
lập trình.
Kỹ năng cần có:
- Có thể sử dụng Visual Studio 2010
- Có thể lập trình C++
2
1
- 11/07/2020
Mục tiêu dạy học
Cung cấp kiến thức về các CTDL và các thuật
toán trên danh sách đặc, danh sách liên kết,
và danh sách hạn chế (stack, queue).
Rèn luyện và nâng cao các kỹ năng lập trình, áp
dụng các CTDL và các thuật toán trên danh sách
đặc và danh sách liên kết, danh sách hạn chế,
giải quyết các bài toán ứng dụng
Có khả năng sử dụng cấu trúc dữ liệu danh sách
phù hợp, giải quyết các bài toán ứng dụng.
3
Nội dung chính
1.1 Danh sách đặc
1.2 Danh sách liên kết
Danh sách liên kết đơn
Danh sách liên kết kép
1.3 Danh sách hạn chế
Ngăn xếp
Hàng đợi
1.4 Tổng kết chương 1
1.5 Bài tập chương 1
Tài liệu tham khảo
4
2
- 11/07/2020
1.1
DANH SÁCH ĐẶC
(LIST)
5
1.1 – DANH SÁCH ĐẶC
Danh sách đặc là một danh sách mà các
phần tử trong danh sách có cùng kiểu dữ
liệu, và được cấp phát liên tục trong bộ
nhớ.
6
3
- 11/07/2020
1.1 – DANH SÁCH ĐẶC
# define MAX 100
int a[MAX];
int n; // n là tổng số phần tử hiện có trong danh sách, 0
- 11/07/2020
1.1 – DANH SÁCH ĐẶC
Nhập danh sách từ bàn phím
Xuất danh sách (ra ngoài màn hình)
Tìm một phần tử trong danh sách
Chèn/ thêm một phần tử mới vào danh
sách tại vị trí i
Xóa một phần tử tại vị trí i trong danh sách
9
1.1 – DANH SÁCH ĐẶC
void input (int a[], int n)
{
for (int i=0; i
- 11/07/2020
1.1 – DANH SÁCH ĐẶC
void output (int a[], int n)
{
for (int i=0; i
- 11/07/2020
1.1 – DANH SÁCH ĐẶC
a[0] a[1] a[2] a[3] a[4] a[5] a[6]
10 50 20 70 30 60 40
13
1.1 – DANH SÁCH ĐẶC
int search (int a[], int n, int x) .
{ .
.
int i = 0;
Hiện lưu trữ n = 7 phần tử
while ( (i
- 11/07/2020
1.1 – DANH SÁCH ĐẶC
Bước 1: i = 0
99
Xét điều kiện while (i < n && a[i] != x) .
i = 0, n = 7: .
.
Hiện lưu trữ n = 7 phần tử
i
- 11/07/2020
1.1 – DANH SÁCH ĐẶC
Bước 3: i = 2
99
Xét điều kiện while (i < n && a[i] != x) .
i = 2, n = 7: .
.
Hiện lưu trữ n = 7 phần tử
i
- 11/07/2020
1.1 – DANH SÁCH ĐẶC
Bước 5: i = 4
99
Xét điều kiện while (i < n && a[i] != x) .
i = 4, n = 7: .
.
Hiện lưu trữ n = 7 phần tử
i
- 11/07/2020
1.1 – DANH SÁCH ĐẶC
.
.
.
Hiện lưu trữ n = 7 phần tử
6 a[6]
5 a[5]
4 a[4]
3 a[3]
2 a[2]
1 a[1]
5 0 a[0]
i=
21
1.1 – DANH SÁCH ĐẶC
Trong danh sách đặc, quá trình chèn/ thêm một phần tử tại vị trí
i (i đi từ 0 đến n-1) trong danh sách đặc tương đối phức tạp và
tốn nhiều thời gian.
Ý tưởng để chèn một giá trị x vào vị trí i ta làm như sau:
Bước 1: Dời các đoạn phần tử từ i đến n-1 ra phía sau một vị trí.
Chuyển giá trị a[n – 1] qua a[n]; (a[n] = a[n-1])
Chuyên giá trị a[n – 2] qua a[n – 1]; (a[n-1] = a[n-2])
….
Chuyển giá trị a[i-1] qua a[i]; (a[i] = a[i-1]) ;
Bước 2: Chèn giá trị x vào vị trí i, a[i] = x;
Bước 3: Tăng n lên 1 giá trị;
22
11
- 11/07/2020
1.1 – DANH SÁCH ĐẶC
99
.
.
.
Bước 1: Dời đoạn các phần tử sau vị trí i lên phía
trước một vị trí (nhỏ dời trước). 6 a[6]
chuyển giá trị a[i + 1] qua a[i]; 5 a[5]
4 a[4]
(a[3] = a[4] a[3] = 30);
3 a[3] n = 7
chuyển giá trị a[i + 2] qua a[i+1];
2 a[2] n = 6
(a[4] = a[5] a[4] = 60); 1 a[1]
chuyển giá trị a[n - 1] qua a[n-2]; 0 a[0]
(a[5] = a[6] a[5] = 40);
Bước 2: Giảm n một giá trị;
23
1.1 – DANH SÁCH ĐẶC
Bước 1: Dời đoạn các phần tử sau vị trí i lên
// Code dời giá trị phần tử
phía trước một vị trí (nhỏ dời trước).
từ n-1 đến i
chuyển giá trị a[i + 1] qua a[i]; (a[3] = for (int j=i; j
- 11/07/2020
1.1 – DANH SÁCH ĐẶC
// i là vị trí cần xóa
int Delete(int a[], int &n, int i)
{
if (i>=0 && i < n)
{
for (int j=i; j
- 11/07/2020
1.2 – DANH SÁCH LIÊN KẾT
DANH SÁCH LIÊN KẾT ĐƠN
Danh sách liên kết đơn là một danh sách mà các
phần tử được cấp phát rời rạc nhau, và cố định
trong bộ nhớ. Mỗi Phần tử trong danh sách gồm có
2 thành phần:
▪ Phần 1: vùng thông tin chưa giá trị cần quả lý
▪ Phần 2: vùng liên kết, chứa địa chỉ bộ nhớ của
phần tử kế tiếp
27
1.2 – DANH SÁCH LIÊN KẾT
DANH SÁCH LIÊN KẾT ĐƠN
First = 2
MINH HỌA
2 Tâm 3
0 Hoa 1
1 Lan NULL Đào 0
3
2 Tâm 3
3 Đào 0 0 Hoa 1
First = 2
1 Lan NULL
28
14
- 11/07/2020
1.2 – DANH SÁCH LIÊN KẾT
DANH SÁCH LIÊN KẾT ĐƠN
Cấu trúc của một phần tử trong danh sách liên kết
gồm 2 vùng (phần):
▪ info (chứa thông tin của phần tử)
▪ link (chứa địa chỉ vùng nhớ của phần tử tiếp
theo)
// cấu trúc 1 node // khai báo danh sách,
first sẽ chứa giá trị là
struct Node địa chỉ ô nhớ của phần
{ tử đầu tiên trong Danh
int info; sách
info link Node * first;
Node *link;
};
29
1.2 – DANH SÁCH LIÊN KẾT
DANH SÁCH LIÊN KẾT ĐƠN
Khởi tạo danh sách (tạo danh sách rỗng).
Duyệt danh sách liên kết (xuất giá trị từng phần tử
trong danh sách liên kết ra màn hình).
Tìm kiếm một phần tử trong danh sách.
Thêm một phần tử vào danh sách: thêm đầu, thêm
cuối, thêm sau một node q.
Xóa một phần tử ra khỏi danh sách: xóa đầu, xóa
cuối, và xóa sau một node q.
30
15
- 11/07/2020
1.2 – DANH SÁCH LIÊN KẾT
DANH SÁCH LIÊN KẾT ĐƠN
Danh sách rỗng là danh sách không có phần tử nào. Do
đó phần tử đầu tiên cũng không tồn tại, nên ta có thể
gán giá trị NULL cho biến first (con trỏ first);
void init()
{
first = NULL;
}
// Chú y: con trỏ first được khai báo toàn cục trong chương trình
31
1.2 – DANH SÁCH LIÊN KẾT
DANH SÁCH LIÊN KẾT ĐƠN
Duyệt danh sách là việc ta truy xuất được giá trị/thông
tin của từng phần tử trong danh sách liên kết (bắt đầu
từ first) void Process_list()
{
Node *p;
p = first;
while (p!=NULL)
{
cout
- 11/07/2020
1.2 – DANH SÁCH LIÊN KẾT
DANH SÁCH LIÊN KẾT ĐƠN
10 20 15 5
first NULL
Node * Search (int x)
{
Node *p= first;
while ( (p!=NULL) && (p->info != x) )
p=p->link;
return p;
}
// hàm trả về NULL nếu không tìm thấy, trả về địa chỉ của node p nếu tìm thấy.
33
1.2 – DANH SÁCH LIÊN KẾT
DANH SÁCH LIÊN KẾT ĐƠN
Thêm vào đầu danh sách
Thêm vào cuối danh sách
Thêm sau node q.
34
17
- 11/07/2020
1.2 – DANH SÁCH LIÊN KẾT
DANH SÁCH LIÊN KẾT ĐƠN
first
10 20 15 5
NULL
X = 30 30
p
Bước 1: cấp phát phần tử mới p (có địa chỉ được
quản lý bởi biến p) Node *p = new Node;
Bước 2: Gán giá trị X (X=30) cho vùng info của p
p->info = x;
Bước 3: Gán giá trị địa chỉ bộ nhớ của first cho
vùng link của p (p->link = first); p->link = first;
Bước 4: Gán giá trị địa chỉ của p cho biến first. first = p;
35
1.2 – DANH SÁCH LIÊN KẾT
DANH SÁCH LIÊN KẾT ĐƠN
void Insert_first(int x) Node *p = new Node;
{
Node *p;
p->info = x;
p = new Node;
p->info = x;
p->link = first; p->link = first;
first = p;
} first = p;
36
18
- 11/07/2020
1.2 – DANH SÁCH LIÊN KẾT
DANH SÁCH LIÊN KẾT ĐƠN
10 20 15 5
first NULL
q p
X = 30 30
Bước 1: cấp phát phần tử mới (có địa chỉ được Node *p = new Node;
quản lý bởi biến p)
Bước 2: Gán giá trị x cho info của p và gán giá p->info = x;
trị NULL cho vùng link của p p->link = NULL;
Bước 3: Tìm phần tử cuối danh sách (nếu có), Node *q = first;
và gán địa chỉ bộ nhớ của phần tử cuối cùng cho while (q -> link!= NULL)
biến q q = q->link;
Bước 4: Gán địa chỉ bộ nhớ của p cho vùng link q->link = p;
của q
37
1.2 – DANH SÁCH LIÊN KẾT
DANH SÁCH LIÊN KẾT ĐƠN
void Insert_last(int x)
{
Node *p; Node *p = new Node;
p = new Node;
p->info = x;
p->link = NULL;
if (first == NULL) //không có phần tử cuối cùng
p->info = x;
first = p; p->link = NULL;
else
{
Node *q = first;
Node *q = first;
while (q-> link!= NULL) while (q -> link!= NULL)
q = q->link; q = q->link;
q->link = p;
}
} q->link = p;
38
19
- 11/07/2020
1.2 – DANH SÁCH LIÊN KẾT
DANH SÁCH LIÊN KẾT ĐƠN
Xóa đầu
Xóa cuối
Xóa sau node q.
39
1.2 – DANH SÁCH LIÊN KẾT
DANH SÁCH LIÊN KẾT ĐƠN
10 20 15 5
first NULL
p
Bước 1:Gán giá trị bộ nhớ của phần tử đầu Node *p = first;
danh sách cho biến p;
Bước 2 : Gán địa chỉ bộ nhớ của phần tử thứ
first = first->link;
2 trong danh sách cho biến first (first = frist-
>link)
Bước 3 : Thu hồi vùng nhớ phần tử đầu
delete p;
danh sách (delete p);
40
20
nguon tai.lieu . vn
