数据结构+基数排序算法
一、问题描述
实现英文单词按字典序排列的基数排序算法 编写一个程序,采用基数排序方法将一组英文单词按字典顺序排 列。假设单词均由小写字母或空格构成,最长的单词有 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…...
中海油某海上平台轨道巡检机器人解决方案
配电房作为能源传输和分配的核心枢纽,其安全运行直接影响到企业的生产稳定性和安全性。对于中海油这样的大型能源企业,配电房的运行状况至关重要。然而,传统的人工巡检方式存在效率低、作业风险高、巡检误差大等问题。为提升巡检效率、降低安…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
Java - Mysql数据类型对应
Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...
使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...
CppCon 2015 学习:Time Programming Fundamentals
Civil Time 公历时间 特点: 共 6 个字段: Year(年)Month(月)Day(日)Hour(小时)Minute(分钟)Second(秒) 表示…...
[拓扑优化] 1.概述
常见的拓扑优化方法有:均匀化法、变密度法、渐进结构优化法、水平集法、移动可变形组件法等。 常见的数值计算方法有:有限元法、有限差分法、边界元法、离散元法、无网格法、扩展有限元法、等几何分析等。 将上述数值计算方法与拓扑优化方法结合&#…...
6.计算机网络核心知识点精要手册
计算机网络核心知识点精要手册 1.协议基础篇 网络协议三要素 语法:数据与控制信息的结构或格式,如同语言中的语法规则语义:控制信息的具体含义和响应方式,规定通信双方"说什么"同步:事件执行的顺序与时序…...
