Linux 利用 ftrace 分析内核调用

目录

  • 一、概述
  • 二、ftrace 的使用
    • 1、常用信息
    • 2、指定 ftrace 跟踪器
    • 3、设置要跟踪的函数
    • 4、ftrace 的开关
    • 5、function 跟踪程序
    • 6、function_graph 跟踪程序
    • 7、函数过滤器
    • 8、跟踪事件
  • 三、trace-cmd 的使用
    • 1、常见命令
    • 2、常用选项
      • 2.1 列出可用的追踪器
      • 2.2 跟踪特定进程的函数调用
      • 2.3 函数过滤
      • 2.4 限制跟踪深度
      • 2.5 追踪特定事件
      • 2.6 了解可被追踪的函数


一、概述

在 Linux 中,ftrace 是一种用于跟踪内核函数调用和事件的工具。它是一个功能强大的跟踪框架,可用于分析和调试内核性能问题。

ftrace 提供了多种功能,包括函数跟踪、事件记录和性能分析等。它能够记录函数的调用和返回信息,以及函数执行的路径和时间。通过跟踪这些信息,我们可以了解到内核函数的执行情况,从而定位和解决性能问题。

ftrace 使用了内核中的一些机制来实现跟踪功能。其中一个关键的机制是函数预编译器,它会在每个内核函数的入口和出口处插入一些特殊的指令,用于记录函数的调用和返回信息。这些指令可以通过内核配置选项来启用或禁用。

此外,ftrace 还支持事件跟踪,可以记录系统中发生的各种事件,比如中断、系统调用、定时器事件等。通过分析这些事件的发生频率和顺序,可以帮助我们找出系统中的瓶颈和性能问题。

除了记录和分析跟踪信息外,ftrace 还提供了一些工具和接口,用于配置和控制跟踪功能。其中最常用的工具是 trace-cmdtrace-cmd-report,它们可以用来收集和分析跟踪数据。

二、ftrace 的使用

1、常用信息

ftrace 是一个自 Linux 2.6 版本起就支持的内核调试工具。最初,ftrace 主要用于函数级别的跟踪(function trace),但经过不断发展,ftrace现已成为一个通用的调试框架,能够实现多种跟踪目的。

ftrace通过 debugfs 虚拟文件系统向用户空间提供访问接口。通常,debugfs 会挂载在 /sys/kernel/debug 目录下,而 ftrace的控制和输出文件位于该目录下的 tracing子目录中,完整路径为 /sys/kernel/debug/tracing。所以要使用 ftrace,就要先进入到 sys/kernel/debug/tracing 目录中(仅对 root 用户可用):

$ cd /sys/kernel/debug/tracing

这个目录下的内容如下:

其中的核心文件介绍如下表:

文件描述
available_tracers可用跟踪器,hwlat blk function_graph wakeup_dl wakeup_rt wakeup function nop,nop 表示不使用跟踪器
current_tracer当前使用的跟踪器
function_profile_enabled启用函数性能分析器
available_filter_functions可跟踪的完整函数列表
set_ftrace_filter选择跟踪函数的列表,支持批量设置,例如 tcp、tcptcp
set_ftrace_notrace设置不跟踪的函数列表
set_event_pid设置跟踪的 PID,表示仅跟踪 PID 程序的函数或者其他跟踪
tracing_on是否启用跟踪,1 启用跟踪;0 关闭跟踪
trace_options设置跟踪的选项
trace_stat(目录)函数性能分析的输出目录
kprobe_events启用 kprobe 的配置
uprobe_events启用 uprobe 的配置
events ( 目录 )事件(Event)跟踪器的控制文件: tracepoint、kprobe、uprobe
trace跟踪的输出 (Ring Buffer)
trace_pipe跟踪的输出;提供持续不断的数据流,适用于程序进行读取

更详细的信息查阅 ftrace 官方文档。

2、指定 ftrace 跟踪器

ftrace 支持多种追踪类型,包括函数调用、函数图、硬件延迟、中断关闭、抢占关闭等,我们可以用上一小节提到的 available_tracers 来查看可用的跟踪器:

$ sudo cat  /sys/kernel/debug/tracing/available_tracers
timerlat osnoise hwlat blk mmiotrace function_graph wakeup_dl wakeup_rt wakeup function nop

如下是其中一些特性的介绍:

  • function : 一个无需参数的函数调用跟踪程序
  • function_graph : 一个使用子调用的函数调用跟踪程序
  • blk: 一个与块 I/O 跟踪相关的调用和事件跟踪程序(它是 blktrace 使用的)
  • mmiotrace: 一个内存映射 I/O 操作跟踪程序
  • nop :最简单的跟踪程序,就像它的名字所暗示的那样,它不做任何事情

其中比较常用的是 functionfunction_graph。如要要设置跟踪器类型,需要把类型写入到 current_tracer 文件。比如设置类型为 function_graph 可以这样操作

sudo sh -c "echo function_graph > /sys/kernel/debug/tracing/current_tracer"

3、设置要跟踪的函数

set_ftrace_filter 表示要跟踪的函数,比如追踪 epoll_wait 可以这样操作:

sudo sh -c "echo SyS_epoll_wait > /sys/kernel/debug/tracing/set_ftrace_filter"

set_graph_function 用于设置 function_graph 跟踪器的触发函数。它不仅跟踪指定的函数,还跟踪该函数调用的所有子函数。

4、ftrace 的开关

ftrace 的开关是通过 tracing_on 文件来控制的。

# 关闭 trace
$ sudo sh -c "echo 0 > /sys/kernel/debug/tracing/tracing_on"# 开启 trace
$ sudo sh -c "echo 1 > /sys/kernel/debug/tracing/tracing_on"

5、function 跟踪程序

先写一个脚本文件 trace.sh,再执行:

$ cat trace.sh
#!/bin/shdir=/sys/kernel/debug/tracingsysctl kernel.ftrace_enabled=1
echo function > ${dir}/current_tracer
echo 1 > ${dir}/tracing_on
sleep 1
echo 0 > ${dir}/tracing_on
less ${dir}/trace$ sudo sh trace.sh

脚本运行完成后,我们将看到下列的输出:

这个输出以“缓冲区中的信息条目数量”和“写入的全部条目数量”开始。这两者的数据差异是缓冲区中事件的丢失数量(在我们的示例中没有发生丢失)。

在这里有一个包含下列信息的函数列表:

  • 进程标识符(PID)
  • 运行这个进程的 CPU(CPU#)
  • 进程的时间戳(TIMESTAMP)
  • 被跟踪函数的名字以及调用它的父级函数;例如,在我们输出的第一行,rb_simple_write 调用了 mutex-unlock 函数。

6、function_graph 跟踪程序

function_graph 跟踪程序的工作和函数跟踪程序一样,但是它更详细:它显示了每个函数的进入和退出点。使用这个跟踪程序,我们可以跟踪函数的子调用并且测量每个函数的运行时间。

还是一样,先写一个脚本文件 trace.sh:

$ cat trace.sh
#!/bin/shdir=/sys/kernel/debug/tracingsysctl kernel.ftrace_enabled=1
echo function_graph > ${dir}/current_tracer
echo 1 > ${dir}/tracing_on
sleep 1
echo 0 > ${dir}/tracing_on
less ${dir}/trace$ sudo sh trace.sh

运行这个脚本之后,我们将得到如下的输出:

DURATION 展示了花费在每个运行的函数上的时间。注意使用 + 符号标记的地方。加号(+)意思是这个函数花费的时间超过 10 毫秒;而如果用感叹号(!)则表示是这个函数花费的时间超过了 100 毫秒。

FUNCTION_CALLS 下面,我们可以看到每个函数调用的信息。

和 C 语言一样使用了花括号 { } 标记每个函数的边界,它展示了每个函数的开始和结束,一个用于开始,一个用于结束;不能调用其它任何函数的叶子函数用一个分号 ; 标记。

7、函数过滤器

ftrace 输出可能会很庞大,精确找出我们所需要的内容可能会非常困难。我们可以使用过滤器去简化我们的搜索:输出中将只显示与我们感兴趣的函数相关的信息。为实现过滤,我们只需要在 set_ftrace_filter 文件中写入我们需要过滤的函数的名字即可。例如:

$ echo kfree > set_ftrace_filter

如果禁用过滤器,我们只需要在这个文件中添加一个空白行即可:

$ echo  > set_ftrace_filter

而 *set_ftrace_notrace * 会得到和 set_ftrace_filter 相反的结果,例如:

$ echo kfree > set_ftrace_notrace 

输出将包含除了 kfree() 以外的任何函数的信息。

另外还有 set_ftrace_pid。它是为在一个特定的进程运行期间调用跟踪函数准备的。

8、跟踪事件

在Linux中,跟踪点(tracepoints)是一种用于动态跟踪程序执行的机制。它是一种轻量级的调试技术,可以在不修改程序源代码的情况下监视系统和应用程序的执行过程。

跟踪点可以被视为在程序的不同位置放置的断点,当程序执行到这些位置时会触发相应的跟踪记录。这些跟踪记录可以提供有关程序行为的有用信息,如函数调用、系统调用、中断事件等。

Linux中的跟踪点分为两类:

  • 内核跟踪点:这些跟踪点嵌入在Linux内核中,用于跟踪内核事件,如系统调用、中断、调度事件等。内核跟踪点是通过Linux动态跟踪(LTTng)和ftrace等工具提供的。
  • 用户空间跟踪点:这些跟踪点是在用户空间应用程序中定义的,用于跟踪应用程序的执行过程。用户空间跟踪点是通过perf工具和SystemTap等工具提供的。

在 Linux 内核中为了从用户空间使用跟踪点,它有一个专门的 API。在 /sys/kernel/debug/tracing 目录中,这里有一个事件目录,它是为了保存系统事件。这些只是为了跟踪系统事件。在这个上下文中系统事件可以理解为包含在内核中的跟踪点。

可以通过运行如下的命令来查看这个事件列表:

$ sudo cat /sys/kernel/debug/tracing/available_events

这个命令将在控制台中输出一个很长的列表。这样看起来很不方便。我们可以使用如下的命令来列出一个结构化的列表:

所有可能的事件都按子系统分组到子目录中。在我们开始跟踪事件之前,我们要先确保启用跟踪,也就是前面提到的 tracing_on 必须为 1。

所有事件相关的系统调用都保存在系统调用目录下。在这里我们将找到一个进入和退出各种系统调用的目录。我们需要在相关的文件中通过写入数字 1 来激活跟踪点:

$ echo 1 > /sys/kernel/debug/tracing/events/syscalls/sys_enter_chroot/enable
$ cat /sys/kernel/debug/tracing/events/syscalls/sys_enter_openat/format
name: sys_enter_openat
ID: 643
format:field:unsigned short common_type;	offset:0;	size:2;	signed:0;field:unsigned char common_flags;	offset:2;	size:1;	signed:0;field:unsigned char common_preempt_count;	offset:3;	size:1;	signed:0;field:int common_pid;	offset:4;	size:4;	signed:1;field:int __syscall_nr;	offset:8;	size:4;	signed:1;field:int dfd;	offset:16;	size:8;	signed:0;field:const char * filename;	offset:24;	size:8;	signed:0;field:int flags;	offset:32;	size:8;	signed:0;field:umode_t mode;	offset:40;	size:8;	signed:0;print fmt: "dfd: 0x%08lx, filename: 0x%08lx, flags: 0x%08lx, mode: 0x%08lx", ((unsigned long)(REC->dfd)), ((unsigned long)(REC->filename)), ((unsigned long)(REC->flags)), ((unsigned long)(REC->mode))

这里直接使用 tracepoint 跟踪 sys_openat 系统调用,设置如下:

$ echo 1 > /sys/kernel/debug/tracing/events/syscalls/sys_enter_openat/enable
$ echo 1 > /sys/kernel/debug/tracing/tracing_on
$ cat /sys/kernel/debug/tracing/trace

我们通过设置 sys_enter_openat/enable 开启对于 sys_enter_openat 的跟踪,trace 文件中的跟踪记录格式与 sys_enter_openat/format 中的 print 章节的格式一致。

print fmt: "dfd: 0x%08lx, filename: 0x%08lx, flags: 0x%08lx, mode: 0x%08lx" ...

结果如下:

关于 sys_enter_openat/filter 文件为跟踪记录的过滤条件设置,格式如下:

field operator value

其中:

  • fieldsys_enter_openat/format 中的字段。
  • operator 为比较符
    • 整数支持:==,!=,</、,<=,>= 和 & ,
    • 字符串支持 ==,!=,~ 等,其中 ~ 支持 shell 脚本中通配符 *,?,[] 等操作。
    • 不同的条件也支持 && 和 || 进行组合。

如需要通过 format 格式中的 mode 字段过滤:

field:umode_t mode;	offset:40;	size:8;	signed:0;

只需要将进行如下设置即可:

$ sudo echo 'mode != 0' >  events/syscalls/sys_enter_openat/filter

如果需要清除 filter,直接设置为 0 即可:

$ sudo echo 0 > events/syscalls/sys_enter_openat/filter

三、trace-cmd 的使用

从上面的例子看出使用 ftrace 还是挺麻烦的,真正使用时实际上使用 trace-cmd 更多一点。trace-cmd 是一个用户空间的命令行工具,用于与 ftrace 进行交互。它提供了一个更方便的接口来配置和使用 ftrace,避免了直接操作 debugfs 文件系统的麻烦。

1、常见命令

trace-cmd 的常见命令如下:

  • trace-cmdrecord:记录实时跟踪数据并将其写入trace.dat 文件
  • trace-cmd report:读取 trace.dat 文件并将二进制数据转换为可读的 ASCII 文本格式。
  • trace-cmd start:开始跟踪但不记录到 trace.dat 文件。
  • trace-cmd stop:停止跟踪。
  • trace-cmd extract:从内核缓冲区提取数据并创建 trace.dat 文件。
  • trace-cmd reset:禁用所有跟踪并恢复系统性能。

下面使用 record 记录 trace 数据:

$ trace-cmd record -p function_graph -e syscalls

注意 trace-cmd 默认开启了 funcgraph-proc 这个 trace-option,不需要手动指定。

使用 ctrl-c 退出这个 trace-cmd 时,会在当前目录生成 trace.dat文件。接下来使用 report 读取 trace.dat 生成可读的文本:

$ trace-cmd report trace.dat

2、常用选项

2.1 列出可用的追踪器

当使用 ftrace 时,你必须查看文件的内容以了解有哪些追踪器可用。但使用 trace-cmd,你可以通过以下方式获得这些信息:

$ trace-cmd list -e
trace-cmd: Permission deniedreading /sys/kernel/tracing/available_tracers

它还可以带一个可选的参数,使用正则表达式进行过滤:

$ trace-cmd list -e '^sched.*' # 列出所有以 sched 开头的事件

2.2 跟踪特定进程的函数调用

如果只想跟踪特定进程的函数调用,可以使用 -P 选项指定进程的 PID。例如,要跟踪用户进程 PID 为 1656 的进程,可以使用以下命令:

$ trace-cmd record -p function_graph -P 1656

2.3 函数过滤

-g 选项用于 function_graph 插件,-g do_sys_open 表示只跟踪 do_sys_open 函数及其调用的所有子函数。

$ trace-cmd record -p function_graph -g do_sys_open

-l 选项指定要跟踪的函数。例如,要跟踪所有以 ext4 开头的函数,可以使用以下命令

$ trace-cmd record -p function_graph -l "ext4_*"

-l 和 -g 的区别也比较显而易见:

  • -l 不会跟踪其内部的调用子函数;
  • -g 会跟踪函数内部调用的子函数。

2.4 限制跟踪深度

默认情况下,trace-cmdfunction_graph 会记录所有嵌套的函数调用。可以通过设置 --max-graph-depth 来限制跟踪深度。例如要将深度设置为 2,可以使用以下命令:

$ trace-cmd record -p function_graph --max-graph-depth 2 -P 1656

2.5 追踪特定事件

可以结合事件追踪 -e 来获取更详细的信息,比如 -es ched:sched_switch 将指定追踪调度切换事件。还可以使用正则表达式过滤,比如追踪 tcp 相关的事件:

$ trace-cmd record -e "tcp:*"

2.6 了解可被追踪的函数

如果你想只追踪某些函数而忽略其他的,你需要知道确切的函数名称。你可以用 list -f 参数来得到它们。例如搜索常见的内核函数 kmalloc,它被用来在内核中分配内存:

$ trace-cmd list -f | grep kmalloc
bpf_map_kmalloc_node
mempool_kmalloc
__traceiter_kmalloc
__traceiter_kmalloc_node
kmalloc_slab
kmalloc_order
kmalloc_order_trace
kmalloc_large_node
__kmalloc_track_caller
__kmalloc_node_track_caller
__kmalloc
__kmalloc_node
bio_kmalloc
devm_kmalloc_match
devm_kmalloc_release
devm_kmalloc
sock_kmalloc
kmalloc_reserve
kmalloc_fix_flags
drmm_kmalloc [drm]

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

计算机毕业设计选题推荐-课程教学平台-Java/Python项目实战

✨作者主页&#xff1a;IT毕设梦工厂✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Py…

ceph

ceph是一个开源的&#xff0c;用c语言编写的分布式的存储系统。存储文件数据。 /dev/sdb fdisk /dev/sdb gdisk /dev/sdb lvm 逻辑卷 可以扩容 raid 磁盘 高可用 基于物理意义上的单机的存储系统。 分布式由多台物理磁盘组成一个集群&#xff0c;在这个基础之上实现高可…

激光导航AGV叉车那么多,究竟该怎么选?一篇文章讲明白~

AGV叉车 随着经济的快速发展&#xff0c;大部分企业的物料搬运开始脱离人工劳作&#xff0c;取而代之的是以叉车为主的机械化搬运。AGV叉车是工业搬运车辆&#xff0c;是指对成件托盘货物进行装卸、堆垛和短距离运输作业的各种轮式搬运车辆&#xff0c;主要应用于货场、工厂车间…

HslCommunicationDemo各品牌Plc通信测试软件工具

目录 1、HslCommunicationDemo程序包 2、ModbusTCP举例说明 (0)概述 &#xff08;1&#xff09;线圈写操作 &#xff08;2&#xff09;寄存器写操作 3、C#工程中DLL库文件使用 &#xff08;1&#xff09;创建Winform程序工程 &#xff08;2&#xff09;写寄存器 1、HslC…

基于内地城市生活垃圾收运场景的路线规划算法

基于混合遗传算法和模拟退火算法的优化垃圾收集路线规划 摘要 本文提出了一种基于混合遗传算法&#xff08;GA&#xff09;和模拟退火算法&#xff08;SA&#xff09;的创新路线规划方法&#xff0c;旨在优化内地城市的生活垃圾收集效率。算法结合了遗传算法的全局搜索能力和…

MySQL第1讲--详细安装教程和启动方法

文章目录 安装教程打开或关闭方式方式1&#xff1a;方式2&#xff1a; 客户端连接方式客户端连接方式1&#xff1a;客户端连接方式2&#xff1a;MySQL环境变量的配置 安装教程 1、mysql官网下载最新的符合本系统的版本 2、点击.msi文件进入安装页面 选择默认的选项开发者安…

15.DMDIS 工具优化

文章目录 前言一、安装部署安装数据源转换作业监控 二、性能优化问题 1 &#xff1a;DMETL 卡顿问题问题 2 &#xff1a;DM -> HIVE 的迁移速度慢问题 3 &#xff1a;ORACLE -> DM 的迁移速度慢问题 4 &#xff1a;GP -> DM 的迁移速度慢问题 5 &#xff1a;DM -> …

[ERR] 1273 - Unknown collation: ‘utf8mb4_0900_ai_ci‘(已解决)

今天在使用navicate Premium运行sql文件时出现如下错误&#xff1a; 错误&#xff1a;1273 - Unknown collation: utf8mb4_0900_ai_ci 报错原因&#xff1a; 生成转储文件&#xff08;也就是sql文件&#xff09;的数据库版本为8.0,而要运行sql文件的数据库版本为5.6,因为是高版…

Android进阶之路 - 字体加粗,定制化字体粗度

在客户端中不论是PC端&#xff0c;还是移动端主要价值之一就体现在用户交互方面&#xff0c;也就是用户体验了&#xff0c;接下来讲的是很常见的字体加粗问题 UI大找茬 深入浅出字体、字体库TextView文本渐变字体阴影、文字阴影字体加粗 - 定制化字体粗度 在开发中经常会遇到…

DFS之搜索顺序与剪枝

搜索顺序&#xff1a; 1.https://www.acwing.com/problem/content/1119/ 首先&#xff0c;我们考虑一个贪心&#xff1a; 假如说A的倒数K个字符恰好与B的前K个字符重合&#xff0c;那么我们就连接。 也就是说我们一旦匹配就直接相连而不是继续找更长的重合的一段子串。 因…

【学习方法】高效学习因素 ② ( 学习动机 | 内在学习动机 | 外在学习动机 | 外在学习动机的调整方向 | 保护学习兴趣 | 高考竞争分析 )

文章目录 一、高效学习的其它因素 - 学习动机1、学习动机2、内在学习动机3、外在学习动机4、外在学习动机的问题所在5、外在学习动机的调整方向6、保护学习兴趣7、高考竞争分析 上一篇博客 【学习方法】高效学习因素 ① ( 开始学习 | 高效学习因素五大因素 | 高效学习公式 - 学…

unplugin-vue-components 插件配置 忽略 部分目录下的组件自动导入

背景 vue3 项目 为了省略 第三方库ui 组件 全局组件的注册代码&#xff0c;使用了 unplugin-vue-components 插件 原理 组件识别 在编译阶段&#xff0c;unplugin-vue-components 会扫描 Vue 单文件组件&#xff08;.vue 文件&#xff09;的模板部分&#xff0c;识别出所有使…

day31

3.9 信号量集 1> 原理图 信号量集主要完成多个进程之间同步问题 2> 信号量集的API函数接口 1、创建用于生成消息队列的钥匙#include <sys/types.h>#include <sys/ipc.h>key_t ftok(const char *pathname, int proj_id);功能&#xff1a;通过给定的文件路径…

你也觉得FOTA升级难吗?这份详细教程让你自信升级!

前言&#xff1a; 我经常在各个讨论群里看到有合宙Air780EP的用户说&#xff1a; FOTA远程升级有点难呀~一步错后面就得重新来了&#xff0c;有没有大佬给个教程啊&#xff1f; 用户提需求了&#xff0c;那我们肯定要满足啊&#xff0c;就连夜赶了一篇 在整理这篇文章之前&…

掌握 LINQ:通过示例解释 C# 中强大的 LINQ的集运算

文章目录 集运算符原理实战示例1. Union2. Intersect3. Except4. ExceptWith5. Concat6. Distinct 注意事项总结 在C#中&#xff0c;LINQ&#xff08;Language Integrated Query&#xff09;提供了丰富的集合操作功能&#xff0c;使得对集合数据进行查询、过滤、排序等操作变得…

删除有序数组中的重复项(LeetCode)

题目 给你一个 升序排列 的数组 &#xff0c;请你 原地 删除重复出现的元素&#xff0c;使每个元素 只出现一次 &#xff0c;返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 中唯一元素的个数。 考虑 的唯一元素的数量为 &#xff0c;你需要做以下事情确…

CVE-2023-1313

开启靶场 url访问/install来运行安装 http://eci-2ze0wqx38em0qticuhug.cloudeci1.ichunqiu.com/install/ 得知其用户和密码为admin 登录 查找文件上传位置 上传一句话木马文件 <?php echo phpinfo();eval($_POST[flw]);?> 下载查看上传木马路径 复制路径 /storag…

代理IP如何助力品牌保护?

品牌是企业非常重要的无形资产&#xff0c;代表着一个公司、一个产品或服务的价值、信誉和形象。在竞争激烈的市场中&#xff0c;一个强有力的品牌可以帮助公司吸引更多的客户、提高销售、提高客户满意度和忠诚度&#xff0c;还可以帮助公司建立和维护其声誉、增强其企业形象&a…

单词拆分——LeetCode

139.单词拆分 题目 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 注意&#xff1a;不要求字典中出现的单词全部都使用&#xff0c;并且字典中的单词可以重复使用 示例 1&#xff1a; 输入: s &qu…

数据结构实验:树和二叉树(附c++源码:实现树有关算法)

目录 一、实验目的 二、问题分析及数据结构设计 三、算法设计&#xff08;伪代码表示&#xff09; 1. 输入字符序列 创建二叉链表 2. 递归前序遍历 3. 递归中序遍历 4. 递归后序遍历 5. 非递归前序遍历 6. 非递归中序遍历 7. 非递归后序遍历 8. 层次遍历 9. 求二叉…