Chinaunix首页 | 论坛 | 博客
  • 博客访问: 75868
  • 博文数量: 20
  • 博客积分: 1297
  • 博客等级: 中尉
  • 技术积分: 230
  • 用 户 组: 普通用户
  • 注册时间: 2011-01-13 15:26
文章分类

全部博文(20)

文章存档

2011年(20)

我的朋友

分类: C/C++

2011-01-16 17:08:23

  1. //串的定长顺序存储表示
  2.  #define MAXSTRLEN 40 // 用户可在255以内定义最大串长(1个字节)
  3.  typedef char SString[MAXSTRLEN+1]; // 0号单元存放串的长度

  4. //串采用定长顺序存储结构的基本操作(14个)
  5.  // SString是数组,故不需引用类型。此基本操作包括算法4.2,4.3,4.5
  6.  Status StrAssign(SString T,char *chars)
  7.  { // 生成一个其值等于chars的串T
  8.    int i;
  9.    if(strlen(chars)>MAXSTRLEN)
  10.      return ERROR;
  11.    else
  12.    {
  13.      T[0]=strlen(chars);
  14.      for(i=1;i<=T[0];i++)
  15.        T[i]=*(chars+i-1);
  16.      return OK;
  17.    }
  18.  }

  19.  Status StrCopy(SString T,SString S)
  20.  { // 由串S复制得串T
  21.    int i;
  22.    for(i=0;i<=S[0];i++)
  23.      T[i]=S[i];
  24.    return OK;
  25.  }

  26.  Status StrEmpty(SString S)
  27.  { // 若S为空串,则返回TRUE,否则返回FALSE
  28.    if(S[0]==0)
  29.      return TRUE;
  30.    else
  31.      return FALSE;
  32.  }

  33.  int StrCompare(SString S,SString T)
  34.  { // 初始条件: 串S和T存在
  35.    // 操作结果: 若S>T,则返回值>0;若S=T,则返回值=0;若S
  36.    int i;
  37.    for(i=1;i<=S[0]&&i<=T[0];++i)
  38.      if(S[i]!=T[i])
  39.        return S[i]-T[i];
  40.    return S[0]-T[0];
  41.  }

  42.  int StrLength(SString S)
  43.  { // 返回串的元素个数
  44.    return S[0];
  45.  }

  46.  Status ClearString(SString S)
  47.  { // 初始条件:串S存在。操作结果:将S清为空串
  48.    S[0]=0;// 令串长为零
  49.    return OK;
  50.  }

  51.  Status Concat(SString T,SString S1,SString S2) // 算法4.2改
  52.  { // 用T返回S1和S2联接而成的新串。若未截断,则返回TRUE,否则FALSE
  53.    int i;
  54.    if(S1[0]+S2[0]<=MAXSTRLEN)
  55.    { // 未截断
  56.      for(i=1;i<=S1[0];i++)
  57.        T[i]=S1[i];
  58.      for(i=1;i<=S2[0];i++)
  59.        T[S1[0]+i]=S2[i];
  60.      T[0]=S1[0]+S2[0];
  61.      return TRUE;
  62.    }
  63.    else
  64.    { // 截断S2
  65.      for(i=1;i<=S1[0];i++)
  66.        T[i]=S1[i];
  67.      for(i=1;i<=MAXSTRLEN-S1[0];i++)
  68.        T[S1[0]+i]=S2[i];
  69.      T[0]=MAXSTRLEN;
  70.      return FALSE;
  71.    }
  72.  }

  73.  Status SubString(SString Sub,SString S,int pos,int len)
  74.  { // 用Sub返回串S的第pos个字符起长度为len的子串。算法4.3
  75.    int i;
  76.    if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)
  77.      return ERROR;
  78.    for(i=1;i<=len;i++)
  79.      Sub[i]=S[pos+i-1];
  80.    Sub[0]=len;
  81.    return OK;
  82.  }

  83.  int Index(SString S,SString T,int pos)
  84.  { // 返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数值为0。
  85.    // 其中,T非空,1≤pos≤StrLength(S)。算法4.5
  86.    int i,j;
  87.    if(1<=pos&&pos<=S[0])
  88.    {
  89.      i=pos;
  90.      j=1;
  91.      while(i<=S[0]&&j<=T[0])
  92.        if(S[i]==T[j]) // 继续比较后继字符
  93.        {
  94.          ++i;
  95.          ++j;
  96.        }
  97.        else // 指针后退重新开始匹配
  98.        {
  99.      i=i-j+2;
  100.          j=1;
  101.        }
  102.      if(j>T[0])
  103.        return i-T[0];
  104.      else
  105.        return 0;
  106.    }
  107.    else
  108.      return 0;
  109.  }

  110.  Status StrInsert(SString S,int pos,SString T)
  111.  { // 初始条件: 串S和T存在,1≤pos≤StrLength(S)+1
  112.    // 操作结果: 在串S的第pos个字符之前插入串T。完全插入返回TRUE,部分插入返回FALSE
  113.    int i;
  114.    if(pos<1||pos>S[0]+1)
  115.      return ERROR;
  116.    if(S[0]+T[0]<=MAXSTRLEN)
  117.    { // 完全插入
  118.      for(i=S[0];i>=pos;i--)
  119.        S[i+T[0]]=S[i];
  120.      for(i=pos;i<pos+T[0];i++)
  121.        S[i]=T[i-pos+1];
  122.      S[0]=S[0]+T[0];
  123.      return TRUE;
  124.    }
  125.    else
  126.    { // 部分插入
  127.      for(i=MAXSTRLEN;i<=pos;i--)
  128.        S[i]=S[i-T[0]];
  129.      for(i=pos;i<pos+T[0];i++)
  130.        S[i]=T[i-pos+1];
  131.      S[0]=MAXSTRLEN;
  132.      return FALSE;
  133.    }
  134.  }

  135.  Status StrDelete(SString S,int pos,int len)
  136.  { // 初始条件: 串S存在,1≤pos≤StrLength(S)-len+1
  137.    // 操作结果: 从串S中删除第pos个字符起长度为len的子串
  138.    int i;
  139.    if(pos<1||pos>S[0]-len+1||len<0)
  140.      return ERROR;
  141.    for(i=pos+len;i<=S[0];i++)
  142.      S[i-len]=S[i];
  143.    S[0]-=len;
  144.    return OK;
  145.  }

  146.  Status Replace(SString S,SString T,SString V)
  147.  { // 初始条件: 串S,T和V存在,T是非空串(此函数与串的存储结构无关)
  148.    // 操作结果: 用V替换主串S中出现的所有与T相等的不重叠的子串
  149.    int i=1; // 从串S的第一个字符起查找串T
  150.    if(StrEmpty(T)) // T是空串
  151.      return ERROR;
  152.    do
  153.    {
  154.      i=Index(S,T,i); // 结果i为从上一个i之后找到的子串T的位置
  155.      if(i) // 串S中存在串T
  156.      {
  157.        StrDelete(S,i,StrLength(T)); // 删除该串T
  158.        StrInsert(S,i,V); // 在原串T的位置插入串V
  159.        i+=StrLength(V); // 在插入的串V后面继续查找串T
  160.      }
  161.    }while(i);
  162.    return OK;
  163.  }

  164.  void DestroyString()
  165.  { // 由于SString是定长类型,无法销毁
  166.  }

  167.  void StrPrint(SString T)
  168.  { // 输出字符串T。另加
  169.    int i;
  170.    for(i=1;i<=T[0];i++)
  171.      printf("%c",T[i]);
  172.    printf("\n");
  173.  }
阅读(3058) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~