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

软件技术基础实验三哈希查找和二叉排序 班级：通信1302班学号：1070213221姓名：马世松一、实验目的设计对哈希表和二叉排序树的算法程序（1）创建由输入文件input.txt指定的随机正整数（不少于12个），设计构造一个哈希查找表，使用线性探查法处理可能的冲突，结果输出到指定文件output.txt。（2）创建由输入文件input.txt指定的随机字母（结点个数不小于10个）序列，按照该随机字母序列的顺序，设计构造一个二叉排序树，结果输出到指定文件output.txt。二、算法原理线性探查法：将散列表T0.m-1看成是一个循环向量,若初始探查的地址为d(即h(key)=d),则最长的探查序列为：d,d+l,d+2,m-1,0,1,d-1即:探查时从地址d开始,首先探查Td,然后依次探查Td+1,直到Tm-1,此后又循环到T0,T1,直到探查到Td-1为止.探查过程终止于三种情况：(1)若当前探查的单元为空,则表示查找失败（若是插入则将key写入其中）；(2)若当前探查的单元中含有key,则查找成功,但对于插入意味着失败；(3)若探查到Td-1时仍未发现空单元也未找到key,则无论是查找还是插入均意味着失败(此时表满).二叉排序树的插入：首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。三、实验流程图步骤（1） 步骤（2）实验源代码#include#include#includeFILE*fin=fopen(input.txt,w);FILE*fout=fopen(output.txt,w);void create_input() int j,a12,b10,p,i=0;char c; srand(unsigned)time(NULL); for(i=0;i12;i+) p=rand()%100+1; for(j=0;j=i)ai=p; elsei-;continue; for(i=0;i12;i+)fprintf(fin,%d ,ai); fputc(n,fin); for(i=0;i10;i+) p=rand()%26; for(j=0;j=i)bi=p; elsei-;continue; for(i=0;i10;i+) c=bi+a; fputc(c,fin); fclose(fin);struct hnode int flag; int key;hnode hash12;void create_hash() int i,k,n12; for(i=0;i12;i+)hashi.flag=0; for(i=0;i12;i+)fscanf(fin,%d ,&ni); for(i=0;i12;i+) k=ni%12+1; while(hashk-1.flag) k=(k+1)%12; hashk-1.key=ni;hashk-1.flag=1; return;void prt_hash() int i;for(i=0;i12;i+)fprintf(fout,%d ,hashi.key);/for(i=0;ilchild=NULL;root-rchild=NULL; char c10;int i;bsnode *p,*q; for(i=0;ic=c0;q=root; for(i=1;ic=ci;p-lchild=p-rchild=NULL;while(q-lchild!=p)&(q-rchild!=p) if(cic) 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 c300; 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);四、实验结果截图五、实验总结这次试验主要利用了线性探查法和二叉排序树的插入等知识，总体难度不是很大，通过这次试验，加深了我对哈希表和二叉排序树的认识，让我对排序算法的理解更深入了一个层次。