查找算法的设计与实现Word文档下载推荐.docx
《查找算法的设计与实现Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《查找算法的设计与实现Word文档下载推荐.docx(39页珍藏版)》请在冰点文库上搜索。
![查找算法的设计与实现Word文档下载推荐.docx](https://file1.bingdoc.com/fileroot1/2023-5/7/07abe2b6-c526-4dcf-b035-4f2ffc0a7ac4/07abe2b6-c526-4dcf-b035-4f2ffc0a7ac41.gif)
分值
得分
实验构思(10%)
1.实验目的明确
5
2.实验内容理解透彻、对实验所涉及到的知识点分析到位
实验设计(15%)
1.有对基本数据结构的抽象数据类型定义
2.实验方案设计完整,数据结构、算法选择合理
3.算法结构和程序功能模块之间逻辑清晰、有相应的流程图
实验实现(25%)
1.代码编写规范、风格统一、注释清楚易读
2.程序运行正常,测试结果正确
15
3.界面友好、易于操作、有较强的容错性
实验报告撰写(10%)
1.内容详实无缺漏,文字流畅、图表清楚
2.实验结果分析客观、详细,实验体会真实可信,对原实验方案的改进和对实验内容的发散性思考
个人工作量(30%)
1.个人完成工作量
2.个人技术水平
10
3.团队合作精神
实验运作(10%)
1.有一定用户群
2.应用前景分析
综合得分:
(满分100分)
指导教师:
年月日
云南大学软件学院2010学年秋季学期
20131120272姓名:
邓飞武本人承担角色:
结果检验
20131120247姓名:
温岩松本人承担角色:
错误总结
20131120258姓名:
程哲本人承担角色:
实验分析
(下面的内容由学生填写,格式统一为,字体:
楷体,行距:
固定行距18,字号:
小四,个人报告按下面每一项的百分比打分。
难度A满分70分,难度B满分90分)
一、【实验构思(Conceive)】
(10%)
(本部分应包括:
描述实验实现的基本思路,包括所用到的离散数学、工程数学、程序设计、算法等相关知识)
数据结构算法的知识:
表的定义;
表项的表示;
表的存储结构;
哈希表的定义;
哈希函数的构造方法;
哈希表查找处理冲突的办法
二、【实验设计(Design)】
(20%)
抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明,主程序模块与各子程序模块间的调用关系)
抽象数据类型的功能规格说明:
定义学生结点:
typedefstructstudent//学生结点
{
charname[16];
charnumber[11];
structstudent*next;
}student;
哈希函数intHash(char*str)
按姓名进行查找student*search1(char*name)
按学号进行查找student*search2(char*number)
插入某指针指向的结点voidins(student*q)
删除p指针所指的结点voiddel(student*p)
插入voidInsert()
输出哈希表全部的内容voidprint()
修改内容voidchange()
两种方式查找voidsearch()
三、【实现描述(Implement)】
(30%)
抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函数设计、函数间的调用关系,关键的程序流程图等,给出关键算法的时间复杂度分析。
)
抽象数据类型具体实现的函数原型说明:
1.节点类型
2.哈希函数
intHash(char*str)//哈希函数
inti;
i=strlen(str);
returni;
}
3.main函数
intmain()
charmenu[220]="
请选择你要的操作的序号:
\n1.插入元素\n2.删除元素\n3.查看哈希表\n4.查找元素\n5.更改信息\n6.退出\n"
;
charc;
printf("
\n\n"
);
****************************************************************\n"
**程序说明:
本程序利用哈希表,按照学生姓名(汉语拼音)长度分**\n"
**配其所在地址,学生信息包括姓名,学号,可以对该表进行插入,**\n"
**删除,查找,查看,更改信息等操作,是一个管理学生的小系统**\n"
****************************************************************\n\n\n"
for(i=0;
i<
13;
i++)
HashTable[i]=NULL;
//初始置空
do
{
puts(menu);
c=getch();
putchar(c);
switch(c)
case'
1'
:
Insert();
break;
2'
Delete();
//两种方法的删除!
!
3'
print();
4'
search();
//两种方法的查找!
5'
change();
//先查找,再修改
6'
谢谢使用本系统,欢迎再次使用!
\n"
);
//下面的while中退出!
default:
putch(7);
输入有误,请重新输入!
}
}while(c!
='
//while后面的'
;
'
不可少
return0;
四、【测试结果(Testing)】
对实验的测试结果,应具体列出每次测试所输入的数据以及输出的数据,并对测试结果进行分析总结)
程序开始界面
执行功能1
多次执行功能1创建哈希表后,执行功能3进行查看
执行功能4,进行查找
执行功能5,更改信息
查找信息,确认更改
执行功能2,删除信息
查看信息,确认更改
四、【实验总结】
自己在实验中完成的任务,注意组内的任意一位同学都必须独立完成至少一项接口的实现;
对所完成实验的经验总结、心得)
蔡智霖:
我们合理的分配了任务,并经过我们共同的努力才把这一实验基本完成了。
从这次的实验中,我看到了自己的不足,首先就是比较轻浮,不能够踏踏实实的,其次,就是我个人的动手操作能力,即上机编程能力还是十分欠缺的,这还是我们平时锻炼的少所造成的。
所以在以后的学习中我们要加强这方面的锻炼。
邓飞武:
在做实验前,一定要将课本上的知识吃透,因为这是做实验的基础,否则,在老师讲解时就会听不懂,这将使你在做实验时的难度加大,浪费做实验的宝贵时间.
温岩松:
通过这次实验,使我学到了不少实用的知识,更重要的是,做实验的过程,思考问题的方法,这与做其他的实验是通用的,真正使我们受益匪浅.
程哲:
在这次实验中,我学到很多东西,加强了我的动手能力,并且培养了我的独立思考能力。
特别是在做实验报告时,因为在做数据处理时出现很多问题,如果不解决的话,将会很难的继续下去。
五、【项目运作描述(Operate)】
项目的成本效益分析,应用效果等的分析。
本程序可以实现基本的学生查找功能,可以根据使用者所输入的学生信息来进行查找。
因为本程序并不具备可视化的运行界面,因此本程序并不具备较高的成本价值,但同时也因为本程序制作成本并不高,因此其效益相对来说尚可。
六、【代码】
完整的代码及充分的注释。
注意纸质的实验报告无需包括此部分。
格式统一为,字体:
Georgia,行距:
固定行距12,字号:
小五)
#include"
stdio.h"
conio.h"
string.h"
stdlib.h"
/**************************************全局变量***********************************/
student*HashTable[16];
//数组里的16个值元素都是头指针(什么都不存),全局变量
charname[16];
charnumber[11];
intlocation;
//地址
/*************************************哈希函数***********************************/
}
/*********************************按姓名查找************************************/
student*search1(char*name)//按姓名查找的简单,因为可以用哈希函数
student*p;
location=Hash(name);
//此同学应该存放的地址
p=HashTable[location];
while(p&
&
strcmp(p->
name,name))//p指针不空并且p->
name不是要找的那个name则循环进行
p=p->
next;
if(!
p)
returnNULL;
//返回空指针
else
returnp;
//返回指针p
/*********************************按学号查找************************************/
student*search2(char*number)
student*p,*q;
16;
p=HashTable[i];
if(p==NULL)//该地址上没有元素的情况
continue;
//p等于下一个位置上的指针
elseif(p->
next==NULL)//该地址上只有1个元素的情况
if(strcmp(p->
number,number))
else//该地址上多于1个元素的情况
q=HashTable[i];
//此时p和q都是HashTable[i]
number,number))//p指针不空并且p->
q=p;
//保持q在p的前面
else//p指针所指的结点p->
name就是要查找的name
//如果直到i=16时才结束,正常结束,则没有找到该学号的学生
/*******************************插入某指针指向的结点*****************************/
voidins(student*q)
location=strlen(q->
name);
if(HashTable[location]==NULL)//此位置上还没有插入一个元素
HashTable[location]=q;
//HashTable[location]指向node
q->
next=NULL;
else//向前插
next=HashTable[location];
//HashTable[location]是指针!
/*********************************删除p指针所指的结点****************************/
voiddel(student*p)//删除p指针所指向的结点
student*q;
intlocation=Hash(p->
//找到地址
if(p->
next==NULL)//要删除的元素所在地址上只有1个元素的情况
HashTable[location]=NULL;
free(p);
else//要删除的元素所在地址上多于1个元素的情况
q=HashTable[location];
//循环结束时已经找到要删的结点了
next=p->
//删除p结点
/************************************插入****************************************/
voidInsert()//插入完成
student*node;
请输入要插入的同学的姓名(汉语拼音,字符不多于15个):
gets(name);
请输入要插入的同学的学号(不多于10位):
gets(number);
node=(student*)malloc(sizeof(structstudent));
node->
strcpy(node->
name,name);
//复制字符串
number,number);
location=Hash(node->
//找到应该插入的位置
HashTable[location]=node;
插入完成!
voidDelete()//按姓名删除
charinfo[16];
请输入要删除的同学的姓名或学号:
gets(info);
if(info[0]>
='
0'
&
info[0]<
9'
)//知道输入的是学号
p=search2(info);
if(!
没有此学号的学生,无法修改信息!
return;
del(p);
删除成功!
p=search1(info);
/**********************************输出哈希表全部的内容*******************************/
voidprint()
inti;
student*p;
哈希表的所有元素及所在地址如下:
for(i=0;
%-2d:
"
i);
HashTable[i])
print