数据结构期末算法复习:树、查找、排序
一、树
1.二叉链-定义
typedef struct BiTNode{
ElemType data;//数据域
struct BiTNode *lchild ,*rchild;//左、右孩子指针
}BiTNode , *BiTree ;
2.查找值为x的结点
BTNode FindNode(BTNode b,ElemType x)
{ BTNode *p;if (b==NULL) return NULL;else if (b->data==x) return b;else{ p=FindNode(b->lchild,x);if (p!=NULL) return p;else return FindNode(b->rchild,x);}
}
3.求高度
int BTHeight(BiTree root)
{ int m,n;if (root==NULL) return 0; //空树的高度为0else { m=BTHeight(root->lchild); //求左子树的高度为lchilddepn=BTHeight(root->rchild); //求右子树的高度为rchilddepreturn(m>n)? (m+1):(n+1));}
}
4.统计二叉树的结点
void PreOrder(BiTree root)
{ int count=0;if(root)
{ count++;PreOrder(root->LChild);PreOrder(root->RChild);}
}
5.输出叶子结点
void inOrder(BiTree root)
{if(root)
{ inOrder(root->LChild);if(root->LChild==NULL&& root->RChild==NULL)printf(root->data);inOrder(root->RChild);}
}
6.统计叶子结点个数
int leaf(BiTree root)
{int nl,nr;
if(root==NULL) return 0; if(root->LChild==NULL&& root->RChild==NULL)return 1;nl=leaf(root->RChild);nr=leaf(root->LChild);return(nl+nr);
}
二、查找
1.定义
typedef struct{//查找表的数据结构(顺序表)
ElemType *elem;//动态数组基址
int TableLen;//表的长度
}SSTable;
2.顺序查找
int Search_Seq( SSTable ST,ElemType key){int i; ST.elem[0] =key; //哨兵 for( i=ST.TableLen ;ST.elem[i] !=key; --i) ;//从后往前找 return i;//查找成功,则返回元素下标;查找失败,则返回0
}
3.折半查找
int Binary_Search( SSTable L,ElemType key){int low=1, high=L.TableLen,mid;while( low<=high){mid=( low+high)/2;//取中间位置if(L.elem[mid]==key)return mid;/查找成功则返回所在位置else if(L.elem [mid]>key)high=mid-1;//从前半部分继续查找
elselow=mid+1;//从后半部分继续查找
}
return -1; //查找失败,返回-1
}
4.二叉排序树
typedef struct BSTNode{int key;//数据域struct BSTNode*lchild ,*rchild;//左、右孩子指针
}BSTNode,*BSTree;
5.查找
BSTNode *BST_Search(BSTree T,int key){
while(T!=NULL&&key!=T->key){//若树空或等于根结点值,则结束循环if(key<T->key)T=T->lchild; //小于,则在左子树上查找else T=T->rchild;//大于,则在右子树上查找
}return T;
}
6.二叉排序树插入
int BST_Insert(BSTree &T, int k){
if(T==NULL){//原树为空,新插入的结点为根结点T=(BSTree )malloc(sizeof(BSTNode) ) ;T->key=k;T->lchild=T->rchild=NULL;return 1;//返回1,插入成功 }
else if(k==T->key)//树中存在相同关键字的结点,插入失败return 0;
else if( k<T->key)//插入到T的左子树return BST_Insert(T->lchild,k);else //插入到T的右子树return BST_Insert(T->rchild,k);}
三、排序
1.待排序的数据类型定义
#define MAXSIZE 1000 //待排序的记录数目
typedef int KeyType; //关键字类型
typedef struct
{KeyType key; //关键字项 OtherType other_data; //其他数据项
} RecordType; //纪录类型
typedef struct
{RecordType r[MAXSIZE+1]; int length; //序列长度
} RecordList; //记录序列类型(顺序表类型)
2.直接插入排序
void InsertionSort ( SqList &L )
{for ( i=2; i<=L.length; ++i ) if (L.r[i].key < L.r[i-1].key) {L.r[0] = L.r[i]; for ( j=i-1; L.r[0].key < L.r[j].key; -- j )L.r[j+1] = L.r[j]; L.r[j+1] = L.r[0]; }
}
3.折半插入排序
void BiInsertionSort ( SqList &L )
{int i,j,low,high,mid;
for ( i=2; i<=L.length; ++i )
{
L.r[0] = L.r[i];
low = 1; high = i-1;
while (low<=high)
{ m= (low+high)/2; if (L.r[0].key < L.r[m].key)high = m-1; else low = m+1; }
for ( j=i-1; j>=low; --j )L.r[j+1] = L.r[j];
}
L.r[low] = L.r[0];
}
4.冒泡法排序
void BubbleSort(RecordList L)
{ int i,j;RecordType x;int flag=1;for(i=1; i<=L.length-1&&flag; i++){ flag=0;for(j=1;j<= L.length-1; j++){ if(L.r[j].key>L.r[j+1].key){ x=L.r[j];L.r[j]=r[j+1];L.r[j+1]=x; flag=1;}}}
}
5.快速排序
int QKpass (RecordType r[ ], int low, int high)
{
r[0] = r[low];
while (low<high)
{while(low<high&& r[high].key>= r[0].key)-- high; r[low] = r[high];
while (low<high && r[low].key<= r[0].key) ++ low;
r[high] = r[low];
}
r[low] = r[0]; return low;
}
void QKSort(RecordType r[ ],int low,int high)
{ r[0]=r[low];if(low<high){pos=QKpass(r,low,high);QKSort(r,low,pos-1);QkSort(r,pos+1,high);
}
6.简单选择排序
void SelectSort(RecordList L)
{ int i,j;RecordType t;for(i=1;i<= L.length -1;i++){ k=i; for(j=i+1;j<= L.length -1; j++) if(L.r[j].key<L.r[k].key) k=j; if(k!=i) { t=L.r[i]; L.r[i]=L.r[k]; L.r[k]=t;}}
}
相关文章:
数据结构期末算法复习:树、查找、排序
一、树 1.二叉链-定义 typedef struct BiTNode{ ElemType data;//数据域 struct BiTNode *lchild ,*rchild;//左、右孩子指针 }BiTNode , *BiTree ;2.查找值为x的结点 BTNode FindNode(BTNode b,ElemType x) { BTNode *p;if (bNULL) return NULL;else if (…...
复习打卡Linux篇
目录 1. Linux常用操作命令 2. vim编辑器 3. 用户权限 4. Linux系统信息查看 1. Linux常用操作命令 基础操作: 命令说明history查看历史执行命令ls查看指定目录下内容ls -a查看所有文件 包括隐藏文件ls -l ll查看文件详细信息,包括权限类型时间大小…...
OpenAI API深度解析:参数、Token、计费与多种调用方式
随着人工智能技术的飞速发展,OpenAI API已成为许多开发者和企业的得力助手。本文将深入探讨OpenAI API的参数、Token、计费方式,以及如何通过Rest API(以Postman为例)、Java API调用、工具调用等方式实现与OpenAI的交互࿰…...
Centos7 部署ZLMediakit
1、拉取代码 #国内用户推荐从同步镜像网站gitee下载 git clone --depth 1 https://gitee.com/xia-chu/ZLMediaKit cd ZLMediaKit #千万不要忘记执行这句命令 git submodule update --init 2、安装编译器 sudo yum -y install gcc 3、安装cmake sudo yum -y install cmake 4…...
python:用 sklearn.metrics 评价 K-Means 聚类模型
sklearn 的 metrics 模块提供的聚类模型评价指标如下: ARI 评价法(兰德系数): adjusted_rand_score AMI 评价法(相互信息): adjusted_mutual_info_score V-measure 评分 : completeness_score FMI 评价法 : fowlkes_m…...
谁说C比C++快?
看到这个问题,我我得说:这事儿没有那么简单。 1. 先把最大的误区打破 "C永远比C快" —— 某位1990年代的程序员 这种说法就像"自行车永远比汽车省油"一样荒谬。我们来看个例子: // C风格 char* str (char*)malloc(100…...
算法刷题Day23:BM60 括号生成
题目链接 描述:给出n对括号,请编写一个函数来生成所有的由n对括号组成的合法组合。 例如,给出n3,解集为: “((()))”, “(()())”, “(())()”, “()()()”, “()(())” 思路: 回溯左子树不断添加‘&#…...
基于Redis实现令牌桶算法
基于Redis实现令牌桶算法 令牌桶算法算法流程图优点缺点 实现其它限流算法 令牌桶算法 令牌桶是一种用于分组交换和电信网络的算法。它可用于检查数据包形式的数据传输是否符合定义的带宽和突发性限制(流量不均匀或变化的衡量标准)。它还可以用作调度算…...
XXE练习
pikachu-XXE靶场 1.POC:攻击测试 <?xml version"1.0"?> <!DOCTYPE foo [ <!ENTITY xxe "a">]> <foo>&xxe;</foo> 2.EXP:查看文件 <?xml version"1.0"?> <!DOCTYPE foo [ <!ENTITY xxe SY…...
Mac上使用ln指令创建软链接、硬链接
在Mac、Linux和Unix系统中,软连接(Symbolic Link)和硬连接(Hard Link)是两种不同的文件链接方式。它们的主要区别如下: 区别: 硬连接: 不能跨文件系统。不能链接目录(为…...
单元测试-Unittest框架实践
文章目录 1.Unittest简介1.1 自动化测试用例编写步骤1.2 相关概念1.3 用例编写规则1.4 断言方法 2.示例2.1 业务代码2.2 编写测试用例2.3 生成报告2.3.1 方法12.3.2 方法2 1.Unittest简介 Unittest是Python自带的单元测试框架,适用于:单元测试、Web自动…...
JAVA没有搞头了吗?
前言 今年的Java程序员群体似乎承受着前所未有的焦虑。投递简历无人问津,难得的面试机会也难以把握,即便成功入职,也往往难以长久。于是,不少程序员感叹:互联网的寒冬似乎又一次卷土重来,环境如此恶劣&…...
ECharts 饼图:数据可视化的重要工具
ECharts 饼图:数据可视化的重要工具 引言 在数据分析和可视化的领域,ECharts 是一个广受欢迎的开源库。它由百度团队开发,用于在网页中创建交互式图表。ECharts 提供了多种图表类型,包括柱状图、折线图、散点图等,而饼图则是其中最常用的一种。本文将深入探讨 ECharts 饼…...
arcGIS使用笔记(无人机tif合并、导出、去除黑边、重采样)
无人机航拍建图之后,通过大疆智图软件可以对所飞行的区域的进行拼图,但是如果需要对拼好的图再次合并,则需要利用到arcGIS软件。下面介绍arcGIS软件在这个过程中常用的操作。 1.导入tif文件并显示的方法:点击“”图标进行导入操作…...
0 前言
ArCS作为一个基于Rust的CAD(计算机辅助设计)开源系统,尽管已经有四年未更新,但其设计理念和技术实现仍然具有很高的学习和参考价值。以下是对ArCS项目的进一步分析和解读: 一、项目亮点与技术优势 高效与安全的Rust语…...
ubuntu server 安装
1 获取ubuntu https://ubuntu.com/download/server 2 安装ubuntu 详细教程查看视频: ubunut server 安装_哔哩哔哩_bilibili...
linux 添加默认网关
在linux 可以使用 route 命令添加默认网关,假设添加的默认网关是192.168.159.2 添加方式如下: route add default gw 192.168.159.2 以上命令只需要把add 改成 del ,就能删除刚才添加的路由 route del default gw 192.168.159.2 #该命…...
一个开源的自托管虚拟浏览器项目,支持在安全、私密的环境中使用浏览器
大家好,今天给大家分享一个开源的自托管虚拟浏览器项目Neko,旨在利用 WebRTC 技术在 Docker 容器中运行虚拟浏览器,为用户提供安全、私密且多功能的浏览体验。 项目介绍 Neko利用 WebRTC 技术在 Docker 容器中运行虚拟浏览器,提供…...
Qt之修改窗口标题、图标以及自定义标题栏(九)
Qt开发 系列文章 - titles-icons-titlebars(九) 目录 前言 一、修改标题 二、添加图标 三、更换标题栏 1.效果演示 2.创建标题栏类 3.定义相关函数 4.使用标题栏类 总结 前言 在我们利用Qt设计软件时,经常需要修改窗口标题、更改软…...
can总线相关概念---frame-signal-message
1、frame 帧是数据链路层的传输单元。它将上层传入的数据添加一个头部和尾部,组成了帧。它的起始点和目的点都是数据链路层。 2、signal 3、message-报文 我们将位于应用层的信息分组称为报文。报文是网络中交换与传输的数据单元,也是网络传输的单元。…...
全排列 dfs
给定一个由不同的小写字母组成的字符串,输出这个字符串的所有全排列。 我们假设对于小写字母有 a<b<…<y<z ,而且给定的字符串中的字母已经按照从小到大的顺序排列。 输入格式 输入只有一行,是一个由不同的小写字母组成的字符串…...
画图,matlab,
clear;close all;clc;tic;dirOutput dir(*.dat); % 罗列所有后缀-1.dat的文件列表,罗列BDDATA的数据 filenames string({dirOutput.name}); % 提取文件名%% 丢包统计 FILENAMES [""]; LOSS_YTJ [ ]; LOSS_RAD [ ]; LOSS_ETH [ ]…...
any/all 子查询优化规则的原理与解析 | OceanBase查询优化
背景 在通常情况下,当遇到包含any/all子查询的语句时,往往需要遵循嵌套执行的方式,因此其查询效率较低。Oceanbase中制定了相应的any/all子查询优化规则,能够能够识别并优化符合条件的any/all子查询,从而有效提升查询…...
Visio——导出的PDF文件缺乏嵌入字体的解决办法 / 设置导出的PDF文件添加嵌入字体的方法
导出PDF时,勾选 “符合PDF/A” 选项 这样就导出的PDF文件添加了嵌入字体了。...
python:用 sklearn SVM 构建分类模型,并评价
编写 test_sklearn_5.py 如下 # -*- coding: utf-8 -*- """ 使用 sklearn 估计器构建分类模型,并评价 """ import numpy as np import matplotlib.pyplot as plt from sklearn import datasets from sklearn.svm import SVC from sk…...
【Python】制作函数,并且实现【注册】【登录】功能
这段代码是一个简单的命令行论坛模拟系统,包含了用户注册、登录和退出的功能。让我们逐行分析代码,并解释每个部分的功能与逻辑: ### 1. 引入 hashlib 模块 python import hashlib - **功能**:引入 Python 内置的 hashlib 模块…...
【大模型】LLaMA-2:Open Foundation and Fine-Tuned Chat Models, July. 2023.
论文:LLaMA-2:Open Foundation and Fine-Tuned Chat Models, July. 2023. 链接:https://arxiv.org/abs/2307.09288 Introduction 创新点 7B - 70B 预训练 微调 开源Llama 2 和Llama 2-Chat,针对对话用例进行了优化Motivation A…...
WebRTC服务质量(04)- 重传机制(01) RTX NACK概述
WebRTC服务质量(01)- Qos概述 WebRTC服务质量(02)- RTP协议 WebRTC服务质量(03)- RTCP协议 WebRTC服务质量(04)- 重传机制(01) RTX NACK概述 WebRTC服务质量(…...
Qt之connectSlotsByName分析
简介 用于界面设置信号槽自动生成,要求槽函数定义形式为on_< objectName >_< signal > connectSlotsByName 其定义在QMetaObject类中,为静态方法,在文件qobjectdefs.h struct Q_CORE_EXPORT QMetaObject {....static void c…...
【Unity3D】无限循环列表(扩展版)
基础版:【Unity技术分享】UGUI之ScrollRect优化_ugui scrollrect 优化-CSDN博客 using UnityEngine; using UnityEngine.UI; using System.Collections.Generic;public delegate void OnBaseLoopListItemCallback(GameObject cell, int index); public class BaseLo…...
校园点餐订餐外卖跑腿Java源码
简介: 一个非常实用的校园外卖系统,基于 SpringBoot 和 Vue 的开发。这一系统源于黑马的外卖案例项目 经过站长的进一步改进和优化,提供了更丰富的功能和更高的可用性。 这个项目的架构设计非常有趣。虽然它采用了SpringBoot和Vue的组合&am…...
如何使用 Python 连接 PostgreSQL 数据库?
在Python开发中,连接PostgreSQL数据库是一个常见的需求。 我们可以使用多种库来实现这一功能,其中最常用的是psycopg2。 下面我将详细介绍如何使用psycopg2来连接PostgreSQL数据库,并提供一些实际开发中的建议和注意事项。 1. 使用 psycop…...
音频开发中常见的知识体系
在 Linux 系统中,/dev/snd 目录包含与声音设备相关的文件。每个文件代表系统中的一部分音频硬件或音频控制接口。以下是你列出的文件及其含义: 一.基本术语 样本长度(sample):样本是记录音频数据最基本的单位,计算机对每个通道采…...
国内外人工智能AI工具网站大全(一键收藏,应有尽有)
本文由 大侠(AhcaoZhu)原创,转载请声明。 链接: https://blog.csdn.net/Ahcao2008 国内外人工智能AI工具网站大全(一键收藏,应有尽有) 摘要一、AI写作工具二、AI图像工具2.1、常用AI图像工具2.2、AI图片插画生成2.3、AI图片背景移…...
HB1910数字IP程控交换机generate.php存在RCE漏洞
免责声明: 本文旨在提供有关特定漏洞的深入信息,帮助用户充分了解潜在的安全风险。发布此信息的目的在于提升网络安全意识和推动技术进步,未经授权访问系统、网络或应用程序,可能会导致法律责任或严重后果。因此,作者不对读者基于本文内容所采取的任何行为承担责任。读者在…...
基于Spring Boot的社区药房系统
一、系统背景与目的 随着医疗改革的深入和社区医疗服务的不断完善,社区药房在居民健康保障中扮演着越来越重要的角色。然而,传统的药房管理方式存在着库存管理混乱、药品销售不透明、客户信息管理不规范等问题。为了解决这些问题,基于Spring…...
level2逐笔委托查询接口
沪深逐笔委托队列查询 前置步骤 分配数据库服务器 查询模板 以下是沪深委托队列查询的请求模板: http://<数据库服务器>/sql?modeorder_book&code<股票代码>&offset<offset>&token<token>查询参数说明 参数名类型说明mo…...
固定资产分类,提升资产盘活效益
固定资产是企业长期使用的重要资源,涵盖范围广、种类多,不同的资产需要针对性管理。通过科学的分类与高效的盘活策略,不仅可以优化资源配置,还能提升企业资产的利用效率和经济效益。以下将详细解析固定资产的分类方式和盘活效益的…...
图像根据mask拼接时,边缘有色差 解决
目录 渐变融合(Feathering) 沿着轮廓线模糊: 代码: 泊松融合 效果比较好: 效果图: 源代码: 泊松融合,mask不扩大试验 效果图: 源代码: 两个图像根据mask拼接时,边缘有色差 渐变融合(Feathering) import numpy as np import cv2# 假设 img1, img2 是两个…...
练习题:一维数组
练习题 第一题 键盘录入一组数列,利用冒泡排序将数据由大到小排序 代码 #include <stdio.h>int arr_home01() {int arr[10];int i,j,temp;printf("请输入10个测试整数:\n");int len sizeof(arr) / sizeof(arr[0]);for(i 0;i < …...
Linux系统安装node.js
一、node官网下载想要的node版本 https://nodejs.org/en/download/package-manager 二、将tar.xz文件解压 tar -xvf node-vxxx.tar.xz 三、改文件夹的名字,改成nodejs mv node-xxx nodejs 四、复制nodejs文件,并上传到linux 服务器 /usr/local 目录下…...
lettuce 默认情况下连接池参数不生效,源码分析
先说结论: 1.LettuceConnectionFactory 属性 shareNativeConnection 默认为true,要想连接池生效,该参数设置为false; 2.使用redisTemplate模版封装的pipeline没有意义,autoFlashCommands 默认为true;spring2.0开始默认使用lettuc…...
三维无人机航迹算法的目标函数如何确定
一、定义目标函数 在三维无人机航迹算法中,目标函数的确定通常基于具体的任务需求和飞行约束。以下是一个简单的例子,展示了如何为三维无人机航迹规划定义一个目标函数。 例子:最小化飞行时间和避障的三维无人机航迹规划 1.任务描述:无人机需要从起点飞到终点,同时避开一些…...
Linux docker离线部署
1. Docker下载 Docker下载地址:https://mirrors.dahuatech.com/docker-ce/。本文下载当前最新版本,链接如下:https://mirrors.dahuatech.com/docker-ce/linux/static/stable/aarch64/docker-27.4.0.tgz。 2. 安装Docker 将压缩包上传到服务器…...
短剧系统开发教程概要
引言 随着移动互联网的快速发展,短剧内容因其简短、精炼、情节紧凑的特点,吸引了大量观众的喜爱。为了满足市场需求,开发一款功能完善、体验优良的短剧平台显得尤为重要。本文将详细介绍短剧源码的开发搭建过程,包括需求分析、技…...
MySQL分区建表例子
以下为MySQL分区建表的例子 CREATE TABLE mz_mjzcfxxmx (SERIALNUM_ID varchar(96) NOT NULL COMMENT 业务角度唯一性ID,DATAGENERATE_DATE datetime NOT NULL COMMENT 业务数据产生时间,ROW_ID varchar(300) DEFAULT NULL COMMENT 数据角度唯一性ID,TASK_ID varchar(96) DEFAU…...
nginx变量
一、Nginx 变量概述 Nginx 变量是一种在 Nginx 配置中用于存储和操作数据的机制,它们可以在不同的配置块(如 http、server、location 等)中使用,以实现动态配置和灵活的请求处理。变量的值可以根据各种条件(如请求头信…...
网络编程 02:IP 地址,IP 地址的作用、分类,通过 Java 实现 IP 地址的信息获取
一、概述 记录时间 [2024-12-18] 前置文章:网络编程 01:计算机网络概述,网络的作用,网络通信的要素,以及网络通信协议与分层模型 本文讲述网络编程相关知识——IP 地址,包括 IP 地址的作用、分类ÿ…...
小红书笔记详情API接口:解锁社交媒体商业价值的钥匙
在当今数字化时代,社交媒体平台已成为企业营销和品牌推广的重要渠道。小红书,作为一个以内容分享为核心的社交媒体平台,汇聚了大量用户和创作者,他们在这里分享生活心得、购物体验、美妆技巧等多元化内容。小红书笔记详情API接口&…...
达梦查询表字段详细信息脚本(字段名称、描述、类型、长度及是否为空)
达梦查询表字段详细信息脚本(字段名称、描述、类型、长度及是否为空) 该SQL 脚本,用于查询表中字段的基本信息,包括字段名称、描述、数据类型、数据长度、是否为空及是否为主键等属性。 SQL 脚本 -- 输入变量 DECLAREp_owner VA…...