数据结构之串

1、串的概念
字符串简称串，是一种特殊的线性表，它的数据元素仅由一个字符组成。

2、串的定义
串(String)是由零个或多个字符组成的有限序列，又称字符串。

这里写图片描述

其中s是串名,用双引号括起来的字符序列为串值，但引号本身并不属于串的内容。ai(1<=i<=n)是一个任意字符,它称为串的元素,是构成串的基本单位，i是它在整个串中的序号；n为串的长度,表示串中所包含的字符个数。

3、术语描述
(1)长度–串中字符的个数，称为串的长度。
(2)空串–长度为零的字符串称为空串。
(3)空格串–由一个或多个连续空格组成的串称为空格串。
(4)串相等–两个串相等，是指两个串的长度相等且对应的字符都相等。
(5)自串–串中任意连续的字符组成的子序列称为该串的子串。
(6)主串–包含子串的串为该子串的主串。
(7)模式匹配–子串的定位运算又称为模式匹配，是一个求子串的队医给字符在主串中序号的运算。被匹配的主串称为目标串，子串称为模式。

例子1：字符串的长度及子串的位置。
字符串
S1=“SHANG”
S2=“HAI”
S3=“SHANGHAI”
S4=SHANG HAI"
S1是S3、S4的子串，S1在S3、S4中的位置都为1。
S2也是S3、S4的子串，S2在S3中的位置为6；S2在S4中的位置为7。

4、串的表示和实现
因为串是数据元素类型为字符型的线性表，所以用于线性表的存储方式仍适合与串。但是由于串中的数据元素是单个字节，其存储方式又有其特殊之处。

4-1、定长顺序存储
类似于线性表，可以用一组地址连续的存储单元依次存放串中的各个字符序列，利用存储单元地址的顺序表示串中字符的相邻关系。

4-1-1 定长存储的C语言描述
在C语言中，字符串顺序存储可以用一个字符型数组和一个整型变量表示，其中字符数量足存储串值，整型变量表示串的长度。


#define MAXLEN 10
typedef struct
{char vec[MAXLEN];int len;
} Str;//可用Str来定义该类型的结构体变量

4-1-2 存储方式
当计算机按字节(Byte)为单位便地址时，一个存储单元刚好存储一个字符,串中相邻的字符顺序地存储在地址相邻的存储单元中.
当计算机按字(例如1字32为)为单位便地址时，一个存储单元可以有4个字节组成。此时顺序存储结构又有非紧凑格式和紧凑格式两种存储方式。

(1)非紧凑格式
设S=“String Structure”,计算机字长为32为(4个Byte)，使用非紧凑格式一个地址只能存储一个字符，如图5-1所示。优点是运算处理简单，但缺点是存储空间十分浪费。

这里写图片描述

(2)紧凑格式
同样存储S=“String Structure”，使用紧凑格式格式一个地址能存四个字符，如图5-2所示。紧凑存储的优点是空间利用率高，缺点是对串中字符处理的效率低。

4-2、链式存储
对于长度不确定的字符串的输入，若采用定长字符串存储就会产生这样的问题:存储空间定的大，而实际输入字符串长度小，则造成内存空间的浪费，反之，存储空间定的小，而实际输入字符串长度大，则存储空间不够用。此时可采用链接存储的方法。

4-2-1 链式存储的描述
用链表存储字符串，每个结点有两个域：一个是数据域(data)和一个指针域(next)。

这里写图片描述

其中数据域(data)–存储串中的字符。
指针域(next)–存放后继结点的地址。
仍然以存储S=“String Structure” 为例，链式存储结构如图所示。

这里写图片描述

(1)链式存储的优点–插入、删除运算方法；
(2)链式存储的缺点==存储，检索效率较低。

由于字符串的特殊性，用链表存作为字符串的存储方式也不太实用，因此使用较少。

4-3 、串的堆分配存储结构
在实际应用中，玩玩要定义很多字符串，并且各字符串长度在定义之前又无法确定。在这种情况下，可以采用堆分配存储(也称为索引存储)，这是一种动态存储结构。

4-3-1 堆分配存储的方法
(1)开辟一块地址连续的存储空间，用于存储各串的值，该存储空间称为"堆"(也称自由存储区)
(2)另外建立一个索引表，用来存储串的名称(name),长度(length)和该串在"堆"中存储的起始地址(Start)。
(3)程序执行过程中,每产生一个串，系统就从"堆"中分配一快大小与串的长度相同的连续的空间，用于存储该串的值，并且在索引表中增加一个索引项，用于登记该串的名称、长度、和该串的起始地址。

4-3-2 索引存储的例子
设字符串:A=“Red” B=“Yellow” C=“Blue” D=“White”
用指针free指向堆中的未使用空间的首地址。
索引表如图5-5所示

这里写图片描述

考虑到对字符串的插入和删除操作，可能引起字符串的长度变化，在“堆”中为串值的分配空间是，可预留适当的空间。这时，索引表的索引项应增加一个域，用于存储该串在“堆”中拥有的实际存储单元的数量。当字符串长度等于该串的实际存储单元时，就不能对串进行插入操作。

4-3-3 带长度的索引表的C语言描述
如图5-5所示，索引项的结点类型为:

#define MAXLEN 10
typedef struct
{char name[MAXLEN];//串名int length;//串长char *Stradr;//起始地址
} LNode

5、串的基本运算

(1)、求串长LenStr(s)
操作条件:串s存在。
操作结果:求出串s的长度。

(2)、串连接ConcatStr(s1,s2)
操作条件:串s1,s2存在。
操作结果:新串s1是串s1和串s2连接以后的新串，原串s2值不变，串s1的值则改变。
例子:设s1=“Micsosoft”，s2=“Office”。
操作结果是s1=“MicsosoftOffice”; s2=“Office”。

(3)、求子串SubStr(s,i,len)
操作条件:串s存在。
操作结果:返回从串s的第i个字符开始的长度为len的子串。len=0得到的是空串。
例子:SubStr(“abcdefghi”,3,4)=“cdef”。

(4)、串比较EqualStr(s1,s2)
操作条件:串s1,s2存在。
操作结果:若s1等于s2,返回值为0；若s1小于s2，返回值小于0; 若s1大于s2，返回值大于0。

(5)、子串查找IndexStr(s,t)
找子串t在主串s中首次出现的位置(也称模式匹配)
操作条件:串s,t存在。
操作结果:若t是s的子串，则返回在s中首次出现的位置，否则返回值为0。
例子:子串定位
IndexStr(“abcdebda”,“bc”)=2;
IndexStr(“abcdebda”,“ba”)=0;

(6)、串插入InsStr(s,t,i)
操作条件:串s,t存在。
操作结果:将串t插入到串s中的第i个字符前，s的串值发生改变。

(7)、串删除DelStr(s,i,len)
操作条件:串s存在。
操作结果:删除串s中第i个字符起长度为len的子串,s的值改变。

6、使用定长顺序串的结构代码实现操作

6-1、串结构体定义


#define MAXLEN 10//定义窜的最大长度typedef struct
{char vec[MAXLEN];int len;//串的实际长度
} Str;//可用Str来定义该类型的结构体变量

在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。比如C语言中处理定长串的方法就是这样的，它是用‘\0’表示串的结束，如图5-6所示。

这里写图片描述

(1) 求串的长度
用判断当前字符是有是‘\0’来确定串是否结束，若非‘\0’，则表示字符串长度的i增加1；若是‘\0’，则表示字符串结束，跳出循环，i即字符串的长度。

int LenStr(Str *r){int i=0;while(r->vec[i]!='\0'){i++;}return i;
}

测试代码如下:


void ShowStr(Str *r){printf("\n\t\t该串值为: ");if(r->vec[0]=='\0'){printf("空串! \n");}else{puts(r->vec);//使用puts函数输出字符串,格式为 puts(字符串组名)}
}
int main()
{Str a;Str *r=&a;r->vec[0]='\0';char choice;int ch=1;while(ch!=0){printf("\n");printf("\n\t\t        串子系统                  *");scanf("%c",&choice);getchar();if(choice=='1'){printf("\n\t\t请输入一个字符串: ");gets(r->vec);//使用get函数输入字符串 格式为 gets(字符串组名)r->len=LenStr(r);}else if(choice=='8'){ShowStr(r);int n=LenStr(r);printf("串长度为:%d",n);}}return 0;
}

测试结果:

这里写图片描述

(2) 串连接
把两个串r1和r2首尾连接成一个新串r1,即：r1=r1+r2。

void ConcatStr(Str *r1,Str *r2){int i;printf("\n\t\t r1=%s  r2=%s\n",r1->vec,r2->vec);if(r1->len+r2->len>MAXLEN){printf("两个串太长,溢出! ");//连接后的串长超过串的最大长度}else{for( i=0;i<r2->len;i++){r1->vec[r1->len+i]=r2->vec[i];//进行连接}r1->vec[r1->len+i]='\0';r1->len=r1->len+r2->len;//修改连接后的新串的长度}printf("\n\t\t r1=%s  r2=%s\n",r1->vec,r2->vec);}

测试代码如下:


int main()
{Str a,b;Str *r=&a,*r1;r->vec[0]='\0';char choice;int ch=1;while(ch!=0){printf("\n");printf("\n\t\t        串子系统                  *");scanf("%c",&choice);getchar();if(choice=='1'){printf("\n\t\t请输入一个字符串: ");gets(r->vec);//使用get函数输入字符串 格式为 gets(字符串组名)r->len=LenStr(r);}else if(choice=='2'){printf("\n\t\t请输入所要连接字符串: ");r1=CreateStr(&b);printf("\n\t\tr1为: ");puts(r1->vec);ConcatStr(r,r1);printf("\n\t\t连接后的新串值为: ");puts(r->vec);int n=LenStr(r);printf("新串长度为:%d",n);}else if(choice=='8'){ShowStr(r);int n=LenStr(r);printf("串长度为:%d",n);}}return 0;
}

测试结果:

这里写图片描述

(3) 求子串
在给定的字符串r中从指定位置i开始连续取出j个字符构成子串r1。

void SubStr(Str *r,Str *r1,int i ,int j){if(i+j-1>MAXLEN){printf("子串越界! ");}else{for(int k=0;k<j;k++){r1->vec[k]=r->vec[i+k-1];//从r中取出子串}r1->len=j;r1->vec[r1->len]='\0';}printf("\n\t\t 取出字符为r1=%s ",r1->vec);
}

测试代码如下:

else if(choice=='3'){printf("\n\t\t请输入从第几个字符开始: ");scanf("%d",&i);getchar();printf("\n\t\t请输入取出的连续字符数: ");scanf("%d",&j);getchar();SubStr(r,&a,i ,j);}

测试结果:

这里写图片描述

(4) 串比较
两个串的长度相等且各对应位置上的字符都相同时，两个串才相等。

int EqualStr(Str *r1,Str *r2){printf("\n\t\t r1=%s  r2=%s\n",r1->vec,r2->vec);int i=0;while(r1->vec[i]==r2->vec[i]&&r1->vec[i]!='\0'&&r2->vec[i]!='\0')i++;if(r1->vec[i]==r2->vec[i])return 0;else if(r1->vec[i]>r2->vec[i])return 1;elsereturn -1;}

测试代码如下:

else if(choice=='7'){printf("\n\t\t请输入第一个串: ");gets(c.vec);printf("\n\t\t请输入第二个串: ");gets(d.vec);int k=EqualStr(&c,&d);if(k>0){printf("\n\t\t第一个串大! \n");}else if(k<0){printf("\n\t\t第二个串大! \n");}else {printf("\n\t\t两个串一样大! \n");}}

测试结果:

这里写图片描述

(5) 插入子串
在字符串r中的指定位置i插入子串r1。

Str *InsStr(Str *r,Str *r1,int i){printf("\n\t\t r=%s  r1=%s\n",r->vec,r1->vec);if(i>r->len||r->len+r1->len>MAXLEN){printf("不能插入!");}else{for(int k=r->len-1;k>=i;k--){r->vec[r1->len+k]=r->vec[k];//后移空出的位置}for(int k=0;k<r1->len;k++){r->vec[i+k]=r1->vec[k];//插入子串}r->len=r->len+r1->len;r->vec[r->len]='\0';}printf("\n\t\t 插入后的新串 r=%s \n",r->vec);return r;
}

测试代码如下:

else if(choice=='5'){printf("\n\t\t请输入在第几个字符前插入: ");scanf("%d",&i);getchar();printf("\n\t\t请输入所要插入的字符串: ");r1=CreateStr(&b);Str *newStr=InsStr(r,r1,i-1);printf("\n\t\t新串值为: ");puts(newStr->vec);}

测试结果:

这里写图片描述

(6) 删除子串
在给定的字符串r中删除从指定位置i开始连续的j个字符。


void DelStr(Str *r,int i ,int j){if(i+j-1>r->len){printf("所要删除的字符串越界！");}else{for(int k=i+j;k<r->len;k++,i++){r->vec[i]=r->vec[k];//将后面的字符串前移覆盖}r->len=r->len-j;r->vec[r->len]='\0';}printf("\n\t\t 删除后的新串 r=%s \n",r->vec);}

测试代码如下:

else if(choice=='4'){printf("\n\t\t请输入从第几个字符开始: ");scanf("%d",&i);getchar();printf("\n\t\t请输入删除的连续字符数: ");scanf("%d",&j);getchar();DelStr(r,i ,j);}

测试结果

这里写图片描述

(7) 查找子串

int IndexStr(Str *r,Str *r1){printf("\n\t\t r=%s  r1=%s\n",r->vec,r1->vec);int i,j,k;for(i=0;r->vec[i];i++){for(j=i,k=0;r->vec[j]==r1->vec[k];j++,k++){if(!r1->vec[k+1]){return i;}return -1;}}
}

测试代码如下:

else if(choice=='6'){printf("\n\t\t请输入所要查找的字符串: ");r1=CreateStr(&b);i=IndexStr(r,r1);if(i!=-1){printf("\n\t\t第一次出现的位置是第%d个.\n ",i+1);}else{printf("\n\t\t该子串不在其中!");}

测试结果:

这里写图片描述

7、串子系统完整代码

#include<iostream>
using namespace std;
#define MAXLEN 100//定义窜的最大长度typedef struct
{char vec[MAXLEN];int len;//串的实际长度
} Str;//可用Str来定义该类型的结构体变量int LenStr(Str *r){int i=0;while(r->vec[i]!='\0'){i++;}return i;
}
Str *CreateStr(Str *r){gets(r->vec);r->len=LenStr(r);return r;
}void ShowStr(Str *r){printf("\n\t\t该串值为: ");if(r->vec[0]=='\0'){printf("空串! \n");}else{puts(r->vec);//使用puts函数输出字符串,格式为 puts(字符串组名)}
}void ConcatStr(Str *r1,Str *r2){int i;printf("\n\t\t r1=%s  r2=%s\n",r1->vec,r2->vec);if(r1->len+r2->len>MAXLEN){printf("两个串太长,溢出! ");//连接后的串长超过串的最大长度}else{for( i=0;i<r2->len;i++){r1->vec[r1->len+i]=r2->vec[i];//进行连接}r1->vec[r1->len+i]='\0';r1->len=r1->len+r2->len;//修改连接后的新串的长度}printf("\n\t\t r1=%s  r2=%s\n",r1->vec,r2->vec);}void SubStr(Str *r,Str *r1,int i ,int j){if(i+j-1>MAXLEN){printf("子串越界! ");}else{for(int k=0;k<j;k++){r1->vec[k]=r->vec[i+k-1];//从r中取出子串}r1->len=j;r1->vec[r1->len]='\0';}printf("\n\t\t 取出字符为r1=%s ",r1->vec);
}int EqualStr(Str *r1,Str *r2){printf("\n\t\t r1=%s  r2=%s\n",r1->vec,r2->vec);int i=0;while(r1->vec[i]==r2->vec[i]&&r1->vec[i]!='\0'&&r2->vec[i]!='\0')i++;if(r1->vec[i]==r2->vec[i])return 0;else if(r1->vec[i]>r2->vec[i])return 1;elsereturn -1;}Str *InsStr(Str *r,Str *r1,int i){printf("\n\t\t r=%s  r1=%s\n",r->vec,r1->vec);if(i>r->len||r->len+r1->len>MAXLEN){printf("不能插入!");}else{for(int k=r->len-1;k>=i;k--){r->vec[r1->len+k]=r->vec[k];//后移空出的位置}for(int k=0;k<r1->len;k++){r->vec[i+k]=r1->vec[k];//插入子串}r->len=r->len+r1->len;r->vec[r->len]='\0';}printf("\n\t\t 插入后的新串 r=%s \n",r->vec);return r;
}void DelStr(Str *r,int i ,int j){if(i+j-1>r->len){printf("所要删除的字符串越界！");}else{for(int k=i+j;k<r->len;k++,i++){r->vec[i]=r->vec[k];//将后面的字符串前移覆盖}r->len=r->len-j;r->vec[r->len]='\0';}printf("\n\t\t 删除后的新串 r=%s \n",r->vec);}int IndexStr(Str *r,Str *r1){printf("\n\t\t r=%s  r1=%s\n",r->vec,r1->vec);int i,j,k;for(i=0;r->vec[i];i++){for(j=i,k=0;r->vec[j]==r1->vec[k];j++,k++){if(!r1->vec[k+1]){return i;}return -1;}}
}int main()
{Str a,b,c,d;Str *r=&a,*r1;r->vec[0]='\0';char choice,p;int i,j, ch=1;while(ch!=0){printf("\n");printf("\n\t\t        串子系统                  *");printf("\n\t\t************************************");printf("\n\t\t*   1------输入字符串      *");printf("\n\t\t*   2------连接字符串      *");printf("\n\t\t*   3------取出子串      *");printf("\n\t\t*   4------删除子串      *");printf("\n\t\t*   5------插入子串      *");printf("\n\t\t*   6------查找子串      *");printf("\n\t\t*   7------比较串大小      *");printf("\n\t\t*   8------显示字符串      *");printf("\n\t\t*   0------返      回      *");printf("\n\t\t************************************");printf("\n\t\t请选择菜单号(0-8)：    *");scanf("%c",&choice);getchar();if(choice=='1'){printf("\n\t\t请输入一个字符串: ");gets(r->vec);//使用get函数输入字符串 格式为 gets(字符串组名)r->len=LenStr(r);}else if(choice=='2'){printf("\n\t\t请输入所要连接字符串: ");r1=CreateStr(&b);printf("\n\t\tr1为: ");puts(r1->vec);ConcatStr(r,r1);printf("\n\t\t连接后的新串值为: ");puts(r->vec);int n=LenStr(r);printf("新串长度为:%d",n);}else if(choice=='3'){printf("\n\t\t请输入从第几个字符开始: ");scanf("%d",&i);getchar();printf("\n\t\t请输入取出的连续字符数: ");scanf("%d",&j);getchar();SubStr(r,&a,i ,j);}else if(choice=='4'){printf("\n\t\t请输入从第几个字符开始: ");scanf("%d",&i);getchar();printf("\n\t\t请输入删除的连续字符数: ");scanf("%d",&j);getchar();DelStr(r,i ,j);}else if(choice=='5'){printf("\n\t\t请输入在第几个字符前插入: ");scanf("%d",&i);getchar();printf("\n\t\t请输入所要插入的字符串: ");r1=CreateStr(&b);Str *newStr=InsStr(r,r1,i-1);printf("\n\t\t新串值为: ");puts(newStr->vec);}else if(choice=='6'){printf("\n\t\t请输入所要查找的字符串: ");r1=CreateStr(&b);i=IndexStr(r,r1);if(i!=-1){printf("\n\t\t第一次出现的位置是第%d个.\n ",i+1);}else{printf("\n\t\t该子串不在其中!");}}else if(choice=='7'){printf("\n\t\t请输入第一个串: ");gets(c.vec);printf("\n\t\t请输入第二个串: ");gets(d.vec);int k=EqualStr(&c,&d);if(k>0){printf("\n\t\t第一个串大! \n");}else if(k<0){printf("\n\t\t第二个串大! \n");}else {printf("\n\t\t两个串一样大! \n");}}else if(choice=='8'){ShowStr(r);int n=LenStr(r);printf("串长度为:%d",n);}else if(choice=='0'){break;}else{printf("\n\t\t请注意:输入有误! \n");if(choice!='X'&&choice!='x'){printf("\n\t\t按回车键继续，按任意键返回主菜单 \n");p=getchar();if(p!='\xA'){getchar();break;}}}}return 0;
}

效果图:

这里写图片描述
Flutter电商实战项目：https://github.com/dechengyang/ydc_flutter_app