UVa245 - Uncompress (String Process)

題目大意：

給你一個經過壓縮的文本，文本中的數字則是代表是前面第幾個單字並輸出，但如果前面那些單字有重複到則只算一次並且是由後往前看的第一次遇到為準，請解壓縮此文本。

註:單字中間只要遇到非英文字母就全部都視為不一樣的單字。

分析：

這題要用 Linked-List 由於每個單字的上一個單字與下一個單字都會隨著壓縮而變不同，剛好符合 Linked-List 的特色。再加上一些優秀的讀取字串技術，就可以輕鬆解決掉這題了XD。

如果不懂的話，下方程式碼有做解說。相信你會很快理解 Linked-List 的，我很努力想讓讀者都能懂啦。但是我個人不太喜歡在解題時使用指標，所以下面並不是指標實作。對不起我就爛，debug 指標的技術很爛

參考連結：

UVA245 WF5184 POJ1885 Uncompress【文本】

心得

這題應該看的出來他是用 Linked-List 拉XD，我一開始是想要用 vector 但是我卻卡關QQ，可惡腦袋不給力呀！之後就用 Linked-List 解決掉這題，不過太久沒有寫字串題目，讀取字串的能力特別差啊讀取字串的能力特別差啊，腦袋整個完全沒想法。後來看到參考連結中的那篇優秀程式碼文章，才讓我對於讀取字串又有了更新的領悟，好讚。非常感謝作者願意將他的程式碼技術公布出來！

也希望我自己也能成為獨當一面的演算法程式設計師，不要甚麼都不太會，未來只能領低薪，我要努力，直到看到夢想為止之前！也希望大家可以幫助我。

不過指標的 Linked-List 我還是覺得寫起來很麻煩阿，常常 Debug 都找不出錯誤，好討厭。我可能之後會變成愛用 C++，但不喜歡指標的怪人吧www。C++ 的優勢根本沒有發揮出來

#include<bits/stdc++.h>
#define LOCAL
#define MAXN 100000
using namespace std ;

char ch ;
string strTemp = "" ;
int wcnt = 0 , head = 0 , num =0   ;
//wcnt linklist 的總量
//head 上一個單字的 index

struct stu_words{
    int next ;
    string word ;
}word[MAXN] ;
// next 上一個單字的 index
// word 此單字

int main(){
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
    //freopen("out.txt" , "w" , stdout );
#endif // LOCAL

    while(1){
        ch = getchar() ;
        if(ch == '0')
            break ;
        else if(isalpha(ch)){
            while(isalpha(ch)){ //不斷讀取單字，直到遇到其他
                strTemp += ch ;
                ch = getchar() ;
            }
            cout << strTemp ;
            word[wcnt].word = strTemp ; //添加新單字
            word[wcnt].next = head ; //上一個單字 index
            head = wcnt++ ; //長度增加
            strTemp = "" ;
        }
        else if(isdigit(ch)){ 
            while(isdigit(ch)){ //不斷讀取數字，直到遇到其他
                num = num * 10 + (ch - '0') ;
                ch = getchar() ;
            }

            int cur = head , prev  ; 
            //cur = 數字的那個單字
            //prev = 數字的下一個單字
            for(int i = 1 ; i < num ; i++){ // 向上追蹤單字
                prev = cur ;
                cur = word[cur].next ;
            }
            num = 0 ;
            cout << word[cur].word ;

            if(head != cur ){ // 要將當前的單字搬到後面，所以單字的上一個 index 也需要更新
                word[prev].next = word[cur].next ; 
                // 因為要移動當前單字所以必須要將當前單字的下一個單字的 next，往前到現在這單字的 next
                word[cur].next = head ;
                // 當前的單字 next 改為現在讀取中的上一個單字
                head = cur ; // 現在這個單字變成結尾
            }

        }
        putchar(ch) ;
    }

}