计算机软件基础作业答案

《计算机软件基础作业答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、软件技术基础实验三——哈希查找和二叉排序班级：通信1302班学号：1070213221姓名：马世松一、实验目的设计对哈希表和二叉排序树的算法程序（1）创建由输入文件input.txt指定的随机正整数（不少于12个），设计构造一个哈希查找表，使用线性探查法处理可能的冲突，结果输出到指定文件output.txt。（2）创建由输入文件input.txt指定的随机字母（结点个数不小于10个）序列，按照该随机字母序列的顺序，设计构造一个二叉排序树，结果输出到指定文件output.txt。二、算法原理线性探查法：将

2、散列表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]时

3、仍未发现空单元也未找到key,则无论是查找还是插入均意味着失败(此时表满).二叉排序树的插入：首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。三、实验流程图步骤（1）步骤（2）实验源代码#include#include#includeFILE*fin=fopen("input.txt","w");FILE*fout=fope

4、n("output.txt","w");voidcreate_input(){intj,a[12],b[10],p,i=0;charc;srand((unsigned)time(NULL));for(i=0;i<12;i++){p=rand()%100+1;for(j=0;j=i)a[i]=p;else{i--;continue;}}for(i=0;i<12;i++)fprintf(fin,"%d",a[i]);fputc('',fin);f

5、or(i=0;i<10;i++){p=rand()%26;for(j=0;j=i)b[i]=p;else{i--;continue;}}for(i=0;i<10;i++){c=b[i]+'a';fputc(c,fin);}fclose(fin);}structhnode{intflag;intkey;};hnodehash[12];voidcreate_hash(){inti,k,n[12];for(i=0;i<12;i++)hash[i].fl

6、ag=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;}voidprt_hash(){inti;for(i=0;i<12;i++)fprintf(fout,"%d",hash[i].key);//for(i=0;i<12;i++)printf("%d",has

7、h[i].key);}structbsnode{charc;bsnode*lchild;bsnode*rchild;};bsnode*root=newbsnode;voidcreate_bstree(){root->lchild=NULL;root->rchild=NULL;charc[10];inti;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

8、;i++){p=newbsnode;p->c=c[i];p->lchild=p->rchild=NULL;while((q->lchild!=p)&&(q->rchild!=p)){if(c[i]c){if(q->lchild!=NULL)q=q->lchild;elseq->lchild=p;}else{if(q->rchild!=NULL)q=q->rchild;elseq->rchild=p;}}q=root;}return;