Cấu trúc dữ liệu và giải thuật
Đỗ Tuấn Anh
Email: [email protected]
Nội dung
z Chương 1 – Thiết kế và phân tích (5 tiết)
z Chương 2 – Giải thuật đệ quy (10 tiết)
z Chương 3 – Mảng và danh sách (5 tiết)
z Chương 4 – Ngăn xếp và hàng đợi (10
tiết)
z Chương 5 – Cấu trúc cây (10 tiết)
z Chương 8 – Tìm kiếm (5 tiết)
z Chương 7 – Sắp xếp (10 tiết)
z Chương 6 – Đồ thị (5 tiết)
Chương 3 – Mảng và Danh sách
1. Mảng
2. Danh sách
3. Một số phép toán trên danh sách nối đơn
4. Các dạng khác của danh sách móc nối
5. Sử dụng danh sách móc nối – Ví dụ bài
toán cộng đa thức
1. Mảng
z Mảng:
{Số phần tử cố đinh
{Kích thước một phần tử cố định
{Các phần tử mảng phải cùng kiểu
{Truy cập ngẫu nhiên (theo chỉ số)
Mảng: Số phần tử cốđịnh
zKích thướcmảng sau khi khai báo là cốđịnh
zVí dụ:
void notAllowed ();
{

a[0]
a[1]
a[4]
a[0][0]
a[0][1] a[0][2] a[0][3] a[0][4] a[4][3] a[4][4]
…
addr
addr + (i*5+j)*sizeof(double)
double a[5][5];
2. Danh sách
z Danh sách những người đến khám bệnh
{Ban đầu chưa có ai
{Có người mới đến
{Có người khám xong đi về
z (Tạo hình ảnh động tại đây)
Danh sách tuyến tính
z Một chuỗi các phần tử
z Tồn tại phần tử đầu và phần tử cuối
z Mỗi phần tử có phần tử trước và phần tử
sau
Danh sách tuyến tính
z Số phần tử biến đổi
z Một phần tử thường là một cấu trúc
(struct)
z Thao tác thường xuyên nhất
{Thêm phần tử
{Xóa phần tử
z Các thao tác khác:
{Tìm kiếm
{Ghép 2 danh sách

167
167
169
177
178
165
Thêm mộtphầntử thứ i vào
mảng
- Chuyểncácphầntử
i->n xuống các vị trí
i+1 ->n+1
-Thêmphầntử cần
thêm vào vị trí thứ i
i
n
n+1
i+1
Lưu trữ kế tiếp - Xóa mộtphầntử
123
125
135
155
161
166
167
167
169
177
178
Xóa mộtphầntử thứ i khỏi

z Một danh sách móc nối là mộtchuỗicác
phần tử, gọi là nút, đượcmócnốivới nhau
z Mỗi nút phải bao gồm
{ Dữ liệu
{ Móc nối(địa chỉ) tớinút
tiếp theo trong danh sách
z Head: con trỏ trỏđến nút đầu tiên
z Nút cuốicùngtrỏđến NULL
A
∅
Head
B C
A
data
next
node
Tổ chức danh sách móc nối
z Nút = dữ liệu + móc nối
{Định nghĩa:
typedef struct node {
int data;
struct node *next;
}Node;
{Tạo nút mới:
Node* p =
malloc(sizeof(Node));
{Giải phóng nút:
free(p);
head
15