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