重写:求比指定数大且最小的“不重复数”问题

问题:给定任意一个正整数,求比这个数大且最小的“不重复数”,“不重复数”的含义是相邻两位不相同,例如1101是重复数,而1201是不重复数.

我之前写过一个(传送门:求比指定数大且最小的“不重复数”问题),里面总结了些不足的地方,就没有想去重写。

直到被 garbageMan 给教育了一番 (传送门:评playerc网友的”求比指定数大且最小的“不重复数”问题”),我才发现,写的太差劲了。

在此感谢 garbageMan 的教导。不多说,下面附上代码,有什么错误还希望大家多指点.

#include <stdio.h>#include <ctype.h>#include <stdlib.h>#include <string.h>#define BCD_UINT_MAX_LENGTH (12)/* 这里 garbageMan 指出 存在潜在的错误,两边要加上括号;(其实回家检查的时候我也发现了)#define min(a,b) (a) < (b) ? (a) : (b)改成如下代码*/#define min(a,b) ((a) < (b) ? (a) : (b))/* bcd unsigned integerlittle endian*/struct bcd_uint{unsigned char value[BCD_UINT_MAX_LENGTH];unsigned int length;};/* 从标准输入获得 bcd_uint */struct bcd_uint * bcd_uint_get(struct bcd_uint * v);/* 在指定的位置加 1. 返回进位影响的最高位的下标 */unsigned int bcd_uint_inc(struct bcd_uint *v, unsigned int where);/* 输出 bcd_uint */void bcd_uint_print(struct bcd_uint v);/*** utils ****//*** 获得最小不重复数 ***/struct bcd_uint * find(struct bcd_uint v);/* 反转字符串 */void str_reverse(unsigned char *str, unsigned int length);/* 交换字符*/void exchange(unsigned char * a, unsigned char *b);/* 得到最右边开始第一次出现重复字的最小下标的地址 */unsigned char * get_repeat_item(unsigned char * v, unsigned int length);int main(void){struct bcd_uint num = {{0u},0u};struct bcd_uint *res = NULL;printf(“Please input Unsigned Integer : “);if (bcd_uint_get(&num) == NULL) return 1;res = find(num);bcd_uint_print(*res);free(res);return 0;}void str_reverse(unsigned char *str, unsigned int length){unsigned char *last;if (length < 2) {return;}for (last = str + length -1; last > str; ++str, –last){exchange(str,last);}}void exchange(unsigned char * a, unsigned char *b){/* cpoint 同学指出 这个地方存在潜在的错误,比如 a=b 的时候*a ^= *b;*b ^= *a;*a ^= *b;  于是,,改成下面通用的代码 */    unsigned char c;    c = *a;    *a = *b;    *b = c;}struct bcd_uint * find(struct bcd_uint v){unsigned int search_length ;unsigned char * finded;unsigned char * last_finded;struct bcd_uint *res = (struct bcd_uint *)malloc(sizeof (struct bcd_uint));res->length = v.length;memcpy(res->value, v.value, sizeof (unsigned char) * v.length);bcd_uint_inc(res, 0); /* v + 1 */search_length = res->length;last_finded = res->value;/* 在最后一次找到重复的位置开始,查找指定的长度。 */while ((finded = get_repeat_item(last_finded, search_length)) != NULL){/* 在找到重复的位置+1,并依据进位影响的位置 设置搜索长度 */search_length = bcd_uint_inc(res, finded – res->value) + 1;search_length = min(search_length, res->length);search_length = search_length – (finded – res->value);last_finded = finded;}/* set rests as 010101010 *//* *last_finded will never be 0 */while (last_finded > res->value){*(last_finded-1) = !*last_finded;– last_finded;}return res;}unsigned char * get_repeat_item(unsigned char * v, unsigned int length){unsigned char * cur;if (length < 2){return NULL;}cur = v + length -1;while (cur > v){if ( *cur == *(cur – 1)){return cur-1;}– cur;}return NULL;}struct bcd_uint * bcd_uint_get(struct bcd_uint * v){unsigned char c;for (v->length = 0; !feof(stdin); ++ v->length){/* 因为最高位可能进 1 所以 -1*/if (v->length > (BCD_UINT_MAX_LENGTH – 1)){fprintf(stderr, “The input is too long!\n”);return NULL;}c = getc(stdin);if (c == ‘\n’ || c == ‘\0’){break;}if (!isdigit(c)){fprintf(stderr, “Please input Unsigned Integer!\n”);return NULL;}v->value[v->length] = c – ‘0’;}str_reverse(v->value, v->length);return v;}void bcd_uint_print(struct bcd_uint v){unsigned char * last ;last = v.value + v.length; while(last > v.value){– last;putchar( *last + ‘0’);}putchar(‘\n’);}unsigned int bcd_uint_inc(struct bcd_uint *v, unsigned int where){unsigned int carry ;for (carry = 1; carry != 0 && where < v->length; ++ where){v->value[where] += carry;carry = v->value[where] / 10;v->value[where] %= 10;}if (carry != 0){v->value[where] = carry;++ v->length;}else {/* 执行这里的时候 where 指向进位影响的下一个,所以减掉*/–where;}return where;}辽远或偏僻的地方,而会常常想起这一次的旅行,想起那座山,那个城,那些人……

重写:求比指定数大且最小的“不重复数”问题

相关文章:

你感兴趣的文章:

标签云: