上一次修改时间：2016-06-19 23:58:22
实例1-最大子序列求和
例：输入-2，11，-4，13，-5，-2时，答案为20(从A2到A4)
代码如下：
#include <stdio.h>
#include <stdlib.h> //malloc()、calloc()、realloc()、free()、system()、atoi()、atol()、rand()、srand()、exit()等等
#include <string.h> //strstr
#include <time.h> //clock()
//返回3个数中的最大值
int Max3(int a, int b, int c){
return a > b ? (a > c ? a : c) : (b > c ? b : c);
}
//算法1---O(N的立方)
int MaxSum1(int arr[], int n){
int i,j,k,ThisSum,MaxSum=0;
for(i=0; i<n; i++){
for(j=i; j<n; j++){
ThisSum = 0;
for(k=i; k<=j; k++)
ThisSum += arr[k];
if(ThisSum > MaxSum)
MaxSum = ThisSum;
}
}
return MaxSum;
}
//算法2---O(N的平方)
int MaxSum2(int arr[], int n){
int i,j,k,ThisSum,MaxSum=0;
for(i=0; i<n; i++){
ThisSum = 0;
for(j=i; j<n; j++){
ThisSum += arr[j];
if(ThisSum > MaxSum)
MaxSum = ThisSum;
}
}
return MaxSum;
}
/*
* 分治：将数组分成左右两部分，分别求出左边，中间及右边的最大子序列的和，取三个中最大值
* 求中间的最大值：
* 1）左边求出包含最后一个项在内的最大了序列的和M；
* 2）右边求出包含第一个项在内的最大子序列的和N；
* 3）M + N 即为中间的最大子序列和；
* 递归时，MaxLeftSum，MaxRightSum均为已知条件，由上一次递归返回
*/
int MaxSum3(int arr[], int Left, int Right){
int MaxLeftSum, MaxRightSum;
int MaxLeftBorderSum, MaxRightBorderSum;
int LeftBorderSum, RightBorderSum;
int Center, i;
//递归的基准条件
if(Left == Right){
if(arr[Left] > 0)
return arr[Left];
else
return 0;
}
Center = (Left + Right) / 2;
MaxLeftSum = MaxSum3(arr, Left, Center);
MaxRightSum = MaxSum3(arr, Center+1, Right);
MaxLeftBorderSum = 0;
LeftBorderSum = 0;
for(i=Center; i>=Left; i--){
LeftBorderSum += arr[i];
if(LeftBorderSum > MaxLeftBorderSum)
MaxLeftBorderSum = LeftBorderSum;
}
MaxRightBorderSum = 0;
RightBorderSum = 0;
for(i=Center+1; i<=Right; i++){
RightBorderSum += arr[i];
if(RightBorderSum > MaxRightBorderSum)
MaxRightBorderSum = RightBorderSum;
}
return Max3(MaxLeftSum, MaxRightSum, MaxRightBorderSum + MaxLeftBorderSum);
}
//联机算法
int MaxSum4(int arr[], int n){
int ThisSum=0, MaxSum=0, j;
for(j=0; j<n; j++){
//每次循环时，ThiSum里已经是前j项里子序列里的最大值
ThisSum += arr[j];
if(ThisSum > MaxSum)
MaxSum = ThisSum;
else if(ThisSum < 0)
ThisSum = 0;
}
return MaxSum;
}
//文件读取
char *FileLoad(char *file_name){
char *pchBuf = NULL;
int nLen = 0;
FILE *pf = fopen(file_name,"r");
fseek(pf, 0, SEEK_END);//文件指针移到文件尾部
nLen = ftell(pf);//得到当前指针位置，即是文件的长度
rewind(pf);//文件指针恢复到文件头位置
//动态申请空间，为保存字符串结尾标志\0，多申请一个字符的空间
pchBuf = (char *)malloc(sizeof(char)*nLen + 1);
if(!pchBuf){
perror("内存不够！\n");
exit(0);
}
//读取文件内容，读取的长度和源文件长度可能有出入，这里自动调整nLen
nLen = fread(pchBuf, sizeof(char), nLen, pf);
pchBuf[nLen] = '\0'; //添加字符串结尾标志
//printf("%s\n", pchBuf); //输出文件内容
fclose(pf); //关闭文件
return pchBuf;
//free(pchBuf); //释放空间
}
/**
* Split a string into some strings according to a list of separators.
*
* @Param dest out: storage the strings has be split.
* @Param count out: the number of strings has be split successfully, 0 for failed to split.
* @Param s_str in: the strings for split.
* @Param separator in: the list of split separators.
* @Param number_separator in: the numbers of separators.
* @Param compress_separator in: will be create a empty string when two split adjacent
* if compress_separator > 0 and not for compress_separator == 0
* @Param keep_separator in: the separators will be put into parameter 'dest' if keep_separator > 0
*/
int strsplit(char ***dest, int *count, char *s_str, char **separator, int number_separators, int compress_separator, int keep_separator)
{
int i = 0;
char **result = NULL;
char **temp_result = NULL;
unsigned int curt_size = 0;
unsigned int new_size = 0;
char *look_ahead = NULL;
char *most_front_separator_start = NULL;
char *most_front_separator_end = NULL;
char *separator_start = NULL;
int find_a_separator = 0;
int find_a_string = 0;
*count = 0;
*dest = NULL;
/* check parameters */
if (
dest == NULL
|| s_str == NULL || *s_str == '\0'
|| separator == NULL
|| number_separators <= 0
|| compress_separator < 0
|| keep_separator < 0
)
return -1;
for (i = 0; i < number_separators; i++)
if (separator[i] == NULL || *separator[i] == '\0')
return -1;
for (look_ahead = s_str; *look_ahead != '\0'; look_ahead = most_front_separator_end)
{
most_front_separator_start = look_ahead + strlen(look_ahead);
most_front_separator_end = look_ahead + strlen(look_ahead);
find_a_separator = 0;
/* find the next separator. */
for (i = 0; i < number_separators; i++)
{
separator_start = strstr(look_ahead, separator[i]);
if (separator_start == NULL)
continue;
find_a_separator = 1;
/* update the most front separator. */
if (separator_start < most_front_separator_start)
{
most_front_separator_start = separator_start;
most_front_separator_end = most_front_separator_start + strlen(separator[i]);
}
}
find_a_string = (look_ahead == most_front_separator_start) ? 0 : 1;
/* allow put the new string into result if need. */
new_size = (find_a_string > 0) ? (curt_size + 1) : ((compress_separator > 0) ? curt_size : (curt_size + 1));
/* allow put the separator into result if need. */
new_size = (keep_separator > 0) ? (new_size + 1) : new_size;
if (new_size == curt_size)
continue;
temp_result = (char **)malloc((new_size) * sizeof(char *));
if (temp_result == NULL)
{
if (result != NULL)
{
for (i = 0; i < curt_size; i++)
if (result[i] != NULL)
free(result[i]);
free(result);
result = NULL;
}
return -2;
}
/* copy the pointers of string find early. */
memset(temp_result, 0, new_size);
for (i = 0; i < curt_size; i++)
temp_result[i] = result[i];
if (find_a_string == 0)
{
if (compress_separator == 0)
{
temp_result[curt_size] = (char *)malloc(sizeof(char));
if (temp_result[curt_size] == NULL)
{
if (temp_result != NULL)
{
for (i = 0; i < curt_size; i++)
if (temp_result[i] != NULL)
free(temp_result[i]);
free(temp_result);
temp_result = NULL;
}
return -2;
}
memset(temp_result[curt_size], 0, 1);
}
}
else
{
/* put the new string into result. */
temp_result[curt_size] = (char *)malloc((most_front_separator_start - look_ahead + 1) * sizeof(char));
if (temp_result[curt_size] == NULL)
{
if (temp_result != NULL)
{
for (i = 0; i < curt_size; i++)
if (temp_result[i] != NULL)
free(temp_result[i]);
free(temp_result);
temp_result = NULL;
}
return -2;
}
memset(temp_result[curt_size], 0, most_front_separator_start - look_ahead + 1);
strncpy(temp_result[curt_size], look_ahead, most_front_separator_start - look_ahead);
temp_result[curt_size][most_front_separator_start - look_ahead] = '\0';
}
if (keep_separator > 0)
{
/* put the separator into result. */
temp_result[new_size - 1] = (char *)malloc(most_front_separator_end - most_front_separator_start + 1);
if (temp_result[new_size - 1] == NULL)
{
if (temp_result != NULL)
{
for (i = 0; i < new_size - 1; i++)
if (temp_result[i] != NULL)
free(temp_result[i]);
free(temp_result);
temp_result = NULL;
}
return -2;
}
memset(temp_result[new_size - 1], 0, most_front_separator_end - most_front_separator_start + 1);
strncpy(temp_result[new_size - 1], most_front_separator_start, most_front_separator_end - most_front_separator_start);
temp_result[new_size - 1][most_front_separator_end - most_front_separator_start] = '\0';
}
/* update result. */
free(result);
result = temp_result;
temp_result = NULL;
curt_size = new_size;
}
*dest = result;
*count = curt_size;
return 0;
}
int main(void){
//文件读取，并切割成数组
char *str = FileLoad("./1W.txt");//注意将该字符串使用完后free掉
char *separator[] = {","};//定义切割符
char **result = NULL;
int n_str = 0,i;
strsplit(&result, &n_str, str, separator, 1, 1, 1);
//去掉分割符
int key=0,n_str_arr = n_str-1, temp_arr[n_str_arr];//去掉结尾的空白符
for (i=0; i<(n_str-1); i++){
if(strcmp(result[i],",") == 0)
n_str_arr -= 1;
else{
temp_arr[key] = atoi(result[i]); //注：result[i]存储的是一个字符串
key++;
}
}
//完成的数组
int arr[n_str_arr];
for(i=0; i<n_str_arr; i++){
arr[i] = temp_arr[i];
//printf("%d\n",arr[i]);
}
for (i = 0; i < n_str; i++)
free(result[i]);
free(result);
/*int arr[] = {-2,11,-4,13,-5,-2};*/
int len = sizeof(arr)/sizeof(arr[0]);
double start, finish;
//算法1---O(N的立方)
start = clock();//取开始时间
int res1 = MaxSum1(arr, len);
finish = clock();//取结束时间
printf( "O(N的立方):%f seconds\n",(finish - start) / CLOCKS_PER_SEC);//以秒为单位显示之
//算法2---O(N的平方)
start = clock();//取开始时间
int res2 = MaxSum2(arr, len);
finish = clock();//取结束时间
printf( "O(N的平方):%f seconds\n",(finish - start) / CLOCKS_PER_SEC);//以秒为单位显示之
//分治算法
start = clock();//取开始时间
int res3 = MaxSum3(arr, 0 , len-1);
finish = clock();//取结束时间
printf( "分治算法:%f seconds\n",(finish - start) / CLOCKS_PER_SEC);//以秒为单位显示之
start = clock();//取开始时间
int res4 = MaxSum4(arr, len);
finish = clock();//取结束时间
printf( "联机算法:%f seconds\n\n",(finish - start) / CLOCKS_PER_SEC);//以秒为单位显示之
printf("res1(O(N的立方))=%d\n", res1);
printf("res2(O(N的平方))=%d\n", res2);
printf("res3(分治算法)=%d\n", res3);
printf("res4(联机算法)=%d\n", res4);
}数据说明：-99999到99999这间的随机数
结果1：(数据量级：2000)
O(N的立方):6.370000 seconds O(N的平方):0.010000 seconds 分治算法:0.000000 seconds 联机算法:0.000000 seconds res1(O(N的立方))=4904628 res2(O(N的平方))=4904628 res3(分治算法)=4904628 res4(联机算法)=4904628
结果2：(数据量级：4000)
O(N的立方):50.840000 seconds O(N的平方):0.050000 seconds 分治算法:0.000000 seconds 联机算法:0.000000 seconds res1(O(N的立方))=7641451 res2(O(N的平方))=7641451 res3(分治算法)=7641451 res4(联机算法)=7641451
结果3：(数据量级：10000) 注：算法1-O(N的立方)运行时间估算在10个多小时，已经没法正常使用
O(N的平方):0.260000 seconds
分治算法:0.000000 seconds
联机算法:0.000000 seconds
res2(O(N的平方))=5849432
res3(分治算法)=5849432
res4(联机算法)=5849432
结果4：(数据量级：10万)注：算法2-O(N的平方)运行时间估算在18个多小时，已经没法正常使用
分治算法:0.020000 seconds 联机算法:0.000000 seconds res3(分治算法)=15878572 res4(联机算法)=15878572
结果4：(数据量级：100万)