串（String）是计算机科学中的一个基本概念，指的是由零个或多个字符组成的有限序列。以下是串的一些核心知识点总结：

1. 定义与表示：
   • 串是由字符组成的序列，可以是空串（没有任何字符）。
   • 串的表示方法多样，如定长数组、动态数组（如C的char[]或C++的std::string）、链表等。
2. 基本操作：
   • 创建与销毁：生成新串或释放已存在的串所占用的资源。
   • 赋值：将一个串的值赋给另一个串。
   • 比较：判断两个串是否相等，或比较它们的字典序。
   • 连接：将两个或多个串合并成一个新串。
   • 查找：在一个串中搜索另一个子串或字符的位置。
   • 替换：在串中查找并替换指定的子串或字符。
   • 长度计算：计算串中字符的个数。
3. 存储结构：
   • 顺序存储：如定长数组，访问速度快，但空间利用率可能不高。
   • 链式存储：如链表，便于动态调整串的长度，但访问速度相对较慢。
4. 模式匹配：
   • 朴素算法：直接比较子串与主串，时间复杂度较高。
   • KMP算法：利用部分匹配表加速匹配过程，提高效率。
   • Boyer-Moore算法：从右向左扫描，利用坏字符和好后缀规则进行匹配。
5. 高级应用：
   • 正则表达式：用于描述和匹配字符串的复杂模式。
   • 文本压缩：如Huffman编码，利用字符频率进行压缩。
   • 文本搜索：如倒排索引，用于快速检索大量文本数据。
6. 性能优化：
   • 根据应用场景选择合适的存储结构和算法。
   • 利用哈希表、后缀数组等数据结构加速查找和匹配过程。
   • 通过并行处理等技术提高处理速度。

串在计算机科学中扮演着重要角色，是文本处理、数据搜索、网络通信等领域不可或缺的基础工具。

#include<stdio.h> #define MaxSize 100 typedef struct { char data[MaxSize]; int length; }sqstring;//申明顺序串类型 void strassign(sqstring &s, const char cstr[]) { int i; for(int i=0;cstr[i]!='\0'&&i<MaxSize-1;i++) { s.data[i] = cstr[i]; } s.data[i] = '\0'; // 确保字符串以空字符结尾 s.length = i; //s.data[i] =cstr[i]; //s.length=i; }//将字符串常量赋值给串s void destroystr(sqstring &s) {} //销毁 void strcopy(sqstring &s,sqstring t) { for(int i=0;i<t.length;i++) s.data[i]=t.data[i]; s.length=t.length; }//串复制 bool strequal(sqstring s,sqstring t) { bool same =true; if(s.length!=t.length) same =false; else for(int i=0;i<s.length;i++) if(s.data[i]!=t.data[i]) { same=false; break; } return same; } //判断串是否相等 int strlength(sqstring s) { return s.length; } sqstring concat(sqstring s,sqstring t) { sqstring str; int i; str.length=s.length+t.length; for(int i=0;i<s.length;i++) str.data[i]=s.data[i]; for(int i=0;i<t.length;i++) str.data[s.length+i]=t.data[i]; return str; }//串连接 sqstring substr(sqstring s,int i,int j) { sqstring str; int k; str.length=0; if(i<=0||i>s.length||j<0||i+j-1>s.length) return str;//参数不正确返回空串 for(k=i-1;k<i+j-1;k++) //s.data[i...i+j]->str str.data[k-i+1]=s.data[k]; str.length=j; return str; } //求子串 sqstring insstr(sqstring s1,int i,sqstring s2) { int j;sqstring str; str.length=0; if(i<=0||i>s1.length+1) return str; for(j=0;j<i-1;j++) str.data[j]=s1.data[j]; for(j=0;j<s2.length;j++) str.data[i+j-1]=s2.data[j]; for(j=i-1;j<s1.length;j++) str.data[s2.length+j]=s1.data[j]; str.length=s1.length+s2.length; return str; } //插入子串 sqstring delstr(sqstring s,int i,int j) { int k;sqstring str; str.length=0; if(i<=0||i>s.length+1) return str; for(k=0;k<i-1;k++) str.data[k]=s.data[k]; for(k=i+j-1;k<s.length;k++) str.data[k-j]=s.data[k]; str.length=s.length-j; return str; } //删除子串 sqstring repstr(sqstring s,int i,int j,sqstring t) { int k;sqstring str; str.length=0; if(i<=0||i>s.length+1||i+j>s.length+1) return str; for(k=0;k<i-1;k++) str.data[k]=s.data[k]; for(k=0;k<t.length;k++) str.data[i+k-1]=t.data[k]; for(k=i+j-1;k<s.length;k++) str.data[t.length+k-j]=s.data[k]; str.length=s.length-j+t.length; return str; }//替换子串 void dispstr(sqstring s) { if(s.length>0) { for(int i=0;i<s.length;i++) printf("%c",s.data[i]); printf("\n"); } } int main() { sqstring s,s1,s2,s3,s4; char temp1[MaxSize] = "abcdefghijklmn"; // 使用字符数组而不是字符串常量 char temp2[MaxSize] = "123"; // 使用字符数组而不是字符串常量 printf(".顺序串的基本运算如下：\n"); printf("1.建立串s和串:s1\n"); strassign(s,temp1); strassign(s1,temp2); //strassign(s,"abcdef"); //strassign(s1,"123"); printf("2.输出串s：\n"); dispstr(s); printf("3.串的长度：%d\n",strlength(s)); printf("4.串s第9个字符位置插入串s1产生串s2:\n"); s2=insstr(s,9,s1); printf("5.输出串s2:\n"); dispstr(s2); printf("6.删除串s第2个字符开始的5个字符产生串s2:\n"); s2=delstr(s,2,3); printf("7.输出串s2:\n"); dispstr(s2); printf("8.串s第2个字符开始的5个字符替换成串s1而产生串s2:\n"); s2=repstr(s,2,5,s1); printf("9.输出串s2:\n"); dispstr(s2); printf("10.提取串s2的第2个字符开始的10个字符而产生串s3:\n"); s3=substr(s,2,10); printf("11.输出串s3:\n"); dispstr(s3); printf("12.将串s1和串s2连接产生串s4:\n"); s4=concat(s1,s2); printf("13.输出串s4:\n"); dispstr(s4); destroystr(s); destroystr(s1); destroystr(s2); destroystr(s3); destroystr(s4); return 0; }