データ構造: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)である.