目录
数据结构-串(第四章)的整理笔记，若有错误，欢迎指正。
可以参考和对比一下C语言里面的字符串：C语言 字符串
串的基本概念：
- 串(string)是由零个或多个字符组成的有限序列。
- 两个串相等当且仅当这两个串的长度相等并且对应位置的字符都相同。
- 一个串中任意个连续字符组成的序列称为该串的子串(substring)。
- 含零个字符的串称为空串，用∅表示。空串是不包含任何字符的串，其长度为0，空串是任何串的子串。
设S为一个长度为n的字符串，其中的字符各不相同，则S中子串的个数为 n ( n + 1 ) 2 + 1 \frac{n(n+1)}{2}+1 2n(n+1)+1；
互异非平凡子串(非空且不同于S本身)的个数为 n ( n + 1 ) 2 + 1 − 2 \frac{n(n+1)}{2}+1-2 2n(n+1)+1−2(减去空串和等于自身的两种情况)= n ( n + 1 ) 2 − 1 \frac{n(n+1)}{2}-1 2n(n+1)−1
串 的 基 本 操 作 { S t r A s s i g n ( & s , c s t r ) — 生 成 串 D e s t r o y S t r ( & s ) — 销 毁 串 S t r C o p y ( & s , t ) — 串 的 复 制 S t r E q u a l ( s , t ) — 判 断 串 相 等 S t r L e n g t h ( s ) — 求 串 长 C o n c a t ( s , t ) — 串 的 连 接 S u b S t r ( s , i , j ) — 求 子 串 I n s S t r ( s 1 , i , s 2 ) — 子 串 的 插 入 D e l S t r ( s , i , j ) — 子 串 的 删 除 R e p S t r ( s , i , j , t ) — 子 串 的 替 换 D i s p S t r ( s ) — 输 出 串 串的基本操作\begin{cases} StrAssign(\&s, cstr)—生成串\\ DestroyStr(\&s)—销毁串\\ StrCopy(\&s,t)—串的复制\\ StrEqual(s,t)—判断串相等\\ StrLength(s)—求串长\\ Concat(s,t)—串的连接\\ SubStr(s,i,j)—求子串\\ InsStr(s1,i,s2)—子串的插入\\ DelStr(s,i,j)—子串的删除\\ RepStr(s,i,j,t)—子串的替换\\ DispStr(s)—输出串\\ \end{cases} 串的基本操作⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧StrAssign(&s,cstr)—生成串DestroyStr(&s)—销毁串StrCopy(&s,t)—串的复制StrEqual(s,t)—判断串相等StrLength(s)—求串长Concat(s,t)—串的连接SubStr(s,i,j)—求子串InsStr(s1,i,s2)—子串的插入DelStr(s,i,j)—子串的删除RepStr(s,i,j,t)—子串的替换DispStr(s)—输出串
串的顺序存储结构——顺序串
- 顺序串中的字符被依次存放在一组连续的存储单元里。一般来说，一个字节(8位)可以表示一个字符(存放其ASCII码)。而计算机内存是按字编址的，即以字为存储单位，一个存储单元指的是一个字。而一个字可能包含多个字节，其所包含的字节数随机器而异。
- 顺序串的存储方式有两种：
一种是每个字只存一个字符(假设一个字包含4个字节)，这称为非紧缩格式(其存储密度小)。
另ー种是每个字存放多个字符，这称为紧缩格式(其存储密度大)。
- 其中，灰色方块代表字节为空闲。
- 串的紧缩式节省存储空间，但处理单个字符不太方便，运算效率低，因为需要花费时间从同一个字中分离字符；相反，非紧缩式比较浪费存储空间，但处理单个字符或者一组连续字符方便。
一. 静态分配
类型声明(非紧缩格式)
typedef struct
{
char data[MaxSize]; //存放字符串字符
int length; //存放串长
}SqString; //顺序串类型
分析
- 串的实际长度只能小于等于MaxSize，超过预定义长度的串值会被舍去，称为載断。
- 串长有两种表示方法：一是如上述定义描述的那样，用一个额外的变量length来存放串的长度；二是在串值后面加一个不计入串长的结東标记字符“\0”，此时的串长为隐含值。
生成串—StrAssign(&s, cstr)
- 将一个C/C++字符串常量cstr(以"\0"字符标识结尾)赋给顺序串s，即生成一个其值等于cstr的串s。
void StrAssign(SqString &s, char cstr[]) //s为引用型参数
{
int i;
for (i = 0; cstr[i] != '\0'; i++)
s.data[i] = cstr[i];
s.length = i; //设置串s的长度
}
销毁串— DestroyStr(&s)
void Destroy(SqString &s)
{ }
分析
- 由于顺序串是直接采用顺序串本身来表示的，而不是顺序串指针，它的存储空间由操作系统管理，即由操作系统分配其存储空间，并在超出作用域时释放其存储空间，所以这里的销毁顺序串运算不包含任何操作。
串的复制—StrCopy(&s,t)
- 将顺序串t赋值给顺序串s。
void StrCopy(SqString& s, SqString t)
{
int i;
for (i = 0; i < t.length; i++) s.data[i] = t.data[i];
s.length = t.length; //设置串s的长度
}
判断串相等—StrEqual(s,t)
- 若两个顺序串s与t相等返回真；否则返回假。
bool StrEqual(SqString s, SqString t)
{
bool same = true;
int i;
if (s.length != t.length) same = false; //长度不相等时返回0
else
for (i = 0; i < s.length; i++)
if (s.data[i] != t.data[i]) //有一个对应字符不相同时返回假
{
same = false;
break;
}
return same;
}
分析
- 参照C语言中的strcmp函数(字符串比较函数)
字符串处理函数
求串长—StrLength(s)
int StrLength(SqString s)
{ return s.length; }
分析
- 参照C语言中的strlen函数(测字符串长度函数)
字符串处理函数
串的连接—Concat(s,t)
- 返回由两个顺序串s和t连接在一起形成的结果串。
SqString Concat(SqString s, SqString t)
{
SqString str; //定义结果串
int i;
str.length = s.length + t.length;
for (i = 0; i < s.length; i++) str.data[i] = s.data[i]; //将s.data[0..s.length-1]复制到str
for (i = 0; i < t.length; i++) str.data[s.length + i] = t.data[i]; //将t.data[0..t.length-1]复制到str
return str;
}
分析
- 参照C语言中的strcat函数(字符串连接函数)
字符串处理函数
求子串—SubStr(s,i,j)
- 返回顺序串s中从第i(1≤i≤n)个字符开始的由连续j个字符组成的子串。当参数不正确时返回一个空串。
SqString SubStr(SqString s, int i, int j)
{
int k;
SqString str; //定义结果串
str.length = 0; //设置str为空串
if (i <= 0 || i > s.length || j<0 || i + j - 1>s.length) return str; //参数不正确时返回空串
for (k = i - 1; k < i + j - 1; k++) str.data[k-i+1] = s.data[k]; //将s.data[i..i+j-1]复制到str
str.length = j;
return str;
}
分析
- 空串是不包含任何字符的串，其长度为0，空串是任何串的子串。
子串的插入—InsStr(s1,i,s2)
- 将顺序串s2插入到顺序串s1的第i(1≤i≤n+1)个位置上，并返回产生的结果串。当参数不正确时返回一个空串。
SqString InsStr(SqString s1, int i, SqString s2)
{
int j;
SqString str; //定义结果串
str.length = 0; //设置str为空串
if (i<=0 || i>s1.length+1) return str; //参数不正确时返回空串
for (j = 0; j < i-1; j++) str.data[j] = s1.data[j]; //将s1.data[0..i-2]复制到str
for (j = 0; j < s2.length; j++) str.data[i+j-1] = s2.data[j]; //将s2.data[0..s2.length-1]复制到str
for (j = i-1; j < s1.length; j++) str.data[j + s2.length] = s1.data[j]; //将s1.data[i-1..s1.length-1]复制到str
str.length = s1.length + s2.length;
return str;
}
子串的删除—DelStr(s,i,j)
- 在顺序串s删去从第i(1≤i≤n+1)个字符开始的长度为j的子串，并返回产生的结果串。当参数不正确时返回一个空串。
SqString DelStr(SqString s, int i, int j)
{
int k = 0;
SqString str; //定义结果串
str.length = 0; //设置str为空串
if (i <= 0 || i > s.length || j<0 || i + j - 1>s.length) return str; //参数不正确时返回空串
for (k = 0; k < i - 1; k++) str.data[k] = s.data[k]; //将s.data[0..i-2]复制到str
for (k = i + j - 1; k < s.length; k++) str.data[k - j] = s.data[k]; //将s.data[i+j-1..s.length-1]复制到str
str.length = s.length - j;
return str;
}
子串的替换—RepStr(s,i,j,t)
- 在顺序串s中将第i(1≤i≤n)个字符开始的连续j个字符构成的子串用顺序串t替换并返回产生的结果串。当参数不正确时返回一个空串。
SqString RepStr(SqString s, int i, int j,SqString t)
{
int k = 0;
SqString str; //定义结果串
str.length = 0; //设置str为空串
if (i <= 0 || i > s.length || j<0 || i + j - 1>s.length) return str; //参数不正确时返回空串
for (k = 0; k < i - 1; k++) str.data[k] = s.data[k]; //将s.data[0..i-2]复制到str
for (k = 0; k <t.length ; k++) str.data[i-1+k] = t.data[k]; //将t.data[0..t.length-1]复制到str
for (k = i + j - 1; k < s.length; k++) str.data[t.length + k - j] = s.data[k]; //将s.data[i+j-1..s.length-1]复制到str
str.length = s.length - j + t.length;
return str;
}
输出串—DispStr(s)
- 输出顺序串s的所有元素值。
void DispStr(SqString s)
{
int i;
if (s.length > 0)
for (i = 0; i < s.length; i++)
printf("%c", s.data[i]);
}
主函数验证
int main()
{
SqString s, t, str;
char cstr1[] = "How are you?";
//生成串s和t
printf("-----生成串s和t-----\n");
StrAssign(s, cstr1);
printf("s：");
DispStr(s);
printf("\ns.length=%d\n", StrLength(s));
char cstr2[] = "I'm fine.";
StrAssign(t, cstr2);
printf("t：");
DispStr(t);
printf("\nt.length=%d\n", StrLength(t));
//串的连接
printf("\n-----串的连接-----\n");
str=ConStr(s, t);
printf("str：");
DispStr(str);
printf("\nstr.length=%d\n", StrLength(str));
//串的复制
printf("\n-----串的复制-----\n");
StrCopy(s, t);
printf("s：");
DispStr(s);
printf("\ns.length=%d\n", StrLength(s));
//判断串相等
printf("\n-----判断串相等-----\n");
printf("串s和t相等吗？—%d \n", StrEqual(s,t));
//求子串
printf("\n-----求子串-----\n");
str=SubStr(s, 5, 4);
printf("str：");
DispStr(str);
printf("\nstr.length=%d\n", StrLength(str));
//子串的删除
printf("\n-----子串的删除-----\n");
str = DelStr(s, 5, 3);
printf("str：");
DispStr(str);
printf("\nstr.length=%d\n", StrLength(str));
//子串的插入
printf("\n-----子串的插入-----\n");
str = RepStr(s, 1, 4, t);
printf("str：");
DispStr(str);
printf("\nstr.length=%d\n", StrLength(str));
return 0;
}
分析
- 运行结果：
二. 动态分配
- 在一些串的操作(如插入、连接等)中，若串值序列的长度超过上界MaxSize，约定用“截断”法处理，要克服这种弊端，只能不限定串长的最大长度，即采用动态分配的方式。
完整代码
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define InitSize 10
typedef char ElemType;
typedef struct
{
char *data; //存放字符串字符
int length; //存放串长
int MaxSize;
}SqString; //顺序串类型
void InitString(SqString &s)
{
s.data = (char*)malloc(sizeof(char) * InitSize);
s.MaxSize = InitSize;
}
bool IncreaseSize(SqString& s, int len)
{
char* p = s.data; //定义整型指针变量，指向队列的首地址
s.data = (char*)malloc(sizeof(char) * (InitSize + len)); //申请一片更大的连续的存储空间
for (int i = 0; i < InitSize; i++)
s.data[i] = p[i]; //将数据复制到新的存储区域中
s.MaxSize = InitSize + len; //队列的最大长度增加
free(p); //释放原来的内存空间
return true;
}
void StrAssign(SqString& s, char cstr[]) //s为引用型参数
{
int i;
if (s.MaxSize >= strlen(cstr))
for (i = 0; cstr[i] != '\0'; i++)
s.data[i] = cstr[i];
else
{
for (i = 0; i < InitSize; i++)
s.data[i] = cstr[i];
IncreaseSize(s, InitSize);
for (i = InitSize; cstr[i] != '\0'; i++)
s.data[i] = cstr[i];
}
s.length = strlen(cstr); //设置串s的长度
}
void Destroy(SqString &s)
{
free(s.data);
}
void StrCopy(SqString &s, SqString t)
{
int i;
for (i = 0; i < t.length; i++) s.data[i] = t.data[i];
s.length = t.length; //设置串s的长度
}
bool StrEqual(SqString s, SqString t)
{
bool same = true;
int i;
if (s.length != t.length) same = false; //长度不相等时返回0
else
for (i = 0; i < s.length; i++)
if (s.data[i] != t.data[i]) //有一个对应字符不相同时返回假
{
same = false;
break;
}
return same;
}
int StrLength(SqString s)
{
return s.length;
}
void DispStr(SqString s)
{
if (s.length > 0)
for (int i = 0; i < s.length; i++)
printf("%c", s.data[i]);
}
SqString ConStr(SqString s, SqString t)
{
SqString str; //定义结果串
str.data = (char*)malloc(sizeof(char) * (s.length + t.length));
int i;
str.length = s.length + t.length;
for (i = 0; i < s.length; i++) //将s.data[0..s.length-1]复制到str
str.data[i] = s.data[i];
for (i = 0; i < t.length; i++) //将t.data[0..s.length-1]复制到str
str.data[s.length + i] = t.data[i];
return str;
}
SqString SubStr(SqString s, int i, int j)
{
int k;
SqString str; //定义结果串
str.data = (char*)malloc(sizeof(char)*s.length);
str.length = 0; //设置str为空串
if (i <= 0 || i > s.length || j<0 || i + j - 1>s.length) return str; //参数不正确时返回空串
for (k = i - 1; k < i + j + 1; k++)
str.data[k - i + 1] = s.data[k]; //将s.data[i..i+j-1]复制到str
str.length = j;
return str;
}
SqString InsStr(SqString s1, int i, SqString s2)
{
int j;
SqString str; //定义结果串
int size = s1.length + s2.length;
str.data = (char*)malloc(sizeof(char) * size);
str.length = 0; //设置str为空串
if (i <= 0 || i > s1.length + 1) return str; //参数不正确时返回空串
for (j = 0; j < i - 1; j++) //将s1.data[0..i-2]复制到str
str.data[j] = s1.data[j];
for (j = 0; j < s2.length; j++) //将s2.data[0..s2.length-1]复制到str
str.data[i + j - 1] = s2.data[j];
for (j = i - 1; j < s1.length; j++) //将s1.data[i-1..s1.length-1]复制到str
str.data[j + s2.length] = s1.data[j];
str.length = s1.length + s2.length;
return str;
}
SqString DelStr(SqString s, int i, int j)
{
int k = 0;
SqString str; //定义结果串
str.data = (char*)malloc(sizeof(char) * s.length);
str.length = 0; //设置str为空串
if (i <= 0 || i > s.length || j<0 || i + j - 1>s.length) return str; //参数不正确时返回空串
for (k = 0; k < i - 1; k++) //将s.data[0..i-2]复制到str
str.data[k] = s.data[k];
for (k = i + j - 1; k < s.length; k++) //将s.data[i+j-1..s.length-1]复制到str
str.data[k - j] = s.data[k];
str.length = s.length - j;
return str;
}
SqString RepStr(SqString s, int i, int j, SqString t)
{
int k = 0;
SqString str; //定义结果串
int size = s.length + t.length;
str.data = (char*)malloc(sizeof(char) * size);
str.length = 0; //设置str为空串
if (i <= 0 || i > s.length || j<0 || i + j - 1>s.length) return str; //参数不正确时返回空串
for (k = 0; k < i - 1; k++) //将s.data[0..i-2]复制到str
str.data[k] = s.data[k];
for (k = 0; k < t.length; k++)
str.data[i - 1 + k] = t.data[k];
for (k = i + j - 1; k < s.length; k++) //将s.data[i+j-1..s.length-1]复制到str
str.data[t.length + k - j] = s.data[k];
str.length = s.length - j + t.length;
return str;
}
int main()
{
SqString s, t, str;
InitString(s);
InitString(t);
//生成串s和t
printf("-----生成串s和t-----\n");
char cstr1[] = "Are you Ok?";
StrAssign(s, cstr1);
printf("s：");
DispStr(s);
printf("\ns.length=%d\n", StrLength(s));
char cstr2[] = "Fine,thanks!";
StrAssign(t, cstr2);
printf("t：");
DispStr(t);
printf("\nt.length=%d\n", StrLength(t));
//串的连接
printf("\n-----串的连接-----\n");
str = ConStr(s, t);
printf("str：");
DispStr(str);
printf("\nstr.length=%d\n", StrLength(str));
//串的复制
printf("\n-----串的复制-----\n");
StrCopy(s, t);
printf("s：");
DispStr(s);
printf("\ns.length=%d\n", StrLength(s));
//判断串相等
printf("\n-----判断串相等-----\n");
printf("串s和t相等吗？—%d \n", StrEqual(s, t));
//求子串
printf("\n-----求子串-----\n");
str = SubStr(s, 6, 4);
printf("str：");
DispStr(str);
printf("\nstr.length=%d\n", StrLength(str));
//子串的删除
printf("\n-----子串的删除-----\n");
str = DelStr(s, 4, 6);
printf("str：");
DispStr(str);
printf("\nstr.length=%d\n", StrLength(str));
//子串的插入
printf("\n-----子串的插入-----\n");
str = RepStr(s, 6, 7, t);
printf("str：");
DispStr(str);
printf("\nstr.length=%d\n", StrLength(str));
return 0;
}
分析
- 运行结果：
