数据结构学习，串篇（顺序串及算法）

作者：IC00

2022-10-14
湖南
本文字数：4367 字
阅读完需：约 14 分钟

前言：

前面我们把栈和队列已经学的差不多了，今天来复习一下，数据结构的串，串的存储结构，在 Java 里面是有 String 类型的，但是 C 语言里面是没有的，需要自己封装一下，再进行操作。串是由零个或多个字符组成的有限序列，串长度为零我们称为空串，它不含任何字符。在学习串我们只要学习，串的算法，例如复制，连接，判断相等，求子串之类的算法。

每日一遍，心情愉悦

（你们应该没有这样的损友吧，😂😂😂）

1.顺序串

顺序串的存储结构的和线性表一样，也是主要分为顺序存储结构和链式存储结构两类，前者简称顺序串，顺序串和顺序表一样，只不过它的每个元素仅由一个字符组成，我们在学串的时候更多的是学习和串相关的算法。

1.1 顺序串的初始化

#include <iostream>#include <stdio.h>#include <stdlib.h>#define MaxSize 100typedef struct{  char data[MaxSize];//设置串的大小  int length;//获取串的长度}SqString;void Assign(SqString &s,char str[])/串的写入，就相当于我们循环输入一样{  int i=0;  while(str[i]!='\0')//字符串一‘\0结尾’  {    s.data[i] = str[i];//给结构体char数组赋值    i++;  }  s.length=i;//字符串长度获取}

复制代码

1.2 顺序串基本的算法：

1.2.1 顺序串字符串复制

字符串复制是很简单的只要，再创建一个串，然后遍历赋值实现复制效果。

void StrCopy(SqString &s,SqString t)//复制函数{  int i;//下标  for(i=0;i<t.length;i++)//循环遍历赋值    s.data[i]= t.data[i];//赋值，将t的值赋值给s  s.length=t.length;//赋值字符串长度}

复制代码

1.2.2 字符串求字符串长度

方法思路：遍历字符串，退出条件不等于‘\0’，然后累加返回值。

int StrLength(SqString s){  return s.length;//博主这里的结构体是有length字段的，所以只要返回它的值，如果你没有这个字段你可以遍历值然后返回}

复制代码

1.2.3 判断两个字符串是否相等

int StrEqual(SqString s,SqString t)//判断两个字符串是不是一样的{  int i=0;  if(s.length!=t.length){//判断两个字符串的长度是否相等    return 0;  }  else{    for(i=0;i<s.length;i++)//循环遍历，因为两个长度是一致的所以用那个字符串的length都是一样的    {       if(s.data[i]!=t.data[i])//如果不相同就返回0，直到遍历完，没有返回0就说明是相同的就返回1       {         return 0;       }    }    return 1;  }}

复制代码

1.2.4 两个字符串的连接

博主有两个方法，博主只展示了一个简单的方法，采用第三方赋值实现，当然还是有其他的方法的，例如我们可以用一个循环在 S3 的 Length 的位置遍历 S1 的串进行赋值，相当于把 S1 直接接在 S3 后面，实现像追加的连接。

SqString Concat(SqString s,SqString t){  SqString r;//新建立的字符串用来保存s和t这两个字符串  int i,j;  for(i=0;i<s.length;i++)//遍历s字符串  {    r.data[i]=s.data[i];//赋值  }  for(j=0;j<t.length;j++)//遍历t字符串  {    r.data[s.length+j]=t.data[j];//赋值，s.length+j表示相当于在s后面追加一样的效果   }    r.length=i+j;//新字符的长度，两个字符串的和   return r;}

复制代码

1.2.4 获取字符串的子串

就是获取从莫个位置到莫个位子的子串

SqString SubStr(SqString s,int i,int j){  SqString t;  int k,n=0;  if(i<1||i>s.length ||j<1||i+j>s.length+1)//判断起始值要大于1，虽然我们的下标第一个是0，但是我们在生活中都是从一开始，起始值不能大于长度，结束值不能小于起始值，两个值的和不能大于最大长度，j是可以大于长度的  {    t.length=0;  }  else{    for(k=i-1;k<i+j;k++)//i-1代表有个下标差    {      t.data[n++]=s.data[k];//赋值    }    t.length = n;//我们用了一个n来保存长度值  }  return t;}

复制代码

1.2.5 查找子串在母串中的位置

返回子串在母串的位置，若子串不是母串的子串就返回 0，是子串就返回母串中子串的第一个逻辑序号。

int Index(SqString s,SqString t)//母串是s，子串是t{  int i=0,j=0;//分别记录子串和母串的下标  while(i<s.length&&j<t.length)//循环遍历直到两个i和j大于他们的长度  {    if(s.data[i]==t.data[j])//相等就一起加一    {      i++;      j++;    }    else{    //代表没有完全匹配子串，      i=i-j+1;//代表假设这个只匹配子串部分的，没有完全匹配，但是我们的母串已经往下移到了，所以要加上之前匹配的位移数。      j=0;//子串重新位移    }  }  if(j>=t.length)//完全匹配了就会退出循环，所i有判断j是不是大于子串的长度  {    return i-t.length+1;//因为i和j是同时移动的所以要减去子串的长度+1,或者减去j也是可以的，是一样的  }  else  {    return 0;  }}

复制代码

1.2.6 字符串的插入

将一个字符串插入指定位置

int InsStr(SqString &s,int i,SqString t)//代表往后移的字符串，i代表指定位置，t代表插入的值{  int j;  if(i<1||i>s.length+1)//不能比起始小，不能比结束大  {    return 0;  }  else{    for(j=s.length-1;j>=i-1;j--)      {      s.data[j+t.length]=s.data[j];//后移t.length位置    }    for(j=0;j<t.length;j++)//插入子串的t    {      s.data[i+j-1]=t.data[j];    }    s.length = s.length+t.length;//修改长度    return 1;  }}

复制代码

1.2.7 字符串中子串删除

指定子串位置进行删除。

int DelStr(SqString &s,int i,int j)//s代表字符串，i表示起始位置，j表示i之后多少个{  int k;  if(i<1||i>s.length||j<1||i+j>s.length+1)//位置参数如果有误  {    return 0;  }  else{    for(k = i+j-1;k<s.length;k++)//将s的第i+j位置之后的往前移动j位    {      s.data[k-j] =s.data[k];    }    s.data[s.length-j]='\0';//避免之前位置的值还在    s.length = s.length-j;//修改s的长度    return 1;  }}

复制代码

1.2.8 字符串的子串替换

将母串中指定的子串替换成另一个子串，形成一个新的字符串。

SqString RepStrAll(SqString s,SqString s1,SqString s2) //s代表母串，s1代表母串中的被替换的子串，s2代表替换s中s1的子串{  int i;  i= Index(s,s1);  while(i>0)  {    DelStr(s,i,s1.length); //从s中删除子串s1    InsStr(s,i,s2);//在s中插入子串s2    i = Index(s,s1);   }    return s;}

复制代码

整体代码和效果展示

#include <iostream>#include <stdio.h>#include <stdlib.h>#define MaxSize 100typedef struct{  char data[MaxSize];  int length;}SqString;
void Assign(SqString &s,char str[]){  int i=0;  while(str[i]!='\0')  {    s.data[i] = str[i];    i++;  }  s.length=i;}
void StrCopy(SqString &s,SqString t){  int i;  for(i=0;i<t.length;i++)    s.data[i]= t.data[i];  s.length=t.length;}
int StrLength(SqString s){  return s.length;}
int StrEqual(SqString s,SqString t){  int i=0;  if(s.length!=t.length){    return 0;  }  else{    for(i=0;i<s.length;i++)    {       if(s.data[i]!=t.data[i])       {         return 0;       }    }    return 1;  }}
SqString Concat(SqString s,SqString t){  SqString r;  int i,j;  for(i=0;i<s.length;i++)  {    r.data[i]=s.data[i];  }  for(j=0;j<t.length;j++)  {    r.data[s.length+j]=t.data[j];   }    r.length=i+j;   return r;}
SqString SubStr(SqString s,int i,int j){  SqString t;  int k,n=0;  if(i<1||i>s.length ||j<1||i+j>s.length+1)  {    t.length=0;  }  else{    for(k=i-1;k<i+j;k++)    {      t.data[n++]=s.data[k];    }    t.length = j;  }  return t;}
int Index(SqString s,SqString t){  int i=0,j=0;  while(i<s.length&&j<t.length)  {    if(s.data[i]==t.data[j])    {      i++;      j++;    }    else{      i=i-j+1;      j=0;    }  }  if(j>=t.length)  {    return i-t.length+1;  }  else  {    return 0;  }}int InsStr(SqString &s,int i,SqString t){  int j;  if(i<1||i>s.length+1)  {    return 0;  }  else{    for(j=s.length-1;j>=i-1;j--)    {      s.data[j+t.length]=s.data[j];    }    for(j=0;j<t.length;j++)    {      s.data[i+j-1]=t.data[j];    }    s.length = s.length+t.length;    return 1;  }}int DelStr(SqString &s,int i,int j){  int k;  if(i<1||i>s.length||j<1||i+j>s.length+1)  {    return 0;  }  else{    for(k = i+j-1;k<s.length;k++)    {      s.data[k-j] =s.data[k];    }    s.data[s.length-j]='\0';    s.length = s.length-j;    return 1;  }}SqString RepStrAll(SqString s,SqString s1,SqString s2) {  int i;  i= Index(s,s1);  while(i>0)  {    DelStr(s,i,s1.length);    InsStr(s,i,s2);    i = Index(s,s1);   }    return s;}void DispStr(SqString s){  int i;  for(i=0;i<s.length;i++)  printf("%c",s.data[i]);  printf("\n");}int main(int argc, char** argv) {   SqString s1,s2,s3,s4,s5,s6,s7;   Assign(s1,"IC");   printf("s1:");   DispStr(s1);   printf("s1的长度为:%d\n",StrLength(s1));   printf("s1复制到s2\n");  StrCopy(s2,s1);        printf("s2:");        DispStr(s2);        printf("s1和s2字符串%s\n",(StrEqual(s1,s2)==1?"相同":"不相同"));        Assign(s3,"666654321");        printf("s3:");        DispStr(s3);        printf("s1和s3连接生成s4:\n");        s4 = Concat(s1,s3);        printf("s4:");        DispStr(s4);        printf("s3[2...5]生成s5\n");        s5=SubStr(s3,2,4);        printf("s5:");        DispStr(s5);        Assign(s6,"543");   printf("s6:");   DispStr(s6);   printf("s6在s3中的位置：%d\n",Index(s3,s6));  printf("从s3中删除s2[3...6]字符\n");  DelStr(s3,3,4);        printf("s3:");        DispStr(s3);        printf("s4中将s6替换成s1生成s7\n");        s7 = RepStrAll(s4,s6,s1);        printf("s7:");        DispStr(s7);  return 0;}

复制代码

效果展示：

总结：

基本上顺序串的一些的简单算法就都介绍完了大家认真看是可以理解的，其实大家把逻辑理解了，做题和写代码根本没啥问题顺序串其实不怎么难，难的是我们的思路和逻辑，数据结构就是教大家学会逻辑，学会这些存储结构，方便大家对存储的理解，博主也只是关公门前刷大刀不自量力，哈哈哈！！！创作不易点赞关注哦！！！

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/4de13cfae33692718120723d4】。文章转载请联系作者。

IC00

关注

一个热爱生活，喜欢拍照的热血青年 2022-07-14 加入

一个想学习技术的小盆友，想努力更文，争取今年发100篇

发布

暂无评论

创作场景

数据结构学习，串篇（顺序串及算法）

前言：

每日一遍，心情愉悦

1.顺序串

1.1 顺序串的初始化

1.2 顺序串基本的算法：

1.2.1 顺序串字符串复制

1.2.2 字符串求字符串长度

1.2.3 判断两个字符串是否相等

1.2.4 两个字符串的连接

1.2.4 获取字符串的子串

1.2.5 查找子串在母串中的位置

1.2.6 字符串的插入

1.2.7 字符串中子串删除

1.2.8 字符串的子串替换

整体代码和效果展示

总结：

IC00

评论