结构算法（25）
定义：是由零个或多个字符组成的有限序列，又名叫字符串。
串的比较是通过组成串的字符之间的编码来进行的，而字符的编码指的是字符在对应字符集中的序号。
ASCII编码，由7位二进制数表示一个字符，总共可以表示128个字符
扩展ASCII码,由8位二进制数表示一人字符，总共可以表示256个字符
Unicode编码由16位二进制数表示一个字符，总共就可以表示216&& 约6.5万多个字符，当然为了兼容ASCII前256个字符与ASCII码相同。
所以我们在C语言中比较两个串是否相等，必须是它们串的长度以及它们各个对应位置的字符都相等时，才算是相等。
串的抽象数据类型
串的逻辑结构和线性表很相似，不同之处在于串针对的是字符集，也就是串中的元素都是字符。
不同之处：对于串的基本操作与线性表是有很大差别的。线性表更关注的是单个元素的操作，比如查找一个元素，插入或删除一个元素，但串中的更多的是查找子串位置、得到指定位置子串、替换子串操作。
ADT& 串& （string）
&&&&&串中元素仅由一个字符组成，相邻元素具有前驱和后继关系
&&&&&&&&&StrAssign(T,*chars):生成一个其值等于字符串常量chars的串T
&&&&&&&&&StrCopy(T,S):串S存在，由串S复制得串T
&&&&&&&&&ClearString(S):串S存在，将串清空。
&&&&&&&&&StringEmpty(S):若串为空，返回true，否则返回false
&&&&&&&&&StrLength(S):返回串S的元素个数，即串的长度。
&&&&&&&&&StrCompare(S,T):若S&T，返回值&0，若S=T，返回0，若S&T，返回&0
&&&&&&&&&Concat(T,S1,S2):由T返回由S1和S2组成的新串
&&&&&&&&&SubString(Sub,S,pos,len):串S存在，1&=pos&=StrLength(S)且0&=len&=StrLength(S)-pos+1，用Sub返回串S的第pos个字符起长度为len子串
&&&&&&&&&Index(S,T,pos): 串S和T存在，T是非空串。1&=pos&=StrLength(S)，若主串S存在和串T相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置，否则返回0。
&&&&&&&&&Replace(S,T,V):串S、T和V存在，T是非空串。用V替换主串S中出现的所有与T相等的不重叠的子串
&&&&&&&&&StrInsert(S,pos,T):串S和T存在，1&=pos&StrLength(S)+1，在串S的第pos个字符之前插入串T。
&&&&&&&&&StrDelete(S,pos,len):串S存在，1&=pos&=StrLength(S)-len+1。从串S中删除第pos个字符起长度为len的子串
我们来看一个Index的实现算法。
int&&Inext(String& S,String& T,int&pos)
&&&&&int& n,m,i;
&&&&String&
&&&&&if(pos&0)
&&&&&&&&&&n=StringLength(S); //主串长度
&&&&&&&&&&m=StringLength(T);//子串长度
&&&&&&&&&&i=
&&&&&&&&&&while(i&=n-m+1)
&&&&&&&&&&&{
&&&&&&&&&&&&&&&&& SubString(sub,S,i,m);
&&&&&&&&&&&&&&&&& if(StrCompare(sub,T)!=0)
&&&&&&&&&&&&&&&&&&&&& ++i;
&&&&&&&&&&&&&&&&&& else
&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&}
串的存储结构
串的顺序存储结构
串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般是用定长数组来定义。既然是定长数组，就存在一个预定义的最大串长度，一般可以将实际中长度值保存在数组的0下标位置。但也有些编辑语言不想这么干，觉得存个数字占个空间麻烦。它规定在串值后面加一个不计入串长度的结束标记字符。比如“\0”。这个时候你想知道长度就需要遍历计算一下。其实还是占用一个空间。
其实顺序存储方式其实是有问题的，因为字符串的操作，比如两串的连接Concat、新串的插入StrInsert，以及字符串的替换Replace，都有可能使得串序列的长度超过数组的长度MaxSize。
于是对于串的顺序存储，有一些变化，串值的存储空间可在程序执行过程中动态分配而得。比如在计算机中存在一个自由存储区，叫做“堆”。这个堆可以由C语言的动态分配函数malloc()和free()来管理。
串的链式存储结构
对于串的链式存储结构，与线性表是相似的，但由于串结构的特殊性，结构中的每个元素数据是一个字符，如果也简单的应用链表存储串值，一个结点对应一个字符，就会存在很大的空间浪费。因此一个结点可以存放多个字符，最后一个结点若是未被占满时，可以用#或其他非串值字符补全。当然一个结点存多少个字符才合适变得很重要，这会直接影响着串处理的效率，需要根据实际情况做出选择。但串的链式存储结构除了在连接串与串操作时有一定方便之外，总的来说不如顺序存储灵活。性能也不如顺序存储结构好。
朴素的模式匹配算法
这种子串的定位操作通常称做串的模式匹配。
简单的说，就是对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配。对主串做大循环，每个字符开做T的长度的循环，直到匹配成功或全部遍历完成为止。
KMP模式匹配算法
克努特---莫里斯---普拉特算法
原理的推导过程还是去看书吧……（大话数据结构那本书的5.7.1那本书里）
我们把T串各个位置的j值的变化定义为一个数组next，那么next的长度就是T串的长度。于是我们可以得到下面的函数定义
next数组值推导
具体如何推导出一个串的next数组呢，我们来看下例
1.&&&T=”abcdex”
1)&&&&当j=1时，next[1]=0;
2)&&&&当j=2时，j由1到j-1就只有一个字符“a”，属于其他情况next[2]=1;
3)&&&&当j=3时，j由1到j-1串是”ab”,显然“a”与“b”不相等，属其他情况，next[3]=1;
4)&&&&以后同理，所以最终此T串的next[j]为011111。
2.&&&T=“abcabx”
1)&&&&当j=1时，next[1]=0;
2)&&&&当j=2时，同上例说明，next[2]=1;
3)&&&&当j=3时，同上，next[3]=1;
4)&&&&当j=4时，同上，next[4] =1
5)&&&&当j=5时，此时j由1到j-1的串是abca，前缀字符”a”与后缀字符”a”相等 根据p1…pk-1=pj-k+1…pj-1得p1=p4
6)&&&&当j=6时，j由1到j-1的串是abcab& next[6]=3;
后缀“ab”相等，所以next[6]=3.
我们可以根据经验得到如果前后缀一个字符相等，k值是2，两个字符k值是3，n个相等k值就是n+1;
KMP模式匹配算法实现
//通过计算返回子串T的next数组
void&&get_next(String&& T,int& *next)
&&&&&&int& i,j;
&&&&&next[1]=0;
&&&&&while(i&T[0]) //T[0]表示串T的长度
&&&&&&&&&&&&&& if(j==0||T[i]==T[j]){
&&&&&&&&&&&&&&&&&& ++i;
&&&&&&&&&&&&&&&&&& ++j;
&&&&&&&&&&&&&&&&&& next[i]=j;
&&&&&&&&&&&&&&&& }else{
&&&&&&&&&&&&&&&&&&&&& j=next[j];& //若字符不相同，则j值回溯
&&&&&&&&&&&&&&&& }
//返回子串在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0
int&&Index_KMP(String& S, String& T,int&pos)
int&& j=1;
int&& next[255] ; //定义一next数组
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;
KMP算法仅当模式与主串之间存在许多“部分匹配”的情况下才体现出它的优势，否则两者差异不明显。
改进的KMP模式匹配算法
void&&get_nextval(String& T,int& *nextval)
&&&&&&int& i,j;
&&&&&nextval[1]=0;
&&&&&while(i&T[0]) //T[0]表示串T的长度
&&&&&&&&&&&&&& if(j==0||T[i]==T[j]){
&&&&&&&&&&&&&&&&&& ++i;
&&&&&&&&&&&&&&&&&& ++j;
&&&&&&&&&&&&&&&&&&if(T[i]!=T[j])
&&&&&&&&&&&&&&&&&&&&&&&&&nextval[i]=j;
&&&&&&&&&&&&&&&&&&&else
&&&&&&&&&&&&&&&&&&&&&&&&&nextval[i] = nextval[j];
&&&&&&&&&&&&&& &&}else{
&&&&&&&&&&&&&&&&&&&&& j=nextval[j];& //若字符不相同，则j值回溯
&&&&&&&&&&&&&&&& }
更详细的KMP算法数学证明和更详细的说明参阅《算法导论》第2版第32章字符匹配。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：117238次
积分：2173
积分：2173
排名：第10604名
原创：80篇
转载：140篇
(4)(9)(2)(2)(1)(18)(9)(6)(2)(15)(33)(12)(4)(18)(5)(16)(3)(3)(48)(2)(1)(2)(1)(2)【Data】队列和串
一、队列的定义：
队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。象日常生活中的排队，最早入队的最早离开。
在队列中，允许插入的的一端叫
，允许删除的一端则称为
抽象数据类型队列:
ADT Queue{
数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n&=0}
数据关系: R1={&ai-1,ai& | ai-1,ai(- D,i=2,...,n}
基本操作：
InitQueue(&Q) 构造一个空队列Q
Destroyqueue(&Q) 队列Q存在则销毁Q
ClearQueue(&Q) 队列Q存在则将Q清为空队列
QueueEmpty(Q) 队列Q存在,若Q为空队列则返回TRUE,否则返回FALSE
QueueLenght(Q) 队列Q存在,返回Q的元素个数,即队列的长度
GetHead(Q,&e) Q为非空队列,用e返回Q的队头元素
EnQueue(&Q,e) 队列Q存在,插入元素e为Q的队尾元素
DeQueue(&Q,&e) Q为非空队列,删除Q的队头元素,并用e返回其值
QueueTraverse(Q,vivsit()) Q存在且非空,从队头到队尾,依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败
}ADT Queue
二、链队列
& & & & & &——队列的链式表示和实现
用链表表示的队列简称为
。一个链队列显然需要两个分别指示队头和队尾的指针。
//存储表示
typedef struct QNode{
struct QNode *
}QNode,*QueueP
typedef struct{
//操作的实现
Status InitQueue(LinkQueue &Q) {
//构造一个空队列Q
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)exit(OVERFLOW);
Q.front-&next=NULL;
return OK;}
Status Destroyqueue(LinkQueue &Q) {
//队列Q存在则销毁Q
while(Q.front){
Q.rear=Q.front-&
free(Q.front);
Q.front=Q.
return OK;}
Status EnQueue(LinkQueue &Q,QElemType e) {
//队列Q存在,插入元素e为Q的队尾元素
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(OVERFLOW);
p-&data=e;p-&next=NULL;
Q.rear-&next=p;
return OK;}
Status DeQueue(LinkQueue &Q,QElemType &e) {
//Q为非空队列,删除Q的队头元素,并用e返回其值
if(Q.front==Q.rear)return ERROR;
p=Q.front-&
Q.front-&next=p-&
if(Q.rear==p)Q.rear=Q.
return OK;}
三、串定义
串（或字符串），是由零个或多个字符组成的有限序列。一般记为：
s='a1a2...an'(n&=0)
其中s是串的名，用单引号括起来的字符序列是串的值；串中字符的数目n称为串的长度。零个字符的串称为空串，它的长度为零。
串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。
例：a='BEI',b='JING',c='BEIJING',d='BEI JING'
串长分别为
3,4,7,8,且a,b都是c,d的子串。
称两个串是相等的，当且仅当这两个串的值相等。
四、串的抽象数据类型的定义：
ADT String{
数据对象：D={ai|ai(-CharacterSet,i=1,2,...,n,n&=0}
数据关系：R1={&ai-1,ai&|ai-1,ai(-D,i=2,...,n}
基本操作：
StrAssign(&T,chars)//chars是字符常量。生成一个其值等于chars的串T。
StrCopy(&T,S)//串S存在则由串S复制得串T
StrEmpty(S)//串S存在,若S为空串,返回真否则返回假
StrCompare(S,T)//串S和T存在,若S&T,则返回值大于0,若S=T,则返回值=0,若S&T,则返回值&0
StrLength(S)//串S存在返回S的元素个数称为串的长度.
ClearString(&S)//串S存在将S清为空串
Concat(&T,S1,S2)//串S1和S2存在用T返回由S1和S2联接而成的新串
SubString(&Sub,S,pos,len)
将串S中从第pos个字符开始长度为len的字符序列复制到 串Sub。
1&=pos&=StrLength(S)且0&=len&=StrLength(S)-pos+1
Index(S,T,pos)//串S和T存在,T是非空,1&=pos&=StrLength(S),若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置,否则函数值为0
Replace(&S,T,V)//串S,T和V存在,T是非空串,用V替换主串S中出现的所有与T相等的不重叠的子串
StrInsert(&S,pos,T)//串S和T存在,1&=pos&=StrLength(S)+1,在串S的第pos个字符之前插入串T
StrDelete(&S,pos,len)//串S存在,1&=pos&=StrLength(S)-len+1从串中删除第pos个字符起长度为len的子串
DestroyString(&S)//串S存在,则串S被销毁
}ADT String
肿么这么多操作！！！
下一篇继续讲好了，串的几种实现方法
本分类共有文章11篇,更多信息详见
& 2012 - 2014 &
&All Rights Reserved. &
/*爱悠闲图+*/
var cpro_id = "u1888441";
/*爱悠闲底部960*75*/
var cpro_id = "u1888128";串的定长顺序存储表示
//串的定长顺序存储表示#define MAXSTRLEN 40 // 用户可在255以内定义最大串长（1个字节）
typedef char
SString[MAXSTRLEN+1];
// 0号单元存放串的长度
//串采用定长顺序存储结构的基本操作(14个)
// SString是数组，故不需引用类型。此基本操作包括算法4.2,4.3,4.5
Status StrAssign(SString
T,char *chars)
{ // 生成一个其值等于chars的串Tint i;if(strlen(chars)&MAXSTRLEN)return ERROR;else
T[0]=strlen(chars);for(i=1;i&=T[0];i++)
T[i]=*(chars+i-1);return OK;
Status StrCopy(SString T,SString S)
{ // 由串S复制得串Tint i;for(i=0;i&=S[0];i++)
T[i]=S[i];return OK;
Status StrEmpty(SString S)
{ // 若S为空串,则返回TRUE,否则返回FALSEif(S[0]==0)return TRUE;elsereturn FALSE;
StrCompare(SString S,SString
{ // 初始条件: 串S和T存在// 操作结果:
若S&T,则返回值&0;若S=T,则返回值=0;若S&T,则返回值&0
int i;for(i=1;i&=S[0]&&i&=T[0];++i)
if(S[i]!=T[i])return S[i]-T[i];return S[0]-T[0];
StrLength(SString S)
{ // 返回串的元素个数return S[0];
Status ClearString(SString S)
{ // 初始条件:串S存在。操作结果:将S清为空串S[0]=0;// 令串长为零return OK;
Status Concat(SString T,SString S1,SString S2) // 算法4.2改{ // 用T返回S1和S2联接而成的新串。若未截断，则返回TRUE，否则FALSE
int i;if(S1[0]+S2[0]&=MAXSTRLEN)
{ // 未截断for(i=1;i&=S1[0];i++)
T[i]=S1[i];for(i=1;i&=S2[0];i++)
T[S1[0]+i]=S2[i];
T[0]=S1[0]+S2[0];return TRUE;
{ // 截断S2for(i=1;i&=S1[0];i++)
T[i]=S1[i];for(i=1;i&=MAXSTRLEN-S1[0];i++)
T[S1[0]+i]=S2[i];
T[0]=MAXSTRLEN;return FALSE;
Status SubString(SString Sub,SString S,int pos,int len)
{ // 用Sub返回串S的第pos个字符起长度为len的子串。算法4.3
int i;if(pos&1||pos&S[0]||len&0||len&S[0]-pos+1)return ERROR;for(i=1;i&=i++)
Sub[i]=S[pos+i-1];
Sub[0]=return OK;
Index(SString S,SString
T,int pos)
{ // 返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数值为0。//
其中,T非空,1≤pos≤StrLength(S)。算法4.5
int i,j;if(1&=pos&&pos&=S[0])
j=1;while(i&=S[0]&&j&=T[0])
if(S[i]==T[j]) // 继续比较后继字符{++i;++j;
// 指针后退重新开始匹配{
}if(j&T[0])return i-T[0];elsereturn 0;
}elsereturn 0;
Status StrInsert(SString S,int pos,SString T)
{ // 初始条件:
串S和T存在,1≤pos≤StrLength(S)+1// 操作结果:
在串S的第pos个字符之前插入串T。完全插入返回TRUE,部分插入返回FALSEint i;if(pos&1||pos&S[0]+1)return ERROR;if(S[0]+T[0]&=MAXSTRLEN)
{ // 完全插入for(i=S[0];i&=i--)
S[i+T[0]]=S[i];for(i=i&pos+T[0];i++)
S[i]=T[i-pos+1];
S[0]=S[0]+T[0];return TRUE;
{ // 部分插入for(i=MAXSTRLEN;i&=i--)
S[i]=S[i-T[0]];for(i=i&pos+T[0];i++)
S[i]=T[i-pos+1];
S[0]=MAXSTRLEN;return FALSE;
Status StrDelete(SString S,int pos,int len)
{ // 初始条件:
串S存在,1≤pos≤StrLength(S)-len+1// 操作结果:
从串S中删除第pos个字符起长度为len的子串int i;if(pos&1||pos&S[0]-len+1||len&0)return ERROR;for(i=pos+i&=S[0];i++)
S[i-len]=S[i];
S[0]-=return OK;
Status Replace(SString S,SString T,SString V)
{ // 初始条件:
串S,T和V存在,T是非空串（此函数与串的存储结构无关）// 操作结果:
用V替换主串S中出现的所有与T相等的不重叠的子串int i=1; // 从串S的第一个字符起查找串Tif(StrEmpty(T)) // T是空串return ERROR;do
i=Index(S,T,i); // 结果i为从上一个i之后找到的子串T的位置if(i) // 串S中存在串T{
StrDelete(S,i,StrLength(T)); // 删除该串TStrInsert(S,i,V); // 在原串T的位置插入串Vi+=StrLength(V); // 在插入的串V后面继续查找串T}
}while(i);return OK;
DestroyString()
{ // 由于SString是定长类型,无法销毁}
StrPrint(SString T)
{ // 输出字符串T。另加int i;for(i=1;i&=T[0];i++)
printf("%c",T[i]);
printf("\n");
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。数据结构（22）
□4.1 串类型的定义
由一个或者多个空格组成的串称为空格串(blank string)，零个字符的串称为空串(null string)。
串(string)是由零个或多个字符组成的有限序列。称两个串是相等的，当且仅当这两个串的值相等。这就是说只有当两个串的长度相等，并且各个对应位置的字符都相等时才相等。串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。在线性表中，大多以&单个元素&作为操作对象，例如在线性表中查找某个元素，求取某个位置上插入一个元素和删除一个元素等；而在串的基本操作中，通常以串的整体作为操作对象，例如在串中查找某个字串，求取一个子串，在串的某个位置上插入一个字串以及删除一个子串等。
// PROJECT04-01.cpp : 定义控制台应用程序的入口点。
#include &stdafx.h&
#include &c1.h&
#include &string.h&
/* ----------------------------------------
串的定长顺序存储表示
----------------------------------------*/
/* 用户可在255以内定义最大串长（1个字节） */
#define MAXSTRLEN 40
/* 0号单元存放串的长度 */
typedef char SString[MAXSTRLEN + 1];
Status StrAssign(SString T,char *chars)
{ /* 生成一个其值等于chars的串T */
if ( strlen(chars) & MAXSTRLEN ){
return ERROR;
T[0] = strlen(chars);
for(i = 1; i &= T[0]; i++){
T[i] = *(chars + i - 1);
return OK;
Status StrCopy(SString T, SString S)
{ /* 由串S复制得串T */
for(i = 0; i &= S[0]; i++){
T[i] = S[i];
return OK;
Status StrEmpty(SString S)
{ /* 若S为空串,则返回TRUE,否则返回FALSE */
if (S[0] == 0){
return TRUE;
return FALSE;
int StrCompare(SString S, SString T)
{ /* 初始条件: 串S和T存在 */
/* 操作结果: 若S&T,则返回值&0;若S=T,则返回值=0;若S&T,则返回值&0 */
for(i = 1;i &= S[0] && i &= T[0]; ++i){
if (S[i] != T[i]){
return S[i] - T[i];
return S[0] - T[0];
int StrLength(SString S)
{ /* 返回串的元素个数 */
return S[0];
Status ClearString(SString S)
{ /* 初始条件:串S存在。操作结果:将S清为空串 */
S[0] = 0;/* 令串长为零 */
return OK;
Status Concat(SString T,SString S1,SString S2) /* 算法4.2改 */
{ /* 用T返回S1和S2联接而成的新串。若未截断，则返回TRUE，否则FALSE */
if (S1[0] + S2[0] & MAXSTRLEN){
/*没有截断*/
for(i = 1; i & S1[0]; i++){
T[i] = S1[i];
for(i = 1; i & S2[0]; i++){
T[S1[0] + i] = S2[i];
T[0] = S1[0] + S2[0];
return TRUE;
/*已截断*/
for(i = 1;i &= S1[0]; i++){
T[i] = S1[i];
for(i = 1; i & MAXSTRLEN - S1[0]; i++){
T[S1[0] + i] = S2[i];
T[0] = MAXSTRLEN;
return FALSE;
Status SubString(SString Sub,SString S,int pos,int len)
{ /* 用Sub返回串S的第pos个字符起长度为len的子串。算法4.3 */
if(pos & 1 || pos & S[0] || len & 0 || len & S[0] - pos + 1){
return ERROR;
for(i = 1; i &= i++){
Sub[i] = S[i + pos - 1];
return OK;
int Index(SString S,SString T,int pos)
{ /* 返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数值为0。 */
/* 其中,T非空,1≤pos≤StrLength(S)。算法4.5 */
if( 1 &= pos && pos &= S[0] ){
i = /*i指向主串的指针*/
/*j指向子串的指针*/
while( i &= S[0] && j &= T[0] ){
if(S[i] == T[j]){ /* 继续比较后继字符 */
else{ /* 指针后退重新开始匹配 */
i = i - j + 2;
if(j & T[0]){
return i - T[0];
void DestroyString()
{ /* 由于SString是定长类型,无法销毁 */
void StrPrint(SString T)
{ /* 输出字符串T。另加 */
for (i = 1; i &= T[0]; i++){
printf(&%c&, T[i]);
printf(&\n&);
Status StrInsert(SString S, int pos, SString T)
{ /* 初始条件: 串S和T存在,1≤pos≤StrLength(S)+1 */
/* 操作结果: 在串S的第pos个字符之前插入串T。完全插入返回TRUE,部分插入返回FALSE */
if( pos & 1 || pos & S[0] + 1 ){
return ERROR;
if(S[0] + T[0] &= MAXSTRLEN){ /* 完全插入 */
/*移动插入以后的后半段*/
for(i = S[0];i &= i--){
S[i + T[0]] = S[i];
/*字符串T的插入*/
for(i = i & pos + T[0]; i++){
S[i] = T[i - pos + 1];
S[0] = S[0] + T[0];
return TRUE;
/* 部分插入 */
for(i = MAXSTRLEN; i &= i--){
S[i]=S[i-T[0]];
for(i =i & pos+T[0]; i++){
S[i]=T[i-pos+1];
S[0]=MAXSTRLEN;
return FALSE;
Status StrDelete(SString S,int pos,int len)
{ /* 初始条件: 串S存在,1≤pos≤StrLength(S)-len+1 */
/* 操作结果: 从串S中删除第pos个字符起长度为len的子串 */
if (pos & 1 || len & 0 || pos & S[0]- len + 1){
return ERROR;
for(i = pos + i &= S[0]; i++){
S[i-len] = S[i];
return OK;
Status Replace(SString S,SString T,SString V)
{ /* 初始条件: 串S,T和V存在,T是非空串（此函数与串的存储结构无关） */
/* 操作结果: 用V替换主串S中出现的所有与T相等的不重叠的子串 */
int i=1; /* 从串S的第一个字符起查找串T */
if(StrEmpty(T)){ /* T是空串 */
return ERROR;
i = Index(S,T,i);/* 结果i为从上一个i之后找到的子串T的位置 */
if (i){/* 串S中存在串T */
StrDelete(S,i,StrLength(T));/* 删除该串T */
StrInsert(S,i,V); /* 在原串T的位置插入串V */
i += StrLength(V);/* 在插入的串V后面继续查找串T */
}while(i);
return OK;
void get_next(SString T, int next[])
{ /* 求模式串T的next函数值并存入数组next 算法 4.7 */
int i = 1,j = 0;
next[1] = 0;
while(i & T[0]){
if (j == 0 || T[i] == T[j]){
j = next[j];
int Index_KMP(SString S,SString T,int pos,int next[])
{ /* 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法。 */
/* 其中,T非空,1≤pos≤StrLength(S)。算法 4.6 */
int i = pos,j = 1;
while(i &= S[0] && j &= T[0]){
if(j == 0 || S[i] == T[j]){ /* 继续比较后继字符 */
else{ /* 模式串向右移动 */
j = next[j];
if(j & T[0]){ /* 匹配成功 */
return i - T[0];
int _tmain(int argc, _TCHAR* argv[])
char s,c[MAXSTRLEN+1];
SString t,s1,s2;
printf(&请输入串s1: &);
k=StrAssign(s1,c);
printf(&串长超过MAXSTRLEN(=%d)\n&,MAXSTRLEN);
printf(&串长为%d 串空否？%d(1:是 0:否)\n&,StrLength(s1),StrEmpty(s1));
StrCopy(s2,s1);
printf(&拷贝s1生成的串为: &);
StrPrint(s2);
printf(&请输入串s2: &);
k=StrAssign(s2,c);
printf(&串长超过MAXSTRLEN(%d)\n&,MAXSTRLEN);
i = StrCompare(s1,s2);
if(i & 0){
else if( i==0 ){
printf(&串s1%c串s2\n&,s);
k=Concat(t,s1,s2);
printf(&串s1联接串s2得到的串t为: &);
StrPrint(t);
if(k==FALSE){
printf(&串t有截断\n&);
ClearString(s1);
printf(&清为空串后,串s1为: &);
StrPrint(s1);
printf(&串长为%d 串空否？%d(1:是 0:否)\n&,StrLength(s1),StrEmpty(s1));
printf(&求串t的子串,请输入子串的起始位置,子串长度: &);
scanf(&%d,%d&,&i,&j);
k=SubString(s2,t,i,j);
printf(&子串s2为: &);
StrPrint(s2);
printf(&从串t的第pos个字符起,删除len个字符，请输入pos,len: &);
scanf(&%d,%d&,&i,&j);
StrDelete(t,i,j);
printf(&删除后的串t为: &);
StrPrint(t);
i=StrLength(s2)/2;
StrInsert(s2,i,t);
printf(&在串s2的第%d个字符之前插入串t后,串s2为:\n&,i);
StrPrint(s2);
i=Index(s2,t,1);
printf(&s2的第%d个字母起和t第一次匹配\n&,i);
SubString(t,s2,1,1);
printf(&串t为：&);
StrPrint(t);
Concat(s1,t,t);
printf(&串s1为：&);
StrPrint(s1);
Replace(s2,t,s1);
printf(&用串s1取代串s2中和串t相同的不重叠的串后,串s2为: &);
StrPrint(s2);
在上述抽象数据类型定义的13种操作中，串赋值StrAssign，串比较StrCompare，求串长StrLength，串连接Concat以及求子串SubString五种操作构成串类型的最小操作子集。即这些操作不可能利用其他操作来实现，反之，其他串操作均可在这个最小操作子集上实现。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：399890次
积分：6977
积分：6977
排名：第1720名
原创：271篇
转载：143篇
评论：31条
(2)(1)(2)(2)(5)(1)(2)(6)(2)(2)(1)(3)(2)(5)(3)(1)(1)(4)(1)(4)(1)(2)(2)(6)(1)(7)(2)(1)(13)(7)(13)(2)(14)(5)(2)(21)(1)(1)(3)(9)(6)(24)(6)(23)(7)(3)(46)(3)(5)(6)(1)(2)(2)(5)(1)(31)(11)(7)(8)(18)(12)(7)(8)(21)