Để 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 (p<>nil) 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 p<>nil 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.
H2(i)=



neukhac
neuii
1
0#11mod2



Để 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.