一.简述
【暂无】
二.头文件
//4_2_part1.h
/**
author:zhaoyu
*/
//2016-6-10
//----串的定长顺序存储表示----
#include "head.h"
#define MAXSTRLEN 255//用户可以在255以内定义最大串长
//这语法还不是很熟悉
typedef unsigned char SString[MAXSTRLEN+];//0 号单元存放串的长度
int StrLength(SString T)
{
for (int i = ; i <= MAXSTRLEN; ++i)
{
if ('\0' == T[i])
{
return i-;
}
}
return MAXSTRLEN;
} /**
algorithm 4.2
*/
Status Concat(SString &T, SString S1, SString S2)
{
//用 T 返回由 S1 和 S2 连接而成的新串。
//若未截断，则返回 TRUE，否则返回 FALSE
Status uncut;
if (S1[] + S2[] < MAXSTRLEN)
{//未截断
int i = ;
for (i = ; i <= S1[]; ++i)
{
T[i] = S1[i];
}
for (i = ; i <= S2[]; ++i)
{
T[S1[]+i] = S2[i];
}
T[] = S1[] + S2[];
uncut = TRUE;
}
else if (S1[] < MAXSTRLEN)
{
int i = ;
for (i = ; i <= S1[]; i++)
{
T[i] = S1[i];
}
for (i = S1[]+; i <= MAXSTRLEN; i++)
{
T[i] = S2[i-S1[]];
}
T[] = MAXSTRLEN;
uncut = FALSE;
}
else
{
for (int i = ; i <= MAXSTRLEN; i++)
{
T[i] = S1[i];
}
T[] = S1[] = MAXSTRLEN;
uncut = FALSE;
}
return uncut;
}
/**
algorithm 4.3
*/
Status SubString(SString &Sub, SString S, int pos, int len)
{
//用 Sub 返回串 S 的第 pos 个字符起长度为 len 的字串
//其中， 1<= pos <<= SreLength(S) 且 0 <= len <= StrLength(S)-pos+1
if (pos < || pos > S[] || len < || len > S[]-pos+)
{
return ERROR;
}
for (int i = ; i <= len; i++)
{
Sub[i] = S[i+pos-];
}
Sub[] = len;
return OK;
}
void PrintSString(SString T)
{
//if(T[])
for (int i = ; i <= T[]; ++i)
{
printf("%c", *(T+i));
}
printf("\n");
} 4_2_part1.h
4_2_part1.h
//4_2_part2.h
/**
author:zhaoyu
*/
//2016-6-12
#include "head.h"
#include <cstdlib>
#include <cstring>
//----串的对分配存储表示----
typedef struct {
char *ch;//
int length;
}HString; Status StrInsert(HString &S, int pos, HString T)
{//1<= pos <= StrLength(S)+1
//在串的第 pos 个字符之前插入串 T
if ( < pos || pos > S.length + )
{
printf("Illegal pos\n");
return ERROR;
}
if (T.length){//T 非空，则重新分配空间，插入 T
if (!(S.ch = (char *)realloc(S.ch, (S.length +
T.length)*sizeof(char))));
{
exit(OVERFLOW);
}
for (int i = S.length-; i >= pos-; i--)
{//为插入 T 为腾出位置
S.ch[i+T.length] = S.ch[i];
}
for (int i = pos-; i <= pos+T.length-; i++)
{//插入 T
S.ch[i] = T.ch[i];
}
S.length += T.length;
}
return OK;
}
//page 76-77
//----基本操作的算法描述----
Status StrAssign(HString &T, char *chars)
{//生成一个其值等于串常量 chars的串 T
if (T.ch)
{
T.ch = NULL;
}
int L;
char *c;;
for (L = , c = chars; *c!='\0'; ++L, ++c);//求 chars 的长度 L
if(!L)
{
T.ch = NULL;
T.length = ;
}
else
{
if (!(T.ch = (char *)malloc(L*sizeof(char))))
{
exit(OVERFLOW);
}
for (int i = ; i < L; ++i)
{
T.ch[i] = chars[i];
}
T.length = L;
}
return OK;
}
int StrLength(HString S)
{//返回 S 的元素个数， 称为串的长度
return S.length;
}
int StrCompare(HString S, HString T)
{//若 S >|=|< T，则返回 >|=|< 0
for (int i = ; i < S.length && i < T.length; i++)
{
if (T.ch[i] != S.ch[i])
{
return S.ch[i] - T.ch[i];
}
}
return S.length - T.length;
}
Status ClearString(HString &S)
{
//将 S 清空为空串
if (S.ch)
{
free(S.ch);
S.ch = NULL;
}
S.length = ;
return OK;
}
Status Concat(HString &T, HString S1, HString S2)
{
if (T.ch)
{//释放旧空间
free(T.ch);
}
if (!(T.ch = (char *)malloc((S1.length+S2.length)*sizeof(char))))
{
exit(OVERFLOW);
}
for (int i = ; i < S1.length; ++i)
{
T.ch[i] = S1.ch[i];
}
for (int i = ; i < S2.length; ++i)
{
T.ch[i+S1.length] = S2.ch[i];
}
T.length = S1.length + S2.length;
return OK;
}
Status SubString(HString &Sub, HString S, int pos, int len)
{
//用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串
//其中，其中， 1<= pos <<= SreLength(S) 且 0 <= len <= StrLength(S)-pos+1
if (pos < || pos > S.length || len < || len > S.length-pos+)
{
return ERROR;
}
if (Sub.ch)
{
free(Sub.ch);
}
if (!len)
{//空子串
Sub.ch = NULL;
Sub.length = ;
}
else
{
Sub.ch = (char *)malloc(len*sizeof(char));
for (int i = ; i < len; ++i)
{
Sub.ch[i] = S.ch[pos+i-];
}
Sub.length = len;
}
return OK;
}
void PrintHString(HString S)
{
for (int i = ; i < S.length; ++i)
{
printf("%c", S.ch[i]);
}
printf("\n");
}
4_2_part2.h
三.CPP文件
#include "4_2_part1.h"
int main(int argc, char const *argv[])
{
SString S1;
SString S2;
SString T;
scanf("%s", S1+);
*S1 = StrLength(S1);
scanf("%s", S2+);
*S2 = StrLength(S2);
Concat(T, S1, S2);
PrintSString(T);
int pos = , len = ;
SubString(T, S1, pos, len);
PrintSString(T);
return ;
}
4_2_part1.cpp
#include "4_2_part2.h"
int main(int argc, char const *argv[])
{
char S[];
HString T = {NULL, };
HString S1 = {NULL, };
HString S2 = {NULL, };
scanf("%s", S);
StrAssign(S1, S);
printf("S1:\t");
PrintHString(S1);
printf("StrLength\t%d\n", StrLength(S1));
scanf("%s", S);
StrAssign(S2, S);
printf("S2\t");
PrintHString(S2);
printf("StrLength\t%d\n", StrLength(S1));
printf("Compare S1 vs S2\t%d\n", StrCompare(S1, S2));
Concat(T, S1, S2);
printf("T = S1 + S2\t");
PrintHString(T);
SubString(S1, T, , );
printf("Sub :T[2]-T[4]\t");
PrintHString(S1);
return ;
}
4_2_part2.cpp
四.测试
连接
求子串
比较串