数据结构实验7：查找的应用

目录

一、实验目的

二、实验原理

1. 顺序查找

2. 折半查找

3. 二叉树查找 

三、实验内容

实验一

任务

 代码

截图

实验2

任务

代码

截图

一、实验目的

1.掌握查找的基本概念；

2.掌握并实现以下查找算法：顺序查找、折半查找、二叉树查找。

二、实验原理

1. 顺序查找

原理：

顺序查找是一种逐个检查数据元素的搜索方法。从列表的第一个元素开始，逐个比较目标值和列表中的元素，直到找到匹配的元素或搜索完整个列表。

时间复杂度：

O(n)，其中n是数据元素的数量。 

代码：

int sequential_search(int arr[], int size, int target) {
	for (int i = 0; i < size; i++) {
		if (arr[i] == target) {//若找到目标元素，返回第一个出现的索引
			return i;
		}
	}
	return -1;//若没有找到目标元素
}

2. 折半查找

原理：

折半查找要求数据元素必须有序。它通过反复将搜索范围减半来查找目标值。首先，与中间元素比较，如果目标值小于中间元素，则在左半部分继续查找；如果大于中间元素，则在右半部分继续查找。重复这个过程直到找到目标值或搜索范围缩小到空。 

时间复杂度：

 O(log n)，其中n是数据元素的数量。

代码：

int binary_search(int arr[], int size, int target) {
	int low = 0, high = size - 1;
	while (low <= high) {
		int mid = (low + high) / 2;
		if (arr[mid] == target) {//若找到目标元素，返回出现的索引
			return mid;
		}
		else if (target < arr[mid]) {//如果中间元素较大
			high = mid - 1;
		}
		else {//如果中间元素较小
			low = mid + 1;
		}
	}
	return -1;//若没有找到目标元素
}

3. 二叉树查找 

原理：

二叉树是一种树形结构，每个节点最多有两个子节点，且左子节点的值小于父节点，右子节点的值大于父节点。二叉树查找利用这个有序性质，通过比较目标值和当前节点的值，决定向左子树或右子树移动，直到找到目标值或达到叶子节点。

时间复杂度：

平均情况下为O(log n)，最坏情况下可能为O(n)，取决于树的平衡性。

代码：

//定义二叉树结构
struct Treenode {
	int value;
	struct Treenode* left;
	struct Treenode* right;
};

//创建新结点
struct Treenode* Create_node(int num) {
	struct Treenode* node = (struct Treenode*)malloc(sizeof(struct Treenode));
	node->value = num;
	node->left = NULL;
	node->right = NULL;
    return node;
}
//二叉树查找
struct Treenode* binary_tree_search(struct Treenode* root,int target) {
	if (root->value == target) {//如果找到
		return root;
	}
	else if(root->value<target){//如果目标值小于根，则在其左子树上查找
		return binary_tree_search(root->left, target);
	}
	else {//如果目标值大于根，则在其右子树上查找
		return binary_tree_search(root->right, target);
	}
}

三、实验内容

对同一组数据，试用三种方法查找某一相同数据：

1.建立一个顺序表，用顺序查找的方法对其实施查找;

2.建立一个有序表，用折半查找的方法对其实施查找;

3.建立一个二叉排序树，根据给定值对其实施查找;

实验一

任务

包括的函数有: typedef struct，创建函数 void create(seqlist &L)，输出函数 voidprint(seqlist L)，顺序查找 int find(seqlist L,intnumber)，折半查找 int halffind(seqlist L,int number)，主函数 main()。

 代码

#include<iostream>
using namespace std;

//定义学生结构
typedef struct Record {
	int ID;//学号
	string name;//姓名
	string sex;//性别
	int age;//年龄
}student;

typedef struct seqlist {
	student record[10];//这个列表最多有十个学生的记录
	int num;//实际学生的数目
};

//对列表进行初始化
void Initial_list(seqlist& list) {
	list.num = 0;
	return;
}

//创建列表
void create(seqlist& L) {
	cout << "请输入学生数目:";
	cin >> L.num;
	cout << "学号  姓名  性别  年龄" << endl;
	for (int i = 0; i < L.num; i++) {
		cin >> L.record[i].ID;
		cin >> L.record[i].name;
		cin >> L.record[i].sex;
		cin >> L.record[i].age;
	}
	return;
}

//打印列表
void print(seqlist L) {
	cout << "学生的基本信息为：" << endl;
	cout << "学号  姓名  性别  年龄" << endl;
	for (int i = 0; i < L.num; i++) {
		cout << L.record[i].ID <<"  " <<L.record[i].name<<"  " << L.record[i].sex << "  "<<L.record[i].age << endl;
	}
	return;
}

//顺序表查找
int find(seqlist L, int number) {
	for (int i = 0; i < L.num; i++) {
		if (L.record[i].ID == number) {//若找到目标元素，返回第一个出现的索引
			return i;
		}
	}
	return -1;//若目标不在顺序表中
}

//折半查找
int halffind(seqlist L, int number) {
	int low = 0, high = L.num - 1;
	while (low <= high) {
		int mid = (low + high) / 2;
		if (L.record[mid].ID == number) {//若找到目标元素，返回出现的索引
			return mid;
		}
		else if (number < L.record[mid].ID) {//如果中间元素较大
			high = mid - 1;
		}
		else {//如果中间元素较小
			low = mid + 1;
		}
	}
	return -1;//若没有找到目标元素
}

 int main() {
	seqlist L1;
	int id1, id2,index1,index2;
	Initial_list(L1);//初始化
	create(L1);//输入,由于要求满足折半查找，则表中元素应该有序
	print(L1);//输出
	cout << "顺序查找" << endl;
	cout << "请输入你要查询的学号：";
	cin >> id1;
	index1 = find(L1, id1);
	if (index1 ==-1 ) {
		cout << "未找到所需元素" << endl;
	}
	else {
		cout << L1.record[index1].ID << "  " << L1.record[index1].name << "  " << L1.record[index1].sex << "  " << L1.record[index1].age << endl;
	}
	cout << "折半查找" << endl;
	cout << "请输入你要查询的学号：";
	cin >> id2;
	index2 = halffind(L1, id2);
	if (index2 == -1) {
		cout << "未找到所需元素" << endl;
	}
	else {
		cout << L1.record[index2].ID << "  " << L1.record[index2].name << "  " << L1.record[index2].sex << "  " << L1.record[index2].age << endl;
	}
}

截图

实验2

任务

 包括的函数有:结构体 typedef struct, 插入函数 void insert(bnode*& T,bnode * S), void insert1(bnode * & T) ， 创 建 函 数 voidcreate(bnode*& T)，查找函数：bnode *search (bnode*T. int number)，主函数main()。

代码

#include <iostream>
#include <cstdlib>
using namespace std;

// 定义二叉树结构
struct TreeNode {
    int ID;
    string name;
    string sex;
    int age;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 创建新结点
struct TreeNode* Create_node(int num) {
    struct TreeNode* newnode = new TreeNode;
    if (newnode == NULL) {
        cout << "内存分配失败" << endl;
        exit(1);  // 或者采取其他处理方式
    }

    newnode->ID = num;
    cout << "输入姓名、性别、年龄：" << endl;
    cin >> newnode->name;
    cin >> newnode->sex;
    cin >> newnode->age;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}

// 建立二叉树
struct TreeNode* buildTree() {
    int elem;
    cout << "输入节点的数值（-1代表空节点）:";
    cin >> elem;
    if (elem == -1) {
        return NULL;
    }
    struct TreeNode* root = Create_node(elem);
    cout << "输入" << elem << "的左节点" << endl;
    root->left = buildTree();
    cout << "输入" << elem << "的右节点" << endl;
    root->right = buildTree();
    return root;
}

// 二叉树查找
struct TreeNode* binary_tree_search(struct TreeNode* root, int target) {
    if (root == NULL || root->ID == target) {
        return root;
    }

    if (target < root->ID) {
        return binary_tree_search(root->left, target);
    }
    else {
        return binary_tree_search(root->right, target);
    }
}

// 插入节点
void insert(struct TreeNode* root, int target) {
    if (root == NULL) {//若是空节点，直接插入
        root= Create_node(target);
        return;
    }

    if (target < root->ID) {//插入左子树
        if (root->left == NULL) {//左子树为空，直接插入
            root->left = Create_node(target);
        }
        else {
            insert(root->left, target);
        }
    }
    else {
        if (root->right == NULL) {
            root->right = Create_node(target);
        }
        else {
            insert(root->right, target);
        }
    }
    return;
}

int main() {
    struct TreeNode* T = buildTree();  // 建立二叉树
    int number;
    cout << "请输入你要插入的学生的ID：";
    cin >> number;
    insert(T, 4);
    int targetID;
    cout << "输入要查找的学生ID：" << endl;
    cin >> targetID;
    struct TreeNode* ans = binary_tree_search(T, targetID);
    if (ans != NULL) {
        cout << ans->ID << " " << ans->name << " " << ans->sex << " " << ans->age << endl;
    }
    else {
        cout << "未找到目标节点" << endl;
    }

    return 0;
}

截图

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/339037.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

2.RHCSA启动配置

2.RHCSA启动配置

rht-clearcourse 0 #重置练习环境 rht-setcourse rh134 #切换CSA练习环境 cat /etc/rht #查看当前环境 virt-manager #打开KVM控制台 rht-vmctl start classroom #必做&#xff0c;start all不会包含classroom&#xff0c;需…
阅读更多...
【Linux】Ubuntu的gnome切换KDE Plasma

【Linux】Ubuntu的gnome切换KDE Plasma

文章目录 安装KDE Plasma桌面环境添加软件源并更新apt安装kubuntu-desktop&#xff08;作者没有成功&#xff09;aptitude安装kubuntu-desktop多次aptitude install&#xff08;特别重要特别重要&#xff09;其他kde软件包 卸载gnome桌面 Ubuntu自带的桌面环境是gnome&#xff…
阅读更多...
PSoc62™开发板之rtc时间获取

PSoc62™开发板之rtc时间获取

实验目的 1.使用PSoc62™芯片读取内部rtc时间 2.OLED屏幕显示当前时间戳 实验准备 PSoc62™开发板SSD1306 OLED模块公母头杜邦线 芯片资源 PSoC 6系列MCU时钟系统由以下几部分组成&#xff0c;PSoc62™开发板没有接外部时钟源&#xff0c;所以只能从IMO、ILO、PILO里边配…
阅读更多...
EtherNet/IP开发：C++搭建基础模块，EtherNet/IP源代码

EtherNet/IP开发：C++搭建基础模块，EtherNet/IP源代码

这里是CIP资料的协议层级图&#xff0c;讲解协议构造。 ODVA&#xff08;www.ODVA.org&#xff09;成立于1995年&#xff0c;是一个全球性协会&#xff0c;其成员包括世界领先的自动化公司。结合其成员的支持&#xff0c;ODVA的使命是在工业自动化中推进开放、可互操作的信息和…
阅读更多...
SQL注入实战：Update注入

SQL注入实战：Update注入

一&#xff1a;Update注入原理 有的程序员在写源代码的时候&#xff0c;只是对查询的sql语句的用户输入内容进行了过滤&#xff0c;忽略了update 类型sql语句的用户输入的内容的过滤 二、mysql的Update语句复习 update语句可用来修改表中的数据&#xff0c;简单来说基本的使…
阅读更多...
算法每日一题： 分割数组的最大值 | 动归 | 分割数组 | 贪心+二分

算法每日一题： 分割数组的最大值 | 动归 | 分割数组 | 贪心+二分

Hello&#xff0c;大家好&#xff0c;我是星恒 呜呜呜&#xff0c;今天给大家带来的又是一道经典的动归难题。 题目&#xff1a;leetcode 410给定一个非负整数数组 nums 和一个整数 k &#xff0c;你需要将这个数组分成 k_ 个非空的连续子数组。设计一个算法使得这 k _个子数组…
阅读更多...
51单片机电子密码锁Proteus仿真+程序+视频+报告

51单片机电子密码锁Proteus仿真+程序+视频+报告

目录 视频 设计分析 系统结构 仿真图 资料内容 资料下载地址&#xff1a;51单片机电子密码锁Proteus仿真程序视频报告 视频 单片机电子密码锁Proteus仿真程序视频 设计分析 (1)能够从键盘中输入密码&#xff0c;并相应地在显示器上显示‘*’&#xff1b; (2)能够判断密码…
阅读更多...
反序列化字符串逃逸（上篇）

反序列化字符串逃逸（上篇）

首先&#xff0c;必须先明白&#xff0c;这个点并不难&#xff0c;我给大家梳理一遍就会明白。 反序列化字符串逃逸就是序列化过程中逃逸出来字符&#xff0c;是不是很简单&#xff0c;哈哈哈&#xff01; 好了&#xff0c;不闹了&#xff0c;其实&#xff1a; 这里你们只要懂…
阅读更多...
【C++ | 数据结构】从哈希的概念 到封装C++STL中的unordered系列容器

【C++ | 数据结构】从哈希的概念 到封装C++STL中的unordered系列容器

文章目录 一、unordered系列容器的底层结构 - 哈希1. 哈希概念2. 哈希冲突 二、解决哈希冲突方法一&#xff1a;合理设计哈希函数&#x1f6a9;哈希函数设计原则&#x1f6a9;常见哈希函数 方法二&#xff1a;开闭散列&#x1f6a9;闭散列线性探测法&#xff08;实现&#xff0…
阅读更多...
Linux操作系统——理解文件系统

Linux操作系统——理解文件系统

预备知识 到目前为止&#xff0c;我们所学习到的关于文件的操作&#xff0c;全部都是基于文件被打开&#xff0c;被访问&#xff0c;访问期间比较重要的有重定向&#xff0c;缓冲区&#xff0c;一切皆文件&#xff0c;当我们访问完毕的时候需要将文件关闭&#xff0c;关闭时那…
阅读更多...
Python 生成 图片网页列表 显示路径和建立时间 笔记

Python 生成 图片网页列表 显示路径和建立时间 笔记

Python 一键 生成 图片网页列表 显示路径和建立时间 &#xff08;方便查看复制路径、重复一键生成&#xff09; 支持格式&#xff1a;jpg \png\ svg\ webp 图片网页列表 图示&#xff1a; 参考代码&#xff1a; # -*- coding: utf-8 -*- import os import datetime# 指定图片…
阅读更多...
八股文学习日常第一期（20240121）

八股文学习日常第一期（20240121）

零、前言 1、目的 帮助掌握面试题&#xff0c;就八股文相关内容展开进行学习和整理&#xff0c;也方便之后的复习和巩固。 2、八股文内容来源 ①https://blog.csdn.net/w20001118/article/details/125724647 一、具体内容分析 1、类的完整书写方式 1.1、类 [Access Mod…
阅读更多...
Stream toList不能滥用以及与collect(Collectors.toList())的区别

Stream toList不能滥用以及与collect(Collectors.toList())的区别

Stream toList()返回的是只读List原则上不可修改&#xff0c;collect(Collectors.toList())默认返回的是ArrayList,可以增删改查 1. 背景 在公司看到开发环境突然发现了UnsupportedOperationException 报错&#xff0c;想到了不是自己throw的应该就是操作collection不当。 发…
阅读更多...
2.上传图片到Minio服务中

2.上传图片到Minio服务中

上传图片 界面原型 第一步: 用户在课程信息编辑界面可以上传课程图片或者修改上传的课程图片 第二步: 请求媒资管理服务将课程图片上传至分布式文件系统同时在媒资管理数据库保存文件信息,上传成功后返回图片在MinIO中的地址 第三步: 请求内容管理服务保存课程信息含课程封…
阅读更多...
【网站项目】基于SSM的274办公自动化管理系统

【网站项目】基于SSM的274办公自动化管理系统

&#x1f64a;作者简介&#xff1a;多年一线开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0c;帮助大学选题。赠送开题报告模板&#xff…
阅读更多...
【Linux系统编程】进程优先级

【Linux系统编程】进程优先级

文章目录 1. 优先级的基本概念2. 为什么存在优先级3. 查看系统进程4. PRI and NI5. top命令修改已存在进程的nice值6. 其他概念 1. 优先级的基本概念 本篇文章讲解进程优先级&#xff0c;首先我们来了解一下进程优先级的概念&#xff1a; cpu资源分配的先后顺序&#xff0c;就…
阅读更多...
burp靶场--访问控制【越权】

burp靶场--访问控制【越权】

【Burp系列】超全越权漏洞实验总结 https://portswigger.net/web-security/access-control/lab-unprotected-admin-functionality 1. 访问控制【越权】 https://portswigger.net/web-security/access-control#what-is-access-control ### 什么是访问控制&#xff1a; 访问控…
阅读更多...
php基础学习之常量

php基础学习之常量

php常量的基本概念 常量是在程序运行中的一种不可改变的量&#xff08;数据&#xff09;&#xff0c;常量一旦定义&#xff0c;通常不可改变&#xff08;用户级别&#xff09;。 php常量的定义形式 使用define函数&#xff1a;define("常量名字", 常量值);使用cons…
阅读更多...
Mac NTFS 磁盘读写工具选哪个好？Tuxera 还是 Paragon？

Mac NTFS 磁盘读写工具选哪个好？Tuxera 还是 Paragon？

在使用 Mac 电脑时&#xff0c;我们经常需要读写 NTFS 格式的硬盘或 U 盘。然而&#xff0c;由于 Mac 系统不支持 NTFS 格式的读写&#xff0c;因此我们需要借助第三方工具来实现这个功能。而在市场上&#xff0c;Tuxera 和 Paragon 是两款备受推崇的 Mac NTFS 磁盘读写工具。那…
阅读更多...
GSP专版软件系统(医疗器械进销存)

GSP专版软件系统(医疗器械进销存)

产品概述 软件完全符合药监局GSP认证要求&#xff0c;可订制其它平台的数据对接; 业务流程清晰&#xff0c;操作简单合理&#xff0c;软件速度非常快; 完善的序列号(UDI)管理,并与整个系统融合在一起; 财务账和业务账完美结合; 可自定义的界面、布局管理;灵活的打印样式设计; 可…
阅读更多...
最新文章

Copyright @ 2022~2023