主题:求助 数据结构 串的堆分配与表示
哪位帮一下忙,其他的函数测试了都对,Replace_str函数的运行结果就是不对啊,帮忙找一下问题,谢谢,我是在win—tc下编译的
[code=C/C++][/code]
#include "stdio.h"
#include "conio.h"
#include "malloc.h"
#define OK 1
#define ERROR -1
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
#define MAXSIZE 100
typedef int Status;
struct Str
{
char *s; /*若是非空串,则按串长分配存储空间,若是空串,则s = NULL*/
int len; /*串的长度*/
};
Status StrAssign(struct Str *s1,char *s2) /*s2是一个字符串常量*/
{
int i = 0;
if(!s2) return ERROR;
if(s1->s) free(s1->s); /*释放s1原有空间*/
while(s2[i] != '\0')
i++;
if(!i) /*若为空串*/
{
s1->s = NULL;
s1->len = 0;
}
else
{
s1->s = (char *)malloc(i * sizeof(char)); /*为str动态分配内存*/
if(!(s1->s)) return OVERFLOW;
s1->len = i;
}
i = 0;
while(s2[i] != '\0')
{
(s1->s)[i] = s2[i];
i++;
}
(s1->s)[i] = '\0'; /*关于串的操作切记不能忘了这句*/
return OK;
}
Status Copy_str(struct Str *s1,struct Str s2) /*将s2串复制到s1串中*/
{
int i = 0;
if(!s1 || s2.len == 0) return ERROR;
while( (s2.s)[i] != '\0' )
{
(s1->s)[i] = (s2.s)[i];
i++;
}
s1->s[i] = '\0';
s1->len = s2.len;
return OK;
}
Status Is_Empty(struct Str s1) /*判断s串是否为空串*/
{
if(s1.len == 0)
return TRUE;
else
return FALSE;
}
Status Compare_str(struct Str s1, struct Str s2) /*比较s1串和s2串,类似strcmp函数*/
{
int i;
for(i = 0; i < s1.len && i < s2.len; i++)
if( (s1.s)[i] != (s2.s)[i] )
return (s1.s)[i] - (s2.s)[i];
return s1.len - s2.len; /*若s1串和s2串相等或者其中一个串包含另外一个串*/
}
Status Len_str(struct Str s1) /*求s串的长度*/
{
return s1.len;
}
Status Clear_str(struct Str *s1) /*清空s串*/
{
if(!s1) return ERROR;
if(s1->s)
{
free(s1->s); /*释放(s1->s)为首地址的空间*/
s1->s = NULL;
}
s1->len = 0;
return OK;
}
Status Conect_str(struct Str s1,struct Str s2,struct Str *s3) /*用s3返回s2串连接在s1串后形成的串*/
{
int i;
s3->s = (char *)malloc( (s1.len + s2.len) * sizeof(char) ); /*为s3动态分配内存空间*/
if( !(s3->s) ) return OVERFLOW;
for(i = 0; i < s1.len; i++)
(s3->s)[i] = (s1.s)[i];
for(i = s1.len; i < s1.len + s2.len; i++) /*注意此处i的上限是(s1->len) + (s2->len) - 1*/
(s3->s)[i] = (s2.s)[i - s1.len];
(s3->s)[i] = '\0';
return OK;
}
Status Sub_str(struct Str *s1, struct Str s2,int pos,int length) /*用s1返回串s2的自第pos个字符起长度为length的子串*/
{
int i;
if(s2.len <= 0 || pos < 1 || pos >= s2.len || length < 0 || length > (s2.len) - pos + 1)
return ERROR;
if(!length)
{
s1->s = NULL; /*空串*/
s1->len = 0;
}
s1->s = (char *)malloc(length * sizeof(char)); /*为s1串动态分配空间*/
for(i = pos - 1; i < pos - 1 + length; i++)
(s1->s)[i-(pos-1)] = (s2.s)[i];
(s1->s)[i-(pos-1)] = '\0';
s1->len = length;
return OK;
}
int Index_str(struct Str s1, struct Str s2, int pos) /*求子串位置的定位函数*/
/*s2为非空串,若主串s1中自第pos个字符往后存在与s2相同的子串,则返回第一个这样的子串在主串s1中的位置,否则,返回0*/
{
int i;
struct Str *sub;
sub = (struct Str *)malloc(sizeof(struct Str));
if(!sub) return OVERFLOW;
if(s1.len == 0 || s2.len == 0 || pos < 0 || pos > s1.len - 1)
return ERROR;
i = pos;
while( i <= s1.len - s2.len + 1 ) /*注意此处i的上限*/
{
Sub_str(sub,s1,i,s2.len); /*在s1中寻找是否出现s2*/
if( Compare_str(s1,*sub) != 0 )
i++;
else
return i;
}
return 0; /*找不到这样的子串*/
}
Status Insert_str(struct Str *s1,int pos,struct Str s2) /*在串s1的第pos个字符之前插入串s2*/
{
int i;
if(!s1 || pos < 1 || pos > s1->len) return ERROR;
if(s2.len)
{ /*s2非空,重新申请分配空间,插入s2*/
s1->s = (char *)realloc( s1->s,(s1->len + s2.len) * sizeof(char) ); /*在原来空间的基础上添加一些*/
if(!(s1->s)) return OVERFLOW;
for(i = s1->len - 1; i >= pos - 1; i--) /*为串s2腾出空间而后移部分元素*/
(s1->s)[i + s2.len] = (s1->s)[i];
for(i = pos-1; i < s2.len + pos - 1; i++)
(s1->s)[i] = s2.s[i-(pos -1)];
s1->len += s2.len;
(s1->s)[s1->len] = '\0'; /*给s1串末尾加上字符串结束符*/
}
return OK;
}
Status Del_str(struct Str *s1,int pos,int length) /*从串s1中删除自第pos个字符往后长度为len的子串(包括第pos个字符)*/
{
int i;
if(!s1 || pos <= 0 || pos > s1->len || length < 0 || length > s1->len)
return ERROR;
s1->s = (char *)realloc( s1->s,(s1->len) * sizeof(char)); /*重新申请空间,删除那几个元素*/
if(!(s1->s)) return OVERFLOW;
for(i = pos - 1; i < s1->len - length; i++)
(s1->s)[i] = (s1->s)[i + length];
s1->len -= length;
(s1->s)[s1->len] = '\0';
return OK;
}
Status Replace_str(struct Str *s1,struct Str s2,struct Str s3)
/*用s3串替换主串s1中出现的所有不重叠的与s2相等的子串*/
{
int i = 1;
if(!(s1->len) || !(s2.len)) return ERROR;
do
{
i = Index_str(*s1,s2,i);
if(i)
{
Del_str(s1,i,s2.len);
Insert_str(s1,i,s3);
i += s3.len; /*跳过刚刚替换的区域,避免替换重叠部分*/
}
}while(i);
return OK;
}
/*for(i = 1; i <= s1->len - s2.len + 1; i++) 注意上限
{
k = Index_str(*s1,s2,i);
if(k)
{
for(j = k - 1; j < k - 1 + s2.len; j++)
(s1->s)[j] = s2.s[j-(k - 1)];
i = k + s2.len - 1; 跳过刚才替换上的一段子串,防止重叠替代
}
}*/
Status Destroy_str(struct Str s1) /*摧毁串s1*/
{
free(s1.s);
return OK;
}
main()
{
char s11[MAXSIZE];
char s22[MAXSIZE];
char s33[MAXSIZE];
struct Str *s1;
struct Str *s2;
struct Str *s3;
s1 = (struct Str *)malloc(sizeof(struct Str));
s2 = (struct Str *)malloc(sizeof(struct Str));
s3 = (struct Str *)malloc(sizeof(struct Str));
printf("Input string\n");
scanf("%s",s11);
StrAssign(s1,s11);
printf("Input string\n");
scanf("%s",s2);
StrAssign(s2,s22);
printf("Input string\n");
scanf("%s",s33);
StrAssign(s3,s33);
Replace_str(s1,*s2,*s3);
printf("%s",s1->s);
getch();
}
[code=C/C++][/code]
#include "stdio.h"
#include "conio.h"
#include "malloc.h"
#define OK 1
#define ERROR -1
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
#define MAXSIZE 100
typedef int Status;
struct Str
{
char *s; /*若是非空串,则按串长分配存储空间,若是空串,则s = NULL*/
int len; /*串的长度*/
};
Status StrAssign(struct Str *s1,char *s2) /*s2是一个字符串常量*/
{
int i = 0;
if(!s2) return ERROR;
if(s1->s) free(s1->s); /*释放s1原有空间*/
while(s2[i] != '\0')
i++;
if(!i) /*若为空串*/
{
s1->s = NULL;
s1->len = 0;
}
else
{
s1->s = (char *)malloc(i * sizeof(char)); /*为str动态分配内存*/
if(!(s1->s)) return OVERFLOW;
s1->len = i;
}
i = 0;
while(s2[i] != '\0')
{
(s1->s)[i] = s2[i];
i++;
}
(s1->s)[i] = '\0'; /*关于串的操作切记不能忘了这句*/
return OK;
}
Status Copy_str(struct Str *s1,struct Str s2) /*将s2串复制到s1串中*/
{
int i = 0;
if(!s1 || s2.len == 0) return ERROR;
while( (s2.s)[i] != '\0' )
{
(s1->s)[i] = (s2.s)[i];
i++;
}
s1->s[i] = '\0';
s1->len = s2.len;
return OK;
}
Status Is_Empty(struct Str s1) /*判断s串是否为空串*/
{
if(s1.len == 0)
return TRUE;
else
return FALSE;
}
Status Compare_str(struct Str s1, struct Str s2) /*比较s1串和s2串,类似strcmp函数*/
{
int i;
for(i = 0; i < s1.len && i < s2.len; i++)
if( (s1.s)[i] != (s2.s)[i] )
return (s1.s)[i] - (s2.s)[i];
return s1.len - s2.len; /*若s1串和s2串相等或者其中一个串包含另外一个串*/
}
Status Len_str(struct Str s1) /*求s串的长度*/
{
return s1.len;
}
Status Clear_str(struct Str *s1) /*清空s串*/
{
if(!s1) return ERROR;
if(s1->s)
{
free(s1->s); /*释放(s1->s)为首地址的空间*/
s1->s = NULL;
}
s1->len = 0;
return OK;
}
Status Conect_str(struct Str s1,struct Str s2,struct Str *s3) /*用s3返回s2串连接在s1串后形成的串*/
{
int i;
s3->s = (char *)malloc( (s1.len + s2.len) * sizeof(char) ); /*为s3动态分配内存空间*/
if( !(s3->s) ) return OVERFLOW;
for(i = 0; i < s1.len; i++)
(s3->s)[i] = (s1.s)[i];
for(i = s1.len; i < s1.len + s2.len; i++) /*注意此处i的上限是(s1->len) + (s2->len) - 1*/
(s3->s)[i] = (s2.s)[i - s1.len];
(s3->s)[i] = '\0';
return OK;
}
Status Sub_str(struct Str *s1, struct Str s2,int pos,int length) /*用s1返回串s2的自第pos个字符起长度为length的子串*/
{
int i;
if(s2.len <= 0 || pos < 1 || pos >= s2.len || length < 0 || length > (s2.len) - pos + 1)
return ERROR;
if(!length)
{
s1->s = NULL; /*空串*/
s1->len = 0;
}
s1->s = (char *)malloc(length * sizeof(char)); /*为s1串动态分配空间*/
for(i = pos - 1; i < pos - 1 + length; i++)
(s1->s)[i-(pos-1)] = (s2.s)[i];
(s1->s)[i-(pos-1)] = '\0';
s1->len = length;
return OK;
}
int Index_str(struct Str s1, struct Str s2, int pos) /*求子串位置的定位函数*/
/*s2为非空串,若主串s1中自第pos个字符往后存在与s2相同的子串,则返回第一个这样的子串在主串s1中的位置,否则,返回0*/
{
int i;
struct Str *sub;
sub = (struct Str *)malloc(sizeof(struct Str));
if(!sub) return OVERFLOW;
if(s1.len == 0 || s2.len == 0 || pos < 0 || pos > s1.len - 1)
return ERROR;
i = pos;
while( i <= s1.len - s2.len + 1 ) /*注意此处i的上限*/
{
Sub_str(sub,s1,i,s2.len); /*在s1中寻找是否出现s2*/
if( Compare_str(s1,*sub) != 0 )
i++;
else
return i;
}
return 0; /*找不到这样的子串*/
}
Status Insert_str(struct Str *s1,int pos,struct Str s2) /*在串s1的第pos个字符之前插入串s2*/
{
int i;
if(!s1 || pos < 1 || pos > s1->len) return ERROR;
if(s2.len)
{ /*s2非空,重新申请分配空间,插入s2*/
s1->s = (char *)realloc( s1->s,(s1->len + s2.len) * sizeof(char) ); /*在原来空间的基础上添加一些*/
if(!(s1->s)) return OVERFLOW;
for(i = s1->len - 1; i >= pos - 1; i--) /*为串s2腾出空间而后移部分元素*/
(s1->s)[i + s2.len] = (s1->s)[i];
for(i = pos-1; i < s2.len + pos - 1; i++)
(s1->s)[i] = s2.s[i-(pos -1)];
s1->len += s2.len;
(s1->s)[s1->len] = '\0'; /*给s1串末尾加上字符串结束符*/
}
return OK;
}
Status Del_str(struct Str *s1,int pos,int length) /*从串s1中删除自第pos个字符往后长度为len的子串(包括第pos个字符)*/
{
int i;
if(!s1 || pos <= 0 || pos > s1->len || length < 0 || length > s1->len)
return ERROR;
s1->s = (char *)realloc( s1->s,(s1->len) * sizeof(char)); /*重新申请空间,删除那几个元素*/
if(!(s1->s)) return OVERFLOW;
for(i = pos - 1; i < s1->len - length; i++)
(s1->s)[i] = (s1->s)[i + length];
s1->len -= length;
(s1->s)[s1->len] = '\0';
return OK;
}
Status Replace_str(struct Str *s1,struct Str s2,struct Str s3)
/*用s3串替换主串s1中出现的所有不重叠的与s2相等的子串*/
{
int i = 1;
if(!(s1->len) || !(s2.len)) return ERROR;
do
{
i = Index_str(*s1,s2,i);
if(i)
{
Del_str(s1,i,s2.len);
Insert_str(s1,i,s3);
i += s3.len; /*跳过刚刚替换的区域,避免替换重叠部分*/
}
}while(i);
return OK;
}
/*for(i = 1; i <= s1->len - s2.len + 1; i++) 注意上限
{
k = Index_str(*s1,s2,i);
if(k)
{
for(j = k - 1; j < k - 1 + s2.len; j++)
(s1->s)[j] = s2.s[j-(k - 1)];
i = k + s2.len - 1; 跳过刚才替换上的一段子串,防止重叠替代
}
}*/
Status Destroy_str(struct Str s1) /*摧毁串s1*/
{
free(s1.s);
return OK;
}
main()
{
char s11[MAXSIZE];
char s22[MAXSIZE];
char s33[MAXSIZE];
struct Str *s1;
struct Str *s2;
struct Str *s3;
s1 = (struct Str *)malloc(sizeof(struct Str));
s2 = (struct Str *)malloc(sizeof(struct Str));
s3 = (struct Str *)malloc(sizeof(struct Str));
printf("Input string\n");
scanf("%s",s11);
StrAssign(s1,s11);
printf("Input string\n");
scanf("%s",s2);
StrAssign(s2,s22);
printf("Input string\n");
scanf("%s",s33);
StrAssign(s3,s33);
Replace_str(s1,*s2,*s3);
printf("%s",s1->s);
getch();
}