《语言字符串数组和特殊矩阵》由会员分享，可在线阅读，更多相关《语言字符串数组和特殊矩阵（65页珍藏版）》请在金锄头文库上搜索。
1、第第4 4章 字符串、数组章 字符串、数组 和特殊矩阵和特殊矩阵 字符串字符串 字符串的模式匹配字符串的模式匹配稀疏矩阵稀疏矩阵 数组数组 特殊矩阵特殊矩阵4 .1 字符串4.1.1 字符串的基本概念字符串是由零个或多个字符构成的有限序列， 一般可表示成如下形式：“c1 c2 ” (n0) 串中所含字符的个数n称为字符串的长度；当n=0时 ，称字符串为空串。串中任意个连续的字符构成的子序列称为该串 的子串，包含子串的串称为主串。通常称字符在字 符串序列中的序号为该字符在串中的位置。子串在 主串中的位置以子串的第一个字符在主串中的位置 来表示。例如：T =“STUDENT”，S=“UDEN”,
2、则S 是T的子串，S在T中出现的位置为3。 两个字符串相等，当且仅当两个串的长度相等 ，并且各个对应位置的字符都相等。例如：T1=“REDROSE” T2=“RED ROSE” 由于T1和T2的长度不相等，因此T1T2。 若T3=“STUDENT” T4=“STUDENS” 虽然T3和T4的长度相等，但两者有些对应的字符不 同，因而T3T4。值得一提的是，若S=“ ”，此时S由一个空格 字符组成，其长度为1，它不等价于空串，因为空串的长度为0。 4.1.2 字符串类的定义ADT string 数据对象D：由零个或多个字符型的数据元素构成 的有限集合；数据关系R：|其中ai, ai+1D, i=
3、1,2,n-1 字符串的基本操作如下：（1） Strcreate(S) （2） Strassign(S, T) （3） Strlength(S) （4） Strempty(S) （5） Strclear(S) （6）Strcompare(S1，S2)（7） Strconcat(S1，S2) （8） Substring(S, i, len) （9） Index(P,T) （10） Strinsert(S, i, T) （11） Strdelete(S,i,len) （12） Replace(S, T1, T2) （13） Strdestroy(S) ADT string 4.1.3 字符串的存储
4、及其实现 1、串的顺序存储及其部分运算的实现串的顺序存储使用数组存放，具体类型定义如下：#define MAXSIZE 100typedef struct char strMAXSIZE;int length ; seqstring; （1）插入运算strinsert(S,i,T)void strinsert(seqstring *S, int i , seqstring T) int k;if (iS-length+1 | S-length + T.lengthMAXSIZE) printf(“connot insertn“);elsefor(k=S-length-1;k=i-1;k-) S
5、-strT.length+k=S-strk;for (k=0;kstri -1 +k=T.strk; S-length= S-length + T.length;S-strS-length=0; （2）删除运算strdelete(S,i,len)void strdelete(seqstring *S,int i,int len) int k ;if (iS-length|i+len-1S-length) printf(“ cannot deleten”);elsefor(k=i-1+len; klength;k+) S-strk-len= S-strk;S-length=S-length-le
6、n;S-strS-length=0; （3）连接运算strconcat(S1,S2) seqstring * strconcat(seqstring S1,seqstring S2) int i; seqstring *r;if (S1.length+S2.lengthMAXSIZE) printf(“cannot concate“); return(NULL);else r=(seqstring*)malloc (sizeof(seqstring); for (i=0; istri= S1.stri;for (i=0; istr S1.length+i= S2.stri;r-length=
7、S1.length+ S2.length;r-strr-length=0;return (r); （4）求子串运算substring(S,i,len) seqstring *substring(seqstring S,int i, int len) int k; seqstring *r;if (iS.length | i+len-1S.length) printf(“errorn”); return(NULL);else r=(seqstring*) malloc (sizeof(seqstring);for(k=0;kstrk= S.stri-1+k;r-length=len;r-strr
8、-length=0;return(r); 2 串的链接存储及其部分运算的实现串的链接存储采用单链表的形式实现，其中每个 结点的定义如下： typedef struct nodechar data; struct node *next; linkstrnode; typedef linkstrnode *linkstring; 例如，串S=“abcde”，其链接存储结构如下图所示： a ab bc cd de e S S（1）创建字符串运算strcreate (S) void strcreate (linkstring *S) char ch; linkstrnode *p,*r;*S=NULL
9、; r=NULL; while (ch=getchar()!=n) p=(linkstrnode *)malloc(sizeof(linkstrnode); p-data=ch; if (*S=NULL) *S=p;else r-next=p; r=p; /*r移向当前链接串的最后一个字符的位置*/if (r!=NULL) r-next=NULL; /*处理表尾结点指针域*/ （2）插入运算strinsert(S,i,T) void strinsert(linkstring *S,int i,linkstring T) int k ; linkstring p,q;p=*S, k=1;whil
10、e (p k+; if (!p) printf(“errorn“); else q=T;while(q-next) q=q-next; q-next=p-next; p-next=T; （3）删除运算strdelete(S,i,len)void strdelete(linkstring *S,int i,int len) int k ; linkstring p,q,r;p=*S, q=null; k=1;/*用p查找S的第i个元素，q始终跟踪p的前驱*/while (p k+; if (!p) printf(“error1n“); else k=1;/*p从第i个元素开始查找长度为len子串
11、的最后元素*/while(knext ;k+;if(!p) printf(“error2n“);else if (!q) r=*S; *S=p-next; /*被删除的子串位于S的最前面*/else /*被删除的子串位于的中间或最后*/r=q-next; q-next= p-next;p-next=null;while (r !=null) p=r; r=r-next; free(p);（4）连接运算strconcat(S1,S2)void strconcat(linkstring *S1, linkstring S2)linkstring p;if (!(*S1) ) *S1=S2; ret
12、urn;elseif (S2) /*S1和S2均不为空串的情形*/p=*S1; /*用p查找S1的最后一个字符的位置*/while(p-next ) p= p-next;p-next=S2; /*将串S2连接到S1之后*/ （5）求子串运算substring(S,i,len)linkstring substring(linkstring S,int i, int len) int k; linkstring p,q,r,t;p=S, k=1;/*用p查找S中的第i个字符*/while (p k+; if (!p) printf(“error1n“); return(null);else r=(
13、linkstring) malloc (sizeof(linkstrnode);r-data=p-data; r-next=null; k=1; q=r; /*用q始终指向子串的最后一个字符的位置*/while (p-next k+;t=(linkstring) malloc (sizeof (linkstrnode);t-data=p-data; q-next=t; q=t;if (knext=null; return(r); /*处理子串的尾部*/ 4.2 字符串的模式匹配 寻找字符串p在字符串t中首次出现的起始位置称 为字符串的模式匹配，其中称p为模式(pattern），t 为正文(te
14、xt)，t的长度远远大于p的长度。4.2.1 朴素的模式匹配算法 朴素模式匹配算法的基本思想是：用p中的每个字 符去与t中的字符一一比较：正文t： t1 t2 tmtn模式p： p1 p2 pm如果t1=p1,t2=p2,.tm=pm，则模式匹配成功；否则 将p向右移动一个字符的位置，重新用p中的字符从 头开始与t中相对应的字符依次比较，即：t1 t2 t3 tm tm+1tnp1 p2 pm-1 pm 如此反复，直到匹配成功或者p已经移到使t中剩下 的字符个数小于p的长度的位置，此时意味着模式匹 配失败，表示t中没有子串与模式p相等，我们约定 返回-1代表匹配失败。朴素模式匹配算法的具体实现
15、如下： int index(seqstring p, seqstring t) int i,j, succ;i=0; succ=0; /* succ为匹配成功的标志*/while(i2）维数组，可以依据上述规律类推 。 4.3.2 数组类的定义ADT array 数据对象D：具有相同类型的数据元素构成的有序集合；数据关系R：对于n维数组，其每一个元素均位于n个向量中 ， 每个元素最多具有n个前驱结点和n个后继结点 ；数组的基本操作如下：（1）Initarray (A, n, index1,index2, index n) （2）Destroyarray(A) （3）Value(A, index1,index2, index n, x)（4）Assign (A, e, index1,index2, index n) ADT array 4.3.3 数组的顺序存储及实现由于数组是由有限
