投稿
  1. 极客之音首页
  2. 后端漫谈

C++查找实验

飞熊 • • 后端漫谈 • 阅读 249

勤奋不是嘴上说说而已，而是实际的行动，在勤奋的苦度中持之以恒，永不退却。业精于勤，荒于嬉；行成于思，毁于随。在人生的仕途上，我们毫不迟疑地选择勤奋，她是几乎于世界上一切成就的催产婆。只要我们拥着勤奋去思考，拥着勤奋的手去耕耘，用抱勤奋的心去对待工作，浪迹红尘而坚韧不拔，那么，我们的生命就会绽放火花，让人生的时光更加的闪亮而精彩。

导读：本篇文章讲解 C++查找实验，希望对大家有帮助，欢迎收藏，转发！站点地址：www.bmabk.com，来源：原文

1.顺序查找

运行结果如图所示：
在这里插入图片描述
seqSearch.cpp

#include <stdio.h>
//定义表中最多记录个数
#define MAXL 100
typedef int KeyType;
typedef char InfoType[10];

typedef struct {
    //KeyType为关键字的数据类型
    KeyType key;
    //其他数据
    InfoType data;
} NodeType;
//顺序表类型
typedef NodeType SeqList[MAXL];

//顺序查找算法
int SeqSearch(SeqList R, int n, KeyType k) {
    int index = 0;
    for (int i = 0; i < n; i++) {
        if (R[i].key == k) {
            index = i;
        }
        printf("%d ", R[i].key);
    }
    return index;
}

int main() {
    SeqList R;
    int n = 10;
    KeyType k = 5;

    int a[] = {3, 6, 2, 10, 1, 8, 5, 7, 4, 9};
    int i;
    //建立顺序表
    for (i = 0; i < n; i++) {
        R[i].key = a[i];
    }
    printf("\n");

    if ((i = SeqSearch(R, n, k)) != -1) {
        printf("\n元素%d的位置是%d\n", k, i);
    } else {
        printf("\n元素%d不在表中\n", k);
    }
    printf("\n");
}

运行截图
在这里插入图片描述

2. 折半查找

运行结果如图所示：
在这里插入图片描述
binSearch.cpp

#include <stdio.h>
//定义表中最多记录个数
#define MAXL 100                    

typedef int KeyType;
typedef char InfoType[10];

typedef struct {
    //KeyType为关键字的数据类型
    KeyType key;
    //其他数据
    InfoType data;
} NodeType;

//顺序表类型
typedef NodeType SeqList[MAXL];

//二分查找算法
int BinSearch(SeqList R, int n, KeyType k) {
    int low = 1;
    int high = n;
    int count = 1;
    int res = 0;
    while (low <= high && count < 4) {
        int mid = (low + high) / 2;
        if (count < 3) {
            printf("第%d次查找:在[%d,%d]中查找到元素R[%d]:%d\n", count, low - 1, high - 1, mid - 1, R[mid - 1].key);
        }
        if (k == R[mid].key) {
            res = mid;
            high = n;
            low = R[mid].key;
            count++;
            printf("第%d次查找:在[%d,%d]中查找到元素R[%d]:%d\n", count, low - 1, high - 1, res, R[res].key);
        } else if (k < R[mid].key) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
        count++;
    }
    return res;
}

int main() {
    SeqList R;
    KeyType k = 9;
    int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, i, n = 10;
    //建立顺序表
    for (i = 0; i < n; i++) {
        R[i].key = a[i];
    }
    printf("\n");

    if ((i = BinSearch(R, n, k)) != -1) {
        printf("元素%d的位置是%d\n", k, i);
    } else {
        printf("元素%d不在表中\n", k);
    }
    printf("\n");
}

运行截图
在这里插入图片描述

3. 二叉排序树的基本运算

运行结果如图所示：
在这里插入图片描述
BST.cpp

#include <stdio.h>
#include <malloc.h>

#define MaxSize 100
//定义关键字类型
typedef int KeyType;
typedef char InfoType;
//记录类型
typedef struct node {
    //关键字项
    KeyType key;
    //其他数据域
    InfoType data;
    //左右孩子指针
    struct node *lchild;
    struct node *rchild;
} BSTNode;
//全局变量,用于存放路径
int path[MaxSize];

//函数说明
void DispBST(BSTNode *b);

//在以*p为根结点的BST中插入一个关键字为k的结点
int InsertBST(BSTNode *&p, KeyType k) {
    //原树为空, 新插入的记录为根结点
    if (p == nullptr) {
        p = (BSTNode *) malloc(sizeof(BSTNode));
        p->key = k;
        p->lchild = p->rchild = nullptr;
        return 1;
    } else if (k == p->key) {
        return 0;
    } else if (k < p->key) {
        //递归调用，插入到*p的左子树中
        return InsertBST(p->lchild, k);
    } else {
        //递归调用，插入到*p的右子树中
        return InsertBST(p->rchild, k);
    }
}

//由数组A中的关键字建立一棵二叉排序树
BSTNode *CreatBST(KeyType A[], int n) {
    //初始时bt为空树
    BSTNode *bt = nullptr;
    int i = 0;
    while (i < n)
        //将A[i]插入二叉排序树T中
        if (InsertBST(bt, A[i]) == 1) {
            printf("    第%d步,插入%d: ", i + 1, A[i]);
            DispBST(bt);
            printf("\n");
            i++;
        }
    //返回建立的二叉排序树的根指针
    return bt;
}

//以括号表示法输出二叉排序树bt
void DispBST(BSTNode *bt) {
    if (bt != nullptr) {
        printf("%d", bt->key);
        if (bt->lchild != nullptr || bt->rchild != nullptr) {
            printf("(");
            DispBST(bt->lchild);
            if (bt->rchild != nullptr) {
                printf(",");
            }
            DispBST(bt->rchild);
            printf(")");
        }
    }
}

//以递归方式输出从根结点到查找到的结点的路径
int SearchBST(BSTNode *bt, KeyType k) {
    printf("%d ", bt->key);
    if (k == bt->key) {
        return bt->key;
    } else if (k < bt->key) {
        return SearchBST(bt->lchild, k);
    } else if (k > bt->key) {
        return SearchBST(bt->rchild, k);
    }
}

//当被删*p结点有左右子树时的删除过程
void Delete1(BSTNode *p, BSTNode *&r) {
    BSTNode *s;
    BSTNode *q;
    q = p;
    s = p->lchild;
    while (s->rchild) {
        q = s;
        s = s->rchild;
    }
    p->key = s->key;
    if (q != p) {
        q->rchild = s->lchild;
    } else {
        q->lchild = s->lchild;
    }
    delete s;
    /*
    if (r->rchild != nullptr)
        Delete1(p, p->lchild);    //递归找最右下结点
    else                        //找到了最右下结点*r
    {
        p->key = r->key;            //将*r的关键字值赋给*p
        q = r;
        r = r->lchild;            //将*r的双亲结点的右孩子结点改为*r的左孩子结点
        free(q);                //释放原*r的空间
    }
     */
}

//从二叉排序树中删除*p结点
void Delete(BSTNode *&p) {
    BSTNode *q;
    //*p结点没有右子树的情况
    if (p->rchild == nullptr) {
        q = p;
        p = p->lchild;
        free(q);
    } else if (p->lchild == nullptr) { //*p结点没有左子树的情况
        q = p;
        p = p->rchild;
        free(q);
    } else { //*p结点既有左子树又有右子树的情况
        Delete1(p, p->lchild);
    }
}

//在bt中删除关键字为k的结点
int DeleteBST(BSTNode *&bt, KeyType k) {
    //空树删除失败
    if (bt == nullptr) {
        return 0;
    } else {
        //小于说明在左边
        if (k < bt->key) {
            //递归在左子树中删除关键字为k的结点
            return DeleteBST(bt->lchild, k);
        } else if (k > bt->key) {
            //递归在右子树中删除关键字为k的结点
            return DeleteBST(bt->rchild, k);
        } else { //k=bt->key的情况
            //调用Delete(bt)函数删除*bt结点
            Delete(bt);
            return 1;
        }
    }
}

int flag = true;
int prev=-256;
bool isBinaryTree(BSTNode *&bt) {
    if (bt->lchild != nullptr && flag) {
        isBinaryTree(bt->lchild);
    }
    if(bt->data<prev){
        flag= false;
    }
    if(bt->rchild!= nullptr&&flag){
        isBinaryTree(bt->rchild);
    }
    return flag;
}


//predt为全局变量,保存当前结点中序前趋的值,初值为-∞
KeyType predt = -32767;

int main() {
    BSTNode *bt;
    KeyType k = 6;
    int a[] = {4, 9, 0, 1, 8, 6, 3, 5, 2, 7}, n = 10;
    /*
    4
   / \
  0   9
   \ /
   1 8
   \  /
   3 6
  /  /\
  2  5 7
     */
    printf(" 创建一棵BST树:");
    printf("\n");
    bt = CreatBST(a, n);

    printf("\n\n BST: ");
    DispBST(bt);
    printf("\n\n");

    printf(" 查找%d关键字: ", k);
    SearchBST(bt, k);
    printf("\n\n");

    printf(" 是否是二叉排序树: \n");
    if(isBinaryTree(bt)){
        printf(" 是二叉排序树 \n");
    } else{
        printf(" 不是二叉排序树 \n");
    }

    printf("\n\n 删除操作:\n");
    printf("   原BST: ");
    DispBST(bt);
    printf("\n");

    printf("   删除结点4: ");
    DeleteBST(bt, 4);
    DispBST(bt);
    printf("\n");

    printf("   删除结点5: ");
    DeleteBST(bt, 5);

    DispBST(bt);
    printf("\n\n");
}

运行截图
在这里插入图片描述

4.自行设计一个算法，判别给定的一棵二叉树是否为二叉排序树

根据第三题结构，添加如下算法代码

#include <stdio.h>
#include <malloc.h>

#define MaxSize 100
//定义关键字类型
typedef int KeyType;
typedef char InfoType;
//记录类型
typedef struct node {
    //关键字项
    KeyType key;
    //其他数据域
    InfoType data;
    //左右孩子指针
    struct node *lchild;
    struct node *rchild;
} BSTNode;
//全局变量,用于存放路径
int path[MaxSize];

//函数说明
void DispBST(BSTNode *b);

//在以*p为根结点的BST中插入一个关键字为k的结点
int InsertBST(BSTNode *&p, KeyType k) {
    //原树为空, 新插入的记录为根结点
    if (p == nullptr) {
        p = (BSTNode *) malloc(sizeof(BSTNode));
        p->key = k;
        p->lchild = p->rchild = nullptr;
        return 1;
    } else if (k == p->key) {
        return 0;
    } else if (k < p->key) {
        //递归调用，插入到*p的左子树中
        return InsertBST(p->lchild, k);
    } else {
        //递归调用，插入到*p的右子树中
        return InsertBST(p->rchild, k);
    }
}

//由数组A中的关键字建立一棵二叉排序树
BSTNode *CreatBST(KeyType A[], int n) {
    //初始时bt为空树
    BSTNode *bt = nullptr;
    int i = 0;
    while (i < n)
        //将A[i]插入二叉排序树T中
        if (InsertBST(bt, A[i]) == 1) {
            printf("    第%d步,插入%d: ", i + 1, A[i]);
            DispBST(bt);
            printf("\n");
            i++;
        }
    //返回建立的二叉排序树的根指针
    return bt;
}

//以括号表示法输出二叉排序树bt
void DispBST(BSTNode *bt) {
    if (bt != nullptr) {
        printf("%d", bt->key);
        if (bt->lchild != nullptr || bt->rchild != nullptr) {
            printf("(");
            DispBST(bt->lchild);
            if (bt->rchild != nullptr) {
                printf(",");
            }
            DispBST(bt->rchild);
            printf(")");
        }
    }
}

int flag = true;
int prev=-256;
bool isBinaryTree(BSTNode *&bt) {
    if (bt->lchild != nullptr && flag) {
        isBinaryTree(bt->lchild);
    }
    if(bt->data<prev){
        flag= false;
    }
    if(bt->rchild!= nullptr&&flag){
        isBinaryTree(bt->rchild);
    }
    return flag;
}


//predt为全局变量,保存当前结点中序前趋的值,初值为-∞
KeyType predt = -32767;

int main() {
    BSTNode *bt;
    KeyType k = 6;
    int a[] = {4, 9, 0, 1, 8, 6, 3, 5, 2, 7}, n = 10;
    /*
    4
   / \
  0   9
   \ /
   1 8
   \  /
   3 6
  /  /\
  2  5 7
     */
    printf(" 创建一棵BST树:");
    printf("\n");
    bt = CreatBST(a, n);
    printf("\n");
    printf(" 是否是二叉排序树: \n");
    if(isBinaryTree(bt)){
        printf(" 是二叉排序树 \n");
    } else{
        printf(" 不是二叉排序树 \n");
    }
}

运行截图
在这里插入图片描述

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/140678.html

赞 (0)
飞熊的头像飞熊bm
0 0

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！