データ構造:n個の要素を持つ配列を左に循環してi個の位置に移動します.

1248 ワード

#include 

using namespace std;

/*
        :     n            i   。
*/

/*        */
void reverses(char *arr, int start, int over)
{
    for(; start < over; start++, over--)
    {
        char temp = arr[start];
        arr[start] = arr[over];
        arr[over] = temp;
    }
}

/*     */
void converse(char *arr, int n, int i)
{
    //     i   
    reverses(arr, 0, i - 1);
    //       n-i   
    reverses(arr, i, n - 1);
    //          
    reverses(arr, 0, n - 1);
    for(int j = 0; j < n; j++)
    {
        cout << arr[j] << ' ';
    }
}

int main()
{
    //         
    char arr[10] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'};
    converse(arr, 10, 5);
    return 0;
}


説明:
以上の配列arrは、配列a bを配列b a(aは配列前のi個の要素を表し、bは配列の残りのn-i個の要素を表す)に変換し、aを逆にしてa'bを得、bを逆にしてa'b'を得、最後にa'b'を逆にして(a'b')=baを得ると考えられます.
たとえば:
abcde fghijについては、2つの部分に分けられ、abcdeとfghij、
1.abcdeを逆さまにしてedcbaを得る
2.fghijを逆にしてjihgfを得る.
        二回逆置した後に得る:edc bajihgf
3.edc bajihgfを逆置して得る:fghijabcde
アルゴリズム解析:
このアルゴリズムは追加の開発空間を必要とせず、空間の複雑さはO(1)であり、時間の複雑さはO(n)である.