数据结构之串

串（string,又称字符串）是一种有特殊的线性表，每个元素结点仅由一个字符组成。

串的常见存储结构有顺序存储结构和链式存储结构。

顺序存储结构按存储方式又分为：

静态存储分配(定长顺序存储)

动态存储分配(堆分配存储)

1 串的定长顺序存储

用一组地址连续的存储单元来存储串中的字符序列。

具体类型定义如下：

 

#define MAXSIZE 100
typedef struct{
    char str[MAXSIZE];
    int len;
}seqString;

基本操作：

//创建字符串
seqString *createStr(seqString *s){
    gets(s->str);
    s->len = lenStr(s);
    return s;
}

//求字符串长度
int lenStr(seqString *s){
    int i=0;
    while(s->str[i]!='\0')
        i++;
    return i;
}
//字符串连接
void catStr(seqString *r1,seqString *r2){
    if(r1->len+r2->len > MAXSIZE){
        printf("两个字符串相加太长，溢出！");
    }else{
        for(i=0;i<r2->len;i++)
            r1->str[r1->len+i] = r2->str[i];
        r1->len=r1->len+r2->len;//修改连接后新串的长度
    }
}
//求子串
seqString *subStr(seqString *r,int i,int j){
	seqString *r1;
	int k;
	if(i+j-1>r->len){
		printf("子串越界");
		return;
	}else{
		for(k=0;k<j;k++){
			r1->str[k] = r->str[i+j-1];//从r中取出子串
		r1->len = j;
		r1->str[r1->len] = '\0';
	}
	return r1;
}
//串相等的比较,在2个串长度不相等的情况下比较串的长度，相等的情况下比较第一个不相同的字符的大小
int equalStr(seqString *r1,seqString *r2){
	int i;
	for(i=0;i<r1->len && i<r2->len;i++)
		if(r1->str[i]!=r2->str[i])
			return (r1->str[i]-r2->str[i]);
		return (r1->len - r2->len);
}
//插入子串
seqString *insertStr(seqString *s,seqString *s1,int i){
	if(i>s->len || s->len + s1->len > MAXSIZE){
		printf("溢出");
	}else{
		int k = s1->len-1;
		//腾出位置
		while(k >= i){
			s->str[k+s1->len] = s->str[k];
			k--;
		}
		for(k=i;k<i+s1->len;k++){
			s->str[k] = s1->str[k-i];
		}
		//改变字符串s的长度
		s->len = s->len + s1->len;
		//修改最后一位
		s->str[s->len] = '\0';
	}
}
//删除子串，从第i位开始，删除j个字符
void delStr(seqString *r,int i,int j){
	int k = 0;
	if(i+j-1 > r->len)
		printf("子串越界");
	else{
		while(k<j){
			r->str[i+k] = s->str[i+k+j];
			k++;
		}
		r->len = r->len - j;
		r->str[r->len] = '\0';//字符串最后以'\0'结束
	}
}

 

2 串的堆分配存储

优点：可以根据具体情况，灵活地申请适当数目的存储空间，从而提高存储资源利用率。

类型定义如下：

typedef struct{
    char *str;
    int len;
}HString;

基本操作：

(1) 串的赋值

//赋值，将字符串常量r的值赋给堆串s
int createHstr(HString *s,char *r){
	int len,i=0;
	if(s->str!=NULL) free(s->str);//若s已经存在，将它占据的空间释放掉
	while(r[i]!='\0') i++;
	if(i!=0){//分配空间
		s->str = (char *)malloc(i);
		if(s->str == NULL){
			printf("空间分配失败");
			return(0);
		}
		for(i=0;i<len;i++)
			s->str[i] = r[i];
	}else{
		s->str = NULL;
	}
	s->len = i;
	return(1);
}

 (2) 判断串是否为空

int isStrEmpty(HString *s){
   return s->len == 0 ? 0:1;
}