-->
当前位置:首页 > 实验 > 正文内容

数据结构实验:查找算法

Luz5年前 (2019-12-09)实验3774
  1. 实验题目:查找算法(验证实验)
  2. 需求分析:

    本演示程序在TC2.0环境下编写调试,完成顺序查找、折半查找和二叉排序树查找等操作。

    输入的形式和输入值的范围。键盘输入相应的数字选择需要的步骤

    首先选择静态查找或动态查找。

    执行顺序查找,从表的一段开始,顺序扫描线性表,依次将扫描到的节点关键字和给定值K比较若当前扫描到的节点关键字和K相同,则扫描成功;若扫描结束后仍未找到关键字等于K的节点,则扫描失败。

    折半查找要求线性表为有序表,即表中节点按关键字有序,并要用向量作为表的存贮结构。

    二叉排序树定义:二叉排序树后者是空树或满足如下条件的二叉树:

    1. 静态查找中依次输入1,10,15,9,154,35,10,-1,生成一个单链表
    2. 动态查找中依次输入10,15,20,3,5,78,65,14,-1,生成一个单链表
    3. 顺序查找中输入15 ,查找15的位置
    4. 顺序查找(设监视哨)中输入154, 查找154的位置
    5. 折半查找输入10 ,查找10的位置
    6. 二叉排序树删除5,输出删除完后的二叉树
    7. 二叉排序树插入60,输出插入完后的二叉树
    8. 二叉排序树查找60,输出查找成功,并输出比较次数
    9. 程序所能达到的功能。演示静态查找和动态查找,初始化查找表,顺序查找,折半查找,二叉排序树的初始化、插入、删除、查找操作。
    10. 测试数据。

       

    11. 若它的左子树非空,则左子树上所有节点的值均小于根节点上的值。
    12. 若它的右子树非空,则右子树上所有节点的值均大于根节点上的值。
    13. 做、右子树本身就是一棵二叉树。
  3. 概要设计
    1. 主函数main()
    2. 显示主界面函数 PrintMenu()
    3. 初始化查找表函数ElemInit()
    4. 输出查找表所有元素函数output()
    5. 数据输入界面函数 input()
    6. 娴熟静态查找主界面函数PrintStaticMenu()
    7. 顺序查找(未设置监视哨)函数 Seqsearch()
    8. 顺序查找(设置监视哨)函数SeqSearchSetMonitor()
    9. 冒泡排序函数BubbleSort()
    10. 折半查找函数 BinarySearch()
    11. 静态查找主程序函数StaticSearch()
    12. 显示动态查找主界面 函数PrintDynamicMenu()
    13. 二叉排序树的节点插入函数InsertBST()
    14. 二叉排序树的更新建立函数CreateBST()
    15. 中根二叉排序树的中根遍历输出函数OutPutBintree()
    16. 二叉排序树中节点的删除DelBSTNode()
    17. 二叉排序树查找SearchBST()
    18. 动态查找主程序DynamicSearch()
    19. 为了实现上述程序功能,需要定义顺序栈的数据结构。
    20. 本程序包含7个函数
  4. 详细设计

    #include<stdio.h>

    #include<conio.h>

    #include<string.h>

    #include<malloc.h>

    #define Keytype int //关键字类型定义

    #define MAX_LIST_LEN 100 //定义线性表的最大长度

    typedef struct{ //定义元素类型

    Keytype key; //关键字定义

    }ElemType;

    typedef struct{ //查找表顺序存储结构定

    ElemType elem[MAX_LIST_LEN+1]; //elem[0]元素当做工作单元

    int length; //查找表长度

    }Seq_Table;

    Seq_Table seqtbl;

    typedef struct NODE{ //查找表链式存储结构定义

    ElemType elem; //其中 ElemType 定义同顺序存储结构

    struct NODE *next;

    }LINK_NODE;

    #define ENDVALUE -1

    typedef struct BINNODE{ //二叉排序树定义

    Keytype key; //关键字值

    struct BINNODE *lchild,*rchild; //左、右孩子指针

    }BSTNode,*BSTree;

    //显示主界面

    void PrintMenu()

    {

    printf("\n\n\n\n\n");

    printf("\t\t\t -- 各类查找综合演示 --\n");

    printf("\n\t\t\t");

    printf("\n\t\t\t* 1------静态查找 *");

    printf("\n\t\t\t* 2------动态查找 *");

    printf("\n\t\t\t* 0------退 出 *");

    printf("\n\t\t\t\n");

    printf("\t\t\t 请选择功能号(0--2): \n");

    }

    //查找表初始化

    void ElemInit()

    {

    int i=1;

    ElemType elem;

    printf("\n 请注意! 假定系统查找表的最大长度为%d",MAX_LIST_LEN);

    printf("\n 请输入若干(<%d) 查找表初始元素的关键字值(整数), 以%d 结束。 \n",

    MAX_LIST_LEN,ENDVALUE);

    seqtbl.length=0; //初始化查找表长度

    while(1)

    {

    scanf("%d",&elem.key);

    if(elem.key==ENDVALUE)

    break;

    else

    seqtbl.elem[i++].key=elem.key; //从第 1 号单元开始存放数据

    seqtbl.length++;

    }

    }

    //输出查找表的所有元素

    void output(Seq_Table seqtbl1)

    {

    int k;

    printf("\n\t 查找表的地址单元: ");

    for(k=1;k<=seqtbl1.length;k++)

    printf("%4d",k);

    printf("\n\t 元素关键字序列为: ");

    for(k=1;k<=seqtbl1.length;k++)

    printf("%4d",seqtbl1.elem[k]);

    }

    //数据输入界面

    int input()

    {

    int x;

    while(1)

    {

    printf("\n 请输入你要查找元素的关键字(整型): ");

    scanf("%d",&x);

    getchar();

    if(!((x>=-32768)&&(x<=32768)))

    printf("\n 关键字输入无效, 请重新输入! ");

    else

    break;

    }

    return x;

    }

    //显示静态查找主界面

    void PrintStaticMenu()

    {

    printf("\n\n\n\n\n");

    printf("\t\t\t -- 静态查找综合演示 --\n");

    printf("\n\t\t\t**");

    printf("\n\t\t\t* 1------查找表初始化 *");

    printf("\n\t\t\t* 2------顺序查找 *");

    printf("\n\t\t\t* 3------顺序查找(设监视哨) *");

    printf("\n\t\t\t* 4------折半查找 *");

    printf("\n\t\t\t* 0------返回主界面 *");

    printf("\n\t\t\t**\n");

    printf("\t\t\t 请选择功能号(0--4): \n");

    }

    //顺序查找, 未设置监视哨的情形

    int SeqSearch(Seq_Table Seq_Tbl,Keytype Sea_Key)

    {

    int pos,len;

    pos=1;

    len=Seq_Tbl.length;

    //当没有到达查找表尾且没有找到时循环

    while(pos<=len&&Seq_Tbl.elem[pos].key!=Sea_Key)

    pos++;

    if(pos>len) //循环结束是因为没找到此元素

    return 0;

    else //找到此元素

    return pos;

    }

    //顺序查找, 设置监视哨的情形

    int SeqSearchSetMonitor(Seq_Table Seq_Tbl,Keytype Sea_Key)

    {

    int i;

    Seq_Tbl.elem[0].key=Sea_Key;

    for(i=Seq_Tbl.length;Seq_Tbl.elem[i].key!=Sea_Key;i--);

    return i;

    }

    //冒泡排序

    void BubbleSort(Seq_Table *Seq_Tbl)

    {

    int i,j;

    ElemType temp;

    for(i=1;i<=Seq_Tbl->length-1;i++) //外循环, i 表示趟数, 总共需要 len-1 趟

    {

    for(j=1;j<=Seq_Tbl->length-i;j++) //内循环, 每趟排序中所需比较的次数

    if(Seq_Tbl->elem[j].key>Seq_Tbl->elem[j+1].key)

    //前面元素大于后面元素, 则交换

    {

    temp=Seq_Tbl->elem[j];

    Seq_Tbl->elem[j].key=Seq_Tbl->elem[j+1].key;

    Seq_Tbl->elem[j+1]=temp;

    }

    }

    }

    //折半查找

    int BinarySearch(Seq_Table Seq_Tb1,Keytype Sea_Key)

    //Seq_Tb1为查找表,Sea_Key 为待查的关键字

    {

    int mid,low,high;

    low=1;

    high=Seq_Tb1.length;

    while(low<=high)

    {

    mid=(low+high)/2;

    if(Seq_Tb1.elem[mid].key<Sea_Key) //若存在, 则必在右半区

    low=mid+1;

    else

    if(Seq_Tb1.elem[mid].key>Sea_Key) //若存在, 则必在左半区

    high=mid-1;

    else //等于待查找的关键字, 查找结束

    break;

    }

    if(low>high) //没有找到

    return 0;

    else

    return mid;

    }

    //静态查找主程序

    void StaticSearch()

    {

    char static_func_choice;

    PrintStaticMenu();

    getchar(); //读主界面的回车符

    static_func_choice=getchar();

    while(static_func_choice!='0')

    {

    switch(static_func_choice)

    {

    case'1':

    ElemInit();

    break;

    case'2': //顺序查找

    {

    int retval,seakey;

    seakey=input();

    retval=SeqSearch(seqtbl,seakey);

    output(seqtbl);

    printf("\n\t 你要查找的关键字为: %d",seakey);

    if(retval>0)

    printf("\n\t 查找成功, 关键字为 %d 的元素位于第 %d 个位置!",seakey,retval);

    else

    printf("\n\t 对不起, 关键字为 %d 的元素不存在.",seakey);

    break;

    }

    case'3': //设置监视哨的情形

    {

    int retval,seakey;

    seakey=input();

    retval=SeqSearchSetMonitor(seqtbl,seakey);

    output(seqtbl);

    printf("\n\t 你要查找的关键字为: %d",seakey);

    if(retval>0)

    printf("\n\t 查找成功, 关键字为 %d 的元素位于第 %d 个位置!",seakey,retval);

    else

    printf("\n\t 对不起, 关键字为 %d 的元素不存在。 ",seakey);

    break;

    }

    case'4': //折半查找

    {

    int retval,seakey;

    seakey=input();

    printf("\n\t 请注意! 折半查找要求是有序表, 若元素顺序无序,则首先将排序! \n");

    BubbleSort(&seqtbl);

    //调用冒泡排序排序法使 查找表成为有序表

    retval=BinarySearch(seqtbl,seakey);

    output(seqtbl);

    printf("\n\t 你要查找的关键字为: %d",seakey);

    if(retval>0)

    printf("\n\t 查找成功, 关键字为 %d 的元素位于第 %d 个位置!",seakey,retval);

    break;

    }

    default:

    printf("\n 请输入正确的操作选项(0-4): ");

    }

    getchar();

    PrintStaticMenu();

    static_func_choice=getchar();

    }

    }

    //显示动态查找主界面

    void PrintDynamicMenu()

    {

    printf("\n\n\n\n\n");

    printf("\t\t\t -- 动态查找综合演示 -- \n");

    printf("\n\t\t\t***");

    printf("\n\t\t\t* 1------二叉排列树初始化 *");

    printf("\n\t\t\t* 2------二叉排列树插入 *");

    printf("\n\t\t\t* 3------二叉排列树删除 *");

    printf("\n\t\t\t* 4------二叉排列树查找 *");

    printf("\n\t\t\t* 0------ 返回主界面 *");

    printf("\n\t\t\t***\n");

    printf("\t\t\t 请选择功能号(0-4): \n");

    }

    //二叉排列树的结点插入

    void InsertBST(BSTree bstree,Keytype Ins_key)

    {

    BSTree s,p,q;

    q=s=bstree; //s 指向二叉排列树的根结点

    while(s) //找到要 chauffeur 的结点的位置

    {

    if(s->key>Ins_key) //在左子树中查找

    {

    q=s;

    s=s->lchild;

    }

    else

    if(s->key<Ins_key) //在右子树中查找

    {

    q=s;

    s=s->rchild;

    }

    else //存在关键字等于 Ins_key 的结点

    {

    printf("\n 插入失败, 树中已经存在此关键字的结点。\n");

    return ;

    }

    }

    p=(BSTree)malloc(sizeof(BSTNode)); //生成一个关键字为Ins_key的结点 p

    p->key=Ins_key;

    p->lchild=NULL;

    p->rchild=NULL;

    if(q->key>Ins_key)

    q->lchild=p; //将节点 p 插入左子树

    else

    q->rchild=p; //将节点 p 插入右子树

    }

    /*二叉排列树的更新建立*/

    BSTree CreateBST() //返回二叉排列树的头指针

    {

    Keytype Ins_key;

    BSTree p,head=NULL;

    int nodeseq=1; //结点序号

    printf("\n\t 请输入若干元素结点的关键字值, 以 %d 结束! \n",ENDVALUE);

    scanf("%d",&Ins_key); //假定关键字类型为整型

    while(Ins_key!=ENDVALUE)

    {

    if(nodeseq==1) //第一个结点单独处理

    {

    p=(BSTree)malloc(sizeof(BSTNode));

    //生成一个关键字为 Ins_key 的结点 p

    p->key=Ins_key;

    p->lchild=NULL;

    p->rchild=NULL;

    head=p;

    nodeseq++;

    }

    else

    InsertBST(head,Ins_key); //调用插入函数

    scanf("%d",&Ins_key);

    }

    getchar();

    return head;

    }

    //中序二叉排列树的中序遍历输出

    void OutPutBintree (BSTree p)

    {

    if(p!=NULL)

    {

    OutPutBintree(p->lchild);

    printf("%4d",p->key);

    OutPutBintree(p->rchild);

    }

    }

    //二叉排序树中结点的删除

    BSTree DelBSTNode(BSTree bstree,Keytype Del_key)

    {

    BSTree s,p,q,f; //s 指向要删除节点的父结点, p 指向要删除的结点

    p=bstree;s=NULL; //p 指向二叉排序树的根结点

    while(p) //查找要删除的节点

    {

    if(p->key==Del_key) //找到, 则结束查找过程

    break;

    else

    {

    s=p; //将其父结点保存在 s 中

    if(p->key<Del_key)

    p=p->rchild; //往右子树继续查找

    else

    p=p->lchild; //往左子树继续查找

    }

    }

    if(p)

    {

    if(p->lchild) //p 有左子树, 查找左子树最右下方的结点

    {

    f=p;

    q=p->lchild;

    while(q->rchild) //查找最右下方结点

    {

    f=q;

    q=q->rchild;

    }

    if(f==p) //q 即为最右下方结点

    f->lchild=q->lchild;

    else

    f->rchild=q->lchild; //将左子树链接到父结点的右子树

    p->key=q->key;

    free(q);

    }

    else //要删除的结点无左子树

    {

    if(s==NULL)//删除结点为根节点

    bstree=p->rchild;

    else

    if(s->lchild==p) //删除结点为父结点的左子树

    s->lchild=p->rchild;

    else

    s->rchild=p->rchild;

    free(p);

    }

    }

    else //没有找到要删除的结点

    {

    printf("\n\t 关键字为%d 的结点不存在! ",Del_key);

    }

    return bstree;

    }

    //二叉排序树查找

    void SearchBST(BSTree bstree,Keytype Sea_Key)

    {

    BSTNode *p;

    int count=0;

    p=bstree;

    while((p!=NULL)&&(p->key!=Sea_Key))

    if(Sea_Key<p->key)

    {

    count++;

    p=p->lchild;

    }

    else{count++;p=p->rchild;}

    if(p==NULL){printf("\n\t\t 查找失败!, 比较次数为%d 次。 ",count);return;}

    else{printf("查找成功, 比较次数为%d 次。 ",count+1);return;}

    }

    //动态查找主程序

    void DynamicSearch()

    {

    Keytype Ins_key,Sea_Key;

    BSTree p,root=NULL;

    char dynamic_func_choice;

    PrintDynamicMenu();

    getchar(); //读主界面的回车符

    dynamic_func_choice=getchar();

    while(dynamic_func_choice!='0')

    {

    switch(dynamic_func_choice)

    {

    case '1':

    root=NULL;

    root=CreateBST();

    printf("\n\t 当前二叉排序树的中序遍历为: \n");

    OutPutBintree(root);

    break;

    case '2':

    printf("\n\t 请输入要插入元素的关键字: ");

    scanf("%d",&Ins_key);

    printf("\n\t 插入之前的关键字序列为: \n");

    OutPutBintree(root);

    if(!root) //第一个结点

    {

    p=(BSTree)malloc(sizeof(BSTNode));

    //生成一个关键字为 Ins_key 的结点 p

    p->key=Ins_key;

    p->lchild=NULL;

    p->rchild=NULL;

    root=p;

    }

    else

    {

    InsertBST(root,Ins_key);

    }

    printf("\n\t 插 入 关 键 字 %d 之 后 的 元 素 的 关 键 字 序 列为 :\n",Ins_key);

    OutPutBintree(root);

    break;

    case '3':

    {

    Keytype Del_key;

    printf("\n\t 请输入要删除元素的关键字: ");

    scanf("%d",&Del_key);

    printf("\n\t 删除之前元素关键字中序遍历序列为: \n");

    printf("\t");

    OutPutBintree(root);

    root=DelBSTNode(root,Del_key);

    printf("\n\t 删除之后元素关键字中序遍历序列为: \n");

    printf("\t");

    OutPutBintree(root);

    break;

    }

    case '4':

    printf("\n\t 请输入要查找的关键字: ");

    scanf("%d",&Sea_Key);

    SearchBST(root,Sea_Key);

    break;

    default:

    printf("\n 请输入正确的操作选项(0-4): ");

    }

    getchar();

    PrintDynamicMenu();

    dynamic_func_choice=getchar();

    }

    }

    //主函数

    int main()

    {

    char func_choice;

    PrintMenu();

    func_choice=getchar();

    while(func_choice!='0')

    {

    switch(func_choice)

    {

    case '1':

    StaticSearch();

    break;

    case '2':

    DynamicSearch();

    break;

    case '0':

    func_choice='0';

    break;

    default:

    printf("\n 请输入正确的操作选项(0-4): ");

    }

    PrintMenu();

    getchar();

    func_choice=getchar();

    }

    }

  5. 调试分析

编译未发现错误

 

  1. 使用说明

    程序名为二叉树chazhao.exe,运行环境为MS-DOS。程序执行后显示:

    要求输入1、2、0分别进入静态查找、动态查找、退出

    静态查找功能

    动态查找功能

  2. 测试结果

静态查找:

    查找表初始化:

 

 

 

 

 

 

顺序查找:

顺序查找(设监视哨):

折半查找:

 

动态查找:

    二叉排列树初始化:

    二叉排列树插入:

二叉排列树删除:

二叉排列树查找:

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。