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

数据结构+基数排序算法

一、问题描述

实现英文单词按字典序排列的基数排序算法 编写一个程序,采用基数排序方法将一组英文单词按字典顺序排 列。假设单词均由小写字母或空格构成,最长的单词有 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 中的元素就按照每个位上的值进行了排序。

相关文章:

数据结构+基数排序算法

一、问题描述 实现英文单词按字典序排列的基数排序算法 编写一个程序&#xff0c;采用基数排序方法将一组英文单词按字典顺序排 列。假设单词均由小写字母或空格构成&#xff0c;最长的单词有 MaxLen 个 字母&#xff0c;用相关数据进行测试并输出各趟的排序结果。 用例&#…...

C++ list【常用接口、模拟实现等】

1. list的介绍及使用 1.1 list的介绍 1.list是可以在常数范围内在任意位置进行插入和删除的序列式容器&#xff0c;并且该容器可以前后双向迭代。 2.list的底层是双向链表结构&#xff0c;双向链表中每个元素存储在互不相关的独立节点中&#xff0c;在节点中通过指针指向其前…...

12.面试题——Spring Boot

1.Spring Boot是什么&#xff1f; Spring Boot 是 Spring 开源组织下的子项目&#xff0c;是 Spring 组件一站式解决方案&#xff0c;主要是简化了使用 Spring 的难度&#xff0c;简省了繁重的配置&#xff0c;提供了各种启动器&#xff0c;开发者能快速上手。 2.为什么要用 …...

【前端VUE】npm i 出现版本错误等报错 简单直接解决命令

前端vue npm i 安装时出现 报错原因 在新版本的npm中&#xff0c;默认情况下&#xff0c;npm install遇到冲突的peerDependencies时将失败。 解决办法 使用--force或--legacy-peer-deps可解决这种情况。 --force 会无视冲突&#xff0c;并强制获取远端npm库资源&#xff0…...

精彩回顾 | 风丘科技亮相2024名古屋汽车工程博览会

2024年7月17日-19日&#xff0c;风丘科技联合德国IPETRONIK亮相日本名古屋汽车工程博览会。该展会面向汽车行业不同应用场景&#xff0c;包括新的eAxle、FCEV、ADAS、测试测量系统和ECU测试等相关技术&#xff0c;是一个专为活跃在汽车行业前线的工程师和研究人员举办的汽车技术…...

设计模式21-组合模式

设计模式21-组合模式&#xff08;Composite Pattern&#xff09; 写在前面 动机定义与结构定义结构主要类及其关系 C代码推导优缺点应用场景总结补充叶子节点不重载这三个方法叶子节点重载这三个方法结论 写在前面 数据结构模式 常常有一些组件在内部具有特定的数据结构。如何…...

如何选择深度学习的损失函数和激活函数

一概述 在深度学习中&#xff0c;损失函数&#xff08;Loss Function&#xff09;和激活函数&#xff08;Activation Function&#xff09;是两个至关重要的组件&#xff0c;它们共同影响着模型的训练效果和泛化能力。本文将简要介绍这两个概念&#xff0c;阐述选择它们的重要性…...

DATAX自定义KafkaWriter

因为datax目前不支持写入数据到kafka中&#xff0c;因此本文主要介绍如何基于DataX自定义KafkaWriter&#xff0c;用来同步数据到kafka中。本文偏向实战&#xff0c;datax插件开发理论宝典请参考官方文档&#xff1a; https://github.com/alibaba/DataX/blob/master/dataxPlug…...

Mybatis分页多表多条件查询

个人总结三种方式&#xff1a; Xml、queryWrapper、PageHelper第三方组件这三种方式进行查询&#xff1b; 方式一&#xff1a; xml中联表查询&#xff0c;在mapper中传参IPage<T>和条件Map&#xff08;这里用map装参数&#xff09;。 代码示例&#xff1a; Mapper层 M…...

SpringBoot快速入门(手动创建)

目录 案例&#xff1a;需求 步骤 1 创建Maven项目 2 导入SpringBoot起步依赖 3 定义Controller 4 编写引导类 案例&#xff1a;需求 搭建简单的SpringBoot工程&#xff0c;创建hello的类定义h1的方法&#xff0c;返回Hello SpringBoot! 步骤 1 创建Maven项目 大家&…...

C 408—《数据结构》算法题基础篇—数组(通俗易懂)

目录 Δ前言 一、数组的合并 0.题目&#xff1a; 1.算法设计思想&#xff1a; 2.C语言描述&#xff1a; 3.算法的时间和空间复杂度 : 二、数组元素的倒置 0.题目 : 1.算法设计思想 : 2.C语言描述 : 3.算法的时间和空间复杂度 : 三、数组中特定值元素的删除 0.题目 : …...

AI秘境-墨小黑奇遇记 - 初体验(一)

“怎么可能&#xff01;”墨小黑盯着屏幕上的代码&#xff0c;整个人都不好了。调试了三遍&#xff0c;翻了几遍书&#xff0c;结果还是不对。就像你以为自己早起赶车&#xff0c;结果发现闹钟根本没响一样崩溃。 这是他第一次真正接触人工智能实战任务——实现一个简单的感知…...

文件IO813

标准IO文件定位&#xff1a; fseek函数&#xff1a; 功能&#xff1a;将stream流文件中的文件指针从whence位置开始偏移offset个字节的长度。 int fseek(FILE *stream , long offset, int whence); FILE *stream 指的是所需要定位的文件&#xff08;文化定位前提是文件要被打…...

STP(生成树)的概述和工作原理

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:Linux运维老纪的首页…...

从AGV到立库,物流自动化的更迭与未来

AGV叉车 随着柔性制造系统的广泛应用&#xff0c;小批量、多批次的生产需求不断增强&#xff0c;“订单导向”生产已经成为趋势。这也让越来越多的企业认识到&#xff0c;产线的智能设备导入只是第一步&#xff0c;要想达到生产效率的最优解&#xff0c;物流系统的再优化必须提…...

阴阳脚数码管

1.小故事 最近&#xff0c;我接到了一个既“清肺”又“烧脑”的新任务&#xff0c;设计一个低功耗蓝牙肺活量计。在这个项目中我们借鉴了一款蓝牙跳绳的硬件设计方案&#xff0c;特别是它的显示方案——数码管。 在电子工程领域&#xff0c;初学者往往从操作LED开始&#xff…...

【Vue3-Typescript】<script setup lang=“ts“> 使用 ref标签 怎么获取 refs子组件呢

注意&#xff1a;请确保子组件已经正确挂载&#xff0c;并且通过 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&#xff…...

TypeScript函数

函数 函数:复用代码块 函数可以不写返回值 调用函数-----函数名() function a(){console.log(无参函数); } a();需要再函数后&#xff0c;写上返回值类型 没有返回值 使用void function e():string{return 可乐 } console.log(我得到了e()); function d():void{console.l…...

中海油某海上平台轨道巡检机器人解决方案

配电房作为能源传输和分配的核心枢纽&#xff0c;其安全运行直接影响到企业的生产稳定性和安全性。对于中海油这样的大型能源企业&#xff0c;配电房的运行状况至关重要。然而&#xff0c;传统的人工巡检方式存在效率低、作业风险高、巡检误差大等问题。为提升巡检效率、降低安…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...