数据结构查找实验报告

实验报告课程数据结构及算法试验项目8.查找成绩专业班级***指导教师***姓名***学号***试验日期***试验八查找一、试验目标掌握次序表查找中不一样查找方法查找思想，并能用C/C++语言实现。掌握树表查找中二叉排序树查找、平衡二叉树查找查找思想，并能用C/C++语言实现。掌握Hash表查找中查找思想，并能用C/C++语言实现。能够针对详细实际，灵活选取适宜查找方法。二、试验环境PC微机，Windows，DOS，TurboC或VisualC++三、试验内容1、二叉排序树查找（1）问题描述查找是计算机操作中一个主要应用技术，查找方法有许多，不一样查找方法有不一样查找效率，而二叉排序树查找就是效率较高查找方法之一。所谓二叉排序树，就是指将原来已经有数据依照大小组成一棵二叉树，二叉树中全部结点数据满足一定大小关系，全部左子树中结点均比根结点小，全部右子树中结点均比根结点大。二叉排序树查找是指按照二叉排序树中结点关系进行查找，查找关键字首先同树根结点进行比较，假如相等则查找成功；假如比根结点小，则在左子树中查找；假如比根结点大，则在右子树中进行查找。这种查找方法能够快速缩小查找范围，大大降低了查找关键字比较次数，从而提升了查找效率。（2）基本要求编程实现时，表现查找全过程，即二叉排序树创建、查找关键字输入、查找关键字查找、查找结果输出等。（3）算法实现#include<stdio.h>#include<stdlib.h>voidGetemptylist();//建立空树voidGetlist();//建立二叉排序树voidSortL();//排序voidConnectlist();//结点连接处理voidLookup();//查找typedefstructlist{intdata;structlist*left; structlist*right;}JD;JD*head;intL[20];intsize;intnum;intmain(){ Getemptylist(); Getlist(); Lookup(); return0;}//+*voidGetemptylist(){ printf("建立空树：\n"); head=(JD*)malloc(sizeof(JD)); head->left=NULL; head->right=NULL; if(!head) { printf("建立失败！\n"); exit(-1); } else { printf("建立成功！\n"); }}voidGetlist(){ inti; printf("建立二叉排序树：\n"); printf("请输入元素个数："); scanf("%d",&size); printf("请输入元素："); for(i=0;i<size;i++) { scanf("%d",&(L[i])); } SortL(); printf("二叉排序树建立中。。。。\n"); Connectlist();}voidSortL(){ inti,j; intmin; for(i=0;i<size;i++) { min=L[i]; for(j=i+1;j<size;j++) { if(L[j]<min) { min=L[j]; L[j]=L[i]; L[i]=min; } } } printf("排序后："); for(i=0;i<size;i++) { printf("%d",L[i]); } printf("\n");}voidConnectlist(){ intlow,high,mid; inti; JD*p,*q; p=(JD*)malloc(sizeof(JD)); p->left=NULL; p->right=NULL; low=0; high=size; mid=(low+high)/2; head->data=L[mid]; q=head; for(i=0;i<size;i++) { q=head;A1: if(L[i]<q->data) { if(q->left==NULL) { p->data=L[i]; q->left=p; p=(JD*)malloc(sizeof(JD)); p->left=NULL; p->right=NULL; } else { q=q->left; gotoA1; } } else { if(q->right==NULL) { p->data=L[i]; q->right=p; p=(JD*)malloc(sizeof(JD)); p->left=NULL; p->right=NULL; } else { q=q->right; gotoA1; } } } if(head->left==NULL&&head->right==NULL) { printf("二叉排序树建立失败！\n"); } else { printf("二叉排序树建立成功！\n"); }}voidLookup(){ inti; JD*q; printf("请输入查找元素："); scanf("%d",&num); q=head; for(;;) { if(num==q->data) { printf("查找成功，此元素为：%d,地址为：%d\n",q->data,q); break; } else { if(num<q->data) { if(q->left==NULL) { printf("查找失败，无此元素\n"); break; } else { q=q->left; } } else { if(q->right==NULL) { printf("查找失败，无此元素\n"); break; } else { q=q->right; } } } }}（4）运行截图2、通讯录管理（1）问题描述试编程完成通讯录通常性管理工作，如通讯录中统计增加、修改、查找、删除、输出等功效。每个统计包含姓名、电话号码、住址等个人基本信息。（2）基本要求将建立通讯录以磁盘文件形式存放，全部通讯录管理均以文件操作方式进行。在查找通讯录中统计时，以统计“姓名”为查找关键字进行查找。因为“姓名”是字符串类型数据，其查找过程比整形关键字查找过程要复杂，关键字比较过程可调用字符串函数，也能够自己实现其比较过程。算法实现#include<stdio.h>#include<stdlib.h>#include<string.h>#definesize50voidGetemptylist();//建立空表voidIncrease();//增加voidModify();//修改voidLookup();//查找voidDelete();//删除voidSee();//查看voidformat();//格式化typedefstructlist{charname[size];//姓名chartelenum[size];//电话charaddress[size];//地址}JD;JDUser[size];intmain(){inta;Getemptylist();A1:printf("请选择操作：\n1.增加2.修改\n3.查找4.删除\n5.查看6.退出\n7.格式化\n");scanf("%d",&a);switch(a){case1:Increase();break;//增加case2:Modify();break;//修改case3:Lookup();break;//查找case4:Delete();break;//删除case5:See();break;//查看case6:exit(1);break;//退出case7:format();break;default:printf("inputerror!\n");}gotoA1; return0;}//+*voidGetemptylist(){ printf("建立空表：\n"); if(!User) { printf("建立失败！\n"); exit(-1); } else { printf("建立成功！\n"); }}voidIncrease(){FILE*fp;inti=0;printf("请输入姓名：");scanf("%s",User[i].name);printf("请输入电话：");scanf("%s",User[i].telenum);printf("请输入地址：");scanf("%s",User[i].address);fp=fopen("D:\\通讯录.txt","a");fprintf(fp,"%6s%11s%6s",User[i].name,User[i].telenum,User[i].address);fclose(fp);printf("添加成功！\n");}voidModify(){FILE*fp;chara[size];inti,j;intx=1;fp=fopen("D:\\通讯录.txt","r");for(i=0;i<5;i++){fscanf(fp,"%6s%11s%6s",User[i].name,User[i].telenum,User[i].address);}fclose(fp);printf("请输入需要修改联络人姓名：");scanf("%s",a);for(i=0;i<5;i++){x=1;for(j=0;j<strlen(a)||j<strlen(User[i].name);j++){if(a[j]!=User[i].name[j]){x=0;break;}}if(x==1){printf("请输入修改后姓名：");scanf("%s",User[i].name);printf("请输入修改后电话：");scanf("%s",User[i].telenum);printf("请输入修改后地址：");scanf("%s",User[i].address);printf("修改成功！修改后：\n");printf("姓名电话地址\n");printf("%6s%11s%6s\n",User[i].name,User[i].telenum,User[i].address);break;}}if(x==1){fp=fopen("D:\\通讯录.txt","w");for(i=0;i<5;i++){fprintf(fp,"%6s%11s%6s",User[i].name,User[i].telenum,User[i].address);}fclose(fp);}if(x==0){printf("无此联络人！\n");}}voidLookup(){FILE*fp;chara[size];inti,j;intx=1;fp=fopen("D:\\通讯录.txt","r");for(i=0;i<5;i++){fscanf(fp,"%6s%11s%6s",User[i].name,User[i].telenum,User[i].address);}fclose(fp);printf("请输入想要查找联络人姓名：");scanf("%s",a);for(i=0;i<5;i++){x=1;for(j=0;j<strlen(a)||j<strlen(User[i].name);j++){if(a[j]!=User[i].name[j]){x=0;break;}}if(x==1){printf("查找成功！\n");printf("姓名电话地址\n");printf("%6s%11s%6s\n\n",User[i].name,User[i].telenum,User[i].address);break;}}if(x==0){printf("无此联络人！\n");}}voidDelete(){FILE*fp;JDmax[size];chara[size];inti,j,k;intx=1;fp=fopen("D:\\通讯录.txt","r");for(i=0;i<5;i++){fscanf(fp,"%6s%11s%6s",User[i].name,User[i].telenum,User[i].address);}fclose(fp);printf("请输入想要删除联络人姓名：");scanf("%s",a);for(i=0;i<5;i++){x=1;for(j=0;j<strlen(a)||j<strlen(User[i].name);j++){if(a[j]!=User[i].name[j]){x=0;break;}}if(x==1){k=0;for(j=0;j<size;j++){if(j==i){j++;}strcpy(max[k].name,User[j].name);strcpy(max[k].address,User[j].address);strcpy(max[k].telenum,User[j].telenum);k++;}for(j=0;j<size;j++){strcpy(User[j].name,max[j].name);strcpy(User[j].address,max[j].address);strcpy(User[j].telenum,max[j].telenum);}printf("删除成功！\n");break;}}if(x==1){fp=fopen("D:\\通讯录.txt","w");