数据结构串的操作实例详解

数据结构串的操作实例详解

串是一种特殊的线性表，它的每个结点是一个字符，所以串也称作字符串。

关于串的操作主要有求串长，串复制，串连接，求子串，串插入，串删除，子串定位等。串的操作也是C语言笔试中常考的一部分。

下面的代码实现了串的主要操作。

#include <stdio.h>
#include <stdlib.h> 

#define MAXSIZE 20
char *String_Create();         //创建串
int String_Length(char *s);       //求串长
void String_Show(char *s);       //输出串
char *String_Copy(char *d, char *s);  //串复制
char *String_Connect(char *d, char *s); //串连接
char *String_SubStr(char *d, char *s, int pos, int len);  //求子串
int String_Compare(char *d, char *s);  //串比较
char *String_Insert(char *d, char *s, int pos);   //串插入
char *String_Delete(char *d, int pos, int len);   //串删除
int String_Index(char *d, char *s, int pos);    //串匹配 

int main(void)
{
  int choice;
  char *str, *c;
  int ans, pos, len; 

  c = (char*)malloc(sizeof(MAXSIZE));
  printf("请输入一串字符串(小于10个字符):\n");
  str = String_Create(); 

  while(1)
  {
    printf("***************************\n");
    printf("字符串操作练习:\n");
    printf("1.求串长\n");
    printf("2.串复制\n");
    printf("3.串连接\n");
    printf("4.求子串\n");
    printf("5.比较串\n");
    printf("6.串插入\n");
    printf("7.串删除\n");
    printf("8.串定位\n");
    printf("9.串输出\n");
    printf("10.退出程序\n"); 

    printf("输入选择:\n");
    scanf("%d", &choice);
    getchar(); 

    switch(choice)
    {
    case 1:
      ans = String_Length(str);
      printf("串的长度为%d\n", ans);
      break;
    case 2:
      c = String_Copy(c, str);
      printf("目标字符串为:\n");
      String_Show(c);
      break;
    case 3:
      printf("输入字串(小于10个字符)\n");
      gets(c);
      c = String_Connect(c, str);
      printf("新的字符串为\n");
      String_Show(c);
      break;
    case 4:
      printf("输入你想求子串所在位置及长度\n");
      scanf("%d %d", &pos, &len);
      c = String_SubStr(c, str, pos, len);
      if(c == NULL)
        printf("求子串失败！\n");
      else
      {
        printf("所求子串为:\n");
        String_Show(c);
      }
      break;
    case 5:
      printf("输入字串:\n");
      gets(c);
      ans = String_Compare(c, str);
      if(ans>0)
        printf("首字符串大\n");
      else if(ans<0)
        printf("第二个字符串大\n");
      else
        printf("两字符串相等\n");
      break;
    case 6:
      printf("输入需在主串中插入的字串\n");
      gets(c);
      printf("输入插入的位置:\n");
      scanf("%d", &pos);
      str = String_Insert(str, c, pos);
      printf("新的字符串为:\n");
      String_Show(str);
      break;
    case 7:
      printf("输入删除子串的起始位置及长度\n");
      scanf("%d %d", &pos, &len);
      str = String_Delete(str, pos, len);
      break;
    case 8:
      printf("输入要定位的子串:\n");
      gets(c);
      ans = String_Index(str, c, 1);
      printf("定位的结果为%d\n", ans);
      break;
    case 9:
      String_Show(str);
      break;
    case 10:
      return 0;
      break;
    default:
      printf("选择无效!\n");
      break;
    }
  }
  return 1;
} 

//创建串
char *String_Create()
{
  char *s, ch;
  int i = 0; 

  s = (char*)malloc(MAXSIZE);
  ch = getchar();
  while(ch != '#')
  {
    *(s+i) = ch;
    i++;
    ch = getchar();
  }
  if(i > MAXSIZE/2)
    printf("输入长度大于10!\n");
  else
    *(s+i) = '\0';
  return s;
} 

//求串长
int String_Length(char *s)
{
  int l=0; 

  while(*s != '\0')
  {
    l++;
    s++;
  } 

  return l;
} 

//串的复制
char *String_Copy(char *d, char *s)
{
  char *c; 

  c = d;
  while((*d++=*s++)!='\0'); 

  return c;
} 

//串连接
char *String_Connect(char *d, char *s)
{
  char *c;
  int l, i=0;; 

  c = d;
  l = String_Length(d);
  d = d + l;
  while((*d++ = *s++) != '\0');    //串连接 

  return c;
} 

//求子串
char *String_SubStr(char *d, char *s, int pos, int len)
{
  char *c1, *c2=NULL;
  int l, i; 

  c2 = (char*)malloc(MAXSIZE/2); 

  c1 = s;
  d = c2;
  l = String_Length(s); 

  if(pos>l || pos<1)      //输入位置非法
    return NULL;
  if(len<0)          //输入长度非法
    return NULL;
  c1 = c1 + pos - 1; 

  for(i=1; i<=len && *c1 != '\0'; i++) //求字串
  {
    *c2++ = *c1++;
  }
  *c2 = '\0';         //不要忘记结尾符号 

  return d;
} 

//串比较
int String_Compare(char *d, char *s)
{
  char *c1, *c2; 

  c1 = d;
  c2 = s; 

  while(*c1 != '\0' || *c2 != '\0')
  {
    if(*c1 > *c2)
      return 1;
    else if(*c1 < *c2)
      return -1;
    c1++;
    c2++;
  }
  if(*c1 == '\0' && *c2 == '\0')   //两个字符处都结束时，则两字符串相等
    return 0;
  else if(*c2 == '\0')        //第二个字符串先结束，则第一个字符串大
    return 1;
  else
    return -1;
} 

//插入串
char *String_Insert(char *d, char *s, int pos)
{
  int i, ld,ls;
  char *c1, *c2; 

  c1 = d;
  c2 = s; 

  ld = String_Length(d);
  ls = String_Length(s); 

  for(i=ld; i>=pos-1; i--)   //字符串后移，留出待插字符串位置
    *(c1 + ls + i) = *(c1 + i);
  for(i=pos; i<=pos+ls-1; i++) //插入子字符串
    *(c1 + i - 1) = *c2++;
  *(c1 + ld + ls) = '\0';     //最后的结尾符号不能忘掉 

  return d;
} 

//串删除
char *String_Delete(char *d, int pos, int len)
{
  int i, l; 

  l = String_Length(d);
  if(pos + len > l)        //如果删除长度大于字串开始位置后面的长度，则只保留主串前面字符
    *(d + pos -1) = '\0';
  else
  {
    for(i=pos+len-1; i<=l; i++)
      *(d + i - len) = *(d + i);
    *(d + l - len) = '\0';   //结束字符
  } 

  return d;
} 

//子串定位
int String_Index(char *d, char *s, int pos)
{
  int i = pos - 1, j = 0, ld, ls, b=0; 

  ld = String_Length(d);
  ls = String_Length(s);
  while(i < ld && j<ls)
  {
    if(*(d+i) == *(s+j))  //当前字符相等，则继续匹配
    {
      i++;
      j++;
    }
    else          //下一趟匹配
    {
      i = i - j + 1;
      j = 0;
    }
  }
  if(j == ls)     //匹配成功
    return (i - ls + 1);
  else
    return 0;
} 

//输出串
void String_Show(char *s)
{
  while(putchar(*s++));
  printf("\n");
}

上面的代码就是串的相关操作。

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！