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

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

Thêm vào BST

Báo xấu

88
lượt xem 13
download

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

Để giải quyết va chạm Chương trinh: để giải quyết bài toán trên trước hết ta cần xây dựng được hàm băm theo đúng yêu cầu của đề bài. Mã ASCII của A la 65 ,của B là 66 nhưng giá trị cho trong bài la 1 va 2 do đó trong hàm băm ta phai trừ đi 128 những ưu điểm của phương pháp trên đã được đề cập đến trong bài 1. Tuy nhiên trong quá trình nhập dữ liệu ta không bắt buộc phải khai báo số phần tử cần nhập mà ta cứ thực hiện thao...

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 3

Để giải quyết va chạm Chương trinh: để giải quyết bài toán trên trước hết ta cần xây dựng được hàm băm theo đúng yêu cầu của đề bài. Mã ASCII của A la 65 ,của B là 66 nhưng giá trị cho trong bài la 1 va 2 do đó trong hàm băm ta phai trừ đi 128 những ưu điểm của phương pháp trên đã được đề cập đến trong bài 1. Tuy nhiên trong quá trình nhập dữ liệu ta không bắt buộc phải khai báo số phần tử cần nhập mà ta cứ thực hiện thao tác nhập cho đến khi nhập đủ 11 phần tử(theo yêu cầu của bài) hoặc nhập ‘Thoát’ để thoát khỏi quá trình nhập. Chương trình cụ thể được xây dựng như sau: program baitap2; const n=11; var a:string; j,vitri:integer; bangbam:array[0..10] of string; ch:char; function h( var x:string) :integer; var tong,j,dai:integer; begin dai:=length(x); tong:=(ord(x[1])+ ord(x[dai])-128) div 2; h:= tong mod 11; end ; procedure timkiem; var tk:string; i:integer; begin { bat dau thu tuc } writeln('nhap chuoi can tim'); readln(tk); write('gia tri bam cua chuoi tren la ',h(tk)); for i:=0 to 10 do begin if bangbam[h(tk)]=tk then
begin writeln('co chuoi ',tk,' trong co so du lieu '); writeln('vi tri cua ',tk,' trong bang bam la ',h(tk)); end else if bangbam[h(tk)]='' then writeln('khong co chuoi ',tk,' trong co so du lieu') else if bangbam[h(tk)] tk then begin i:=h(tk); repeat i:=i+1; until( bangbam[i]=tk) or (i>10); if bangbam[i]=tk then begin writeln('co chuoi ',tk,' trong co so du lieu'); writeln('vi tri cua ',tk,' trong bang bam la ',i); writeln('do co va cham xay ra nen gia tri bam cua chuoi tren khac voi vi tri cua no trong bang bam '); end ; if i>10 then writeln('khong co chuoi tren trong co so du lieu'); end; end; end; begin {CHUONG TRINH CHINH} for j:=0 to 10 do {khoi tao gia tri cua bang bam la rong} bangbam[j]:=''; j:=0; repeat writeln('nhap chuoi thu ',j+1);
readln(a); if bangbam[h(a)] ='' then begin bangbam[h(a)]:=a ; writeln('chuoi ',a,' duoc luu vao vi tri thu ',h(a),' trong bang bam'); end else if bangbam[h(a)]=a then begin repeat writeln('da co chuoi tren trong co so du lieu ! hay nhap chuoi khac'); readln(a); until bangbam[h(a)]='' ; bangbam[h(a)]:=a; writeln ('vi tri cua chuoi ',a,' trong bang bam la ',h(a)); end else if bangbam[h(a)]a then begin vitri:=h(a); repeat vitri:=vitri+1; until bangbam[vitri]='' ; bangbam[vitri]:=a; writeln('chuoi ',a,' duoc luu vao vi tri thu ',vitri,' trong bang bam' ); writeln('vi tri cua chuoi tren khac voi gia tri bam cua no do da xay ra va cham'); end; j:=j+1 ; until j>10; 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 2 gi¶i b»ng ph¬ng ph¸p d©y truyÒn program bai2; 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 averange:integer; n:integer; begin n:=length(ten); averange:=(ord(ten[1])+ord(ten[n])-128) div 2; hambam:=averange 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; dem:=dem+1; end else begin dem:=dem+1; p:=p^.next;
end; end; procedure nhap(var T:bangbam;item:elementtype); begin timkiem(T,item); if found=true then writeln('Item da co trong bang bam tai bang thu ',loc,'-',dem) else 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; begin khoitao(userT); 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. Bài 3: Phương pháp băm kép để xử lý va chạm được mô tả như sau. Nếu mục I va chạm với một mục khác trong bảng tại vị trí a, dùng hàm băm thu hai h2 cho mục ấy để xác định k=h2(i). Sau đó thực hiện như trong thăm dò tuyến tính , nhưng thay vì thử các vị trí liên tiếp ta thử các phần tử của bảng theo thứ tự a, a+k, a+2k,… được chia theo modun n (n: là kích thước bảng). Hãy chỉ ra bảng băm nhận được khi dùng các số ở bài tập 1, nhưng dùng phương pháp băm kép để giải quyết va chạm với hàm băm thứ cấp sau đây. 2i mod 11neui #0 H2(i)=  1neukhac
Để giải quyết bài toán trên ta xây dựng hai hàm băm h và h2. Nếu có va chạm xảy ra thì ta xác định giá trị khoá của phần tử nhập vào theo hàm băm h2 và dùng thăm dò tuyến tính để tìm được vị trí phù hợp của phần tử đó trong bảng băm theo cách đã nêu trong bài thay vì thử các vị trí liên tiếp ngay sau đó. Như vậy thủ tục tìm kiếm cũng sẽ hoạt động theo nguyên tắc trên. Chương trình cụ thể: program Dung_bam_kep_xu_ly_va_cham ; Var ch:char; bangbam:array[0..10] of string; function h( var x:string) :integer; var tong,j,dai:integer; Begin dai:=length(x); tong:=0; for j:=0 to dai-1 do tong:=tong+ ord(x[j]); h:= tong mod 11; end ; function h2(var x :string):integer; var tong,j,dai :integer; Begin dai:=length(x); tong:=0; for j:=0 to dai-1 do tong:=tong+2*ord(x[j]); h2:=tong mod 11 ;
end; procedure nhapchuoi; var i,nho:integer; a:string; begin for i:=0 to 10 do bangbam[i]:=''; i:=0; repeat writeln('nhap chuoi thu ',i+1); readln(a); if bangbam[h(a)]='' then begin bangbam[h(a)] :=a ; writeln('vi tri cua ',a,' trong bang bam la ',h(a)); end else if bangbam[h(a)]=a then begin repeat writeln('da co xau tren trong co so du lieu ! hay nhap lai'); readln(a); until bangbam[h(a)]=''; writeln('vi tri cua xau ',a, ' trong bang bam 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'); if bangbam[h2(a)]='' then begin
bangbam[h2(a)]:=a ; writeln('vi tri cua xau ',a,' trong bang bam sau khi su dung bam kep la ',h2(a)); end else begin nho:=h2(a); repeat nho:=nho+h2(a); until bangbam[nho]=''; bangbam[nho]:=a; writeln('vi tri cua ',a,' trong bang bam sau khi su ly va cham la ',nho); end; end; i:=i+1; until (i>11) or (a='thoat') ; writeln('ban da nhap duoc ',i-1,' chuoi'); end; procedure timkiem; var tk:string; i:integer; begin { bat dau thu tuc } writeln('nhap chuoi can tim'); readln(tk); writeln('gia tri bam cua chuoi tren la ',h(tk)); if bangbam[h(tk)]=tk then begin writeln('co chuoi ',tk,' trong co so du lieu '); writeln('vi tri cua ',tk,' trong bang bam la ',h(tk)); end
else if bangbam[h(tk)]='' then writeln('khong co chuoi ',tk,' trong co so du lieu') else if bangbam[h(tk)] tk then begin i:=h2(tk); repeat i:=i+h2(tk); until( bangbam[i]=tk) or (i>11); if bangbam[i]=tk then begin writeln('co chuoi ',tk,' trong co so du lieu'); writeln('vi tri cua ',tk,' trong bang bam la ',writeln('do co va cham xay ra nen gia tri bam cua chuoi tren khac voi vi tri cua no trong bang bam '); end ; if i>10 then writeln('khong co chuoi tren trong co so du lieu'); end; end; begin { CHUONG TRINH CHINH } writeln('ban hay nhap du lieu'); nhapchuoi; writeln('ban co muon tim kiem du lieu khong Y\N'); readln(ch); if( (ch='y') or( ch='Y')) then timkiem; readln; end.