数据结构实验报告七查找、
- 格式:doc
- 大小:211.50 KB
- 文档页数:21
云南大学软件学院数据结构实验报告
(本实验项目方案受“教育部人才培养模式创新实验区(X3108005)”项目资助)实验难度: A □ B □ C □
学期:2010秋季学期
任课教师:
实验题目: 查找算法设计与实现
姓名: 王辉
学号: 20091120154
电子邮件:
完成提交时间: 2010 年 12 月 27 日
云南大学软件学院2010学年秋季学期
《数据结构实验》成绩考核表
学号:姓名:本人承担角色:
综合得分:(满分100分)
指导教师:年月日(注:此表在难度为C时使用,每个成员一份。)
(下面的内容由学生填写,格式统一为,字体: 楷体, 行距: 固定行距18,字号: 小四,个人报告按下面每一项的百分比打分。难度A满分70分,难度B满分90分)一、【实验构思(Conceive)】(10%)
1 哈希表查找。根据全年级学生的姓名,构造一个哈希表,选择适当的哈希函数和解决冲突的方法,设计并实现插入、删除和查找算法。
熟悉各种查找算法的思想。
2、掌握查找的实现过程。
3、学会在不同情况下运用不同结构和算法求解问题。
4 把每个学生的信息放在结构体中:
typedef struct //记录
{
NA name;
NA tel;
NA add;
}Record;
5 void getin(Record* a)函数依次输入学生信息
6 人名折叠处理,先将用户名进行折叠处理折叠处理后的数,用除留余数法构造哈希函数,并返回模值。并采用二次探测再散列法解决冲突。
7姓名以汉语拼音形式,待填入哈希表的人名约30个,自行设计哈希函数,用线性探测再散列法或链地址法处理冲突;在查找的过程中给出比较的次数。完成按姓名查询的操作。将初始班级的通讯录信息存入文件。
二、【实验设计(Design)】(20%)
(本部分应包括:抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明,主程序模块与各子程序模块间的调用关系)
1抽象数据类型的功能规格说明和结构体:
#include
#include
#include
#include
#define MAXSIZE 20 //电话薄记录数量
#define MAX_SIZE 20 //人名的最大长度
#define HASHSIZE 53 //定义表长
#define SUCCESS 1
#define UNSUCCESS -1
#define LEN sizeof(HashTable)
typedef int Status;
typedef char NA[MAX_SIZE];
typedef struct //记录
{
NA name;
NA tel;
NA add;
}Record;
typedef struct //哈希表
{
Record *elem[HASHSIZE]; //数据元素存储基址
int count; //当前数据元素个数
int size; //当前容量
}HashTable;
2 主函数与各子函数的调用关系:(通过switch(num)函数按不同功能要求分别调用相关函数)int main(int argc, char* argv[]){
system("color 61");
int c,flag=1;
HashTable *H;
H=(HashTable*)malloc(LEN);
for(int i=0;i H->elem[i]=NULL; H->size=HASHSIZE; H->count=0; Record a[MAXSIZE]; while (1) { printf("\n ★☆★☆★☆★☆★☆wang hui★☆★☆★☆★☆★☆★☆"); printf("\n ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★"); printf("\n ★☆★☆我的未来不是梦★☆★☆"); printf("\n ★☆★☆无聊中郁闷死★☆★☆"); printf("\n ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★"); printf("\n ┏━━━━━━━━━━━━━┓"); printf("\n ★┃欢迎欢迎欢迎欢迎欢迎欢迎┃★"); printf("\n 〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒"); printf("\n ★★★★★★★哈希表的设计与实现★★★★★★"); printf("\n 【】. 添加用户信息"); printf("\n 【】. 读取所有用户信息"); printf("\n 【】. 以姓名建立哈希表(再哈希法解决冲突) "); printf("\n 【】. 以电话号码建立哈希表(再哈希法解决冲突) "); printf("\n 【】. 查找并显示给定用户名的记录"); printf("\n 【】. 查找并显示给定电话号码的记录"); printf("\n 【】. 清屏"); printf("\n 【】. 保存"); printf("\n 【】. 退出程序"); printf("\n 温馨提示:"); printf("\n Ⅰ.进行操作前请先输出"); printf("\n Ⅱ.进行操作前请先输出"); printf("\n ★★★★★★★〒〒〒〒〒〒〒〒〒★★★★★★"); printf("\n"); printf("请输入一个任务选项>>>"); printf("\n"); int num; scanf("%d",&num); switch(num){ case 1: getin(a); break; case 2: ShowInformation(a); break; case 3: CreateHash1(H,a); /* 以姓名建立哈希表*/ break; case 4: CreateHash2(H,a); /* 以电话号码建立哈希表*/ break;