C语言数据结构中串的模式匹配

C语言数据结构中串的模式匹配

串的模式匹配问题:朴素算法与KMP算法

#include<stdio.h>
#include<string.h>
int Index(char *S,char *T,int pos){
//返回字串T在主串S中第pos个字符之后的位置。若不存在,则函数值为0.
//其中,T非空,1<=pos<=StrLength(s).
int i=pos;
int j=1;
while(i<=S[0]&&j<=T[0]){
    if(S[i]==T[j]){++i;++j;}
    else{i=i-j+2;j=1;}
}
if(j>T[0]) return i-T[0];
else return 0;
}
int get_next(char *T,int next[]){
//求模式串T的next函数值并存入数组next。
int i=1;next[1]=0;int j=0;
while(i<T[0]){
    if (j==0||T[i]==T[j]){++i;++j;next[i]=j;}
else j=next[j];
}
return *next;
}
int Index_KMP(char *S,char *T,int pos){
//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法,其中T非空,1<=pos<=StrLength(S).
int next[100];
*next=get_next(T,next);
int j=1,i=pos;
while(i<=S[0]&&j<=T[0]){
    if(j==0||S[i]==T[j]){++i;++j;}
    else j=next[j];
}
if(j>T[0]) return i-T[0];
else return 0;
}
void main()
{
int id,j,k,i,a;
printf("输入主串、子串和匹配起始位置\n");
char A[20];char B[10];
printf("请输入主字串内容\n");
    gets(A+1);
    *A=strlen(A+1);
printf("请输入子字串内容\n");
    gets(B+1);
    *B=strlen(B+1);
printf("请输匹配起始位置\n");
    scanf("%d",&j);
//printf("%d ",k);
    do{
       printf("\n请输入您需要的任务的序号");
       printf("\n1:朴素的模式匹配算法");
       printf("\n2:快速模式匹配算法");
       printf("\n3:退出\n");
       scanf("%d",&id);
    switch(id){
       case 1:
           {printf("\n\n你调用了功能1:");
           printf("\n朴素的模式匹配算法");
           k=Index(A,B,j);
           printf("\n该位置为:");
           printf("%d\n",k);
           break;}
       case 2:
           {printf("\n\n你调用了功能2:");
              printf("\n 快速模式匹配算法");
              a=Index_KMP(A,B,j);
              printf("\n该位置为:");
              printf("%d\n",a);
              break;}
       case 3:
           {printf("\n\n你调用了功能3:");
              printf("\n退出\n");
              }
    }
       }while(id!=3);
#include<stdio.h>
#include<string.h>
int Index(char *S,char *T,int pos){
//返回字串T在主串S中第pos个字符之后的位置。若不存在,则函数值为0.
//其中,T非空,1<=pos<=StrLength(s).
int i=pos;
int j=1;
while(i<=S[0]&&j<=T[0]){
    if(S[i]==T[j]){++i;++j;}
    else{i=i-j+2;j=1;}
}
if(j>T[0]) return i-T[0];
else return 0;
}
int get_next(char *T,int next[]){
//求模式串T的next函数值并存入数组next。
int i=1;next[1]=0;int j=0;
while(i<T[0]){
    if (j==0||T[i]==T[j]){++i;++j;next[i]=j;}
else j=next[j];
}
return *next;
}
int Index_KMP(char *S,char *T,int pos){
//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法,其中T非空,1<=pos<=StrLength(S).
int next[100];
*next=get_next(T,next);
int j=1,i=pos;
while(i<=S[0]&&j<=T[0]){
    if(j==0||S[i]==T[j]){++i;++j;}
    else j=next[j];
}
if(j>T[0]) return i-T[0];
else return 0;
}
void main()
{
int id,j,k,i,a;
printf("输入主串、子串和匹配起始位置\n");
char A[20];char B[10];
printf("请输入主字串内容\n");
    gets(A+1);
    *A=strlen(A+1);
printf("请输入子字串内容\n");
    gets(B+1);
    *B=strlen(B+1);
printf("请输匹配起始位置\n");
    scanf("%d",&j);
//printf("%d ",k);
    do{
       printf("\n请输入您需要的任务的序号");
       printf("\n1:朴素的模式匹配算法");
       printf("\n2:快速模式匹配算法");
       printf("\n3:退出\n");
       scanf("%d",&id);
    switch(id){
       case 1:
           {printf("\n\n你调用了功能1:");
           printf("\n朴素的模式匹配算法");
           k=Index(A,B,j);
           printf("\n该位置为:");
           printf("%d\n",k);
           break;}
       case 2:
           {printf("\n\n你调用了功能2:");
              printf("\n 快速模式匹配算法");
              a=Index_KMP(A,B,j);
              printf("\n该位置为:");
              printf("%d\n",a);
              break;}
       case 3:
           {printf("\n\n你调用了功能3:");
              printf("\n退出\n");
              }
    }
       }while(id!=3);

}

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

(0)

相关推荐

  • C语言数据结构之动态分配实现串

    C语言数据结构之动态分配实现串 说明:堆分配存储实现串时,串并不是以'\0', 而是用数据项int length来表示的,所以和传统的c语言操作字符串有所不同. 头文件 #ifndef PILEHEAD_H_INCLUDED #define PILEHEAD_H_INCLUDED #include <stdio.h> #include <stdlib.h> typedef struct { char* ch ; int len ; }HString ; int StrAssign(

  • C数据结构中串简单实例

    C数据结构中串简单实例 运行截图: 实例代码: #include "stdio.h" #include "string.h" #include "stdlib.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 40 /* 存储空间初始分配量 */ typedef int Status; /* Status是函数的类型,其值是函数结果状态代码

  • JavaScript数据结构中串的表示与应用实例

    本文实例讲述了JavaScript数据结构中串的表示与应用.分享给大家供大家参考,具体如下: 类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列.下面我们以串联接为例,讲解一下这种存储结构时串的操作.JavaScript自带有concat方法,该方法返回字符串值,该值包含了两个或多个提供的字符串的连接. 其实思路很简单,就是将第二个串拼接在第一个串后面,代码如下 <!DOCTYPE html> <html> <head> <meta chars

  • C语言数据结构实现字符串分割的实例

    C语言数据结构实现字符串分割的实例 以下为"字符串分割"的简单示例: 1. 用c语言实现的版本 #include<stdio.h> /* 根据空格分隔字符串 */ int partition(char *src, char *par, int pos) { int i,j; i = pos; //取到第一个非空格字符 while(src[i] == ' ') { ++i; } if(src[i] != '\0') { j = 0; while((src[i] != '\0'

  • C语言数据结构之模式匹配字符串定位问题

    C语言数据结构之模式匹配字符串定位问题 主要实现了三种字符串的模式匹配,主要包括字符串子操作的集合,字符串指针回溯,和KMP算法 头文件  #ifndef INDEXHEAD_H_INCLUDED #define INDEXHEAD_H_INCLUDED #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXLEN 255 typedef char Sstring[MAXLEN + 1

  • C语言实现数据结构串(堆分配存储表示法)实例详解

    堆分配存储表示法 存储结构: 构建堆来存储字符串,本质上是顺序表 实现代码: #include <stdio.h> #include <stdlib.h> #include <string.h> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define OVERFLOW -2 #define STR_INIT_SIZE 100 #define STRINCREMENT 10 typedef i

  • 数据结构基本概念和术语之位字节、字、位串、元素等

    数据结构基本概念和术语:位.字节.字.位串.元素.数据域.物理结构.逻辑结构 位(Bit):"位(bit)"是电子计算机中最小的数据单位.每一位的状态只能是0或1. 字节(Byte):8个二进制位构成1个"字节(Byte)",它是存储空间的基本计量单位.1个字节可以储存1个英文字母或者半个汉字,换句话说,1个汉字占据2个字节的存储空间. 字:"字"由若干个字节构成,字的位数叫做字长,不同档次的机器有不同的字长.例如一台8位机,它的1个字就等于1个

  • C++语言数据结构 串的基本操作实例代码

    C语言数据结构 串的基本操作实例代码 输出结果: 实现代码: #include<iostream> using namespace std; typedef int Status; #define Max 20 #define OK 1 #define ERROR 0 #define OVERLOE -2 typedef struct//堆分配表示串 { char *ch; int length; }HString; //====================================

  • C语言数据结构中串的模式匹配

    C语言数据结构中串的模式匹配 串的模式匹配问题:朴素算法与KMP算法 #include<stdio.h> #include<string.h> int Index(char *S,char *T,int pos){ //返回字串T在主串S中第pos个字符之后的位置.若不存在,则函数值为0. //其中,T非空,1<=pos<=StrLength(s). int i=pos; int j=1; while(i<=S[0]&&j<=T[0]){ i

  • C语言数据结构中约瑟夫环问题探究

    目录 问题描述 基本要求 测试数据 实现思路1 实现思路2 结果 数据结构开讲啦!!! 本专栏包括: 抽象数据类型 线性表及其应用 栈和队列及其应用 串及其应用 数组和广义表 树.图及其应用 存储管理.查找和排序 将从简单的抽象数据类型出发,深入浅出地讲解复数 到第二讲线性表及其应用中会讲解,运动会分数统计,约瑟夫环,集合的并.交和差运算,一元稀疏多项式计算器 到最后一步一步学会利用数据结构和算法知识独立完成校园导航咨询的程序. 希望我们在学习的过程中一起见证彼此的成长. 问题描述 约瑟夫环问题

  • C语言数据结构中二分查找递归非递归实现并分析

    C语言数据结构中二分查找递归非递归实现并分析 前言: 二分查找在有序数列的查找过程中算法复杂度低,并且效率很高.因此较为受我们追捧.其实二分查找算法,是一个很经典的算法.但是呢,又容易写错.因为总是考虑不全边界问题. 用非递归简单分析一下,在编写过程中,如果编写的是以下的代码: #include<iostream> #include<assert.h> using namespace std; int binaty_search(int* arr, size_t n, int x)

  • C语言 数据结构中求解迷宫问题实现方法

    C语言 数据结构中求解迷宫问题实现方法 在学习数据结构栈的这一节遇到了求迷宫这个问题,拿来分享一下~ 首先求迷宫问题通常用的是"穷举求解" 即从入口出发,顺某一方向试探,若能走通,则继续往前走,否则原路返回,换另一个方向继续试探,直至走出去. 我们可以先建立一个8*8的迷宫其中最外侧为1的是墙 int mg[M+2][N+2]={ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,

  • C语言数据结构中数制转换实例代码

    C语言数据结构中数制转换实例代码 数制转换是严蔚敏的数据结构那本书中的例子,但是那本书中的例子大都是用伪代码的形式写的,不是很容易理解和实现,对初学者造成了不小的困扰,在这里我们将其详尽的实现出来,以便初学者调试和运行,并从中有所收获. #include <stdlib.h> #include <stdio.h> #include<malloc.h> #define STACK_INIT_SIZE 10 //定义最初申请的内存的大小 #define STACK_INCR

  • C语言数据结构中堆排序的分析总结

    目录 一.本章重点 二.堆 2.1堆的介绍(三点) 2.2向上调整 2.3向下调整 2.4建堆(两种方式) 三.堆排序 一.本章重点 堆 向上调整 向下调整 堆排序 二.堆 2.1堆的介绍(三点) 1.物理结构是数组 2.逻辑结构是完全二叉树 3.大堆:所有的父亲节点都大于等于孩子节点,小堆:所有的父亲节点都小于等于孩子节点. 2.2向上调整 概念:有一个小/大堆,在数组最后插入一个元素,通过向上调整,使得该堆还是小/大堆. 使用条件:数组前n-1个元素构成一个堆. 以大堆为例: 逻辑实现: 将

  • C语言数据结构中树与森林专项详解

    目录 树的存储结构 树的逻辑结构 双亲表示法(顺序存储) 孩字表示法(顺序+链式存储) 孩子兄弟表示法(链式存储) 森林 树的遍历 树的先根遍历(深度优先遍历) 树的后根遍历(树的深度优先遍历) 树的层序遍历(广度优先遍历) 森林的遍历 先序遍历森林 中序遍历森林 树的存储结构 树的逻辑结构 树是n(n≥0)个结点的有限集合,n=0时,称为空树,这是一种特殊情况.在任意--棵非空树中应满足: 1)有且仅有一个特定的称为根的结点. 2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集合T

  • C语言数据结构中定位函数Index的使用方法

    数据结构中定位函数Index的使用方法 实现代码: #include<stdio.h> #include<string.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 40 //最大字符串 typedef int Status; typedef char SString[MAXSIZE+1]; //此处声明的SString[

随机推荐