[C++知识库]C 语言: 递归方式统计任意整数 16 进制中数位出现的次数

遇到一道面试题: 以 C 编写一个完整的程序, 用递归方式统计任意整数 16 进制中数位出现的次数, 按从少到多输出统计结果. 如 439078109, 其 16 进制为 1A2B CCDD, 则输出结果为: 1:1,2:1,A:1,B:1,C:2,D:2.

首先, 笔者觉得应该设计一个方便调用的接口.

题目没有说明整数是否可以为负, 于是将传入参数定义为无符号整型数, 这样的话, 就算传入负数, 也能对其补码形式, 复用同样的逻辑.

为了方便结果的复用, 过程的返回值应该是一个映射, 键为 16 个十六进制数, 值则为其出现的次数. 而因为键恰好是连续稳定递增的, 所以可以简单用一个长度为 16 的整型数数组存储.

问题在于, C 语言中不能直接返回一个数组, 这里笔者熟悉的有两种方式: 一种是向过程传入数组的地址; 另一种则是定义一个结构类型, 在其成员中定义一个数组, 并将结构类型作为函数的返回值类型.

前者的话, 需要用户负责空间的管理, 使用起来不是特别流畅 (虽然可能是 C 语言常见操作); 采取后一种方式, 则定义类似如下:

typedef struct {
  int count[16];
} Count16Result;

Count16Result count16Chars(unsigned int num);

然而随即又遇到另一个问题, 题目要求用递归实现.

一般来说, 每层递归应是负责统计一个十六进制数位, 因此用来记录统计数据的数组要能被整个递归栈访问. 假使这个数组不是由用户分配并传入, 那么过程便要负责这件事.

于是可以分别设计入口函数和负责递归的函数. 在入口函数中负责变量的分配, 并将其传入负责递归的函数. 但在不引入多文件的情况下, 全局的递归函数可能会被用户误用.

而如果使用单一函数, 在不使用静态变量的情况下, 为了将这个数组传入给之后的递归调用, 函数的接口就要发生变化, 进而为调用增加烦恼 (除此之外, 还需要判断递归的层数, 以决定是否需要分配或释放空间).

于是考虑使用静态变量, 尽管仍然需要判断递归的层数, 但是函数的接口不用增添额外的参数了.

并且由于使用递归, 将返回值设置为一个结构体类型或许也不是很高效的做法. 笔者索性直接在函数中完成结果的输出; 这么一来, 也不需要定义结构了, 直接使用静态数组即可.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

void count16Chars(unsigned int num);

int main() {
  int num;
  scanf("%d", &num);
  count16Chars(num);
}

函数定义如下:

// 用于输出结果的函数, 事先声明
void print16Count(const int count[]);

void count16Chars(unsigned int num) {
  static int depth = 0;  // 记录递归层数
  static int count[16];  // 记数

  if (depth == 0) {  // 初次进入递归
    // 清零计数数组
    for (int i = 0; i < 16; ++i) count[i] = 0;
    // 由于使用 num == 0 作为递归终止条件,
    // 因此如果传入的数据是 0, 则需要特别处理:
    if (num == 0) {
      count[0] = 1;
      print16Count(count);  // 输出计数结果
      return;  // 完成
    }
  }

  if (num == 0) { return; }  // 递归出口
  else {
    ++depth;  // 递归层数 + 1
    count[num % 16] += 1;
    count16Chars(num / 16);
    --depth;  // 递归完成, 递归层数 -1
    if (depth == 0) {  // 如果递归层数回到 0, 说明递归处理完成
      print16Count(count);  // 输出计数结果
      return;  // 完成
    }
  }
}

接下来还要定义输出结果的函数. 分析题目可知, 计数为零的项不需输出, 且输出项要按照计数大小进行排序. 笔者决定分两步实现: 先找出 / 去除计数为零的项, 然后再排序.

void print16Count(const int count[]) {
  struct {  // 定义存储计数项的结构: 对应的字符 + 计数
    char c;
    int cnt;
  } t, items[16];  // 最多 16 个计数项
                   // 其实对于 unsigned int 来说最多只会有 8 个
  int len = 0;     // 记录长度的变量

  static const char c[] = "0123456789ABCDEF"; // 用于查找十六进制数对应的字符

  // 选取非零项
  for (int i = 0; i < 16; ++i) {
    if (count[i] != 0) {
      items[len].c = c[i];
      items[len].cnt = count[i];
      ++len;
    }
  }
  
  // 冒泡排序
  int swapped = 0;
  int n = len;
  do {
    swapped = 0;
    for (int p = 1; p < n; ++p) {
      if (items[p - 1].cnt > items[p].cnt) {
        t = items[p];
        items[p] = items[p - 1];
        items[p - 1] = t;
        swapped = 1;
      }
    }
    --n;
  } while (swapped);

  // 打印排序后的计数项
  for (int j = 0; j < len; ++j) {
    printf("%c:%d", items[j].c, items[j].cnt);
    if (j != len - 1) printf(",");  // 只在项之间输出 ',' 作为间隔
  }
}

综上, 题目完成.