Cấu trúc dữ liệu
1EE3490: Kỹ thuật lập trình – HK1 2011/2012
Đào Trung Kiên – ĐH Bách khoa Hà Nội
Mở đầu: mảng động
Mảng trong C có số phần tử cố định từ khi khai báo
Mảng động là mảng có số phần tử thay đổi: bản chất là
một con trỏ và một biến cho biết số phần tử
int n = 5;
int* arr = (int*)malloc(n*sizeof(int));
Bài toán chèn phần tử vào mảng động:
pos = 2; val = 25;
arr1 = (int*)malloc((n+1)*sizeof(int));
memcpy(arr1, arr, pos*sizeof(int));
memcpy(arr1+pos+1, arr+pos, (n-pos)*sizeof(int));
arr1[pos] = val;
free(arr);
arr = arr1;
Tương tự khi xoá phần tử
2EE3490: Kỹ thuật lập trình – HK1 2011/2012
Đào Trung Kiên – ĐH Bách khoa Hà Nội
10
20
30
40
50
25
10
20
25
30
40
50
Khái niệm
Ví dụ trên cho thấy mảng động khá kém hiệu quả trong
việc thêm/bớt phần tử vì cần di chuyển các vùng nhớ,
nhất là khi mảng có nhiều phần tử cần các cấu trúc dữ
liệu linh hoạt hơn
Các cấu trúc dữ liệu phổ biến, ứng dụng tuỳ bài toán:
Ngăn xếp (stack)
Hàng đợi (queue)
Danh sách liên kết (linked list)
Mảng động (vector, dynamic array)
Ánh xạ (map), từ điển (dictionary), bảng băm (hash table)
Tập hợp (set)
Cây (tree)
Đồ thị (graph)
3EE3490: Kỹ thuật lập trình – HK1 2011/2012
Đào Trung Kiên – ĐH Bách khoa Hà Nội
Danh sách liên kết (DSLK)
Là tập hợp các phần tử được móc nối với nhau bằng con trỏ:
Một con trỏ trỏ đến phần tử đầu tiên (hoặc NULL nếu chưa có phần tử nào)
Mỗi phần tử bao gồm 2 thành phần: dữ liệu, con trỏ next tới phần tử tiếp theo
Con trỏ next của phần tử cuối cùng trỏ đến NULL
4EE3490: Kỹ thuật lập trình – HK1 2011/2012
Đào Trung Kiên – ĐH Bách khoa Hà Nội
data
next
data
next
data
next
list
