Re: [問題] C做字串互換

[Hazukashiine (私は幸せです)]

※ 引述《sagwow (不是我)》之銘言：
: 問題(Question)：
: 字串互換
: 餵入的資料(Input): apple dog
: 預期的正確結果(Expected Output)：dog apple
: 補充說明(Supplement)：
: 我宣告char a[100][1000]，想交換其中a[0]和a[1]兩個字串，
: 想請問有沒有不用一個字元一個字元交換的方法。

GitHub Gist: https://gist.github.com/anonymous/ea41f753a335f34a3ec458f730c8f499

不一定要用二維陣列去處理，有 in-place 的 recursive 算法提供參考

大致上的做法就是 先對原字串反轉一次，再對子字串反轉一次就可以了


#include <stdio.h>
#include <string.h>

char *swapstr_rec(char *str, int begin, int end, int first)
{
    while (begin < end - 1)
    {
        char tmp = str[begin];
        str[begin++] = str[--end];
        str[end] = tmp;
    }
    end += begin;

    if (!first)
        return NULL;

    for (int idx = 1, prv = 0; idx <= end; idx++)
    {
        if (((str[idx]     == ' ' || str[idx]     == '\0') ^
             (str[idx - 1] == ' ' || str[idx - 1] == '\0')))
            swapstr_rec(str, prv, idx, 0), prv = idx;
    }

    return str;
}

char *swapstr(char *str)
{
    return swapstr_rec(str, 0, strlen(str), 1);
}

int main(void)
{
    char str[] = "apple dog";

    printf("%s\n", swapstr(str));
}

--

 作者  llyre (r^^||)                                           看板  Soft_Job 
 標題  Fw: [台北] 台北360徵Linux/Android安全研究員                            

推 hsnuonly: 推 這間的軟體大家用過都不會移除
推 discoby : 推 因為都不太知道怎麼移除
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.243.51.36
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1473178449.A.BE7.html
推 sagwow: 感謝，對我來說有點難  研究一下^^a
→ HolyBugTw: 我比較推這個處理方法，原理不難啊，就如作者所述
→ HolyBugTw: "123 abc" -swap-> "cba 321" -swap-> "abc 123"
推 yvb: 搭配一樓原原PO的排序程式, 好一個嚇人的字串Bubble Sort...
→ Eleina: leetcode 的 rotate 問題
推 yvb: 總覺得上面那個 recursive 假假的...
→ yvb: 把 first=0 獨立拉成一個 sub-function, 就不 revursive 了啊
→ Hazukashiine: 沒有吧～ 這確實算是 tail recursion 不是嗎？
→ Hazukashiine: 然後重用了上半部分 swap 的 code
→ Hazukashiine: https://zh.wikipedia.org/wiki/尾調用
→ Hazukashiine: 確實這也很容易轉寫成迭代的形式 都可以啦 不重要
→ Hazukashiine: 我比較好奇這 code 有什麼實際的應用
→ Hazukashiine: 原原PO好像要的不是這個 我後來才發現 wwwwwww
→ Hazukashiine: 他好像需要的是 swap 任意的子字串 而不是整個的說
※ 編輯: Hazukashiine (1.160.123.188), 09/08/2016 03:14:44
→ Hazukashiine: 我終於知道為什麼會這個遞迴看起來假假的了
→ Hazukashiine: 其實就把它想像成邊界條件是層數為一的遞迴就可以了
→ Hazukashiine: 這樣是不是就有一般遞迴的 feel 惹 (づ′・ω・)づ
推 yvb: 不是 tail recursion. f(n) 最後叫用 f(k) 來結束 f(n) 才是.
→ yvb: 而你的 swapstr_rec() 最後是 return str;
推 TeaEEE: 這樣的做法做了二次的swap好像沒比較快