INDUSTRIAL UNIVERSITY OF HO CHI MINH CITY
Data structures and algorithms
Doubly/Circular linked list
Dr. Ngo Huu Dung
Dẫn nhập
Danh sách liên kết đôi
Danh sách liên kết vòng
2
Hai chiều
Thêm con trỏ previous
Từ một nút có thể duyệt đến nút trước và sau nó
Các thao tác tương tự singly linked list
Xử lý thêm cho con trỏ previous
Nút cuối trỏ đến nút đầu
Có thể là danh sách đơn hoặc đôi
Các thao tác tương tự
Cấu trúc dữ liệu và giải thuật - DSLK
prev
data
next
prev
data
next
prev
data
next
tail
head
NULL
NULL
Doubly linked list
Danh sách liên kết đôi
Doubly linked list – Khai báo
Khai báo nút kiểu cấu trúc
Phần dữ liệu (int, float, char, struct…)
Phần liên kết (pointer)
Khai báo con trỏ head và tail
1.
2.
3.
4.
5.
6.
7.
8.
9.
4
struct Node
{
int data;
struct Node *next;
struct Node *prev;
};
typedef struct Node tNode;
tNode *head;
tNode *tail;
prev
Cấu trúc dữ liệu và giải thuật - DSLK
data
head
tail
next
Thao tác cơ bản
Khởi tạo danh sách, nút mới
Thêm phần tử
Duyệt danh sách
5
Min, max, giá trị X
Xoá phần tử
Xuất, trích xuất, đếm, tính toán
Tìm kiếm
Vào đầu, vào cuối, chèn vào sau một phần tử
Ở đầu, ở cuối, ở giữa
Sắp xếp
Cấu trúc dữ liệu và giải thuật - DSLK
nguon tai.lieu . vn