数据结构:BM算法

设计思路

BM算法是一种后缀匹配算法,其具有比KMP算法更优秀的性能表现.其核心思想有二
,第一是坏字符,坏字符就是pattern与text从右往左第一失配的在text中的字符,
二是好后缀,好后缀就是pattern与text从右往左连续匹配成功的子串.对于坏字符
和好后缀,有各自的模式串移动规则,可以确定各自失配时需要移动的位数,最终选
择二者中移动位数较大者移动.在主函数中,让用户输入文档名与需要查找的单词.
每次从文档中读取一行进行匹配搜索,每次使用BM算法搜索完成后,若搜索到单词,
则将主串中开始匹配的位置定为查找到单词的下一行,使用BM算法进行下一个匹配
搜索,直至搜索完当前行.而后循环直至匹配完整个文档.

阅读更多

数据结构:迷宫问题

设计思路

图编号

图编号
如图所示,从上到下,从左到右,给17个顶点进行编号,以两个顶点代表一条边,例入2-3代表可以从顶点2走到顶点3。问题即为求解从2 -> 17的通路。

求解思想

求解一条通路,应当从起点出发,不断前进到后续可行顶点,当在一个顶点无法继续前进时,则回退到上一个顶点,寻找其他可行顶点,直到到达终点。此思想符合数据结构栈的特点。首先将起点压栈,然后将从当前顶点可到达的一个顶点压栈,然后将该顶点标记为已访问,随后到达下一个顶点,在某个顶点无法继续走通时,将当前顶点出栈,回退到上一个顶点重新选择可以到达的且未访问的顶点。如此循环,直到终点被压入栈中,此时栈中所有顶点即为一条通路。

求解一条最短路径,应当从起点出发,访问所有可以到达的下一级顶点。再从所有下一级顶点出发,访问所有可访问的再下一级顶点,如此循环,每一级顶点距起点距离相同。过程中记录路线。此想法符合数据结构中队列的特点。首先,将起点入队。然后将队头元素出队,将该元素可访问到的且未被访问的顶点置为已访问,然后入队,注意记录被入队节点的前一个节点。直到队列为空。最后顺着终点的前驱顶点输出即可得到路线。若有多个终点,要寻找到最近的终点出去,则将结束循环条件改为有终点入队即可。

阅读更多
Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×