C++博客-不晓得哪个

二分搜索算法（迭代，递归）

缘分游走 — Mon, 22 Feb 2010 07:14:00 GMT

1 int bnsearch(int *array,int n,int value)
2 {
3     int left=0,right=n-1;
4     while(left<=right)
5     {
6         int middle=(left+right)/2;
7         if(array[middle]==value) return middle;
8
9         else if(value<array[middle])
10             right=middle-1;
11         else left=middle+1;
12     }
13     return -1;
14 }
15 int re_bnsearch(int *array,int left,int right,int value)
16 {
17     int middle = left + ((right - left) / 2) ;
18
19     if(right<left)
20         return -1;
21     if(value<array[middle])
22     {
23         right=middle-1;
24         return re_bnsearch(array,left,right,value);
25     }
26     else if(array[middle]<value)
27     {
28         left=middle+1;
29         return re_bnsearch(array,left,right,value);
30     }
31     else return middle;
32 }

缘分游走 2010-02-22 15:14 发表评论

vim配置备份

缘分游走 — Wed, 27 Jan 2010 15:28:00 GMT

syntax on
set tabstop=4
set softtabstop=4
set shiftwidth=4
set autoindent
set cindent
set nu
set showmatch
set tags=tags;
set autochdir
let Tlist_Auto_Open=1
let Tlist_Auto_Update=1
let Tlist_Enable_Fold_Column=1
let Tlist_Sort_Type = "name"
let Tlist_WinWidth = 30
let Tlist_Show_One_File = 0
let Tlist_Exit_OnlyWindow = 1
let Tlist_Use_SingleClick = 1
map :Tlist:
map :wincmd p

缘分游走 2010-01-27 23:28 发表评论

从windows读取linux分区里的文件

缘分游走 — Thu, 21 Jan 2010 08:28:00 GMT

R-Linu 这个软件支持ext2/3/4
http://www.data-recovery-software.net/Linux_Recovery_Download.shtml

缘分游走 2010-01-21 16:28 发表评论

c++运算符优先级列表

缘分游走 — Sun, 03 Jan 2010 07:16:00 GMT

http://www.cppreference.com/wiki/operator_precedence

缘分游走 2010-01-03 15:16 发表评论

哈希表（连接法）V0.000001

缘分游走 — Thu, 31 Dec 2009 06:33:00 GMT

摘要: 1，哈希函数用的上一篇文章中的第一个DJB（不知道实现正确了没 :P）2，冲突是用的连接表3，代码虽然能勉强运行，但是比较糟糕。。。。 Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1 /* ... 阅读全文

缘分游走 2009-12-31 14:33 发表评论

一些经典字符串哈希函数算法的 PHP 实现

缘分游走 — Thu, 24 Dec 2009 09:36:00 GMT

摘要: 记录一些经典字符串哈希函数算法，虽然是 PHP 的，但是很容易改为 C 的转自：http://www.flyinghail.net/?p=65 注释：int ord ( string $string ) PHP中返回string字符串中首字母的ASCII码。算法的一些说明：函数后面注释中是我本地测试的执行1000次的速度（单位：s），可以看出来MD5Hash是最快的，而且... 阅读全文

缘分游走 2009-12-24 17:36 发表评论

计数排序

缘分游走 — Fri, 18 Dec 2009 17:35:00 GMT

逻辑比较简单的算法，却用了比较长的时间来实现，主要时间花在三个数组边界上面了，代码很丑，将就了

1 #include<stdio.h>
2 #include<time.h>
3 #include<stdlib.h>
4 #define MAX 100
5 #define MAX2 200
6 #define RANDOM(x) (rand()%x)
7 int * counting_sort(int *arr, int size)
8 {
9     int i,min,max=0,range;
10     int *temp,*des;
11     //min=max=arr[0];
12     for(i=0;i<size;i++)
13     {
14         if(arr[i]>max) max=arr[i];
15         //if(arr[i]>max)max=arr[i];
16         //if(arr[i]
17     }
18     range=max+1;
19     temp =(int *)malloc(range*sizeof(int));
20     des  =(int *)malloc(range*sizeof(int));
21
22     for(i=0;i<range;i++)
23     {
24         temp[i]=0;
25     }
26     for(i=0;i<size;i++)
27     {
28         temp[arr[i]]+=1;
29     }
30     for(i=1;i<range;i++)
31     {
32         temp[i]=temp[i]+temp[i-1];
33     }
34 #if 0
35     printf("temp=");
36     for(i=0;i<range;i++)
37     {
38         printf("%d ",temp[i]);
39     }
40 #endif
41     for(i=size-1;i>=0;i--)
42     {
43         des[temp[arr[i]]]=arr[i];
44         temp[arr[i]]-=1;
45     }
46 return des;
47 }
48 int main()
49 {
50     int i=0;
51     int * arr=(int *)malloc(MAX*sizeof(int));
52     int * get;
53     srand(time(0));
54     for(i=0;i<MAX;i++)
55     {
56         arr[i]=RANDOM(MAX2);
57 //        printf("%d\t",arr[i]);
58     }
59     get=counting_sort(arr,MAX);
60         printf("\n");
61     for(i=1;i<=MAX;i++)
62         printf("%d\t",get[i]);
63     printf("\n");
64 }

缘分游走 2009-12-19 01:35 发表评论

字符串匹配算法（普通BF）

缘分游走 — Wed, 16 Dec 2009 03:01:00 GMT

1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 int main(int argc,char **argv)
5 {
6     int i,j,m=0,n=0;
7     char *src="a ab abc abcd abcde abcdef abcdefg abcdefgh abcdefghi abcdefghij abcdefghijk abcdefghijkl abcdefghijklm abcdefghijklmn abcdefghijklmno abcdefghijklmnop abcdefghijklmnopq abcdefghijklmnopq abcdefghijklmnopq abcdefghijklmnopq abcdefghijklmnopqr abcdefghijklmnopqrs abcdefghijklmnopqrst abcdefghijklmnopqrstuv abcdefghijklmnopqrstuvw abcdefghijklmnopqrstuvwx abcdefghijklmnopqrstuvwxy abcdefghijklmnopqrstuvwxyz";
8     char *des=argv[1];
9     if (argc<2)
10     {
11         printf("usage: %s str_des\n",argv[0]);
12         exit(1);
13     }
14 //    printf("src=%s\n",src);
15 //    printf("des=%s\n",des);
16     i=strlen(src);
17     j=strlen(des);
18     while((m=m-n+1)<i)
19     {
20         n=0;
21         while(src[m-1]==des[n])
22         {
23             if(n==j-1)
24             {
25                 printf("the \"%s\" is fond in the src on %d\n",argv[1],m-n);
26                 exit(0);
27             }
28             m++,n++;
29         }
30     }
31     printf("the \"%s\" is  NOT in the src\n",argv[1]);
32 }

缘分游走 2009-12-16 11:01 发表评论

堆排序

缘分游走 — Wed, 16 Dec 2009 02:45:00 GMT

1 #include<stdio.h>
2 #define MAX 10
3 #define RANDOM(x) rand()%x
4 swap(int *a,int*b)
5 {
6     int tmp;
7     tmp=*a;
8     *a=*b;
9     *b=tmp;
10 }
11 void heapify(int *arr,int size,int i)
12 {
13     int largest=i,left=i*2,right=(i*2)+1;
14     if (left<size&&arr[left]>arr[i])
15     {
16         largest=left;
17     }
18     else
19     {
20         largest=i;
21     }
22     if (right<size&&arr[right]>arr[largest])
23     {
24         largest=right;
25     }
26     if(largest!=i)
27     {
28         swap(&arr[i],&arr[largest]);
29         heapify(arr,size,largest);
30     }
31 }
32
33 void build_heap(int *arr,int size)
34 {
35     int i;
36     for(i=size/2;i>=0;i--)
37     {
38         heapify(arr,size,i);
39     }
40 }
41
42 heap_sort(int *arr,int size)
43 {
44     int i;
45     build_heap(arr,size);
46     for(i=size-1;i>=1;i--)
47     {
48         swap(&arr[0],&arr[i]);
49         size-=1;
50         heapify(arr,size,0);
51     }
52 }
53
54 int main()
55 {
56     int i,arr[MAX+1];
57         //arr[]={4,1,3,2,16,9,10,14,8,7};
58     srand(time(0));
59     for(i=0;i<MAX;i++)
60     {
61         arr[i]=RANDOM(100);
62         printf("%d ",arr[i]);
63     }
64     printf("\n");
65     heap_sort(arr,MAX);
66
67     for(i=0;i<MAX;i++)
68     {
69         printf("%d ",arr[i]);
70     }
71     printf("\n");
72 }

缘分游走 2009-12-16 10:45 发表评论

shell排序

缘分游走 — Mon, 07 Dec 2009 09:53:00 GMT

1 #include<stdio.h>
2 #include<time.h>
3 #define MAX 20
4 #define RANDOM(x) rand()%x
5 void shell_sort(int *arr,int n)
6 {
7
8     int i,j,k,temp,gap;
9     int gaps[]={1,4,13,100,301,};
10     for(k=0;gaps[k]<n;k++);
11     while(--k>=0)
12     {
13         gap=gaps[k];
14         for(i=gap;i<n;i++)
15         {
16             temp=arr[i];
17             j=i;
18             while(arr[j-gap]>temp&&j>=gap)
19             {
20                 arr[j]=arr[j-gap];
21                 j=j-gap;
22             }
23             arr[j]=temp;
24         }
25     }
26 }
27 int main()
28 {
29     int arr[MAX];
30     int i;
31     srand(time(0));
32     for(i=0;i<MAX;i++)
33     {
34         arr[i]=RANDOM(100);
35         printf("%d ",arr[i]);
36     }
37 printf("\n");
38     shell_sort(arr,MAX);
39     for(i=0;i<MAX;i++)
40     {
41         printf("%d ",arr[i]);
42     }
43 printf("\n");
44 }

缘分游走 2009-12-07 17:53 发表评论