1. Си / Говнокод #23278

    +3

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    // https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/code/c/1.1%EF%BC%9A%E5%B7%A6%E6%97%8B%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.c

#include <stdio.h>
#include <string.h>
//字符串旋转问题,例如abcdef 左旋2位 变成 cdefab

//暴力移位法
void leftShift1(char * arr, int n)
{
    size_t tmpLen = strlen(arr);
    char tmpChar;
    int i, j;
    if (n >= 0)
    {
        for (i = 0; i < n; i++)
        {
            tmpChar = *arr;
            for (j = 0; j < tmpLen - 1; j++)
            {
                *(arr + j) = *(arr + j + 1);
            }
            *(arr + tmpLen - 1) = tmpChar;
        }
    }
    else
    {
        for (i = 0; i < -n; i++)
        {
            tmpChar = *(arr + tmpLen - 1);
            for (j = tmpLen - 1; j > 0; j--)
            {
                *(arr + j) = *(arr + j - 1);
            }
            *arr = tmpChar;
        }
    }
}

    Копаясь в гитхабе, нашел я тут The Art Of Programming By July, написанный каким-то китайцем.
    https://github.com/julycoding/The-Art-Of-Programming-By-July

    Запостил: j123123, 18 Августа 2017

    Комментарии (5) RSS

    • ava j123123 18.08.2017 16:30 # +1 

      void leftShift2(char * arr, int len, int n)
{
    int i;
    size_t tmpLen = len;
    int p0 = 0;
    int p1 = n;
    char tmpChar;
    /*  O(m - n - k)  k is the last section*/
    while (p1 + n - 1 < tmpLen)
    {
        tmpChar = *(arr + p0);
        *(arr + p0) = *(arr + p1);
        *(arr + p1) = tmpChar;
        p0++;
        p1++;
    }
    /*
     *  not good O(k * (n + k)) k = tmpLen - p1
     for(i = 0;i < tmpLen - p1;i++){ //移动后面剩下的
     tmpChar = *(arr + tmpLen - 1);
     for(j = tmpLen - 1;j > p0;j--){
     *(arr + j) = *(arr + j -1);
     }
     *(arr + p0) = tmpChar;
     }
     */
    /* good O(k * n) */
    while (p1 < tmpLen)
    {
        tmpChar = *(arr + p1);
        for (i = p1; i > p0; i--)
        {
            *(arr + i) = *(arr + i - 1);
        }
        *(arr + p0) = tmpChar;
        p0++;
        p1++;
    }
}
//指针移位法,尾部处理用递归
void leftShift3(char * arr, int len, int n)
{
    size_t tmpLen = len;
    int p0 = 0;
    int p1 = n;
    char tmpChar;
    /*  O(m - n - k)  k is the last section*/
    while (p1 + n - 1 < tmpLen)
    {
        tmpChar = *(arr + p0);
        *(arr + p0) = *(arr + p1);
        *(arr + p1) = tmpChar;
        p0++;
        p1++;
    }
    if (p1 < tmpLen)
    {
        leftShift2(arr + p0, len - p0, n);
    }
}
//指针移位法,递归
void leftShift4(char * arr, int len, int n)
{
    size_t tmpLen = len;
    int p0 = 0;
    int p1 = n;
    char tmpChar;
    /*  O(m - n - k)  k is the last section*/
    while (p1 < tmpLen)
    {
        tmpChar = *(arr + p0);
        *(arr + p0) = *(arr + p1);
        *(arr + p1) = tmpChar;
        p0++;
        p1++;
    }
    int i = n - tmpLen % n;
    if (i != 0 && p0 != tmpLen - 1) // p0 can not be the tmpLen - 1
    {
        leftShift4((arr + p0), n, i);
    }
}
      Ответить

    • ava bormand 18.08.2017 18:35 # +1

      Но это же не shift, а rotate.
      Ответить

      • ava j123123 18.08.2017 18:40 # +1

        Это бракованная китайская версия shift, которая работает как rotate.
        Ответить

      • ava Stallman 18.08.2017 18:41 # 0

        Трудности перевода.
        Ответить

        • ava bormand 18.08.2017 18:46 # +3

          К слову, гугл коммент над функцией (где abcdef -> cdefab) перевёл как rotation.
          Ответить

    Добавить комментарий