【数据结构】【线性表】特殊的线性表-字符串
目录
字符串的基本概念
字符串的三要素
字符串的基本概念
串的编码
串的实现及基本运算
顺序串的实现
串的静态数组实现
串的动态数组的实现
顺序存储的四种方案
链式串的实现
基本运算
方案三
方案一
字符串的基本概念
数据结构千千万，但距离我们最近的还是字符串。在这里我们定义：有限个字符组成的序列为字符串。在大多数人看来，字符串仅仅是一个char类型的数组，但在作者看来，数组也是一种特殊的线性表。回想顺序表、顺序栈、顺序队列这些都和数组有着千丝万缕的联系。但在我们这里要讲的字符串，它的格式不仅仅是数组格式，数组格式只是串格式的众多种类中的一种。
我们回顾数据结构的三要素：逻辑结构、物理结构和基本运算。线性表是指元素之间的逻辑结构为线性的一系列的数据结构，其特点是一对一。类似的，字符串各个元素之间的逻辑结构也可以视为线性，因此字符串是一种特殊的线性表。
字符串的三要素
- 逻辑结构：线性结构
- 物理结构：顺序存储/链式存储
- 基本运算
- StrCopy(&T,S)复制串，将串S复制到串T；
- StrEmpty(S)串判空，判断串S是否为空串；
- StrLength(S)求串长，求串S的长度；
- ClearStr(S)清空串，清空串S，使其成为空串；
- DestroyStr(&S)销毁串，清空串并释放其内存空间；
- ConcatStr(&T,S1,S2)串连两个串，在S1串后面链接上S2成为一个串T；
- SubString(&Sub,S,pos,len)求子串，求串S以pos为起点，长度为len的子串；
- StrCompare(S,T)比较串，比较串S与T，S>T则返回值大于0;S=T则返回值等于0;S<T则返回值小于0；
- Index(S,T)定位子串，如果主串S中存在与T相同的子串，则返回主串第一次出现子串的第一个位置；
上述基本操作涉及到一些串的相关名词，在这里作一下定义说明，没有疑问的可跳过。
字符串的基本概念
字符串：有限个字符组成的序列
- 串长：有限字符的个数n
- 空串：有限字符个数为0
- 空格串：串内所有字符均为空格；例如：“ ”
- 主串和子串：这是一个相对概念，一般来说，把一个完整的字符串当成主串，而子串是从主串中任意提出来的连续字符组成的序列。
例如:
a="qwer1314"；
b="qwer"
c="1314",
d="wer1",
在这里b c d均是a的子串
注意空串和空格串，空串里面没有一个字符，而空格串是包含了字符，只不过这个字符是空格。
串的编码
- 英文字符：ASCII码等。
- 中英文字符：UTF8、UTF16、GB2312等。
我们知道，计算机的存储是二进制的，也就是说无论什么字符，其存储的数据都是二进制，那么如何将二进制数与符号相对应，这就是我们的编码。编码是一种规则，一个二进制数通过这个规则对应表示一个字符。抽象理解成一个y=f(x)的函数，自变量x为二进制数，编码为映射规则f，因变量为字符集y。满足函数一一对应的性质。编码有多种多样的，例如BCD码，格雷码等。
ASCII码是我们最常用的一种编码，其存储空间一般为1B。它包含了我们常见的大部分英文字符，例如26个大小写英文字母，数字，空格等。其具体的ASCII表在网上众多，我就不一一赘述了。
UTF8、UTF16、GB2312都是包含了中英文字符的编码，在需要使用中文的体系中常用，但需要注意的是使用这几种的人数较多较杂，不像英文字符大部分人都用ASCII，这几种也很多人使用，因此我们在打开其他人的文件时很容易出现乱码，其主要原因就是你打开打编码方式与他写的编码方式不一致。因此当遇到乱码，应当及时更正打开文件的编码方式。
串的实现及基本运算
顺序串的实现
顺序串即存储结构为连续顺序的字符串，和顺序表类似，其构建方法一般可以分为静态数组和动态数组两种。
串的静态数组实现
#define MaxSize 100;//定义最大分配空间为100个
typedef struct{
char str[MaxSize];//定义静态字符数组
int length;//定义串的实际长度
}SString;静态数组在分配得到时候固定了大小空间
串的动态数组的实现
typedef struct{
char *str;
int length;
}HString;动态数组只分配了数组的基址，大小可自己拓展。在应用过程中拓展需要用到malloc函数，同时销毁元素时也要手动free空间。
顺序存储的四种方案
方案1是最常见的格式，也是一般字符串的默认格式，不包含表长元素，以'\0'作为结尾符号；
方案2是我们默认使用的格式，前面是串的各个字符元素，最后存放表长元素；
方案3是舍弃数组的第一个元素，使数组下标与字符的位序对其，最后存放表长元素；
方案4不单独设置表长元素，将串的字符数组的第一个元素存放表长数据， 同时也让数组下标与字符位序对齐；但表长元素的数据类型是int，字符数组的数据类型是char，使用中有很多需要注意，因此实用性不是很好。
四个方案相较而言方案3更具有优势，但方案1的普遍性更强。
链式串的实现
链式串的物理结构类似于单链表，每个结点存放一组数据，并指向下一个结点，结构示意图：
其中S是头结点，从1开始才是串的实际字符数据；当然采用无头结点的串也是可以的，只需要注意第一个结点特殊处理就行。
typedef struct StringNode{
char str;//每个结点存储一个字符
struct StringNode *next;//指向下一个结点
}StringNode,*String;一般而言我们会采用一个结点储存一个字符，但有些特殊情况下需要一个结点储存固定长度的字符，同时也节省空间。
typedef struct StringNode{
char str[4];//每个结点存储4个字符
struct StringNode *next;//指向下一个结点
}StringNode,*String;基本运算
在讲基本操作之前，我们先确定一下其串的格式，物理存储格式决定这基本运算的操作思路、步骤与顺序。从编程的逻辑性和简易性而言，方案三是最合适的。
但又考虑到普遍的字符串存储格式是方案一：
因此我们选择在方案三的基础上完成思路和源码的讲解，同时展示完整的方案一源码，在源码中简单讲解。
方案三
方案三字符串结构体创建
#define MaxSize 100;//定义最大分配空间为100个
typedef struct{
char str[MaxSize];//定义静态字符数组
int length;//定义串的实际长度
}SString;
/*初始化串*/
void InitString(SString &S){
for(int i=0;i<MaxSize;i++)//将所有值设定为字符串终止符，也可以是别的没歧义的内容
S.str[i]='\0';
S.length=0;//初始化字符串长度为0
}复制串，将串S复制得到串T
void StrCopy(SString &T,SString S){
T.length=S.length;
for(int i=1;i<=T.length;i++){
T.str[i]=S.str[i];
}
}串判空，判断串是否为空串，是返回true，不是返回false
bool StrEmpty(SString S){
if(S.length==0)//字符串长度为0则为空字符串
return true;
else if(S.length>0)
return false;
}求串长，在这个格式下有点多此一举，但也还是说明一下吧
int StrLength(SString S){
return S.length;
}清空串，使其成为空串，但其实在这里没办法真的成为空，毕竟空间就在那，一般操作方式是给每个字符空间赋值为特殊值，例如0或者'\0'，然后修改表长。对于char数据类型建议赋值为'\0'；对于其他int或者float建议赋值为0
void ClearString(SString &S){
for(int i=0;i<=S.length;i++)
S.str[i]='\0';
S.length=0;
}销毁串，因为这个结构采用的是静态数组，静态数组不需要手动释放空间，内存会在超出变量作用域时自动释放空间。
连接串，串连两个串，在S1串后面连接上S2成为一个串T；
bool ConcatString(SString &T,SString S1,SSrting S2){
T.length=S1.length+S2.length;//拼接后的长度
if(T.length+1>MaxSize)//判断长度是否超限
return false;//长度超限，拼接失败
for(int i=1;i<=S1.length;i++)//将S1的数据复制到T
T.str[i]=S1.str[i];
for(int i=1;i<=S2.length;i++)//将S2的数据复制到S1后面
T.str[S1.length+i]=S2.str[i];
return true;//拼接成功
}求子串，求主串S第pos位开始的长len的子串
bool SubString(SString &Sub,SString S,int pos,int len){
if(pos+len-1>S.length)//判断子串是否越界
return false;//子串越界，获取子串失败
Sub.length=len;//子串长度为len
for(int i=1;i<len+1;i++)//读取子串并复制给Sub
Sub.str[i]=S.str[i+pos-1];
Sub.str[i]='\0';//给子串添加终止符
return true;//获取子串成功
}
StrCompare(S,T)比较串，比较串S与T，S>T则返回值大于0;S=T则返回值等于0;S<T则返回值小于0。
有人就说了字符串怎么能比较呢？这也是作者刚开始疑惑的问题，字符串比什么，除了能比一不一样还能干嘛？所以在比较字符串之前一定要有比较的标准，制定比较标准时需要注意以下三个要点
- 要不要考虑字符的大小写
- 字符串的长度
- 对于特殊字符和不同编码如何处理
下面我们先制定字符串比较的规则：
- 比较对字符大小写敏感，直接按顺序比较字符在ASCLL的码值，先出现更大字符的串更大
- 考虑字符串长度，长串前缀与短串字符一致时，长串更大
- 不考虑特殊字符，默认均为ASCII码
int StrCompare(SString S,SString T){
//遍历查找两个字符串每个位置的字符比较情况
for(int i=1;i<=S.length && i<=T.length;i++){
if(S.str[i]!=T.str[i])//字符不相同则相减并返回
return S.str[i]-T.str.[i];
}
return S.length-T.length;//
}定位子串， 如果主串S中存在与T相同的子串，则返回主串第一次出现子串的第一个位置。
int IndexStr(SString S,SString T){
int m=S.length;
int n=t.length;
int flag;
SString Sub;
for(int i=1;i<=n-m+1;i++){
/*取出字符串S中长度为n的子串*/
if(i+n-1>S.length)//判断子串是否越界
return 0;//子串越界，获取子串失败
Sub.length=n;//子串长度为n
for(int j=1;j<=n;j++)//读取子串并复制给Sub
Sub.str[j]=S.str[j+i-1];
/*比较T与S的子串Sub*/
for(int j=1;j<=S.length && j<=T.length;j++){
if(S.str[j]!=Sub.str[j])
flag=T.str[j]-Sub.str[j];
}
flag=S.length-T.length;
/*判断两串是否相等*/
if(flag==0)
return i;
}
return 0;//没有到与T相等的子串
}上述代码中有求子串和比较子串的操作，我们采用源码表示，但也可以直接用函数：
int IndexStr(SString S,SString T){
int m=S.length;
int n=t.length;
bool flag;
SString Sub;
for(int i=1;i<=n-m+1;i++){
/*取出字符串S中长度为n的子串*/
flag=SubString(Sub,S,i,n);
if(flag==false)
return 0;//子串违法
/*判断两串是否相等*/
if(StrCompare(T,Sub)==0)
return i;
}
return 0;//没有到与T相等的子串
}方案一
方案一是最常见的字符串类型例如：
char str[]="qwer1314";这种方式不需要结构体，同时也是我们在大多数场合输入字符串的默认格式，因此在这里我们再次进行代码讲解；
/*将字符串S复制给T*/
void StrCopy(char *S,char *T){
int i=0;
while(S[i]!='\0'){
T[i]=S[i];
i++;
}
T[i]='\0';
}
/*判定字符串S是否为空*/
bool StrEmpty(char *S){
if(S[0]=='\0')
return true;
else
return false;
}
/*求字符串S的长度*/
int StrLength(char *S){
int len=0;
while(S[len]!='\0'){
len++;
}
return len;
}
/*清空字符串*/
void ClearString(char *S){
int i=0;
while(S[i]!='\0'){
S[i]='\0';
i++;
}
}
/*串联两个字符串*/
char *ConcatStr(const char *str1, const char *str2) {
// 检查输入是否为NULL
if (str1 == NULL || str2 == NULL) {
return NULL;
}
// 计算新字符串的长度
int len1 = StrLength(str1);
int len2 = StrLength(str2);
int newLen = len1 + len2 + 1;
// 分配内存
char *result = (char *)malloc(newLen * sizeof(char));
if (result == NULL) {
// 内存分配失败
return NULL;
}
// 复制第一个字符串到结果中
int i = 0;
while (i < len1) {
result[i] = str1[i];
i++;
}
// 连接第二个字符串到结果中
int j = 0;
while (j < len2) {
result[i + j] = str2[j];
j++;
}
// 添加终止符
result[i + j] = '\0';
return result;
}
/*求子串*/
char *SubString(char *str, int pos, int len) {
int length = StrLength(str);
if (pos + len > length || pos < 0 || len < 0) {
return NULL; // 检查边界条件
}
// 分配内存
char *result = (char *)malloc((len + 1) * sizeof(char));
if (result == NULL) {
return NULL; // 检查内存分配是否成功
}
for (int i = 0; i < len; i++) {
result[i] = str[pos + i];
}
result[len] = '\0'; // 添加字符串结束符
return result;
}
/*比较字符串*/
int Strcompare(char *str1,char *str2){
int len1=StrLength(str1),len2=StrLebgth(str2);
for(int i=0;i<len1 && i<len2;i++){
if(str1[i]!=str2[i])
return str1[i]-str2[i];
}
return len1-len2;
}
/*定位字符串*/
int Index(char *str1,char *str2){
int m=StrLength(str1);
int n=StrLength(str2);
bool flag;
char *Sub;
for(int i=1;i<=n-m+1;i++){
/*取出字符串S中长度为n的子串*/
Sub=SubString(S,i,n);
if(flag==NULL)
return 0;//子串违法
/*判断两串是否相等*/
if(StrCompare(S,Sub)==0)
return i;
}
return 0;//没有到与T相等的子串
}常见字符串操作：
将字符串转换成int
//字符串转化为int
int string_int(char *str) {
if (str == NULL || *str == '\0') {
// 输入为空或空字符串
return 0;
}
int num = 0;
int i = 0;
int flag = 1;
// 检查负号
if (str[i] == '-') {
flag = -1;
i++;
}
// 转换数字部分
while (str[i] >= '0' && str[i] <= '9') {
int digit = str[i] - '0';
// 检查是否会发生溢出
if (num > (INT_MAX - digit) / 10) {
// 发生溢出，返回0或其他错误值
return 0;
}
num = num * 10 + digit;
i++;
}
return flag * num;
}将int转化为字符串
char *int_string(int num) {
// 假设整数最多有11位（包括负号）
char *str = (char *)malloc(12 * sizeof(char)); // 分配内存用于存储转换后的字符串
if (str == NULL) {
return NULL; // 如果内存分配失败，返回NULL
}
int i = 0; // 用于记录当前字符的位置
int isNegative = 0; // 标记是否为负数
if (num < 0) {
isNegative = 1; // 如果是负数，设置标记并取绝对值
num = -num;
}
// 将数字转换为字符串
do {
str[i++] = (num % 10) + '0'; // 将最低位的数字转换为字符并存储
num /= 10; // 去掉已经处理的最低位
} while (num > 0);
if (isNegative) {
str[i++] = '-'; // 如果是负数，添加负号
}
// 反转字符串
for (int j = 0; j < i / 2; j++) { // 注意这里需要声明j的类型为int
char temp = str[j];
str[j] = str[i - j - 1];
str[i - j - 1] = temp;
}
// 添加字符串终止符
str[i] = '\0';
return str; // 返回转换后的字符串
}
将字符串转换成float
// 将字符串转换为浮点数的函数
float string_float(char *str) {
// 如果输入为空或空字符串，返回0.0f
if (str == NULL || *str == '\0') {
return 0.0f;
}
// 初始化变量
float num = 0.0f; // 最终结果
int i = 0; // 当前字符索引
int flag = 1; // 符号标志，1表示正数，-1表示负数
int fractional_part = 0; // 是否处理小数部分的标志
float fractional_divisor = 1.0f; // 小数部分的除数
// 检查负号
if (str[i] == '-') {
flag = -1;
i++;
}
// 转换数字部分和小数部分
while (str[i] != '\0') {
if (str[i] >= '0' && str[i] <= '9') {
int digit = str[i] - '0'; // 将字符转换为数字
if (fractional_part) {
// 处理小数部分
fractional_divisor *= 10.0f;
num += digit / fractional_divisor;
} else {
// 处理整数部分
if (num > (FLT_MAX - digit) / 10.0f) {
// 发生溢出，返回0或其他错误值
return 0.0f;
}
num = num * 10.0f + digit;
}
} else if (str[i] == '.' && !fractional_part) {
// 遇到小数点，开始处理小数部分
fractional_part = 1;
} else {
// 非法字符，直接返回当前结果
break;
}
i++;
}
// 返回最终结果，考虑符号
return flag * num;
}
将float转换为字符串
// 将浮点数转换为字符串的函数
char *float_string(float num) {
// 假设浮点数最多有38位（包括负号、小数点和指数）
char *str = (char *)malloc(40 * sizeof(char)); // 分配内存用于存储转换后的字符串
if (str == NULL) {
return NULL; // 如果内存分配失败，返回NULL
}
int i = 0; // 用于记录当前字符的位置
int isNegative = 0; // 标记是否为负数
if (num < 0) {
isNegative = 1; // 如果是负数，设置标记并取绝对值
num = -num;
}
// 处理整数部分
int integerPart = (int)num; // 获取整数部分
do {
str[i++] = (integerPart % 10) + '0'; // 将整数部分逐位转换为字符并存储
integerPart /= 10; // 去掉已经处理的最低位
} while (integerPart > 0);
if (isNegative) {
str[i++] = '-'; // 如果是负数，添加负号
}
// 反转整数部分，使其按正确顺序排列
for (int j = 0; j < i / 2; j++) {
char temp = str[j];
str[j] = str[i - j - 1];
str[i - j - 1] = temp;
}
// 添加小数点
str[i++] = '.';
// 处理小数部分
float fractionalPart = num - (int)num; // 获取小数部分
int precision = 6; // 设置精度为6位小数
for (int k = 0; k < precision; k++) {
fractionalPart *= 10; // 将小数部分放大10倍
int digit = (int)fractionalPart; // 获取当前最高位的小数
str[i++] = digit + '0'; // 将小数转换为字符并存储
fractionalPart -= digit; // 去掉已经处理的最高位小数
}
// 添加字符串终止符
str[i] = '\0';
return str; // 返回转换后的字符串
}