Bài giảng Thao tác với danh sách

Giới thiệu
Thao tác với danh sách
1
Nội dung trình bày
• Mô hình cấu trúc dữ liệu mảng
• Mô hình cấu trúc dữ liệu tự trỏ
 Danh sách liên kết đơn
 Danh sách liên kết vòng
 Danh sách liên kết đôi
• Một số cấu trúc dữ liệu
 Cấu trúc dữ liệu stack
 Cấu trúc dữ liệu queue
2
Cấu trúc dữ liệu mảng
• Là dãy các phần tử liên tiếp nhau trong bộ nhớ
 Một mảng được trỏ bởi một con trỏ
 Một mảng là mối khối nhớ liên tục
 Truy xuất phần tử mảng là ngẫu nhiên (truy xuất 
đến phần tử theo chỉ số)
• Đặc trưng về quản lý
 Mảng được cấp phát tại thời điểm khai báo
 Không thay đổi được số lượng phần tử mảng tại 
thời điểm thực hiện
 Cần khai báo lượng tối đa có thể cần phải lưu trữ
3
Cấu trúc dữ liệu mảng (t)
• Sử dụng con trỏ, và cấp phát động
 Dữ liệu được cấp phát tại thời điểm hoạt động
 Sự thay đổi về dung lượng bộ nhó khó khăn
4
Cấu trúc dữ liệu mảng (t)
• Phù hợp
 Không gian dữ liệu bé, ổn định
 Cần phải tính toán với truy xuất phần tử là ngẫu 
nhiên
 Ví dụ: sắp xếp đếm, sắp xếp nổi bọt, chọn, tìm kiếm 
nhị phân
• Không phù hợp
 Dữ liệu lớn, thay đổi thường xuyên về dung lượng
 Xử lý theo phương thức tuần tự
5
Cấu trúc tự trỏ
• Cấu trúc tự trỏ đến chính bản thân nó
typedef struct {Tên_kiểu} 
{ 
{Kiểu_1} {Tên_trường_1} ; 
<Kiểu_2} {Tên trường_2} ; 
.. 
{Kiểu_n} {Tên_trường_n} ;
{ Tên_kiểu } *{Con_trỏ_tự_trỏ_1};
{ Tên_kiểu } *{Con_trỏ_tự_trỏ_n};
};
6
Cấu trúc tự trỏ (t)
typedef struct list{
int data;
list *next;
};
7
Danh sách liên kết đơn
• Mô hình
8
Head NULL
Danh sách liên kết đơn (t)
• Mô hình chức năng
 Khởi tạo - init
 Giải phóng danh sách - empty
 Thêm phần tử (đầu, cuối) – addhead, addtail
 Loại bỏ phần tử (đầu, cuối) – deletehead, deletetail
 Tìm kiếm phần tử - search
 Chèn phần tử ở sau - insert
 Xóa phần tử -delete
 Kiểm tra rỗng - isempty
9
Danh sách liên kết đơn (t)
• Void Init (list *head)
 List=null
• Int isempty(list *head)
 If(head==null) return 0;
 Return -1;
• list* search(list *head, int x)
 t=head;
 while(t!=null)
• If(t.data==x) break;
• T=t->next;
 return t;
10
Danh sách liên kết đơn (t)
11
lifo NULL
NULLlifo
NULLlifo
Danh sách liên kết đơn (t)
• Int addhead(list *head, int x)
 T=malloc(sizeof(list));
 If(T==null)
• Return -1;
 T->data=x;
 T->next=head;
 Head=t;
12
Danh sách liên kết đơn (t)
13
NULLlifo
NULLlifo
NULLlifo
Danh sách liên kết đơn (t)
• Int deletehead(list *head, int *x)
 If(head==null)
• Return -1;
 T=head;
 Head=t->next;
 *X=t->data;
 Free(t);
 Return 0;
14
Danh sách liên kết vòng
• Thay vì phần tử ở đuôi chỉ đến null, danh sách 
liên kết vòng chỉ đến head;
 Tạo vòng, mọi phần tử trong vòng có thể là đầu
 Các thao tác cần kiểm tra với con trỏ head để biết 
kết thúc vòng
 Phù hợp với dạng dữ liệu mô tả là vòng
15
Danh sách liên kết đôi
• Mỗi phần từ được định nghĩa có con trỏ left và 
right;
 Con trỏ left chỉ về phần tử bên trái, right chỉ về phần 
tử phải
 Mọi thao tác cần thực hiện với hai con trỏ
 Cho phép duyệt theo chiều ngược và xuôi
16
Cấu trúc dữ liệu stack
• Khởi tạo – Init
• Đưa phần tử vào stack – push
• Lấy phần tử khỏi stack – pop
• Kiểm tra rỗng – isempty
• Kiểm tra giá trị ở đỉnh - gettop
17
Cấu trúc dữ liệu stack (t)
• Triển khai trên mảng
 Khai báo mảng đủ
 Dùng chỉ số để quy định phần tử ở đỉnh
• Sử dụng danh sách liên kết
 Init – init 
 Push-addhead
 Pop-deletehead
 Isempty – isempty
18
Cấu trúc dữ liệu stack (t)
• Int gettop(list *head, int *x)
 If(head==null) return -1;
 X=head->data;
 Return 0;
19
Cấu trúc dữ liệu queue
• Khởi tạo – Init
• Đưa phần tử vào stack – put
• Lấy phần tử khỏi stack – get
• Kiểm tra rỗng – isempty
20
Cấu trúc dữ liệu queue (t)
• Triển khai dạng mảng
 Sử dụng mảng với độ lớn chấp nhận được
 Sử dụng hai con trỏ là đầu và đuôi để đưa vào và lấy 
ra
 Do việc tăng liên tục nên cần kiểm tra tình huống là 
chỉ số đủ lớn thì quay lại bằng 0
• Triển khai dạng danh sách liên kết
 Sử dụng hai con trỏ là head, tail để thêm vào lấy ra
 Thêm bằng head, lấy ra bằng head
21
Cấu trúc dữ liệu queue (t)
• Init(list *head, *tail)
 Head=null
 Tail=null
• Isempty(list*head, *tail)
 If(head==null)
• Return 0
 Return -1
22
Cấu trúc dữ liệu queue (t)
• Int Put(list *head, *tail, int x)
 T=malloc(sizeof(list));
 If(t==null)
• Return -1;
 T->data=x;
 T->next=null;
 If(head==null)
• Head=t;
• Tail=t;
 Tail->next=t;
 Tail=t;
 Return 0;
23
Cấu trúc dữ liệu queue (t)
• Int get(list *head, * tail, int *x)
 If(head==null)
• Return -1;
 T=head;
 Head=head->next;
 If(head==null) tail=null;
 *x=t->data;
 Free(t);
 Return 0;
24
Nội dung trình bày
• Mô hình cấu trúc dữ liệu mảng
• Mô hình cấu trúc dữ liệu tự trỏ
 Danh sách liên kết đơn
 Danh sách liên kết vòng
 Danh sách liên kết đôi
• Một số cấu trúc dữ liệu
 Cấu trúc dữ liệu stack
 Cấu trúc dữ liệu queue
25
26
Bài tập
- Triển khai kiểu dữ liệu
- Danh sách liên kết đơn
- Danh sách liên kết vòng
- Danh sách liên kết kép
- Stack 
- Mảng
- Danh sách liên kết
- Queue
- Mảng 
- Danh sách liên kết
- Chuẩn bị bài toán chuyển trung tố hậu, tố, và tính toán số lớn