|
|
#2
gailv72011-11-16 17:54
难道就没有人会了么?程序我改了,代码如下://-----串的堆分配存储表示------#include<stdio.h> #include<stdlib.h> #include <malloc.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define INFEASIBLE -1 typedef struct { char *ch; //若是非空串,则桉串长分配存储区,否则ch为NULL int length; //串长度 }HString; //--------基本操作-------- //-----初始化------- void InitString(HString *S) { S->ch=NULL; S->length=0; } //----生成一个其值等于串常量chars的串T-------- void StrAssign(HString *T,char *chars) { if(T->ch) free(T->ch); int len=0; while(chars[len]) { ++len; } if(0==len) { T->ch=NULL; T->length=0; } else { T->ch=(char *)malloc(sizeof(char)*len); if(NULL==T->ch) { printf("Out of space!\n"); exit(OVERFLOW); } else { for(int i=0;i!=len;++i) { T->ch[i]=chars[i]; } T->length=len; } } } //---返回S的元素个数,即为串的长度------ int StrLength(HString S) { return S.length; } //----两个串的比较------ int StrCompare(HString S,HString T) { for(int i=0;(i!=S.length)&&(i!=T.length);++i) { if(S.ch[i]!=T.ch[i]) return (S.ch[i]-T.ch[i]); } return (S.length-T.length); } //-----将S清为空串------ void ClearString(HString *S) { if(S->ch) { free(S->ch); S->ch=NULL; S->length=0; } } //-------将两个串联接成一个新串--------- void Concat(HString *T,HString S1,HString S2) { ClearString(T); //释放旧空间 T->ch=(char *)malloc((S1.length+S2.length)*sizeof(char)); if(NULL==T->ch) { printf("Out of space!!!\n"); exit(OVERFLOW); } else { for(int i=0;i!=S1.length;++i) { T->ch[i]=S1.ch[i]; } T->length=S1.length+S2.length; for(int j=S1.length,k=0;j!=T->length,k!=S2.length;++j,++k) { T->ch[j]=S2.ch[k]; } } } //------用sub返回串S的第pos个字符长度为len的子串------- void SubString(HString *Sub,HString S,int pos,int len) { if(pos<1||pos>S.length||len<0||len>S.length-pos+1) { printf("子串的起始位置或串长错误!\n"); } ClearString(Sub); if(0==len) { Sub->ch=NULL; Sub->length=0; } else { Sub->ch=(char *)malloc(len*sizeof(char)); if(NULL==Sub->ch) { printf("Out of space!!\n"); exit(0); } int i=0; int k=0; for(i=0,k=pos-1;i!=len,k!=pos+len-1;++i,++k) { Sub->ch[i]=S.ch[k]; Sub->length=len; } } } // 在串st1的第pos个字符之前插入串st2 int StrInsert(HString *st1,int pos,HString st2) { int i; if(pos<1||pos>(*st1).length+1) // pos不合法 return ERROR; if(st2.length) // st2非空,则重新分配空间,插入st2 { (*st1).ch = (char*)realloc((*st1).ch, ((*st1).length+st2.length)*sizeof(char)); if(!(*st1).ch) exit(OVERFLOW); for(i=(*st1).length-1;i>=pos-1;--i) // 为插入st2而腾出位置 (*st1).ch[i+st2.length]=(*st1).ch[i]; for(i=0;i<st2.length;i++) (*st1).ch[pos-1+i]=st2.ch[i]; // 插入st2 (*st1).length+=st2.length; } return OK; } // 从串st1中删除第pos个字符起长度为len的子串 int StrDelete(HString *st1,int pos,int len) { int i; if((*st1).length<pos+len-1) exit(OVERFLOW); for(i=pos-1;i<=(*st1).length-len;i++) (*st1).ch[i]=(*st1).ch[i+len]; (*st1).length-=len; (*st1).ch=(char*)realloc((*st1).ch,(*st1).length*sizeof(char)); return OK; } //-----输出串中的字符----- void PrintString(HString S) { if(S.length) { for(int i=0;i!=S.length;++i) printf("%-4c",S.ch[i]); printf("\n"); } else { printf("empty!\n"); } } int main() { HString st1; HString st2; HString sub; HString T; char ch1[20]; printf("输入st1:"); gets(ch1); InitString(&st1); StrAssign(&st1,ch1); PrintString(st1); printf("串长:%d\n",StrLength(st1)); printf("输入st2:"); gets(ch1); InitString(&st2); StrAssign(&st2,ch1); int state=StrCompare(st1,st2); if(0==state) { printf("st1和st2比较:st1=st2\n"); } else if(state>0) { printf("st1和st2比较:st1>st2\n"); } else { printf("st1和st2比较:st1<st2\n"); } InitString(&T); printf("st1连接st2:"); Concat(&T,st1,st2); PrintString(T); InitString(&sub); printf("st1中起始位置为7,长度为1的子串:"); SubString(&sub,st1,7,1); PrintString(sub); InitString(&st1); printf("插入st2后的串st1="); StrInsert(&st1,3,st2); PrintString(st1); InitString(&st1); printf("删除起始位置为4,长度为3的子串后st1="); StrDelete(&st1,4,3); PrintString(st1); ClearString(&st1); ClearString(&st2); ClearString(&sub); ClearString(&T); return ERROR; } 大侠救急啊!!! |
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
typedef struct
{
char *ch; // 若是非空串,则按串长分配存储区,否则ch为NULL
int length; // 串长度
}HString;
// 初始化(产生空串)字符串T
void InitString(HString *T)
{
(*T).length=0;
(*T).ch=NULL;
}
// 生成一个其值等于串常量chars的串T
int StrAssign(HString *T, char *chars)
{
int i,j;
if((*T).ch)
free((*T).ch); // 释放T原有空间
i = strlen(chars); // 求chars的长度i
if(!i)
{
// chars的长度为0
(*T).ch = NULL;
(*T).length = 0;
}
else
{
// chars的长度不为0
(*T).ch = (char*)malloc(i*sizeof(char)); // 分配串空间
if(!(*T).ch) // 分配串空间失败
exit(0);
for(j = 0; j < i; j++) // 拷贝串
(*T).ch[j] = chars[j];
(*T).length = i;
}
return 1;
}
// 由串S复制得串T
int StrCopy(HString *T,HString S)
{
int i;
if((*T).ch)
free((*T).ch); // 释放T原有空间
(*T).ch=(char*)malloc(S.length*sizeof(char)); // 分配串空间
if(!(*T).ch) // 分配串空间失败
exit(0);
for(i=0;i<S.length;i++) // 拷贝串
(*T).ch[i]=S.ch[i];
(*T).length=S.length;
return 1;
}
// 若S为空串,则返回1,否则返回0
int StrEmpty(HString S)
{
if(S.length == 0 && S.ch == NULL)
return 1;
else
return 0;
}
// 若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0
int StrCompare(HString S,HString T)
{
int i;
for(i=0;i<S.length && i<T.length;++i)
if(S.ch[i] != T.ch[i])
return S.ch[i]-T.ch[i];
return S.length-T.length;
}
// 返回S的元素个数,称为串的长度
int StrLength(HString S)
{
return S.length;
}
// 将S清为空串
int ClearString(HString *S)
{
if((*S).ch)
{
free((*S).ch);
(*S).ch=NULL;
}
(*S).length=0;
return 1;
}
// 用T返回由S1和S2联接而成的新串
int Concat(HString *T,HString S1,HString S2)
{
int i;
if((*T).ch)
free((*T).ch); // 释放旧空间
(*T).length=S1.length+S2.length;
(*T).ch=(char *)malloc((*T).length*sizeof(char)); //分配新串的长度
if(!(*T).ch)
exit(0);
for(i=0;i<S1.length;i++) //将S1接到新串T的后面
(*T).ch[i]=S1.ch[i];
for(i=0;i<S2.length;i++) //将S2接到新串T的后面
(*T).ch[S1.length+i]=S2.ch[i];
return 1;
}
// 用Sub返回串S的第pos个字符起长度为len的子串。
int SubString(HString *Sub, HString S,int pos,int len)
{
int i;
if(pos<1||pos>S.length||len<0||len>S.length-pos+1)
return 0;
if((*Sub).ch)
free((*Sub).ch); // 释放旧空间
if(!len) // 空子串
{
(*Sub).ch=NULL;
(*Sub).length=0;
}
else
{ // 完整子串
(*Sub).ch=(char*)malloc(len*sizeof(char));
if(!(*Sub).ch)
exit(0);
for(i=0;i<=len-1;i++)
(*Sub).ch[i]=S.ch[pos-1+i];
(*Sub).length=len;
}
return 1;
}
// 算法4.1
// T为非空串。若主串S中第pos个字符之后存在与T相等的子串,
// 则返回第一个这样的子串在S中的位置,否则返回0
int Index(HString S,HString T,int pos)
{
int n,m,i;
HString sub;
InitString(&sub);
if(pos>0)
{
n=StrLength(S);
m=StrLength(T);
i=pos;
while(i<=n-m+1) //从第i个位置开始求与T等长的子串,循环直到找到
{
SubString(&sub,S,i,m); //从第i个位置开始求得子串
if(StrCompare(sub,T)!=0)//将求得的子串与T对比,若不等则i++
++i;
else
return i;
}
}
return 0;
}
// 算法4.4
// 在串S的第pos个字符之前插入串Ts
int StrInsert(HString *S,int pos,HString T)
{
int i;
if(pos<1||pos>(*S).length+1) // pos不合法
return 0;
if(T.length) // T非空,则重新分配空间,插入T
{
(*S).ch = (char*)realloc((*S).ch,
((*S).length+T.length)*sizeof(char));
if(!(*S).ch)
exit(0);
for(i=(*S).length-1;i>=pos-1;--i) // 为插入T而腾出位置
(*S).ch[i+T.length]=(*S).ch[i];
for(i=0;i<T.length;i++)
(*S).ch[pos-1+i]=T.ch[i]; // 插入T
(*S).length+=T.length;
}
return 1;
}
// 从串S中删除第pos个字符起长度为len的子串
int StrDelete(HString *S,int pos,int len)
{
int i;
if((*S).length<pos+len-1)
exit(0);
for(i=pos-1;i<=(*S).length-len;i++)
(*S).ch[i]=(*S).ch[i+len];
(*S).length-=len;
(*S).ch=(char*)realloc((*S).ch,(*S).length*sizeof(char));
return 1;
}
// 用V替换主串S中出现的所有与T相等的不重叠的子串
int Replace(HString *S,HString T,HString V)
{
int i=1; // 从串S的第一个字符起查找串T
if(StrEmpty(T)) // T是空串
return 0;
do
{
i=Index(*S,T,i); // 结果i为从上一个i之后找到的子串T的位置
if(i) // 串S中存在串T
{
StrDelete(S,i,StrLength(T)); // 删除该串T
StrInsert(S,i,V); // 在原串T的位置插入串V
i+=StrLength(V); // 在插入的串V后面继续查找串T
}
}while(i);
return 1;
}
void DestroyString()
{
// 堆分配类型的字符串无法销毁
}
// 输出T字符串
void StrPrint(HString T)
{
int i;
for(i=0;i<T.length;i++)
printf("%c",T.ch[i]);
printf("\n");
}
int main()
{
int i;
char c,*p="God bye!",*q="God luck!";
HString t,s,r;
// HString类型必需初始化
InitString(&t);
InitString(&s);
InitString(&r);
StrAssign(&t,p);
printf("串t为: ");
StrPrint(t);
printf("串长为%d 串空否?%d(1:空 0:否)\n",StrLength(t),StrEmpty(t));
StrAssign(&s,q);
printf("串s为: ");
StrPrint(s);
i=StrCompare(s,t);
if(i<0)
c='<';
else if(i==0)
c='=';
else
c='>';
printf("串s%c串t\n",c);
Concat(&r,t,s);
printf("串t联接串s产生的串r为: ");
StrPrint(r);
StrAssign(&s,"oo");
printf("串s为: ");
StrPrint(s);
StrAssign(&t,"o");
printf("串t为: ");
StrPrint(t);
Replace(&r,t,s);
printf("把串r中和串t相同的子串用串s代替后,串r为:\n");
StrPrint(r);
ClearString(&s);
printf("串s清空后,串长为%d 空否?%d(1:空 0:否)\n",
StrLength(s),StrEmpty(s));
SubString(&s,r,6,4);
printf("串s为从串r的第6个字符起的4个字符,长度为%d 串s为: ",
s.length);
StrPrint(s);
StrCopy(&t,r);
printf("复制串t为串r,串t为: ");
StrPrint(t);
StrInsert(&t,6,s);
printf("在串t的第6个字符前插入串s后,串t为: ");
StrPrint(t);
StrDelete(&t,1,5);
printf("从串t的第1个字符起删除5个字符后,串t为: ");
StrPrint(t);
printf("%d是从串t的第1个字符起,和串s相同的第1个子串的位置\n",
Index(t,s,1));
printf("%d是从串t的第2个字符起,和串s相同的第1个子串的位置\n",
Index(t,s,2));
system("pause");
return 0;
}
难道就没有人会了么?程序我改了,代码如下://-----串的堆分配存储表示------