查找算法的设计与实现Word文档下载推荐.docx

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

2、技术水平103. 团队合作精神实验运作（10%）1. 有一定用户群2. 应用前景分析综合得分： （满分100分）指导教师： 年 月 日云南大学软件学院2010学年 秋季 学期20131120272 姓名：邓飞武 本人承担角色：结果检验20131120247 姓名：温岩松 本人承担角色：错误总结20131120258 姓名：程哲 本人承担角色：实验分析（下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】（10%）（本部分应包括：描述实验实现的基本思路，包括

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

4、ent *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%）抽象数据类型具体实现的函数原型说明、 关键操作实现的伪码算法、 函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。）抽象数

5、据类型具体实现的函数原型说明：1.节点类型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 ; char c; printf（nn）;*n* 程序说明:本程序利用哈希表，按照学生姓名（汉语拼音）长度分 *n* 配其所在地址,学生信息包括姓名，学号，可以对该表进行插入， *n* 删除，查找，查看，更改信息等操作，是一个管理学生的小

6、系统 *n*nnn for（i = 0 ; i name,name） /p指针不空并且p-name不是要找的那个name则循环进行 p = p-next; if （!p） return NULL; /返回空指针 else return p; /返回指针p /*按学号查找*/ student *search2（char *number） student *p,*q; 16 ; p = HashTablei; if （p = NULL） /该地址上没有元素的情况 continue; /p等于下一个位置上的指针 else if （p-next = NULL） /该地址上只有1个元素的情况 if （s

7、trcmp（p-number,number） else /该地址上多于1个元素的情况 q = HashTablei; /此时p和q都是HashTablei number,number） /p指针不空并且p- q = p; /保持q在p的前面 else /p指针所指的结点 p-name就是要查找的name /如果直到i=16时才结束，正常结束，则没有找到该学号的学生 /*插入某指针指向的结点*/ void ins（student *q） location = strlen（q-name）; if （HashTablelocation = NULL） /此位置上还没有插入一个元素 HashTabl

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

9、1个元素的情况 q = HashTablelocation; /循环结束时已经找到要删的结点了 next = p- /删除p结点 /*插入*/ void Insert（） /插入完成 student *node;请输入要插入的同学的姓名（汉语拼音，字符不多于15个）: gets（name）;请输入要插入的同学的学号（不多于10位）: gets（number）; node = （student *）malloc（sizeof（struct student）; node- strcpy（node-name,name）; /复制字符串 number,number）; location = Hash（

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