数据结构-查找-实验报告

实 验 报 告课 程数据结构及算法实验项目8.查找成 绩专业班级*指导教师*姓 名*学号*实验日期*实验八 查找一、实验目的1、 掌握顺序表查找中不同查找方法的查找思想，并能用C/C+语言实现。2、 掌握树表查找中二叉排序树查找、平衡二叉树查找的查找思想，并能用C/C+语言实现。3、 掌握Hash表查找中的查找思想，并能用C/C+语言实现。4、 能够针对具体实际，灵活选用适宜的查找方法。二、实验环境PC微机，Windows，DOS，Turbo C或Visual C+三、实验内容1、二叉排序树查找（1）问题描述查找是计算机操作中的一种重要应用技术，查找的方法有许多，不同的查找方法有不同的查找效率，而二叉排序树查找就是效率较高的查找方法之一。 所谓二叉排序树，就是指将原来已有数据根据大小构成一棵二叉树，二叉树中的所有结点数据满足一定的大小关系，所有左子树中的结点均比根结点小，所有右子树中的结点均比根结点大。 二叉排序树查找是指按照二叉排序树中结点的关系进行查找，查找关键字首先同树根结点进行比较，如果相等则查找成功；如果比根结点小，则在左子树中查找；如果比根结点大，则在右子树中进行查找。这种查找方法可以快速缩小查找范围，大大减少了查找关键字的比较次数，从而提高了查找效率。（2）基本要求编程实现时，体现查找的全过程，即二叉排序树的创建、查找关键字的输入、查找关键字的查找、查找结果的输出等。（3）算法实现#include#includevoid Getemptylist(); / 建立空树void Getlist(); / 建立二叉排序树void SortL(); / 排序void Connectlist(); / 结点连接处理void Lookup(); / 查找typedef struct list int data; struct list *left;struct list *right;JD;JD *head;int L20;int size;int num;int main()Getemptylist();Getlist();Lookup();return 0;/+*void Getemptylist()printf(建立空树：n);head=(JD*)malloc(sizeof(JD);head-left = NULL;head-right = NULL;if(!head)printf(建立失败！n);exit(-1);elseprintf(建立成功！n);void Getlist()int i;printf(建立二叉排序树：n);printf(请输入元素个数：);scanf(%d,&size);printf(请输入元素：);for(i = 0;i size;i+)scanf(%d,&(Li);SortL();printf(二叉排序树建立中。n);Connectlist();void SortL()int i,j;int min;for(i = 0;i size;i+)min = Li;for(j = i + 1;j size;j+)if(Lj min)min = Lj;Lj = Li;Li = min;printf(排序后：);for(i = 0;i left = NULL;p-right = NULL;low = 0;high = size;mid = (low + high) / 2;head-data = Lmid;q = head;for(i = 0;i size;i+)q = head;A1:if(Li data)if(q-left = NULL)p-data = Li;q-left = p;p=(JD*)malloc(sizeof(JD);p-left = NULL;p-right = NULL;elseq = q-left;goto A1;elseif(q-right = NULL)p-data = Li;q-right = p;p=(JD*)malloc(sizeof(JD);p-left = NULL;p-right = NULL;elseq = q-right;goto A1;if(head-left = NULL & head-right = NULL)printf(二叉排序树建立失败！n);elseprintf(二叉排序树建立成功！n);void Lookup()int i;JD *q;printf(请输入查找元素：);scanf(%d,&num);q = head;for(;)if(num = q-data)printf(查找成功，此元素为：%d,地址为：%dn,q-data,q);break;elseif(num data)if(q-left = NULL)printf(查找失败，无此元素n);break;elseq = q-left;elseif(q-right = NULL)printf(查找失败，无此元素n);break;elseq = q-right;（4）运行截图2、通讯录的管理（1）问题描述试编程完成通讯录的一般性管理工作，如通讯录中记录的增加、修改、查找、删除、输出等功能。每个记录包含姓名、电话号码、住址等个人基本信息。（2）基本要求将建立的通讯录以磁盘文件的形式存储，所有的通讯录管理均以文件操作的方式进行。在查找通讯录中的记录时，以记录的“姓名”为查找关键字进行查找。由于“姓名”是字符串类型的数据，其查找过程比整形关键字的查找过程要复杂，关键字比较过程可调用字符串函数，也可以自己实现其比较过程。（3） 算法实现#include#include#include#define size 50void Getemptylist(); / 建立空表void Increase(); / 增加void Modify(); / 修改void Lookup(); / 查找void Delete(); / 删除void See(); / 查看void format(); / 格式化typedef struct list char namesize; / 姓名 char telenumsize; / 电话 char addresssize; / 地址JD;JD Usersize;int main() int a; Getemptylist();A1: printf(请选择操作：n1.增加 2.修改n3.查找 4.删除n5.查看 6.退出n7.格式化n); scanf(%d,&a); switch(a) case 1:Increase();break; / 增加 case 2:Modify();break; / 修改 case 3:Lookup();break; / 查找 case 4:Delete();break; / 删除 case 5:See();break; / 查看 case 6:exit(1);break; / 退出 case 7:format();break; default:printf(input error!n); goto A1;return 0;/+*void Getemptylist()printf(建立空表：n);if(!User)printf(建立失败！n);exit(-1);elseprintf(建立成功！n);void Increase() FILE *fp; int i = 0; printf(请输入姓名：); scanf(%s,U); printf(请输入电话：); scanf(%s,Useri.telenum); printf(请输入地址：); scanf(%s,Useri.address); fp = fopen(D:通讯录.txt,a); fprintf(fp,%6s%11s%6s,U,Useri.telenum,Useri.address); fclose(fp); printf(添加成功！n);void Modify() FILE *fp; char asize; int i,j; int x = 1; fp = fopen(D:通讯录.txt,r); for(i = 0;i 5;i+) fscanf(fp,%6s%11s%6s,U,Useri.telenum,Useri.address); fclose(fp); printf(请输入需要修改的联系人的姓名：); scanf(%s,a); for(i = 0;i 5;i+) x = 1; for(j = 0;j strlen(a) | j strlen(U);j+) if(aj != Uj) x = 0; break; if(x = 1) printf(请输入修改后的姓名：); scanf(%s,U); printf(请输入修改后的电话：); scanf(%s,Useri.telenum); printf(请输入修改后的地址：); scanf(%s,Useri.address); printf(修改成功！修改后：n); printf(姓名 电话 地址n); printf(%6s %11s %6sn,U,Useri.telenum,Useri.address); break; if(x= 1) fp = fopen(D:通讯录.txt,w); for(i = 0;i 5;i+) fprintf(fp,%6s%11s%6s,U,Useri.telenum,Useri.address); fclose(fp); if(x = 0) printf(无此联系人！n); void Lookup() FILE *fp; char asize; int i,j; int x = 1; fp = fopen(D:通讯录.txt,r); for(i = 0;i 5;i+) fscanf(fp,%6s%11s%6s,U,Useri.telenum,Useri.address); fclose(fp); printf(请输入想要查找的联系人的姓名：); scanf(%s,a); for(i = 0;i 5;i+) x = 1; for(j = 0;j strlen(a) | j strlen(U);j+) if(aj != Uj) x = 0; break; if(x = 1) printf(查找成功！n); printf(姓名 电话 地址n); printf(%6s %11s %6snn,U,Useri.telenum,Useri.address); break; if(x = 0) printf(无此联系人！n); void Delete() FILE *fp; JD maxsize; char asize; int i,j,k; int x = 1; fp = fopen(D:通讯录.txt,r); for(i = 0;i 5;i+) fscanf(fp,%6s%11s%6s,U,Useri.telenum,Useri.address); fclose(fp); printf(请输入想要删除的联系人的姓名：); scanf(%s,a); for(i = 0;i 5;i+) x = 1; for(j = 0;j strlen(a) | j strlen(U);j+) if(aj != Uj) x = 0; break; if(x = 1) k = 0; for(j = 0;j size;j+) if(j = i) j+; strcpy(,U); strcpy(maxk.address,Userj.address); strcpy(maxk.telenum,Userj.telenum); k+; for(j = 0;j size;j+) strcpy(U,); strcpy(Userj.address,maxj.address); strcpy(Userj.telenum,maxj.telenum); printf(删除成功！n); break; if(x= 1) fp = fopen(D:通讯录.txt,w); for(i = 0;i 5;i+) fprintf(fp,%6s%11s%6s,U,Useri.telenum,Useri.address); fclose(fp); if(x = 0) printf(无此联系人！n); void See() FILE *fp; int i; fp = fopen(D:通讯录.txt,r); for(i = 0;i 5;i+) fscanf(fp,%6s%11s%6s,U,Useri.telenum,Useri.address); fclose(fp); printf(姓名 电话 地址n); for(i