http://www.cnblogs.com/LBSer/p/3310455.html
http://www.sxrczx.com/pages/my.oschina.net/853294317/blog/296594.html
http://community.apicloud.com/bbs/forum.php?mod=viewthread&tid=5300
受朋友委托写个查找附近人的算法,当然是不会写,不知道从何下手,于是学习了下geohash算法。看懂后开始一步步实现,当然还没有完全写完。不会之处在于:如何对已有的字符串进行前缀匹配的呢?怎么查找附近的人呢?
写了很多注释,怕自己以后看不懂。这也算是第一次体会到算法在工程中的作用。想起以前老师说算法在开发中没用!!表示汗颜、无语。
1 #include<iostream>
2 #include<stdio.h>
3 #include<string>
4 #include<string.h>
5 #include<map>
6 #include <stdlib.h>
7 #include <stdio.h>
8 #include <winsock.h>
9 #include <mysql.h>
10 #include <cstring>
11 using namespace std;
12 map<string, string> base32;
13
14 //将纬度、经度二进制化
15 //纬度范围(-90, 90)
16 //经度范围(-180, 180)
17 //传入w,返回二进制编码
18 //max_step控制递归次数同时也是二进制编码长度
19 //注意返回的是逆序的字符串 max_step必须是5的倍数
20 string geohash_w_bin(double w,double left,double right,int step,int max_step)
21 {
22 if (step > max_step)
23 {
24 return "";
25 }
26 double mid = (left + right)*1.0 / 2;
27
28 if (w >= left && w <= mid) {
29 return geohash_w_bin(w, left, mid,step+1,max_step)+"0";
30 }
31 if (w >= mid && w <= right) {
32 return geohash_w_bin(w, mid, right,step+1,max_step)+"1";
33 }
34
35 }
36
37 //合并经纬度
38 //传入经度和纬度 返回合并的二进制编码
39 string geohash_merge(string j, string w) {
40 string s;
41 for (int i = 0; i <j.size(); i++){
42 s += j[i];
43 s += w[i];
44 }
45 return s;
46 }
47
48 //二进制编码base32化
49 string geohash_base32(string s) {
50 string temp;
51 string ans;
52 for (int i = 0; i < s.size(); i++) {
53 temp += s[i];
54 if ((i + 1) % 5 == 0) {
55 ans+=base32[temp];
56 temp = "";
57 }
58 }
59
60 return ans;
61 }
62
63 //*****************
64 //将经纬度转为base32 返回base32编码
65 //w为纬度 j为经度
66 //*****************
67 string geohash(double j, double w) {
68 string s_w="", s_j="";
69 string s="", ss="";
70
71 s_w = geohash_w_bin(w, -90, 90, 1, 30);
72 s_j = geohash_w_bin(j, -180, 180, 1, 30);
73
74 reverse(s_w.begin(), s_w.end());
75 reverse(s_j.begin(), s_j.end());
76
77 s = geohash_merge(s_j, s_w);
78 s= geohash_base32(s);
79 return s;
80 }
81
82 //有返回值的数据库写入
83 MYSQL_RES * executeQuery(char *sql)
84 {
85 MYSQL* pConn = mysql_init(0);
86 if (!mysql_real_connect(pConn, "localhost", "root", "root", "study1", 0, 0, 0))
87 {
88 goto error;
89 }
90 if (mysql_query(pConn, "set names gbk"))
91 {
92 goto error;
93 }
94 if (mysql_query(pConn, sql))
95 {
96 goto error;
97 }
98
99 MYSQL_RES *result = mysql_store_result(pConn);
100 mysql_close(pConn);
101 return result;
102
103 error:
104 cout << "执行出错 " << mysql_error(pConn)<<endl;
105 //fprintf(cgiOut, "执行出错 %s", mysql_error(pConn));
106 //printf("执行出错 %s",mysql_error(pConn));
107 exit:
108 mysql_close(pConn);
109 }
110
111 //无返回值的数据库写入
112 void executeNonQuery(char * sql)
113 {
114 MYSQL* pConn = mysql_init(0);
115 if (!mysql_real_connect(pConn, "localhost", "root", "root", "study1", 0, 0, 0))
116 {
117 goto error;
118 }
119 if (mysql_query(pConn, "set names gbk"))
120 {
121 goto error;
122 }
123 if (mysql_query(pConn, sql))
124 {
125 goto error;
126 }
127 goto exit;
128 error:
129 cout << "执行出错 " << mysql_error(pConn) << endl;
130 /*cgiHeaderContentType("text/html;charset=gbk");
131 fprintf(cgiOut, "执行出错 %s", mysql_error(pConn));*/
132 //printf("执行出错 %s",mysql_error(pConn));
133 exit:
134 mysql_close(pConn);
135 }
136
137
138 //字符串截取函数
139 string jiequ(string s, int l, int r) {
140 string temp;
141 for (int i = 0; i < r; i++)
142 {
143 temp += s[i];
144 }
145 return temp;
146 }
147
148
149 //输入base32编码,结果打印在屏幕上
150 //查询编码前缀相同的
151 void geohash_search(string base32)
152 {
153 for (int i = base32.size()-3; i > 0; i--)
154 {
155 string temp_base32 = jiequ(base32, 0, i);
156 const char *temp_c_base32 = temp_base32.c_str();
157 char sql[1024]; char *c = "%";
158 int f = 0;
159
160 sprintf(sql, "select * from t_theatre where base32 like '%s%s'", temp_c_base32,c);
161 MYSQL_RES *result = executeQuery(sql);
162 MYSQL_ROW row;
163
164 while (row = mysql_fetch_row(result))
165 {
166 char *base32 = row[1];
167 char *name = row[2];
168 cout << base32 << " " << name << endl;
169 //f = 1;
170 }
171
172 /*if (f) {
173 return;
174 }*/
175
176 }
177
178
179
180
181 }
182 int main()
183 {
184 base32["00000"] = "0";
185 base32["00001"] = "1";
186
187 base32["00010"] = "2";
188 base32["00011"] = "3";
189
190 base32["00100"] = "4";
191 base32["00101"] = "5";
192 base32["00110"] = "6";
193 base32["00111"] = "7";
194
195 base32["01000"] = "8";
196 base32["01001"] = "9";
197 base32["01010"] = "b";//10
198 base32["01011"] = "c";//11
199 base32["01100"] = "d";//12
200 base32["01101"] = "e";//13
201 base32["01110"] = "f";//14
202 base32["01111"] = "g";//15
203
204 base32["10000"] = "h";//16
205 base32["10001"] = "j";//17
206 base32["10010"] = "k";//18
207 base32["10011"] = "m";//19
208 base32["10100"] = "n";//20
209 base32["10101"] = "p";//21
210 base32["10110"] = "q";//22
211 base32["10111"] = "r";//23
212 base32["11000"] = "s";//24
213 base32["11001"] = "t";//25
214 base32["11010"] = "u";//26
215 base32["11011"] = "v";//27
216 base32["11100"] = "w";//28
217 base32["11101"] = "x";//29
218 base32["11110"] = "y";//30
219 base32["11111"] = "z";//31
220
221 geohash_search("wttf1y0ewmt3");
222
223 //select * from where like'wttc%'
224 //geohash_search("select * from t_theatre where base32 like 'wttc%'");
225
226
227
228 /*while (1) {
229 double w, j; char name[128], sql[1024];
230 cin >> j >> w>>name;
231
232 string base32=geohash(j,w);
233 const char *ch = base32.c_str();
234
235 sprintf(sql, "insert into t_theatre(base32,name) values('%s','%s')", ch,name);
236 executeNonQuery(sql);
237 }*/
238
239
240 ////insert into t_theatre(base32) values()
241 //char sql[] = "insert into t_theatre(base32) values('klkl')";
242 //executeNonQuery(sql);
243 //120.677252 31.316891
244 //cout << geohash(120.677252, 31.316891) << " 精品酒店" << endl;
245 //cout << geohash(120.674144, 31.316012) << " 星海实验中学" << endl;
246 // cout<< geohash(120.648933, 31.374867) << " 相称去政府" <<endl;
247 //cout << geohash(120.683958, 31.391834) << " 我的位置" <<endl;
248
249 /*cout<<"111001001100011111101011100011000010110000010001010001000100";*/
250 ////double a = 90.0;
251 //string s=geohash_w_bin(104.031601, -180, 180, 1,30);
252 //reverse(s.begin(), s.end());
253 //cout << s<<endl;
254 ////cout << "101010111001001000100101101010";
255 ////cout << "110010011111101001100000000000";
256
257 getchar();
258 return 0;
259 }
View Code
最后希望自己踏实学习算法。一张纸叠n次可以比天高,而n张纸叠在一起就不一定了。
原文链接: https://www.cnblogs.com/sundy-lee/p/4936839.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/224080
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!