行程編碼壓縮算法

1. 算法說明

RLE（Run Length Encoding行程編碼）算法是一個簡單高效的無損資料壓縮算法，其基本思路是把資料看成一個線性序列，而這些資料序列組織方式分成兩種情況：一種是連續的重複資料塊，另一種是連續的不重複資料塊。對于連續的重複資料快采用的壓縮政策是用一個位元組（我們稱之為資料重數屬性）表示資料塊重複的次數，然後在這個資料重數屬性位元組後面存儲對應的資料位元組本身，例如某一個檔案中有如下的資料序列AAAAA，在未壓縮之前占用5個位元組，而如果使用了壓縮之後就變成了5A，隻占用兩個位元組，對于連續不重複的資料序列，表示方法和連續的重複資料塊序列的表示方法一樣，隻不過前面的資料重數屬性位元組的内容為1。一般的這裡的資料塊取一個位元組，這篇文章中資料塊都預設為一個位元組。具體來講，字元串的編碼規則如下：在字元串中，2～9個相同的字元組成的子字元串用2個字元來編碼表示。第1個字元是這一字元串的長度，為2～9。第2個字元是相同字元的值。如果一個字元串存在相同字元且多于9個的子串，就先對前9個字元進行編碼，然後對其餘相同字元組成的子串采用相同方法進行編碼。例如AAAAAABCCCC編碼為6A1B14C。在字元串中，如果存在某個子串，其中沒有一個字元連續重複出現，就表示為以字元1開始，後面跟着這一子串，再以字元結束。如果在字元串中存在隻有1個字元1出現的子串，則以兩個字元1作為輸出，例如12344編碼為11123124。

Input

輸入一個字元串。

Output

輸出RLE編碼後的字元串。

Sample Input

AAAAAABCCCC12344

Sample Output

6A1B14C11123124

2. 函數實作

#include <stdio.h>
#include <string.h>
int main()
{
    char str[] = {'\0'};
    char result[] = {'\0'};
    int number[] = {};
    scanf("%s", str);
    int i;
    char c = '\0';
    int flag =;
    int nums = ;
    int j=, k=;
    for (i=; i<strlen(str); i++)
    {
        if (str[i] == str[i+]) //前後兩者相同
        {
            if (nums==) //目前達到9
            {
                result[j++] = str[i];
                number[k++] = nums;
                nums = ;
            }
            nums ++;
        }
        else
        {
            result[j++] = str[i];
            number[k++] = nums;
            nums = ;
        }
    }

    for (i=; i<j; i++)
    {
        if (number[i]!=)
        {
            if (flag==)
            {
                printf("1");
                flag = ;
            }
            printf("%d%c", number[i], result[i]);
        }
        else
        {
            if (flag == )
            {
                printf("1");
                flag = ;
            }

            if (result[i]=='1')
            {
                printf("11");
            }
            else
            {
                printf("%c", result[i]);
            }

        }

    }

    return ;
}