`

将字符串循环左移n个位置

阅读更多
/**
 * @file 020_move_string.c
 * @author dinghuaneng
 * @date 2011.06.22
 * @brief 将字符串进行向左旋转,即循环左移的算法实现。
 *        最后那种方法在时间和空间上都很高效,且代码简短,很难出错。
 *        最节约空间和时间的方法来源:《编程珠玑》
 * @defgroup move_string
 * @{
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*********************** 最节约时间的方法 ************************/
/**
 * @brief 将字符串向左旋转n个位置
 * @param      str  待旋转的字符串
 * @param[in]  mov  需要旋转的数量
 * @return 无
 */
void move_string_left(char *str, int mov)
{
    if (NULL == str || mov <= 0)
        return;
    char tmp[mov];
    int i;
    int len = strlen(str);
    if (len == 0)
        return;
    mov %= len;
    if (mov == 0)
        return;
    for (i = 0; i < sizeof tmp; i++)
        tmp[i] = str[i];
    tmp[i] = '\0';
    for (i = 0; i < len-mov; i++)
        str[i] = str[i+mov];
    for (; i < len; i++)
        str[i] = tmp[i-(len-mov)];
}

/**
 * @brief 将字符串向右旋转n个位置
 * @param      str  待旋转的字符串
 * @param[in]  mov  需要旋转的数量
 * @return 无
 */
void move_string_right(char *str, int mov)
{
    if (NULL == str || mov <= 0)
        return;
    char tmp[mov];
    int i;
    int len = strlen(str);
    if (len == 0)
        return;
    mov %= len;
    if (mov == 0)
        return;
    for (i = len - mov; i < len; i++) {
        tmp[i-(len-mov)] = str[i];
    }
    tmp[i-(len-mov)] = '\0';
    for (i = len - 1; i >= mov; i--) {
        str[i] = str[i-mov];
    }
    for (; i >= 0; i--)
        str[i] = tmp[i];
}
/*********************** 最节约时间的方法 ************************/

/*********************** 最节约空间的方法 ************************/
/**
 * @brief 将字符串向左旋转1个位置
 * @param      str  待旋转的字符串
 * @param[in]  mov  需要旋转的数量
 * @return 无
 */
void move_string_one_left(char *str)
{
    if (NULL == str)
        return;
    int  len = strlen(str);
    int  i;
    if (len == 0)
        return;
    char tmp = str[0];
    for (i=0; i<len-1; i++) {
        str[i] = str[i+1];
    }
    str[i] = tmp;
}

/**
 * @brief 将字符串向右旋转1个位置
 * @param      str  待旋转的字符串
 * @param[in]  mov  需要旋转的数量
 * @return 无
 */
void move_string_one_right(char *str)
{
    if (NULL == str)
        return;
    int  len = strlen(str);
    if (len == 0)
        return;
    char tmp = str[len-1];
    int  i;
    for (i=len-1; i>0; i--) {
        str[i] = str[i-1];
    }
    str[i] = tmp;
}
/*********************** 最节约空间的方法 ************************/

/*********************** 最节约空间和时间的方法之一 ************************/
/**
 * @brief 返回数值i和j的最大公约数
 * @return 正确返回最大公约数,参数有问题返回-1
 */
int gcd(int i, int j)
{
    if (i<=0 || j<=0)
        return -1;
    while (i != j) {
        if (i > j)
            i -= j;
        else
            j -= i;
    }
    return i;
}

/**
 * @brief 将字符串向左旋转n个位置
 * @param      str  待旋转的字符串
 * @param[in]  mov  需要旋转的数量
 * @return 无
 */
void move_string_fast_left(char *str, int mov)
{
    if (NULL == str || mov <= 0)
        return;
    int len = strlen(str);
    char tmp;
    if (!mov)
        return;
    mov %= len;
    if (!mov)
        return;
    int i, j, k;
    int g_cd = gcd(mov, len);
    for (i=0; i<g_cd; i++) {
        tmp = str[i];
        j = i;
        while (1) {
            k = j + mov;
            if (k >= len)
                k -= len;
            if (k == i)
                break;
            str[j] = str[k];
            j = k;
        }
        str[j] = tmp;
    }
}

/**
 * @brief 将字符串向右旋转n个位置
 * @param      str  待旋转的字符串
 * @param[in]  mov  需要旋转的数量
 * @return 无
 */
void move_string_fast_right(char *str, int mov)
{
    if (NULL == str || mov <= 0)
        return;
    int len = strlen(str);
    if (!mov)
        return;
    mov %= len; // 修移动次数
    if (!mov)
        return;
    mov = len - mov;
    move_string_left(str, mov);
}
/*********************** 最节约空间和时间的方法之一 ************************/

/*********************** 最节约空间和时间的方法之二 ************************/
/**
 *  @brief 交换字符串str中的从pos1开始和从pos2开始长度为num的两部分元素。
 *         注意防止内存越界!
 *  @param      str  待交换部分字符的字符串
 *  @param[in]  pos1 第一部分起始位置
 *  @param[in]  pos2 第二部分起始位置
 *  @param[in]  num  要交换的字符数量
 */
void swap_string(char *str, int pos1, int pos2, int num)
{
    char *str1 = str + pos1;
    char *str2 = str + pos2;
    int i;
       char tmp;
    for (i=0; i<num; i++) {
        tmp   = *str1;
        *str1 = *str2;
        *str2 = tmp;
        str1++;
        str2++;
    }
}

/**
 * @brief 用交换元素的方法进行向左旋转(循环左移)
 * @param      str  待旋转的字符串
 * @param[in]  mov  需要旋转的数量
 * @return 无
 */
void move_string_swap_left(char *str, int mov)
{
    if (NULL == str || mov <= 0)
        return;
    int len = strlen(str);
    if (!mov)
        return;
    mov %= len; // 修移动次数
    if (!mov)
        return;
    int i = mov;
    int j = len - mov;
    while (i != j) {
        if (i > j) {
            swap_string(str, mov-i, mov, j);
            i -= j;
        }
        else {
            swap_string(str, mov - i, mov - i + j, i);
            j -= i;
        }
    }
    swap_string(str, mov-i, mov, i);
}
/*********************** 最节约空间和时间的方法之二 ************************/

/*********************** 最节约空间和时间的方法之三 ************************/
/**
 * @brief 将字符串str中从start开始至end结束的字符进行逆转
 * @param     str  待逆转部分字符的字符串
 * @param[in] start  开始的位置
 * @param[in] end    结束的位置
 * @return 无
 */
void reverse(char *str, int start, int end)
{
    char *pos1 = str + start;
    char *pos2 = str + end;
    char  tmp;
    while (pos1 < pos2) {
        tmp   = *pos1;
        *pos1 = *pos2;
        *pos2 = tmp;
        pos1++;
        pos2--;
    }
}

/**
 * @brief  利用逆转的方法对字符串进行向左旋转(循环左移)
 * @param      str  待旋转的字符串
 * @param[in]  mov  需要旋转的数量
 * @return 无
 */
void move_string_reverse_left(char *str, int mov)
{
    if (NULL == str || mov <= 0)
        return;
    int len = strlen(str);
    if (!mov)
        return;
    mov %= len; // 修移动次数
    if (!mov)
        return;
    reverse(str, 0, mov-1);
    reverse(str, mov, len-1);
    reverse(str, 0, len-1);
}
/*********************** 最节约空间和时间的方法之三 ************************/
/** @} */

#if 1
int main(int argc, char **argv)
{
    char str[] = "Hello World!";
    int  n = atoi(argv[1]);
    int  i;
    move_string_reverse_left(str, n);
    printf("%s\n", str);
    return 0;
}
#endif

 

0
1
分享到:
评论

相关推荐

    python字符串循环左移

    给定一个字符串S[0…N-1],要求把S的前k个字符移动到S的尾部,如把字符串“abcdef”前面的2个字符‘a’、‘b’移动到字符串的尾部,得到新字符串“cdefab”:即字符串循环左移k位。 循环左移k位等价于循环右移n-k位...

    字符串循环左移(右移)的2种算法(附图解析)

    字符串循环左移算法问题描述:暴力法利用三次翻转巧妙实现 问题描述: 给定一个字符串s[0…n-1],要求将s的前k个字符移动到字符串s的尾部。 举个栗子:将字符串“HelloWorld”的前5个字符移动到字符串的尾部,即要...

    数据结构和算法:字符串

    首先,字符串循环左移问题是指将一个字符串S的前k个字符移动到字符串的尾部,例如字符串“abcdef”前两个字符“ab”移动到尾部后得到新字符串“cdefab”。这个问题有多种解决方法,其中一种是暴力移位法,即每次循环...

    C语言中关于字符串左右循环移位的问题

    首先,让我们来解决字符串循环右移的问题。方法一:利用已有的字符串函数。我们可以使用strcpy函数和strlen函数来实现字符串的循环右移。下面是具体的实现代码: ```c void rightloop(char *a, int n) { char b...

    c#循环左移字符示例

    C# 循环左移字符示例是指将一个字符串中的字符进行循环左移操作,以达到将字符串中的一部分字符移至字符串的另一部分的效果。这种操作在实际应用中有着非常重要的作用,例如在数据加密、字符串处理等领域。 循环...

    字符串面试题整理

    1. **字符串循环左移**:给定一个字符串和一个整数k,将字符串中的每个字符向左移动k个位置。例如,字符串"abcdefg",k=2,移动后的结果为"efgabcd"。可以使用双指针技巧,将字符串分为两部分,然后交换它们。 2. *...

    数据结构-字符串.pptx

    1. **字符串循环左移**:这是一个常见的字符串操作,要求将字符串的前k个字符移到末尾。例如,字符串"abcdef"循环左移2位变为"cdefab"。实现这个操作的高效方法是在O(n)的时间复杂度和O(1)的空间复杂度内完成。暴力...

    C语言字符串的练习题和答案

    ### 字符串循环左移 #### 代码示例: ```c void fun(char s[], int m) { int i, j; char ch; for (i = 0; i ; i++) { ch = s[0]; for (j = 1; s[j] != '\0'; j++) { s[j - 1] = s[j]; } s[j - 1] = ch; } ...

    Python 实现字符串中指定位置插入一个字符

    如下所示: str_1='wo shi yi zhi da da niu/n'str_list=list(str_1) nPos=str_list.index('/') str_list.insert(nPos,',') str_2=.join(str_list) ... 您可能感兴趣的文章:python字符串循环左移Python拼接字符串的7

    字符串左旋

    // a 是待处理的字符串,k 为循环左移的位数,n 为字符串的长度 int d, i, j; int last; char tmp; // 注意:此处 k 应该是处理过的, k = k % n d = gcd(k, n); // d 为 k 和 n 的最大公约数 // d 代表了会...

    字符串题目记录

    该题目要求找出^5 位的无前导 0 的一个数字 Y,X[i] 表示其循环左移 i 位得到的数字,求这些 X 中小于 Y,=Y,大于 Y 的不同的数字有多少个。 该题目使用 KMP 算法来解决,首先找到字符串的循环节,然后使用 KMP ...

    华为2019校招笔试题之处理字符串(python版)

    - 对合法字符串循环左移10次后的结果。 - 对上一步的结果按照ASCII表排序输出。 #### 示例分析 根据题目给出的示例,我们可以看到输入与输出的具体形式。 **输入示例**: ``` abc def == acd123 44234tjg aga'-...

    12_除法溢出_逻辑运算移位指令_字符串指令1

    除法溢出、逻辑运算和移位指令、字符串操作指令 根据提供的文件信息,下面对标题、描述、标签、部分内容进行详细的知识点解释: 除法溢出 ...该函数用于将无符号整数 x 循环左移 n 位,并返回结果。

    c代码-编写一个函数 rightrot(x, n),该函数返回将 x 循环右移(即从最右端 移出的位将从最左端移入)n(二进制)位后所得到的值。

    本文将深入探讨如何用C语言编写一个名为`rightrot`的函数,该函数实现的功能是将输入的整数x按照二进制表示循环右移n位。 首先,我们需要理解二进制循环右移的概念。对于一个二进制数x,如果将其右移n位,最右侧的n...

    java实现左旋转字符串

    Java 实现左旋转字符串是 Java 编程语言中的一种常见操作,主要用于实现字符串的循环左移操作。下面将详细介绍 Java 实现左旋转字符串的知识点。 什么是左旋转字符串 左旋转字符串是指将一个字符串的一部分移到...

    Python-列表转字符串

    4. **字符串连接**:`.join()` 是字符串的一个方法,它接受一个列表作为参数,将列表中的所有元素用该字符串连接起来。在这里,我们使用空字符串`''`作为分隔符,所以`.join(li)`的结果就是没有分隔符的连续字符串。...

    3级数据库上机100题.doc

    在给定的题目中,需要实现一个`change(char*s)`函数,该函数要求将字符串`s`中的所有字符左移一个位置,即将第一个字符移到最后。实现这个功能的关键在于正确地遍历字符串并重新排列字符。可以先用`strlen()`函数...

Global site tag (gtag.js) - Google Analytics