




下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、重庆大学根底性实践环节实践报告实践课程名称数据结构开课实验室数统学院LD104学院数统学院年级2021级专业班理科实验班数学类01学生姓名学号开课时间2021至2021学年第一学期总成绩教师签名数统学院制课程名称数据结构实验题目用的根本操作与KMP心匹配算法实践目的掌握用的操作实践环境C+算法描述1 .米用堆分配存储与表示串2 .串的连接3 .串的截取4 .next数组记录失配后重新比拟的位置#include<stdio.h>#include<stdlib.h># defineTRUE1# defineFALSE0# defineOK1# defineERROR0# d
2、efineINFEASIBLE-1# defineOVERFLOW-2# defineMAXQSIZE5/Status是函数的类型,其值是函数结果状态码typedefintStatus;typedefstructchar*ch;/假设是非空用,那么按用长分配存储区,否那么ch为NULLintlength;/字符串长度HString;/生成一个其值等于用常量chars的用TStatusStrAssign(HString&S,char*chars)inti;for(i=0;charsi;i+).if(S.ch)/free(S.ch);/S.ch=NULL;/)if(!i)S.ch=NULL
3、;S.length=0;elseS.ch=(char*)malloc(i*sizeof(char);/i?if(!S.ch)exit(OVERFLOW);S.length=i;for(intj=0;j<i;j+)S.chj=charsj;returnOK;/返回用长度ntStrLength(HString&S)returnS.length;/比拟大小,假设S>T返回值>0.相等返回0,否那么返回<0ntStrCompare(HStringS,HStringT)for(inti=0;i<S.length&&i<T.length;i+)i
4、f(S.chi!=T.chi)returnS.chi-T.chi;returnS.length-T.length;/return?/清空用S为空用,并释放所占空间StatusClearString(HString&S)if(S.ch)free(S.ch);S.ch=NULL;S.length=0;returnOK;/连接两个字符串,生成一个新的字符串StatusConcat(HString&T,HStringS1,HStringS2)/if(T.ch)free(T.ch);T.ch=(char*)malloc(S1.length+S2.length)*sizeof(char);
5、if(!T.ch)exit(OVERFLOW);T.length=S1.length+S2.length;for(inti=0;i<S1.length;i+)T.chi=S1.chi;for(i=0;i<S2.length;i+)T.chi+S1.length=S2.chi;returnOK;/字符串截取,返回截取的申StatusSubString(HString&sub,HStringS,intpos,intlen)if(pos<1|pos>S.length|len<0|(S.length-pos+1)<len)returnERROR;/if(su
6、b.ch)free(sub.ch);sub.ch=(char*)malloc(len*sizeof(char);if(!sub.ch)exit(OVERFLOW);for(inti=0;i<len;i+)sub.chi=S.chi+pos-1;sub.length=len;returnOK;/*StatusIndexString(Hstring&S,Hstring&T)if(T.length>S.length)returnERROR;elsefor(i=0;i<S.length;i+)for(j=0;j<T.length;j+)S.chi+j=T.chj
7、;7voidget_next(HString&T,int*next)inti,j;i=1;j=0;next1=0;while(i<T.length)if(j=0|T.chi-1=T.chj-1)i+;j+;nexti=j;else/假设字符不相同,那么j值回溯j=nextj;printf("模式用的nex数组:n");for(i=1;i<=T.length;i+)printf("next%d=%dn",i,nexti);voidget_next1(HString&T,int*next1)inti,j;i=1;j=0;next1
8、1=0;while(i<T.length)if(j=0|T.chi-1=T.ch-1)i+;j+;if(T.chi-1!=T.chj-1)next1i=j;elsenext1i=next1j;else/假设字符不相同,那么j值回溯j=next1j;for(i=1;i<=T.length;i+)printf("next1%d=%dn",i,next1i);StatusIndex_KMP(HString&S,HString&T)inti=1;/j用于子用T中当前位置下标值intj=1;定义next数组intnext255;对用T作分析,得到next数
9、组get_next(T,next);/假设i小于S的长度且j小于T的长度时,循环继续while(i<=S.length&&j<=T.length)/两字母相等那么继续,相对于朴素算法增加了/j=0判断if(j=0|S.chi-1=T.chj-1)i+;j+;/指针后退重新开始匹配else/j退回适宜的位置,i值不变j=nextj;if(j>T.length)returni-T.length;elsereturn0;voidprintV(HString&S)for(inti=0;i<S.length;i+)printf("地址:%p,&q
10、uot;心S.chi);printf("值:%cn",S.chi);voidprints(HString&S)for(inti=0;i<S.length;i+)printf("%c",S.chi);printf("%sn","");voidmain()HStringS1,S2;char*c1,*c2;charstr150,str250;intx,k;截取请按2n模式匹printf("用的操作应用:n连接请按1配(KMP)请按3n");scanf("%d",&am
11、p;x);if(x=1)printf("请输入第一个字符串S1:n");scanf("%s",str1);c1=str1;printf("请输入第二个字符串S2:n");scanf("%s",str2);c2=str2;StrAssign(S1,c1);StrAssign(S2,c2);HStringT;Concat(T,S1,S2);printf("%s","T:");prints(T);elseif(x=2)intm;intn;printf("请输字符串T:n&
12、quot;);scanf("%s",str1);c1=str1;printf("请输入截取的初始位置m:n");scanf("%d",&m);printf("请输入截取的长度n:n");scanf("%d",&n);/ClearString(S1);StrAssign(S1,c1);HStringsub;SubString(sub,S1,m,n);if(SubString(sub,S1,m,n)=0)printf("ERROR'n");elseprin
13、tf("子用:");prints(sub);elseif(x=3)printf("请输入主用S1:n");scanf("%s",str1);c1=str1;printf("请输入模式用S2:n");scanf("%s",str2);c2=str2;intnext20;/intnext120;StrAssign(S1,c1);StrAssign(S2,c2);k=Index_KMP(S1,S2);if(k=0)printf("不匹配n");elseprintf("匹配
14、开始位置:%dn",k);/*ClearString(SI);c="hell"StrAssign(S1,c);printf("%s","S1:");prints(S1);printV(S1);HStringS2;c="China"StrAssign(S2,c);printf("%s","S2:");prints(S2);printV(S2);HStringT;Concat(T,S1,S2);printf("%s","T:");
15、prints(T);printV(T);HStringsub;SubString(sub,T,1,3);printf("%s","sub:");prints(sub);printV(sub);*/1 .用的连接:截取请按2串的操作应用;连接请按1模式即配附请按31请输入第一个字符串SLfw4gff2运行结果请输入第:个字符串S2:4535gfdfdT:fw4gff24535gfdfdPressanykeytocontinue.2 .截取:I串的操作应用;连接请按1截取请按2模式匹配(KMP)请按32请输字符串T:ygyugyng清输入假取的初始位置叱2请输入低取的长度n:6于串:gyugyuPressanykeytocontinue3 .KMP模式匹配;不匹配:连接请按1截取请旅膜式匹配(KMP)请按33请输入主串Shfghvhgv43bJ23
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 综合解析人教版八年级上册物理物态变化《温度》专项测试试题(解析卷)
- 2025年手表质量安全专项考核试卷
- 2025年花生病毒病绿色防控技术考核试卷
- 解析卷人教版八年级物理上册第6章质量与密度-质量单元测评试卷(含答案详解版)
- 入境旅游服务失误归因与补救考核试卷
- 考点解析-人教版八年级物理上册第4章光现象-光的色散专项训练试卷(附答案详解)
- 明理:感受探索之乐为思维插上翅膀
- 考点解析-人教版八年级物理上册第5章透镜及其应用-生活中的透镜章节测试试卷(含答案详解)
- 解析卷-人教版八年级物理上册第5章透镜及其应用-透镜同步测试练习题(含答案解析)
- 2025年建筑工程验收标准合同协议
- 2025-2026学年西师大版(2024)小学数学二年级上册(全册)教学设计(附教材目录P234)
- 2025昭通市盐津县公安局警务辅助人员招聘(14人)备考考试题库附答案解析
- 自动扶梯施工方案编制
- 2.2运动与相互作用(第2课时二力平衡)学案-八年级科学浙教版上册
- 第一单元第二课《表现形式》课件人教版初中美术七年级上册
- 一例甲状腺癌患者的护理查房 2
- 国开2025年《行政领导学》形考作业1-4答案
- 第8课《网络新世界》第一课时-统编版《道德与法治》四年级上册教学课件
- 具身智能在智能工厂生产流程中的应用可行性分析
- 餐饮连锁品牌营销推广策略案例分析
- 新能源车电机热管理技术进展
评论
0/150
提交评论