数据结构第四次上机实习

C++ 上机 数据结构
数据结构上机实习
发布日期:   2021-01-26
文章字数:   2.9k
阅读时长:   13 分
阅读次数:  

实习题目：搜索效率比较

一、 上机实习题目与要求

问题描述

生成N个整数序列，序列分为两组：顺序序列和随机序列，在其中搜索最大的n个数。 对顺序序列采用顺序搜索、折半搜索、二叉排序树、平衡二叉排序树进行搜索；对随机序列采用顺序搜索、二叉排序树、平衡二叉排序树进行搜索。其中， N=500,1000,2000,5000,10000,20000,30000,50000。 n=N/100；

基本要求

（1）分析最坏情况下不同搜索算法的复杂度；

（2）统计分析并比较不同搜索算法在N取值不同时的性能，完成以下三个方面：

对每个测试数据集，统计计算不同搜索算法搜索成功的ASL；

对每个测试数据集运行多次获得不同搜索算法的 运行时间的平均值；

绘制算法实际运行结果（ASL和运行时间）的曲线图，验证和理论分析的时间复杂度的吻合性。

二、数据结构设计

选择带头结点的单链表存储稀疏多项式。

顺序搜索和折半搜索均选择数组作为存储结构：在搜索表中，数据对象存放于数组中，利用数组元素的下标作为数据对象的存放地址更加方便快捷。

二叉排序树搜索选择二叉树作为数据的存储结构：每个结点都存放一个作为搜索依据的关键码，其中左子树上所有结点的关键码都小于根节点的关键码，右子树的所有结点的关键码都大于根节点的关键码，其中左子树和右子树也是二叉搜索树。

三、源代码

stdfax.h

#ifndef STDFAX_H_INCLUDE
#define STDFAX_H_INCLUDE
#include <iostream>
#include <ctime>
#include <time.h>
#include <stdlib.h>
#include <stack>
#include <windows.h>
#include <algorithm>
using namespace std;
#endif // !SYDFAX_H_INCLUDE

search.h

#ifndef SEARCH_H_INCLUDED
#define SEARCH_H_INCLUDED
#include "stdfax.h"

//冒泡排序将无序序列转换为顺序序列
void Sort(int arr[], int N) 
{
    int i, j;
    int temp;
    for (i = 0; i < N - 1; i++)
        for (j = 0; j < N - 1 - i; j++)
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
}

//先在N个数中找到最大的n个数
//array为待检查的数组，N为数组长度，n为需要取出的最大的n个数
int* TopK(int* array, int N, int n)
{
    int* flag;
    int* result;
    flag = new int[N];                    //用于标记这个数是否已经被提取过
    result = new int[n];                //用于存储这n个最大的数
    for (int i = 0;i < n;i++)
    {//选择排序n次获取n个最大的数
        int maxIndex = 0;                //最大数的位置
        int maxNum = array[0];            //保存最大数
        for (int j = 0;j < N;j++)
        {
            if (array[j] > maxNum && flag[j]!=-1)  //如果大于最大数并且没有被取出来过就记录下来
            {
                maxNum = array[j];
                maxIndex = j;
            }
        }
        flag[maxIndex] = -1;    //将此次遍历的最大数的位置标记为-1，防止再次被取出
        result[i] = maxNum;        //存入该最大数
    }
    return result;
}

//顺序搜索
int SequenceSearch(int a[], int value, int n)
{
    int i;
    for (i = 0; i < n; i++)
        if (a[i] == value)
            return a[i];
    return -1;
}

//在顺序搜索中在N个数中找到最大的n个数
//original为原始序列，maxNum为需要搜索的数字，N为原始序列长度，n为需要取出的最大的n个数
void SeqSearch(int* original, int* maxNum, int N, int n)
{
    int result=0;
    cout << "顺序搜索后最大的"<< n <<"个数为:";
    for (int i = 0;i < n; i++)
    {
        result = SequenceSearch(original, maxNum[i], N);
        cout << result << " ";
    }
}

//二分搜索（折半搜索)
int BinarySearch(int a[], int value, int n)
{
    int low, high, mid;
    low = 0;
    high = n - 1;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (a[mid] == value)
            return a[mid];
        if (a[mid] > value)
            high = mid - 1;
        if (a[mid] < value)
            low = mid + 1;
    }
    return -1;
}

//在二分搜索中在N个数中找到最大的n个数
//original为原始序列，maxNum为需要搜索的数字，N为原始序列长度，n为需要取出的最大的n个数
void BinSearch(int* original, int* maxNum, int N, int n)
{
    int result = 0;
    cout << "二分搜索后最大的" << n << "个数为:";
    for (int i = 0;i < n; i++)
    {
        result = BinarySearch(original, maxNum[i], N);
        cout << result << " ";
    }
}

//二叉排序树搜索
struct Node
{
    int data;
    int height;
    Node* left;
    Node* right;
};
class BST                       //二叉树搜索类
{
public:
    Node* root;                      //二叉搜索树根指针
    BST() :root(NULL){}             //析构函数
    //中序遍历输出树的序列
    void InOrderPrint(Node* root)        
    {
        if (root == NULL) 
        {
            return;
        }
        InOrderPrint(root->left);
        cout << root->data << " ";
        InOrderPrint(root->right);
    }

    //释放树的存储空间
    void release(Node* root)        
    {
        if (root == NULL)
        {
            return;
        }
        release(root->left);
        release(root->right);
        delete root;
    }

    //二叉树的插入
    void insert(Node*& root, int value)            
    {
        if (root == NULL)                    //树根为空时，建立根节点
        {
            root = new Node;
            root->left = NULL;
            root->right = NULL;
            root->data = value;
            return ;
        }
        if (value > root->data)                //插入值大于当前值，插入右子树
        {
            insert(root->right, value);
        }
        else if (value == root->data)        //插入值等于当前值，不插入
        {
            return;
        }
        else
        {
            insert(root->left, value);        //插入值小于当前值，插入左子树
        }
    }

    //二叉树的建立
    void Creat(int* A, int n)            //根据提供的数据数组A[n]建立二叉树
    {
        for (int i = 0;i < n;i++)
        {
            insert(root, A[i]);
        }
    }

    //二叉树的搜索
    void search(Node*& root, int key, Node**& result)        
    {

        if (root == NULL)            //搜索失败的情况
        {
            result = NULL;
            return;
        }
        if (key < root->data)        //查找的值小于当前值，在左子树搜索
        {
            search(root->left, key, result);
        }
        else if (key == root->data)    //查找的值等于当前值，搜索成功
        {
            result = &root;
            return;
        }
        else                        //否则查找的值大于于当前值，在右子树搜索
        {
            search(root->right, key, result);
        }
    }
};

//在二叉排序树中在N个数中找到最大的n个数
//original为原始序列，maxNum为需要搜索的数字，N为原始序列长度，n为需要取出的最大的n个数
void BSTSearch(int* original, int* maxNum, int N, int n)
{
    Node** result;
    BST tree;
    tree.Creat(original, N);
    cout << "二叉排序树搜索后最大的" << n << "个数为:";
    for (int i = 0;i < n; i++)
    {
        tree.search(tree.root, maxNum[i],result);;
        cout << (*result)->data << " ";
    }
}

//AVL搜索树
class AVL                       //二叉树搜索类
{
public:
    Node* root;                      //二叉搜索树根指针
    AVL() :root(NULL) {}             //析构函数
    //中序输出AVL树
    void AVLInOrderPrint(Node* root)
    {
        if (root == NULL)
        {
            return;
        }
        AVLInOrderPrint(root->left);
        cout << root->data << " ";
        AVLInOrderPrint(root->right);
    }

    //AVL树的空间释放
    void AVLrelease(Node* root)
    {
        if (root == NULL)
        {
            return;
        }
        AVLrelease(root->left);
        AVLrelease(root->right);
        delete root;
    }

    //平衡因子的获取
    int BalanceFactor(Node* root)
    {
        int bf = 0;            //平衡因子
        if (root->left != NULL && root->right != NULL)            //左右子树都存在
        {
            bf = root->left->height - root->right->height;        //平衡因子为左子树高度减去右子树的高度
        }
        else if (root->left != NULL)                            //只存在左子树，不存在右子树
        {
            bf = root->left->height;                            //平衡因子为左子树的高度
        }
        else if (root->right != NULL)                            //只存在右子树，不存在左子树
        {
            bf = -root->right->height;                            //平衡因子为右子树的高度
        }
        return bf;
    }

    //结点的高度计算
    void Height(Node* root)
    {
        if (root->left != NULL && root->right != NULL)            //左右子树都存在
        {
            root->height = root->left->height > root->right->height ?//高度为左（右）子树中高度较大的+1
                root->left->height + 1 : root->right->height + 1;
        }
        else if (root->left != NULL)                            //只存在左子树，不存在右子树
        {
            root->height = root->left->height + 1;                //高度为左子树高度+1
        }
        else if (root->right != NULL)                            //只存在右子树，不存在左子树
        {
            root->height = root->right->height + 1;                //高度为右子树高度+1
        }
        else
        {
            root->height = 1;
        }
    }

    //右单旋
    void RotateR(Node*& root) {

        Node* subR = root;            //要右旋转的结点
        root = subR->left;            //原根的左子女
        subR->left = root->right;    //root成为新根前卸掉右边负载
        root->right = subR;            //右单旋转，root成为新根
    }

    //左单旋
    void RotateL(Node*& root)
    {
        Node* subR = root;            //要左旋转的结点
        root = subR->right;            //原根的右子女
        subR->right = root->left;    //root成为新根前卸掉左边负载
        root->left = subR;            //左单旋转，root成为新根
    }

    //平衡二叉树的插入操作
    bool AVLinsert(Node*& root, int value)
    {

        if (root == NULL)        //根节点为空时，创建新结点存储
        {
            root = new Node;
            root->left = NULL;
            root->right = NULL;
            root->data = value;
            root->height = 1;
            return true;
        }
        if (value > root->data)    //插入值大于当前值，插入右子树
        {
            if (!AVLinsert(root->right, value))
            {
                return false;
            }
            else
            {    //插入右子树可能引起右边不平衡，如果不平衡进行左单旋
                int bf = BalanceFactor(root);
                if (bf == -2)
                {
                    RotateL(root);
                }
            }
        }
        else if (value == root->data)        //原来树中存在这个值，不插入
        {
            return false;
        }
        else                            //插入值小于当前值，插入左子树
        {
            if (!AVLinsert(root->left, value))
            {
                return false;
            }
            else
            {//插入右子树可能引起左边不平衡，如果不平衡进行右单旋
                int bf = BalanceFactor(root);
                if (bf == 2) {
                    RotateR(root);
                }
            }
        }
        Height(root);
        return true;
    }

    //AVL树的建立
    void Creat(int* A, int n)            //根据提供的数据数组A[n]建立二叉树
    {
        for (int i = 0;i < n;i++)
        {
            AVLinsert(root, A[i]);
        }
    }

    //AVL树的搜索算法
    void search(Node*& root, int key, Node**& result)
    {

        if (root == NULL)
        {
            result = NULL;
            return;
        }

        if (key < root->data)                        //查找的值小于当前值，在左子树中搜索
        {
            search(root->left, key, result);
        }
        else if (key == root->data)                    //查找的值等于当前值，搜索成功
        {
            result = &root;
            return;
        }
        else                                        //否则查找的值大于当前值，在右子树中搜索
        {
            search(root->right, key, result);
        }

    }

};

//在AVL树中在N个数中找到最大的n个数
//original为原始序列，maxNum为需要搜索的数字，N为原始序列长度，n为需要取出的最大的n个数
void AVLSearch(int* original, int* maxNum, int N, int n)
{
    Node** result;
    AVL tree;
    tree.Creat(original, N);
    cout << "AVL树搜索后最大的" << n << "个数为:";
    for (int i = 0;i < n; i++)
    {
        tree.search(tree.root, maxNum[i], result);;
        cout << (*result)->data << " ";
    }
}
#endif
// !SEARCH_H_INCLUDED

main.cpp

#include "stdfax.h"
#include "search.h"

int main()
{
    clock_t start, end;
    double time;
    int N;
    cout << "请输入元素的个数N:";            //获取元素个数n    
    cin >> N;
    int n = N / 100;
    int* original;
    int* result;
    original = new int[N];
    result = new int[n];
    //获取一个由N个随机数组成的一个随机序列
    for (int i = 0;i < N; i++)
    {
        original[i] = rand();
    }
    result = TopK(original, N, n);

    //测试顺序搜索无序序列耗时
    start = clock();
    SeqSearch(original, result, N, n);
    cout << endl;
    end = clock();
    time = double(end - start)/CLOCKS_PER_SEC;
    cout << "顺序搜索无序序列耗时为" << time << "s." << endl;
    cout << endl;

    //测试二叉排序树搜索无序序列耗时
    start = clock();
    BSTSearch(original, result, N, n);
    cout << endl;
    end = clock();
    time = double(end - start)/CLOCKS_PER_SEC;
    cout << "二叉排序树搜索无序序列耗时为" << time << "s." << endl;
    cout << endl;

    //测试AVL树搜索无序序列耗时
    start = clock();
    AVLSearch(original, result, N, n);
    cout << endl;
    end = clock();
    time = double(end - start) / CLOCKS_PER_SEC;
    cout << "AVL树搜索无序序列耗时为" << time << "s." << endl;
    cout << endl;

    //无序序列转化为顺序序列
    sort(original,original+N);
    //测试顺序搜索顺序序列耗时
    start = clock();
    SeqSearch(original, result, N, n);
    cout << endl;
    end = clock();
    time = double(end - start) / CLOCKS_PER_SEC;
    cout << "顺序搜索顺序序列耗时为" << time << "s." << endl;
    cout << endl;

    //测试折半搜索顺序序列耗时
    start = clock();
    BinSearch(original, result, N, n);
    cout << endl;
    end = clock();
    time = double(end - start) / CLOCKS_PER_SEC;
    cout << "折半搜索顺序序列耗时为" << time << "s." << endl;
    cout << endl;

    //测试二叉排序树搜索顺序序列耗时
    start = clock();
    BSTSearch(original, result, N, n);
    cout << endl;
    end = clock();
    time = double(end - start) / CLOCKS_PER_SEC;
    cout << "二叉排序树搜索顺序序列耗时为" << time << "s." << endl;
    cout << endl;

    //测试AVL树搜索顺序序列耗时
    start = clock();
    AVLSearch(original, result, N, n);
    cout << endl;
    end = clock();
    time = double(end - start) / CLOCKS_PER_SEC;
    cout << "AVL树搜索顺序序列耗时为" << time << "s." << endl;
    system("pause");
}
文章作者: 陈细利
文章链接: https://firewolf321.github.io/2021/01/26/shu-ju-jie-gou-di-si-ci-shang-ji/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 陈细利 !
C++ 上机 数据结构
赏
评论
 上一篇
数据结构第五次上机实习 数据结构第五次上机实习
实习题目：图的三种算法的同步演示一、 上机实习题目与要求问题描述分别写出深度优先遍历、Prim算法与Dijkstra算法这三个算法，同时动态显示出相应的构造过程。 基本要求（1）基于第3页ppt的图例构造图（权值可以自行设计添加）； （2）
2021-01-29 数据结构上机实习
C++ 上机 数据结构
下一篇 
数据结构第三次上机实习 数据结构第三次上机实习
实习题目：唯一的确定一棵二叉树一、 上机实习题目与要求问题描述如果给出了遍历二叉树的前序序列和中序序列，则可以构造出唯一的一棵二叉树。试编写实现上述功能的程序。 基本要求已知一棵二叉树的前序和中序序列，试设计完成下列任务的一个算法： （1）
2021-01-24 数据结构上机实习
C++ 上机 数据结构
  目录