c语言怎么把字符串压缩
时间: 2023-03-05 22:57:29 浏览: 140
在C语言中,可以使用各种算法来对字符串进行压缩,例如哈夫曼编码、Lempel-Ziv算法等。这些算法可以将字符串中重复出现的内容进行压缩,从而减小字符串的大小。
其中,哈夫曼编码是一种无损压缩算法,它可以根据字符串中各个字符出现的频率来构建一颗哈夫曼树,将字符转换为对应的二进制编码,并将编码后的二进制串进行压缩。
而Lempel-Ziv算法则是一种通用的压缩算法,它将字符串看做是由多个重复的子串组成,通过记录已经出现过的子串来进行压缩。
无论使用哪种算法,压缩后的字符串都需要通过解压算法来还原为原来的字符串。在C语言中,可以使用各种库函数来实现字符串的压缩和解压,例如zlib、gzip等。
相关问题
c语言压缩字符串
在C语言中,压缩字符串可以使用各种压缩算法,例如哈夫曼编码、LZW算法等。这里介绍一种简单的压缩算法——重复字符计数压缩。
重复字符计数压缩算法的思想是将连续重复出现的字符压缩成一个字符和一个计数值。例如字符串"AAAABBBCCCD"可以压缩成"4A3B3C1D"。
下面是一个示例代码,实现了将字符串压缩和解压的功能:
```c
#include <stdio.h>
#include <string.h>
// 压缩字符串
void compress_string(char* str) {
int len = strlen(str);
char compressed[len];
int count = 1;
char curr = str[0];
int pos = 0;
for (int i = 1; i < len; i++) {
if (str[i] == curr) {
count++;
} else {
// 压缩当前字符
compressed[pos++] = count + '0';
compressed[pos++] = curr;
// 更新计数器和当前字符
count = 1;
curr = str[i];
}
}
// 压缩最后一个字符
compressed[pos++] = count + '0';
compressed[pos++] = curr;
compressed[pos] = '\0';
// 将压缩结果拷贝回原字符串
strcpy(str, compressed);
}
// 解压字符串
void decompress_string(char* str) {
int len = strlen(str);
char decompressed[len];
int pos = 0;
for (int i = 0; i < len; i += 2) {
int count = str[i] - '0';
char curr = str[i + 1];
// 解压当前字符
for (int j = 0; j < count; j++) {
decompressed[pos++] = curr;
}
}
decompressed[pos] = '\0';
// 将解压结果拷贝回原字符串
strcpy(str, decompressed);
}
int main() {
char str[] = "AAAABBBCCCD";
printf("原字符串:%s\n", str);
compress_string(str);
printf("压缩后:%s\n", str);
decompress_string(str);
printf("解压后:%s\n", str);
return 0;
}
```
输出结果如下:
```
原字符串:AAAABBBCCCD
压缩后:4A3B3C1D
解压后:AAAABBBCCCD
```
需要注意的是,这种压缩方式只适用于包含大量重复字符的字符串,对于随机分布的字符串效果不佳。同时,压缩后的字符串长度可能会变长,因此需要根据实际情况选择合适的压缩算法。
C语言字符串压缩算法
基于哈夫曼编码的字符串压缩算法是一种常见的字符串压缩算法,下面是C语言实现的步骤和代码示例:
1. 定义结构体Node,用于构建哈夫曼树:
```c
typedef struct Node {
char ch; // 字符
int freq; // 字符出现的频率
struct Node *left, *right; // 左右子节点
} Node;
```
2. 定义函数getFreq(),用于统计字符串中每个字符出现的频率:
```c
int *getFreq(char *str) {
int *freq = (int *) calloc(256, sizeof(int)); // 初始化为0
while (*str) {
freq[(int) *str++]++;
}
return freq;
}
```
3. 定义函数createNode(),用于创建一个新的节点:
```c
Node *createNode(char ch, int freq) {
Node *node = (Node *) malloc(sizeof(Node));
node->ch = ch;
node->freq = freq;
node->left = node->right = NULL;
return node;
}
```
4. 定义函数getMinNode(),用于从节点数组中找到频率最小的两个节点:
```c
void getMinNode(Node **nodes, int n, int *min1, int *min2) {
*min1 = *min2 = -1;
for (int i = 0; i < n; i++) {
if (nodes[i] == NULL) continue;
if (*min1 == -1 || nodes[i]->freq < nodes[*min1]->freq) {
*min2 = *min1;
*min1 = i;
} else if (*min2 == -1 || nodes[i]->freq < nodes[*min2]->freq) {
*min2 = i;
}
}
}
```
5. 定义函数buildTree(),用于构建哈夫曼树:
```c
Node *buildTree(char *str) {
int *freq = getFreq(str);
Node **nodes = (Node **) malloc(sizeof(Node *) * 256);
int n = 0;
for (int i = 0; i < 256; i++) {
if (freq[i] > 0) {
nodes[n++] = createNode((char) i, freq[i]);
}
}
while (n > 1) {
int min1, min2;
getMinNode(nodes, n, &min1, &min2);
Node *node = createNode('\0', nodes[min1]->freq + nodes[min2]->freq);
node->left = nodes[min1];
node->right = nodes[min2];
nodes[min1] = node;
nodes[min2] = NULL;
n--;
}
Node *root = nodes[0];
free(freq);
free(nodes);
return root;
}
```
6. 定义函数getCode(),用于获取每个字符的哈夫曼编码:
```c
void getCode(Node *node, char *code, int len) {
if (node == NULL) return;
if (node->left == NULL && node->right == NULL) {
printf("%c: %s\n", node->ch, code);
return;
}
code[len] = '0';
getCode(node->left, code, len + 1);
code[len] = '1';
getCode(node->right, code, len + 1);
}
```
7. 定义函数compress(),用于压缩字符串:
```c
char *compress(char *str, Node *root) {
char *result = (char *) malloc(sizeof(char) * strlen(str) * 8 + 1);
int len = 0;
while (*str) {
Node *node = root;
while (node->left != NULL && node->right != NULL) {
if (*str == '0') {
node = node->left;
} else {
node = node->right;
}
str++;
}
result[len++] = node->ch;
}
result[len] = '\0';
return result;
}
```
8. 编写main()函数进行测试:
```c
int main() {
char *str = "hello,world!";
Node *root = buildTree(str);
getCode(root, (char *) malloc(sizeof(char) * 100), 0);
char *result = compress(str, root);
printf("Original string: %s\n", str);
printf("Compressed string: %s\n", result);
return 0;
}
```