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...
Nội dung trích xuất từ tài liệu:
PHÉP BIẾN ĐỔI KHÓA – HÀM BĂM part 3Để giải quyết va chạmChươ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ầucủ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 128những ưu điểm của phương pháp trên đã được đề cập đến trong bài 1. Tuy nhiên trongquá 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ựchiệ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 dobeginif bangbam[h(tk)]=tk thenbeginwriteln(co chuoi ,tk, trong co so du lieu );writeln(vi tri cua ,tk, trong bang bam la ,h(tk));endelseif bangbam[h(tk)]= thenwriteln(khong co chuoi ,tk, trong co so du lieu)elseif bangbam[h(tk)] tk thenbegini:=h(tk);repeati:=i+1;until( bangbam[i]=tk) or (i>10);if bangbam[i]=tk thenbeginwriteln(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 trongbang 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)] = thenbeginbangbam[h(a)]:=a ;writeln(chuoi ,a, duoc luu vao vi tri thu ,h(a), trong bang bam);endelseif bangbam[h(a)]=a thenbeginrepeatwriteln(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));endelseif bangbam[h(a)]a thenbeginvitri:=h(a);repeatvitri:=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 YN);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Ònprogram 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;varaverange: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;beginkhoitao(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ạmvới một mục khác trong b ...