数据结构 - C/C++ - 串

• 公开视频 -> 链接点击跳转公开课程
• 博客首页 -> 链接点击跳转博客主页

字符处理

C

• 特性

  • C语言中字符串存储在字符数组中，以空字符'\0'结束。

  • 字符串常量，const char* str = "Hello"，存储在只读的数据段中。

• 布局

  • 字符串在内存中是字符连续存储的集合，最后一个字符为空字符(ASCII值为0)，用来标识当前字符串的结束。

  • 字符串可以存储在栈(局部变量)、堆(动态分配)、全局、静态区等。

• 处理

  • C标准库提供的字符串处理函数，<string.h>头文件中，包含了字符串拷贝、拼接、比较、长度、截断等。

CPP

• 特性

  • C++提供了std::string类型，它封装了字符数组，并且在此基础上提供了更加丰富的字符串处理业务。

  • std::string支持内存动态扩容，不需要指定缓冲区大小。

• 布局

  • std::string内部管理与维护一个动态分配内存大小的指针，用于存储字符串数据。

• 处理

  • std::string是标准模板库(STL)中的一部分，其实现定义在头文件<string.h>中。

串的概念

• 串基本概念

  • 串(字符串)是由零个或多个字符组成的有限序列。

• 串和线程表

  • 线性表指的是元素之间的线性关系，元素之间的物理结构是次要的。

  • 串是特殊的线性表，串当中的元素为字符，串整体与字串的关系。

• 串存储结构

  • 顺序结构

    • 顺序结构基于一段连续的内存空间来存储串当中的字符序列。

  • 链式结构

    • 链式结构基于链表的形式存储字符串，每个节点可以包含一个或多个字符。

  • 块链结构

    • 块链结构基于串的分割，每一块包含一个字符数组，不同的块通过链表关联。
       

串的操作

#include <iostream>namespace str
{// length       字符串长度// str          源字符串int length(const char* str){// 参数校验if (str == NULL) return -1;// 获取长度int nLength = 0;while (*(str++) != '\0') nLength++;// 返回结果return nLength;}// Assign       字符串赋值// Dest         目标字符串的缓冲区// Sour         源字符串// DestSize     目标缓冲区的大小void Assign(char* Dest, const char* Sour, size_t DestSize){// 参数校验if (Dest == NULL || Sour == NULL || DestSize == 0) return;// 内容赋值int nLength = 0;while (*Sour/*源字符串当前下标字符是否为空*/ && nLength < DestSize - 1/*目标缓冲区长度是否满足*/){//Dest[nLength] = Sour[nLength];*Dest++ = *Sour++;nLength++;}*Dest = '\0';}// Concatenate  字符串拼接// str1         第一个字符串的缓冲区// str2         连接的字符串缓冲区// str1Size     第一个字符串的缓冲区长度void Concatenate(char* str1, const char* str2, size_t str1Size){//参数校验if (str1 == NULL || str2 == NULL || str1Size == 0) return;//字符长度int str1length = str::length(str1);//字符拼接int i = 0;for (i = 0; str2[i] != '\0' && str1Size - 1 > str1length + i; i++){str1[str1length + i] = str2[i];}//追加标记str1[str1length + i] = '\0';}// SunString    子串提取// Sour         源字符串数据// Dest         提取字符串空间// nDestSize    提取字符串容量 // nStart       提取字符串位置// nCount       提取字符串数量void SubString(const char* Sour, char* Dest, int nDestSize, int nStart, int nCount){//参数校验if (Sour == NULL || Dest == NULL || nDestSize == 0 || nCount == 0) return;//起始校验int nSourLength = str::length(Sour);if (nSourLength <= nStart || nStart < 0) return;//长度校验if (nCount < 0 || nCount > nSourLength - nStart) return;//空间校验if (nCount >= nDestSize) return;//提取子串int i = 0;for (i = 0; i < nCount; i++){Dest[i] = Sour[nStart + i];}//字符追加Dest[i] = '\0';}// SubPosition  子串查找// Sour         源字符串// Sub          子串内容int SubPosition(const char* Sour, const char* Sub){//参数校验if (Sour == NULL || Sub == NULL) return -1;//数据备份int nPosition = 0;const char* str_it;const char* sub_it;//算法定位for (str_it = Sour; *str_it != '\0'; str_it++){sub_it = Sub;//数据匹配if (*str_it == *sub_it){const char* str_temp = str_it;//匹配子串while (*str_temp && *sub_it && (*str_temp == *sub_it)){str_temp++, sub_it++;}if (*sub_it == '\0'){return nPosition;}}nPosition++;}return -1;}// Compare      字符串比较// str1         源字符串// str2         目标字符串int Compare(const char* str1, const char* str2){//参数校验if (str1 == NULL || str2 == NULL) return -1;//字符比较while (*str1 && *str2){if (*str1 == *str2){str1++;str2++;}else{break;}}return *str1 - *str2;}// Insert       字符串插入// str1         源字符串数据// str2         被插入字符串数据// nPos         插入位置索引// size_str1    源字符串缓冲区总大小void Insert(char* str1, const char* str2, int nPos, int size_str1){//参数校验if (str1 == NULL || str2 == NULL) return;//字符长度int str1len = str::length(str1);int str2len = str::length(str2);//下标越界if (nPos < 0 || nPos > str1len) return;//空间处理if (str1len + str2len + 1 > size_str1) return;//移动空间for (int i = str1len; i >= nPos; i--){str1[i + str2len] = str1[i];}//数据拷贝for (int i = 0; i < str2len; i++){str1[nPos + i] = str2[i];}}// Delete       字符串删除// str          源字符串数据// nPos         起始删除位置// nlength      删除字符长度void Delete(char* str, int nPos, int nlength){//参数校验if (str == NULL) return;//起始校验int strlen = str::length(str);if (nPos < 0 || nPos > strlen) return;//删除校验if (nlength < 0 || (nPos + nlength) > strlen) return;//位置修正char* Start = str + nPos;char* End = str + nPos + nlength;//数据删除while (*End){*Start++ = *End++;}*Start = '\0';}// Replace      字符串替换// str          源字符串数据// to_replace   被替换字符串// repalce      替换字符串// size_str     缓冲区长度void Replace(char* str, const char* to_replace, const char* repalce, int size_str){//参数校验if (str == NULL || to_replace == NULL || repalce == NULL) return;//子串定位int nPos = str::SubPosition(str, to_replace);if (nPos == -1)return;//空间判断int strlen = str::length(str);int torlen = str::length(to_replace);int replen = str::length(repalce);if (strlen - torlen + replen > size_str) return;//拷贝数据char* pTemp = (char*)malloc(size_str);if (pTemp == NULL)return;memset(pTemp, 0, size_str);//00 00 00 00 00 00 00 00 00 00 00 00 00memcpy(pTemp, str, nPos);//H E L 00 00 00 00 00 00 00 00 00 00memcpy(pTemp + nPos, repalce, replen);//H E L 0 x C C 00 00 00 00 00 00memcpy(pTemp + nPos + replen, str + nPos + torlen, strlen - torlen - nPos);//H E L 0 x C C H E L L O 0memcpy(str, pTemp, size_str);free(pTemp);}// Split        字符串分割// str          源字符串数据// chDelimiter  分隔符// outCount     子串数量char** Split(const char* str, char chDelimiter, int* outCount){//参数校验if (str == NULL) return NULL;//分割数量int nCount_Delimiter = 1;for (int i = 0; str[i] != '\0'; i++){if (str[i] == chDelimiter) ++nCount_Delimiter;}//写回数据*outCount = nCount_Delimiter;//分配空间char** strArr = (char**)malloc(nCount_Delimiter * sizeof(char*));if (!strArr) return NULL;memset(strArr, 0, nCount_Delimiter * sizeof(char*));//子串长度int i = 0;int j = 0;int nCount_Word = 0;for (i = 0, nCount_Word = 0; str[i] != '\0'; i++){if (str[i] != chDelimiter){nCount_Word++;}else{strArr[j++] = (char*)malloc(nCount_Word * sizeof(char) + 1);nCount_Word = 0;}       }strArr[j] = (char*)malloc(nCount_Word * sizeof(char) + 1);//拷贝数据for (i = 0, j = 0, nCount_Word = 0; str[i]; i++){if (str[i] != chDelimiter){strArr[j][nCount_Word++] = str[i];}else{strArr[j][nCount_Word++] = '\0';j++;nCount_Word = 0;}}strArr[j][nCount_Word++] = '\0';return strArr;}}int main()
{//字符长度const char szBuffer1[50] = "0xCC";int nLength = str::length(szBuffer1);//字符赋值char szBuffer2[4] = { 0 };str::Assign(szBuffer2, "Hello", sizeof(szBuffer2));//字符拼接char szBuffer3[50] = "Hello";str::Concatenate(szBuffer3, "World", sizeof(szBuffer3));//子串提取char szBuffer4[] = "Hello World";char szBuffer5[10] = { 0 };str::SubString(szBuffer4, szBuffer5, sizeof(szBuffer5), 6, 5);//子串查找char szBuffer8[] = "HELHELLHELLO";char szBuffer9[] = "HELLO";str::SubPosition(szBuffer8, szBuffer9);//字符比较char szBuffer6[] = "Hel";char szBuffer7[] = "Hel";str::Compare(szBuffer6, szBuffer7);//字符插入char szBuffer10[12] = "Hello";char szBuffer11[] = "0xCC";str::Insert(szBuffer10, szBuffer11, 1, sizeof(szBuffer10));//字符删除str::Delete(szBuffer10, 1, 4);//字符替换char szBuffer12[] = "HELHELLHELLO";char szBuffer13[] = "HELL";char szBuffer14[] = "CC";   str::Replace(szBuffer12, szBuffer13, szBuffer14, sizeof(szBuffer12));//字符分割int nCount = 0;char szBuffer15[] = "Hello,World,Ferry,0xCC";char** resule = str::Split(szBuffer15, ',', &nCount);return 0;
}