数据结构之字符串

1、串的相关概念

   1）串（string）是由零个或多个字符组成的有限序列，又名叫字符串。

   2）串中含有的字符数据称为串的长度，零个字符的串称为空串（null string），它的长度为零。

   3）子串与主串，串中任意个数的连续字符组成的子序列称为该串的子串，相应地，包含子串的串称为主串。

   4）子串在主串中的位置就是子串的第一个字符在主串中的序号。

2、串的存储结构

  串的存储结构与线性表相同，分为两种。

2.1 串的顺序存储结构

    串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小，为每个

定义的串变量分配一个固定长度的存储区。一般是用定长数组来定义。

    规定在串值后面加一个不计入串长度的结束标记字符，比如“\0”来表示串值终结。  

    串的顺序存储方式其实可能会有问题，因为字符串的操作，比如两船的连接Concat、新串的插入等操

作，都有可能使得串序列的长度超过了数组长度MaxSize。于是对于串的顺序存储，有一些变化，串值的存

储空间可在程序执行过程中动态分配而得。比如在计算机中存在一个自由存储区，叫做堆。这个堆可由C语

言的动态分配函数malloc()和free()来管理。

2.2 串的链式存储结构

    串的链式存储结构除了在连接串与串操作时有一定方便外，总的来说不如顺序存储灵活，性能也不如顺

序存储结构好。

3. 串的相关操作——《C标准库》

  

/**注意:
 * 检查指针有效性
 * strncpy和memcpy的区别,'\0'的判断
 * 内存区重叠问题
 * 进行链式操作等
*/

char *s_strcpy(char *dest, const char *src)
{
    char *tmp = dest;

    assert((dest != NULL) && (src != NULL));

    while((*dest++ = *src++) != '\0')
    {
        ;
    }

    //*dest = '\0';

    return tmp;
}

char *s_strncpy(char *dest, const char *src, size_t n)
{
    char *tmp = dest;
    size_t len = 0;

    assert((dest != NULL) && (src != NULL));

    while(((*dest++ = *src++) != '\0') && len++ < n)
    {
        ;
    }

    *dest = '\0';        //n小于src字符串的长度

    return tmp;
}

//与strncpy最大的区别是: memcpy不会遇到'\0'结束拷贝
void *s_memcpy(void *destaddr, const void *srcaddr, size_t n)
{

    assert((destaddr != NULL) && (srcaddr != NULL) && (n > 0));

    char *dest = (char *)destaddr;
    const char *src = (const char *)srcaddr;

    while(n-- > 0)
    {
        *dest++ = *src++;
    }

    return destaddr;
}

//memmove很好的解决了memcpy不能解决的数据区重叠的问题
void *memmove(void *dest, const void *src, size_t n)
{
    char *tmp = dest;
    const char *src_tmp = src;

    //assert((dest != NULL) && (src != NULL));

    if(src < dest && dest < src + n)
    {
        for(dest += n, src_tmp += n; 0 < n; --n)
        {
            *--dest = *--src_tmp;            //copy backwards
        }
    }
    else
    {
        for( ; 0 < n; --n)
        {
            *dest++ = *src_tmp++;            //copy forwards
        }
    }

    return tmp;
}

void *s_memset(void *s, int c, size_t n)
{
    const unsigned char uc = c;
    unsigned char *su = (unsigned char *)s;

    for( ; 0 < n; --n)
    {
        *su++ = uc;
    }

    return s;
}

size_t s_strlen(const char *str)
{
    size_t len = 0;

    assert(str != NULL);

    while(*str++ != '\0')
    {
        len++;
    }

    return len;
    /*
    if(str == NULL || *str == '\0')
    {
        return 0;
    }
    else
    {
        return s_strlen(str + 1) + 1;
    }
    */

}

char *s_strcat(char *dest, const char *src)
{
    char *tmp = dest;

    assert((dest != NULL) && (src != NULL));

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

    while((*dest = *src) != '\0')
    {
        dest++;
        src++;
    }

    *dest = '\0';

    return tmp;
}

int s_strcmp(const char *str1, const char *str2)
{
    const char *tmp_str1 = str1;
    const char *tmp_str2 = str2;

    assert((str1 != NULL) && (str2 != NULL));

    while((*tmp_str1 == *tmp_str2) && *tmp_str1)
    {
        tmp_str1++;
        tmp_str2++;
    }

    return (*tmp_str1 - *tmp_str2);
}

int s_strncmp(const char *str1, const char *str2, size_t n)
{
    const char *tmp_str1 = str1;
    const char *tmp_str2 = str2;

    assert((str1 != NULL) && (str2 != NULL));

    while((n-- > 0) && (*tmp_str1 == *tmp_str2) && (*tmp_str1))
    {
        tmp_str1++;
        tmp_str2++;
    }

    return (*tmp_str1 - *tmp_str2);
}

char * s_strchr(const char *str, const char c)
{
    const char *tmp = str;
    const char ch = c;

    assert(str != NULL);

    for( ; *tmp != ch; tmp++)
    {
        if(*tmp == '\0')
        {
            return NULL;
        }
    }

    return tmp;
}

                                                       梦醒潇湘love

    2013-01-14  11：40