Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Tài liệu đang bị lỗi
File tài liệu này hiện đang bị hỏng, chúng tôi đang cố gắng khắc phục.
Chương 3: Phân tích độ phức tạp một số giải thuật trên cấu trúc dữ liệu pps
Nội dung xem thử
Mô tả chi tiết
1
Ch ng 3
Phân tích ph c t p m t s
gi i thu t trên c u trúc d li u
2
N i dung
1. Tìm ki m tu n t trên danh s ch liên k t
2. Cây tìm ki m nh phân
3. Hàng i có u tiên và heapsort
4. K thu t b m
3
1.Tìm ki m tu n t trên danh s ch liên k t
Tìm ki m tu n t sequential search) c th c th c
hi n th ng qua vi c d ng danh s ch liên k t (linked
list) bi u di n c c m u tin trong t p tin.
M t l i i m: d làm cho danh s ch liên k t có th t
mà giúp cho vi c tìm ki m nhanh chóng h n.
4
3 4 7 21
Z
…
Tìm ki m tu n t trên m t danh s ch liên k t có
th t .
Qui c: z là nút gi trong danh sách liên k t.
type link = ↑ node
node = record key, info: integer;
next: link
end;
var head, t, z: link;
i: integer;
5
Gi i thu t tìm ki m tu n t trên danh s ch
liên k t
procedure initialize;
begin
new(z); z↑.next: = z;
new(head); head↑.next:= z
end;
function listsearch (v: integer; t: link): link;
begin
z↑.key: = v;
repeat t:= t↑.next until v < = t↑.key;
if v = t↑.key then listsearch:= t
else listsearch: = z
end;