计算机软件基础作业答案.docx

软件技术基础实验三
——哈希查找和二叉排序

班级：通信1302班
学号：1070213221
姓名：马世松

一、实验目的
设计对哈希表和二叉排序树的算法程序
（1）创建由输入文件input.txt指定的随机正整数（不少于12个），设计构造一个哈希查找表，使用线性探查法处理可能的冲突，结果输出到指定文件output.txt。
（2）创建由输入文件input.txt指定的随机字母（结点个数不小于10个）序列，按照该随机字母序列的顺序，设计构造一个二叉排序树，结果输出到指定文件output.txt。
二、算法原理
线性探查法：将散列表T[0..m-1]看成是一个循环向量,若初始探查的地址为d(即h(key)=d),则最长的探查序列为：d,d+l,d+2,…,m-1,0,1,…,d-1
即:探查时从地址d开始,首先探查T[d],然后依次探查T[d+1],…,直到T[m-1],此后又循环到T[0],T[1],…,直到探查到T[d-1]为止.
探查过程终止于三种情况：(1)若当前探查的单元为空,则表示查找失败（若是插入则将key写入其中）；(2)若当前探查的单元中含有key,则查找成功,但对于插入意味着失败；(3)若探查到T[d-1]时仍未发现空单元也未找到key,则无论是查找还是插入均意味着失败(此时表满).
二叉排序树的插入：首先执行查找算法，找出被插结点的父亲结点。
判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。

三、实验流程图
步骤（1）

步骤（2）

实验源代码
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
FILE*fin=fopen("input.txt","w");
FILE*fout=fopen("output.txt","w");
void create_input()
{ int j,a[12],b[10],p,i=0;char c;
srand((unsigned)time(NULL));
for(i=0;i<12;i++)
{ p=rand()%100+1;
for(j=0;j<i;j++)
if(p==a[j])break;
if(j>=i)a[i]=p;
else{i--;continue;}
}
for(i=0;i<12;i++)fprintf(fin,"%d ",a[i]);
fputc('\n',fin);
for(i=0;i<10;i++)
{ p=rand()%26;
for(j=0;j<i;j++)
if(p==b[j])break;
if(j>=i)b[i]=p;
else{i--;continue;}
}
for(i=0;i<10;i++)
{ c=b[i]+'a';
fputc(c,fin);
}
fclose(fin);
}
struct hnode
{ int flag;
int key;
};
hnode hash[12];
void create_hash()
{ int i,k,n[12];
for(i=0;i<12;i++)hash[i].flag=0;
for(i=0;i<12;i++)fscanf(fin,"%d ",&n[i]);
for(i=0;i<12;i++)
{ k=n[i]%12+1;
while(hash[k-1].flag)
k=(k+1)%12;

hash[k-1].key=n[i];hash[k-1].flag=1;
}
return;
}
void prt_hash()
{ int i;
for(i=0;i<12;i++)fprintf(fout,"%d ",hash[i].key);//for(i=0;i<12;i++)printf("%d ",hash[i].key);
}
struct bsnode
{ char c;
bsnode *lchild;
bsnode *rchild;
};
bsnode *root=new bsnode;
void create_bstree()
{ root->lchild=NULL;root->rchild=NULL;
char c[10];int i;bsnode *p,*q;
for(i=0;i<10;i++){c[i]=fgetc(fin);/*printf("%c ",c[i]);*/}
root->c=c[0];q=root;
for(i=1;i<10;i++)
{ p=new bsnode;
p->c=c[i];
p->lchild=p->rchild=NULL;
while((q->lchild!=p)&&(q->rchild!=p))
{ if(c[i]<q->c)
{ if(q->lchild!=NULL)q=q->lchild;
else q->lchild=p;
}
else
{ if(q->rchild!=NULL)q=q->rchild;
else q->rchild=p;
}
}
q=root;
}
return;
}
void intrav(bsnode*p)
{ if(p!=NULL)
{ intrav(p->lchild);
fprintf(fout,"%c ",p->c);
intrav(p->rchild);
}
}
void main()
{ create_input();
fin=fopen("input.txt","r");
char c[300];
create_hash();
fprintf(fout,"哈希表为：\n");
prt_hash();
fputc('\n',fout);
rewind(fin);fgets(c,300,fin);
create_bstree();
fprintf(fout,"中序遍历二叉排序树为：\n"
intrav(root);
fclose(fin);
fclose(fout);
}
四、实验结果截图

五、实验总结
这次试验主要利用了线性探查法和二叉排序树的插入等知识，总体难度不是很大，通过这次试验，加深了我对哈希表和二叉排序树的认识，让我对排序算法的理解更深入了一个层次。