当前位置: 首页 > news >正文

【PTA数据结构 | C语言版】前缀树的3个操作

本专栏持续输出数据结构题目集,欢迎订阅。

文章目录

    • 题目
    • 代码

题目

请编写程序,利用前缀树查找给定字符串是否在某给定字符串集合 S 中。

输入格式:
输入首先给出一个正整数 n(≤1000),随后 n 行,每行给出一个仅由小写英文字母组成、长度不超过 1000 的字符串,以回车结尾。以上为给定字符串集合 S。
接下来给出查询请求。首先给出一个正整数 m(≤1000),随后 m 行,每行给出一个仅由小写英文字母组成、长度不超过 1000 的待查找字符串,以回车结尾。

输出格式:
对每个待查找的字符串,如果它在 S 中,则在一行中输出 yes;否则输出 no。

输入样例:
3
binarytree
trie
binarysearch
5
binary
trie
tree
binarytree
binarysearch

输出样例:
no
yes
no
yes
yes

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_N 10000
#define MAX_LENGTH 10001// 字符串比较函数,用于qsort
int compare(const void *a, const void *b) {return strcmp(*(const char **)a, *(const char **)b);
}// 二分查找函数
int binary_search(const char **arr, int n, const char *target) {int left = 0, right = n - 1;while (left <= right) {int mid = left + (right - left) / 2;int cmp = strcmp(arr[mid], target);if (cmp == 0) {return 1; // 找到目标字符串} else if (cmp < 0) {left = mid + 1;} else {right = mid - 1;}}return 0; // 未找到目标字符串
}int main() {int n, m;char **S = (char **)malloc(MAX_N * sizeof(char *));// 读取集合 Sscanf("%d", &n);getchar(); // 消耗掉scanf后的换行符for (int i = 0; i < n; i++) {S[i] = (char *)malloc(MAX_LENGTH * sizeof(char));fgets(S[i], MAX_LENGTH, stdin);// 移除换行符size_t len = strlen(S[i]);if (len > 0 && S[i][len - 1] == '\n') {S[i][len - 1] = '\0';}}// 对集合 S 进行排序,以便使用二分查找qsort(S, n, sizeof(char *), compare);// 处理查询scanf("%d", &m);getchar(); // 消耗掉scanf后的换行符for (int i = 0; i < m; i++) {char query[MAX_LENGTH];fgets(query, MAX_LENGTH, stdin);// 移除换行符size_t len = strlen(query);if (len > 0 && query[len - 1] == '\n') {query[len - 1] = '\0';}// 使用二分查找判断查询字符串是否存在于集合 S 中if (binary_search(S, n, query)) {printf("yes\n");} else {printf("no\n");}}return 0;
}    
http://www.lryc.cn/news/590196.html

相关文章:

  • 关于程序=数据结构+算法这句话最近的一些思考
  • 数字ic后端设计从入门到精通11(含fusion compiler, tcl教学)全定制设计入门
  • Java-数构链表
  • golang语法-----指针
  • 笔试——Day10
  • 简单易懂,什么是连续分配管理方式
  • Qt 将触摸事件转换为鼠标事件(Qt4和Qt5及以上版本)
  • Java线程创建与运行全解析
  • DuckDB 高效导入 IPv6 地址数据的实践与性能对比
  • #Datawhale组队学习#7月-强化学习Task1
  • java解析word文档
  • 使用JS编写一个购物车界面
  • C++ 面向对象
  • 第2章通用的高并发架构设计——2.3 高并发读场景方案2:本地缓存
  • 开源 python 应用 开发(七)数据可视化
  • Linux 定时器应用示例(修正版)
  • GIT版本回退
  • Python中可以反转的数据类型
  • GaussDB 数据库架构师修炼(五) 存储容量评估
  • 搜索框的显示与隐藏(展开与收起)
  • el-input 回显怎么用符号¥和变量拼接展示?
  • openEuler 22.03 LTS Rootless Docker 安装指南
  • MongoDB复杂查询 聚合框架
  • 洛谷 P11247 [GESP202409 六级] 算法学习-普及/提高-
  • pymongo库:简易方式存取数据
  • ETL还是ELT,大数据处理怎么选更靠谱?
  • 步态循环(Gait Cycle)
  • 【MySQL事务和锁】回顾事务
  • 图像质量评价(Image Quality Assessment,IQA)
  • 调试bug记录