Tham khảo bài thuyết trình 'bài giảng cấu trúc dữ liệu - chương 2 cấu trúc dữ liệu danh sách phần 2', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng cấu trúc dữ liệu - Chương 2 Cấu trúc dữ liệu danh sách Phần 2
- KHOA KHOA HỌC MÁY TÍNH – BỘ MÔN LẬP TRÌNH
BÀI GIẢNG
CẤU TRÚC DỮ LIỆU
(BẬC CAO ĐẲNG)
Chương2: CẤU TRÚC DỮ LIỆU DANH SÁCH
Nguyễn Thanh Cẩm
- NỘI DUNG TRÌNH BÀY
1. Danh sách
2. Danh sách đặc
3. Danh sách liên kết
4. Ngăn xếp
5. Hàng đợi
1
- 1. Danh sách
a. Định nghĩa
b. Các phép toán trên danh sách
- 1. Danh sách
a. Định nghĩa
Danh sách là tập hợp hữu hạn các phần tử
cùng kiểu (Elementtype) : a1, a2, …, an (n>=1)
với tính chất: nếu biết được ai sẽ biết ai+1
(0
- 1. Danh sách
b. Các phép toán trên danh sách
Phép duyệt danh sách: là phép thăm tất cả các
phần tử của danh sách thỏa mãn
nào đó để thực hiện công việc
Ví dụ:
Phép tìm kiếm: là thao tác tìm phần tử trong
danh sách thỏa mãn điều kiện nào đó
Ví dụ:
- 1. Danh sách
b. Các phép toán trên danh sách
Thêm phần tử vào danh sách: là thao tác thêm
phần tử mới Vào danh sách. Phần tử có thể được
thêm vào cuối, đầu hoặc giữa danh sách.
Chú ý danh sách đầy
Ví dụ:
- 1. Danh sách
b. Các phép toán trên danh sách
Loại bỏ phần tử khỏi danh sách: là thao tác
loại bỏ phần tử khỏi danh sách. Trước khi loại bỏ
phải xác định phần tử cần loại bỏ (tìm kiếm).
Chú ý: sau khi loại bỏ, số phần tử của danh sách
giảm đi 1 đơn vị
Ví dụ:
- 1. Danh sách
b. Các phép toán trên danh sách
Sửa đổi phần tử trong danh sách: là thao tác
hiệu chỉnh phần tử trong danh sách. Trước khi
hiệu chỉnh cần phải xác định phần tử cần hiệu
chỉnh (tìm kiếm)
Ví dụ:
Sắp xếp thứ tự danh sách: là thao tác sắp lại
thứ tự các phần tử trong danh sách theo một quy
tắc nào đó
Ví dụ:
- 1. Danh sách
b. Các phép toán trên danh sách
Tách một danh sách thành nhiều danh sách: là
thao tác tách một phần hoặc tất cả các phần tử
trong DS đưa sang các danh sách khác
Vd:
Ghép nhiều danh sách thành danh sách mới:
là thao tác ngược lại của quá trình tách.
Trộn nhiều danh sách thành danh sách mới
- 2. Danh sách đặc
a. Định nghĩa
b. Khai báo
c. Các phép toán
d. Đặc điểm của danh sách đặc
- 2. Danh sách đặc
a. Định nghĩa
Danh sách đặc là danh sách mà các phần tử được
sắp xếp kế tiếp nhau trong bộ nhớ, phần tử ai+1 đứng
sau phần tử ai.
a0 a1 … ai ai+1 … an-2 an-1
add[1] add[i] ←d → add[n]
add[i] = add[1] + (i-1)*d
- 2. Danh sách đặc
b. Khai báo
#define MaxLength ... //Số nguyên thích hợp để chỉ độ dài của danh
sách
typedef ... ElementType; //kiểu của phần tử trong danh sách
typedef int Position; //kiểu vị trí cuả các phần tử
typedef struct {
ElementType Elements[MaxLength]; //mảng chứa các phần tử của DS
Position Last; //giữ độ dài danh sách
} List;
Vd:
- 2. Danh sách đặc
c. Các phép toán
i. Khởi tạo danh sách rỗng
ii. Kiểm tra danh sách rỗng
iii. Tìm kiếm phần tử trong danh sách
iv. Chèn phần tử vào danh sách
v. Loại bỏ phần tử khỏi danh sách
- 2. Danh sách đặc
c. Các phép toán
i. Khởi tạo danh sách rỗng
void Make_List(List *L)
{
L->Last = 0;
}
Trong đó Last chỉ vị trí của phần tử cuối cùng
trong danh sách và đó cũng là độ dài hiện tại của
danh sách
- 2. Danh sách đặc
c. Các phép toán
ii. Kiểm tra danh sách rỗng
Danh sách rỗng là một danh sách mà độ dài của
nó bằng 0.
int Empty_List(List L)
{
return L.Last == 0;
}
- 2. Danh sách đặc
c. Các phép toán
iii. Chèn phần tử vào danh sách
Giả sử ta chèn phần tử có nội dung x vào danh
sách ở vị trí p. Khi đó các phần tử từ vị trí thứ p đến
vị trí thứ last được di chuyển ra sau 1 đơn vị và độ
dài danh sách tăng lên 1 đơn vị.
- 2. Danh sách đặc
c. Các phép toán
Giải thuật Chèn phần tử vào danh sách
void Insert_List(ElementType X, Position P, List *L){
if (L->Last==MaxLength) printf("Danh sach day");
else
if ((PL->Last)) printf("Vi tri khong hop le");
else{ Position i;
for(i=L.Last; i>=p; i--) L->element[i+1]= L->element[i];
L->Elements[p]=X;
L->Last++;
}
}
- 2. Danh sách đặc
c. Các phép toán
iv. Loại bỏ phần tử khỏi danh sách
Để loại bỏ phần tử vị trí p ra khỏi danh sách L ta dời
các phần tử từ vị trí p+1 đến cuối danh sách sang trái
1 vị trí.
Lưu ý: độ dài của danh sách giảm đi 1 đơn vị
- 2. Danh sách đặc
c. Các phép toán
iv. Loại bỏ phần tử khỏi danh sách
Giải thuật loại bỏ
void Delete_List(Position P,List *L){
if ((PL->Last)) printf("Vi tri khong hop le");
else if (Empty_List(*L)) printf("Danh sach rong!");
else{ Position i;
for(i=P;iLast;i++)
L->Elements[i] = L->Elements[i+1];
L->Last--;
}
}
- 2. Danh sách đặc
c. Các phép toán
v. Tìm kiếm phần tử trong danh sách
Trường hợp danh sách không thứ tự
Position Search_List(ElementType X,List L){
Position found=0, i=0;
if (Empty_List(L)) printf("Danh sach rong!");
else{ while (i
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
