数据结构—串（C/C++版）

本文为CSDN博主coder_gxd原创

转载请注明：https://blog.csdn.net/coder_gxd/article/details/79854201

本文介绍数据结构中串的常用算法（C/C++版），欢迎各位同学讨论指正。

#include <stdlib.h>//函数malloc(),free()所在头文件 
#define maxsize 100     

//串的定义之顺序存储表示
typedef struct {
	char str[maxsize+1];//maxsize表示串的最大长度，maxsize+1是因为结尾'\0';
	int length; //串长 
}Str0;
//串的定义之变长分配存储表示，本文以这种定义方式表示串； 
typedef struct {
	char *ch;//指向动态存储区首地址的字符指针； 
	int length; //串长 
}Str; 

//串的赋值操作,时间复杂度O(ch.length) 
//串的赋值操作是对每一个元素逐个赋值，成功返回1，失败返回0；
int strassign(Str &str,char *ch){//c指向字符数组的首地址，将c中字符赋给串str; 
	if(str.ch!=NULL){//若串str不为空，则释放原字符串； 
		free(str.ch);
	} 
	int len=0;char *c=ch;
	while(*c){++len;++c;}//求字符数组ch长度；
	if(len==0){//若字符数组ch为空，则直接返回空串
		str.ch=NULL;
		str.length=0;
		return 1; 
	}
	else{//若字符数组ch不为空
		str.ch=(char *)malloc(sizeof(char)*(len+1));//去len+1为了多分配一个空间存放结束符'\0';
		if(str.ch==NULL){//分配空间失败，返回0； 
			return 0;
		} 
		else{//分配空间成功 
			c=ch;
			for(int i=0;i<=len;i++,++c){//将字符数组ch的元素逐个赋给串str; 
				str.ch[i]=*c;
			}
			str.length=len;//赋值串长； 
			return 1;
		} 
	}
}

//串比较操作,时间复杂度O(min(s1.length,s2.length));
//串按照字典序比较，若串s1>s2,返回正数；串s1<s2,返回负数；串s1=s2,返回 0；
int strcompare(Str s1,Str s2){
	for(int i=0;i<s1.length&&i<s2.length){
		if(s1.ch[i]!=s2.ch[i]){
			return s1.ch[i]-s2.ch[i];
		}
		return s1.length-s2.length;
	}
} 

//串连接操作,时间复杂度O(s1.length+s2.length);
//将串str2链在串str1后，并赋给Str;成功则返回1，失败返回0；
int concat(Str &str,Str str1,Str str2){
	if(str.ch!=NULL){//若串str不为空，则释放； 
		free(str.ch);
		str.ch=NULL;
	}
	str.ch=(char *)malloc(sizeof(char)*(str1.length+str2.length+1));//重新分配串str内存，多分配一个用来存储结束标志'\0'; 
	if(str.ch==NULL){//分配失败，返回0； 
		return 0;
	}
	int i=0;
	while(i<str.length){//将str1赋给str; 
		str.ch[i]=str1.ch[i];
		++i;
	}
	int j=0;
	while(j<=str2.length){//将str2赋给str; 
		str.ch[i+j]=str1.ch[j];
		++j;
	}
	str.length=str1.length+str2.length;//赋值str.length; 
	return 1;
} 

//串清空操作,时间复杂度为O(1); 
//将串str清空,str.length置为0； 
int clearstring(Str &str){
	if(str.ch!=NULL){
		free(str.ch);
		str.ch=NULL;
	}
	str.length=0;
	return 1;
}