C 语言 Strfry() 函数

2025年1月7日 | 阅读13分钟

strfry() 函数是 GNU C 库 (glibc) 中一个专门的实用工具，它提供了一种随机打乱字符串中字符的方法。它的主要目的是演示 C 语言中的字符串操作和随机化。尽管它不是标准 C 库的一部分，但 strfry() 是一个有趣的非标准库扩展示例，它可以提供超出基本 ANSI C 规范的附加功能。

在支持 GNU C 库的系统上，此函数定义在string.h头文件中。它的设计简单直接。该函数接受一个参数，即指向以 null 结尾的字符串的指针，并就地打乱其字符。原始字符序列被随机化，函数返回指向修改后的字符串的指针。这种行为对于需要简单混淆形式的应用程序或用于教育目的以说明 C 语言中字符串和随机化工作原理的应用程序特别有用。

strfry() 函数作为 C 语言中简单的字符串操作和随机化的工具。虽然由于其非标准性质和基本随机化质量，其实际应用有限，但它仍然是学习这些概念的有用工具。开发人员应考虑其局限性，并确保它符合其项目的特定需求，尤其是在可移植性和随机性要求方面。

语法

它具有以下语法：

在这里，字符串表示要打乱的输入字符串。该函数返回传入字符串的相同指针。需要注意的是，strfry() 函数直接更改原始字符串的内容，这意味着原始字符序列会丢失，并被随机顺序取代。

方法 1：Fisher-Yates 洗牌算法

Fisher-Yates 洗牌（也称为 Knuth 洗牌）是一种广泛使用且高效的算法，用于随机排列有限序列，在本例中是字符串的字符。该算法的特别之处在于其简单性和均匀随机性，这意味着序列的每种排列都同样可能。

Fisher-Yates 洗牌算法的核心思想是从最后一个元素到第一个元素迭代数组，将每个元素与前面（包括自身）随机选择的另一个元素进行交换。这种就地算法的时间复杂度为 O(n)，其中 n 是数组中的元素数量，并且它只需要 O(1) 的额外空间，这使其既高效又节省空间。

程序

 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <ctype.h>
// Function to perform the Fisher-Yates shuffle on a string
void fisherYatesShuffle(char *str) {
  // Calculate the length of the string
  size_t n = strlen(str);
  // Iterate from the last element down to the second element
  for (size_t i = n - 1; i > 0; i--) {
    // Generate a random index j such that 0 <= j <= i
    size_t j = rand() % (i + 1);
    // Swap characters at indices i and j
    char temp = str[i];
    str[i] = str[j];
    str[j] = temp;
  }
}
// Function to check if a string contains only printable characters
int isPrintableString(const char *str) {
  // Iterate through the string until the null terminator
  while (*str) {
    // Check if each character is printable
    if (!isprint((unsigned char)*str)) {
      return 0; // Return 0 if any character is not printable
    }
    str++;
  }
  return 1; // Return 1 if all characters are printable
}
// Function to shuffle a string multiple times
void shuffleMultipleTimes(char *str, int times) {
  // Shuffle the string 'times' a number of times
  for (int i = 0; i < times; i++) {
    fisherYatesShuffle(str);
    // Print the result after each shuffle
    printf("Shuffle %d: %s\n", i + 1, str);
  }
}
int main() {
  // Declare a buffer to hold the input string
  char str[256]; // Buffer size 256 is arbitrarily chosen and can be adjusted
  printf("Enter a string to shuffle: ");
  // Read input string, ensuring no buffer overflow
  if (fgets(str, sizeof(str), stdin) == NULL) {
    fprintf(stderr, "Error reading input.\n");
    return 1; // Return 1 to indicate an error
  }
  // Remove the newline character at the end of the input string
  str[strcspn(str, "\n")] = '\0';
  // Validate the string to ensure it contains only printable characters
  if (!isPrintableString(str)) {
    fprintf(stderr, "Error: String contains non-printable characters.\n");
    return 1; // Return 1 to indicate an error
  }
  // Display the original string before shuffling
  printf("Original: %s\n", str);
  // Seed the random number generator using the current time
  srand((unsigned int)time(NULL));
  // Define the number of times the string should be shuffled
  int shuffleCount = 5; // This value can be adjusted as needed
  // Shuffle the string multiple times and print the results
  shuffleMultipleTimes(str, shuffleCount);
  // Return 0 to indicate successful execution
  return 0;
}   

输出

 
Enter a string to shuffle: example text
Original: Example text
Shuffle 1: pt etmleaxxe
Shuffle 2: mlxepet atxe
Shuffle 3: mlxpatt eexe
Shuffle 4: em etaxltpex
Shuffle 5: amxlep xtete

说明

提供的 C 程序说明了 Fisher-Yates 洗牌算法，这是一种经典的、高效的生成数组或字符串随机排列的方法。该程序包含输入验证、多次洗牌以及大量使用标准 C 库等多种功能。

头文件和库
程序包含几个标准 C 库
stdio.h：此库提供输入和输出函数，例如用于向控制台打印的 printf 和用于读取用户输入的 fgets。
stdlib.h：对于 rand（随机数生成）和 srand（为随机数生成器设置种子）等函数至关重要。它还包括用于动态内存管理的malloc和 free，尽管在此特定程序中未使用它们。
time.h：它提供用于处理日期和时间的函数，特别是 time() 用于为随机数生成器设置种子，以确保每次程序运行时输出都不同。
string.h：它包含用于处理 C 字符串的函数，例如用于查找字符串长度的 strlen 和用于字符串扫描的 strcspn。
ctype.h：它包括用于字符处理的函数，例如 isprint，它检查字符是否可打印。
2. Fisher-Yates 洗牌函数
程序的 Hiser-Yates Shuffle 函数的核心功能在 fisherYatesShuffle 函数中实现。此函数使用Fisher-Yates 算法获取字符串（字符数组）并就地打乱其内容。该算法的工作原理如下：
字符串长度计算：函数使用 strlen 计算字符串长度。
迭代洗牌：它从字符串的最后一个字符迭代到第二个字符。对于每个字符，它生成一个介于 0 和 i（含）之间的随机索引 j，并将索引 i 处的字符与索引 j处的字符进行交换。
随机性：洗牌的随机性是通过 rand() 函数实现的，该函数生成伪随机整数。交换操作是就地执行的，这意味着原始字符串直接被修改。
3. 可打印字符串验证
isPrintableString函数可确保输入字符串仅包含可打印字符。这是一种安全措施，可防止显示非打印字符时出现潜在问题，这些字符可能是控制字符或其他二进制数据。该函数遍历字符串中的每个字符，使用 ctype.h 中的 isprint 来检查其可打印性。如果所有字符都可打印，则函数返回 1；否则返回 0，表示输入无效。
4. 多次洗牌函数
shuffleMultipleTimes 函数是一个实用函数，用于多次洗牌字符串。它在循环中调用 fisherYatesShuffle，并在每次洗牌后打印结果。这演示了洗牌的可变性以及可以从同一初始字符串生成的不同排列。
5. Main 函数
main 函数是程序的入口点，并协调整体流程
用户输入：程序提示用户输入字符串。fgets 函数通过限制读取的字符数来读取输入，并提供了安全措施以防止缓冲区溢出。
输入清理：读取输入后，程序会删除用户按下 Enter 键时可能包含的所有尾随换行符。
验证：程序使用 isPrintableString 检查输入字符串是否可打印。如果不可打印，则打印错误消息并终止。
随机数种子：为了确保洗牌结果在每次运行时都不同，使用当前时间通过 srand(time(NULL)) 为随机数生成器设置种子。
洗牌：程序多次洗牌输入字符串，并打印每个结果以显示不同的可能排列。
6. 输出和用户交互
输出包括原始字符串和几个打乱后的版本，展示了 Fisher-Yates 洗牌的有效性。此过程强调了来自同一输入字符串的不同排列如何产生，这是需要随机化的应用程序（例如游戏或随机化测试）的关键功能。
总的来说，该程序是应用 Fisher-Yates 算法的全面的 C 语言示例，展示了处理用户输入、确保数据有效性以及有效利用标准库的最佳实践。

复杂度分析

时间复杂度

Fisher-Yates 洗牌函数 (fisherYatesShuffle)

Fisher-Yates 洗牌算法对数组（或字符串）进行精确一次迭代，从最后一个元素到第一个元素，在每次迭代期间执行一个恒定时间的操作（交换两个元素）。

循环分析：循环运行 n-1 次，其中 n 是字符串的长度。在每次迭代中，都会生成一个随机索引，并执行交换操作。

操作

随机索引生成：rand() % (i + 1) 恒定时间，O(1)

交换操作：它交换两个元素，并且具有恒定时间，O(1)

总时间复杂度：由于这些操作是为字符串中的每个字符（第一个字符除外）执行的，因此时间复杂度为 O(n)，其中 n 是字符串的长度。这意味着所需时间随输入大小线性增长。

可打印字符串验证 (isPrintableString)

此函数遍历字符串中的每个字符以检查其是否可打印。

循环分析：循环运行 n 次，其中 n 是字符串的长度，检查每个字符的可打印性。

操作

检查可打印性 (isprint)：恒定时间，O(1)

总时间复杂度：该函数也具有线性时间复杂度 O(n)，因为它必须检查字符串中的每个字符。

多次洗牌 (shuffleMultipleTimes)

此函数多次调用 fisherYatesShuffle 函数（如 times 参数所示）。

循环分析：外循环运行 times 次迭代，对于每次迭代，fisherYatesShuffle 函数运行，其复杂度为O(n)。

总时间复杂度：如果 times 是一个常量 c，则复杂度仍然是 O(n)。但是，如果 times 取决于输入大小，则复杂度将为 O(cn)，这简化为 O(n)，因为 c 是一个常数乘数。

总体时间复杂度

该程序的总体时间复杂度由最复杂的操作决定，在本例中是 Fisher-Yates 洗牌。因此，总体时间复杂度保持为 O(n)。

空间复杂度

Fisher-Yates 洗牌函数 (fisherYatesShuffle)

该函数就地操作，这意味着它不需要与输入大小成比例的额外空间。

辅助空间：它使用一些变量（用于索引和交换的临时变量），这些变量独立于输入大小。

总空间复杂度：空间复杂度为 O(1)，表示与输入大小无关的恒定空间使用。

可打印字符串验证 (isPrintableString)

与洗牌函数类似，此函数也就地操作并使用恒定的额外空间。

多次洗牌 (shuffleMultipleTimes)

此函数也不需要超出 fisherYatesShuffle 函数所用空间的额外空间。

总体空间复杂度

整个程序的操作使用恒定空间 O(1)，因为它不分配与输入大小成比例的额外内存。

方法 2：随机排列生成

生成索引的随机排列是一种字符串打乱方法，它涉及创建字符索引的排列，然后根据该排列重新排列字符串。此方法提供了灵活性，并且在各种场景中都很有用，例如当您需要将相同的排列应用于多个数组时，或者当您需要保留原始顺序以便以后参考时。

程序

 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
// Function to perform the Fisher-Yates shuffle
void fisher_yates_shuffle(int *array, int n) {
  for (int i = n - 1; i > 0; i--) {
    int j = rand() % (i + 1);
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
}
// Function to permute a string based on a random permutation of indices
void permute_string(char *str) {
  int n = strlen(str); // Length of the string  
  // Create an array to hold the indices
  int *indices = malloc(n * sizeof(int));
  if (indices == NULL) {
    perror("Failed to allocate memory for indices");
    exit(EXIT_FAILURE);
  }  
  // Initialize the indices array
  for (int i = 0; i < n; i++) {
    indices[i] = i;
  } 
  // Shuffle the indices array
  fisher_yates_shuffle(indices, n);
  // Create a new string to hold the permuted result
  char *result = malloc((n + 1) * sizeof(char));
  if (result == NULL) {
    perror("Failed to allocate memory for result");
    free(indices);
    exit(EXIT_FAILURE);
  } 
  // Rearrange the original string based on the shuffled indices
  for (int i = 0; i < n; i++) {
    result[i] = str[indices[i]];
  }
  result[n] = '\0'; // Null-terminate the new string
  // Copy the permuted string back to the original string
  strcpy(str, result);
  // Clean up
  free(indices);
  free(result);
}
int main() {
  // Seed the random number generator
  srand(time(NULL)); 
  // Define the string to be permuted
  char str[] = "example string for permutation"; 
  // Print the original string
  printf("Original: %s\n", str);  
  // Perform the permutation
  permute_string(str); 
  // Print the permuted string
  printf("Permuted: %s\n", str); 
  return 0;
}   

输出

 
Original: example string for permutation
Permuted: oesnnptarmtmirulrfixeo gap et

说明

提供的 C 代码演示了一种使用 Fisher-Yates 洗牌算法生成字符串字符随机排列的方法。这种方法是一个健壮且富有教育意义的示例，说明了如何在 C 语言中处理字符串操作和随机化。

代码的主要目标是以随机顺序打乱字符串中的字符。这是通过首先生成代表字符串中字符位置的索引排列，然后根据此排列重新排列字符来实现的。

头文件包含
代码包含几个标准库：用于输入和输出操作的 stdio.h、用于动态内存分配和随机数生成的 stdlib.h、用于使用当前时间为随机数生成器设置种子的 time.h，以及用于字符串操作函数的 string.h。这些库提供了实现该功能所需的函数和常量。
Fisher-Yates 洗牌函数
此函数实现了 Fisher-Yates 洗牌算法，这是一种用于生成数组随机排列的著名方法。该算法通过从末尾到开头遍历数组，将每个元素与之前（或自身）随机选择的元素进行交换来操作。这确保了数组的所有可能排列都同样可能。
rand() 函数用于生成随机索引，元素交换可确保排列均匀随机。此函数对于创建将应用于字符串的随机字符顺序至关重要。
Permute String 函数
内存分配：此函数首先为两个数组分配内存：一个用于保存字符串的索引，另一个用于存储排列后的结果。包括适当的错误检查以处理潜在的内存分配失败，确保程序能够优雅地处理内存不足的情况。
初始化和洗牌索引：indices 数组用与字符串中字符位置对应的顺序值初始化。例如，对于长度为 5 的字符串，indices 数组最初将包含 [0, 1, 2, 3, 4]。然后将 Fisher-Yates 洗牌应用于此数组以创建这些索引的随机排列。
重新排列字符串：使用打乱后的索引，通过将原始字符串中的字符放置在排列后的索引指定的位置来构造一个新字符串。这有效地将字符以随机顺序重新排列。重新排列后，新字符串会以 null 结尾，以确保其格式正确。
内存清理：函数最后释放 indices 数组和结果字符串的分配内存。此步骤对于避免内存泄漏至关重要，内存泄漏可能导致内存使用效率低下和程序崩溃。
主函数
随机种子：srand() 函数用于使用从 time(NULL) 获取的当前时间为随机数生成器设置种子。这确保了每次程序运行时 rand() 生成的随机数序列都不同，从而导致字符串的排列不同。
字符串定义和排列：定义一个字符串用于排列。调用 permute_string() 函数来打乱字符串，并将原始字符串和排列后的字符串都打印到控制台。

复杂度分析

时间复杂度

Fisher-Yates 洗牌函数

Fisher-Yates 洗牌函数是生成随机排列的核心。以下是其时间复杂度分步解析：

初始化：除了设置循环之外，该函数不执行任何显著的初始化。

循环执行：Fisher-Yates 洗牌的核心操作是从 n-1 向下到 1 运行的 for 循环。在每次迭代中，算法执行一个恒定时间的操作：选择一个随机索引并交换两个元素。

循环执行n-1 次，其中 n 是 indices 数组中的元素数量。每次迭代都涉及恒定数量的操作：生成一个随机索引和交换两个元素。

因此，此算法部分的时间复杂度为O(n)。

Permute String 函数

此函数涉及几个不同的步骤：

内存分配：内存为 indices 数组分配，并且结果字符串涉及每次分配 O(n) 时间。虽然这很重要，但相对于要分配的元素数量，它通常是恒定时间。

初始化索引：使用顺序值初始化 indices 数组需要一次遍历数组，这需要O(n) 时间。

洗牌索引：如上所述，应用于 indices 数组的 Fisher-Yates 洗牌是 O(n)。

重新排列字符串：根据打乱的索引创建新字符串，需要一次遍历字符串来复制字符，这需要O(n) 时间。

复制回和清理：将排列后的结果复制回原始字符串并释放分配的内存的操作也需要 O(n) 时间用于复制和 O(1) 时间用于释放内存。

将所有这些操作加在一起，时间复杂度中的主导因素是 O(n)，因为所有主要操作（洗牌、重新排列和复制）都与字符串长度呈线性关系。

空间复杂度

内存分配

indices 数组：分配一个大小为 n 的数组来保存索引。这需要 O(n) 空间。

结果字符串：分配一个大小为 n 的新字符串来存储排列后的结果，这需要O(n) 空间。

附加空间

临时变量：该函数使用一些额外的变量（temp、i、j），但这些变量只消耗恒定的空间，即 O(1)。

总体空间复杂度

总空间复杂度由动态分配数组的大小决定。indices 数组和结果字符串都与输入字符串的长度成正比。

因此，此函数的空间复杂度为O(n)。

下一个主题Iconv-close-function-in-c

← 上一个下一个 →

C 语言 Strfry() 函数

语法

方法 1：Fisher-Yates 洗牌算法

程序

说明

复杂度分析

方法 2：随机排列生成

程序

说明

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C 语言教程

C 语言控制语句

C 语言函数

C 语言数组

C 语言指针

C 语言动态内存

C 语言字符串

C 语言数学

C 语言结构体和联合体

C 语言文件处理

C 语言预处理器

C 语言命令行

C 语言程序

C 语言面试

选择题

C 语言编程测试

C 语言基础测试

C 语言控制语句测试

C 语言函数测试

C 语言数组测试

C 语言指针测试

C 语言字符串测试

C 语言结构体测试

C 语言预处理器测试

数学

C 语言杂项

C 语言 Strfry() 函数

语法

方法 1：Fisher-Yates 洗牌算法

程序

说明

复杂度分析

方法 2：随机排列生成

程序

说明

相关帖子

C 语言数组衰退

C 语言 pthread_self()

C 语言和 Dart 的区别

使用 fork() 函数的 C 语言链式进程与扇形进程

C 语言死锁检测程序

C 语言最优页替换算法

C 语言 pthread_getcpuclockid() 函数

C 语言 fcvt()

C 语言脚本文件和二进制文件的区别

C 语言和 Fortran 的区别

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器