DANH SÁCH LIÊN KẾT
Tổ chức lưu trữ DSLK đơn Định nghĩa
Danh sách liên kế là một danh sách mà các phần tử được kết nối với nhau nhờ vào
vùng liên kết của chúng.
 Một phần tử của DSLK bao gồm 2 vùng chính  Vùng chứa thông tin
 Vùng chứa địa chỉ, còn gọi là vùng liên kết
 Việc lưu trữ DSLK tốn bộ nhớ hơn DSĐ vì phải chứa thêm phần liên kết. Danh sách liên kết đơn
 DSLK đơn là loại DSLK mà vùng địa chỉ của mỗi phần tử chỉ chứa duy nhất
một địa chỉ của phần tử tiếp theo.
 Phần tử cuối cùng của DSLK đơn sẽ trỏ đến NULL.
 Khởi tạo danh sách rỗng  gán pHead = NULL
Kiểm tra danh sách có rỗng hay không  ktra pHead = NULL hay không
Kiểm tra danh sách có đầy hay chưa  không kiểm tra được tính đầy đối với DSLK
Duyệt danh sách  cho con trỏ p chạy từ đầu đến cuối
Thêm một phần tử vào danh sách danh sách
B1: Tạo một phần tử trong bộ nhớ
Tìm kiếm một phần tử trong danh sách  nếu tìm thấy
trả về con trỏ p, ngược lại trả về NULL
B2: Gắn phần tử vừa tạo vào danh sách Thêm vào đầu danh sách Thên vào sau vị trí q Thêm vào cuối danh sách
Xóa phần tử đứng sau phần tử q
Xóa phần tử có giá trị X
Xóa phần tử ở đầu danh sách Hủy toàn bộ danh sách STACK KHỞI TẠO RỖNG  ĐỊNH NGHĨA
 Stack là một danh sách hoạt động
theo cơ chế LIFO (Last In First Out).
 Thao tác thêm và hủy được thực
hiện ở cùng một phía của Stack 
KIỂM TRA CÓ RỖNG HAY KHÔNG
cơ chế LIFO: phần tử nào vào sau sẽ được lấy ra trước. TỔ CHỨC LƯU TRỮ
KIỂM TRA CÓ ĐẦY HAY CHƯA
THÊM MỘT PHẦN TỬ VÀO ĐỈNH STACK
LẤY MỘT PHẦN TỬ KHỎI ĐỈNH STACK
XEM THÔNG TIN PHẦN TỬ Ở ĐỈNH STACK QUEUE TỔ CHỨC LƯU TRỮ ĐỊNH NGHĨA
 Queue (hàng đợi) là một danh sách hoạt động theo cơ chế
FIFO (First In First Out).
 Thao tác thêm và hủy được thực hiện ở 2 phía của queue 
cơ chế FIFO: phần tử nào vào trước sẽ được lấy ra trước. KHỞI TẠO RỖNG
LẤY MỘT PHẦN TỬ Ở ĐẦU QUEUE
KIỂM TRA CÓ RỖNG HAY KHÔNG
XEM THÔNG TIN PHẦN TỬ Ở ĐẦU VÀ CUỐI QUEUE
KIỂM TRA CÓ ĐẦY HAY CHƯA
THÊM MỘT PHẦN TỬ VÀO CUỐI QUEUE LINEAR SEARCH BINARY SEARCH Ý TƯỞNG: Ý TƯỞNG:
Bắt đầu từ phần tử đầu tiên của danh sách, so sánh lần lượt Điều kiện: danh sách phải có thứ tự.
từng phần tử của danh sách với giá trị X cần tìm:
So sánh giá trị muốn tìm X với phần tử nằm ở vị trí giữa của danh sách:
 Nếu có phần tử bằng X, thuật toán dừng lại (thành
 Nếu bằng, tìm kiếm dừng lại (thành công). công).
 Nếu X lớn hơn thì tiếp tục tìm kiếm ở phần danh sách bên phải phần tử
 Nếu đến cuối danh sách mà không có phần tử nào giữa.
bằng X, thuật toán dừng lại (không thành công).
 Nếu X nhỏ hơn thì tiếp tục tìm kiếm ở phần danh sách bên trái phần tử giữa.
 Trường hợp tốt nhất: số lần so sánh 1
 Trường hợp xấu nhất: số lần so sánh n
 Trường hợp trung binh: số lần so sánh (n+1)/2
 Độ phức tạp T(n) = O(n) NGHỊCH THẾ Khái niệm
Xét một mảng các số a1, a2, … an
Nếu có i aj, thì đó là một nghịch thế.
Mảng chưa sắp xếp sẽ có nghịch thế.
Mảng đã có thứ tự sẽ không có nghịch thế a1≤ a2≤... ≤ an
 Trường hợp tốt nhất: số lần so sánh 1
 Trường hợp xấu nhất: số lần so sánh log(n)
 Trường hợp trung binh: số lần so sánh log(n/2)
 Độ phức tạp T(n) = O(log(n)) INTERCHANGE SORT BUBBLE SORT Ý TƯỞNG Ý TƯỞNG
Xuất phát từ phần tử đầu danh sách, tìm tất các các cặp nghịch Thuật toán sắp xếp bubble sort thực hiện sắp xếp dãy số bằng cách lặp lại
thế chứa phần tử này. Triệt tiêu chúng bằng cách đổi chỗ 2 phần công việc đổi chỗ 2 số liên tiếp nhau nếu chúng đứng sai thứ tự(số sau bé
tử trong cặp nghịch thế. Lặp lại xử lý trên với phần tử kế tiếp trong hơn số trước với trường hợp sắp xếp tăng dần) cho đến khi dãy số được danh sách. sắp xếp. Trường hợp tốt nhất: Trườ ố ầ ị ng hợp tốt nhất:
 Số lần so sánh: n(n-1)/2 ; s l n hoán v : 0 Trường hợp xấu nhất:
 Số lần so sánh: n(n-1)/2 ; số lần hoán vị: 0 Trườ ố ầ ị ng hợp xấu nhất:
 Số lần so sánh: n(n-1)/2 ; s l n hoán v : n(n-1))/2
 Số lần so sánh: n(n-1)/2 ; số lần hoán vị: n(n-1))/2 SELECTION SORT INSERTION SORT Ý TƯỞNG Ý TƯỞNG
Thuật toán selection sort sắp xếp một mảng bằng cách đi tìm phần Thuật toán sắp xếp chèn thực hiện sắp xếp dãy số theo cách duyệt từng
tử có giá trị nhỏ nhất(giả sử với sắp xếp mảng tăng dần) trong đoạn phần tử và chèn từng phần tử đó vào đúng vị trí trong mảng con(dãy số
đoạn chưa được sắp xếp và đổi cho phần tử nhỏ nhất đó với phần từ đầu đến phần tử phía trước nó) đã sắp xếp sao cho dãy số trong
tử ở đầu đoạn chưa được sắp xếp(không phải đầu mảng). Thuật toán mảng sắp đã xếp đó vẫn đảm bảo tính chất của một dãy số tăng dần.
sẽ chia mảng làm 2 mảng con
 Một mảng con đã được sắp xếp
 Một mảng con chưa được sắp xếp Trường hợp tốt nhất:
 Số lần so sánh: n-1 ; số lần hoán vị: 2(n-1) Trường hợp xấu nhất:
 Số lần so sánh: n(n-1)/2 ; số lần hoán vị: n(n-1)/2 + 2(n-1) Trường hợp tốt nhất:
 Số lần so sánh: n(n-1)/2 ; số lần hoán vị: 0 Trường hợp xấu nhất:
 Số lần so sánh: n(n-1)/2 ; số lần hoán vị: n-1 BINARY INSERTION SORT
SO SÁNH CÁC THUẬT TOÁN SẮP XẾP Ý TƯỞNG
Binary Insertion Sort được sử dụng để tìm kiếm nhị phân vị trí thích hợp để chèn
mục đã chọn ở mỗi lần lặp.