抽象数据类型String

ADT——String

定义头文件——string.h

• 结构定义与基本操作

  // 采用变长数组
  typedef struct
  {
      char * ch;
      int length;
  }Str;
  
  // 赋值操作
  int strAssign(Str * str, char * ch);
  
  // 取串长度
  int strLength(Str str);
  
  // 串比较
  int strCompare(Str s1, Str s2);
  
  // 串联接
  int concat(Str * str, Str str1, Str str2);
  
  // 求子串操作，以pos为起点，长度为len
  int subString(Str * substr, Str str, int pos, int len);
  
  // 清空串
  int clearString(Str * str);

实现文件——string.c

• 给串赋值

  #include "string.h"
  
  // 给串赋值
  int strAssign(Str * str, char * ch)
  {
      // 如果ch非空，将其置空，这里用C的话
      // Linux下free这段代码有问题，不能释放
      // 可能和未初始化有关，去掉此判断即可
      if(str->ch)
          free(str->ch);
  
      int len = 0;
      char *c = ch;
  
      while(*c) { ++len; ++c; }
  
      // 如果赋空
      if(len==0)
      {
          str->ch = NULL;
          str->length = 0;
          return 1;
      }
      else
      {
          str->ch = (char *)malloc(sizeof(char) * len + 1);
          //如果分配失败
          if(str->ch == NULL)
              return 0;
          else
          {
              c = ch;
              int i;
              for(i = 0; i <= len; ++i, ++c)
                  str->ch[i] = *c;
              // 下标从1开始，不把0号位置的长度考虑进去
              // 故此处减去1
              str->length = len-1;
              return 1;
          }
      }
  }

• 取串长度

  // 返回串的长度
  int strLength(Str str)
  {
      return str.length;
  }

• 比较串的大小

  // 这个字符串比较nice啊
  int strCompare(Str s1, Str s2)
  {
      int i;
      for(i = 0; i < s1.length && i < s2.length; ++i)
          if(s1.ch[i] != s2.ch[i])
              return s1.ch[i] - s2.ch[i];
      
      return s1.length - s2.length;
  }

• 串的连接

  // 字符串连接
  int concat(Str * str, Str str1, Str str2)
  {
      if(str->ch)
      {
          free(str->ch);
          str->ch = NULL;
      }
      str->ch = (char *)malloc(sizeof(char)*(str1.length + str2.length + 1));
      // 如果分配空间失败
      if(!str->ch)
          return 0;
      
      // 将字符串1赋给Str
      int i = 0;
      while(i < str1.length)
      {
          str->ch[i] = str1.ch[i];
          i++;
      }
      // 将字符串2继续赋给Str
      int j = 0;
      // 当j=str2.legthn时，将'\0'赋给str
      while(j <= str2.length)
      {
          str->ch[i+j] = str2.ch[j];
          j++;
      }
      str->length = str1.length + str2.length;
      return 1;
  }

• 求子串

  // 求子串
  int subString(Str * substr, Str str, int pos, int len)
  {
      // 排除不合法位置
      if(pos< 0 || pos >= str.length || len < 0 || len > str.length - pos)
          return 0;
      // 如果substr不为空，释放
      if(substr->ch)
      {
          free(substr->ch);
          substr->ch = NULL;
      }
      // 如果截取长度为0，substr赋值空
      if(len == 0)
      {
          substr->ch = NULL;
          substr->length = 0;
          return 1;
      }
      else
      {
          substr->ch = (char *)malloc(sizeof(char) * (len + 1));
          int i = pos;
          int j = 0;
          while(i < pos + len)
          {
              substr->ch[j] = str.ch[i];
              i++;
              j++;
          }
          substr->ch[j] = '\0';
          substr->length = len;
          return 1;
      }
  }

• 销毁串

  int clearString(Str * str)
  {
      if(str->ch)
      {
          // 释放指针指向的内存后，还需要将其指向空
          // 否则任然指向原来的位置
          free(str->ch);
          str->ch = NULL;
      }
      str->length = 0;
      return 0;
  }