test1.cpp

数据结构中相关ADT的C++实现,注解清晰,让你快速掌握

//实现变长存储的串连接和模式匹配算法
#include<iostream.h>
#include<string.h>
typedef struct
{
	char * ch;
	int length;
}Hstring;
void assign(Hstring & t,char * chars)
{
//生成一个其值等于串常量chars的串T

	int i;
i=strlen(chars);
	if(!i)
	{
		t.ch=NULL;t.length=0;
	}
	else
	{
		t.ch=new char[i];
		t.length=i;
		for(i=0;i<t.length;i++)
			t.ch[i]=chars[i];
	}
}
int strlength(Hstring s)
{
//返回S的元素个数，称为串的长度。
	return s.length;
}
int strcompare(Hstring s,Hstring t)
{
//若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 int(s.ch[i]-t.ch[i]);
	}
	return s.length-t.length;
}
void concat(Hstring & t,Hstring s1,Hstring s2)
{
//用T返回由S1和S2联接而成的新串。
int j;
	t.length=s1.length+s2.length;
	t.ch=new char[t.length];
	for(int i=0;i<s1.length;i++)
	{
		t.ch[i]=s1.ch[i];
	}
	for( j=0,i=s1.length;j<s2.length;j++,i++)
	{
		t.ch[i]=s2.ch[j];
	}
}
int substring(Hstring & sub,Hstring s,int pos,int len)
{
//1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos＋1
//返回串S的第pos个字符起长度为len的子串。
if(pos<1||pos>strlength(s)||len<0||len>strlength(s)-pos+1) return 0;
if(strlength(sub))  {sub.ch=NULL;sub.length=0;}
if(!len){sub.ch=NULL;sub.length=0;return 1;}
sub.ch=new char[len];
for(int i=pos,j=0;i<(len+pos);i++,j++)
{
	sub.ch[j]=s.ch[i-1];
	sub.length++;
}
return 1;
}
int index(Hstring s,Hstring t,int pos)
{
//t为非空串。若主串S中第pos个字符之后存在与t相等的子
//串，则返回第一个这样的子串在S中的位置，否则返回0。
	int p=pos;
	Hstring sy;
	if(pos<1||pos>strlength(s))return 0;
while((p+strlength(t))<=strlength(s)+1)
{
	if(substring(sy,s,p,strlength(t)))
	{
		if(!strcompare(t,sy))
		{
			return p;
		}
		else
			p++;
	}
}
return 0;
}

void main()
{
	Hstring s,s1,s2,sub;
	char * c1="aabbcc";
	char * c2="ddef";
	assign(s1,c1);
	assign(s2,c2);
	concat(s,s1,s2);
	substring(sub,s,3,4);
cout<<index(s,s1,1)<<endl<<index(s,s2,1)<<endl;


}