2. it技术
  3. 复习理解串的基本操作

复习理解串的基本操作

it2025-07-13  1

知识给人重量，成就给人光彩，大多数人只是看到了光彩，而不去称量重量

字符串、简称串，它也是一种重要的线性结构。计算机中处理的大部分数据都是字符串数据，例如，学生学籍信息系统的姓名、性别、家庭住址、院系名称等信息都属于字符串数据。串广泛应用于各种专业的信息管理、信息检索、问答系统、机器翻译等系统处理中。

一、顺序串的基本操作：

stringAssign () 初始化串 stringCopy () 串的拷贝 getLength () 获取串的长度 stringClear() 清空串 subString() 求子串 stringCompare() 串的比较 stringInsert() 串的插入 stringConcat() 串的连接 getNextVal() 获取每个字符的下一个匹配开始点 KMP_Index() KMP 模式匹配算法 stringDelete() 串的删除（用到模式匹配算法，这里使用KMP算法） stringReplace() 子串替换，只替换第一个子串 stringPrint() 打印串

1.1 基本操作代码实现：
#include <stdio.h> #include <stdlib.h> #include <string.h> #define TRUE 1; #define FALSE 0; #define OK 1; #define ERROR 0; #define MAX_NUM 100 #define Status int typedef struct { char ch[MAX_NUM+1]; int length; }String; // 初始化串 void stringAssign(String *str, char *chars){ if (str == NULL) exit(0); int len = strlen(chars); str->length = len; for (int i = 0; i < len; ++i) { str->ch[i] = chars[i]; } } // 串的拷贝 void stringCopy(String *str, String *str_){ for (int i = 0; i < str_->length; ++i) { str->ch[i] = str_->ch[i]; } str->length = str_->length; } // 获取串的长度 // 也可由此函数 判空 length = 0 int getLength(String *str){ return str->length; } // 清空串 void stringStr(String *str){ str->length = 0; } // 求子串 : 用sub返回串S的第pos个字符起长度为len的字串(包括pos下标) Status subString(String *str, String *sonStr, int pos, int len){ if (pos < 0 || len < 1 || pos >=str->length || pos+len > str->length) return FALSE; // 子串范围越界 for (int i = pos; i < pos+len; ++i) { sonStr->ch[i-pos] = str->ch[i]; } sonStr->length = len; return TRUE; } // 串的比较 int stringCompare(String *str, String *compareStr){ for (int i = 0; i <str->length&& i< compareStr->length; ++i) { if (str->ch[i] != compareStr->ch[i]) { return str->ch[i] - compareStr->ch[i]; // > 0 || < 0 } } return str->length - compareStr->length; // 扫描过的所有字符都相同，则长度长的串更大 } // 串的插入 Status stringInsert(String *str, int pos, String *insertStr){ if (str == NULL && insertStr == NULL) return ERROR; if (pos < 0 || pos > str->length || pos+insertStr->length > MAX_NUM) return ERROR; for (int i = str->length-1 ; i >= pos; --i) { // 空出位置 str->ch[i+insertStr->length] = str->ch[i]; } for (int j = 0; j < insertStr->length; ++j) { // 插入 str->ch[j+pos] = insertStr->ch[j]; } str->length += insertStr->length; return OK; } // 串的连接 Status stringConcat(String *str, String *conStr){ if (str == NULL && conStr == NULL) return ERROR; for (int i = 0; i < conStr->length; ++i) { str->ch[str->length+i] = conStr->ch[i]; } str->length += conStr->length; return TRUE; } // 获取每个字符的下一个匹配开始点 int getNextVal(int next[], String *T) { int j = 0, k =-1; // j 定义的是比较的位置 next[0] = -1; // 规定 next[0] = -1 后面更好算 while (j< T->length-1) { if (k == -1 || T->ch[j] == T->ch[k]) { j++; k++; if (T->ch[j] == T->ch[k])// 当两个字符相同时，就跳过 next[j] = next[k]; else next[j] = k; } else k = next[k]; } } // KMP 模式匹配算法: 若主串S中存在与串T值相同的子串则返回它在函数中第一次出现的位置；否则函数值为 -1、 int KMP_Index(String *str, String *T){ int next[T->length],i=0,j=0; // next[] 前缀表 getNextVal(next,T); // next数组 // 搜索子串位置 while (i< str->length && j< T->length) { if (j == -1 || str->ch[i] == T->ch[j]) { i++; j++; } else j = next[j]; // j 回退 } if (j >= T->length) { return (i - T->length); // 匹配成功，返回子串的位置 } else return -1; // 没找到 } // 串的删除（用到模式匹配算法，这里使用KMP算法） Status stringDelete(String *str, String *deleteStr){ if (str == NULL && deleteStr == NULL) return ERROR; if (deleteStr->length > str->length) return ERROR; int index = KMP_Index(str,deleteStr); // 判断是否是子串，并且删除 if (index < 0) { return FALSE; } for (int i = index; i < str->length-deleteStr->length; ++i) { str->ch[i] = str->ch[i+deleteStr->length]; } str->length -= deleteStr->length; return TRUE; } // 子串替换，只替换第一个子串 Status stringReplace(String *str, String *T, String *reStr){ if (str == NULL || T == NULL|| reStr == NULL) return FALSE; int index = KMP_Index(str, T); stringDelete(str,T); return stringInsert(str,index,reStr); } // 打印串 void stringPrint(String *str){ for (int i = 0; i < getLength(str); ++i) { printf("%c",str->ch[i]); } printf("\n"); } int main(){ String str, str_, sonStr, comStr, deStr,reStr, conStr; int pos = 1, len = 3; char *chars = "I Love China!"; char *chars_ = "China nb China nb!"; char *comChars = "China is the best in the world!"; char *reChars = "66"; char *deChars = "in"; char *conChars = "China is the best"; stringAssign(&str, chars); printf("str初始化："); stringPrint(&str); printf("----------------------\n"); stringAssign(&str_, chars_); printf("str_初始化："); stringPrint(&str_); printf("======================\n"); int strLen = getLength(&str); printf("str串的长度为：%d\n", strLen); printf("======================\n"); stringCopy(&str, &str_); printf("str 拷贝 str_ : "); stringPrint(&str); printf("======================\n"); subString(&str,&sonStr, pos, len); printf("求子串 第 1 个字符起到长度为 3 的子串(不含第一个本身)："); stringPrint(&sonStr); printf("======================\n"); stringAssign(&comStr, comChars); printf("str 与 comStr 比较： "); int result = stringCompare(&str, &comStr); if (result > 0) { printf("str 大\n"); }else if (result == 0) { printf("两者相等\n"); }else { printf("comStr 大\n"); } printf("======================\n"); stringAssign(&reStr,reChars); stringAssign(&deStr, deChars); stringReplace(&str,&deStr,&reStr); printf("替换 in 子串 为 666(只替换第一个)："); stringPrint(&str); printf("======================\n"); int index = KMP_Index(&str,&deStr); printf("KMP 模式匹配算法，求子串 in 的位置：%d\n", index); printf("======================\n"); stringDelete(&str, &deStr); printf("删除子串 in: "); stringPrint(&str); printf("======================\n"); stringAssign(&conStr, conChars); stringConcat(&str, &conStr); printf("str 与 constr 进行拼接："); stringPrint(&str); return 0; }

1.2 KMP算法实现原理：

可跳转至此篇博文，讲的非常好 —> KMP算法—终于全部弄懂了

二、 串的块链存储表示：

串结构的特殊性------结构中的每个数据元素是一个字符，则用链表存储串值时，存在一个“结点大小”的问题，即每个结点可以存放一个字符，也可以存放多个字符。

基本操作实现：
#include <stdio.h> #include <stdlib.h> #include <string.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define CHUNKSIZE 80 char blank='#'; typedef int Status; //定义块链存储的串的每个节点 typedef struct Chunk { char ch[CHUNKSIZE]; struct Chunk *next; }Chunk; //定义块链存储的串 typedef struct { Chunk *head, *tail; //串的头指针和尾指针 int curlen; //串的当前长度 }LString; void InitString(LString *T) { (*T).curlen=0; (*T).head=NULL; (*T).tail=NULL; } //生成一个其值等于串常量chars的串T Status StrAssign(LString *T,char *chars) { int i,j,k,l; Chunk *p,*q; i=strlen(chars); if(!i || strchr(chars,blank)) return ERROR; (*T).curlen=i; j=i/CHUNKSIZE; if(i%CHUNKSIZE) j++; for(k=0;k<j;k++) { p=(Chunk*)malloc(sizeof(Chunk)); if(!p) return ERROR; if(k==0) (*T).head=q=p; else { q->next=p; q=p; } for(l=0;l<CHUNKSIZE&&*chars;l++) *(q->ch+l)=*chars++; if(!*chars) { (*T).tail=q; q->next=NULL; for(;l<CHUNKSIZE;l++) *(q->ch+l)=blank; } } return OK; } Status StrCopy(LString *T,LString S) { Chunk *h=S.head,*p,*q; (*T).curlen=S.curlen; if(h) { p=(*T).head=(Chunk*)malloc(sizeof(Chunk)); *p=*h; h=h->next; while(h) { q=p; p=(Chunk*)malloc(sizeof(Chunk)); q->next=p; *p=*h; h=h->next; } p->next=NULL; (*T).tail=p; return OK; } else return ERROR; } Status StrEmpty(LString S) { if(S.curlen) return FALSE; else return TRUE; } int StrCompare(LString S,LString T) { int i=0; Chunk *ps=S.head,*pt=T.head; int js=0,jt=0; while(i<S.curlen&&i<T.curlen) { i++; while(*(ps->ch+js)==blank) { js++; if(js==CHUNKSIZE) { ps=ps->next; js=0; } }; while(*(pt->ch+jt)==blank) { jt++; if(jt==CHUNKSIZE) { pt=pt->next; jt=0; } }; if(*(ps->ch+js)!=*(pt->ch+jt)) return *(ps->ch+js)-*(pt->ch+jt); else { js++; if(js==CHUNKSIZE) { ps=ps->next; js=0; } jt++; if(jt==CHUNKSIZE) { pt=pt->next; jt=0; } } } return S.curlen-T.curlen; } int StrLength(LString S) { return S.curlen; } Status ClearString(LString *S) { Chunk *p,*q; p=(*S).head; while(p) { q=p->next; free(p); p=q; } (*S).head=NULL; (*S).tail=NULL; (*S).curlen=0; return OK; } Status Concat(LString *T,LString S1,LString S2) { LString a1,a2; InitString(&a1); InitString(&a2); StrCopy(&a1,S1); StrCopy(&a2,S2); (*T).curlen=S1.curlen+S2.curlen; (*T).head=a1.head; a1.tail->next=a2.head; (*T).tail=a2.tail; return OK; } Status SubString(LString *Sub, LString S,int pos,int len) { Chunk *p,*q; int i,k,n,flag=1; if(pos<1||pos>S.curlen||len<0||len>S.curlen-pos+1) return ERROR; n=len/CHUNKSIZE; if(len%CHUNKSIZE) n++; p=(Chunk*)malloc(sizeof(Chunk)); (*Sub).head=p; for(i=1;i<n;i++) { q=(Chunk*)malloc(sizeof(Chunk)); p->next=q; p=q; } p->next=NULL; (*Sub).tail=p; (*Sub).curlen=len; for(i=len%CHUNKSIZE;i<CHUNKSIZE;i++) *(p->ch+i)=blank; q=(*Sub).head; i=0; p=S.head; n=0; while(flag) { for(k=0;k<CHUNKSIZE;k++) if(*(p->ch+k)!=blank) { n++; if(n>=pos&&n<=pos+len-1) { if(i==CHUNKSIZE) { q=q->next; i=0; } *(q->ch+i)=*(p->ch+k); i++; if(n==pos+len-1) { flag=0; break; } } } p=p->next; } return OK; } int Index(LString S,LString T,int pos) { int i,n,m; LString sub; if(pos>=1&&pos<=StrLength(S)) { n=StrLength(S); m=StrLength(T); i=pos; while(i<=n-m+1) { SubString(&sub,S,i,m); if(StrCompare(sub,T)!=0) ++i; else return i; } } return 0; } void Zip(LString *S) { int j,n=0; Chunk *h=(*S).head; char *q; q=(char*)malloc(((*S).curlen+1)*sizeof(char)); while(h) { for(j=0;j<CHUNKSIZE;j++) if(*(h->ch+j)!=blank) { *(q+n)=*(h->ch+j); n++; } h=h->next; } *(q+n)=0; ClearString(S); StrAssign(S,q); } Status StrInsert(LString *S,int pos,LString T) { int i,j,k; Chunk *p,*q; LString t; if(pos<1||pos>StrLength(*S)+1) return ERROR; StrCopy(&t,T); Zip(S); i=(pos-1)/CHUNKSIZE; j=(pos-1)%CHUNKSIZE; p=(*S).head; if(pos==1) { t.tail->next=(*S).head; (*S).head=t.head; } else if(j==0) { for(k=1;k<i;k++) p=p->next; q=p->next; p->next=t.head; t.tail->next=q; if(q==NULL) (*S).tail=t.tail; } else { for(k=1;k<=i;k++) p=p->next; q=(Chunk*)malloc(sizeof(Chunk)); for(i=0;i<j;i++) *(q->ch+i)=blank; for(i=j;i<CHUNKSIZE;i++) { *(q->ch+i)=*(p->ch+i); *(p->ch+i)=blank; } q->next=p->next; p->next=t.head; t.tail->next=q; } (*S).curlen+=t.curlen; Zip(S); return OK; } Status StrDelete(LString *S,int pos,int len) { int i=1; Chunk *p=(*S).head; int j=0; if(pos<1||pos>(*S).curlen-len+1||len<0) return ERROR; while(i<pos) { while(*(p->ch+j)==blank) { j++; if(j==CHUNKSIZE) { p=p->next; j=0; } } i++; j++; if(j==CHUNKSIZE) { p=p->next; j=0; } }; while(i<pos+len) { while(*(p->ch+j)==blank) { j++; if(j==CHUNKSIZE) { p=p->next; j=0; } } *(p->ch+j)=blank; i++; j++; if(j==CHUNKSIZE) { p=p->next; j=0; } }; (*S).curlen-=len; return OK; } Status Replace(LString *S,LString T,LString V) { int i=1; if(StrEmpty(T)) return ERROR; do { i=Index(*S,T,i); if(i) { StrDelete(S,i,StrLength(T)); StrInsert(S,i,V); i+=StrLength(V); } }while(i); return OK; } void StrPrint(LString T) { int i=0,j; Chunk *h; h=T.head; while(i<T.curlen) { for(j=0;j<CHUNKSIZE;j++) if(*(h->ch+j)!=blank) { printf("%c",*(h->ch+j)); i++; } h=h->next; } printf("\n"); } void DestroyString() { } int main() { char *s1="ABCDEFGHI", *s2="12345", *s3="", *s4="asd#tr", *s5="ABCD"; Status k; int pos,len; LString t1,t2,t3,t4; InitString(&t1); InitString(&t2); printf("===============分隔符=========================\n"); printf("初始化串t1后，串t1空否？%d (1:空 0:否) 串长=%d\n",StrEmpty(t1),StrLength(t1)); k=StrAssign(&t1,s3); if(k==OK) { printf("s3赋值给串t1为: \n"); StrPrint(t1); } else printf("s3赋值给串t1出错\n"); k=StrAssign(&t1,s4); if(k==OK) { printf("s4赋值给串t1为: \n"); StrPrint(t1); } else printf("s4赋值给串t1出错\n"); k=StrAssign(&t1,s1); if(k==OK) { printf("s1赋值给串t1为: "); StrPrint(t1); } else printf("s1赋值给串t1出错\n"); printf("串t1空否？%d(1:空 0:否) 串长=%d\n",StrEmpty(t1),StrLength(t1)); printf("初始化s2赋值给t2。\n"); StrAssign(&t2,s2); printf("串t2为: "); StrPrint(t2); StrCopy(&t3,t1); printf("由串t1拷贝得到串t3,串t3为: "); StrPrint(t3); InitString(&t4); printf("初始化s5赋值给t4。\n"); StrAssign(&t4,s5); printf("串t4为: "); StrPrint(t4); Replace(&t3,t4,t2); printf("===============分隔符=========================\n"); printf("用t2取代串t3中的t4串后，串t3为: "); StrPrint(t3); ClearString(&t1); printf("===============分隔符=========================\n"); printf("清空串t1后，串t1空否？%d(1:空 0:否) 串长=%d \n",StrEmpty(t1),StrLength(t1)); Concat(&t1,t2,t3); printf("===============分隔符=========================\n"); printf("串t1(=t2+t3)为: "); StrPrint(t1); Zip(&t1); printf("去除不必要的占位符后，串t1为: "); StrPrint(t1); pos=Index(t1,t3,1); printf("pos=%d\n",pos); printf("===============分隔符=========================\n"); printf("在串t1的第pos个字符之前插入串t2，请输入pos: "); scanf("%d",&pos); k=StrInsert(&t1,pos,t2); if(k) { printf("插入串t2后，串t1为: "); StrPrint(t1); } else printf("插入失败！\n"); return 0; }

最新回复(0)