1.题目要求
(语言: C)给定一个数字n，生成共有n个括号的所有正确的形式
例如n=3时生成的括号为
"((()))", "(()())", "(())()", "()(())", "()()()"
输入输出格式为
printf("Please input the number\n");
scanf("%d");
printf("values are %d\n");
for ( )
{printf("%s\n");
}
函数原型为
char** generateParenthesis(int n, int* returnSize)
注：不考虑非法输入的情况，输入的必须是正整数，且不超过10，数目太大程序运行太慢。
程序运行示例
Please input the number
3
values are 5
((()))
(()())
(())()
()(())
()()()
2.代码实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>void generate(char** result, int* returnSize, char* current, int left, int right, int index, int n) {if (left == 0 && right == 0) {result[*returnSize] = (char*)malloc(sizeof(char) * (n * 2 + 1));strcpy(result[*returnSize], current);(*returnSize)++;return;}if (left > 0) {current[index] = '(';generate(result, returnSize, current, left - 1, right, index + 1, n);}if (right > left) {current[index] = ')';generate(result, returnSize, current, left, right - 1, index + 1, n);}
}char** generateParenthesis(int n, int* returnSize) {char** result = (char**)malloc(sizeof(char*) * 1000);char* current = (char*)malloc(sizeof(char) * (n * 2 + 1));current[n * 2] = '\0';*returnSize = 0;generate(result, returnSize, current, n, n, 0, n);free(current); // 释放 current 分配的内存return result;
}int main() {int n;printf("Please input the number\n");scanf("%d", &n);int returnSize;char** result = generateParenthesis(n, &returnSize);printf("values are %d\n", returnSize);for (int i = 0; i < returnSize; i++) {printf("%s\n", result[i]);free(result[i]); // 释放 result 中每个元素所指向的内存}free(result); // 释放 result 数组本身return 0;
}
3.代码详解
1.知识点：此题需灵活运用递归和指针，还涉及到了动态内存管理。
2.generate函数
- 函数参数：
char** result：一个指向字符指针的指针，用于存储生成的括号组合。int* returnSize：一个指向整数的指针，用于记录生成的括号组合的数量。char* current：一个字符数组，用于存储当前正在生成的括号组合。int left：表示还可以使用的左括号的数量。int right：表示还可以使用的右括号的数量。int index：表示当前正在生成括号的位置。int n：表示总的括号对数。
- 递归逻辑：
- 当
left 和 right 都为 0 时，说明已经生成了一个合法的括号组合。使用 malloc 为该组合分配内存，使用 strcpy 将 current 复制到 result[*returnSize] 中，并增加 *returnSize 的值。 - 如果
left 大于 0，将 ( 放入 current[index] 位置，并递归调用 generate 函数，同时减少 left 的数量，增加 index 的位置。 - 如果
right 大于 left，将 ) 放入 current[index] 位置，并递归调用 generate 函数，同时减少 right 的数量，增加 index 的位置。
3.递归思想
- 本题使用递归算法来生成括号组合。
- 从空字符串开始，在每个位置上可以选择添加
( 或 )。 - 递归的终止条件是
left 和 right 都为 0，即已经使用完所有的括号。 - 为保证括号组合合法，添加左括号的条件是
left > 0，添加右括号的条件是 right > left，这是因为在任何时刻，左括号的数量不能小于右括号的数量。
