数据结构+基数排序算法
一、问题描述
实现英文单词按字典序排列的基数排序算法 编写一个程序,采用基数排序方法将一组英文单词按字典顺序排 列。假设单词均由小写字母或空格构成,最长的单词有 MaxLen 个 字母,用相关数据进行测试并输出各趟的排序结果。 用例:R[] = {“ while”, “if”, “if else”, “for”, “do while”, “ switch”} 排序结果: “do while”, “for”, “if”, “if else”, “ while”, “ switch”
二、问题解决
#include <stdio.h>
#include <malloc.h> #include <string.h>
#define MAX_LEN 10 // 单词的最大长度
#define RADIX 27 // 基数 rd 为 27,分
别对应' ','a',...,'z' typedef char String[MAX_LEN + 1]; // 定义 String 为字
符数组类型
typedef struct node
{ String word; struct node *next;
}link_node; // 单链表结点类型 //输出单词 void disp_word(String R[], int n)
{ int i; printf(" "); for(i = 0; i < n; i++) { printf(" %s ", R[i]); } printf("\n");
} //对单词进行预处理,用空格填充尾部至 MAX_LEN 长 void pre_process(String R[], int n)
{ int i, j; for(i = 0; i < n; i++) { if(strlen(R[i]) < MAX_LEN) { for(j = strlen(R[i]); j < MAX_LEN; j++) { R[i][j] = ' '; } R[i][j] = '\0'; } }
} //恢复处理,删除预处理时填充的尾部空格 void end_process(String R[], int n)
{ int i, j; for(i = 0; i < n; i++) { for(j = MAX_LEN - 1; R[i][j] == ' '; j--) R[i][j + 1] = '\0'; }
} //按关键字的第 j 个分量进行分配,进入此过程时各队列一定为空 void distribute(String R[], link_node *head[], link_node *tail[],
int j, int n)
{ int i; // 循环变量 int k; // 队列编号 link_node *p; for(i = 0; i < n; i++) // 依次扫描
R[i],将其入队 { if(R[i][j] == ' ') // 空格时放入 0
号队列中,'a'放入 1 号队列中 k = 0; else k = R[i][j] - 'a' + 1; p = (link_node *)malloc(sizeof(link_node)); // 创建新结点 strcpy(p->word, R[i]); p->next = NULL; if(head[k] == NULL) { head[k] = p; tail[k] = p; } else { tail[k]->next = p; tail[k] = p; } }
} //依次将各非空队列中的结点收集起来,并释放各非空队列中的所有结点 void collect(String R[], link_node *head[])
{ int i; int k = 0; link_node *pre, *p; for(i = 0; i < RADIX; i++) { if(head[i] != NULL) { pre = head[i]; p = pre->next; while(p != NULL) { strcpy(R[k++], pre->word); free(pre); pre = p; p = p->next; } strcpy(R[k++], pre->word); free(pre); } }
} //对 R[0...n-1]进行基数排序 void radix_sort(String R[], int n)
{ int i, j; link_node *head[RADIX], *tail[RADIX]; for(i = MAX_LEN - 1; i >= 0; i--) // 从低位到
高位做 MAX_LEN 趟基数排序 { for(j = 0; j < RADIX; j++) head[j] = tail[j] = NULL; distribute(R, head, tail, i, n); // 第 i 趟分
配 collect(R, head); // 第 i 趟收
集 }
} int main()
{ int n = 6; String R[] = {"while", "if", "if else", "for", "do while",
"switch"}; printf("排序前:"); disp_word(R, n); pre_process(R, n); radix_sort(R, n); end_process(R, n); printf("排序后:"); disp_word(R, n); return 0;
}
三、代码分析
在对这组英文字母排序之前,要使它们的长度保持一致(即用空格填充), 在排序完成之后再将填充的空格删去。这里运用的排序方法时基数排序, 基 数排序是一种非比较排序算法,它根据元素的每个位上的值进行排序。 函数 radix_sort 接受一个字符串数组 R 和数组的长度 n 作为参数。它使 用了两个辅助数组 head 和 tail,用于存储链表的头节点和尾节点。 首先,代码中使用两个循环嵌套来进行基数排序。外层循环从最高位开始,逐 渐向低位移动,共进行 MAX_LEN 趟排序。内层循环用于初始化 head 和 tail 数 组,将它们全部置为 NULL。 每一趟排序中,代码调用了两个函数:distribute 和 collect。这两个函 数分别用于分配和收集元素。函数 distribute 接受参数 R、head、tail、i 和 n,其中 R 是待排序的字符串数组,head 和 tail 是链表的头节点和尾节点数 组,i 表示当前进行排序的位数,n 表示数组的长度。该函数根据第 i 位上的 值将元素分配到不同的链表中。函数 collect 接受参数 R 和 head,其中 R 是 待排序的字符串数组,head 是链表的头节点数组。 该函数将链表中的元素按顺序收集到数组 R 中,完成一趟排序。通过循环 嵌套的方式,代码依次进行每一趟排序,直到最低位排序完成。最终,数组 R 中的元素就按照每个位上的值进行了排序。
相关文章:
数据结构+基数排序算法
一、问题描述 实现英文单词按字典序排列的基数排序算法 编写一个程序,采用基数排序方法将一组英文单词按字典顺序排 列。假设单词均由小写字母或空格构成,最长的单词有 MaxLen 个 字母,用相关数据进行测试并输出各趟的排序结果。 用例&#…...
C++ list【常用接口、模拟实现等】
1. list的介绍及使用 1.1 list的介绍 1.list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。 2.list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前…...
12.面试题——Spring Boot
1.Spring Boot是什么? Spring Boot 是 Spring 开源组织下的子项目,是 Spring 组件一站式解决方案,主要是简化了使用 Spring 的难度,简省了繁重的配置,提供了各种启动器,开发者能快速上手。 2.为什么要用 …...
【前端VUE】npm i 出现版本错误等报错 简单直接解决命令
前端vue npm i 安装时出现 报错原因 在新版本的npm中,默认情况下,npm install遇到冲突的peerDependencies时将失败。 解决办法 使用--force或--legacy-peer-deps可解决这种情况。 --force 会无视冲突,并强制获取远端npm库资源࿰…...
精彩回顾 | 风丘科技亮相2024名古屋汽车工程博览会
2024年7月17日-19日,风丘科技联合德国IPETRONIK亮相日本名古屋汽车工程博览会。该展会面向汽车行业不同应用场景,包括新的eAxle、FCEV、ADAS、测试测量系统和ECU测试等相关技术,是一个专为活跃在汽车行业前线的工程师和研究人员举办的汽车技术…...
设计模式21-组合模式
设计模式21-组合模式(Composite Pattern) 写在前面 动机定义与结构定义结构主要类及其关系 C代码推导优缺点应用场景总结补充叶子节点不重载这三个方法叶子节点重载这三个方法结论 写在前面 数据结构模式 常常有一些组件在内部具有特定的数据结构。如何…...
如何选择深度学习的损失函数和激活函数
一概述 在深度学习中,损失函数(Loss Function)和激活函数(Activation Function)是两个至关重要的组件,它们共同影响着模型的训练效果和泛化能力。本文将简要介绍这两个概念,阐述选择它们的重要性…...
DATAX自定义KafkaWriter
因为datax目前不支持写入数据到kafka中,因此本文主要介绍如何基于DataX自定义KafkaWriter,用来同步数据到kafka中。本文偏向实战,datax插件开发理论宝典请参考官方文档: https://github.com/alibaba/DataX/blob/master/dataxPlug…...
Mybatis分页多表多条件查询
个人总结三种方式: Xml、queryWrapper、PageHelper第三方组件这三种方式进行查询; 方式一: xml中联表查询,在mapper中传参IPage<T>和条件Map(这里用map装参数)。 代码示例: Mapper层 M…...
SpringBoot快速入门(手动创建)
目录 案例:需求 步骤 1 创建Maven项目 2 导入SpringBoot起步依赖 3 定义Controller 4 编写引导类 案例:需求 搭建简单的SpringBoot工程,创建hello的类定义h1的方法,返回Hello SpringBoot! 步骤 1 创建Maven项目 大家&…...
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
目录 Δ前言 一、数组的合并 0.题目: 1.算法设计思想: 2.C语言描述: 3.算法的时间和空间复杂度 : 二、数组元素的倒置 0.题目 : 1.算法设计思想 : 2.C语言描述 : 3.算法的时间和空间复杂度 : 三、数组中特定值元素的删除 0.题目 : …...
AI秘境-墨小黑奇遇记 - 初体验(一)
“怎么可能!”墨小黑盯着屏幕上的代码,整个人都不好了。调试了三遍,翻了几遍书,结果还是不对。就像你以为自己早起赶车,结果发现闹钟根本没响一样崩溃。 这是他第一次真正接触人工智能实战任务——实现一个简单的感知…...
文件IO813
标准IO文件定位: fseek函数: 功能:将stream流文件中的文件指针从whence位置开始偏移offset个字节的长度。 int fseek(FILE *stream , long offset, int whence); FILE *stream 指的是所需要定位的文件(文化定位前提是文件要被打…...
STP(生成树)的概述和工作原理
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:Linux运维老纪的首页…...
从AGV到立库,物流自动化的更迭与未来
AGV叉车 随着柔性制造系统的广泛应用,小批量、多批次的生产需求不断增强,“订单导向”生产已经成为趋势。这也让越来越多的企业认识到,产线的智能设备导入只是第一步,要想达到生产效率的最优解,物流系统的再优化必须提…...
阴阳脚数码管
1.小故事 最近,我接到了一个既“清肺”又“烧脑”的新任务,设计一个低功耗蓝牙肺活量计。在这个项目中我们借鉴了一款蓝牙跳绳的硬件设计方案,特别是它的显示方案——数码管。 在电子工程领域,初学者往往从操作LED开始ÿ…...
【Vue3-Typescript】<script setup lang=“ts“> 使用 ref标签 怎么获取 refs子组件呢
注意:请确保子组件已经正确挂载,并且通过 defineExpose 暴露了您想要在父组件中访问的属性或方法 parent.vue <template><child ref"childRef"></child><button click"fun">点击父组件</button> &l…...
npm 超详细使用教程
文章目录 一、简介二、npm安装三、npm 的使用3.1 npm初始化项目3.2 安装包3.3 安装不同版本包3.4 避免系统权限3.5 更新包3.6 卸载包3.7 执行脚本3.8 pre- 和 post- 脚本3.9 npm link3.10 发布和卸载发布的包3.11 使用npm版本控制3.22 npm资源 四、总结 一、简介 npmÿ…...
TypeScript函数
函数 函数:复用代码块 函数可以不写返回值 调用函数-----函数名() function a(){console.log(无参函数); } a();需要再函数后,写上返回值类型 没有返回值 使用void function e():string{return 可乐 } console.log(我得到了e()); function d():void{console.l…...
中海油某海上平台轨道巡检机器人解决方案
配电房作为能源传输和分配的核心枢纽,其安全运行直接影响到企业的生产稳定性和安全性。对于中海油这样的大型能源企业,配电房的运行状况至关重要。然而,传统的人工巡检方式存在效率低、作业风险高、巡检误差大等问题。为提升巡检效率、降低安…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
【VLNs篇】07:NavRL—在动态环境中学习安全飞行
项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战,克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...
给网站添加live2d看板娘
给网站添加live2d看板娘 参考文献: stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下,文章也主…...
