4.字符串

该串的相关信息。这种存储结构称为堆结构。动态分配存储空间的顺序串也叫堆串。堆串可定义如下： typedef struct { int length; int start; } HeapString;4.2 串的存储结构4-* 4.2 串的存储结构 在C语言中，有一个称为“堆”的自由存储空间，并可利用malloc()和free()等动态存储管理函数，根据实际需要动态分配和释放字符数组空间，如下图所示。其类型可描述如下： typedef struct { char *ch; //指示串的起始地址，可按实际的串长分配存储区 int len; } HString; HString s; //定义一个串变量 顺序串的动态存储结构4.2 串的存储结构4-* 4.2 串的存储结构 在程序中，可根据实际需求为这种类型的串变量动态分配存储空间，这样做非常有效、方便，只是在程序执行过程中要不断地生成新串和销毁旧串。 4.2 串的存储结构4-* 4.2 串的存储结构4.2.2 串的链式存储 顺序串上的插入和删除操作极不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串，如下图所示。结点大小为1的链串s4.2 串的存储结构4-* 4.2 串的存储结构链串的类型描述： typedef struct node { char ch; struct node *next; //next为指向结点的指针 } LString; LString s; //定义一个串变量s 一个链串由头指针惟一确定。 这种结构便于进行插入和删除运算，但存储空间利用率太低。4.2 串的存储结构4-* 4.2 串的存储结构 为了提高存储密度，可使每个结点存放多个字符。如图所示，通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。结点大小为4的链串4.2 串的存储结构4-* 4.2 串的存储结构 对于结点大小不为1的链串，其类型定义只需对上述的结点类型做简单的修改即可。 #define nodesize 80 typedef struct node { char data[nodesize]; struct node *next; } LString; 虽然增大结点的数据域使得存储密度增大，但是做插入、删除运算时，需要考虑结点的分拆与合并，可能会引起大量字符的移动，给运算带来不便。4.2 串的存储结构4-* 4.2 串的存储结构链串的插入4.3 串的基本运算的实现4-* 4.3 串的基本运算的实现1. 求子串运算(采用静态存储顺序串) int StrSub(SString *sub, SString s, int pos, int len) //用sub返回串s中序号pos开始的长度为len 的子串 { int i; if (pos<0 || pos>s.len || len<1 || len>s.len-pos) { sub->len=0; return(0); } //子串起始位置及长度是否合适 else { for(i=0;ich[i]=s.ch[i+pos]; sub->[len]= '\0'; //子串结束 sub->len=len; return(1); } }4.3 串的基本运算的实现4-* 4.3 串的基本运算的实现2. 定位运算(采用静态存储顺序串) 串的定位运算也称为串的模式匹配，是一种重要的串运算。 设s和t是给定的两个串，在主串s中找到等于子串t的过程称为模式匹配，如果在s中找到等于t的子串，则称匹配成功，函数返回t在s中的首次出现的存储位置(或序号)，否则匹配失败，返回－1。t也称为模式。 【算法思想】首先将s0与t0进行比较，若不同，就将s1与t0进行比较……，直到s的某一个字符si和t0相同，再将它们之后的字符进行比较，若也相同，则如此继续往下比较，当s的某一个字符si与t的字符tj不同时，则s返回到本趟开始字符的下一个字符，即si－j+1，t返回到t0，继续开始下一趟的比较，重复上述过程。若t中的字符全部比较完，则说明本趟匹配成功，本趟的起始位置是i－j，否则，匹配失败。 设主串s=“ababcabcacbab”，模式t=“abcac”，匹配过程如下图所示。null简单模式匹配的匹配过程4.3 串的基本运算的实现4-* 4.3 串的基本运算的实现模式匹配算法 int StrIndex(SString s,int pos,SString t) //求串t在串s中的位置 { int i,j; if(t.len==0) return(0); i=pos;j=0; while(i=t.len) return(i-j); //匹配成功，返回存储位置 else return(-1); }4.3 串的基本运算的实现4-* 4.3 串的基本运算的实现3．插入运算(采用动态存储串) StrInsert(HString *s, int pos, HString t) //在串s的第pos个字符之前插入串t { char *temp; int i; if(pos<0 || pos>s->len) return(0); //pos不合理 if(t.len) //t非空 { temp=(char*)malloc((s->len+t.len)*sizeof(char)); //临时变量，暂存插入后的结果 if(temp==NULL) return(0); for(i=0;ich[i]; for(i=0;ilen;i++) temp[i+t.len]=s->ch[i]; s->len+=t.len; free(s->ch); //释放原串s s->ch=temp; //s获得相加结果 return(1); } }4.3 串的基本运算的实现4-* 4.3 串的基本运算的实现4．连接运算(采用动态存储串) StrCat(HString *s,HString t) //将串t连接在串s的后面 { char *temp; int i; temp=(char *) malloc((s->len+t.len)*sizeof(char)); if(temp==NULL) return(0); for(i=0;i<=s->len;i++) temp[i]=s->ch[i]; //复制s串 for(i=s->len;i<=s->len+t.len;i++) //复制t串 temp[i]=t.ch[i-s->len]; s->len+=t.len; free(s->ch); s->ch=temp; return(1); }4.3 串的基本运算的实现4-* 4.3 串的基本运算的实现5．串定位(采用链串存储) LString *lindex(LString s,LString t) //求串t在串s中的位置，返回指向t串起始位置的指针 { LString *loc,*p,*q; loc=s; p=loc;q=t; while(p && q) //当t、s串均未结束时 { if(p->data==q->data) //字符匹配时，指针后移 { p=p->next; q=q->next; } else //字符不匹配时，回溯 { loc=loc->next; p=loc; q=t; } } if(q==NULL) return(loc); //匹配完成，返回 else return(NULL); }习 题 44-* 习 题 41. 简述下列每对术语的区别：空串和空白串，串常量和串变量，主串和子串，静态分配的顺序串和动态分配的顺序串。 2. 设s=‘I am a student’，q=‘programer’。给出下列操作的结果： StrLength(s) SubString(sub1,s,1,7) Index(s, 'a',4) Replace(s, 'student',q) 结果: （1）14 （2）sub1 =‘I am a ’ （3）6 （4） s=‘I am a programer’