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

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;