100分 求最优算法根据地址反查行政区代码 (面试题之一.)
110000北京市
110100北京市市辖区
110101北京市东城区
110102北京市西城区
110103北京市崇文区
110104北京市宣武区
110105北京市朝阳区
110106北京市丰台区
110107北京市石景山区
110108北京市海淀区
110109北京市门头沟区
110111北京市房山区
110112北京市通州区
....略
120000天津市
120100天津市市辖区
120101天津市和平区
120221天津市宁河县
120223天津市静海县
120225天津市蓟县
130000河北省
130100河北省石家庄市
130101河北省石家庄市市辖区
....
130107河北省石家庄市井陉矿区
130108河北省石家庄市裕华区
130121河北省井陉县
.....
==========================
大概4000多行
以上是地址行政区代码文件

要求用 C# Framework 2.0
根据客户提供的地址 找到行政区编码

例 地址：北京市朝阳区南湖南路15号院甲1号 应返回 110105


要求效率最高的一种方法

行政区文件 可以导入数据库 也可以导成 XML 或者就普通文本

请大家支个招...














[解决办法]
生成树.

然后把地址拆分试探.
[解决办法]
Dictionary<string, string> dict = new Dictionary<string, string>();

var ret = from kp in dict where "北京市朝阳区南湖南路15号院甲1号".IndexOf(kp.Key)> 0 select kp;

效率不是最高 但代码最少的方法
[解决办法]
假设是查行政区代码的话，那么就从左向右查是最快的。比如只要是有“北”开头的行政区，那么就不可能再去考虑从“京”这个字以后的任何字符开始查找了。而从“北”开头的行政区中有几个与这个字符串相匹配，实际上很容易找到，你保留字符最多的一个行政区作为结果就行了。

这有一个数据结构的问题，就是假设先把4000行数据创建为单字的“倒排序”全文检索索引树，那么就可以非常快地搜索到。

[解决办法]
在数据库中 select top 1 code
from mytable
where '北京市朝阳区南湖南路15号院甲1号'
like name +"%"
order by name desc
[解决办法]
楼主,把这些放在数据库中处理吧,别说4000条数据,
我做了个测试,七百万条数据(大小400兆),不需要任何索引,1秒钟之内搞定:
(这个sql算法如果再稍加优化,还能应付上亿级的数据)

SQL code

--比如说:Create table t2(Code1 CHAR(6),Code2 NVARCHAR(50);DECLARE @se NVARCHAR(100);SET @se=N'北京市朝阳区南湖南路15号院甲1号';SELECT * FROM(    SELECT * FROM t2    WHERE left(Code2,3)= LEFT(@se,3)) tWHERE Code2=left(@se,len(Code2));