第四章4.2.1串的定长顺序存储表示
代码实现
main.cpp
#include <stdio.h> // printf(); scanf()
#include <stdlib.h> // exit(); malloc()
#include <time.h> // srand((unsigned)time(NULL));
#include <string.h>
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
// Status是函数的类型，其值是函数结果状态代码
typedef int Status;
// #define ElemType int // 也可以用宏定义确定ElemType类型
typedef int ElemType;
// -----串的定长顺序存储表示-----
#define MAXSTRLEN 25 // 用户可在255(1个字节)以内定义最大串长
typedef unsigned char SString[MAXSTRLEN + 1]; // 0号单元存放串的长度
#define DestroyString ClearString // DestroyString()与ClearString()作用相同
// 初始条件：chars是字符串常量。
// 操作结果：生成一个其值等于chars的串T。
Status StrAssign(SString &T, char *chars) {
if(strlen(chars) > MAXSTRLEN)
return ERROR;
else {
T[0] = strlen(chars); // 0号单元存放串的长度
for(int i=1; i<=T[0]; i++)
T[i] = *(chars+i-1);
return OK;
}
}
// 初始条件：串S存在。
// 操作结果：由串S复制得串T。
Status StrCopy(SString &T, SString S) {
for(int i=0; i<=S[0]; i++)
T[i] = S[i];
return OK;
}
// 初始条件：串S存在。
// 操作结果：若S为空串，则返回TRUE；否则返回FALSE。
Status StrEmpty(SString S) {
if(S[0] == 0)
return TRUE;
else
return FALSE;
}
// 初始条件：串S和T存在。
// 操作结果：若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0。
int StrCompare(SString S, SString T) {
int i;
for(i=1; i<=S[0] && i<=T[0]; ++i)
if(S[i] != T[i])
return S[i]-T[i];
return S[0]-T[0];
}
// 初始条件：串S存在。
// 操作结果：返回串S的元素个数，称为串的长度。
int StrLength(SString S) {
return S[0];
}
// 初始条件：串S存在。
// 操作结果：将S清为空串。
Status ClearString(SString S) {
S[0] = 0; // 令串长为零
return OK;
}
// 初始条件：串S1和S2存在。
// 操作结果：用T返回S1和S2联接而成的新串。
Status Concat(SString T, SString S1, SString S2) {
// 若未截断，则返回TRUE；否则返回FALSE。
int i;
if(S1[0]+S2[0] <= MAXSTRLEN) { // 未截断
for(i=1; i<=S1[0]; i++) // 将串S1赋给T
T[i] = S1[i];
for(i=1; i<=S2[0]; i++) // 将串S2赋给T中已有串S1的后面
T[S1[0]+i] = S2[i];
T[0] = S1[0] + S2[0]; // 新串的长度
return TRUE;
} else if(S1[0] < MAXSTRLEN) { // 截断S2的部分字符序列
for(i=1; i<=S1[0]; i++) // 将串S1赋给T
T[i] = S1[i];
for(i=1; i<=MAXSTRLEN-S1[0]; i++)// 将串S2未截断的部分赋给T中已有串S1的后面
T[S1[0]+i] = S2[i];
T[0] = MAXSTRLEN;
return FALSE;
} else { // 截断(仅取S1)
for(i=1; i<=MAXSTRLEN; i++) // 将串S1赋给T
T[i] = S1[i];
T[0] = MAXSTRLEN;
return FALSE;
}
}//Concat 算法 4.2
// 初始条件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。
// 操作结果：用Sub返回串S的第pos个字符起长度为len的子串。
Status SubString(SString Sub, SString S, int pos, int len) {
int i;
if(pos<1 || pos>S[0] || len<0 || len>S[0]-pos+1)
return ERROR;
for(i=1; i<=len; i++)
Sub[i] = S[pos+i-1];
Sub[0] = len;
return OK;
}//SubString 算法 4.3
// 初始条件：串S和T存在，T就非空串，1≤pos≤StrLength(S)。
// 操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置; 否则函数值为0。
int Index2(SString S, SString T, int pos) {
// T为非空串。若主串S中第pos个字符之后存在与T相等的子串。
// 则返回第一个这样的子串在S中的位置，否则返回0。
int i, n, m;
SString sub;
if(pos > 0) {
n = StrLength(S);
m = StrLength(T);
i = pos;
while(i <= n-m+1) {
SubString(sub, S, i, m);// 用Sub返回串S的第pos个字符起长度为len的子串
if (StrCompare(sub, T) != 0)
++i;
else
return i; // 返回子串在主串中的位置
}// while
}// if
return 0; // S中不存在与T相等的子串
}//Index 算法 4.1
int Index(SString S, SString T, int pos)
{ // 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。
// 其中，T非空，1≤pos≤StrLength(S)。
int i, j;
if(1<=pos && pos<=S[0])
{
i = pos;
j = 1;
while(i<=S[0] && j<=T[0])
if(S[i] == T[j]) // 继续比较后继字符
{
++i;
++j;
} else { // 指针后退重新开始匹配
i = i-j+2;
j = 1;
}
if(j>T[0])
return i-T[0];
else
return 0;
}
else
return 0;
}//Index 算法 4.5
// 初始条件：串S和T存在，1≤pos≤StrLength(S)+1。
// 操作结果：在串S的第pos个字符之前插入串T。
Status StrInsert(SString S, int pos, SString T) {
// 完全插入返回TRUE，部分插入返回FALSE
int i;
if(pos<1 || pos>S[0]+1)
return ERROR;
if(S[0]+T[0] <= MAXSTRLEN) {
// 完全插入
for(i = S[0]; i >= pos; i--)
S[i+T[0]] = S[i];
for(i = pos; i < pos+T[0]; i++)
S[i] = T[i-pos+1];
S[0]+= T[0];
return TRUE;
} else {
// 部分插入
for(i = MAXSTRLEN; i >= pos+T[0]; i--)
S[i] = S[i-T[0]];
for(i = pos; i < pos+T[0] && i <= MAXSTRLEN; i++)
S[i] = T[i-pos+1];
S[0] = MAXSTRLEN;
return FALSE;
}
}
// 初始条件：串S存在，1≤pos≤StrLength(S)-len+1。
// 操作结果：从串S中删除第pos个字符起长度为len的子串。
Status StrDelete(SString S, int pos, int len) {
int i;
if(pos<1 || pos>S[0]-len+1 || len<0)
return ERROR;
for(i = pos+len; i<= S[0]; i++)
S[i-len] = S[i];
S[0] -= len;
return OK;
}
// 初始条件：串S，T和V存在，T是非空串。
// 操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串。
Status Replace(SString S, SString T, SString V) { // 此函数与串的存储结构无关
int i = 1; // 从串S的第一个字符起查找串T
Status k;
if(StrEmpty(T)) return ERROR; // T是空串
do {
i = Index(S, T, i); // 结果i为从上一个i之后找到的子串T的位置
if(i) { // 串S中存在串T
StrDelete(S, i, StrLength(T)); // 删除该串T
k = StrInsert(S, i, V); // 在原串T的位置插入串V
if(!k) // 不能完全插入
return ERROR;
i+= StrLength(V); // 在插入的串V后面继续查找串T
}
} while(i);
return OK;
}
// 输出字符串T。
void StrPrint(SString T) {
for( int i = 1; i<= T[0]; i++)
printf("%c ", T[i]);
printf("\n");
}
int main() {
int i, j;
char cmp, c[MAXSTRLEN+1];
SString T, S, Sub, S1, S2;
// 初始化串S, Sub, S1, S2，并显示相关信息
// StrAssign(SString &T, char *chars)生成一个其值等于chars的串T。
printf("请输入串S: ");
// gets(c);
strcpy(c, "XYZNMP");
if(!StrAssign(S, c)) {
printf("串长超过MAXSTRLEN=%d，程序正常退出。\n", MAXSTRLEN);
exit(0);
}
StrPrint(S);
printf("串长为：%d 串空否(1:是0:否)：%d\n", StrLength(S), StrEmpty(S));
printf("\n");
printf("请输入串Sub: ");
// gets(c);
strcpy(c, "");
if(!StrAssign(Sub, c)) {
printf("串长超过MAXSTRLEN=%d，程序正常退出。\n", MAXSTRLEN);
exit(0);
}
StrPrint(Sub);
printf("串长为：%d 串空否(1:是0:否)：%d\n", StrLength(Sub), StrEmpty(Sub));
printf("\n");
printf("请输入串S1: ");
// gets(c);
strcpy(c, "ABCD");
if(!StrAssign(S1, c)) {
printf("串长超过MAXSTRLEN=%d，程序正常退出。\n", MAXSTRLEN);
exit(0);
}
StrPrint(S1);
printf("串长为：%d 串空否(1:是0:否)：%d\n", StrLength(S1), StrEmpty(S1));
printf("\n");
printf("请输入串S2: ");
// gets(c);
strcpy(c, "EFGH");
if(!StrAssign(S2, c)) {
printf("串长超过MAXSTRLEN=%d，程序正常退出。\n", MAXSTRLEN);
exit(0);
}
StrPrint(S2);
printf("串长为：%d 串空否(1:是0:否)：%d\n", StrLength(S2), StrEmpty(S2));
printf("\n");
// StrCopy(SString &T, SString S)由串S复制得串T
printf("由串S复制得串T：");
StrCopy(T, S);
StrPrint(T);
printf("\n");
// int StrCompare(SString S, SString T)若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0。
i = StrCompare(S, T);
if(i < 0)
cmp = '<';
else if(i == 0)
cmp = '=';
else
cmp = '>';
printf("串S %c 串T\n", cmp);
printf("\n");
// ClearString(SString S)将S清为空串。
ClearString(S);
printf("清为空串后, 串S为：");
StrPrint(S);
printf("串长为：%d 串空否(1:是0:否)：%d\n", StrLength(S), StrEmpty(S));
printf("\n");
// Concat(SString T, SString S1, SString S2)用T返回S1和S2联接而成的新串
printf("用T返回S1和S2联接而成的新串：");
if(!Concat(T, S1, S2))
printf("串T有截断！\n");
StrPrint(T);
printf("\n");
printf("由串T复制得串S：");
StrCopy(S, T);
StrPrint(S);
printf("\n");
// SubString(SString Sub, SString S, int pos, int len)用Sub返回串S的第pos个字符起长度为len的子串。
printf("用Sub返回串S的第pos个字符起长度为len的子串, 请输入pos、len: ");
//scanf("%d %d", &i, &j);
i = 5, j = 3;
if(SubString(Sub, S, i, j)) {
printf("子串Sub为：");
StrPrint(Sub);
printf("\n");
}
// int Index(SString S, SString T, int pos)返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。
i = Index(S, T, 1);
printf("返回子串T在主串S中第pos个字符之后的位置：%d\n", i);
printf("\n");
// StrDelete(SString S, int pos, int len)从串S中删除第pos个字符起长度为len的子串。
printf("从串S中删除第pos个字符起长度为len的子串，请输入pos、len: ");
//scanf("%d %d", &i, &j);
i = 3, j = 4;
if(StrDelete(S, i, j)) {
printf("删除后的串S为");
StrPrint(S);
printf("\n");
}
// StrInsert(SString S, int pos, SString T)在串S的第pos个字符之前插入串T。
i = StrLength(S2);
printf("在串S的第%d个字符之前插入串T, 串S为\n", i);
StrInsert(S, i, T);
StrPrint(S);
printf("\n");
// Replace(SString S, SString T, SString V)用V替换主串S中出现的所有与T相等的不重叠的子串
if(Replace(S, T, S1)) {
printf("用S1替换主串S中出现的所有与T相等的不重叠的子串, 串S为\n");
StrPrint(S);
printf("\n");
}
DestroyString(T); // 销毁操作同清空
DestroyString(S);
DestroyString(Sub);
DestroyString(S1);
DestroyString(S2);
return 0;
}
案例
参考文献
[1] 严蔚敏，吴伟民. 数据结构(C语言版)[M]. 清华大学出版社.
[2] 悟浮生. 《数据结构》（C语言版）——串的定长顺序存储表示[EB/OL]. https://blog.csdn.net/prlhnxx/article/details/79827685