字符串压缩

痛定思痛。 2022-09-21 13:19 133阅读 0赞

![Image 1][]![Center][]

时间优先法，但是这里有个问题，就是如果遇到第一个是数字的，且是单个数字的怎样进行压缩。

比如：3aaaa2bbbb

/* 压缩与解压缩
    时间优先
    如果有单个数字的怎样处理？ */
    
    #include<stdio.h> 
    #include<stdlib.h>
    #include<string.h>
    #include<memory.h>
    #include<malloc.h> 
    
    /* 压缩 */
    char * timefastzip(char *str)
    {
    	int length = strlen(str);
    	char *newstr = calloc(length + 1, 1);	//分配内存 calloc():在已分配的内存空间中的值默认为0
    	//分配在栈上，会动释放内存 
    	char *p = str;
    	char *newp = newstr;	//备份 
    	while (*p != '\0')
    	{
    		char *pis = p; 		//标识当前指针
    		//	char ch = *pis;		//当前的字符
    		int strlength = 0;
    		while ((*pis) == (*(pis + 1))) //如果 
    		{
    			pis++;		//指针移动 
    			strlength++; //计数 
    		}
    		if (strlength == 0) //没有相同的字符 
    		{
    			*newp = *p;
    			newp++;
    			p++;
    		}
    		else
    		{
    			*newp = strlength + 1 + '0';	//转化为字符
    			*(newp + 1) = *p;		//保存字符
    			newp += 2;		//跳过2个地址，因为一个保存了字符出现的次数，一个是字符
    			p += strlength + 1;	//指针向前移动，跳过相同的字符到下不同的字符 			 
    		}
    	}
    	length = strlen(newstr);	//新字符串的长度
    	newstr = realloc(newstr, length + 1);	//压缩内存 
    	return newstr;
    }
    
    char * jy(char *str)
    {
    	//解压缩要开辟足够在空间，重新分配内存空间
    	char *pstr = calloc(1024, 1); //分配在栈上，会动释放内存 
    	char *p = pstr;
    	while (*str != '\0')
    	{
    		if (*str >'0' && *str <= '9')
    		{
    			int length = *str - '0';
    			char temp = *(str + 1);
    			for (int i = 0; i<length; i++)
    			{
    				*pstr = temp;
    				pstr++;
    			}
    			str += 2;
    		}
    		else
    		{
    			*pstr = *str;
    			pstr++;
    			str++;
    		}
    
    	}
    	int length = strlen(p);	//新字符串的长度
    	p = realloc(p, length + 1);	//压缩内存 
    	return p;
    
    }
    
    void main()
    {
    	//char str[1024] = "223331111aaaaabbbliuguangahooooooooo";
    	char str[1024] = "43a223331111aaaaabbbliuguangahooooooooo";
    	/* 5a3bliuguangah9o*/
    	printf("%s\n", str);
    	char *p = timefastzip(str);
    	printf("%s\n", p);
    	printf("%s\n", jy(p));
    	system("pause");
    }

空间优先：即缩解压都是在原来字符串上进行不在另申请新的内存空间。

压缩时：直接在原字符串中进行压缩。

解压时：直接在压缩的字符串中进行扩展空间。

#include<stdio.h>
    #include<stdlib.h>
    
    void spaceFastZip(char *str)
    {
    	char *p1 = str;
    	char *p2 = str;
    	while ((*p1 = *p2) != '\0')
    	{
    		int length = 0;
    		
    		while (*p1 == *(p2+1))
    		{
    			length++;
    			p2++;
    		}
    		//有相同的字符
    		if (length)
    		{
    			*p1 = length + 1+'0';
    			*(p1+1) = *p2;
    			p2++;
    			p1 += 2;
    		}
    		else
    		{
    			p1++;
    			p2++;
    		}
    		//printf("...%s...\n", str);
    	}
    	
    }
    
    void spaceFastUnzip(char *str)
    {
    	char *p1 = str;
    	char *p2 = str;
    	while ((*p1 = *p2) != '\0')
    	{
    		int length = 0;
    		/* 如果是压缩的字符，则需要移动字符 */
    		if (*p1 > 0 && *p1 <= '9')
    		{
    			 length = *p1 - '0';//转化为数字		
    		}
    		if (length)
    		{
    			//把字符串后移，为要解压的字符串留下足够的内存空间。
    			for (char *p = p2 + strlen(p2); p > p2; p--)	//整体后移
    			{
    				*(p + length - 2) = *p;
    			}
    			//插入压缩的字符
    			for (int i = 0; i < length; i++)
    			{
    				*p1 = *(p2+1);
    				p1++;
    			}		
    			p2 += length;			
    		}
    		else
    		{
    			p1++;
    			p2++;
    		}
    	}
    }
    
    void main()
    {
    	char str[] = "aaabbbbbbcchinacccccc";
    	printf("压缩前字符串：%s\n", str);
    	printf("开始压缩数据......\n");
    	spaceFastZip(str);
    	printf("压缩后字符串：%s\n", str);
    	printf("开始解压......\n");
    	spaceFastUnzip(str);
    	printf("解缩后字符串：%s\n", str);
    
    	system("pause");
    }

[Image 1]: 
[Center]: /images/20220721/f9e1b2b2981e4c3c87ad1c2fe43857a6.png