c查找与排序实验

《c查找与排序实验》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、附件（四）深圳大学实验报告课程名称：实验项目名称：学院：专业：指导教师2报告人：实验时间：实验报告提交时间::据结构实验与课程设计树结构实验计算机与软件学院软件工程班级:教务处制一、实验目的与完成说明：数裾结构实验--哈希査找给出一个数裾序列，建立哈希表，采用求余法作为哈希函数，模数为11,哈希冲突用链地址法和表头插入如果首次查找失败，就把数据插入到相应的位置屮实现哈希查找功能数据结构实验--希尔排序给出一个数据序列，使用希尔排序算法进行从小到大的排序间隔gap使用序列长度循环除2直到1数据结构实验--快速排序第一行输入t，表示有t个测试示例第二行输入n，表示第一个示例有n个

2、数据第三行输入n个数据，都是正整数，数据之间用空格隔开以此类推二、主要思路与方法：哈希査找：给定K值，根据造表时设定的哈希函数得到哈希地址，若此表中此位置没有记录，则査找不成功，否则比较关键字，若何给定值相等，则查找成功；否则根据造表时设定的处理冲突的方法找下一地址，直至哈希表的某个位置为空或表中记录的关键字等于给定的定值时为止。希尔排序：先将整个待排记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。快速排序：通过一趟排序将待排记录分割成独立的两个部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两

3、部分记录继续进行排序，以达到整个序列有序。三.实验程序或内容：哈希査找：#includeusingnamespacestd;classnode{public:intdata;node氺next;nodc(){data=0;ncxt=NULL;}}；intmain(){intn;boolvisit[11];for(intz二0;z〈ll;z++)visit[z]=false;inti;cin>>n;inta[20];for(i=0;i

4、i++){temp=a[i]%l1;if(!visit[temp]){node*s=newnode();s->data二a[i];mylistnode[temp].next=s;visit[temp]=true;}else{node*p=mylistnode[temp].next;node*q=newnode();q->data=a[i];mylistnode[temp].next=q;q->next=p;}}intt;cin»t;while(t—){cin>>target;inttl=target%ll;if(!visit[tl])cout〈〈〃error〃〈〈endl;n

5、ode本r=ncwnodc();r-〉data=target;niylistnode[tl].next=r;visit[tl]=true;}else{intflag=0;intcount=0;node氺x=mylistnode[tl]>next;while(x!=NULL){count++;if(x~>data==target){flag=l;break;}x=x->next;}if(flag==0){node氺n2=mylistnode[tl].next;node*newnode=newnode();newnode->data=target;mylistnodc[tl]en

6、cxt=ncwnodc;newnode->next=n2;cout«/zerrorzz«endl;}else{cout〈〈tl〈〈"cout«count«endl;return0;希尔排序:#includeusingnamespacestd;classhaxi{public:voidShelllnsert(intlist口，intdk,intlength){inti,j;for(i=dk+l;i<=lcngth;++i)if(list[i]0&&(list[O]

7、j]);j-=dk)list[j+dk]=list[j];list[j+dk]=list[0];voidShellSort(intlist[],intdlta[],intt,intlength){for(intk=0;k