VBGood网站全文搜索 Google

搜索VBGood全站网页(全文搜索)

VB爱好者乐园(VBGood)

 找回密码
 立即注册
搜索
查看: 3498|回复: 6

[经验技巧] 用二叉平衡搜索树实现的汉字转拼音代码

[复制链接]
 楼主| 发表于 2010-6-29 11:38:18 | 显示全部楼层 |阅读模式
本帖最后由 nighthk3 于 2010-6-29 12:10 编辑

本程序用链式存储结构实现了二叉平衡搜索树,并通过二叉搜索树反查汉字拼音,汉字匹配时采用了基于码表的中文分词法提高多音字准确率,由于本程序除了初始化外,完全抛弃了Api,所以查找速度很快

附件中的代码中用到了指针技术,关于VB中指针的使用可以参考http://blog.csdn.net/AdamBear/category/11152.aspx

VB中指针的定义的一般形式

  1. Dim Ptr(0) as Long
  2. Dim pPtr as Long
  3. Dim pPtrSave as Long

  4. ' 定义
  5. CopyMemory pPtr, ByVal VarPtrArray(Ptr), 4
  6. pPtr = pPtr + 12
  7. pPtrSave = VarPtr(Ptr(0))
  8. CopyMemory ByVal pPtr, VarPtr(DataType), 4
复制代码
经过上面的定义后可以称Ptr(0)为DataType型变量的指针,当退出程序时必须恢复数组Ptr(0)的pvData指针,否则程序会出错.

  1. ' 恢复
  2. CopyMemory ByVal pPtr, pPtrSave, 4
复制代码
有一点需要说明一下,结构体变量是变量而不是指针,为了在VB中轻松的移动结构体变量的指针需要定义一个指向结构体变量的指针的指针:
设node(0)为某结构体类型tNode的变量,现在要将nodePtr(0)定义为指向tNode类型指针的指针

  1. Dim node(0) As tNode
  2. Dim pNode As Long
  3. Dim pNodeSave As Long

  4. Dim nodePtr(0) As Long
  5. Dim pNodePtr As Long
  6. Dim pNodePtrSave As Long

  7. ' 定义
  8. CopyMemory pNode, ByVal VarPtrArray(node), 4
  9. pNode = pNode + 12
  10.    
  11. CopyMemory pNodePtr, ByVal VarPtrArray(nodePtr), 4
  12. pNodePtr = pNodePtr + 12
  13. pNodePtrSave = VarPtr(nodePtr(0))
  14. CopyMemory ByVal pNodePtr, pNode, 4
  15. pNodeSave = nodePtr(0)

  16. ' 恢复
  17. nodePtr(0) = pNodeSave
  18. CopyMemory ByVal pNodePtr, pNodePtrSave, 4
复制代码
经过如上定义以后可以在程序中完全抛弃缓慢的CopyMemory,从而像在C/C++中一样轻松的使用指针。

本程序中的内存分配比较特殊,使用了字符串函数Space$(),由于VB内部使用的是unicode,所以长度为3的字符串实际占用内存为6

当内存分配好以后,只要把结构体类型变量的指针指向如上地址就可以用结构体变量访问这段内存了,下面给一段例子:

  1. Private Type tNode
  2.     a As Long
  3.     b As Long
  4. End Type

  5. ' 字符串变量
  6. Dim Malloc As String

  7. ' 字符串变量指针
  8. Private MallocPtr(0) As Long
  9. Private pMallocPtr As Long
  10. Private pMallocPtrSave As Long

  11. ' tNode结构体类型指针
  12. Private node(0) As tNode
  13. Private pNode As Long
  14. Private pNodeSave As Long

  15. ' tNode结构体类型指针的指针
  16. Private nodePtr(0) As Long
  17. Private pNodePtr As Long
  18. Private pNodePtrSave As Long

  19. ' 字符串指针定义
  20. CopyMemory pMallocPtr, ByVal VarPtrArray(MallocPtr), 4
  21. pMallocPtr = pMallocPtr + 12
  22. pMallocPtrSave = VarPtr(MallocPtr(0))
  23. CopyMemory ByVal pMallocPtr, VarPtr(Malloc), 4

  24. ' tNode类型指针以及指针的指针的定义
  25. CopyMemory pNode, ByVal VarPtrArray(node), 4
  26. pNode = pNode + 12
  27.    
  28. CopyMemory pNodePtr, ByVal VarPtrArray(nodePtr), 4
  29. pNodePtr = pNodePtr + 12
  30. pNodePtrSave = VarPtr(nodePtr(0))
  31. CopyMemory ByVal pNodePtr, pNode, 4
  32. pNodeSave = nodePtr(0)

  33. ' 实际使用
  34. Malloc = Space$(Len(node(0)/2)
  35. nodePtr(0) = MallocPtr(0)
  36. node(0).a = 78
  37. node(0).b = 45

  38. ' 用Debug.Print查看变量地址,看看发生了什么?
  39. Debug.Print StrPtr(Malloc), VarPtr(node(0))

  40. ' 当分配下一个地址时字符串变量指针要设置为NULL,想想为什么呢?
  41. MallocPtr(0) = 0

  42. ' 恢复
  43. MallocPtr(0) = nodePtr(0)
  44. Malloc = VbNullString              ' 这是释放内存的方法

  45. CopyMemory ByVal pMallocPtr, pMallocPtrSave, 4
  46.    
  47. nodePtr(0) = pNodeSave
  48. CopyMemory ByVal pNodePtr, pNodePtrSave, 4

复制代码
上面的代码仅适用于结构体中不包含字符变量的情况,如果要包含字符串变量就要作一些修改。

详细的就看的附件吧

忘了说一下,程序第一次使用时要先整理拼音码表,这个过程比较慢,请耐心等待,第二次使用就以载入生成的码表,速度快多了,如果想要把拼音码表编译到Exe中的话可以先生成unicode的码表,然后添加到自定义资源文件中

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

评分

参与人数 2威望 +2 人气 +1 收起 理由
gujin162 + 1 + 1 发布源码
drogan12 + 1

查看全部评分

发表于 2010-6-29 11:44:20 | 显示全部楼层
我正在找这个。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-6-29 11:48:07 | 显示全部楼层
关于VB的动态内存分配方法大概有三种:API法(Api类型库IMalloc接口)、数组法 Dim a as Byte():Redim a(n)、字符串函数法 Space$(), String$()

我经过测试发现Space$()的速度最快,其次是API法,Redim最慢
回复 支持 反对

使用道具 举报

发表于 2010-6-29 15:05:31 | 显示全部楼层
你这个如果要查找的数据是完全静态的数据的话,不如预先排序了,直接用二分搜索,这样程序代码短了不少,而且速度和BST的速度差不多……

不过AVL树的代码倒是可以参考一下(我这里数据结构的书里面也有)……
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-6-29 22:16:29 | 显示全部楼层
数据是静态的话二分法也是比较不错的方法,二分法和BST的速度主要差在二分法还要不断进行算术运算,如果需要动态插入数据的话二分法就不适合了, 例如我在程序中添加插入自定义词组以纠正多音字准确率的功能,AVL树的效率这时就体现出来了。
回复 支持 反对

使用道具 举报

发表于 2010-6-30 01:03:35 | 显示全部楼层
5# nighthk3

你编译是开启所有高级优化选项,那个“\2”就会自动变成右移位……
回复 支持 反对

使用道具 举报

头像被屏蔽
发表于 2010-7-2 12:52:20 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

文字版|手机版|小黑屋|VBGood  

GMT+8, 2022-7-4 23:20

VB爱好者乐园(VBGood)
快速回复 返回顶部 返回列表