数据结构之字符串反转

说明：有一条语句，如"Life is painting a picture, not doing a sum"，要求语句中的单词左右对换，但每个单词不变，即变换后的串应该为

"sum a doing not, picture a painting is Life"

两种方法：

1.分治法，将字符串变成一个单词和一个新的字符串然后对换，递归处理字符串。

2.先整体反转，再每个单词反转，类似数组右移K位的方法

 

// project1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<string.h>

const int LENGTH=1000;

//分治法
int blank_pos(char str[],int beg,int end){
    for(int i=beg;str[i] && i<=end;i++){
        if(str[i]==' ')
            return i;
    }
    return -1;
}
void reverse_adjacent(char str[],int beg,int end){
    for(int i=beg,j=end;i<j;i++,j--){
        char tmp=str[i];
        str[i]=str[j];
        str[j]=tmp;
    }
}

void combine(char str[],int beg,int pos,int end){
    char tmp[LENGTH];
    //将str[pos+1..end]复制到tmp[beg..beg+end-pos-1]
    memcpy(&tmp[beg],&str[pos+1],sizeof(char)*(end-pos));
    memcpy(&tmp[beg+end-pos+1],&str[beg],sizeof(char)*(pos-beg));
    //str[beg+end-pos]=' '
    tmp[beg+end-pos]=' ';
    memcpy(&str[beg],&tmp[beg],sizeof(char)*(end-beg+1));
}
//分治法
void reverse_words(char str[],int beg,int end){
    if(str==NULL || beg==end)
        return;
    int pos=blank_pos(str,beg,end);//空格位置
    if(pos!=-1 && pos>=beg && pos<=end){//存在空格
        reverse_words(str,pos+1,end);
        combine(str,beg,pos,end);
    }
}
//先整体反转，再每个单词反转
void reverse_words_two(char str[],int beg,int end){
    reverse_adjacent(str,beg,end);//整体反转
    //每个单词反转
    int i=beg;
    while(i<=end){
        int start=i,ending;
        while(str[i] && str[i]!=' ')
            i++;
        ending=i-1;
        i++;//跳过空格
        if(start<ending)
            reverse_adjacent(str,start,ending);
    }
}


int _tmain(int argc, _TCHAR* argv[])
{
    char str1[LENGTH]=" banana apple orange ";
    char str2[LENGTH]="abcdefghij klmn ";
    char str3[LENGTH]=" 123456789 234 986 3433 9999";
    
    reverse_words_two(str1,0,strlen(str1)-1);
    reverse_words(str1,0,strlen(str1)-1);
    printf("After reverse,str=%s\n",str1);
    reverse_words_two(str2,0,strlen(str2)-1);
    reverse_words(str2,0,strlen(str2)-1);
    printf("After reverse,str=%s\n",str2);
    reverse_words_two(str3,0,strlen(str3)-1);
    reverse_words(str3,0,strlen(str3)-1);
    printf("After reverse,str=%s\n",str3);
    return 0;
}