软基上机实验报告-查找和排序(拓展题).doc

四、程序流程说明ex5_2：Hash查找——扩展题1）一个班有30位同学，安排装进一个有30个元素的数组，以姓名作为关键字进行哈希存储，具体方法如下：将姓名字符串中的每个字节按ASCII码（中文也支持 的哦）加起来，除以30，取得的余数作为元素存放位置（数组下标）。冲突解决采用线性探查法。2）输入少于30个学生姓名，按Hash方式存入表中。3）验证能够按Hash方式找到表中学生，不在表中将提示错误ex5_3：排序——基本题1）编写简单选择法函数2）编写直接插入法函数3）编写冒泡法排序函数4）在主程序中输入一组数据元素，如513，87，512，61，908，170，897，275，653，462，分别调用三种排序函数，输出每趟排序结果。ex5-4：排序——扩展题编写快速排序函数五、实验程序代码：Ex.2#include<stdio.h>#include<string.h>struct student{ char name[20];};struct student s[30];int hash(char *cp)//哈希查找{ int sum=0; int n,k; char *q; q=cp; int i; n=strlen(cp); for(i=0;i<n;i++) { sum+=(*cp); cp++; } k=sum%30; while(s[k].name[0]!='\0'&&strcmp(s[k].name,q)!=0) {k=(k+1)%30;} if(s[k].name[0]!='\0') {printf("searching success\n");} else printf("searching failed\n"); return 0;}void hash_save()//哈希表的建立{ int i=0,n,sum=0; int k; char name[20]; char *p; printf("input the number of the names:\t"); scanf("%d",&n); while(n--) { printf("input the name:"); scanf("%s",name); p=name; k=strlen(p); for(i=0;i<k;i++) { sum+=(*p); p++; } k=sum%30; while(s[k].name[0]!='\0') { k=(k+1)%30; } i=0; while(name[i]!='\0') { s[k].name[i]=name[i]; i++; } }}main(){ void hash_save(); int hash(char *cp); hash_save(); char name[20]; printf("input one name to search:\t"); scanf("%s",name); hash(name); printf("input the another name to search:\t"); scanf("%s",name); hash(name);}Ex.3#include<stdio.h>#define N 10void selectsort(int s[])//简单选择排序{ int i,j,k,small; int swap; for(i=0;i<N-1;i++) { small=i; for(j=i+1;j<N;j++) { if(s[j]<s[small]) small=j; } if(small!=i) { swap=s[i]; s[i]=s[small]; s[small]=swap; } printf("第%d趟:\t",i+1); for(k=0;k<N;k++) {printf("%d ",s[k]);} printf("\n"); }}void insertsort(int s[])//简单插入排序{ int i,j,k; int a; for(i=0;i<N-1;i++) { a=s[i+1]; j=i; while(j>-1&&a<s[j]) { s[j+1]=s[j]; j--; } s[j+1]=a; printf("第%d趟:\t",i+1); for(k=0;k<N;k++) {printf("%d ",s[k]);} printf("\n"); }}void bubblesort(int s[])//冒泡排序{ int i,j,k; int swap; for(i=0;i<N-1;i++) { for(j=0