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

38. 考古学家

news 来源：原创 2025/5/17 9:54:18

题目描述

有一个考古学家发现一个石碑，但是很可惜，发现时其已经断成多段，原地发现n个断口整齐的石碑碎片。为了破解石碑内容，考古学家希望有程序能帮忙计算复原后的石碑文字组合数，你能帮忙吗？

输入描述

第一行输入n，n表示石碑碎片的个数。

第二行依次输入石碑碎片上的文字内容s，共有n组。

输出描述

输出石碑文字的组合（按照升序排列），行末无多余空格。

用例

输入 3
a b c
输出 abc
acb
bac
bca
cab
cba
说明无

输入 3
a b a
输出 aab
aba
baa
说明无

一、问题分析

首先读题，仔细看描述中的内容，发现需求是

1.有一个考古学家发现一个石碑，但是很可惜，发现时其已经断成多段

2.原地发现n个断口整齐的石碑碎片

3.为了破解石碑内容，考古学家希望有程序能帮忙计算复原后的石碑文字组合数

4.输入描述：第一行输入n，n表示石碑碎片的个数。

第二行依次输入石碑碎片上的文字内容s，共有n组。

5.输出描述：输出石碑文字的组合（按照升序排列），行末无多余空格。

二、解题思路

1.首先我们读取碎片个数int n;

scanf("%d", &n);

2.然后我们读取文字内容,存储为一个二维字符数组（通过动态分配内存实现）

char **fragments = (char **)malloc(n * sizeof(char *));

for(int i = 0; i < n; i++) {

fragments[i] = (char *)malloc(100 * sizeof(char));

scanf("%s", fragments[i]);

}

3.然后通过递归的方式手动生成所有可能的碎片文字排列组合情况，将这些排列组合存储在另一个动态分配内存的二维字符数组中。

char **result = NULL;

int resultSize = 0;

permute(fragments, 0, n, &result, &resultSize);

4.之后对这些排列组合进行排序

qsort(result, resultSize, sizeof(char *), compare);

5.排序后去除重复的组合

removeDuplicates(&result, &resultSize);

6.之后逐行输出这些排列组合

for(int i = 0; i < resultSize; i++) {

printf("%s\n", result[i]);

free(result[i]);

}

7.释放动态分配的内存避免内存泄漏

free(fragments);

free(result);

return 0;

8.使用到的库有标准库，标准输入输出库，字符串处理库

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

9.定义一个交换函数，用于交换两个字符指针所指向的字符串，在生成排列组合的过程中，通过交换指针指向的字符串来改变顺序，从而得到不同的排列情况。它接受两个二级字符指针作为参数，通过中间临时指针temp实现两个指针所指向字符串的交换。

void swap(char **a, char **b) {

char *temp = *a;

*a = *b;

*b = temp;

}

10.生成排列组合函数，这是一个递归函数，用于生成给定字符串数组fragments的所有全排列情况，并将结果存储到动态分配内存的result数组中，同时通过resultSize指针记录结果数组的大小（元素个数）。

递归终止条件：当start参数等于size - 1时，表示已经固定了前面所有位置的元素，当前位置就是最后一个位置了，此时已经生成了一种完整的排列组合。首先为这个新的排列组合分配足够的内存空间（根据每个碎片字符串长度和碎片个数计算所需字节数，额外加1是为了存储字符串结束符\0），然后通过循环将各个碎片字符串拼接起来形成一个完整的排列组合字符串newPerm。接着使用realloc函数动态调整result数组的内存大小，为新的排列组合字符串分配空间，并将其存储到result数组中，同时更新resultSize值。

递归生成排列组合部分：在start小于size - 1时，通过循环将当前位置start的元素与它后面的元素依次交换（通过调用swap函数），然后对剩余的元素（即从start + 1位置开始）递归调用permute函数来生成所有可能的排列情况，在一次递归调用返回后，再将交换的元素交换回来，回复原来的顺序，继续下一次交换和递归调用，以此类推，最终生成所有的排列组合情况。

void permute(char **fragments, int start, int size, char ***result, int *resultSize) {

if(start == size - 1) {

char *newPerm = (char *)malloc((strlen(fragments[0]) * size + 1) * sizeof(char));

newPerm[0] = '\0';

for(int i = 0; i < size; i++) {

strcat(newPerm, fragments[i]);

}

(*result) = (char **)realloc(*result, (*resultSize + 1) * sizeof(char **));

(*result)[*resultSize] = newPerm;

(*resultSize)++;

return;

}

for(int i = start; i < size; i++) {

swar(&fragments[start], &fragments[i]);

permute(fragments, start + 1, size, result, resultSize);

swap(&fragments[start], &fragments[i]);

}

11.比较函数，为qsort排序函数提供自定义的比较规则。qsort函数要求传入一个比较函数指针，用于比较两个元素的大小关系。在这里，比较的元素是字符指针（指向字符串），所以先通过*(char **)a和*(char **)b解引用得到实际的字符指针，再使用strcmp函数比较这两个指针所指向的字符串的大小（按照字典序比较），返回比较结果，供qsort函数根据这个结果对数组元素进行排序。

int compare(const void *a, const void *b) {

return strcmp(*(char **)a, *(char **)b);

}

12.去重函数，用于去除result数组中的重复字符串。通过循环遍历result数组，比较相邻的两个字符串（使用strcmp函数），如果不相等，就将当前字符串保留（将其复制到索引为j的位置，同时j自增1）；如果相等，说明是重复的字符串，就释放其占用的内存空间（通过free函数）。最后将最后一个字符串也添加到去重后的数组中，并更新resultSize的值为去重后的数组元素个数，实现去重功能。

void removeDuplicates(char ***result, int *resultSize) {

int i, j;

for(int i = 0, j = 0; i < *resultSize - 1; i++) {

if(strcmp((*result)[i], (*result)[i + 1]) != 0) {

(*result)[j++] = (*result)[i];

}else {

free((*result)[i]);

}

(*result)[j++] = (*result)[*resultSize - 1];

*resultSize = j;

}

三、具体步骤

使用的语言是C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 交换两个字符串
void swap(char **a, char **b) {char *temp = *a;*a = *b;*b = temp;
}// 生成全排列的函数，采用递归的方式
void permute(char **fragments, int start, int size, char ***result, int *resultSize) {if (start == size - 1) {// 为新的排列组合分配内存空间char *newPerm = (char *)malloc((strlen(fragments[0]) * size + 1) * sizeof(char));newPerm[0] = '\0';for (int i = 0; i < size; i++) {strcat(newPerm, fragments[i]);}// 将新的排列组合添加到结果数组中(*result) = (char **)realloc(*result, (*resultSize + 1) * sizeof(char **));(*result)[*resultSize] = newPerm;(*resultSize)++;return;}for (int i = start; i < size; i++) {swap(&fragments[start], &fragments[i]);permute(fragments, start + 1, size, result, resultSize);swap(&fragments[start], &fragments[i]);}
}// 比较两个字符串指针指向的字符串是否相等
int compare(const void *a, const void *b) {return strcmp(*(char **)a, *(char **)b);
}// 去除结果数组中的重复字符串
void removeDuplicates(char ***result, int *resultSize) {int i, j;for (i = 0, j = 0; i < *resultSize - 1; i++) {if (strcmp((*result)[i], (*result)[i + 1])!= 0) {(*result)[j++] = (*result)[i];} else {free((*result)[i]);}}(*result)[j++] = (*result)[*resultSize - 1];*resultSize = j;
}int main() {int n;scanf("%d", &n);char **fragments = (char **)malloc(n * sizeof(char *));for (int i = 0; i < n; i++) {fragments[i] = (char *)malloc(100 * sizeof(char));  // 假设每个碎片字符串最长100个字符，可根据实际调整scanf("%s", fragments[i]);}char **result = NULL;int resultSize = 0;permute(fragments, 0, n, &result, &resultSize);// 排序qsort(result, resultSize, sizeof(char *), compare);// 去重removeDuplicates(&result, &resultSize);for (int i = 0; i < resultSize; i++) {printf("%s\n", result[i]);free(result[i]);}free(fragments);free(result);return 0;
}

题目描述

输入描述

输出描述

用例

一、问题分析

二、解题思路

三、具体步骤

相关文章：