数据结构 查找 静态查找表算法 折半查找 二叉排序树查找算法 实验报告

实验内容：
基本内容：
算法1：采用顺序存储结构创建静态查找表，对查找表进行顺序查找和改进的顺序查找，并对其查找效率进行比较；
算法2：采用顺序存储结构创建静态查找表——有序表，对有序表进行二分查找；
选作内容：
编程实现按二叉排序树算法进行查找。

静态查找表算法（未改进）：
代码：

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100typedef int keytype;
typedef struct
{
      keytype key;int info;
}ElemType;typedef  struct 
{
      ElemType  elem[MAXSIZE];int  length;
}Sstable;int Search_Seq(Sstable ST,keytype key)
{
    int i=1;while(i<=ST.length){
    if(key==ST.elem[i].key){
    return i;}i++;}
}void Create(Sstable &ST,int n)
{
    int i;printf("输入元素："); for(i=1;i<=n;i++)scanf("%d",&ST.elem[i].key);
} int main()
{
    Sstable ST;keytype key;int i;printf("输入长度：");scanf("%d",&ST.length);Create(ST,ST.length);while(1){
    printf("输入要查找的元素：");scanf("%d",&key);i=Search_Seq(ST,key);if(i) printf("元素位置在：%d\n",i);else  printf("元素不存在\n");		}
} 

运行结果：

静态查找表算法（改进）：
代码：

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100typedef int keytype;
typedef struct
{
      keytype key;int info;
}ElemType;typedef  struct 
{
      ElemType  elem[MAXSIZE];int  length;
}Sstable;int Search_Seq(Sstable ST,keytype key)
{
    int i=ST.length;ST.elem[0].key=key;while(i>=0){
    if(key==ST.elem[i].key){
    return i;}i--;}
}void Create(Sstable &ST,int n)
{
    int i;printf("输入元素："); for(i=1;i<=n;i++)scanf("%d",&ST.elem[i].key);
} int main()
{
    Sstable ST;keytype key;int i;printf("输入长度：");scanf("%d",&ST.length);Create(ST,ST.length);while(1){
    printf("输入要查找的元素：");scanf("%d",&key);i=Search_Seq(ST,key);if(i) printf("元素位置在%d\n",i);else  printf("元素不存在\n");		}
} 

运行结果：

折半查找：
代码：

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100typedef int keytype;
typedef struct
{
      keytype key;int info;
}ElemType;typedef  struct 
{
      ElemType  elem[MAXSIZE];int  length;
}Sstable;int Search_Bin(Sstable ST,keytype key)
{
    int low,high,mid;low=1;high=ST.length;while(low<=high){
    mid=(low+high)/2;if(key==ST.elem[mid].key) return mid;else if(key<ST.elem[mid].key) high=mid-1;else low=mid+1;}return 0;
}void Create(Sstable &ST,int n)
{
    int i;printf("输入元素："); for(i=1;i<=n;i++)scanf("%d",&ST.elem[i].key);
} int main()
{
    Sstable ST;keytype key;int i;printf("输入长度：");scanf("%d",&ST.length);Create(ST,ST.length);while(1){
    printf("输入要查找的元素：");scanf("%d",&key);i=Search_Bin(ST,key);if(i) printf("元素位置在：%d\n",i);else  printf("元素不存在\n");		}
} 

运行结果：

选做（二叉排序树查找）：

#include<stdio.h> 
#include<stdlib.h>
#define OVERFLOW -2
#define OK 1
#define TRUE 1
#define ERROR 0
#define FALSE 0
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))typedef int Status;typedef struct Volunteer {
    int key;char name[15];char phoneNo[11];
}ElemType;typedef struct BiNode{
    ElemType data;struct BiNode *lchild,*rchild;
}BiNode, *BiTree;Status SearchBST(BiTree T,int key,BiTree f,BiTree &p)
{
    if(!T){
    p=f;return FALSE;}else if(EQ(key,T->data.key)){
    p=T;return TRUE;}else if LT(key,T->data.key){
    return SearchBST(T->lchild,key,T,p);}elsereturn SearchBST(T->rchild,key,T,p);
}Status InsertBST(BiTree &T,ElemType e)
{
    BiTree s,p;if(!SearchBST(T,e.key,NULL,p)){
    if(!(s=(BiTree)malloc(sizeof(BiNode))))exit(OVERFLOW);s->data=e;s->lchild=s->rchild=NULL;if(!p){
    T=s;}else if LT(e.key,p->data.key){
    p->lchild=s;}else {
    p->rchild=s;}return TRUE;}elsereturn FALSE;} 
Status Delete(BiTree &p)
{
    BiTree q,s;if(!p->rchild){
    q=p;p=p->lchild;free(q);}else if(!p->lchild){
    q=p;p=p->rchild;free(q);}else{
    q=p;s=p->lchild;while(s->rchild){
    q=s;s=s->rchild;}p->data=s->data;if(q!=p){
    q->rchild=s->lchild;}else{
    q->lchild=s->lchild;}free(s);return TRUE;} 
}Status DeleteBST(BiTree &T,int key)
{
    if(!T){
    return ERROR;}else {
    if(EQ(key,T->data.key)){
    Delete(T);}else if(LT(key,T->data.key)){
    return DeleteBST(T->lchild,key);}else{
    return DeleteBST(T->rchild,key);}}
}void InOrderTraverse(BiTree T)
{
    if(T){
    InOrderTraverse(T->lchild);printf("%d\t%s\t%s\n",T->data.key,T->data.name,T->data.phoneNo);InOrderTraverse(T->rchild);}
}void showmenu()
{
    printf("******欢迎进入志愿者信息管理系统******\n");printf("* 1:我要报名 *\n");printf("* 2:我要取消报名 *\n");printf("* 3:我想知道关心的同伴是否也报名了 *\n");printf("* 4:看看全部的报名信息 *\n");printf("* 5:退出系统 *\n");printf("* 请选择你所要执行的操作（1-5） *\n");printf("**************************************\n");
}
int main()
{
    BiTree T=NULL,p=NULL;ElemType e;int no,flag,st;while(1){
    showmenu();scanf("%d",&flag);switch(flag){
    case 1:printf("请输入你的学号，姓名和联系方式，用空格隔开！\n");printf("\n");scanf("%d%s%s",&e.key,e.name,e.phoneNo);InsertBST(T,e);printf("\n");printf("报名成功，你是一个有爱心的同学，为你点赞！\n");printf("\n");break;case 2:if(!T){
    printf("请先报名，再操作！\n");break;}printf("请输入你的学号： ");scanf("%d",&no);DeleteBST(T,no);printf("\n");printf("你的报名信息已删除，不过欢迎你随时加入我们志愿者团队哦！\n");printf("\n");break;case 3:if(!T){
    printf("二叉排序树还未建立，请先建立后再操作！\n");break;}printf("请输入你关心的同伴的学号：");scanf("%d",&no);st=SearchBST(T,no,NULL,p);if(st){
    printf("\n");printf("你关心的同学已经报名，快来报名加入我们的志愿者活动吧！\n");printf("\n");}else{
    printf("\n");printf("你关心的同伴还未报名，快邀请同伴一起加入我们的志愿队伍吧！\n");printf("\n");}break;case 4:printf("已报名的志愿者信息为：\n");printf("\n");InOrderTraverse(T);printf("\n");break;case 5:exit (0);default :printf("输入非法，请输入数字1-5！\n");fflush(stdin);}}
}