查找算法的设计与实现.docx

1、查找算法的设计与实现 （本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助） 实验难度： A B C 序号学号姓名成绩指导教师 （签名）学期：2014 秋季学期 任课教师: 张德海 王常吉 实验题目: 查找算法的设计与实现 小 组 长: 联系电话: 电子邮件: 完成提交时间：2014年 12月 31日云南大学软件学院2014学年 秋季 学期数据结构实验成绩考核表学号：20131120267 姓名：蔡智霖 本人承担角色：代码设计，算法分析，运行监测，填写报告评分项目评分指标分值得分实验构思（10%）1. 实验目的明确52. 实验内容理解透彻、对实验所涉及到的知识点分析到

2、位5实验设计（15%）1. 有对基本数据结构的抽象数据类型定义52. 实验方案设计完整，数据结构、算法选择合理 53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图5实验实现（25%）1. 代码编写规范、风格统一、注释清楚易读 52. 程序运行正常，测试结果正确153. 界面友好、易于操作、有较强的容错性5实验报告撰写（10%）1. 内容详实无缺漏，文字流畅、图表清楚52. 实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考5个人工作量（30%）1. 个人完成工作量152. 个人技术水平103. 团队合作精神5实验运作（10%）1. 有一定用户群52. 应

3、用前景分析5综合得分： （满分100分）指导教师： 年 月 日云南大学软件学院2010学年 秋季 学期数据结构实验成绩考核表学号：20131120272 姓名：邓飞武 本人承担角色：结果检验评分项目评分指标分值得分实验构思（10%）1. 实验目的明确52. 实验内容理解透彻、对实验所涉及到的知识点分析到位5实验设计（15%）1. 有对基本数据结构的抽象数据类型定义52. 实验方案设计完整，数据结构、算法选择合理 53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图5实验实现（25%）1. 代码编写规范、风格统一、注释清楚易读 52. 程序运行正常，测试结果正确153. 界面友好、易于操作、

4、有较强的容错性5实验报告撰写（10%）1. 内容详实无缺漏，文字流畅、图表清楚52. 实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考5个人工作量（30%）1. 个人完成工作量152. 个人技术水平103. 团队合作精神5实验运作（10%）1. 有一定用户群52. 应用前景分析5综合得分： （满分100分）指导教师： 年 月 日云南大学软件学院2010学年 秋季 学期数据结构实验成绩考核表学号：20131120247 姓名：温岩松 本人承担角色：错误总结评分项目评分指标分值得分实验构思（10%）1. 实验目的明确52. 实验内容理解透彻、对实验所涉及到的知识

5、点分析到位5实验设计（15%）1. 有对基本数据结构的抽象数据类型定义52. 实验方案设计完整，数据结构、算法选择合理 53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图5实验实现（25%）1. 代码编写规范、风格统一、注释清楚易读 52. 程序运行正常，测试结果正确153. 界面友好、易于操作、有较强的容错性5实验报告撰写（10%）1. 内容详实无缺漏，文字流畅、图表清楚52. 实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考5个人工作量（30%）1. 个人完成工作量152. 个人技术水平103. 团队合作精神5实验运作（10%）1. 有一定用户群5

6、2. 应用前景分析5综合得分： （满分100分）指导教师： 年 月 日云南大学软件学院2010学年 秋季 学期数据结构实验成绩考核表学号：20131120258 姓名：程哲 本人承担角色：实验分析评分项目评分指标分值得分实验构思（10%）1. 实验目的明确52. 实验内容理解透彻、对实验所涉及到的知识点分析到位5实验设计（15%）1. 有对基本数据结构的抽象数据类型定义52. 实验方案设计完整，数据结构、算法选择合理 53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图5实验实现（25%）1. 代码编写规范、风格统一、注释清楚易读 52. 程序运行正常，测试结果正确153. 界面友好、易于

7、操作、有较强的容错性5实验报告撰写（10%）1. 内容详实无缺漏，文字流畅、图表清楚52. 实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考5个人工作量（30%）1. 个人完成工作量152. 个人技术水平103. 团队合作精神5实验运作（10%）1. 有一定用户群52. 应用前景分析5综合得分： （满分100分）指导教师： 年 月 日（下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验

8、实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）数据结构算法的知识： 表的定义；表项的表示；表的存储结构；哈希表的定义；哈希函数的构造方法；哈希表查找处理冲突的办法二、【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系）抽象数据类型的功能规格说明：定义学生结点：typedef struct student /学生结点 char name16; char number11; struct student *next; student;哈希函数 int Hash(cha

9、r *str)按姓名进行查找 student *search1(char *name)按学号进行查找 student *search2(char *number)插入某指针指向的结点 void ins(student *q)删除p指针所指的结点 void del(student *p)插入 void Insert()输出哈希表全部的内容 void print()修改内容 void change()两种方式查找 void search()三、【实现描述（Implement）】(30%)（本部分应包括：抽象数据类型具体实现的函数原型说明、 关键操作实现的伪码算法、 函数设计、函数间的调用关系，关键

10、的程序流程图等，给出关键算法的时间复杂度分析。）抽象数据类型具体实现的函数原型说明：1.节点类型typedef struct student /学生结点 char name16; char number11; struct student *next; student;2.哈希函数int Hash(char *str) /哈希函数 int i; i = strlen(str); return i; 3.main函数int main() char menu220 = 请选择你要的操作的序号:n 1.插入元素n 2.删除元素n 3.查看哈希表n 4.查找元素n 5.更改信息n 6.退出n ; ch

11、ar c; int i; printf(nn); printf(*n); printf(* 程序说明:本程序利用哈希表，按照学生姓名（汉语拼音）长度分 *n); printf(* 配其所在地址,学生信息包括姓名，学号，可以对该表进行插入， *n); printf(* 删除，查找，查看，更改信息等操作，是一个管理学生的小系统 *n); printf(*nnn); for(i = 0 ; i name,name) /p指针不空并且p-name不是要找的那个name则循环进行 p = p-next; if (!p) return NULL; /返回空指针 else return p; /返回指针p

12、/*按学号查找*/ student *search2(char *number) int i; student *p,*q; for(i = 0 ; i next = NULL) /该地址上只有1个元素的情况 if (strcmp(p-number,number) continue; else return p; else /该地址上多于1个元素的情况 q = HashTablei; /此时p和q都是HashTablei while (p & strcmp(p-number,number) /p指针不空并且p-name不是要找的那个name则循环进行 q = p; /保持q在p的前面 p =

13、p-next; if (!p) continue; else /p指针所指的结点 p-name就是要查找的name return p; return NULL; /如果直到i=16时才结束，正常结束，则没有找到该学号的学生 /*插入某指针指向的结点*/ void ins(student *q) location = strlen(q-name); if (HashTablelocation = NULL) /此位置上还没有插入一个元素 HashTablelocation = q; / HashTablelocation指向node q-next = NULL; else /向前插 q-next

14、 = HashTablelocation; /HashTablelocation 是指针! HashTablelocation = q; /*删除p指针所指的结点*/ void del(student *p) /删除p指针所指向的结点 student *q; int location = Hash(p-name); /找到地址 if (p-next = NULL) /要删除的元素所在地址上只有1个元素的情况 HashTablelocation = NULL; free(p); else /要删除的元素所在地址上多于1个元素的情况 p = HashTablelocation; q = HashT

15、ablelocation; while (p & strcmp(p-name,name) /p指针不空并且p-name不是要找的那个name则循环进行 q = p; /保持q在p的前面 p = p-next; /循环结束时已经找到要删的结点了 q-next = p-next; free(p); /删除p结点 /*插入*/ void Insert() /插入完成 student *node; printf(请输入要插入的同学的姓名（汉语拼音，字符不多于15个）:n); gets(name); printf(请输入要插入的同学的学号（不多于10位）:n); gets(number); node =

16、 (student *)malloc(sizeof(struct student); node-next = NULL; strcpy(node-name,name); /复制字符串 strcpy(node-number,number); location = Hash(node-name); /找到应该插入的位置 if (HashTablelocation = NULL) /此位置上还没有插入一个元素 HashTablelocation = node; / HashTablelocation指向node printf( 插入完成!nn); else /向前插 node-next = Hash

17、Tablelocation; /HashTablelocation 是指针! HashTablelocation = node; printf( 插入完成!nn); void Delete() /按姓名删除 student *p; char info16; printf(请输入要删除的同学的姓名或学号:n); gets(info); if (info0 = 0 & info0 = 9) /知道输入的是学号 p = search2(info); if(!p) printf(没有此学号的学生，无法修改信息!nn); return; else del(p); printf(删除成功!nn); return; else p = search1(info); if (!p) printf(没有此学号的学生，无法修改信息!nn); return; else del(p); printf(删除成功!nn); return; /*输出哈希表全部的内容*/ void print() int i ; student *p ; printf(哈希表的所有元素及所在地址如下:n); for (i = 0 ; i 16 ; i+) printf(%-2d :,i); if (!HashTablei) print