›
›

Bài giảng Kỹ thuật lập trình - Chương 4, Phần 2: Một số cấu trúc dữ liệu và giải thuật căn bản - Lương Mạnh Bá

Download
Chương 4  
Một số cꢁu trꢂc dꢃ liꢀu và giải  
thuật căn bản  
1.Đꢀ qui  
2.Cꢁu trꢂc dꢃ liꢀu (5LT-3BT)  
01/05/2022  
Last Update 8-2010  
SE-SoICT  
KTLT4-2.1  
1. Các khái niꢀm cơ bản  
Cꢁu trꢂc dꢃ liꢀu  
• Cꢁu trꢂc dꢃ liꢀu là cách tổ chức và thao  
tác có hꢀ thống trên dꢃ liꢀu  
• Một cꢁu trꢂc dꢃ liꢀu :  
– Mô tả  
• Các dꢃ liꢀu cꢁu thành  
• Mối liên kết về mặt cꢁu trꢂc giꢃa các dꢃ liꢀu đó  
– Xác định các thao tác trên dꢃ liꢀu đó  
01/05/2022  
Last Update 8-2010  
SE-SoICT  
KTLT4-2.2  
1. Các khái niꢀm cơ bản  
Kiểu dꢃ liꢀu  
• Kiểu dꢃ liꢀu cơ bản  
• Kiểu dꢃ liꢀu có cꢁu  
trúc (structured data  
type)  
(primitive data type)  
– Đại diꢀn cho các dꢃ  
liꢀu giống nhau, không  
thể phân chia nhỏ hơn  
được nꢃa  
– Thường được các  
ngôn ngꢃ lập trình  
định nghĩa sẵn  
– Được xây dựng từ các  
kiểu dꢃ liꢀu (cơ bản,  
có cꢁu trꢂc) khác  
– Có thể được các ngôn  
ngꢃ lập trình định  
nghĩa sẵn hoặc do lập  
trình viên tự định  
nghĩa  
– Ví dụ:  
• C/C++: int, long,  
char, boolean, v.v.  
• Thao tác trên các số  
nguyên: + - * / ...  
01/05/2022  
Last Update 8-2010  
SE-SoICT  
KTLT4-2.3  
1. Các khái niꢀm cơ bản  
Dꢃ liꢀu, kiểu dꢃ liꢀu, cꢁu trꢂc dꢃ liꢀu  
0100110001101001010001  
Machine Level Data Storage  
3.1415  
'A'  
28  
Primitive Data Types  
Basic Data Structures  
array  
stack  
queue  
list  
High-Level Data Structures  
hash table  
tree  
01/05/2022  
Last Update 8-2010  
SE-SoICT  
KTLT4-2.4  
II. Cꢁu trꢂc dꢃ liꢀu  
• Mảng ( tự đꢄc )  
• Danh sách  
• Cây  
• Bảng băm  
01/05/2022  
Last Update 8-2010  
SE-SoICT  
KTLT4-2.5  
1. Danh sách (list)  
• Danh sá ch :  
– Tập hợp các phần tử cùng kiểu  
– Số lượng các phần tử của danh sách không cố định  
• Phân loại:  
– Danh sách tuyến tính:  
• Có phần tử đầu tiên, phần tử cuối cùng  
• Thứ tự trước / sau của các phần tử được xác định rõ ràng  
– Danh sách không tuyến tính: các phần tử trong danh sách không được sắp  
thứ tự  
• Có nhiều hình thức lưu trꢃ danh sách  
– Sử dụng vùng các ô nhớ liên tiếp trong bộ nhớ → danh sách kế tiếp  
– Sử dụng vùng các ô nhớ không liên tiếp trong bộ nhớ → danh sách móc nối  
• Danh sách nối đơn  
• Danh sách nối kép  
…………………  
01/05/2022  
Last Update 8-2010  
SE-SoICT  
KTLT4-2.6  
1. Danh sá ch  
• Thao tác trên danh sách tuyến tính  
– Khởi tạo danh sách (create)  
– Kiểm tra danh sá ch rỗng (isEmpty)  
– Kiểm tra danh sá ch đầy (isFull)  
– Tính kích thước (sizeOf)  
– Xóa rỗng danh sách (clear)  
– Thêm một phần tử vào danh sách tại một ví trí cụ thể (insert)  
– Loại bỏ một phần tử tại một vị trí cụ thể khỏi danh sách (remove)  
– Lꢁy một phần tử tại một vị trí cụ thể (retrieve)  
– Thay thế giá trị của một phần tử tại một vị trí cụ thể (replace)  
– Duyꢀt danh sách và thực hiꢀn một thao tác tại các vị trí trong danh  
sá ch (traverse)  
– ......................................  
01/05/2022  
Last Update 8-2010  
SE-SoICT  
KTLT4-2.7  
1.1. Danh sách kế tiếp  
• Sử dụng một vector lưu trꢃ gồm một số  
các ô nhớ liên tiếp để lưu trꢃ một danh  
sách tuyến tính  
– Các phần tử liền kề nhau được lưu trꢃ trong  
nhꢃng ô nhớ liền kề nhau  
– Mỗi phần tử của danh sách cũng được gán  
một chỉ số chỉ thứ tự được lưu trꢃ trong  
vector  
– Tham chiếu đến các phần tử sử dụng địa chỉ  
được tính giống như lưu trꢃ mảng.  
0
1
2
i
last  
n-1  
01/0
T4-2.8  
Last
1.1. Danh sách kế tiếp  
• Ưu điểm của cách lưu trꢃ kế tiếp  
– Tốc độ truy cập vào các phần tử của danh sách  
nhanh  
• Nhược điểm của cách lưu trꢃ kế tiếp  
– Cần phải biết trước kích thước tối đa của danh sách  
• Tại sao?  
– Thực hiꢀn các phép toán bổ sung các phần tử mới và  
loại bỏ các phần tử cũ khá tốn kém  
• Tại sao?  
01/05/2022  
Last Update 8-2010  
SE-SoICT  
KTLT4-2.9  
1.1.a. Thêm một phần tử vào một danh  
sách kế tiếp  
• 2 trường hợp  
– insert(index, element): thêm một phần tử element vào một vị trí cụ thể index  
– insert(list, element): thêm một phần tử element vào vị trí bꢁt kỳ trong danh sách  
list  
• Điều kiꢀn tiên quyết:  
– Danh sách phải được khởi tạo rồi  
– Danh sách chưa đầy  
– Phần tử thêm vào chưa có trong danh sách  
• Điều kiꢀn hậu nghiꢀm:  
– Phần tử cần thêm vào có trong danh sách  
insert(3, ‘z’)  
0 1 2 3 4 5 6 7 8 9  
z
a b c e g
01/05/2022  
Last Update 8-2010  
SE-SoICT  
KTLT4-2.10  
ccoouunntt==98  
1.1.a. Thêm một phần tử vào một danh  
sách kế tiếp  
Algorithm Insert  
Input: index là vị trí cần thêm vào, element là giá trị cần thêm vào  
Output: tình trạng danh sách  
if list đầy  
return overflow  
if index nằm ngoài khoảng [0..count]  
return range_error  
//Dời tất cả các phần tử từ index về sau 1 vị trí  
for i = count-1 down to index  
entry[i+1] = entry[i]  
entry[index] = element  
count++  
return success;  
// Gán element vào vị trí index  
// Tăng số phần tử lên 1  
End Insert  
01/05/2022  
SE-SoICT  
KTLT4-2.11  
Last Update 8-2010  
1.1.b.Xóa 1 phần tử khỏi danh sách kế  
tiếp  
remove(3, ‘d’)  
0 1 2 3 4 5 6 7 8 9  
a b c d e f g h  
h
count=7  
8
01/05/2022  
Last Update 8-2010  
SE-SoICT  
KTLT4-2.12  
1.1.b.Xóa 1 phần tử khỏi danh sách kế tiếp  
Algorithm Remove  
Input: index là vị trí cần xóa bỏ, element là giá trị lꢁy ra được  
Output: danh sách đã xóa bỏ phần tử tại index  
if list rỗng  
return underflow  
if index nằm ngoài khoảng [0..count-1]  
return range_error  
element = entry[index]  
count--  
//Lấy element tại vị trí index ra  
//Giảm số phần tử đi 1  
//Dời tất cả các phần tử từ index về trước 1 vị trí  
for i = index to count-1  
entry[i] = entry[i+1]  
return success;  
End Remove  
01/05/2022  
SE-SoICT  
KTLT4-2.13  
Last Update 8-2010  
1.1.c.Duyꢀt danh sách kế tiếp  
Algorithm Traverse  
Input: hàm visit dùng để tác động vào từng phần tử  
Output: danh sách được cập nhật bằng hàm visit  
//Quét qua tất cả các phần tử trong list  
for index = 0 to count-1  
Thi hành hàm visit để duyꢀt phần tử entry[index]  
End Traverse  
01/05/2022  
Last Update 8-2010  
SE-SoICT  
KTLT4-2.14  
1.2. Danh sách nối đơn  
• Một phần tử trong  
danh sách = một  
nút  
INFO  
N
E
X
T
L
• Quy cách của một  
nút  
– INFO: chứa thông tin  
(nội dung, giá trị)  
ứng với phần tử  
– NEXT: chứa địa chỉ  
của nꢂt tiếp theo  
• Để thao tác được  
trên danh sách, cần  
nắm được địa chỉ  
của nꢂt đầu tiên  
trong danh sá ch,  
tức là biết được  
con trỏ L trỏ tới đầu  
01/05/2022  
danh sá ch  
Last Update 8-2010  
Tổ chức danh sách móc nối  
• Nút = dữ liệu + móc nối{  
• Định nghĩa:  
typedef struct node {  
typed data;  
struct node *next; } Node;  
• Tạo nút mới:  
Node *p = malloc(sizeof(Node));{  
• Giải phóng nút:  
free(p);  
01/05/2022  
Last Update 8-2010  
SE-SoICT  
KTLT4-2.16  
Khởi tạo và truy cập danh sách  
móc nối  
• Khai báo một con trỏ  
Node *Head;  
Head là con trỏ trỏ đến nꢂt đầu của danh sách.Khi danh  
sách rỗng thì Head =NULL.  
• Tham chiếu đến các thành phần của một nꢂt trỏ bởi p  
– INFO(p)  
– NEXT(p)  
• Một số thao tác với danh sách nối đơn  
– 1.Thêm một nꢂt mới tại vị trí cụ thể  
– 2.Tìm nꢂt có giá trị cho trước  
– 3.Xóa một nꢂt có giá trị cho trước  
– 4.Ghép 2 danh sách nối đơn  
– 5.Hủy danh sách nối đơn  
01/05/2022  
SE-SoICT  
KTLT4-2.17  
Last Update 8-2010  
Truyền danh sách móc nối vào hàm  
• { Khi truyền danh sách móc nối vào  
hàm, chỉ cần truyền Head.  
• { Sử dụng Head để truy cập toàn bộ  
danh sá ch  
– { Note: nếu hàm thay đổi vị trí nꢂt đầu của  
danh sách (thêm hoặc xóa nꢂt đầu) thì Head  
sẽ không còn trỏ đến đầu danh sách  
– { Do đó nên truyền Head theo tham biến  
(hoặc trả lại một con trỏ mới)  
01/05/2022  
Last Update 8-2010  
SE-SoICT  
KTLT4-2.18  
Thêm một nꢂt mới  
• Các trường hợp của thêm nꢂt  
1.Thêm vào danh sách rỗng  
2.Thêm vào đầu danh sách  
3.Thêm vào cuối danh sách  
4.Thêm vào giꢃa danh sách  
• { Thực tế chỉ cần xét 2 trường hợp  
– Thêm vào đầu danh sách(TH1 vàTH2)  
– Thêm vào giꢃa hoặc cuối danh sách(TH3 và  
TH4 )  
01/05/2022  
Last Update 8-2010  
SE-SoICT  
KTLT4-2.19  
Thêm vào danh sách rỗng  
• Head = NULL  
Node *newNode;  
newNode=  
malloc(sizeof(Node));  
newNode->data = 20;  
newNode->next = NULL;  
Head = newNode;  
01/05/2022  
Last Update 8-2010  
SE-SoICT  
KTLT4-2.20  
Tải về để xem bản đầy đủ
ppt 123 trang Thùy Anh 13120 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Kỹ thuật lập trình - Chương 4, Phần 2: Một số cấu trúc dữ liệu và giải thuật căn bản - Lương Mạnh Bá", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pptbai_giang_ky_thuat_lap_trinh_chuong_4_phan_2_mot_so_cau_truc.ppt