10.字符串的基本认识

//05 字符串
/*
5.4 串的抽象数据类型
线性表更关注的是单个元素的操作，比如查找一个元素，插入或删除一个元素，
但串中更多的时查找子串位置、得到指定位置子串、替换子串等操作。

ADT 串 (string)
Data
    串中元素仅由一个字符组成，相邻元素具有前驱和后继关系。
Operation
    StrAssign(T, *chars):     生成一个其值等于字符串常量chars的串T。
    StrCopy(T, S):      串S存在，由串S复制得串T。
    ClearString(S):     串S存在，将串清空。
    StringEmpty(S):     若串为空，返回true。否则返回false。
    StrLength(S):       返回串S的元素个数，即串的长度。
    StrCompare(S, T):   若S>T,返回值>0,若S=T,返回0，若S<T，返回值<0。
    Concat(T, S1, S2):  用T返回由S1和S2联接而成的新串。
    SubString(Sub, S, pos, len):    在S串中第pos位置开始 截取 len长度，用Sub进行返回
    Index(S, T, pos):   在串S中找串T首次出现的位置pos返回
    Replace(S, T, V):   在S中查找到T并用V进行替换
    StrInsert(S, pos, T):   在串S的第pos个字符之前插入串T
    strDelete(S, pos, len):     在串S中删除第pos个字符起长度为len的子串
endADT
*/

//看一个操作Index的实现算法:
//T为非空串。若主串S中第pos个字符之后存在与T相等的子串，则返回第一个这样的子串在S中的位置，否则返回0
int Index(String S, String T, int pos)
{
    int n,m,i;
    String sub;
    if(pos > 0)
    {
        //得到主串S的长度
        n=StrLength(S);
        //得到子串T的长度
        m=StrLength(T);
        i = pos;
        while (i <= n-m +1)
        {
            //取主串第i个位置，长度与T相等子串给sub
            SubString(sub, S, i, m);
            //如果两串不相等
            if (StrCompare(sub, T) != 0)
                ++i;
            else        //如果两串相等，则返回i值
                return i;
        }
    }
    //若无子串与T相等，返回0
    return 0;
}

/*
5.5串的存储结构，串的存储结构与线性表相同，分为两种，串的顺序存储结构；串的链式存储结构；
串的链式存储结构每个结点中可以存放一个字符，也可以考虑存放多个字符，若最后一个结点若是未被占满时，
可以用#或其他非串值字符补全；当然，这里一个结点存多少个字符才合适就变得很重要，这会直接影响着串处理效率
*/