数据结构:字符串的基本操作

字符串(string)是由0个或多个字符组成的有限序列。一般使用顺序存储结构,末尾以'\0'表示结束,但不计入字符串的长度。

示例程序:(改编自《大话数据结构》)

#include<iostream>
using namespace std;

#define MAXSIZE 20
typedef char String[MAXSIZE + 1]; //以'\0'结尾
/* 生成一个串*/
bool StrAssign(String Dest, char *ptr)
{
    cout << "Assign Str ..." << endl;
    int i;
    for (i = 0; ptr[i] != '\0' && i < MAXSIZE; i++)
        Dest[i] = ptr[i];
    Dest[i] = '\0';
    return true;
}
/* 拷贝一个字符串 */
bool StrCopy(String Dest, String Src)
{
    cout << "Copy Str ..." << endl;
    int i;
    for (i = 0; Src[i] != '\0' && i < MAXSIZE; i++)
        Dest[i] = Src[i];
    Dest[i] = '\0';
    return true;
}

int StrLength(String Src)
{
    int i = 0;
    while (Src[i] != '\0')
        i++;
    return i;
}

bool StrEmpty(String Src)
{
    if (StrLength(Src) == 0)
        return true;
    else
        return false;

}
/* 若Str1>Str2,则返回值>0;若Str1=Str2,则返回值=0;若Str1<Str2,则返回值<0 */
int StrCompare(String Str1, String Str2)
{
    int len1 = StrLength(Str1);
    int len2 = StrLength(Str2);
    for (int i = 0; i < len1 && i < len2; i++)
        if (Str1[i] != Str2[i])
            return Str1[i] - Str2[i];
    return len1 - len2;
}

bool ClearString(String Src)
{
    for (int i = 0; Src[i] != '\0'; i++)
        Src[i] = '\0';
    return true;
}
/* 用Dest返回Str1和Str2联接而成的新串。若未截断,则返回TRUE,否则FALSE */
bool StrConcate(String Dest, String Str1, String Str2)
{
    cout << "Concate String ..." << endl;
    if (StrLength(Str1) + StrLength(Str2) <= MAXSIZE)
    {
        /*  未截断 */
        int i, j;
        for (i = 0; Str1[i] != '\0'; i++)
            Dest[i] = Str1[i];
        j = i;
        for (i = 0; Str2[i] != '\0'; i++, j++)
            Dest[j] = Str2[i];
        Dest[j] = '\0';
        return true;
    }
    else //截断Str2
    {
        int i, j;
        for (i = 0; Str1[i] != '\0'; i++)
            Dest[i] = Str1[i];
        j = i;
        for (i = 0; Str2[i] != '\0' && j <= MAXSIZE - 1; i++, j++)
            Dest[j] = Str2[i];
        Dest[j] = '\0';
        return false;
    }

}
/* 用Sub返回串Src的第pos个字符起长度为len的子串。 */
bool SubString(String Sub, String Src, int pos, int len)
{
    /*cout<<"Get SubString ..."<<endl;*/
    if (pos < 1 || pos > StrLength(Src) ||
            len < 0 || len > StrLength(Src) - pos + 1)
        return false;
    int i;
    for (i = 0; i <= len - 1; i++)
        Sub[i] = Src[i + pos - 1];
    Sub[i] = '\0';
    return true;
}
/* 返回子串Sub在主串Src中第pos个字符之后的位置。若不存在,则函数返回值为0。 */
int Index1(String Src, String Sub, int pos)
{
    int len1 = StrLength(Src);
    int len2 = StrLength(Sub);
    int i = pos;
    String sub;
    if (pos > 0)
    {
        while (i <= len1 - len2 + 1)
        {
            SubString(sub, Src, i, len2);
            /* 如果两串相等 , 则返回i值 */
            if (StrCompare(Sub, sub) == 0)
                return i;
            else/* 如果两串不相等,前进位置 */
                i++;
        }
    }
    return 0;
}

int Index2(String Src, String Sub, int pos)
{
    int i = pos - 1;
    int j = 0;
    int len1 = StrLength(Src);
    int len2 = StrLength(Sub);
    while (i <= len1 - 1 && j <= len2 - 1)
    {
        if (Src[i] == Sub[j])/* 两字母相等则继续 */
        {
            ++i;
            ++j;
        }
        else
        {
            /* i退回到上次匹配首位的下一位 */
            i = i - j + 1;
            j = 0;/* j退回到子串Sub的首位 */
        }
    }

    if (j == len2) //子串已经遍历完毕
        return i - len2 + 1;
    else
        return 0;
}
/* 在串Src的第pos个字符之前插入串In。完全插入返回TRUE,部分插入返回FALSE */
bool StrInsert(String Src, int pos, String In)
{
    int i;
    int len1 = StrLength(Src);
    int len2 = StrLength(In);
    if (pos < 1 || pos > len1 + 1)
        return false;

    if (len1 + len2 <= MAXSIZE)
    {
        /*  完全插入 */
        for (i = len1; i >= pos - 1; i--)
            Src[i + len2] = Src[i];
        for (i = pos - 1; i < pos + len2 - 1; i++)
            Src[i] = In[i - pos + 1];
        if (pos == len1 + 1) //末尾插入,最后添加'\0'
            Src[i] = '\0';
        return true;
    }

    else
    {
        /*  部分插入,In截断 */
        for (i = MAXSIZE; i > pos; i--)
            Src[i] = Src[pos + i - MAXSIZE];

        for (i = 0; i < MAXSIZE - pos; i++)
            Src[pos - 1 + i] = In[i];
        return false;
    }
}
/* 从串Src中删除第pos个字符起长度为len的子串 */
bool StrDelete(String Src, int pos, int len)
{
    int i;
    if (pos < 1 || pos > StrLength(Src) - len + 1 || len < 0)
        return false;
    for (i = pos + len - 1; i <= StrLength(Src); i++)
        Src[i - len] = Src[i];
    return true;
}
/* 用Re替换主串Src中出现的所有与Sub相等的不重叠的子串 */
bool StrReplace(String Src, String Sub, String Re)
{
    int i = 1;/*  从串Src的第一个字符起查找串Sub */
    if (StrEmpty(Sub))
        return false;
    do
    {
        i = Index1(Src, Sub, i);/*  结果i为从上一个i之后找到的子串Sub的位置 */

        if (i)
        {
            StrDelete(Src, i, StrLength(Sub));/*  删除该串Sub */
            StrInsert(Src, i, Re); /*  在原串Sub的位置插入串Re */
            i += StrLength(Re);/*  在插入的串Re后面继续查找串Sub */
        }

    }
    while (i);

    return true;
}

void StrPrint(String Src)
{
    cout << "Print Str ..." << endl;
    for (int i = 0; Src[i] != '\0'; i++)
        cout << Src[i];
    cout << endl;

}

int main(void)
{
    String Str1;
    StrAssign(Str1, "ILOVEYOU");
    StrPrint(Str1);

    String Str2;
    StrCopy(Str2, Str1);
    StrPrint(Str2);

    if (!StrEmpty(Str1))
        cout << "Str1's Length : " << StrLength(Str1) << endl;

    String Str3;
    StrAssign(Str3, "ILOVEyou");

    if (StrCompare(Str1, Str3) > 0)
        cout << "Str1 > Str3" << endl;
    else if (StrCompare(Str1, Str3) == 0)
        cout << "Str1 = Str3" << endl;
    else
        cout << "Str1 < Str3" << endl;

    String Str4, Str5;
    StrAssign(Str4, " HLZ");
    StrConcate(Str5, Str1, Str4);
    StrPrint(Str5);

    String Str6;
    cout << "Get SubString ..." << endl;
    SubString(Str6, Str5, 1, 8);
    StrPrint(Str6);

    cout << "Index of (Str5, Str4) " << Index2(Str5, Str4, 2) << endl;

    StrInsert(Str6, 9, " HLZ");
    StrPrint(Str6);
    StrInsert(Str6, 8, " HLZ");
    StrPrint(Str6);

    StrDelete(Str5, 2, 4);
    StrPrint(Str5);

    String Str7, Str8;
    StrAssign(Str7, "ILOVEJDWSOVEDSOVEde");
    StrAssign(Str8, "OVE");
    StrReplace(Str7, Str8, "ove");
    StrPrint(Str7);

    return 0;
}

输出为:

对于字符串的链式存储结构来说,一个节点存放多少个字符才合适显得很重要,这会直接影响字符串处理的效率,需要根据实际情况做出选择。但字符串的链式存储结构除了在连接串与串操作时有一定方便之外,总的来说不如顺序存储灵活,性能也不如顺序存储结构好。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一个会写诗的程序员的博客

Spring Data JPA WITH Kotlin

异常消息: No default constructor for entity: : com.ak47.cms.cms.entity.StockIndex; n...

732
来自专栏杂烩

Arthasa应用 原

Arthasa是个好东西,用熟了确实一大助力,本文主要描述如何用Arthasa解决问题(官网https://alibaba.github.io/arthas)。

762
来自专栏xingoo, 一个梦想做发明家的程序员

【设计模式】—— 中介者模式Mediator

  模式意图   使用一个中介的对象,封装一组对象之间的交互,这样这些对象就可以不用彼此耦合。   这个中介者常常起着中间桥梁的作用,使其他的对象可以利用中介...

1809
来自专栏Django Scrapy

python爬取链家租房之获得每一页的房屋信息地址(持续更新)

__author__ = 'Lee' import requests from bs4 import BeautifulSoup url_text = 'ht...

3106
来自专栏一个会写诗的程序员的博客

java.sql.SQLException: connection holder is null

java.sql.SQLException: connection holder is null

811
来自专栏有趣的django

21天打造分布式爬虫-Scrapy框架(七)

pip install Twisted-18.7.0-cp36-cp36m-win_amd64.whl

631
来自专栏小樱的经验随笔

【宅男宅女们的福音】电影天堂最新电影爬取及搜索脚本

多线程电影天堂最新资源爬取脚本、电影搜索脚本 PS:方便大家使用写到了HTML中生成表格。 线程可以在脚本里直接改,测试线程为30时IP可能会被限制访问。[...

3528
来自专栏令仔很忙

令仔代码收藏系列(二)----BASE64编码

612
来自专栏Ryan Miao

从国家统计局爬下来的地区信息

发现地区编码网上流传了很多版本。有很多崇文区,玄武区之类的。于是想了想,还是自己做一份。不敢保证没问题,但还没遇到问题。 首先,从网上找到一个大神写的jsoup...

2936
来自专栏有趣的django

21天打造分布式爬虫-Crawl爬取小程序社区(八)

583

扫码关注云+社区