c语言哈希函数

1. 数据结构 哈希表，c语言解答

#include <stdio.h>
#include<malloc.h>
#include<string.h>
//#include
#define HASH_LEN 50 //哈希表的长度
#define M 47
#define NAME_NO 30 //人名的个数
typedef struct NAME
{
char *py; //名字的拼音
int k; //拼音所对应的整数
}NAME;
NAME NameList[HASH_LEN];

typedef struct hterm //哈希表
{
char *py; //名字的拼音
int k; //拼音所对应的整数
int si; //查找长度
}HASH;
HASH HashList[HASH_LEN];
/*-----------------------姓名（结构体数组）初始化---------------------------------*/
void InitNameList()
{ int i;
char *f;
int r,s0;
NameList[0].py="chenghongxiu";
NameList[1].py="yuanhao";
NameList[2].py="yangyang";
NameList[3].py="zhanghen";
NameList[4].py="chenghongxiu";
NameList[5].py="xiaokai";
NameList[6].py="liupeng";
NameList[7].py="shenyonghai";
NameList[8].py="chengquan";
NameList[9].py="luqing";
NameList[10].py="gongyunxiang";
NameList[11].py="sunzhenxing";
NameList[12].py="sunrongfei";
NameList[13].py="sunminglong";
NameList[14].py="zhanghao";
NameList[15].py="tianmiao";
NameList[16].py="yaojianzhong";
NameList[17].py="yaojianqing";
NameList[18].py="yaojianhua";
NameList[19].py="yaohaifeng";
NameList[20].py="chengyanhao";
NameList[21].py="yaoqiufeng";
NameList[22].py="qianpengcheng";
NameList[23].py="yaohaifeng";
NameList[24].py="bianyan";
NameList[25].py="linglei";
NameList[26].py="fuzhonghui";
NameList[27].py="huanhaiyan";
NameList[28].py="liudianqin";
NameList[29].py="wangbinnian";

for (i=0;i<NAME_NO;i++)// *求出各个姓名的拼音所对应的整数
{
s0=0;
f=NameList[i].py;

for (r=0;*(f+r) != '\0';r++) //方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字
s0=*(f+r)+s0;

NameList[i].k=s0;
}
}
/*-----------------------建立哈希表---------------------------------*/
void CreateHashList()
{int i;
for ( i=0; i<HASH_LEN;i++)//哈希表的初始化
{
HashList[i].py="";
HashList[i].k=0;
HashList[i].si=0;
}

for (i=0; i<NAME_NO;)
{
int sum=0;
int adr=(NameList[i].k) % M; //哈希函数
int d=adr;
if(HashList[adr].si==0) //如果不冲突
{
HashList[adr].k=NameList[i].k;
HashList[adr].py=NameList[i].py;
HashList[adr].si=1;
}
else //冲突
{
do
{
d=(d+((NameList[i].k))%10+1)%M; //伪散列
sum=sum+1; //查找次数加1
}while (HashList[d].k!=0);

HashList[d].k=NameList[i].k;
HashList[d].py=NameList[i].py;
HashList[d].si=sum+1;
}i++;
}
}

/*-------------------------------------查找------------------------------------*/
void FindList()
{ int r;
char name[20]={0};
int s0=0;
int sum=1;
int adr;
int d;
printf("\n\n请输入姓名的拼音: "); //输入姓名
scanf("%s",name);

for ( r=0;r<20;r++) //求出姓名的拼音所对应的整数(关键字)
s0+=name[r];

adr=s0 % M; //使用哈希函数
d=adr;

if(HashList[adr].k==s0) //分3种情况进行判断
printf("\n姓名:%s 关键字:%d 查找长度为: 1",HashList[d].py,s0);
else if (HashList[adr].k==0)
printf("无该记录!");
else
{
int g=0;
do
{
d=(d+s0%10+1)%M; //伪散列
sum=sum+1;
if (HashList[d].k==0)
{
printf("无记录! ");
g=1;
}
if (HashList[d].k==s0)
{
printf("\n姓名:%s 关键字:%d 查找长度为:%d",HashList[d].py,s0,sum);
g=1;
}
}while(g==0);
}
}

/*--------------------------------显示哈希表----------------------------*/
void Display()
{int i;
float average=0;
printf("\n\n地址\t关键字\t\t搜索长度\tH(key)\t\t拼音 \n"); //显示的格式
for( i=0; i<15; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}
// printf("按任意键继续显示...\n"); //由于数据比较多，所以分屏显示（以便在Win9x／DOS下能看到所有的数据）
// getch();
for( i=15; i<30; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}
// printf("按任意键继续显示...\n");
// getch();
for( i=30; i<40; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}
//printf("按任意键继续显示...\n");
//getch();
for( i=40; i<50; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}

for (i=0;i<HASH_LEN;i++)
{average+=HashList[i].si;
average/=NAME_NO;
printf("\n\n平均查找长度：ASL(%d)=%f \n\n",NAME_NO,average);
}
}
/*--------------------------------主函数----------------------------*/
void main()
{
/* ::SetConsoleTitle("哈希表操作"); //Windows API函数,设置控制台窗口的标题
HANDLE hCon = ::GetStdHandle(STD_OUTPUT_HANDLE); //获得标准输出设备的句柄
::SetConsoleTextAttribute(hCon, 10|0); //设置文本颜色
*/
printf("\n------------------------哈希表的建立和查找----------------------");
InitNameList();
CreateHashList ();

while(1)
{ char ch1;
printf("\n\n");
printf(" 1. 显示哈希表\n");
printf(" 2. 查找\n");
printf(" 3. 退出\n");

err:

scanf("%c",&ch1);
if (ch1=='1')
Display();
else if (ch1=='2')
FindList();
else if (ch1=='3')
return;
else
{
printf("\n请输入正确的选择!");
goto err;
}
}
}

2. c语言数据结构（考题，测试你的能力）－－编写源代码

P88 稀疏矩阵十字链表相加算法如下：
/*假设ha为A稀疏矩阵十字链表的头指针，hb为B稀疏矩阵十字链表的头指针*/
#include<stdio.h>
#define maxsize 100
struct linknode
{ int i,j;
struct linknode *cptr,*rptr;
union vnext
{ int v;
struct linknode *next;} k;
};

struct linknode creatlindmat( ) /*建立十字链表*/
{ int x, m, n, t, s, i, j, k;
struct linknode *p , *q, *cp[maxsize],*hm;
printf("请输入稀疏矩阵的行、列数及非零元个数\n");
scanf("%d%d%d",&m,&n,&t);
if (m>n) s=m; else s=n;
hm=(struct linknode*)malloc(sizeof(struct linknode)) ;
hm->i=m; hm->j=n;
cp[0]=hm;
for (i=1; i<=s;i++)
{ p=(struct linknode*)malloc(sizeof(struct linknode)) ;
p->i=0; p->j=0;
p->rptr=p; p->cptr=p;
cp[i]=p;
cp[i-1]->k.next=p;
}
cp[s]->k.next=hm;
for( x=1;x<=t;x++)
{ printf("请输入一个三元组(i,j,v)\n");
scanf("%d%d%d",&i,&j,&k);
p=(struct linknode*)malloc(sizeof(struct linknode));
p->i=i; p->j=j; p->k.v=k;
/*以下是将p插入到第i行链表中 */
q=cp[i];
while ((q->rptr!=cp[i]) &&( q->rptr->j<j))
q=q->rptr;
p->rptr=q->rptr;
q->rptr=p;
/*以下是将P插入到第j列链表中*/
q=cp[j];
while((q->cptr!=cp[j]) &&( q->cptr->i<i))
q=q->cptr;
p->cptr=q->cptr;
q->cptr=p;
}
return hm;
}
/* ha和hb表示的两个稀疏矩阵相加，相加的结果放入ha中*/
struct linknode *matadd(struct linknode *ha, struct linknode *hb)
{ struct linknode *pa, *pb, *qa, *ca,*cb,*p,*q;
struct linknode *hl[maxsize];
int i , j, n;
if((ha->i!=hb->i)||(ha->j!=hb->j))
printf("矩阵不匹配,不能相加\n");
else
{ p=ha->k.next; n=ha->j;
for (i=1;i<=n; i++)
{ hl[i]=p;
p=p->k.next;
}
ca=ha->k.next; cb=hb->k.next;
while(ca->i==0)
{pa=ca->rptr; pb=cb->rptr;
qa=ca;
while(pb->j!=0)
{ if((pa->j<pb->j)&&(pa->j!=0))
{ qa=pa; pa=pa->rptr;}
else if ((pa->j>pb->j)||(pa->j==0)) /*插入一个结点*/
{ p=(struct linknode*)malloc(sizeof(struct linknode));
p->i=pb->i; p->j=pb->j;
p->k.v=pb->k.v;
qa->rptr=p; p->rptr=pa;
qa=p; pb=pb->rptr;
j=p->j; q=hl[j]->cptr;
while((q->i<p->i)&&(q->i!=0))
{ hl[j]=q; q=hl[j]->cptr;}
hl[j]->cptr=p; p->cptr=q;
hl[j]=p;
}
else
{pa->k.v=pa->k.v+pb->k.v;
if(pa->k.v==0) /*删除一个结点*/
{ qa->rptr=pa->rptr;
j=pa->j; q=hl[j]->cptr;
while (q->i<pa->i)
{hl[j]=q; q=hl[j]->cptr;}
hl[j]->cptr=q->cptr;
pa=pa->rptr; pb=pb->rptr;
free(q);
}
else
{ qa=pa; pa=pa->rptr;
pb=pb->rptr;
}
}
}
ca=ca->k.next; cb=cb->k.next;
}
}
return ha;
}
void print(struct linknode *ha) /*输出十字链表*/
{ struct linknode *p,*q;
p=ha->k.next;
while(p->k.next!=ha)
{ q=p->rptr;
while(q->rptr!=p)
{ printf("%3d%3d%3d\t",q->i,q->j,q->k.v);
q=q->rptr;
}
if(p!=q)
printf("%3d%3d%3d",q->i,q->j,q->k.v);
printf("\n");
p=p->k.next;
}
q=p->rptr;
while(q->rptr!=p)
{ printf("%3d%3d%3d\t",q->i,q->j,q->k.v);
q=q->rptr;
}
if(p!=q)
printf("%3d%3d%3d",q->i,q->j,q->k.v);
printf("\n");
}

void main()
{
struct linknode *ha=NULL,*hb=NULL,*hc=NULL;
ha=creatlindmat( ); /*生成一个十字链表ha*/
hb=creatlindmat( ); /*生成另一个十字链表hb*/
printf("A:\n"); /*输出十字链表ha*/
print(ha);printf("\n");
printf("B:\n"); /*输出十字链表hb*/
print(hb);printf("\n");
hc=matadd(ha,hb); /*十字链表相加*/
printf("A+B:\n"); /*输出相加后的结果*/
print(hc);printf("\n");
}

P94 数据类型描述如下：
#define elemtype char
struct node1
{ int atom;
struct node1 *link;
union
{
struct node1 *slink;
elemtype data;
} ds;
}

P95 数据类型描述如下：
struct node2
{ elemtype data;
struct node2 *link1,*link2;
}

P96 求广义表的深度depth(LS)
int depth(struct node1 *LS)
{
int max=0,dep;
while(LS!=NULL)
{ if(LS->atom==0) //有子表
{ dep=depth(LS->ds.slink);
if(dep>max) max=dep;
}
LS=LS->link;
}
return max+1;
}

P96 广义表的建立creat(LS)
void creat(struct node1 *LS)
{
char ch;
scanf("%c",&ch);
if(ch=='#')
LS=NULL;
else if(ch=='(')
{LS=(struct node*)malloc(sizeof(struct node));
LS->atom=0;
creat(LS->ds.slink);
}
else
{ LS=(struct node*)malloc(sizeof(struct node));
LS->atom=1;
LS->ds.data=ch;
}
scanf("%c",&ch);
if(LS==NULL);
else if(ch==',')
creat(LS->link);
else if((ch==')')||(ch==';'))
LS->link=NULL;
}

P97 输出广义表print(LS)
void print(struct node1 *LS)
{
if(LS->atom==0)
{
printf("(");
if(LS->ds.slink==NULL)
printf("#");
else
print(LS->ds.slink);
}
else
printf("%c ",LS->ds.data);
if(LS->atom==0)
printf(")");
if(LS->link!=NULL)
{
printf(";");
print(LS->link);
}
}

P98 该算法的时间复杂度为O(n)。整个完整程序如下：
#include<stdio.h>
#define elemtype char
struct node1
{ int atom;
struct node1 *link;
union
{
struct node1 *slink;
elemtype data;
} ds;
};

void creat(struct node1 LS) /*建立广义表的单链表*/
{
char ch;
scanf("%c",&ch);
if(ch=='#')
LS=NULL;
else if(ch=='(')
{LS=(struct node1*)malloc(sizeof(struct node1));
LS->atom=0;
creat(LS->ds.slink);
}
else
{ LS=(struct node1*)malloc(sizeof(struct node1));
LS->atom=1;
LS->ds.data=ch;
}
scanf("%c",&ch);
if(LS==NULL);
else if(ch==',')
creat(LS->link);
else if((ch==')')||(ch==';'))
LS->link=NULL;
}
void print(struct node1 LS) /*输出广义单链表*/
{
if(LS->atom==0)
{
printf("(");
if(LS->ds.slink==NULL)
printf("#");
else
print(LS->ds.slink);
}
else
printf("%c",LS->ds.data);
if(LS->atom==0)
printf(")");
if(LS->link!=NULL)
{
printf(";");
print(LS->link);
}
}
int depth(struct node1 LS) /*求广义表的深度*/
{
int max=0;
while(LS!=NULL)
{ if(LS->atom==0)
{ int dep=depth(LS->ds.slink);
if(dep>max) max=dep;
}
LS=LS->link;
}
return max+1;
}
main()
{ int dep;
struct node1 *p=NULL;
creat(p); /*建立广义表的单链表*/
print(p); /*输出广义单链表*/
dep=depth(p); /*求广义表的深度*/
printf("%d\n",dep);
}

第六章 树
P109 二叉链表的结点类型定义如下：
typedef struct btnode
{ anytype data;
struct btnode *Lch,*Rch;
}tnodetype;

P109 三叉链表的结点类型定义如下：
typedef struct btnode3
{ anytype data;
struct btnode *Lch,*Rch，*Parent ;
}tnodetype3;

P112 C语言的先序遍历算法：
void preorder (tnodetype *t)
/*先序遍历二叉树算法，t为指向根结点的指针*/
{ if (t!=NULL)
{printf("%d ",t->data);
preorder(t->lch);
preorder(t->rch);
}
}

P113 C语言的中序遍历算法：
void inorder(tnodetype *t)
/*中序遍历二叉树算法，t为指向根结点的指针*/
{
if(t!=NULL)
{inorder(t->lch);
printf("%d ",t->data);
inorder(t->rch);
}
}

P113 C语言的后序遍历算法：
void postorder(tnodetype *t)
/*后序遍历二叉树算法，t为指向根结点的指针*/
{
if(t!=NULL)
{ postorder(t->lch);
postorder(t->rch);
printf("%d ",t->data);
}
}

P114 如果引入队列作为辅助存储工具，按层次遍历二叉树的算法可描述如下：
void levelorder(tnodetype *t)
/*按层次遍历二叉树算法，t为指向根结点的指针*/
{tnodetype q[20]; /*辅助队列*/
front=0;
rear=0; /*置空队列*/
if (t!=NULL)
{ rear++;
q[rear]=t; /*根结点入队*/
}
while (front!=rear)
{ front++;
t=q [front];
printf ("%c\n",t->data);
if (t->lch!=NULL) /*t的左孩子不空，则入队*/
{ rear++;
q [rear]=t->lch;
}
if (t->rch!=NULL) /*t的右孩子不空，则入队*/
{ rear++;
q [rear]=t->rch;
}
}
}

P115 以中序遍历的方法统计二叉树中的结点数和叶子结点数，算法描述为：
void inordercount (tnodetype *t)
/*中序遍历二叉树，统计树中的结点数和叶子结点数*/
{ if (t!=NULL)
{ inordercount (t->lch); /*中序遍历左子树*/
printf ("%c\n",t->data); /*访问根结点*/
countnode++; /*结点计数*/
if ((t->lch==NULL)&&(t->rch==NULL))
countleaf++; /*叶子结点计数*/
inordercount (t->rch); /*中序遍历右子树*/
}
}

P115 可按如下方法计算一棵二叉树的深度：
void preorderdeep (tnodetype *t,int j)
/*先序遍历二叉树，并计算二叉树的深度*/
{ if (t!=NULL)
{ printf ("%c\n",t->data); /*访问根结点*/
j++;
if (k<j) k=j;
preorderdeep (t->lch,j); /*先序遍历左子树*/
preorderdeep (t->rch,j); /*先序遍历右子树*/
}
}

P117 线索二叉树的结点类型定义如下：
struct nodexs
{anytype data;
struct nodexs *lch, *rch;
int ltag,rtag; /*左、右标志域*/
}

P117 中序次序线索化算法
void inorderxs (struct nodexs *t)
/*中序遍历t所指向的二叉树，并为结点建立线索*/
{ if (t!=NULL)
{ inorderxs (t->lch);
printf ("%c\n",t->data);
if (t->lch!=NULL)
t->ltag=0;
else { t->ltag=1;
t->lch=pr;
} /*建立t所指向结点的左线索，令其指向前驱结点pr*/
if (pr!=NULL)
{ if (pr->rch!=NULL)
pr->rtag=0;
else { pr->rtag=1;
pr->rch=p;
}
} /*建立pr所指向结点的右线索，令其指向后继结点p*/
pr=p;
inorderxs (t->rch);
}
}

P118 在中根线索树上检索某结点的前驱结点的算法描述如下：
struct nodexs * inpre (struct nodexs *q)
/*在中根线索树上检索q所指向的结点的前驱结点*/
{ if (q->ltag==1)
p=q->lch;
else { r=q->lch;
while (r->rtag!=1)
r=r->rch;
p=r;
}
return (p);
}

P119 在中根线索树上检索某结点的后继结点的算法描述如下：
struct nodexs * insucc (struct nodexs *q)
/*在中根线索树上检索q所指向的结点的后继结点*/
{ if (q->rtag==1)
p=q->rch;
else { r=q->rch;
while (r->ltag!=1)
r=r->lch;
p=r;
}
return (p);
}

P120 算法程序用C语言描述如下：
void sortBT(BT *t,BT *s) /*将指针s所指的结点插入到以t为根指针的二叉树中*/
{ if (t==NULL) t=s; /*若t所指为空树，s所指结点为根*/
else if (s->data < t->data)
sortBT(t->lch,s); /*s结点插入到t的左子树上去*/
else
sortBT(t->rch,s); /*s结点插入到t的右子树上去*/
}

P121 二叉排序树结点删除算法的C语言描述如下：
void delnode(bt,f,p)
/*bt为一棵二叉排序树的根指针，p指向被删除结点，f指向其双亲*/
/*当p=bt时f为NULL*/
{ fag=0; /*fag=0时需修改f指针信息，fag=1时不需修改*/
if (p->lch==NULL)
s=p->rch; /*被删除结点为叶子或其左子树为空*/
else if (p->rch==NULL)
s=p->lch;
else { q=p; /*被删除结点的左、右子树均非空*/
s=p->lch;
while (s->rch!=NULL)
{ q=s;
s=s->rch;
} /*寻找s结点*/
if (q=p)
q->lch=s->lch;
else q->rch=s->lch;
p->data=s->data; /*s所指向的结点代替被删除结点*/
DISPOSE(s);
Fag=1;
}
if (fag=0) /*需要修改双亲指针*/
{ if (f=NULL)
bt=s; /*被删除结点为根结点*/
else if (f->lch=p)
f->lch=s;
else f->rch=s;
DISPOSE(p); /*释放被删除结点*/
}
}

第七章 图
P134 用邻接矩阵表示法表示图，除了存储用于表示顶点间相邻关系的邻接矩阵外，通常还需要用一个顺序表来存储顶点信息。其形式说明如下：
# define n 6 /*图的顶点数*/
# define e 8 /*图的边(弧)数*/
typedef char vextype; /*顶点的数据类型*/
typedef float adjtype; /*权值类型*/
typedef struct
{vextype vexs[n];
adjtype arcs[n][n];
}graph;

P135 建立一个无向网络的算法。
CREATGRAPH(ga) /*建立无向网络*/
Graph * ga;
{
int i,j,k;
float w;
for(i＝0;i<n;i++ )
ga ->vexs[i]＝getchar(); /*读入顶点信息，建立顶点表*/
for(i＝0;i<n;i++ )
for(j＝0;j<n;j++)
ga ->arcs[i][j]＝0; /*邻接矩阵初始化*/
for(k＝0;k<e;k++) /*读入e条边*/
(scanf("％d％d％f",&I,&j,&w); /*读入边(vi,vj)上的权w */
ga ->arcs[i][j]＝w;
ga - >arcs[j][i]＝w;
}
} /*CREATGRAPH*/

P136 邻接表的形式说明及其建立算法：
typedef struct node
{int adjvex; /*邻接点域*/
struct node * next; /*链域*/
}edgenode; /*边表结点*/
typedef struct
{vextype vertex; /*顶点信息*/
edgenode link; /*边表头指针*/
}vexnode; /*顶点表结点*/
vexnode ga[n];

CREATADJLIST(ga) /*建立无向图的邻接表*/
Vexnode ga[ ];
{int i,j,k;
edgenode * s;
for(i=o;i<n;i++＝ /*读入顶点信息*/
(ga[i].vertex＝getchar();
ga[i].1ink＝NULL; /*边表头指针初始化*/
}
for(k＝0;k<e;k++＝ /*建立边表*/
{scanf("％d％d",&i,&j); /*读入边(vi , vj)的顶点对序号*/
s＝malloc(sizeof(edgenode)); /*生成邻接点序号为j的表结点*s */
s-> adjvex＝j;
s- - >next：＝ga[i].Link;
ga[i].1ink＝s; /*将*s插入顶点vi的边表头部*/
s＝malloc(size0f(edgende)); /*生成邻接点序号为i的边表结点*s */
s ->adjvex＝i;
s ->next＝ga[j].1ink;
ga[j].1ink＝s; /*将*s插入顶点vj的边表头部*/
}
} /* CREATADJLIST */

P139 分别以邻接矩阵和邻接表作为图的存储结构给出具体算法，算法中g、g1和visited为全程量，visited的各分量初始值均为FALSE。
int visited[n] /*定义布尔向量visitd为全程量*/
Graph g; /*图g为全程量*/

DFS(i) /*从Vi+1出发深度优先搜索图g，g用邻接矩阵表示*/
int i;
{ int j;
printf("node：％c＼n" , g.vexs[i]); /*访问出发点vi+1 */
Visited[i]＝TRUE; /*标记vi+l已访问过*/
for (j＝0;j<n;j++) /*依次搜索vi+1的邻接点*/
if((g.arcs[i][j]＝＝1) ＆＆(! visited[j]))
DFS(j); /*若Vi+l的邻接点vj+l未曾访问过，则从vj+l出发进行深度优先搜索*/
} /*DFS*/
vexnode gl[n] /*邻接表全程量*/

DFSL(i) /*从vi+l出发深度优先搜索图g1，g1用邻接表表示*/
int i;
{ int j;
edgenode * p;
printf("node：％C\n" ,g1[i].vertex);
vistited[i]＝TRUE;
p＝g1[i].1ink; /*取vi+1的边表头指针*/
while(p !＝NULL) /*依次搜索vi+l的邻接点*/
{
if(! Vistited[p ->adjvex])
DFSL(p - >adjvex); /*从vi+1的未曾访问过的邻接点出发进行深度优先搜索*/
p＝p - >next; /*找vi+l的下一个邻接点*/
}
} /* DFSL */

P142 以邻接矩阵和邻接表作为图的存储结构，分别给出宽度优先搜索算法。
BFS(k) /＊从vk+l出发宽度优先搜索图g，g用邻接矩阵表示，visited为访问标志向量*/
int k;
{ int i,j;
SETNULL(Q); /*置空队Q */
printf("％c＼n"，g.vexs[k]); /*访问出发点vk+l*x/
visited[k]＝TRUE; /*标记vk+l已访问过*/
ENQUEUE(Q，K); /*已访问过的顶点(序号)入队列*/
While(!EMPTY(Q)) /*队非空时执行*/
{i＝DEQUEUE(Q); /*队头元素序号出队列*/
for(j＝0;j<n;j++)
if((g.arcs[i][j]＝＝1)＆＆(! visited[j]))
{printf("％c＼n" , g.vexs[j]); /*访问vi+l的未曾访问的邻接点vj+l */
visited[j]＝TRUE;
ENQUEUE(Q,j); /*访问过的顶点入队*/
}
}
} /* BFS */
BFSL(k) /*从vk+l出发宽度优先搜索图g1，g1用邻接表表示*/
int k
{ int i;
edgenode * p;
SETNULL(Q);
printf("％c＼n" , g1[k].vertex);
visited[k]＝TRUE;
ENQUEUE(Q,k);
while(! EMPTY(Q));
{ i＝DEQUEUE(Q);
p＝g1[i].1ink /*取vi+l的边表头指针*/
while(p !＝NULL) /*依次搜索vi+l的邻接点*/
{ if( ! visited[p - >adjvex]) /*访问vi+l的未访问的邻接点*/
{ printf{"％c＼n" , g1[p - >adjvex].vertex};
visited[p - >adjvex]＝TRUE;
ENQUEUE(Q,p - >adjvex); /*访问过的顶点入队*/
}
p＝p - >next; /*找vi+l的下一个邻接点*/
}
}
} /*BFSL*/

P148 在对算法Prim求精之前，先确定有关的存储结构如下：
typdef struct
{Int fromvex，endvex; /*边的起点和终点*/
float length; /*边的权值*/
} edge;

float dist[n][n]; /*连通网络的带权邻接矩阵*/
edgeT[n-1]; /*生成树*/

P149 抽象语句(1)可求精为：
for(j=1;j<n;j++) /*对n-1个蓝点构造候选紫边集*/
{T[j-1].fromvex＝1}; /*紫边的起点为红点*/
T[j-1].endvex＝j+1; /*紫边的终点为蓝点*/
T[j-1].1ength＝dist[0][j]; /*紫边长度*/
}

P149 抽象语句(3)所求的第k条最短紫边可求精为：
min＝max; /*znax大于任何边上的权值*/
for (j＝k;j<n-1;j++) /*扫描当前候选紫边集T[k]到T[n-2]，找最短紫边*/
if(T[j].1ength<min)
{min＝T[j].1ength;m＝j; /*记录当前最短紫边的位置*/
}

P149 抽象语句(4)的求精：
e＝T[m];T[m]＝T[k];T[k]＝e， /* T[k]和T[m]交换*/
v＝T[kl.Endvex]; /* v是刚被涂红色的顶点*/

P149 抽象语句(5)可求精为：
for(j＝k+1;j<n-1;j++) /*调整候选紫边集T[k+1]到T[n-2]*/
{d＝dist[v-1][T[j].endvex-1]; /*新紫边的长度*/
if(d<T[j].1ength) /*新紫边的长度小于原最短紫边*/
{T[j].1ength＝d;
T[j].fromvex＝v; /*新紫边取代原最短紫边*/
}
}

P150 完整的算法：
PRIM() /*从第一个顶点出发构造连通网络dist的最小生成树，结果放在T中*/
{int j , k , m , v , min , max＝l0000;
float d;
edge e;
for(j=1;j<n;j++) /*构造初始候选紫边集*/
{T[j-1].formvex＝1; /*顶点1是第一个加入树中的红点*/
T[j-1].endvex＝j+1;
T[j-1].length＝dist[o][j];
}
for(k＝0;k<n-1;k++) /*求第k条边*/
{min＝max;
for(j＝k;j<n-1;j++) /*在候选紫边集中找最短紫边*/
if(T[j].1ength<min)
{min＝T[j].1ength;
m＝j;
} /*T[m]是当前最短紫边*/
}
e＝T[m];T[m]＝T[k];T[k]＝e; /*T[k]和T[m]交换后，T[k]是第k条红色树边*/
v＝T[k].endvex ; /* v是新红点*/
for(j＝k+1;j<n-1;j++) /*调整候选紫边集*/
{d＝dist[v-1][T[j].endvex-1];
if(d<T[j].1ength);
{T[j].1ength＝d;
T[j].fromvex＝v;
}
}
} /* PRIM */

P151 Kruskl算法的粗略描述：
T＝(V,φ);
While(T中所含边数<n-1)
{从E中选取当前最短边(u,v);
从E中删去边(u,v);
if((u,v)并入T之后不产生回路，将边(u,v)并入T中;
}

P153 迪杰斯特拉算法实现。算法描述如下：
#define max 32767 /*max代表一个很大的数*/
void dijkstra (float cost[][n],int v)
/*求源点v到其余顶点的最短路径及其长度*/
{ v1=v-1;
for (i=0;i<n;i++)
{ dist[i]=cost[v1][i]; /*初始化dist*/
if (dist[i]<max)
pre[i]=v;
else pre[i]=0;
}
pre[v1]=0;
for (i=0;i<n;i++)
s[i]=0; /*s数组初始化为空*/
s[v1]=1; /*将源点v归入s集合*/
for (i=0;i<n;i++)
{ min=max;
for (j=0;j<n;j++)
if (!s[j] && (dist[j]<min))
{ min=dist[j];
k=j;
} /*选择dist值最小的顶点k+1*/
s[k]=1; /*将顶点k+1归入s集合中*/
for (j=0;j<n;j++)
if (!s[j]&&(dist[j]>dist[k]+cost[k][j]))
{ dist[j]=dist[k]+cost[k][j]; /*修改 V-S集合中各顶点的dist值*/
pre[j]=k+1; /*k+1顶点是j+1顶点的前驱*/
}
} /*所有顶点均已加入到S集合中*/
for (j=0;j<n;j++) /*打印结果*/
{ printf("%f\n%d",dist[j],j+1;);
p=pre[j];
while (p!=0)
{ printf("%d",p);
p=pre[p-1];
}
}
}

P155 弗洛伊德算法可以描述为：
A(0)[i][j]=cost[i][j]; //cost为图的邻接矩阵
A(k)[i][j]=min{A(k-1) [i][j],A(k-1) [i][k]+A(k-1) [k][j]}
其中 k=1,2,…,n

P155 弗洛伊德算法实现。算法描述如下：
int path[n][n]; /*路径矩阵*/
void floyd (float A[][n],cost[][n])
{ for (i=0;i<n;i++) /*设置A和path的初值*/
for (j=0;j<n;j++)
{ if (cost[i][j]<max)
path[i][j]=j;
else { path[i][j]=0;
A[i][j]=cost[i][j];
}
}
for (k=0;k<n;k++)
/*做n次迭代，每次均试图将顶点k扩充到当前求得的从i到j的最短路径上*/
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (A[i][j]>(A[i][k]+A[k]

3. C语言实现哈希表的相关运算算法 编写程序实现哈希表的构造过程。

#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,

4. C语言中的hash函数

Hash，一般翻译做"散列"，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
HASH主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码里，叫做HASH值. 也可以说，hash就是找到一种数据内容和数据存放地址之间的映射关系。Hash算法在信息安全方面的应用主要体现在以下的3个方面：文件校验、数字签名、鉴权协议
程程序实现
// 说明：Hash函数（即散列函数）在程序设计中的应用目标 ------ 把一个对象通过某种转换机制对应到一个
//size_t类型（即unsigned long）的整型值。
// 而应用Hash函数的领域主要是 hash表（应用非常广）、密码等领域。
// 实现说明：
// ⑴、这里使用了函数对象以及泛型技术，使得对所有类型的对象（关键字）都适用。
// ⑵、常用类型有对应的偏特化，比如string、char*、各种整形等。
// ⑶、版本可扩展，如果你对某种类型有特殊的需要，可以在后面实现专门化。
// ⑷、以下实现一般放在头文件中，任何包含它的都可使用hash函数对象。
//------------------------------------实现------------------------------------------------
#include <string>
using std::string;
inlinesize_thash_str(const char* s)
{
unsigned long res = 0;
for (; *s; ++s)
res = 5 * res + *s;
returnsize_t(res);
}
template <class Key>
struct hash
{
size_toperator () (const Key& k) const;
};
// 一般的对象，比如：vector< queue<string> >；的对象，需要强制转化
template < class Key >
size_thash<Key>::operator () (const Key& k) const
{
size_tres = 0;
size_tlen = sizeof(Key);
const char* p = reinterpret_cast<const char*>(&k);
while (len--)
{
res = (res<<1）^*p++;
}
return res;
}
// 偏特化
template<>
size_thash< string >::operator () (const string& str) const
{
return hash_str(str.c_str());
}
typedef char* PChar;
template<>
size_thash<PChar>::operator () (const PChar& s) const
{
return hash_str(s);
}
typedef const char* PCChar;
template<>
size_thash<PCChar>::operator () (const PCChar& s) const
{
return hash_str(s);
}
template<> size_t hash<char>::operator () (const char& x) const { return x; }
template<> size_t hash<unsigned char>::operator () (const unsigned char& x) const { return x; }
template<> size_t hash<signed char>::operator () (const signed char& x) const { return x; }
template<> size_t hash<short>::operator () (const short& x) const { return x; }
template<> size_t hash<unsigned short>::operator () (const unsigned short& x) const { return x; }
template<> size_t hash<int>::operator () (const int& x) const { return x; }
template<> size_t hash<unsigned int>::operator () (const unsigned int& x) const { return x; }
template<> size_t hash<long>::operator () (const long& x) const { return x; }
template<> size_t hash<unsigned long>::operator () (const unsigned long& x) const { return x; }
// 使用说明：
//
// ⑴、使用时首先由于是泛型，所以要加上关键字类型。
//
// ⑵、其次要有一个函数对象，可以临时、局部、全局的，只要在作用域就可以。
//
// ⑶、应用函数对象作用于对应类型的对象。
//----------------------- hash函数使用举例 -------------------------
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main()
{
vector<string> vstr⑵；
vstr[0] = "sjw";
vstr[1] = "suninf";
hash<string> strhash; // 局部函数对象
cout << " Hash value: " << strhash(vstr[0]) << endl;
cout << " Hash value: " << strhash(vstr[1]) << endl;
cout << " Hash value: " << hash< vector<string> >() (vstr) << endl;
cout << " Hash value: " << hash<int>() （100） << endl; // hash<int>() 临时函数对象
return 0;
}

5. C语言版数据结构哈希算法题：设m=16,HASH函数为H（key）=key mod 13,现采用再哈希法Hi=RHi(key）处理冲突

应该是这个意思：
第一次冲突就是散列的位置+1，这次发生冲突了就继续第二次
第二次用的是平方取中，55^2= 3025，当然第二次冲突的RH2就是02了，答案(2)

6. 如何使用C语言获取文件的SHA1哈希值

有现成的SHA1算法函数

复制过来。

然后打开文件， 读数据森庆谨， 调用SHA1函数即可。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<errno.h>

#undefBIG_ENDIAN_HOST
typedefunsignedintu32;

/****************
*Rotatea32此基bitintegerbynbytes
*/
#ifdefined(__GNUC__)&&defined(__i386__)
staticinlineu32
	rol(u32x,intn)
{
	__asm__("roll%%cl,%0"
		:"=r"(x)
		:"0"(x),"c"(n));
	returnx;
}
#else
#definerol(x,n)(((x)<<(n))|((x)>>(32-(n))))
#endif


typedefstruct{
	u32h0,h1,h2,h3,h4;
	u32nblocks;
	unsignedcharbuf[64];
	intcount;
}SHA1_CONTEXT;void
	sha1_init(SHA1_CONTEXT差橘*hd)
{
	hd->h0=0x67452301;
	hd->h1=0xefcdab89;
	hd->h2=0x98badcfe;
	hd->h3=0x10325476;
	hd->h4=0xc3d2e1f0;
	hd->nblocks=0;
	hd->count=0;
}


/****************
*-bit-words
*/
staticvoid
	transform(SHA1_CONTEXT*hd,unsignedchar*data)
{
	u32a,b,c,d,e,tm;
	u32x[16];

	/*getvaluesfromthechainingvars*/
	a=hd->h0;
	b=hd->h1;
	c=hd->h2;
	d=hd->h3;
	e=hd->h4;

#ifdefBIG_ENDIAN_HOST
	memcpy(x,data,64);
#else
	{
		inti;
		unsignedchar*p2;
		for(i=0,p2=(unsignedchar*)x;i<16;i++,p2+=4)
		{
			p2[3]=*data++;
			p2[2]=*data++;
			p2[1]=*data++;
			p2[0]=*data++;
		}
	}
#endif


#defineK10x5A827999L
#defineK20x6ED9EBA1L
#defineK30x8F1BBCDCL
#defineK40xCA62C1D6L
#defineF1(x,y,z)(z^(x&(y^z)))
#defineF2(x,y,z)(x^y^z)
#defineF3(x,y,z)((x&y)|(z&(x|y)))
#defineF4(x,y,z)(x^y^z)


#defineM(i)(tm=x[i&0x0f]^x[(i-14)&0x0f]
	^x[(i-8)&0x0f]^x[(i-3)&0x0f]
	,(x[i&0x0f]=rol(tm,1)))

#defineR(a,b,c,d,e,f,k,m)do{e+=rol(a,5)
	+f(b,c,d)
	+k	
	+m;	
	b=rol(b,30);
	}while(0)
	R(a,b,c,d,e,F1,K1,x[0]);
	R(e,a,b,c,d,F1,K1,x[1]);
	R(d,e,a,b,c,F1,K1,x[2]);
	R(c,d,e,a,b,F1,K1,x[3]);
	R(b,c,d,e,a,F1,K1,x[4]);
	R(a,b,c,d,e,F1,K1,x[5]);
	R(e,a,b,c,d,F1,K1,x[6]);
	R(d,e,a,b,c,F1,K1,x[7]);
	R(c,d,e,a,b,F1,K1,x[8]);
	R(b,c,d,e,a,F1,K1,x[9]);
	R(a,b,c,d,e,F1,K1,x[10]);
	R(e,a,b,c,d,F1,K1,x[11]);
	R(d,e,a,b,c,F1,K1,x[12]);
	R(c,d,e,a,b,F1,K1,x[13]);
	R(b,c,d,e,a,F1,K1,x[14]);
	R(a,b,c,d,e,F1,K1,x[15]);
	R(e,a,b,c,d,F1,K1,M(16));
	R(d,e,a,b,c,F1,K1,M(17));
	R(c,d,e,a,b,F1,K1,M(18));
	R(b,c,d,e,a,F1,K1,M(19));
	R(a,b,c,d,e,F2,K2,M(20));
	R(e,a,b,c,d,F2,K2,M(21));
	R(d,e,a,b,c,F2,K2,M(22));
	R(c,d,e,a,b,F2,K2,M(23));
	R(b,c,d,e,a,F2,K2,M(24));
	R(a,b,c,d,e,F2,K2,M(25));
	R(e,a,b,c,d,F2,K2,M(26));
	R(d,e,a,b,c,F2,K2,M(27));
	R(c,d,e,a,b,F2,K2,M(28));
	R(b,c,d,e,a,F2,K2,M(29));
	R(a,b,c,d,e,F2,K2,M(30));
	R(e,a,b,c,d,F2,K2,M(31));
	R(d,e,a,b,c,F2,K2,M(32));
	R(c,d,e,a,b,F2,K2,M(33));
	R(b,c,d,e,a,F2,K2,M(34));
	R(a,b,c,d,e,F2,K2,M(35));
	R(e,a,b,c,d,F2,K2,M(36));
	R(d,e,a,b,c,F2,K2,M(37));
	R(c,d,e,a,b,F2,K2,M(38));
	R(b,c,d,e,a,F2,K2,M(39));
	R(a,b,c,d,e,F3,K3,M(40));
	R(e,a,b,c,d,F3,K3,M(41));
	R(d,e,a,b,c,F3,K3,M(42));
	R(c,d,e,a,b,F3,K3,M(43));
	R(b,c,d,e,a,F3,K3,M(44));
	R(a,b,c,d,e,F3,K3,M(45));
	R(e,a,b,c,d,F3,K3,M(46));
	R(d,e,a,b,c,F3,K3,M(47));
	R(c,d,e,a,b,F3,K3,M(48));
	R(b,c,d,e,a,F3,K3,M(49));
	R(a,b,c,d,e,F3,K3,M(50));
	R(e,a,b,c,d,F3,K3,M(51));
	R(d,e,a,b,c,F3,K3,M(52));
	R(c,d,e,a,b,F3,K3,M(53));
	R(b,c,d,e,a,F3,K3,M(54));
	R(a,b,c,d,e,F3,K3,M(55));
	R(e,a,b,c,d,F3,K3,M(56));
	R(d,e,a,b,c,F3,K3,M(57));
	R(c,d,e,a,b,F3,K3,M(58));
	R(b,c,d,e,a,F3,K3,M(59));
	R(a,b,c,d,e,F4,K4,M(60));
	R(e,a,b,c,d,F4,K4,M(61));
	R(d,e,a,b,c,F4,K4,M(62));
	R(c,d,e,a,b,F4,K4,M(63));
	R(b,c,d,e,a,F4,K4,M(64));
	R(a,b,c,d,e,F4,K4,M(65));
	R(e,a,b,c,d,F4,K4,M(66));
	R(d,e,a,b,c,F4,K4,M(67));
	R(c,d,e,a,b,F4,K4,M(68));
	R(b,c,d,e,a,F4,K4,M(69));
	R(a,b,c,d,e,F4,K4,M(70));
	R(e,a,b,c,d,F4,K4,M(71));
	R(d,e,a,b,c,F4,K4,M(72));
	R(c,d,e,a,b,F4,K4,M(73));
	R(b,c,d,e,a,F4,K4,M(74));
	R(a,b,c,d,e,F4,K4,M(75));
	R(e,a,b,c,d,F4,K4,M(76));
	R(d,e,a,b,c,F4,K4,M(77));
	R(c,d,e,a,b,F4,K4,M(78));
	R(b,c,d,e,a,F4,K4,M(79));

	/*Updatechainingvars*/
	hd->h0+=a;
	hd->h1+=b;
	hd->h2+=c;
	hd->h3+=d;
	hd->h4+=e;
}


/*
*ofINBUFwithlengthINLEN.
*/
staticvoid
	sha1_write(SHA1_CONTEXT*hd,unsignedchar*inbuf,size_tinlen)
{
	if(hd->count==64){/*flushthebuffer*/
		transform(hd,hd->buf);
		hd->count=0;
		hd->nblocks++;
	}
	if(!inbuf)
		return;
	if(hd->count){
		for(;inlen&&hd->count<64;inlen--)
			hd->buf[hd->count++]=*inbuf++;
		sha1_write(hd,NULL,0);
		if(!inlen)
			return;
	}

	while(inlen>=64){
		transform(hd,inbuf);
		hd->count=0;
		hd->nblocks++;
		inlen-=64;
		inbuf+=64;
	}
	for(;inlen&&hd->count<64;inlen--)
		hd->buf[hd->count++]=*inbuf++;
}


/*
*returnsthedigest.
*,butaddingbytestothe
*.
*Returns:20bytesrepresentingthedigest.
*/

staticvoid
	sha1_final(SHA1_CONTEXT*hd)
{
	u32t,msb,lsb;
	unsignedchar*p;

	sha1_write(hd,NULL,0);/*flush*/;

	t=hd->nblocks;
	/*multiplyby64tomakeabytecount*/
	lsb=t<<6;
	msb=t>>26;
	/*addthecount*/
	t=lsb;
	if((lsb+=hd->count)<t)
		msb++;
	/*multiplyby8tomakeabitcount*/
	t=lsb;
	lsb<<=3;
	msb<<=3;
	msb|=t>>29;

	if(hd->count<56){/*enoughroom*/
		hd->buf[hd->count++]=0x80;/*pad*/
		while(hd->count<56)
			hd->buf[hd->count++]=0;/*pad*/
	}
	else{/*needoneextrablock*/
		hd->buf[hd->count++]=0x80;/*padcharacter*/
		while(hd->count<64)
			hd->buf[hd->count++]=0;
		sha1_write(hd,NULL,0);/*flush*/;
		memset(hd->buf,0,56);/*fillnextblockwithzeroes*/
	}
	/*appendthe64bitcount*/
	hd->buf[56]=msb>>24;
	hd->buf[57]=msb>>16;
	hd->buf[58]=msb>>8;
	hd->buf[59]=msb	;
	hd->buf[60]=lsb>>24;
	hd->buf[61]=lsb>>16;
	hd->buf[62]=lsb>>8;
	hd->buf[63]=lsb	;
	transform(hd,hd->buf);

	p=hd->buf;
#ifdefBIG_ENDIAN_HOST
#defineX(a)do{*(u32*)p=hd->h##a;p+=4;}while(0)
#else/*littleendian*/
#defineX(a)do{*p++=hd->h##a>>24;*p++=hd->h##a>>16;	
	*p++=hd->h##a>>8;*p++=hd->h##a;}while(0)
#endif
	X(0);
	X(1);
	X(2);
	X(3);
	X(4);
#undefX
}

7. C语言 数据结构中解决冲突的方法是什么

可以参考如下方法：

1 基本原理
使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素"分类"，然后将这个元素存储在相应"类"所对应的地方。
但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了"冲突"，换句话说，就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。
总的来说，"直接寻址"与"解决冲突"是哈希表的两大特点。

2 函数构造
构造函数的常用方法（下面为了叙述简洁，设 h(k) 表示关键字为 k 的元素所对应的函数值）：
a) 除余法：
选择一个适当的正整数 p ，令 h(k ) = k mod p
这里， p 如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。
b) 数字选择法：
如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。

3 冲突处理
线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为 S ，则当 h(k) 已经存储了元素的时候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。

4 支持运算
哈希表支持的运算主要有：初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(member)。
设插入的元素的关键字为 x ，A 为存储的数组。
初始化比较容易，例如
const empty=maxlongint; // 用非常大的整数代表这个位置没有存储元素
p=9997; // 表的大小
procere makenull;
var i:integer;
begin
for i:=0 to p-1 do
A[i]:=empty;
End;
哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子：
function h(x:longint):Integer;
begin
h:= x mod p;
end;
我们注意到，插入和查找首先都需要对这个元素定位，即如果这个元素若存在，它应该存储在什么位置，因此加入一个定位的函数 locate
function locate(x:longint):integer;
var orig,i:integer;
begin
orig:=h(x);
i:=0;
while (i<S)and(A[(orig+i)mod S]<>x)and(A[(orig+i)mod S]<>empty) do
inc(i);
//当这个循环停下来时，要么找到一个空的存储单元，要么找到这个元
//素存储的单元，要么表已经满了
locate:=(orig+i) mod S;
end;
插入元素
procere insert(x:longint);
var posi:integer;
begin
posi:=locate(x); //定位函数的返回值
if A[posi]=empty then A[posi]:=x
else error; //error 即为发生了错误，当然这是可以避免的
end;
查找元素是否已经在表中
procere member(x:longint):boolean;
var posi:integer;
begin
posi:=locate(x);
if A[posi]=x then member:=true
else member:=false;
end;
这些就是建立在哈希表上的常用基本运算。

4.1 应用的简单原则
什么时候适合应用哈希表呢？如果发现解决这个问题时经常要询问："某个元素是否在已知集合中？"，也就是需要高效的数据存储和查找，则使用哈希表是最好不过的了！那么，在应用哈希表的过程中，值得注意的是什么呢？
哈希函数的设计很重要。一个不好的哈希函数，就是指造成很多冲突的情况，从前面的例子已经可以看出来，解决冲突会浪费掉大量时间，因此我们的目标就是尽力避免冲突。前面提到，在使用"除余法"的时候，h(k)=k mod p ，p 最好是一个大素数。这就是为了尽力避免冲突。为什么呢？假设 p=1000 ，则哈希函数分类的标准实际上就变成了按照末三位数分类，这样最多1000类，冲突会很多。一般地说，如果 p 的约数越多，那么冲突的几率就越大。
简单的证明：假设 p 是一个有较多约数的数，同时在数据中存在 q 满足 gcd(p,q)=d >1 ，即有 p=a*d , q=b*d, 则有 q mod p= q - p* [q div p] =q - p*[b div a] . ① 其中 [b div a ] 的取值范围是不会超过 [0，b] 的正整数。也就是说， [b div a] 的值只有 b+1 种可能，而 p 是一个预先确定的数。因此 ① 式的值就只有 b+1 种可能了。这样，虽然mod 运算之后的余数仍然在 [0，p-1] 内，但是它的取值仅限于 ① 可能取到的那些值。也就是说余数的分布变得不均匀了。容易看出， p 的约数越多，发生这种余数分布不均匀的情况就越频繁，冲突的几率越高。而素数的约数是最少的，因此我们选用大素数。记住"素数是我们的得力助手"。
另一方面，一味的追求低冲突率也不好。理论上，是可以设计出一个几乎完美，几乎没有冲突的函数的。然而，这样做显然不值得，因为这样的函数设计很浪费时间而且编码一定很复杂，与其花费这么大的精力去设计函数，还不如用一个虽然冲突多一些但是编码简单的函数。因此，函数还需要易于编码，即易于实现。
综上所述，设计一个好的哈希函数是很关键的。而"好"的标准，就是较低的冲突率和易于实现。