串(1)--基本概念

本文主要是介绍串(1)--基本概念，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一:基本概念：

           串是字符线性的有限集合，记作a=′a1…an ′ (n≥0)。其中：a是串名，用双引号括起来的字符序列是为串的值，双引号不是串内的成份，其作用是为了避免与变量名或常量混淆。ai(1≤i≤n)或是字母数据，或是其它字符称为串的元素，是构成串的基本单位。n为串的长度，且n≥0，如果n=0，则称a为空串（Null String），记作：a= ′′，其长度为０。而a= ′  ′称为空白串(Blank String)，由于空格本身就是一个字符,它的长度不为０。因此，它可以出现在其它字符中间。为了表示清楚下文中的空格符用′Φ′。

二.串的存储结构:

 1.顺序结构

   串的存储分配是在编译时完成的，是静态的,串中的字符依次存放在一组连续的存储空间中

    typedef struct{char ch[MAXLEN+1]；int length；/*串的实际长度*/}SString; 

  2.堆存储结构

     存储空间是在程序执行过程中动态分配的

typedef struct{  char  *ch；/*若是非空串，则按串长分配存储区，否则ch为NULL */int  length；  /* 串长度 */}HString；

 3.块链结构

       每个结点既可以存放一个字符，也可以存放多个字符。每个结点称为块，整个链表称为块链结构，为了便于操作，再增加一个尾指针。结点大小为数据域中存放字符的个数,当结点大小大于1时，由于串长不一定是结点大小的整倍数，则链表中的最后一个结点不一定全被串值占满，此时通常补上〞#〞或其他的非串值字符。

#define  CHUNKSIZE  <长度>  /*可由用户定义的块大小*/
typedef  struct Chunk
{  char  ch[CHUNKSIZE]；struct Chunk  *next；
}Chunk；
typedef struct
{  Chunk *head，  *tail； /* 串的头和尾指针 */int    curlen；            /*串的当前长度*/}LString；

三.串的基本操作:

           虽从逻辑结构来看，串是特殊的线性表，串的存贮结构和线性表不同，串的基本操作和线性表也不同。一是它们的基本操作子集不同。二是线性表的操作通常以“数据元素”为操作对象。而串的操作主要以“串整体”为操作对象。因此，实现串的基本操作有其自己的处理方法。

1.串的联接

假设T、S1、S2都是SString类型串，基于对串S1、S2长度的不同情况，串T值的产生可能有三种情况：

1). S1.length＋S2.length≤MAXLEN

2).S1.length＋S2.length＞MAXLEN而S1.length＜MAXLEN

3).S1.length=MAXLEN

int Concat(SString *T，SString S1，SString S2) /*用T返回由S1和S2联接的新串。成功返TRUE，否则FALSE。*/
{if (S1.length+S2.length<=MAXLEN)         /*未截断*///S1.length＋S2.length≤MAXLEN{T->ch[1..S1.length]=S1.ch[1..S1.length]；T->ch[S1.length+1..S1.length+S2.length]=S2.ch[1..S2.length]；T->length=S1.length+S2.length；return TRUE；}elseif  (S1.length<MAXLEN)              /*截断*///S1.length＋S2.length＞MAXLEN而S1.length＜MAXLEN{T->ch[1..S1.length]=S1.ch[1..S1.length]；T->ch[S1.length+1..MAXLEN]=S2.ch[1..MAXLEN-S1.length]；T->length =MAXLEN；retuen FALSE；}else                                /*截断(仅取S1)*///.S1.length=MAXLEN{  T[0..MAXLEN]=S1[0..MAXLEN]；return FALSE；}
} 

2.串的插入:

 int StrInsert(SString *s，int pos，SString t)  /*在串s中第pos之前插入串t */
{if (pos<0 || pos>s->length) return FALSE；  /*插入位置不合法*/if (s->length+t.length<=MAXLEN)                /*插入后串长≤MAXLEN*/{  for (i=s->length；i>=pos；--i)    s->ch[t.length+i]=s->ch[i]；for (i=1，i<=t.length，++i)         s->ch[pos+i-1]=t.ch[i]；s->length+=t.length；}else if (pos+t.length-1<=MAXLEN)/*插入后串长＞MAXLEN，但串t可全部插入，串s被截断*/{for (i=MAXLEN-t.length；i>=pos；--i)s->ch[i+t.length]=s->ch[i]；for (i=1；i<=t.length；++i)s->ch[pos+i-1]=t.ch[i]；s->length=MAXLEN；}else                                                  /*串t部分或全部被截断*/{ for (i=1；i<=MAXLEN-pos+1；++i)s->ch[pos+i-1]=t.ch[i]；s->length=MAXLEN；}return TRUE；
}

3.串的删除

int StrDelete(SString *s，int pos，int len)/* 在串s中删除从序号pos起len个字符*/
{ if (pos<0 || pos>s->length-len+1)return FALSE；for (i=pos+len；i<=s->length；++i)s->ch[i-len]=s->ch[i]；s->length-=len；
}

这篇关于串(1)--基本概念的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---