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

字符串(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 条评论
登录 后参与评论

相关文章

来自专栏机器学习入门

LWC 53:693. Binary Number with Alternating Bits

LWC 53:693. Binary Number with Alternating Bits 传送门:693. Binary Number with Alte...

2038
来自专栏aCloudDeveloper

全排列(含递归和非递归的解法)

全排列在近几年各大网络公司的笔试中出现的比较频繁 首先来看看题目是如何要求的。 用C++写一个函数, 如 Foo(const char *str), 打印出 s...

2279
来自专栏一英里广度一英寸深度的学习

线性排序算法-堆排序 (2)

在学数据结构的时候,链表、堆栈、树三种数据结构印象最深刻。当时理解有误区,堆栈被当成一种结构,可能因为堆栈有同样的特性——只关心堆顶或栈顶的元素。

1013
来自专栏King_3的技术专栏

leetcode-151-翻转字符串里的单词

1、这道题给定一个字符串s,相当于一个英文句子,要求把这个句子中的单词反转一下,后面的要放在前面,前面放在后面。

1581
来自专栏desperate633

LeetCode Remove Linked List Elements

Remove all elements from a linked list of integers that have value val. Example...

411
来自专栏五分钟学算法

每天一算:Minimum Size Subarray Sum

leetcode上第209号问题:Minimum Size Subarray Sum

451
来自专栏极客慕白的成长之路

ACM札记二

由数学基本定理可知:任何一个大于1的非素数整数(即合数)都可以唯一分解成若干个素数的乘积。编写程序,从控制台读入一个合数(合数的大小不会超过int数据类型表示的...

511
来自专栏落影的专栏

程序员进阶之算法练习(三十二)LeetCode专场

题目链接 题目大意: 给出一个链表RandomListNode *next, *random; 每个节点有int值,有两个指针,一个指向下一个节点,一个指...

782
来自专栏desperate633

LeetCode 75. Sort Colors题目分析

给定一个包含红,白,蓝且长度为 n 的数组,将数组元素进行分类使相同颜色的元素相邻,并按照红、白、蓝的顺序进行排序。 我们可以使用整数 0,1 和 2 分别代...

763
来自专栏King_3的技术专栏

leetcode-520-Detect Capital

2025

扫码关注云+社区