数据结构 串的基本操作

初学数据结构,实现了串的基本操作,记录如下

StrAssign(HString &T,char *chars)
//生成一个其值等于串常量的chars的串T
StrInsert(HString &S,int pos,HString T)
//在串S的第pos个字符之前插入串T
Display(HString S)
//输出,显示串
StrCompare(HString S,HString T)
//按照字典序比较HString的大小,越排后越大
//若S>T,则返回值>0;若S=T,则返回值=0;若S

程序源代码如下:

#include<iostream>

using namespace std;

typedef struct 
{
	char *ch;
	int length;
}HString;



void StrInsert(HString &S,int pos,HString T)
	//在串S的第pos个字符之前插入串T
{
	if(pos<1||pos>S.length+1)
		exit(1);
	if(T.length)
	{
		if(!(S.ch=(char *)realloc(S.ch,(S.length+T.length)*sizeof(char))))
			exit(1);
		for(int i=S.length-1;i>=pos-1;--i)
			S.ch[i+T.length]=S.ch[i];
		for(int i=pos-1;i<=pos+T.length-2;i++)
			S.ch[i]=T.ch[i-pos+1];
		S.length+=T.length;
	}
}

void StrAssign(HString &T,char *chars)
	//生成一个其值等于串常量的chars的串T
{
	int i;
	char *c=chars;
	for(i=0;*c;i++,c++);
	T.ch=(char *)malloc(i*sizeof(char));
	if(!T.ch)
		exit(1);
	for(int k=0;k<i;k++)
		T.ch[k]=chars[k];
	T.length=i;
}
void Display(HString S)
	//输出,显示串
{
	for(int i=0;i<S.length;i++)
		cout<<*(S.ch+i);
	cout<<endl;
}

int StrCompare(HString S,HString T)
	//按照字典序比较HString的大小,越排后越大
//若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0
{
	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;
}

void Concat(HString &T,HString S1,HString S2)
   //用T返回由S1,S2联接而成的新串
{
	int i;
	T.ch=(char *)malloc((S1.length+S2.length)*sizeof(char));
	for(i=0;i<S1.length;i++)
		T.ch[i]=S1.ch[i];
	for(i=S1.length;i<S1.length+S2.length;i++)
		T.ch[i]=S2.ch[i-S1.length];
	T.length=S1.length+S2.length;
}

void SubString(HString &Sub,HString S,int pos,int len)
	//用Sub返回串S的第pos个字符起长度为len的子串
	//其中 1<=pos<=S.length  并且0<=len<=S.length-pos+1
{
	if(pos<1||pos>S.length||len<0||len>S.length-pos+1)
		exit(1);
	Sub.ch=(char *)malloc(len*sizeof(char));
	for(int i=0;i<len;i++)
		Sub.ch[i]=S.ch[i+pos-1];
	Sub.length=len;
}

void StrClear(HString &S)
	//将S清空为空串
{
	if(S.ch)
	{
		free(S.ch);
		S.ch=NULL;
	}
	S.length=0;
}

int Index(HString S,HString T,int pos)
	//返回子串T在主串S中第pos个字符后的位置,若不存在,则函数值为0
{
	int i=pos-1,j=0;
	while(i<S.length&&j<T.length)
	{
		if(S.ch[i]==T.ch[j])
		{
			++i;
			++j;
		}
		else
		{
			i=i-j+1;
			j=0;
		}
	}
    if(j>=T.length)
		return i-T.length+1;
	else
		return 0;
}

void StrDelete(HString &S,int pos,int len)
	//删除S中第pos个位置后的长度为len的子串
{
	int i;
	for(i=pos-1;i+len<S.length;i++)
	{
		S.ch[i]=S.ch[i+len];
	}
	S.length-=len;
}
void Replace(HString &S,HString T,HString V)
	//在S中用V代替所有T
{
	int i=1;
	while(i)
	{
		i=Index(S,T,i);
		if(i)
		{
		StrDelete(S,i,T.length);
		StrInsert(S,i,V);
		i+=V.length;
		}
	}
}
int main()
{
	char *c1="hellolololodd";HString A;
	StrAssign(A,c1);
	char *c2="world";HString B;
	StrAssign(B,c2);

	char *c4="lo";HString T;StrAssign(T,c4);
	char *c5="ok";HString V;StrAssign(V,c5);

	cout<<"字符串A为:";Display(A);cout<<"字符串B为:";Display(B);
	HString C,D;
	Concat(C,A,B);
	SubString(D,A,2,3);
	cout<<"C字符串为A和B的连接";Display(C);
	cout<<"D字符串为A在第2个位置后的长度为3的子串";Display(D);
	char *c3="l";
	HString E;StrAssign(E,c3);
	cout<<"E字符串为";Display(E);
	cout<<"E字符串在B中的位置"<<Index(B,E,1)<<endl;
	StrDelete(B,1,3);
	cout<<"删除B字符串中第1个位置后长度为3的子串    B为";Display(B);
	Replace(A,T,V);
	cout<<"A中字符串的";Display(T);cout<<"替换为";Display(V);
	cout<<"结果为";Display(A);
	cout<<"\nthe program is over\n";
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注