數(shù)據(jù)結(jié)構(gòu)實驗報告串

1、實驗四串【實驗目的】1、掌握串的存儲表示及基本操作；2、掌握串的兩種模式匹配算法：BF 和 KMP。3、了解串的應用。【實驗學時】2 學時【實驗預習】回答以下問題：1、串和子串的定義串的定義：串是由零個或多個任意字符組成的有限序列。子串的定義：串中任意連續(xù)字符組成的子序列稱為該串的子串。2、串的模式匹配串的模式匹配即子串定位是一種重要的串運算。設(shè)s 和 t 是給定的兩個串，從主串s的第 start個字符開始查找等于子串t 的過程稱為模式匹配， 如果在 S 中找到等于t 的子串，則稱匹配成功，函數(shù)返回t 在 s 中首次出現(xiàn)的存儲位置（或序號）；否則，匹配失敗，返回0。【實驗容和要求】1、按照要求

2、完成程序exp4_1.c ，實現(xiàn)串的相關(guān)操作。調(diào)試并運行如下測試數(shù)據(jù)給出運行結(jié)果：求“ This is a boy”的串長；比較” abc3”和“ abcde “； 表示空格比較” english”和“ student “；比較” abc ”和“ abc “；截取串” white ”，起始2，長度 2；截取串” white ”，起始1，長度 7；截取串” white ”，起始6，長度 2；連接串” asddffgh ”和” 12344”；#include<stdio.h>#include<string.h>#define MAXSIZE 100#define ERROR

3、 0#define OK 1/* 串的定長順序存儲表示 typedef struct */char dataMAXSIZE;int length; SqString;int strInit(SqString *s);/*int strCreate(SqString *s);/*int strLength(SqString *s);/*intstrCompare(SqString*s1,SqString*s2);int subString(SqString *sub,SqString *s,int pos,int len);int strConcat(SqString *t,SqString *

4、s1,SqString *s2);/*/*/*初始化串 */生成一個串 */求串的長度 */兩個串的比較*/求子串 */兩個串的連接*/* 初始化串 */int strInit(SqString *s)s->length=0;s->data0='0'return OK;/*strInit*/* 生成一個串 */int strCreate(SqString *s)printf("input string :");gets(s->data);s->length=strlen(s->data);return OK;/*strCreat

5、e*/* （ 1） - 求串的長度 */int strLength(SqString *s)return s->length;/*strLength*/* （ 2） - 兩個串的比較， S1>S2 返回 >0， s1<s2 返回 <0， s1=s2 返回 0*/ int strCompare(SqString *s1,SqString *s2) int i;for(i=0;i<s1->length&&i<s2->length;i+)if(s1->datai>s2->datai)return 1;if(s1-

6、>datai<s2->datai)return -1;return 0;/*strCompare*/* （ 3） - 求子串， sub 為返回的子串， pos 為子串的起始位置， len 為子串的長度 */ int subString(SqString *sub,SqString *s,int pos,int len)int i;if(pos<1|pos>s->length|len<0|len>s->length-pos+1)return ERROR;sub->length=0;for(i=0;i<len;i+)sub->

7、datai=s->datai+pos-1;sub->length+;sub->datai='0'return OK;/*subString*/* （ 4） - 兩個串連接， s2 連接在 s1 后，連接后的結(jié)果串放在 t 中 */ int strConcat(SqString *t,SqString *s1,SqString *s2) int i=0,j=0;while(i<s1->length)t->datai=s1->datai;i+;while(j<s2->length)t->datai+=s2->data

8、j+;t->datai='0't->length=s1->length+s2->length;return OK;/*strConcat*/int main()int n,k,pos,len;SqString s,t,x;doprintf("n -String- n");printf(" 1. strLentghn");printf(" 2. strComparen");printf(" 3. subStringn");printf(" 4. strConcatn&

9、quot;);printf(" 0. EXITn");printf("n -String-n");printf("ninput choice:");scanf("%d",&n);getchar();switch(n)case 1:printf("n*show strLength*n");strCreate(&s);printf("strLength is %dn",strLength(&s);break;case 2:printf("n*sh

10、ow strCompare*n");strCreate(&s);strCreate(&t);k=strCompare(&s,&t); /* （5） - 調(diào)用串比較函數(shù)比較 s， t*/ if(k=0)printf("two string equal!n");else if(k<0)printf("first string<second string!n");elseprintf("first string>second string!n");break;case 3:prin

11、tf("n*show subString*n");strCreate(&s);printf("input substring pos,len:");scanf("%d,%d",&pos,&len);if(subString(&t,&s,pos,len)printf("subString is %sn",t.data);elseprintf("pos or len ERROR!n");break;case 4:printf("n*show subC

12、oncat*n");strCreate(&s);strCreate(&t);if(strConcat(&x,&s,&t) /* （ 6） - 調(diào)用串連接函數(shù)連接 s&t*/ printf("Concat string is %s",x.data);elseprintf("Concat ERROR!n");break;case 0:exit(0);default:break;while(n);return 0;2 、按照要求完成程序exp4_2.c ，實現(xiàn) BF&KMP串的模式匹配算法。調(diào)試

13、及測試數(shù)據(jù)并給出結(jié)果：應用 BF 算法求子串” JING”在主串” BEIJING”中的位置， 測試起始位置分別為 1 和 5 的情況；應用 KMP算法求子串” abaabcac ”在主串” acabaabaabcacaabc ”中的位置， 測試起始位置分別為 1， 10 的情況，并寫出子串的 next 值；exp4_2.c 部分代碼如下：#include<stdio.h>#include<string.h>#define MAXSIZE 100#define ERROR 0#define OK 1/* 串的定長順序存儲表示*/typedef structchar da

14、taMAXSIZE;int length; SqString;int strCreate(SqString *s);int indexBf(SqString *s,SqString *t,int pos);/*void getNext(SqString *t,int next);/*KMPint indexKmp(SqString *s,SqString *t,int start,int next); /*串的模式匹配求 nextBF*/值 */串的模式匹配KMP*/* 生成一個串 */int strCreate(SqString *s)printf("input string :&

15、quot;);gets(s->data);s->length=strlen(s->data);return OK;/*strCreate*/* （ 1） - 串的模式匹配BF*/int indexBf(SqString *s,SqString *t,int pos)int i=pos-1,j=0;while(i<s->length&&j<t->length)if(s->datai=t->dataj)i+;j+;elsei=i-j+1;j=0;if(j>=t->length)return i-t->lengt

16、h+1;elsereturn 0;/*index_bf*/* （ 2） -KMP 求 next 值*/void getNext(SqString *t,int next)int i=0,j=-1;next0=-1;while(i<t->length)if(j=-1)|(t->datai=t->dataj)j+;i+;nexti=j;elsej=nextj;/*getNext*/* （ 3） -KMP 模式匹配 */int indexKmp(SqString *s,SqString *t,int start,int next)int i=start-1,j=0;while

17、(i<s->length&&j<t->length)if(j=-1|s->datai=t->dataj)i+;j+;elsej=nextj;if(j>=t->length)return i-t->length+1;elsereturn 0;/*index_kmp*/int main()int n,i,pos,nextMAXSIZE;SqString s,t;doprintf("n -String- n");printf(" 1. Index_BFn");printf(" 2.

18、 INdex_KMPn");printf(" 0. EXITn");printf("n -String-n");printf("ninput choice:");scanf("%d",&n);getchar();switch(n)case 1:printf("n*show Index_BF*n");printf(" s:");strCreate(&s);printf(" t:");strCreate(&t);printf("input st