Những mã vùng cần biết môn Công nghệ thông tin | Đại học Hoa Sen

Những mã vùng cần biết môn Công nghệ thông tin | Đại học Hoa Sen được sưu tầm và soạn thảo dưới dạng file PDF để gửi tới các bạn sinh viên cùng tham khảo, ôn tập đầy đủ kiến thức, chuẩn bị cho các buổi học thật tốt. Mời bạn đọc đón xem

DANH SÁCH LIÊN K T
Đị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. ế
Mt phn t c a DSLK bao g m 2 vùng chính
Vùng cha 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ữ hơn DSĐ DSLK tn b nh 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 ca mi phn t ch cha duy nh t
một địa ch ca ph n t ti p theo. ế
Phn t cui cùng c tr ủa DSLK đơn sẽ đến NULL.
Khi t o danh sách r ng gán pHead = NULL
Kim 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 vi DSLK
T ch ức lưu trữ DSLK đơn
Duyt danh sách cho con tr p ch y t n cu i đầu đế
danh sách
Tìm ki m m t ph n t trong danh sách n u tìm th y ế ế
tr v con tr c l i tr v NULL p, ngượ
Thêm m t ph n t vào danh sách
B1: T o m t ph n t trong b nh
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 phn t u danh sách đầ
Xóa ph n t ng sau ph đứ n t q
Xóa phn t có giá tr X
Hy toàn b danh sách
STACK
ĐỊNH NGHĨA
Stack là m t danh sách ho ng ạt độ
theo cơ chế LIFO ( ast n irst ut). L I F O
Thao tác thêm và h c th c ủy đượ
hin cùng m t phía c a Stack
cơ chế LIFO: phn t nào vào sau s
được lấy ra trước.
T CHỨC LƯU TRỮ
LY MT PH N T KH NH STACK ỎI ĐỈ
XEM THÔNG TIN PH N T NH STACK ĐỈ
QUEUE
ĐỊNH NGHĨA
Queue (hàng đợi) là mt danh sách ho ạt động theo cơ chế
FIFO ( irst n F I First Out).
Thao tác thêm và h c th c hi n 2 phía c a queue ủy đượ
cơ chế FIFO: phn t c s c l c. nào vào trướ đượ ấy ra trướ
T CHỨC LƯU TRỮ
KHI T O R NG
KIM TRA CÓ RNG HAY KHÔNG
KIỂM TRA CÓ ĐẦY HAY CHƯA
THÊM M T PH N T VÀO CU I QUEUE
LY MT PH N T U QUEUE ĐẦ
XEM THÔNG TIN PH N T U VÀ CU I QUEUE ĐẦ
LINEAR SEARCH
Ý TƯỞNG:
Bắt đầ ần lượu t phn t đầu tiên ca danh sách, so sánh l t
tng ph n t c a danh sách v i giá tr X c n tìm:
Nếu ph n t b ng X, thu t toán d ng l i (thành
công).
Nếu đến cu i danh sách không ph n t nào
bng X, thu t toán d ng l i (không thành công).
Trường hp t t nh t: s l n so sánh 1
Trường hp x u nh t: s l n so sánh n
Trường hp trung binh: s l n so sánh (n+1)/2
Độ ph c t p T(n) = O(n)
NGHCH TH
Khái ni m
Xét m t m ng các s a1, a2, … an
Nếu có i<j và ai > aj, thì đó là một nghch 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
BINARY SEARCH
Ý TƯỞNG:
Điều kin: danh sách ph i có th t .
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 bng, tìm kiếm d ng l i (thành công).
Nếu X lớn hơn thì tiếp tc tìm ki m ph n danh sách bên phế i phn t
gia.
Nếu X nh p t c tìm ki m ph hơn thì tiế ế n danh sách bên trái phn t
gia.
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
Ý TƯỞNG
Xut phát t ph n t đầu danh sách, tìm t t các các c p ngh ch
thế cha ph n t này. Tri t tiêu chúng b ng cách đổi ch 2 ph n
t trong c p ngh ch th . L p l i x trên v i ph n t k ti p trong ế ế ế
danh sách.
Trường h p t t nh t:
S ln so sánh: n(n-1)/2 ; s l n hoán v : 0
Trường h p x u nh t:
S ln so sánh: n(n-1)/2 ; s l n hoán v : n(n-1))/2
BUBBLE SORT
Ý TƯỞNG
Thut 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 li
công vi i ch 2 s liên ti p nhau n ng sai th t sau bé ệc đổ ế ếu chúng đ (s
hơn số ới trườ ếp tăng dần) cho đế trước v ng hp sp x n khi dãy s được
sp x p. ế
Trường h p t t nh t:
S ln so sánh: n(n-1)/2 ; s l n hoán v : 0
Trường h p x u nh t:
S ln so sánh: n(n-1)/2 ; s l n hoán v : n(n-1))/2
SELECTION SORT
Ý TƯỞNG
Thut toán selection sort s p x p m ế t m ng b n ằng cách đi tìm phầ
t có giá tr nh nh s v i s p x p m n t(gi ế ảng tăng dần) trong đoạ
đoạn chưa đượ ếp đổ ất đó vớc sp x i cho phn t nh nh i phn
t đầu đoạn chưa được s p x p(không ph ế ải đầu mng). Thu t toán
s chia m ng làm 2 m ng con
Mt mảng con đã được sp xếp
Mt mảng con chưa được sp xếp
Trường h p t t nh t:
S ln so sánh: n(n-1)/2 ; s l n hoán v : 0
Trường h p x u nh t:
S ln so sánh: n(n-1)/2 ; s l n hoán v : n-1
INSERTION SORT
Ý TƯỞNG
Thut 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 ế ế
phn t chèn t ng ph n t đó vào đúng vị trí trong m ng con(dãy s
t đầu đến phn t phía trước nó) đã sp xếp sao cho dãy s trong
mng s m b o tính ch t c a m t dãy s n. ắp đã xếp đó vẫn đả tăng dầ
Trường h p t t nh t:
S ln so sánh: n-1 ; s ln hoán v : 2(n-1)
Trường h p x u nh t:
S ln so sánh: n(n-1)/2 ; s l n hoán v : n(n-1)/2 + 2(n-1)
BINARY INSERTION SORT
Ý 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.
SO SÁNH CÁC THU T TOÁN S P X P
| 1/40

Preview text:

DANH SÁCH LIÊN KT
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 THUT TOÁN SP XP Ý 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.