云南大学软件学院数据结构实验7

1、云南大学软件学院 数据结构实验报告 实验难度： A B C 序号学号姓名成绩指导教师 （签名）学期：2017秋季学期 任课教师: 刘宇 实验题目: 组员及组长: 承担工作： 联系电话: 电子邮件: 完成提交时间： 年 月 日一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计等相关知识，对问题进行概要性地分析）（一）二叉排序树的查找算法及算法原理： 对给定的二叉排序树，如果想知道某元素是否在其中出现，可以和根结点比较，如果相等结束；如果不等，若比其大，进入右子树；否则进入左子树；继续按照上面的方法，直到出现相等或者到某分

2、支结束为止，返回查找信息。（二）哈希表的查找算法及其原理： 给定K值，根据造表时设定的哈希函数求得哈希地址，若表中此位置上没有记录，则查找不成功；否则比较关键字，若和给定值相等，则查找成功；否则根据造表时设定的处理冲突的方法找到“下一地址”，直至哈希表中某个位置为“空”或者表中所记录的关键字等于给定值时为止。二、【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的定义和基本操作说明，程序包含的模块以及各模块间的调用关系，关键算法伪码描述及程序流程图等，如有界面则需包括界面设计，功能说明等）抽象数据类型定义：typedef int KeyType;typedef struct c

3、har *name; int namenum;Name;typedef struct Name data; int pos;HashTable;typedef struct Hash /链地址结构 Name data; int pos; struct Hash *next;*Hash_P,Hash_L;typedef struct BSTNode KeyType key; struct BSTNode *lc,*rc;*BSTree;算法及各模块实现见第七部分【代码】调用关系：三、【实现（Implement）】(30%)（本部分应包括：抽象数据类型各操作的具体实现代码、 关键操作的具体算法实现

4、、 函数实现，主程序实现等，并给出关键算法的时间复杂度分析。如有界面则需包括界面的关键实现方法等。）具体实现代码见第七部分【代码】算法时间复杂度分析：哈希表查找: O(1)插入一个元素时，最坏情况下的时间复杂度为O（N），因为它有可能探测了N-1个元素！如果二叉排序树是平衡的，则n个节点的二叉排序树的高度为Log2n+1,其查找效率为O(Log2n)，近似于折半查找。如果二叉排序树完全不平衡，则其深度可达到n，查找效率为O(n)，退化为顺序查找。一般的，二叉排序树的查找性能在O(Log2n)到O(n)之间。四、【测试结果（Testing）】(10%)（本部分应包括：对实验的测试结果，应具体列出

5、每次测试所输入的数据以及输出的数据，并对测试结果进行分析，可附截图）主菜单：哈希表的线性探测查找：初始化：查找：显示：哈希表的二次探测查找：初始化：查找：显示：哈希表的链地址探测查找：初始化：查找：显示：建立二叉排序树：查询建立好的二叉排序树：查询成功：查询失败：删除元素：删除后查询：添加元素：插入后查询：退出：五、【实验总结】(10%)（本部分应包括：自己在实验中完成的任务，及存在的问题，所完成实验过程中的具体经验总结、心得）哈希表问题，在于存储位置和关键字之间建立对应关系f，根据对应关系f找到定值K。若结构中存在关键字和定值K相等的记录，必定在f（K）的存储位置上，由此可以省去比较过程，直

6、接找到所查记录。哈希表其实不难，课程设计考验的是我们的学习态度、独立思考问题、和解决问题的能力。在学习哈希表的过程中要注意对应关系和关键字的建立，并且要和二叉树结合学习，不然很容易出错。六、思考题或【项目运作描述（Operate）】(10%)（注：选择C难度的才需要填写“项目运作描述”，其他难度的只需完成思考题）（项目运作描述应包括：项目的成本效益分析，应用效果等的分析。）可以实现动态查找表中的二叉排序树的建立与查找，包括新结点的插入和删除等操作。通过哈希表的构造、查找和维护，能够对全年级的学生进行按姓名的哈希查找。采用链地址法：(1)拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突

7、，因此平均查找长度较短； (2)由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况； (3)开放定址法为减少冲突，要求装填因子较小，故当结点规模较大时会浪费很多空间。而拉链法中可取1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间； (4)在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行

8、删除操作，只能在被删结点上做删除标记，而不能真正删除结点七、【代码】(10%)（本部分应包括：完整的代码及充分的注释。 注意纸质的实验报告无需包括此部分。格式统一为，字体: Georgia , 行距: 固定行距12，字号: 小五）#include<stdio.h>#include<math.h>#include<conio.h>#include<malloc.h>#include<stdlib.h>#define NameNum 30 /人名个数#define HashNum 50 /哈希表的大小#define HashNum_L 1

9、7 /链地址查找哈希表大小#define dupSize 15 /二次探测数组的大小typedef int KeyType;typedef struct char *name; int namenum;Name;typedef struct Name data; int pos;HashTable;typedef struct Hash /链地址结构 Name data; int pos; struct Hash *next;*Hash_P,Hash_L;typedef struct BSTNode KeyType key; struct BSTNode *lc,*rc;*BSTree;voi

10、d InsertBST(BSTree *bst, KeyType key)/若在二叉排序树中不存在关键字等于key的元素，插入该元素 BSTree s; if(*bst=NULL) /递归结束条件 s=(BSTree)malloc(sizeof(BSTNode); /申请新的结点s s->key=key; s->lc=NULL; s->rc=NULL; *bst=s; else if (key < (*bst)->key) InsertBST(&(*bst)->lc),key); /将s插入左子树 else if (key > (*bst)-&

11、gt;key) InsertBST(&(*bst)->rc),key); /将s插入右子树void CreateBST(BSTree *bst) /从键盘输入元素的值，创建相应的二叉排序树 printf("建立二叉排序树：n"); KeyType key; *bst=NULL; scanf("%d",&key); while(key<10000) InsertBST(bst,key); scanf("%d",&key); printf("二叉排序树建立成功n");BSTree s

12、earch(KeyType k,BSTree root) BSTree p=root; while(p!=NULL) if(p->key=k) return p; /查找成功 else if(p->key>k) p=p->lc; /进入左子树查找 else if(p->key<k) p=p->rc; /进入右子树查找 return NULL;BSTNode *DelBST(BSTree t, KeyType k)/在二叉排序树t中删去关键字为k的结点 BSTNode *p,*f,*s,*q; p=t; f=NULL; while(p) /查找关键字为k

13、的待删结点p if(p->key=k ) break; /找到，则跳出查找循环 f=p; /f指向p结点的双亲结点 if(p->key>k) p=p->lc; else p=p->rc; if(p=NULL) printf("结点不存在，删除失败n"); return t; /若找不到，返回原来的二叉排序树 if(p->lc=NULL) /p无左子树 if(f=NULL) t=p->rc; /p是原二叉排序树的根 else if(f->lc=p) /p是f的左孩子 f->lc=p->rc; /将p的右子树链到f的左

14、链上 else /p是f的右孩子 f->rc=p->rc; /将p的右子树链到f的右链上 free(p); /释放被删除的结点p else /p有左子树 q=p; s=p->lc; while(s->rc) /在p的左子树中查找最右下结点 q=s; s=s->rc; if(q=p) q->lc=s->lc; /将s的左子树链到q上 else q->rc=s->lc; p->key=s->key; /将s的值赋给p free(s); printf("删除成功n"); return t;int menu_X()/

15、功能1：哈希表的线性探测查找menu int num; while(1) /system("cls"); /用于清屏 printf("n_线性探测_n"); printf("nt 1.初始化 2.线性探测查找"); printf("nt 3.显示 4.返回主页面n"); printf("n_n"); printf("请输入操作序号（1-4）："); scanf("%d",&num); fflush(stdin);/清空输入缓冲区 if(num<

16、;1|num>4) printf("输入操作数错误，请重新输入!"); getch(); else break; /while return num;int menu_T()/功能2：哈希表的二次探测查找menu int num; while(1) /system("cls"); /用于清屏 printf("n_二次探测_n"); printf("nt 1.初始化 2.二次探测查找"); printf("nt 3.显示 4.返回主页面n"); printf("n_n")

17、; printf("请输入操作序号（1-4）："); scanf("%d",&num); fflush(stdin); if(num<1|num>4) printf("输入操作数错误，请重新输入!"); getch(); else break; return num;int menu_L()/哈希表的链地址探测查找menu int num; while(1) /system("cls"); /用于清屏 printf("n_链地址探测_n"); printf("n1.

18、初始化 2.链地址探测查找n"); printf("3.显示 4.返回主页面n"); printf("n_n"); printf("请输入操作序号（1-4）："); scanf("%d",&num); fflush(stdin);/清空输入缓冲区 if(num<1|num>4) printf("输入操作数错误，请重新输入!"); getch(); else break; /while() return num;Name nameListNameNum;void in

19、itName()/初始化 char *name; nameL="chenjun" nameL="ganyu" nameL="chenjingjing" nameL="liuyinping" nameL="baifan" nameL="lijiayi" nameL="libaiyun" nameL="nim

20、iaomiao" nameL="liqin" nameL="liuhuijun" nameL="linmenghao" nameL="zhengweicong" nameL="liuyu" nameL="chenhailong" nameL="luojia" nameL="qinbo

21、" nameL="xurui" nameL="wangyuewei" nameL="liuxin" nameL="lihaomin" nameL="wangxiao" nameL="lishihan" nameL="yangyan" nameL="liweimo" na

22、meL="zhongjingyan" nameL="liujikao" nameL="liuzhufeng" nameL="chenhaozhen" nameL="sunyue" nameL="cuichunteng" for(int i=0;i<NameNum;i+) name=nameL; nameLnum=0;

23、 for(int j=0;*(name+j)!='0'j+) nameLnum+=*(name+j); printf("%dt",nameLnum); HashTable HashListHashNum;void initHashTable_X()/初始化哈希表 int pos; int d,count; /初始为空或 for(int n=0;n<HashNum;n+) HashL="" HashLnum=0; HashListn.pos=0

24、; /赋值 for(int i=0;i<NameNum;i+) count=1; pos=nameLnum%HashNum; /哈希函数 if(HashListpos.pos=0) HashListpos.data=nameListi; HashListpos.pos=1; / printf("不冲突！"); else d=pos; while (HashListd.pos!=0) / printf("冲突了！"); d=(d+1)%HashNum; count+; HashListd.data=nameListi; HashLi

25、std.pos=count; /printf("n冲突了%d次的人是%sn",count,nameL); printf("n初始化完毕！");int dupdupSize;void initHashTable_T() int pos; int d,count; int k=0; /初始为空或 for(int n=0;n<HashNum;n+) HashL="" HashLnum=0; HashListn.pos=0; for(int m=1;m<du

26、pSize/2;m+) dupk+=m*m; dupk+=-m*m; /赋值 for(int i=0;i<NameNum;i+) count=1; pos=nameLnum%HashNum; /哈希函数 if(HashListpos.pos=0) HashListpos.data=nameListi; HashListpos.pos=1; /printf("不冲突！"); else d=pos;k=0; while (HashListd.pos!=0) / printf("冲突了！"); d=(d+HashNum+dupk+)%H

27、ashNum; count+; HashListd.data=nameListi; HashListd.pos=count; / printf("n冲突了%d次的人是%sn",count,nameL); printf("n初始化完毕！");Hash_L HashList_LHashNum_L;void initHashTable_L() int pos,count=2; Hash_P p,q; for(int m=0;m<HashNum_L;m+) HashList_Lm.next=NULL; HashList_Lm.data.n

28、ame="" HashList_Lnum=0; HashList_Lm.pos=0; for(int i=0;i<NameNum;i+) pos=nameLnum%HashNum_L; count=2; if(HashList_Lpos.pos=0) /printf("nthe first if"); HashList_Lpos.data=nameListi; HashList_Lpos.pos=1; HashList_Lpos.next=NULL; / printf("-不冲突！");

29、else p=&HashList_Lpos; while (p->next!=NULL) p=p->next; count+; / printf("冲突了！"); q=(Hash_P)malloc(sizeof(Hash_L); q->next=p->next; p->next=q; q->data=nameListi; q->pos=count; / printf("n冲突了%d次的人是%sn",count,nameL); printf("初始化完毕！");void

30、 show() double ASL=0,sum=0; printf("t姓名tt关键字tt位置tt冲突次数n"); for(int i=0;i<HashNum;i+) if(HashListi.pos!=0) printf("%18s%10d%14d%18dn", HashL,HashLnum,i,HashListi.pos); sum+=HashListi.pos; ASL=sum/NameNum; printf("n线性探测查找的平均查找长度为：ASL=(%f)/(%d)=%f

31、n",sum,NameNum,ASL);void show_L() double ASL=0,sum=0; Hash_P p; printf("显示格式为：姓名/关键字/位置/冲突次数n"); for(int i=0;i<HashNum_L;i+) p=&HashList_Li; printf("第%d个位置:",i); while(p!=NULL) sum+=p->pos; printf("n -> %s / %d / %d / %d ", p->,p->data.n

32、amenum,i,p->pos); p=p->next; printf("n"); ASL=sum/NameNum; printf("n线性探测查找的平均查找长度为：ASL=(%f)/(%d)=%fn",sum,NameNum,ASL);void findName_X() char fname20=0; int findNum=0,fhashNum=0,d; printf("请输入学要查找的姓名（小写拼音的形式）："); scanf("%s",fname); for(int m=0;m<20;m+

33、) /求出姓名的拼音所对应的整数(关键字) findNum+=fnamem; printf("nfindNum is :%dn",findNum); fhashNum=findNum%HashNum; if(HashListfhashNnum=0) printf("该姓名不存在！"); else if(HashListfhashNnum=findNum) printf("该学生姓名为：%sn该学生关键字为：%dn该学生位置为：%dn 查找该学生冲突次数:%dn", HashListfha

34、shN,HashListfhashNnum,fhashNum,HashListfhashNum.pos); else d=fhashNum; while(HashLnum!=findNum) d=(d+1)%HashNum; printf("该学生姓名为：%sn该学生关键字为：%dn该学生位置为：%dn 查找该学生冲突次数:%dn", HashL,HashLnum,d,HashListd.pos); void findName_T() char

35、 fname20=0; int findNum=0,fhashNum=0,d,k=0; printf("请输入学要查找的姓名（小写拼音的形式）："); scanf("%s",fname); for(int m=0;m<20;m+) /求出姓名的拼音所对应的整数(关键字) findNum+=fnamem; printf("nfindNum is :%dn",findNum); fhashNum=findNum%HashNum; if(HashListfhashNnum=0) printf("该姓名

36、不存在！"); else if(HashListfhashNnum=findNum) printf("该学生姓名为：%sn该学生关键字为：%dn该学生位置为：%dn 查找该学生冲突次数:%dn", HashListfhashN,HashListfhashNnum,fhashNum,HashListfhashNum.pos); else d=fhashNum; while(HashLnum!=findNum) d=(d+dupk+HashNum)%HashNum; p

37、rintf("该学生姓名为：%sn该学生关键字为：%dn该学生位置为：%dn 查找该学生冲突次数:%dn", HashL,HashLnum,d,HashListd.pos); void findName_L() char fname20=0; int findNum=0,fhashNum=0,pos; Hash_P p; printf("请输入学要查找的姓名（小写拼音的形式）："); scanf("%s",fname); for(int m=0;m<20;m+) /求出姓名

38、的拼音所对应的整数(关键字) findNum+=fnamem; printf("nfindNum is :%dn",findNum); pos=findNum%HashNum_L; p=&HashList_Lpos; if(!p) printf("该姓名不存在！"); while (p&&p->num!=findNum) p=p->next; if (p->num=findNum) printf("该学生姓名为：%sn该学生关键字为：%dn该学生位置为：%dn 查找该

39、学生冲突次数:%dn", p->,p->num,pos,p->pos); int Menu() int n; printf("tt*n"); printf("tt*1-哈希表的线性探测查找-*n"); printf("tt*2-哈希表的二次探测查找-*n"); printf("tt*3-哈希表的链地址探测查找-*n"); printf("tt*4-建立二叉排序树-*n"); printf("tt*5-二叉排序树查找-*n&

40、quot;); printf("tt*6-二叉排序树删除-*n"); printf("tt*7-二叉排序树插入-*n"); printf("tt*0-退出-*n"); printf("tt*n"); printf("tt您的选择是："); scanf("%d",&n); return n;int main() int choose,choose1,n; KeyType k; /查找关键字 BSTree T; /二叉排序树 /BSTree *M; bool f1=false,f2=false; /f1判断有序表是否创建,f2判断二叉排序树是否创