实验---数据结构中字符串的匹配问题
2018-06-17 23:36:24来源:未知 阅读 ()
【问题描述】对任意输入的一串字符,在某文档中进行匹配,并给出匹配结果。
【测试数据】
(1)输入的一行程序,与源代码匹配,源程序自行选择;
(2)输入的一串字符,在某文本文件中匹配,文本文件自行选择。
#include <stdio.h> #include "stdlib.h" #include <iostream> #include<fstream> using namespace std; //宏定义 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define MAXSTRLEN 100 typedef char SString[MAXSTRLEN + 1]; /* *************** ** 字符串的匹配 ** @autho 刘辉 ** @time 2016年11月7日 *************** */ int length(SString S) //计算字符数组的长度 { int i=0; while(S[i]!='\0') i++; return i; } /* *********************************************************************** 存放长度change() 1、将字符串的长度存到字符数组的第一个字符位 2、不能返回一个字符数组,定义一个字符指针指向数组,返回指针 3、注意的是长度的类型是int ,这里存到字符数组中之后会进行自动转码 但如果要使用的时候要进行强制类型转化 4、这里我设置的字符数组的长度没有加上首字符的空间 *********************************************************************** */ char *change(SString S) //将字符的长度存到字符数组的第一个字符位S[0] { int i = 0; char *p; for(i=length(S);i>=0;i--) S[i+1] = S[i]; S[0] = length(S)-1; p = S; return p; } /* *********************************************************************** 算法的实现 index__BF() 1、BF算法,匹配两个字符串,并返回匹配的字符串首字母所在位置 2、这里参数传递进来的方式是,主函数通过字符指针传递给函数的字符数组接收 3、这里要注意判断条件时的强制类型转换 4、要注意最后的判断条件,长度减一后使用 *********************************************************************** */ int index__BF(SString S,SString T, int pos) //BF算法,匹配两个字符串,并返回匹配的字符串首字母所在位置 { if (pos <1 || pos > (int)S[0] ) return 0; int i = pos, j =1; while (i<= (int)S[0]&& j <= (int)T[0]) { if (S[i] == T[j]) { ++i; ++j; } else { i = i-j+ 2; j = 1; } } if(j > (int)T[0]) return (i - (int)T[0]); return 0; } /* ************************************************************************ 求子串next[i]值的算法 1、注意算法的使用 2、这里的if句内包含了很多巧合的实现 /************************************************************************/ void GetNext(SString T, int next[]) { int j = 1, k = 0; next[1] = 0; while(j < (int)T[0]){ if(k == 0 || T[j]==T[k]) { ++j; ++k; next[j] = k; } else { k = next[k]; } } } /* *************** KMP算法的具体实现 *************** */ int KMPindex(SString S, SString T, int pos) { if (pos <1 || pos > (int)S[0] ) exit(ERROR); int i = pos, j =1; int next[MAXSTRLEN]; GetNext( T, next); while (i<= (int)S[0] && j <= (int)T[0]) { if (S[i] == T[j]||j==0) { ++i; ++j; } else { j = next[j]; } } if(j > (int)T[0]) return i - (int)T[0]; return ERROR; } /* ******************************************************* 主函数main() 1、以字符数组保存 2、然后建立指针指向经过change()后的数组。 3、再建立字符数组存放指针指向的内容 4、用数组参与到BF算法中 ****************************************************** */ void main(){ SString S = "abcacdbadab"; //或者用SString S = {'a','b','c','a','c','d','b','a','d','a','b'}; SString S3; int i = 0; ifstream in("d:/test.txt"); //文件流读取文件内的字符串 if(!in) { cout<<"open file error!"<<endl; } while(in) //循环读取数据 { in.get(S3[i]); i++; } in.close(); S3[i] = '\0'; SString T ; cout<<"请输入要匹配的字符串:"; cin>>T; int pos = 0,pos1 = 0,pos2 = 0; char *p = change(S); char *q = change(T); char *k = change(S3); SString S1,S2,S4; for(int i=0;i<length(S)+1;i++) S1[i] = p[i]; for(int i=0;i<length(T)+1;i++) S2[i] = q[i]; for(int i=0;i<length(S3)+1;i++) S4[i] = k[i]; pos = index__BF( S1, S2, 1); pos1 = KMPindex( S1, S2, 1); pos2 = KMPindex( S3, S2, 1); cout<<"Pos:"<<pos<<endl; cout<<"Pos1:"<<pos1<<endl; cout<<"Pos2:"<<pos2<<endl; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:Codevs 1860 最大数
- 数据结构—链表 2020-05-29
- 图 2020-05-02
- 【数据结构】树套树——线段树套平衡树 2020-04-18
- 数据结构之顺序表的实现 2020-04-06
- 数据结构-线性表 2020-03-28
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash