第15週プロジェクト1-検証アルゴリズム
3967 ワード
質問:
コード:
実行結果:
知識ポイントのまとめ:
ハッシュ表が適用されます.
/*
* Copyright (c)2015,
* All rights reserved.
* : 1.cbp
* :
* :2015 12 11
* :v1.0
* : , {16, 74, 60, 43, 54, 90, 46, 31, 29, 88, 77}
, 0.8, h(k)=key%p,p=11, 。 :
(1) ;
(2) 29 ;
(3) 77 , 。
* :
* :
*/
コード:
#include <stdio.h>
#define MaxSize 100 //
#define NULLKEY -1 //
#define DELKEY -2 //
typedef int KeyType; //
typedef char * InfoType; //
typedef struct
{
KeyType key; //
InfoType data; //
int count; //
} HashData;
typedef HashData HashTable[MaxSize]; //
void InsertHT(HashTable ha,int &n,KeyType k,int p) // k
{
int i,adr;
adr=k % p;
if (ha[adr].key==NULLKEY || ha[adr].key==DELKEY) //x[j]
{
ha[adr].key=k;
ha[adr].count=1;
}
else //
{
i=1; //i x[j]
do
{
adr=(adr+1) % p;
i++;
}
while (ha[adr].key!=NULLKEY && ha[adr].key!=DELKEY);
ha[adr].key=k;
ha[adr].count=i;
}
n++;
}
void CreateHT(HashTable ha,KeyType x[],int n,int m,int p) //
{
int i,n1=0;
for (i=0; i<m; i++) //
{
ha[i].key=NULLKEY;
ha[i].count=0;
}
for (i=0; i<n; i++)
InsertHT(ha,n1,x[i],p);
}
int SearchHT(HashTable ha,int p,KeyType k) // k
{
int i=0,adr;
adr=k % p;
while (ha[adr].key!=NULLKEY && ha[adr].key!=k)
{
i++; //
adr=(adr+1) % p;
}
if (ha[adr].key==k) //
return adr;
else //
return -1;
}
int DeleteHT(HashTable ha,int p,int k,int &n) // k
{
int adr;
adr=SearchHT(ha,p,k);
if (adr!=-1) //
{
ha[adr].key=DELKEY;
n--; // 1
return 1;
}
else //
return 0;
}
void DispHT(HashTable ha,int n,int m) //
{
float avg=0;
int i;
printf(" :\t");
for (i=0; i<m; i++)
printf(" %3d",i);
printf("
");
printf(" :\t");
for (i=0; i<m; i++)
if (ha[i].key==NULLKEY || ha[i].key==DELKEY)
printf(" "); // 3
else
printf(" %3d",ha[i].key);
printf("
");
printf(" :\t");
for (i=0; i<m; i++)
if (ha[i].key==NULLKEY || ha[i].key==DELKEY)
printf(" "); // 3
else
printf(" %3d",ha[i].count);
printf("
");
for (i=0; i<m; i++)
if (ha[i].key!=NULLKEY && ha[i].key!=DELKEY)
avg=avg+ha[i].count;
avg=avg/n;
printf(" ASL(%d)=%g
",n,avg);
}
int main()
{
int x[]= {16,74,60,43,54,90,46,31,29,88,77};
int n=11,m=13,p=13,i,k=29;
HashTable ha;
CreateHT(ha,x,n,m,p);
printf("
");
DispHT(ha,n,m);
i=SearchHT(ha,p,k);
if (i!=-1)
printf(" ha[%d].key=%d
",i,k);
else
printf(" %d
",k);
k=77;
printf(" %d
",k);
DeleteHT(ha,p,k,n);
DispHT(ha,n,m);
i=SearchHT(ha,p,k);
if (i!=-1)
printf(" ha[%d].key=%d
",i,k);
else
printf(" %d
",k);
printf(" %d
",k);
InsertHT(ha,n,k,p);
DispHT(ha,n,m);
printf("
");
return 0;
}
実行結果:
知識ポイントのまとめ:
ハッシュ表が適用されます.