查找实验报告

桃扇骨 2022-07-24 12:19 211阅读 0赞

**查找的有关操作：**

**一、实验目的**

1．掌握折半查找算法的思想及程序实现。

2．掌握二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现。

3．掌握散列存储结构的思想，能选择合适散列函数，实现不同冲突处理方法的散列表的查找、建立。

**二、实验仪器及环境：**

PC计算机；windows XP操作系统、VisualC++6.0、codeblocks10.05

# 三、实验内容及结果 #

1．利用实验一建立有序表，采用折半查找实现某一已知的关键字的查找。

2．随机产生一组关键字，利用二叉排序树的插入算法建立二叉排序树，然后删除某一指定关键字元素。

\*3．建立ＡＶＬ树并实现删除某一指定关键字元素。

4．已知散列函数为H(key)=key%p（p为自定的常数），冲突处理方法分别为线性探测法、外拉链法实现散列表的建立（利用插入算法实现）。

**第一题代码实现：**

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    
    #define Maxsize 100
    #define EQ(a,b) (!strcmp((a),(b)))
    #define LT(a,b) (strcmp((a),(b))<0)
    #define GT(a,b) (strcmp((a),(b))>0)
    #define LQ(a,b) (strcmp((a),(b))<=0)
    
    using namespace std;
    
    typedef char*KeyType;
    typedef struct
    {
        KeyType key;
        char name[20];
        char sex;
        float score[10];
    }SElemType;
    
    typedef struct
    {
        SElemType *elem;
        int length;
    }SSTable;
    
    void Create(SSTable &L)
    {
        L.elem=(SElemType *)malloc(Maxsize*sizeof(SElemType));
        L.length=0;
        int i=1;
        printf("Please Input the Sno of Students:\n");
        L.elem[i].key=(char *)malloc(20*sizeof(char));
        scanf("%s",L.elem[i].key);
        while(!EQ(L.elem[i].key,"0000"))
        {
            printf("Please Input the Name,Sex and Three Scores:\n");
            scanf("%s",L.elem[i].name);
            scanf(" %c",&L.elem[i].sex);
            for(int j=0;j<3;j++)
            scanf("%f",&L.elem[i].score[j]);
    
            i++;
            L.length++;
            printf("Please Input the Sno of Students:\n");
            L.elem[i].key=(char *)malloc(20*sizeof(char));
            scanf("%s",L.elem[i].key);
        }
    }
    
    int Search_Seq(SSTable L,KeyType key)
    {
        L.elem[0].key=key;
    ///    int i=L.length;
    ///   for(i=L.length;!EQ(L.elem[i].key,key);i--);
    ///    return i;
        int i=L.length;
        while(i>=0)
        {
            if(EQ(L.elem[i].key,key))
            {
                return i;
            }
            i--;
        }
    }
    
    int Search_Bin(SSTable L,KeyType key) ///已知原序列递增
    {
        int low,high,mid;
        low=1;
        high=L.length;
        while(low<=high)
        {
            mid=(low+high)/2;
            if(EQ(L.elem[mid].key,key))
            {
                return mid;
            }
            else if(LT(L.elem[mid].key,key))
            {
                low=mid+1;
            }
            else
            {
                high=mid-1;
            }
            //cout<<low<<" "<<mid<<" "<<high<<" ";
        }
        return 0;
    }
    int main()
    {
        SSTable L;
        Create(L);
        printf("Create Over!\n");
        int flag=Search_Bin(L,"224128"); ///二分查找和学号224128去匹配
        ///int flag=Search_Seq(L,"224128"); ///顺序查找和学号224128去匹配
        printf("flag=%d\n",flag);
        if(flag!=0)
        {
            printf("记录存在，位置为：%d\n",flag);
            printf("记录为：\n");
            printf("学号：%s 姓名：%s 性别：%c \n",L.elem[flag].key,L.elem[flag].name,L.elem[flag].sex);
            printf("成绩为：%.2f %.2f %.2f\n",L.elem[flag].score[0],L.elem[flag].score[1],L.elem[flag].score[2]);
        }
        else printf("记录不存在！\n");
        return 0;
    }
    
    /*测试样例
    224127
    DaMing f 98 95.0 67
    224128
    LiHong m 78 99.00 66
    224129
    LingLing f 88 90 67
    224220
    Xiaohua m 90 78 97
    224221
    BenXiong f 89 88.0 78
    224222
    KaiXin m 77.0 67 23 
    0000
    */