串的基本操作

1、由 0 个或多个 字符 组成的 有限的 序列，通常记为：s =“a1 a2 a3 … ai …an” ( n≥0 ，且n是有限的)。其中的引号不属于串，只是一个标记作用！
2、n就是串的长度，且字符串里的字符 ai 的值由 字母、数字或其他字符 组成的。

串的相关术语

1、空串：不含任何字符的串，长度 = 0，用符号 f 表示。也就是说空串也是字符串！
2、空格串：仅由一个或多个空格组成的串。 区分空串和空格串！
3、子串：由串中任意个连续的字符组成的子序列。空串是任意串的子串，任意串是其自身的子串。
4、主串：包含子串的串。
5、字符的位置：字符在序列中的序号。
6、子串在主串中的位置：子串的首字符在主串中的位置。
7、串相等：当两个串的长度相等且各个对应位置的字符都相等时才相等。

串的基本操作

和线性表差别较大。 线性表的基本操作大多以“单个元素”作为操作对象，比如删除一个元素，初始化一个结点，插入一个结点等，而串的基本操作通常以“串这个整体”作为操作对象。比如在串中查找某个子串、在串的某个位置上插入一个子串、删除一个子串，子串的模式匹配等。

串的存储结构

串有两种表示形式：顺序存储表示和链式存储表示。

串的逻辑结构：串的逻辑结构和线性表很相似。

串和线性表的区别：串的数据对象，我们约定是字符集，也就是说，字符串是数据受限的！而线性表的数据对象，不一定是字符集！可以存储整数，浮点数等。

顺序存储表示：串的顺序存储结构简称为顺序串，顺序串中的字符序列被顺序地存放在一组连续的存储单元中，主要有三种存储结构。

（串也是一类特殊的线性表，故其存储结构与线性表的存储结构类似，只不过组成串的结点是单个字符而已。）

***定长顺序存储

也称为静态存储分配的顺序串。即用一组地址连续的存储单元依次存放串中的字符序列。“定长”、“静态”的意思可简单地理解为一个确定的存储空间，它的长度是不变的。

串长的表示方法：

（1）在串的存贮区首地址显式地记录串的长度，方便使用。

（2）在串之后加结束标志，隐式记录串的长度，不直观，如 使用 “\0”。这里使用的是1）中的显式方式记录串长度。

注意：

（1）串的实际长度可在这个预定义长度的范围内随意设定，超过预定义长度的串值则被舍去，称之为“截断”。

（2）字符类型存储的是对应字符在 ASCII 里的值，10进制表示。

缺点 ：
1、需事先预定义串的最大长度，这在实际的程序运行前是很难估计的。
2、由于定义了串的最大长度，使得串的某些操作受限（截尾），如串的联接、插入、置换等运算。
**克服办法：**不限定最大长度——动态分配串值的存储空间。

***堆分配存储

1、仍以一组空间足够大的、地址连续的存储单元依次存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配的，C 语言中提供的串类型就是以这种存储方式实现的。
2、由动态分配函数 malloc() 分配一块实际串长所需要的存储空间（“堆”），如果分配成功，则返回此空间的起始地址，作为串的基址，由 free( ) 释放串不再需要的空间。

typedef struct {
    char *chr;//存放串的首地址
    int len;
} strHeap;

这样分配的字符串，对分配的，可以动态改变长度，进行串的复制，插入，连接，置换算法等

优点：

既有顺序存储结构的特点，处理方便，操作中对串长没有任何限制，更加灵活，在串的处理中经常会应用到。

***块链存储

堆分配，是顺序表的动态分配的演化，自然有链表的演化，串值也可用单链表存储，简称为链串。 链串与单链表的差异只是它的结点数据域为单个字符。

优点：
便于插入和删除
缺点：
空间利用率低 。

基本操作

1）字符串操作

strcpy(p, p1) 复制字符串

strncpy(p, p1, n) 复制指定长度字符串

strcat(p, p1) 附加字符串

strncat(p, p1, n) 附加指定长度字符串

strlen§ 取字符串长度

strcmp(p, p1) 比较字符串

strcasecmp忽略大小写比较字符串

strncmp(p, p1, n) 比较指定长度字符串

strchr(p, c) 在字符串中查找指定字符

strrchr(p, c) 在字符串中反向查找

strstr(p, p1) 查找字符串

strpbrk(p, p1) 以目标字符串的所有字符作为集合，在当前字符串查找该集合的任一元素

strspn(p, p1) 以目标字符串的所有字符作为集合，在当前字符串查找不属于该集合的任一元素的偏移

strcspn(p, p1) 以目标字符串的所有字符作为集合，在当前字符串查找属于该集合的任一元素的偏移

（ 具有指定长度的字符串处理函数在已处理的字符串之后填补零结尾符 ）

2）字符串到数值类型的转换

strtod(p, ppend) 从字符串 p 中转换 double 类型数值，并将后续的字符串指针存储到 ppend 指向的 char* 类型存储。

strtol(p, ppend, base) 从字符串 p 中转换 long 类型整型数值，base 显式设置转换的整型进制，设置为 0 以根据特定格式判断所用进制，0x, 0X 前缀以解释为十六进制格式整型，0 前缀以解释为八进制格式整型

atoi§ 字符串转换到 int 整型

atof§ 字符串转换到 double 符点数

atol§ 字符串转换到 long 整型

3）字符检查

isalpha() 检查是否为字母字符

isupper() 检查是否为大写字母字符

islower() 检查是否为小写字母字符

isdigit() 检查是否为数字

isxdigit() 检查是否为十六进制数字表示的有效字符

isspace() 检查是否为空格类型字符

iscntrl() 检查是否为控制字符

ispunct() 检查是否为标点符号

isalnum() 检查是否为字母和数字

isprint() 检查是否是可打印字符

isgraph() 检查是否是图形字符，等效于 isalnum() | ispunct()

代码实现

#include<iostream>
#include<malloc.H>

using namespace std;
typedef int Status;

#define Max 20
#define OK 1
#define ERROR 0
#define OVERLOE -2

typedef struct//堆分配表示串
{
 char *ch;
 int length;
}HString;

Status CreatHString(HString &H)//构造字符串
{
 H.length = 0;
 H.ch = (char *)malloc(Max*sizeof(char));
 for (int i = 0; i < Max; i++)
 {
 H.ch[i]=getchar();
 H.length++;
 if (getchar() == '\n')
  break;
 }
 return OK;
}

Status PrintHString(HString H)//输出所输入的字符串
{
 if (H.length == 0)
 {
 cout << "空串！" << endl;
 return ERROR;
 }
 else
 for (int i = 0; i < H.length; i++)
  cout << H.ch[i] << " ";
 cout << endl;
 return OK;
}

Status HStringLength(HString H)//求字符串的长度
{
 cout << "您输入的字符串长度为：" << endl;
 cout << H.length << endl;
 return OK;
}

Status HStringCompare(HString H, HString T)//求两个字符串长度差（绝对值）
{
 cout << "两个字符串的长度差为：" << endl;
 int L;
 L = H.length - T.length;
 if (L<0)
 cout << -L << endl;
 if (L>=0)
 cout << L << endl;
 return OK;
}

Status ConcatHString(HString &S, HString H, HString T)//链接H和T
{
 if (!(S.ch = (char *)malloc((H.length + T.length)*sizeof(char))))
 exit(OVERLOE);
 for (int i = 0; i < H.length; i++)
 S.ch[i] = H.ch[i];
 S.length = H.length + T.length;
 for (int j = H.length; j < S.length; j++)
 S.ch[j] = T.ch[j-H.length];
 return OK;
}

Status SubHString(HString &Sub, HString S, int pos,int len)//用Sub返回串S的第pos个字符起长度为len的子串
{
 if (pos<1 || pos>S.length)
 {
 cout << "输入的位置有误！" << endl;
 return ERROR;
 }
 if (len<0 || len>S.length - pos + 1)
 {
 cout << "输入的长度有误！" << endl;
 return ERROR;
 }
 if (!len)
 {
 Sub.ch == NULL;
 Sub.length = 0;
 }
 else
 {
 Sub.ch = (char *)malloc(len*sizeof(char));
 for (int i = 0; i < len ; i++)
  Sub.ch[i] = S.ch[pos + i - 1];
 Sub.length = len;
 }
 return OK;
}//SubHString

Status ClearHString(HString &H)//将H清为空串
{
 if (H.ch)
 {
 free(H.ch);
 H.ch = NULL;
 }
 H.length = 0;
 return OK;
}//ClearHString

int main()
{
 HString S,H,T;
 cout << "请输入一个字符串（按回车键结束）：" << endl;
 CreatHString(H);
 cout << "现在串中的字符为：" << endl;
 PrintHString(H);
 HStringLength(H);
 cout << "请再输入一个字符串（按回车键结束）：" << endl;
 CreatHString(T);
 HStringCompare(H, T);
 ConcatHString(S, H, T);
 cout << "现在串中的字符为：" << endl;
 PrintHString(S);
 HString Sub;
 int pos, len;
 cout << "请输入截取位置pos及长度len：" << endl;
 cin >> pos >> len;
 SubHString(Sub, S, pos, len);
 cout << "截取的子串为：" << endl;
 PrintHString(Sub);
 ClearHString(S);
 cout << "检验S清空后是否为空：" << endl;
 PrintHString(S);
}
 

样例输出