数据结构实验报告七.doc

云南大学软件学院 数据结构实验报告 （本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助） 实验难度： A B C 序号学号姓名成绩120111120181董呢喃220111120143罗淑静3指导教师 （签名）学期：2010秋季学期 任课教师: 秦江龙 实验题目: 哈希表查找 小 组 长: 联系电话:电子邮件:2625802805 完成提交时间:2012年12月16日云南大学软件学院2010学年 秋季 学期数据结构实验成绩考核表学号： 20111120143 姓名： 罗淑静 本人承担角色： 程序设计、算法分析 评分项目评分指标分值得分实验构思（10%）1. 实验目的明确52. 实验内容理解透彻、对实验所涉及到的知识点分析到位5实验设计（15%）1. 有对基本数据结构的抽象数据类型定义52. 实验方案设计完整，数据结构、算法选择合理 53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图5实验实现（25%）1. 代码编写规范、风格统一、注释清楚易读 52. 程序运行正常，测试结果正确153. 界面友好、易于操作、有较强的容错性5实验报告撰写（10%）1. 内容详实无缺漏，文字流畅、图表清楚52. 实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考5个人工作量（30%）1. 个人完成工作量152. 个人技术水平103. 团队合作精神5实验运作（10%）1. 有一定用户群52. 应用前景分析5综合得分： （满分100分）指导教师： 年 月 日（注：此表在难度为C时使用，每个成员一份。）云南大学软件学院2010学年 秋季 学期数据结构实验成绩考核表学号： 20111120181 姓名： 董呢喃 本人承担角色： 算法分析、后期调试 评分项目评分指标分值得分实验构思（10%）1. 实验目的明确52. 实验内容理解透彻、对实验所涉及到的知识点分析到位5实验设计（15%）1. 有对基本数据结构的抽象数据类型定义52. 实验方案设计完整，数据结构、算法选择合理 53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图5实验实现（25%）1. 代码编写规范、风格统一、注释清楚易读 52. 程序运行正常，测试结果正确153. 界面友好、易于操作、有较强的容错性5实验报告撰写（10%）1. 内容详实无缺漏，文字流畅、图表清楚52. 实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考5个人工作量（30%）1. 个人完成工作量152. 个人技术水平103. 团队合作精神5实验运作（10%）1. 有一定用户群52. 应用前景分析5综合得分： （满分100分）指导教师： 年 月 日（注：此表在难度为C时使用，每个成员一份。）一、【实验构思（Conceive）】(10%)实现下列操作:构造空表、销毁表、搜索指定关键字的元素、插入新元素、删除指定关键字的元素、遍历表中所有元素。二、【实验设计(Design)】(20%)ADT DynamicSearchTable数据对象：D是具有相同特性的数据元素的集合，各个数据元素均含有类型相同，可唯一标识数据元素的关键字。数据关系：数据元素同属一个集合。基本操作：BSP InitBST(BiTree &T)操作结果：构造一棵空树BSP createBst(key)操作结果：建立一个二叉树结点void traverseBST(BSP T)操作结果：中序遍历（递归）动态查找表（二叉链表），并打印结点值BSP FindMin(BSP T)操作结果：找到关键字最小的结点，即最左边的节点int SearchBST(BiTree T,int key,BiTree f,BiTree &p)操作结果：在根指针T所指的二叉树中递归地查找其关键字等于key的元素，查找成功：指针p指向该结点，并返回TRUE，否则：p指向查找路径上访问的最后一个结点，即插入位置，并返回FALSEint InsertBST(BiTree &T,TElemType e) 当二叉树T中不存在关键字等于e.key的数据元素事，插入e并返回TRUE，否则返回FLASEint DeleteBST(BiTree &T,int key) 操作结果：查找树T中是否存在关键字等于key的数据元素，存在：删除，并返回TRUE，不存在：返回FALSEvoid DestoryBST(BiTree &T) 操作结果：销毁二叉树ADT DynamicSearchTable三、【实现描述（Implement）】(30%)1.抽象数据类型具体实现的函数原型说明:typedef int keytype; /定义关键字类型typedef struct Bnodekeytype data;struct Bnode *lchild,*rchild;BST,*BSP; / 定义树节点类型2.函数的调用关系：（在main函数中）int select=0,flag=1,a; /操作选择字符，循环控制字符，查找函数返回值接受符 T=NULL; while(flag) /操作选择 printf(1-创建2叉查找树n); printf(2-插入元素n); printf(3-查找元素n); printf(4-删除元素n); printf(5-删除表n); printf(6-退出n); printf(请选择操做n); scanf(%d,&select); switch(select) case 1: /创建二叉查找表 printf(请输入关键字,0结束n); scanf(%d,&key); while(key!=0) S=createBst(key); T=InsertBST(T,S); printf(请继续输入：); scanf(%d,&key); printf(查找表为n); traverseBST(T); printf(nn); break; case 2: /插入元素 printf(请输入要插入的元素；n); scanf(%d,&key); S=createBst(key); T=InsertBST(T,S); printf(n插入成功n); printf(插入的元素为：n); traverseBST(S); printf(nn); break; case 3: /查找元素 printf(请输入要查找的元素：n); scanf(%d,&key); a=Search(T,key); printf(nn); break; case 4: /删除元素 printf(请输入要删除的元素：n); scanf(%d,&key); DeleteBST(T,key); printf(nn); break; case 5:/销毁二叉查找表 DestroyBST(T); printf(删除成功); case 6: /退出 flag=0; break; 3、其中部分操作的伪码算法如下：1)BSP InitBST() BSP T; T-data=0; T-lchild=T-rchild=NULL; return T;2)void DestroyBST(BSP T) if(T) /中序删除各结点 DestroyBST(T-lchild); T-data=NULL; free(T); DestroyBST(T-rchild); 3)BSP createBst(keytype key) /建立一个二叉树结点 BSP s; s=(BSP)malloc(sizeof(BST); s-data=key; s-lchild=s-rchild=NULL; return s;4)BSP InsertBST(BSP T,BSP S) BSP p,q; if(T=NULL) return S; else p=T; q=NULL; while(p) /树不空时，依次查看 q=p; if(S-data=p-data) /找到与关键字相同的结点，返回 printf(该元素已在表中); return T; if(S-datadata) /关键字小于当前结点关键字，查看左孩子 p=p-lchild; else /否则查看右孩子 p=p-rchild; if(S-datadata) /关键字小于当前结点，插入做左孩子 q-lchild=S; else /否则插入做右孩子 q-rchild=S; return T; 5)int Search(BSP T,keytype x) BSP p; if(T=NULL) printf(error); else p=T; while(p) /树不空时，依次查找 if(p-data=x) printf(查找成功); return 0; else if(xdata) p=p-lchild; else p=p-rchild; if(!p) /树空表示没找到 printf(所找元素不存在); return 0;6)void traverseBST(BSP T) if(T) /中序遍历，打印关键字 traverseBST(T-lchild); printf(%d,T-data); traverseBST(T-rchild); 7)BSP FindMin(BSP T) /找到关键字最小的结点，即最左边的节点 if(T=NULL) return NULL; else if(T-lchild=NULL) return T; else return FindMin(T-lchild);8)BSP DeleteBST(BSP T,keytype x) keytype y; BSP p; if(T=NULL) printf(错误); else if(xdata) /关键字小于当前节点，则看左孩子 T-lchild=DeleteBST(T-lchild,x); else if(xT-data) /关键字大于当前节点，则看又孩子 T-rchild=DeleteBST(T-rchild,x); else if(T-lchild!=NULL&T-rchild!=NULL) /左右孩子都不空，则找到最小节点代替 p=FindMin(T-rchild); T-data=p-data; T-rchild=DeleteBST(T-rchild,T-data); else p=T; if(T-lchild=NULL) /左孩子空，则用右孩子代替 T=T-rchild; else if(T-rchild=NULL)/右孩子空，则用左孩子代替 T=T-lchild; free