>假设我有 N 个 char 数组,我想将它们连接在一起。 每个字符数组都存储在一个单独的结构中。 为了访问 stuct1 中的 char 数组,我需要访问 struct2,要访问结构 2,我需要访问 struct3,等等(想象一下一个链表,头部在 structN,尾部在 struct1)。
我想连接每个结构中的每个字符数组,以便来自 struct1 的字符数组首先出现,来自结构 N 的字符数组出现在最后。
例如,假设与结构 1、结构 2 和结构 3 关联的字符数组的内容为"A"、"B"、"C"。 我想得到结果的字符数组"ABC"。 但是,如上所述,要访问结构X,我必须首先访问结构X+1。 因此,在左侧连接这些字符数组会更有效;我不必继续浏览所有结构。
有没有办法在 C 中有效地做到这一点(即 strcat、snprintf 等),或者我是否必须手动操作每个 char 数组才能获得我想要的东西(或者浏览列表,保存指向结构的指针,然后返回)?
编辑(清晰度) 假设我有一个链接的链表。 每个元素都有一个字符数组。 我想以相反的顺序连接字符数组。 有没有办法在不重复列表的情况下做到这一点? 我知道运行时所有 char 数组的最大大小,但在我访问列表的每个元素之前我不知道它们各自的大小(当我访问元素 X 时,我知道存储在 X 处的 char 数组的大小)
这是反向打印链表的代码,您应该能够通过传入 char 缓冲区参数来针对您的 concat 问题修改它。
void ReversePrint(Node *head)
{
if (head == NULL)
return;
else if (head->next == NULL) {
printf("%dn", head->data);
} else {
ReversePrint(head->next);
printf("%dn", head->data);
}
}
诀窍是在执行实际工作之前进行递归调用,以便从最后一个节点开始处理,然后在展开时处理其他所有内容。 然后,您可以避免左手连接问题,您只需像通常想要的那样在末尾连接即可。
我做了一个简单的工作台来检查哪种方法更有效:
- 在每次迭代中使用
realloc
- 遍历列表两次,第一次获取大小,第二次复制字符串
我在这个长凳中使用的列表元素是一个结构:
struct elem
{
char *str;
size_t size;
};
这是双向链表的一个元素(我在列表的实现中使用了这个)。
然后我以这样的方式生成了一些字符串:
for(int j = 0; j < i; j ++)
{
char * str = malloc(SINGLE_STRING_LEN + 1);
memset(str, gimme_next_char(), SINGLE_STRING_LEN);
str[SINGLE_STRING_LEN] = ' ';
struct elem e;
e.str = str;
e.size = SINGLE_STRING_LEN;
dl_list_insert_at_tail(&l, (void *) &e);
}
SINGLE_STRING_LEN
具有值10
,gimme_next_char
周期性地从A
返回字符到Z
。i
是来自外部循环的值,它允许控制向列表中插入多少项。我测试了 100、200、...、900 个元素的操作。
第一种方法如下所示:
char *concat_str = NULL;
size_t concat_str_len = 1; // Remember about ' ' character
for_each_in_dl_list(struct elem, e, l)
{
size_t new_len = concat_str_len + e->size;
concat_str = realloc(concat_str, new_len);
strcpy(&concat_str[concat_str_len - 1], e->str);
concat_str_len = new_len;
}
(我假设sizeof(char) == 1
)。
正如您在每次迭代中看到的那样,realloc
用于调整字符串的大小。然后,使用strcpy
将列表中的字符串追加到生成的字符串中。基本上,你到达那里O(N * (M + realloc complexity))
M
strcpy
函数复杂性。
第二种方法:
size_t concat_str_len = 1;
for_each_in_dl_list(struct elem, e, l)
concat_str_len += e->size;
char *concat_str = malloc(concat_str_len);
concat_str_len = 1;
for_each_in_dl_list(struct elem, e, l)
{
size_t new_len = concat_str_len + e->size;
strcpy(&concat_str[concat_str_len - 1], e->str);
concat_str_len = new_len;
}
在这里,我们首先获取整个最终字符串的大小,然后遍历列表以附加列表中的每个字符串。你到达那里O(N + N * M + malloc complexity)
.
必须释放动态分配的数据,但我不想在此处粘贴此代码,因为它在本主题中毫无用处。
我已经调用了第一个程序和第二个程序~20次来计算执行时间的平均值:
Elems on the list | 105 | 305 | 505 | 705 | 905
First approach [us] | 9 | 25 | 42 | 54 | 67
Second approach [us] | 6 | 14 | 25 | 31 | 39
第二种方法要快得多。我还可以看到第一种方法的标准差要大得多(列表中 6 个元素的标准差大约是 905 倍)。这可能是多次调用函数realloc
因为第一种方法更依赖于系统。
如果您不介意做一些指针丑陋的事情,我会考虑遵循代码。
struct Ptr {
char *alloc_;
char *start_;
};
struct Ptr concat(Node *head) {
Ptr ptr;
ptr.alloc_ = malloc(maxSizeOfCharArray);
ptr.start_ = ptr.alloc_ + maxSizeOfCharArray - 2;
*(ptr.start_ + 1) = 0;
while (head != NULL){
ptr.start_ -= strlen(head->str)
memcpy(ptr.start_, head->str, strlen(head->str));
head = head->next;
}
return ptr;
}
完成所有这些之后,您有责任释放alloc_内存。不知道它是否会比天真的解决方案更快。