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

《云南大学软件学院数据结构实验7》由会员分享，可在线阅读，更多相关《云南大学软件学院数据结构实验7（50页珍藏版）》请在装配图网上搜索。

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

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

3、*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#include#include#include#include#define NameNum 30 /人名个数#define HashNum 50 /哈希表的大小#define HashNum_L 17 /链地址查找哈希表大小#define dupSize 15 /二次探测数组的大小typedef int KeyType;typedef struct cha

9、r *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;void InsertBST(BSTree *bst, KeyType key)/若在二叉排序树中不存在核心字等于key的元素，插入该元素 BSTree s; if(

10、*bst=NULL) /递归结束条件 s=(BSTree)malloc(sizeof(BSTNode); /申请新的结点s s-key=key; s-lc=NULL; s-rc=NULL; *bst=s; else if (key key) InsertBST(&(*bst)-lc),key); /将s插入左子树 else if (key (*bst)-key) InsertBST(&(*bst)-rc),key); /将s插入右子树void CreateBST(BSTree *bst) /从键盘输入元素的值，创立相应的二叉排序树 printf(建立二叉排序树：n); KeyType key;

11、 *bst=NULL; scanf(%d,&key); while(keykey=k) return p; /查找成功 else if(p-keyk) p=p-lc; /进入左子树查找 else if(p-keyrc; /进入右子树查找 return NULL;BSTNode *DelBST(BSTree t, KeyType k)/在二叉排序树t中删去核心字为k的结点 BSTNode *p,*f,*s,*q; p=t; f=NULL; while(p) /查找核心字为k的待删结点p if(p-key=k ) break; /找到，则跳出查找循环 f=p; /f指向p结点的双亲结点 if(p-

12、keyk) 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的左链上 else /p是f的右孩子 f-rc=p-rc; /将p的右子树链到f的右链上 free(p); /释放被删除的结点p else /p有左子树 q=p; s=p-lc; while(s-rc) /在p的左子树中查找最右下结

13、点 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()/功能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(

14、%d,&num); fflush(stdin);/清空输入缓冲区 if(num4) 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); printf(请输入操作序号（1-4）：); scanf(%d,&num); ff

15、lush(stdin); if(num4) printf(输入操作数错误，请重新输入!); getch(); else break; return num;int menu_L()/哈希表的链地址探测查找menu int num; while(1) /system(cls); /用于清屏 printf(n_链地址探测_n); printf(n1.初始化 2.链地址探测查找n); printf(3.显示 4.返回主页面n); printf(n_n); printf(请输入操作序号（1-4）：); scanf(%d,&num); fflush(stdin);/清空输入缓冲区 if(num4) pr

16、intf(输入操作数错误，请重新输入!); getch(); else break; /while() return num;Name nameListNameNum;void initName()/初始化 char *name; nameList0.name=chenjun; nameList1.name=ganyu; nameList2.name=chenjingjing; nameList3.name=liuyinping; nameList4.name=baifan; nameList5.name=lijiayi; nameList6.name=libaiyun; nameList7.

17、name=nimiaomiao; nameList8.name=liqin; nameList9.name=liuhuijun; nameList10.name=linmenghao; nameList11.name=zhengweicong; nameList12.name=liuyu; nameList13.name=chenhailong; nameList14.name=luojia; nameList15.name=qinbo; nameList16.name=xurui; nameList17.name=wangyuewei; nameList18.name=liuxin; nam

18、eList19.name=lihaomin; nameList20.name=wangxiao; nameList21.name=lishihan; nameList22.name=yangyan; nameList23.name=liweimo; nameList24.name=zhongjingyan; nameList25.name=liujikao; nameList26.name=liuzhufeng; nameList27.name=chenhaozhen; nameList28.name=sunyue; nameList29.name=cuichunteng; for(int i

19、=0;iNameNum;i+) name=nameListi.name; nameListi.namenum=0; for(int j=0;*(name+j)!=0;j+) nameListi.namenum+=*(name+j); printf(%dt,nameListi.namenum); HashTable HashListHashNum;void initHashTable_X()/初始化哈希表 int pos; int d,count; /初始为空或 for(int n=0;nHashNum;n+) HashListn.data.name=; HashListn.data.namen

20、um=0; HashListn.pos=0; /赋值 for(int i=0;iNameNum;i+) count=1; pos=nameListi.namenum%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; HashListd.pos

21、=count; /printf(n冲突了%d次的人是%sn,count,nameListi.name); printf(n初始化完毕！);int dupdupSize;void initHashTable_T() int pos; int d,count; int k=0; /初始为空或 for(int n=0;nHashNum;n+) HashListn.data.name=; HashListn.data.namenum=0; HashListn.pos=0; for(int m=1;mdupSize/2;m+) dupk+=m*m; dupk+=-m*m; /赋值 for(int i=0

22、;iNameNum;i+) count=1; pos=nameListi.namenum%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+)%HashNum; count+; HashListd.data=nameListi; HashListd.pos=count; / printf(n冲突了%d

23、次的人是%sn,count,nameListi.name); printf(n初始化完毕！);Hash_L HashList_LHashNum_L;void initHashTable_L() int pos,count=2; Hash_P p,q; for(int m=0;mHashNum_L;m+) HashList_Lm.next=NULL; HashList_Lm.data.name=; HashList_Lm.data.namenum=0; HashList_Lm.pos=0; for(int i=0;inext!=NULL) p=p-next; count+; / printf(冲

24、突了！); 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,nameListi.name); printf(初始化完毕！);void show() double ASL=0,sum=0; printf(t姓名tt核心字tt位置tt冲突次数n); for(int i=0;iHashNum;i+) if(HashListi.pos!=0) printf(%18s%10d%14d%18dn, HashListi.d

25、ata.name,HashListi.data.namenum,i,HashListi.pos); sum+=HashListi.pos; ASL=sum/NameNum; printf(n线性探测查找的平均查找长度为：ASL=(%f)/(%d)=%fn,sum,NameNum,ASL);void show_L() double ASL=0,sum=0; Hash_P p; printf(显示格式为：姓名/核心字/位置/冲突次数n); for(int i=0;ipos; printf(n - %s / %d / %d / %d , p-data.name,p-data.namenum,i,p-

26、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;m20;m+) /求出姓名的拼音所相应的整数(核心字) findNum+=fnamem; printf(nfindNum is :%dn,findNum)

27、; fhashNum=findNum%HashNum; if(HashListfhashNum.data.namenum=0) printf(该姓名不存在！); else if(HashListfhashNum.data.namenum=findNum) printf(该学生姓名为：%sn该学生核心字为：%dn该学生位置为：%dn 查找该学生冲突次数:%dn, HashListfhashNum.data.name,HashListfhashNum.data.namenum,fhashNum,HashListfhashNum.pos); else d=fhashNum; while(HashLi

28、std.data.namenum!=findNum) d=(d+1)%HashNum; printf(该学生姓名为：%sn该学生核心字为：%dn该学生位置为：%dn 查找该学生冲突次数:%dn, HashListd.data.name,HashListd.data.namenum,d,HashListd.pos); void findName_T() char fname20=0; int findNum=0,fhashNum=0,d,k=0; printf(请输入学要查找的姓名（小写拼音的形式）：); scanf(%s,fname); for(int m=0;m20;m+) /求出姓名的拼音

29、所相应的整数(核心字) findNum+=fnamem; printf(nfindNum is :%dn,findNum); fhashNum=findNum%HashNum; if(HashListfhashNum.data.namenum=0) printf(该姓名不存在！); else if(HashListfhashNum.data.namenum=findNum) printf(该学生姓名为：%sn该学生核心字为：%dn该学生位置为：%dn 查找该学生冲突次数:%dn, HashListfhashNum.data.name,HashListfhashNum.data.namenum,

30、fhashNum,HashListfhashNum.pos); else d=fhashNum; while(HashListd.data.namenum!=findNum) d=(d+dupk+HashNum)%HashNum; printf(该学生姓名为：%sn该学生核心字为：%dn该学生位置为：%dn 查找该学生冲突次数:%dn, HashListd.data.name,HashListd.data.namenum,d,HashListd.pos); void findName_L() char fname20=0; int findNum=0,fhashNum=0,pos; Hash_

31、P p; printf(请输入学要查找的姓名（小写拼音的形式）：); scanf(%s,fname); for(int m=0;mdata.namenum!=findNum) p=p-next; if (p-data.namenum=findNum) printf(该学生姓名为：%sn该学生核心字为：%dn该学生位置为：%dn 查找该学生冲突次数:%dn, p-data.name,p-data.namenum,pos,p-pos); int Menu() int n; printf(tt*n); printf(tt*1-哈希表的线性探测查找-*n); printf(tt*2-哈希表的二次探测查

32、找-*n); printf(tt*3-哈希表的链地址探测查找-*n); printf(tt*4-建立二叉排序树-*n); printf(tt*5-二叉排序树查找-*n); 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=f

33、alse,f2=false; /f1判断有序表与否创立,f2判断二叉排序树与否创立 while(1) choose=Menu(); choose1=0; switch(choose) case 1: system(cls); while (choose1!=4) system(cls); choose1=menu_X(); switch(choose1) case 1: initName(); initHashTable_X(); getch(); break; case 2: findName_X(); getch(); break; case 3: show(); getch(); bre

34、ak; case 4: break; break; case 2: system(cls); while (choose1!=4) system(cls); choose1=menu_T(); switch(choose1) case 1: initName(); initHashTable_T(); getch(); break; case 2: findName_T(); getch(); break; case 3: show(); getch(); break; case 4: break; break; case 3: system(cls); while (choose1!=4)

35、system(cls); choose1=menu_L(); switch(choose1) case 1: initName(); initHashTable_L(); getch(); break; case 2: findName_L(); getch(); break; case 3: show_L(); getch(); break; case 4: break; break; case 4: system(cls); printf(从键盘输入元素的值，创立相应的二叉排序树（输入不小于等于10000则退出输入）n); CreateBST(&T); f2=true; break; case 5: system(cls); if(f2=true) printf(请输入查找的核心字：n); scanf(%d,&k); if(search(k,T)!=NULL) printf(查找成功。n); else printf(查找失败。n); else printf(二叉排序树不存在n); break; case 6: system(cls); if(f2=true) printf(请输入删除的核心字：n); scanf(%d,&k); T=DelBST(T,k); else printf(二叉排序树不存在n