CẤU TRÚC DỮ LIỆU
CẤU TRÚC DỮ LIỆU
(BẬC CAO ĐẲNG)

Nguyễn Thanh Cẩm
Nguyễn Thanh Cẩm
BÀI GIẢNG
BÀI GIẢNG
KHOA KHOA HỌC MÁY TÍNH – BỘ MÔN LẬP TRÌNH
Chương2:
Chương2:CẤU TRÚC DỮ LIỆU DANH SÁCH
CẤU TRÚC DỮ LIỆU DANH SÁCH1. 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
NỘI DUNG TRÌNH BÀY
1
11. Danh sách
a. Định nghĩa
b. Các phép toán trên danh sách

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ụ:
b. Các phép toán trên danh sách1. 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ụ:
b. Các phép toán trên danh sách1. 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ụ:
b. Các phép toán trên danh sách1. 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)

đứng
sau phần tử a
i
.
a. Định nghĩa
a
0
a
1
… a
i
a
i+1
… a
n-2
a
n-1
add[1] add[i] add[n]← d →
add[i] = add[1] + (i-1)*d2. Danh sách đặc (CONDENSED LIST)
#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;
b. Khai báo

return L.Last == 0;
}
c. Các phép toán2. Danh sách đặc (CONDENSED LIST)
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ị.
c. Các phép toán2. Danh sách đặc (CONDENSED LIST)
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 ((P<0) || (P>L->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++;
}
}
c. Các phép toán2. Danh sách đặc (CONDENSED LIST)

if(L.element[i]==x) found=1;
else i++;
if(found==0) return -1;
return i;
}
}
c. Các phép toán2. Danh sách đặc (CONDENSED LIST)
v. Tìm kiếm phần tử trong danh sách
Trường hợp danh sách có thứ tự
(tự nghiên cứu)
c. Các phép toán2. Danh sách đặc (CONDENSED LIST)
i. Ưu điểm
d. Đặc điểm của danh sách đặc

Sử dụng 100% ô nhớ để lưu trữ thông tin

Truy xuất trực tiếp phần tử List[i]

Dễ dàng tìm kiếm phần tử bằng phương pháp
nhị phân, nếu danh sách có thứ tự.2. Danh sách đặc (CONDENSED LIST)
ii. Nhược điểm