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

    • 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);
          }
      }
      Ответить
    • Но это же не shift, а rotate.
      Ответить
      • Это бракованная китайская версия shift, которая работает как rotate.
        Ответить
      • Трудности перевода.
        Ответить
        • К слову, гугл коммент над функцией (где abcdef -> cdefab) перевёл как rotation.
          Ответить

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