数据结构-串

xiaoxiao2021-02-28  9

串:

串(string)是由零个或多个字符组成的有限序列,又名叫字符串。  串一般记为。用双引号或单引号括起来的字符序列是串的值(引号不属于串的内容)。所谓的序列,说明串的相邻字符之间具有前驱和后继的关系。  几种特殊的串 

空串(nullstring):零个字符的串,它的长度为零,可以直接用两双引号“""”表示,也可以用希腊字母“Φ”来表示。 空格串:只包含空格的串。  子串与主串:串中任意个数的连续字符组成的子序列称为该串的子串,相应地,包含子串的串称为主串。子串在主串中的位置就是子串的第一个字符在主串中的序号。串的比较是通过组成串的字符之间的编码来进行的,而字符的编码指的是字符在对应字符集中的序号。  目前计算机常用的编码方式为标准的ASCII编码,由7位二进制数表示一个字符,总共可以表示128个字符。后来发现一些特殊符号的出现,128个不够用,于是扩展ASCII码由8位二进制数表示一个字符,总共可以表示256个字符,这已经足够满足以英语为主的语言和特殊符号进行输入、存储、输出等操作的字符需要了。  全世界有成百上千种语言与文字,显然这256个字符是不够的,因此后来就有了Unicode编码,比较常用的是由16位的二进制数表示一个字符,这样总共就可以表示个字符,约是6.5万多个字符,足够表示世界上所有语言的所有字符了。为了和ASCII码兼容,Unicode的前256个字符与ASCII码完全相同。串的比较是通过组成串的字符之间的编码来进行的,而字符的编码指的是字符在对应字符集中的序号。  串的基本操作代码如下:

头文件:

#define SIZE 100 typedef struct Str {  char elem[SIZE];  int length;//字符串有效长度 }Str; //功能函数 void StrAssign(Str*s, const char *chars);/// void StrCpy(Str*s, Str *t); void show(Str *s); bool Isempty(Str *s);// int GetLength(Str*s); void clear(Str*s); bool SubStr(Str*sub, Str*s, int pos, int len);//从s里面的第pos位置提取长度为len的子串,放到sub中。空白不提取 bool Insert(Str*s, int pos, Str*t);//在pos位置插入t int BF(Str*s, Str*sub, int pos); bool DeletePos(Str*s, int pos, int len);//从pos位置开始删除len长度 bool Delete(Str*s, int pos, Str*t);//从pos位置删子串t bool Replace(Str*s, Str *t, Str*v, int pos);//用v替换从pos位置开始的第一个 bool ReplaceAll(Str *s, Str *t, Str*v); Str.cpp #include<stdio.h> #include<assert.h> #include<string.h> #include"Str.h" void StrAssign(Str *s,const char *chars)//初始化 {  assert(s != NULL);  int len = strlen(chars);  if (len > SIZE)  {   return;  }  for (int i = 0; i < len; i++)  {   s->elem[i] = chars[i];  }  s->length = len; } void StrCpy(Str *s, Str*t)//串t 拷贝到s {  assert(s!= NULL&& t!=NULL);  for (int i = 0; i < t->length; i++)  {   s->elem[i] = t->elem[i];  }  s->length = t->length; } void show(Str *s)//show {  for (int i = 0; i < s->length; i++)  {   printf("%c", s->elem[i]);  }  printf("\n"); } bool IsEmpty(Str*s)//判空 {  return s->length == 0; } int GetLength(Str*s)//串长度 {  return s->length; } void Clear(Str*s)//清空 {  s->length = 0; } bool SubStr(Str*sub, Str*s, int pos, int len)//从s里面的第pos位置提取长度为len的子串,放到sub中。且空白不提取 {  assert(sub != NULL&& s != NULL);  if (pos < 0 || len<=0||pos+len>s->length-1|| pos>=s->length)  {   return false;  }  for (int i =0; i <= len;i++)  {   sub->elem[i] = s->elem[i+pos];  }  sub->length = len;  return true; } bool Insert(Str*s, int pos, Str*t)//在pos位置插入字符串t {  assert(s != NULL&& t != NULL);  int lens = GetLength(s);  int lent = GetLength(t);  if (pos < 0||lens+lent>SIZE||pos>=s->length)  {   return false;  }  for (int i =lens-1; i > pos ; --i)//挪数据  {   s->elem[i + lent] = s->elem[i];  }  for (int i = 0; i < lent; i++)  {   s->elem[pos + i] = t->elem[i];  }  s->length += t->length; } int BF(Str*s, Str*sub, int pos)// {  if (pos<0 || pos>s->length)  {   return -1;  }  int i = pos;  int j = 0;  int lens = GetLength(s);  int lensub = GetLength(sub);  while (i < lens&&j < lensub)  {   if (s->elem[i] == sub->elem[j])   {    i++;    j++;   }   else   {    i = i - j + 1;    j = 0;   }  }  if (j >= lensub)  {   return i - j;  }  else  {   return -1;  } } bool DeletePos(Str*s, int pos, int len)//从pos位置开始删除len长度 {  assert(s != NULL);  if (pos <0 || len > s->length || pos+len>s->length||len<0)  {   return false;  }  for (int i = pos; i < s->length - len; i++)  {   s->elem[i] = s->elem[i+len];  }  s->length -= len;  return true; } bool Delete(Str*s, int pos, Str*t)//从pos位置删子串t {  int index = BF(s, t, pos);//找子串  if (index < 0)  {   return false;  }  return DeletePos(s, index, t->length); } bool Replace(Str*s, Str *t, Str*v, int pos)//用v替换从pos位置开始的第一个 {  assert(s != NULL || t != NULL || v != NULL);  int index = BF(s, t, pos);  if (index < 0)  {   return false;  }  DeletePos(s, index, t->length);  return Insert(s, index, v); } bool ReplaceAll(Str *s, Str *t, Str*v)//全替换 {  while (Replace(s, t, v, 0));  return true; } 测试用例: test.cpp #include<stdio.h> #include<string.h> #include"Str.h" int main() {  Str s;  char *s1 = "iloveyouandyouloveme";  StrAssign(&s,s1);  show(&s);  int len1 = GetLength(&s);  printf("字符串1长度:%d\n", len1);  Str t;  char *s2 = "love";  StrAssign(&t,s2);  show(&t);  int len2 = GetLength(&t);  printf("字符串2长度:%d\n", len2);    /*Str s3;  SubStr(&s3, &s, 2, 5);  show(&s3);  Insert(&s,3, &t);  show(&s);     //StrCpy(&s, &t);  //show(&s);  int bf = BF(&s, &t, 5);  printf("bf:%d\n", bf);  DeletePos(&s, 5, 10);  show(&s);  Delete(&s, 5, &t);  show(&s);*/  Str s3;  char *p = "oooo";  StrAssign(&s3, p);  show(&s3);  Replace(&s, &t, &s3, 5);  printf("替换为:");  show(&s);    ReplaceAll(&s, &t, &s3);  printf("全替换为:");  show(&s);  return 0; } 运行结果:

转载请注明原文地址: https://www.6miu.com/read-2250340.html

最新回复(0)