P398字符串压缩

发表于 更新于 分类于 阅读次数：

一个释放的信号

大概在2023/2/22中午的时候，出现了关于C语言期末考试的一些相关信息，粗略列出了考试的范围，并规定了考试题目数量。随后，一道题目被特别提出，投入到xdoj上，并在各大卷群快速传播。

这道题就是P398字符串压缩。

如果你认真做过xdoj的话，你就会发现，这道题其实就是P73字符串压缩（其实应该叫字符串解压缩）的翻版。但是，P398字符串压缩在P73字符串压缩的基础上，增加了函数和指针的考察，而不仅仅局限于字符串。

在这个大家都在复习高数的时间，抛出这道题，不得不让人引起遐想，而其他各门科目的难度拔高，也让C语言考试的难度拔高，成为了可能。

题目

标题：字符串压缩

问题描述：有一种简单的字符串压缩算法，对于字符串中连续出现的同一个英文字符，用该字符加上连续出现的次数来表示（连续出现次数小于3时不压缩）。

例如，字符串 aaaaabbbabaaaaaaaaaaaaabbbb 可压缩为 a5b3aba13b4 。

请设计一个程序，采用该压缩方法对字符串压缩并输出。请编写一个函数 compress ，采用该压缩方法对字符串 src 进行压缩。函数定义如下:

1
char *compress(char *src);

返回值：指向压缩后的字符串数据

参数： src ：输入/输出参数，输入表示待压缩字符串，输出表示压缩后的字符串

主函数输入说明：输入第一行为源字符串src（长度小于100），该字符串只包含大小写字母。

主函数输出说明：输出一个数据，表示压缩后的字符串。

主函数输入样例：aaaaabbbabaaaaaaaaaaaaabbbb

主函数输出样例：a5b3aba13b4

注意：函数声明已包含在主程序中，不需要自己定义。只需要提交自定义的函数代码。

主程序代码：

1
2
3
4
5
6
7
8
9
10
11
12
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char *compress(char *src);
int main()
{
	char src[100];
	scanf("%s",src);
	char *ps = compress(src);
	puts(ps);
	return 0;
}

分析

这道题的考察点其实就两个，一是字符串处理，二是对函数和指针的理解。

题目的本质是一个模拟，遍历字符串，从第一个字符开始遍历，如果后面的字符和前面的相同，就计数加一，直到下一个字符和前面的字符不一样，或者到字符串的末尾为止。

这时候每个字符理论上都有一个统计的数字，比如a的2次，b的3次等，根据题目的规则决定他们的存储形式，也就是1次和2次直接存储，3次网上的用字符加上连续的数字表示。

与直接输出不同的是，我们需要将它存储在一个字符串里，并返回它的地址。

问题列表

注意事项

如何存储字符串，成为了一个问题。

如果你在自定义函数内设置字符串并返回字符串的地址，估计是会出错的。局部变量储存在栈区，在函数调用结束后，局部变量可能不存在于内存中。因此，C不支持函数返回数组。

  • 函数占用的空间由编译器自动分配释放, 存放函数的参数值,局部变量等
  • 不要返回局部变量的地址，栈区开辟的数据由编译器自动释放

算法的参考代码

在电专的课本上有这道题的原题，具体位置忘了，反正题目除了没有必须要求使用指针，其他的都没有问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
char *pe = src;
//指针指向初始的字符
while (*src) {
	//是否遍历到字符串末尾，没有就继续遍历
	while (*src == *pe) {
		pe++;
		//如果遍历的字符相同，指针pe右移，直到不相同为止
	}
	int len = pe - src;
	//两个指针的长度就是重复次数
	if (len < 3) {
		for (int i = 0; i < len; i++) {
			printf("%c", src[i]);
			//非压缩情况下的输出
		}
	} else {
		printf("%c%d", *src, len);
		//压缩情况下的输出
	}
	src = pe;
	//更新位置
}

题解

malloc方法

malloc 是课本上提到的一个方法。

1
void *malloc(size_t a)

其中a为以字节为单位的内存大小，该函数会返回一个指针 ，指向已分配大小的内存。

malloc的全称是memory allocation，中文叫动态内存分配，用于申请一块连续的指定大小的内存块区域以void*类型返回分配的内存区域地址，当无法知道内存具体位置的时候，想要绑定真正的内存空间，就需要用到动态的分配内存，且分配的大小就是程序要求的大小。

malloc函数其实就是在内存中找一片指定大小的空间，然后将这个空间的首地址给一个指针变量，这里的指针变量可以是一个单独的指针，也可以是一个数组的首地址，这要看malloc函数中参数size的具体内容。

在分配内存后，我们还需要释放内存，防止内存泄露（这破题没那么多讲究）。

1
free(a);

对于本题来说，我们需要创建一个空间，来保证能把字符串处理的内容返回给主函数。

1
a = (char*)malloc(100*sizeof(char));

这句语句给a分配了一个大小为100字节的内存，而(char*)代表a是一个指向字符串的指针。

下面是一段参考代码，同时也给出了关于数字转化为字符串的实例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//writer:22-计算机-轮椅人
char *compress(char *src)
{
	int i,j=0,n=1;
	int m,mask=1,mm;
	char* comp;
	comp = (char*)malloc((int)strlen(src)*sizeof(char));		
	//动态申请一个和传入字符串大小一样空间,既能保证返回值类型一致，也能保证函数返回后，空间被释放
    //(int)strlen(src)指src字符串长度，可以用100代替
	for(i=0; i<(int)strlen(src); i++){							
	//遍历字符串
		comp[j]=*(src+i);									
		//将传入字符串每一项都压入压缩字符串（如果没有不同字符出现，，j是不会变的）
		if(*(src+i)==*(src+i+1)){
			while(n++){
				if(*(src+i)==*(src+i+n)){						
				//比较相同时，直接在循环里比较下一位，在循环结束后再将i+n-1
					continue;
				}
				if(*(src+i)!=*(src+i+n))						
				//当比较出现不同时
				{
					if(n>2){
						m=n;
						j++;									
						//此时压缩字符串应前进一位，不然数字会覆盖掉原来的字符
						mask=1;									
						//输出数字的程序（已扩展到5位数）
						while(m/=10){							
						//判断相同字符长度的位数
							mask*=10;
						}
						m=n;									
						//此时m=0，将m重新赋值
						do{
							mm=m/mask;							
							//输出此时最高位的项
							comp[j++]=mm+48;					
							//将数字加入压缩字符串，并移至下一位
							m%=mask;							
							//将最高位抹去
						}while(mask/=10);						
						//位数-1（由于最终mask=0，为避免出现分母为0的情况，在程序片段开始时将mask赋值为1）
						i+=n-1;									
						//将传入字符串已比较的项跳过
						n=1;
						break;
					}
					else{										
					//如果相同字符串长度小于3，按传入字符串前后位不相同处理
						n=1;
						j++;
						break;
					}
				}
			}
		}else j++;								
		//比较出现不相同时，下一项一定与本项不同，需要在压缩字符串向前进一位
	}
	comp[j]=0;									
	//字符串末尾应补字符NULL，因为压缩字符串的长度小于等于传入字符串的长度
	return comp;
	free(comp);			
	//释放分配的内存空间（意义不大，走不到这一行）
}

static方法

static 一般用于修饰局部变量，全局变量和函数。在局部变量被修饰过后，变量将存储到堆区，防止了函数结束后空间被自动释放的问题。

1
static char *a;

在变量前加上static即可。

直接覆写

由于原题提供了原字符串的地址，同时压缩后的字符串小于原字符串，因此可以通过直接对原字符串覆写并返回原字符串地址的方式进行解答。

下面是一个参考代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
char *compress(char *src) {
	int i, count = 0, cnt = 0, lena = strlen(src);
	char t;
	for (i = 0; i < lena; i++) {
		count = 1;
		while (src[i] == src[i + 1]) {
			count++;
			i++;
		}
		if (count <= 2)
			for (int j = 1; j <= count; j++)
				src[cnt++] = src[i];
		else if (count < 10 && count > 2) {
			src[cnt++] = src[i];
			src[cnt++] = count + '0';
		} else if (count >= 10 && count < 100) {
			src[cnt++] = src[i];
			src[cnt++] = count / 10 % 10 + '0';
			src[cnt++] = count % 10 + '0';
		}
	}
	for (i = cnt; i < lena; i++) {
		src[i] = 0;
	}
	return src;
}

直接输出并空返回

如果你不想让puts函数生效的话，你可以直接空返回，并在你的处理函数里面直接输出。

这是一个取巧的办法，不建议使用。以书本代码做样例演示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
char *compress(char *src) {
	char *pe = src;
	while (*src) {
		while (*src == *pe) {
			pe++;
		}
		int len = pe - src;
		if (len < 3) {
			for (int i = 0; i < len; i++) {
				printf("%c", src[i]);
			}
		} else {
			printf("%c%d", *src, len);
		}
		src = pe;
	}
	return "\0";
}

其他的可运用小技巧

sprintf

sprintf函数调用的主要用途就是把一个字符串放在一个已知的字符数组里去。在这道题里，可以很方便的用来转化数字为字符串。

1
int sprintf(char *string, char *format [,argument,…]);

具体的运用在此处不再赘述，读者有兴趣可自行搜索。

结构体

使用结构体进行存储，并转化成char*。

在一个循环内看看是否前一个结构体的a一样，一样就b++，不一样就下一个结构体，然后输出就行了。

思路来源于摆就完了（企鹅教南王），因为笔者对此也不太了解，所以不详细展开。

结语

第一次写这种东西，如果有错误和遗漏的话请多多包涵！

祝大家C语言考试顺利！