C 语言如何实现向量(字符串)旋转(循环位移)

《编程珠玑》上有这样一题:
将一个 n 元一维向量左旋转 i 个位置。例如,当 n = 8, i = 3 时,
向量 abcdefgh 旋转为 defghabc 。简单的代码使用一个 n元中间向量
在 n 步内完成工作。能否仅使用 10 字节额外的存储空间,在正比于 n 的
时间内完成向量旋转。
下面,是参照书上的思路完成的代码。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

unsigned int str_len(char * str){
	unsigned int len = 0;
	if(NULL != str){
		while('\0' != *str++){
			len++;
		}
	}
	return len;
}

void str_rotation(
	char * vector,
	unsigned int length,
	unsigned int delta
){
	if(delta > length){
		delta =  delta % length;
	}

	if(0 == delta || 1 == length || delta == length){
		return;
	}

	char buffer;
	unsigned int i;
	while(delta--){
		buffer = vector[0];
		i = 0;
		while(i < length){
			vector[i] = vector[++i];
		}
		vector[length - 1] = buffer;
	}
}

void str_rotation_step(
	char * vector,
	unsigned int length,
	unsigned int delta
){

	if(delta > length){
		delta =  delta % length;
	}

	if(0 == delta || 1 == length || delta == length){
		return;
	}

	char * end = vector + length - 1, buffer;
	unsigned int i, j = 0, step = length / delta, k;

	while(j < delta){
		k = i = j++;
		buffer = vector[i];
		while(1){
			k = i + delta;
			if(k >= length){
				break;
			}
			vector[i] = vector[k];
			i = k;
		}
		vector[i] = buffer;
	}
	//旋转结尾剩余的未排序的向量
	i = length % delta;
	if(i > 0){
		str_rotation_step(vector + length - delta, delta, delta - i);
	}
}

static void swap_str(
	char * vector,
	unsigned int a,
	unsigned int b,
	unsigned int len
){
	char buffer;
	unsigned int i = len;
	while(len--){
		buffer = vector[a + len];
		vector[a + len] = vector[b + len];
		vector[b + len] = buffer;
	}
}

void str_rotation_swap(
	char * vector,
	unsigned int length,
	unsigned int delta
){
	if(delta > length){
		delta =  delta % length;
	}

	if(0 == delta || 1 == length || delta == length){
		return;
	}

	unsigned int i, j, p;
	i = p = delta;
	j = length - p;

	while(i != j){
		if(i > j){
			swap_str(vector, p - i, p, j);
			i -= j;
		}
		else{
			swap_str(vector, p - i, p + j - i, i);
			j -= i;
		}
	}
	swap_str(vector, p - i, p, i);
}

static void str_copy(char * dest, char * src, unsigned int len){
	if(NULL == dest || NULL == src || len < 1){
		return;
	}

	while(len--){
		dest[len] = src[len];
		if('\n' == src[len]){
			return;
		}
	}
}

#define MAX_STR_LENGTH 12
#define TEST_CASES 5
#define ROTATIONS 4
#define ROTATION_FUNCTIONS 3
static char test_str[MAX_STR_LENGTH];
typedef void (*rotation_function)(char * v, unsigned int l, unsigned int d);
static char test_cases[TEST_CASES][ROTATIONS][MAX_STR_LENGTH] = {
	{"abcdefghij", "bcdefghija", "cdefghijab", "defghijabc"},
	{"abcdef", "bcdefa", "cdefab", "defabc"},
	{"abc", "bca", "cab", "abc"},
	{"ab", "ba", "ab", "ba"},
	{"a", "a", "a", "a"}
};
static rotation_function rotation_functions[ROTATION_FUNCTIONS] = {
	str_rotation,
	str_rotation_step,
	str_rotation_swap
};
static char rotation_function_names[ROTATION_FUNCTIONS][20] = {
	"str_rotation",
	"str_rotation_step",
	"str_rotation_swap"
};

void test_one(char * vector, rotation_function f, unsigned int delta, char * expected){
	str_copy(test_str, vector, MAX_STR_LENGTH);
	printf("%-15s->", test_str);
	f(test_str, str_len(test_str), delta);
	printf("%15s\t[%c]\n", test_str, (0 == strcmp(test_str, expected)) ? 'Y' : 'N');
}

void run_test(){
	int i, j, k;
	char * test_case;
	for(j = 0; j < ROTATION_FUNCTIONS; j++){
		printf("\nRun testcases of [ %-22s ]\n-------------\n", rotation_function_names[j]);
		for(i = 0 ; i < TEST_CASES; i++){
			test_case = test_cases[i][0];
			for(k = 1; k < ROTATIONS; k++){
				test_one(test_case, rotation_functions[j], k, test_cases[i][k]);
			}
		}
	}
}

#define BENCHMARKS 100000

void run_benchmark(){
	printf("\nStart Benchmark.\n-------------\n");
	int i, k;
	char * vector = "abcdefghijklnmopqrstuvwxyz012345678910ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	unsigned int length = str_len(vector);
	char * test = malloc(length + 1);
	if(NULL != test){
		time_t startime, endtime;
		for(k = 0; k < ROTATION_FUNCTIONS; k++){
			str_copy(test, vector, length + 1);
			startime = clock();
			for(i = 0 ; i < BENCHMARKS; i++){
				rotation_functions[k](test, length, i);
			}
			endtime = clock();
			printf("%-22s : %d \n", rotation_function_names[k], endtime - startime);
		}
	}
	printf("-------------\nEnd Benchmark.\n");
}

int main(int argc, char ** argv){
	run_test();
	run_benchmark();
	return 0;
}

下面是运行输出的结果:

Run testcases of [ str_rotation           ]
-------------
abcdefghij     ->     bcdefghija	[Y]
abcdefghij     ->     cdefghijab	[Y]
abcdefghij     ->     defghijabc	[Y]
abcdef         ->         bcdefa	[Y]
abcdef         ->         cdefab	[Y]
abcdef         ->         defabc	[Y]
abc            ->            bca	[Y]
abc            ->            cab	[Y]
abc            ->            abc	[Y]
ab             ->             ba	[Y]
ab             ->             ab	[Y]
ab             ->             ba	[Y]
a              ->              a	[Y]
a              ->              a	[Y]
a              ->              a	[Y]

Run testcases of [ str_rotation_step      ]
-------------
abcdefghij     ->     bcdefghija	[Y]
abcdefghij     ->     cdefghijab	[Y]
abcdefghij     ->     defghijabc	[Y]
abcdef         ->         bcdefa	[Y]
abcdef         ->         cdefab	[Y]
abcdef         ->         defabc	[Y]
abc            ->            bca	[Y]
abc            ->            cab	[Y]
abc            ->            abc	[Y]
ab             ->             ba	[Y]
ab             ->             ab	[Y]
ab             ->             ba	[Y]
a              ->              a	[Y]
a              ->              a	[Y]
a              ->              a	[Y]

Run testcases of [ str_rotation_swap      ]
-------------
abcdefghij     ->     bcdefghija	[Y]
abcdefghij     ->     cdefghijab	[Y]
abcdefghij     ->     defghijabc	[Y]
abcdef         ->         bcdefa	[Y]
abcdef         ->         cdefab	[Y]
abcdef         ->         defabc	[Y]
abc            ->            bca	[Y]
abc            ->            cab	[Y]
abc            ->            abc	[Y]
ab             ->             ba	[Y]
ab             ->             ab	[Y]
ab             ->             ba	[Y]
a              ->              a	[Y]
a              ->              a	[Y]
a              ->              a	[Y]

Start Benchmark.
-------------
str_rotation           : 950000
str_rotation_step      : 160000
str_rotation_swap      : 60000
-------------
End Benchmark.

Post a Comment

Your email is never shared. Required fields are marked *

*
*