发布时间 : 星期六 文章数据结构实验报告（华夏）更新完毕开始阅读3b8bbc00ccbff121dd368354
实验七 散列（哈希）表的建立和查找算法设计
一、预习报告
实验目的
1、掌握用Turbo C上机调试散列表的设计及应用算法的程序；
2、了解散列表的设计及应用，包括：建立散列表、解决冲突和查找元素； 基本原理与方法 利用散列（哈希）表的形成原理用C语言编程实现
实验设备 PC机一台、配置Turbo C软件 二、实验内容
散列表的设计及应用
〔问题描述〕 设一个序列为{53，17，12，61，98，70，87，25，63，46，14，59，67，
75} 建立散列表，并用开放地址二次探测再散列处理冲突
[基本要求] 1. 建立散列表，设哈希函数为：H（K）=K MOD 17 ；
2. 二次探测再散列处理冲突求“下一个”的地址公式是； d1 = H(ki) ;
d2j = (d1 + j2 ) MOD m ; m=18; d 2j+1 = (d1 – j2 ) MOD m j=1,2,….. 3. 查找值为70 的元素位置；
[参考程序] # include “stdio.h” # include “string.h” #define MAX 50
int ha[MAX], hlen[MAX] ,n, m, p ; void creathash ( )
{ int i, j , d , d1, odd , s , key [MAX] ;
printf (“=========建立散列表=========”) ; printf (“输入元素个数n:”) ; scanf (“%d” ,&n) ;
printf (“\\n输入表的长度m:”) ; scanf (“%d” ,&m) ;
printf (“\\n散列函数为 K MOD p, (输入p)”) ; scanf (“%d” ,&p) ; for (i=0 ; i { ha [i] = 9999 ；hlen[i]=0 ；} /* hlen[I]为第i个元素的查找长度*/ i=0 ; while (i { printf (“输入第% d个元素 ：i+1 ”) ; scanf (“%d” ,&key[i]) ; odd=1 ; if ( key[i] <= 0 ) printf (“\\n输入错误，重新输入！”) ; else i++ } i=0 ; printf (“ \\n建立散列表如下”) ; while (i j =s =1 ; /*为记录比较次数*/ printf (“ H(%d)= %d MOD %d = %d”, key(i) , key(i) , p , d) ; while ( ha[d] != 9999) { printf (“ 冲突 \\n”) ; if (odd ) { d= ( d1+j *j) % m ; printf (“ H(%d)= (%d+%d*%d) MOD %d = %d”, key(i) , d1, j,j,m , d) ; odd = 0 ; } else d= ( d1-j *j) % m ; printf (“ H(%d)= (%d - %d*%d) MOD %d = %d”, key(i) , d1, j,j,m , d) ; odd = 1 ; j ++ ; } s ++ ; } printf ( “ 比较次数为%d \\ n”, s) ; ha[d]=key [ i] ; hlen [d] = s ; i++ ; } printf (“ \\n 散列表如下\\n”) ; for (i=0 ; i printf (“M”, i) ; printf (“\\n”); for (i=0 ; i for (i=0 ; i s= s+hlen[i] ;while ( ha[d] != 9999 && hlen[d]!= x)if (odd ) { d= ( d1+j *j) % m ; odd=0 } { d= ( d1-j *j) % m ; odd=1 ; j++ ;}ha[d] = = 9999 ) printf( “ \\t %d 不在散列表中\\n”, x);printf( “ \\t ha[%d]=%d\\n ”, d, x); } main ()creathash ( ) ; 三、实验结果分析讨论若要查找值为70，17，18的元素位置时，程序应做怎样的修改？ 四、巩固题 实验八 常规排序算法设计 一、预习报告 实验目的 1、掌握用Turbo C上机调试常规排序算法的程序； 基本原理与方法 利用常规排序算法原理用C语言编程实现 实验设备 PC机一台、配置Turbo C软件 二、实验内容 学生成绩统计 〔问题描述〕 给出N个学生的考试成绩信息，每条信息由姓名与分数组成，设计一个算 法： 1、按分数高低次序，打印每个学生在考试中获得的名次； 2、按名次列出每个学生的姓名与分数； [基本要求] 1、学生的成绩必须由键盘输入数据而建立； 2、要控制好输入、输出的格式及界面； [算法实现] 用直接选择排序法实现； [参考程序] # defile n 30 typedef struct student { char name[8] ; int score ; } student p[n] ; main () { int num , I , j, max , temp ; printf(“\\n请输入学生成绩：\\n”) ； for (i=0 ; i { printf(“姓名： 成绩“)； scanf(“%s”, p[i].name) ; scanf(“M”,&p[i].score) ; } num=1 ; for (i=0 ; i for (j=j+1 ; j < n ; j++) if ( p[j].score > p [max].score ) max=j ; if ( max !=i ) { temp = p[max] ; p[max]=p[ i ] ; p[ i ] = temp ; } if ( (i>0) && (p[j].score < p [i-1].score ) ) . num = num+1 ; printf ( “M %s M “, num , p[i].name , p[i].score); } } 三、实验结果分析讨论 1． 自己设定数据运行程序，检测程序有无错误，若有请改正； 2． 在此基础上，试用插入法、归并法排序实现； 四、巩固题 阅读下列用冒泡法编制的排序程序，总结编程技巧。 〔问题描述〕1. 在程序运行的过程中随机产生10个100以内的整数； 2. 用自上往下扫描的冒泡法对这10个数进行排序； 3. 输出每一趟扫描后的结果 [算法实现] 1. 随机数的初始化使用的函数为randomize()， 产生随机数的函数为random() 2. 自上往下扫描的冒泡法排序的基本思路是：每次在从前往后扫描并交换的过程中，用一个变量如flag记录下进行交换的最后一个元素的位置。本次扫描结束后再用该变量flag作为下一趟排序终止的条件。 [参考程序] # include “stdio.h” # include “string.h” # include “alloc.h” #define N 10 main() /*主程序*/ ｛ int i ,j ,k , a[N]; int flag， x，count＝0； ; randomize() ; /*随机数初始化*/ printf(“ \\n产生的随机数序列为：” )； /*输出产生的随机数序列*/ for (i=0;i ｛ a[i]=random(100); printf(“M”,a[i]); ｝ for (i=0;i<58;i++) printf(“*” ); /*输出58个*作为分界*/ i＝N－1； while（i>0） ｛ flag＝0；count＋＋ ； for (j=0;j ｛ x＝a[j];a[j]=a[j+1];a[j+1]=x; flag＝j；} ｝ printf(“ \\n第％d趟的数据序列为：”，count )； for (k=0;k 测试数据：产生的随机数序列为 ： 52 43 19 74 75 14 77 10 13 74 *********************************************************** 第1趟的数据序列为 ：43 19 52 74 14 75 10 13 74 77 第2趟的数据序列为 ：19 43 52 14 74 10 13 74 75 77 第3趟的数据序列为 ：19 43 14 52 10 13 74 74 75 77 第4趟的数据序列为 ：19 14 43 10 13 52 74 74 75 77 第5趟的数据序列为 ：14 19 10 13 43 52 74 74 75 77 第6趟的数据序列为 ：14 10 13 19 43 52 74 74 75 77 第7趟的数据序列为 ：10 13 14 19 43 52 74 74 75 77