PHÉP BIẾN ĐỔI KHÓA – HÀM BĂM part 2

Chia sẻ: Pham Duong | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

82
lượt xem 15
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

. - Giá trị của hàm trả về vị trí của phần tử thêm vào hoặc 0 nếu bảng băm đầy. - Nếu đã có khóa k ở trong bảng thì hàm cho biết vị trí của khóa này trong bảng băm mà không thêm vào khóa này. - Phần tử ở vị trí 0 luôn là vị trí trống, nó được sử dụng để đảm bảo việc tìm kiếm luôn kết thúc thành công, nó đống vai trò như phần tử cầm canh. Function

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: PHÉP BIẾN ĐỔI KHÓA – HÀM BĂM part 2

- Procedure Initialize; var i:integer; Begin For i:=0 to M do T[i].key:=free; R:=M+1; End; c. Thêm một khóa vào bảng băm. - Hàm THEM_KHOA(k:integer) thực hiện việc thêm khóa k vào bảng băm. - Giá trị của hàm trả về vị trí của phần tử thêm vào hoặc 0 nếu bảng băm đầy. - Nếu đã có khóa k ở trong bảng thì hàm cho biết vị trí của khóa này trong bảng băm mà không thêm vào khóa này. - Phần tử ở vị trí 0 luôn là vị trí trống, nó được sử dụng để đảm bảo việc tìm kiếm luôn kết thúc thành công, nó đống vai trò như phần tử cầm canh. Function THEM_KHOA(k:integer):integer; Var i,j :integer; Begin I:=H(k)+1; {0
if (i0) and (T[i].keyk) then begin T[i].key:=k; T[i].next:=0; End; THEM_KHOA:=i; End; c)Phương pháp băm kép: Ví dụ, ta có thể dùng một mảng các con trỏ chỉ đến các nút gốc của các cây tìm kiếm nhị phân và dúng các thủ tục chèn và tìm kiếm ở phần trước. Một sơ đồ phổ biến khác, gọi là băm kép sẽ được mô tả tương tự như phương pháp dò tuyến tính, chỉ khác là thay vì kiểm tra mỗi phần tử liên tiếp tại vị trí xung đột đó, do đó số lần dò sẽ giảm đi so với dò tuyến tính, chúng ta dùng một hàm băm thứ hai. Chú ý, hàm băm thứ hai h2 phải được chọn cẩn thận ở một vài khía cạnh, nếu không thì chương trình có thể không hoạt động tốt. Yếu tố thứ ba trong việc thiết kế bảng băm là việc chọn bảng băm. Dĩ nhiên là dáng điệu của hàm này ảnh hưởng đến tần số va chạm. Ví dụ, hàm băm h(Name) = Name[1] ở ví dụ trước không phải là sự chọn lựa tốt vì một vài kí tự như các chữ đầu của tên xuất hiện nhiều lần hơn các kí tự khác. Do đó danh sách liên kết của các tên bắt đầu bằng ‘S’ sẽ dài hơn nhiều so với các danh sách chứa những tên bắt đầu bằng ‘Z’. “Hiệu ứng chùm” này làm cho việc tìm kiếm các tên bắt đầu bằng S lâu hơn bắt đầu bằng Z. Một hàm băm tốt hơn phân phối đến các tên trong bảng băm có thể là giá trị “trung bình” của các kí tự đầu và cuối trong tên. h(Name) = chr(ord( FirstLetter ) + ord(LastLetter) div 2) hoặc có thể dùng gía trị trung bình của tất cả các kí tự. Tuy nhiên hàm băm không được quá phức tạp để việc tính nó có thể chấp nhận được. Một hàm băm lý tưởng dễ tính và rải đều các mục trong bảng băm làm giảm xác xuất va chạm đến giá trị nhỏ nhất. Mặc dù không có phương pháp băm nào hoàn thiện trong mọi trường hợp, một phương pháp thông dụng hiện thời là băm ngẫu nhiên kỹ thuật tạo số ngẫu nhiên để rải đều các mục trong bảng băm “một cách ngẫu nhiên”. Trước hết mục đó được chuyển sang một số nguyên lớn ngẫu nhiên bằng cách dùng một lệnh, chẳng hạn như: RandomInt := (( 25173 * Item ) + 13849) mod 65536
Và gía trị này được chia theo môđun kích thước bảng để xác định vị trí của mục: Location := RandomInt mod TSize; Có thể dùng hàm băm này với các mục không phải là số nguyên nếu trước hết ta mã hoá những mục này như là những số nguyên; ví dụ, một tên có thể được mã hoá như tổng của các mã số ASCII của một vài hoặc tất cả các giá trị của kí tự đó. Chương trình giải quyết một số bài toán về hàm băm: Bài 1: dùng bảng băm với 11 vị trí và hàm băm h(i)=I mod 11 ,hãy chỉ ra bang băm nhận được sau khi chèn các số nguyên sau theo thư tự : 26, 42, 5, 44, 92, 59, 40, 36, 12, 60, 80. Dùng : a. Thăm dò tuyến tính b. Phương pháp dâu truyền Để giai quyết va chạm.
để giải quyết bài toán trên ta xây dựng hàm băm và bảng băm với kích thước 100 và chọn m=97 thay vì 11 .Như vậy chúng ta có thể nhập được tối đa 100 phần tử Xây dựng thủ tục tìm kiếm để thấy được ưu điểm của việc sử dụng bảng băm lưu trữ các phần tử: Do các phần tử được lưu vào bảng băm tai vị trí úng với giá trị băm (khoá) của nó nên chúng ta không cần phải sắp xếp -> rút ngắn được thời gian cũng như số lượng phép toán trong quá trình tim kiếm Chương trình: program tp; {uses crt;} const m=97; var n,i,dai,kq,j:integer; {"dai" la bien do do dai cua xau} x,a,tk: string ; {"tk" la bien chi xau can tim kiem} bangbam : array[0..101] of string; ch:char; function h( var x:string) :integer; var tong,j:integer; begin dai:=length(x); tong:=0; for j:=1 to dai do tong:=tong+ ord(x[j]); h:= tong mod m; end; procedure timkiem; begin writeln; writeln('nhap chuoi can tim'); readln(tk); writeln('gia tri bam cua ',tk,' la ',h(tk)); if bangbam[h(tk)]=tk then begin writeln('co chuoi ',tk,' trong co so du lieu'); writeln('vi tri cua chuoi ',tk,' trong co so du lieu la',h(tk));
end else begin i:=h(tk); repeat i:=i+1; until (i=99) or( bangbam[i]=tk); if i=99 then writeln('khong co chuoi ',tk,' trong co so du lieu') else begin writeln('co chuoi ',tk,' trong co so du lieu'); writeln('chuoi ', tk, ' thuoc vi tri thu ',i,' trong bang bam ') ; writeln('vi tri cua chuoi tren khac voi gia tri bam la do da xay ra va cham '); end; end; end; begin {CHUONG TRINH CHINH } writeln('ban muon nhap bao nhieu phan tu? chu y "NHAP DANG SO "!'); readln(n); while n>100 do begin writeln(' so phan tu ma ban nhap vao la qua lon !nhap lai voi so phan tu nho hon 100'); readln(n); end ; for i:=0 to 100 do bangbam[i]:=''; for i:=0 to n-1 do begin writeln('nhap gia tri thu',i+1); readln(a); if bangbam[h(a)]='' then
begin bangbam[h(a)]:=a ; writeln('gia tri cua ',a,' trong bang bam la',h(a)); end else if bangbam[h(a)]=a then begin repeat writeln('da co sau tren trong co so du lieu ! de nghi nhap mot sau khac') ; readln(a); until bangbam[h(a)]='' ; bangbam[h(a)]:=a; writeln('gia tri bam cua sau da nhap la ',h(a)); end else if bangbam[h(a)]a then begin writeln('da xay ra va cham tai vi tri ',h(a),' trong bang bam'); j:=h(a) ; repeat j:=j+1 ; until bangbam[j]=''; bangbam[j]:=a; writeln('gia tri bam cua chuoi ',a,' sau khi giai quyet va cham la ',j); end; end; writeln('ban co muon thuc hien thao tac tim kiem khong? Y\N'); readln(ch); if ((ch='Y') or (ch = 'y')) then timkiem ; readln; end.
Bµi tËp 1 gi¶i b»ng ph¬ng ph¸p d©y truyÒn program bai1; type banghi=record ten:string; end; elementtype=banghi; point=^usernode; usernode=record data:elementtype; next:point; end; bangbam=array[0..12] of point; var f:text; userRec:banghi; userT:bangbam; found:boolean; loc:integer; p:point; ten:string; c:char; dem:integer; procedure khoitao(var T:bangbam); var i:integer; begin for i:=0 to 12 do T[i]:=nil; end;
function hambam(ten:string):integer; var tong:integer; i:integer; begin tong:=0; for i:=1 to length(ten) do tong:=tong+ord(ten[i]); hambam:=tong mod 11; end; procedure timkiem(T:bangbam;item:elementtype); begin loc:=hambam(item.ten); p:=T[loc]; found:=false; dem:=1; while not found and (pnil) do if p^.data.ten=item.ten then begin found:=true; writeln('da co o vi tri ',loc,'-',dem); end else begin dem:=dem+1; p:=p^.next; end; end; procedure nhap(var T:bangbam;item:elementtype);
begin timkiem(T,item); if found=false then begin new(p); p^.data:=item; p^.next:=T[loc]; T[loc]:=p; writeln('da dien vao vi tri ',loc,'-',dem); end; end; procedure ghi; var i:integer; begin for i:=1 to 11 do begin write('',i,': '); begin p:=userT[i]; while pnil do begin write('',p^.data.ten,' '); p:=p^.next; end; writeln; end; end; end; procedure doc;
begin end; begin khoitao(userT); begin repeat writeln('Nhap ten: ');readln(userrec.ten); nhap(userT,userrec); write('ban co muon nhap nua khong (y/n) ?');readln(c); until c='n'; write('ban co muon xem bang bam khong (y/n) ?'); readln(c); if c='y' then ghi; writeln; writeln('Cac khoa co cung vi tri thi co cung mot dong'); writeln('Cac khoa co vi tri khac nhau thi khac dong'); readln; end; end.
Bài 2: Giả sử rằng các ký tự được mã hoá như sau : ‘A’=1, ‘B’=2, ….’Z’=26. Dùng bảng băm với 11 vị trí và hàm băm h(i)=average mod 11 , trong đó average là giá trị trung bình của các mã số của các ký tự đầu và cuối trong I, hãy chỉ ra bảng băm nhận được khi chèn các định danh sau theo thứ tự : Beta , rate, freq, alpha, mean, sum, num, bar, wage, pay, kappa. Dùng: a.Phương pháp thăm dò tuyến tính . b. Phương pháp dây chuyền.