考研数据结构复习——串（堆分配）

/**
***@Title   ：考研数据结构复习
***@Subject ：串（堆分配）
***@Author  ：lxfhahaha
***@language： C语言
***@Time    ： 2018/10/2 11：13
*****/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define Inital_Size 50
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Bool;
typedef int Status;

typedef struct { 
	char *ch;
	int length; //当前已分配的存储空间
}HString;

//生成一个其值等于串常量chars的串str
Status StrAssign(HString *str,char *chars){
	char *c,*d;
	int i,j;
	for(i=0,c=chars;*c;c++,i++);
	if(!i){
		str->length=0;
		str->ch=NULL;
	}else{
		if(!(str->ch=(char*)malloc(i*sizeof(char)))){
			printf("Malloc Error!!\n");
			exit(0);
		}
		str->length=i;
		for(c=chars,d=str->ch;*c;*(d++)=*(c++));
	}
	return OK;
}

//返回str的元素个数，称为串的长度
int StrLength(HString str){
	return str.length;
}

//若sa>sb，则返回值>0；若sa=sb，则返回值=0；若sa<sb，则返回值<0
int StrComare(HString sa,HString sb){
	int i,j;
	for(i=0;i<sa.length&&i<sb.length;i++)
		if(sa.ch[i]!=sb.ch[i]) return sa.ch[i]-sb.ch[i];
	return sa.length-sb.length;
}

//将str请为空串
Status ClearString(HString *str){
	if(str->ch){
		free(str->ch);
		str->ch=NULL;
		str->length=0;
	}
	return OK;
}

//用str返回由sb，sc构成的新串
Status Concat(HString *str,HString sb,HString sc){
	int i,j;
	if(str->ch){
		free(str->ch);
		str->ch=NULL;
	}
	if(!(str->ch=(char*)malloc(sizeof(char)*(sb.length+sc.length)))){
		printf("Malloc Error!!\n");
		exit(0);
	}
	str->length=sb.length+sc.length;
	for(i=0;i<sb.length;i++)
		str->ch[i]=sb.ch[i];
	for(j=0;j<sc.length;j++)
		str->ch[i+j]=sc.ch[j];
	return OK;
}

//用sub返回串str的第pos个字符起长度为len的子串
//其中，1<=pos<=StrLength(str)且0<=len<=strlength(str)-pos+1
Status SubString(HString *sub,HString str,int pos,int len){
	int i,j;
	if(pos<1||pos>StrLength(str)||len<0||len>StrLength(str)-pos+1){
		printf("Error!!\n");
		return ERROR;
	}
//	if(sub->ch) free(sub->ch);
	if(!(sub->ch=(char*)malloc(sizeof(char)*len))){
		printf("Malloc Error!\n");
		exit(0);
	}
	sub->length=len;
	for(i=0,j=pos-1;i<len;i++,j++)
		sub->ch[i]=str.ch[j];
	return OK;
}

//串str存在，由串str复制得到串snew
Status StrCopy(HString *snew,HString str){
	char *c,*d;
	int i,j;
	if(!(snew->ch=(char*)malloc(str.length*sizeof(char)))){
			printf("Malloc Error!!\n");
			exit(0);
	}
	snew->length=str.length;
	for(c=str.ch,d=snew->ch;*c;*(d++)=*(c++));
	return OK;
}

//打印
Status StrPrintf(HString str){
	int i;
	if(!str.ch){
		printf("Inital First!\n");
		exit(0);
	}
	printf("length: %d \n",str.length);
	printf("[");
	for(i=0;i<str.length;i++)
		putchar(str.ch[i]);
	printf("]\n",str.ch);
	return OK;
}



//若空串返回TRUE，都则ERROR
Bool StrEmpty(HString str){
	return str.length==0? TRUE:FALSE;
}

//1<=pos<=StrLength(sa)
//若主串sa中存在和串sb值相同的子串，则返回它在主串s中第pos个
//字符起，第一次出现的位置，否则函数值为0
int Index(HString sa,HString sb,int pos){
	HString sc;
	if(pos<1||pos>StrLength(sa))
		return 0;
	while(pos<=sa.length-sb.length+1){
		SubString(&sc,sa,pos,sb.length);
		if(StrComare(sc,sb)!=0){
			pos++;
		}else{
			return pos;
		}		
	}		
	return 0;
}

//1<=pos<=StrLength(sa)+1
//在串str的第pos个字符前插入sa
Status StrInsert(HString *str,int pos,HString sa){
	int i,j,k;
	if(!str->ch||pos<1||pos>sa.length+1){
		printf("Insert Error!\n");
		exit(0);
	}
	if(!(str->ch=(char*)realloc(str->ch,sizeof(char)*(sa.length+str->length)))){
		printf("Realloc Error!\n");
		exit(0);
	}
	str->length=sa.length+str->length;
	for(i=str->length-1;i>=pos+sa.length-1;i--){
		str->ch[i]=str->ch[i-sa.length];
	}
	for(i=pos-1,j=0;j<sa.length;i++,j++){
		str->ch[i]=sa.ch[j];
	}
	
	return OK;
}

//1<=pos<=StrLength(sa)-len+1
//从串str中删除第pos个字符起长度为len的子串
Status StrDelete(HString *str,int pos,int len){
	int i,j,k;
	if(!str->ch||pos<1||pos>str->length+1-len){
		printf("Delete Error!\n");
		exit(0);
	}
	for(i=pos-1;i<str->length-len;i++){
		str->ch[i]=str->ch[i+len];
	}
	if(!(str->ch=(char*)realloc(str->ch,sizeof(char)*(str->length-len)))){
		printf("Realloc Error!\n");
		exit(0);
	}
	str->length-=len;
	return OK;
}


//用sb替换主串str中出现的所有与sa相等的不重叠的子串
Status Replace(HString *str,HString sa,HString sb){
	HString sc;
	int i,j,k;
	if(!sa.ch){
		printf("Inital First!\n");
		return ERROR;
	}
	for(i=1,j=Index(*str, sa, i);j!=0;){
		
		StrDelete(str,j, sa.length);
		StrInsert(str,j,sb);
		i=j+sb.length;
		j=Index(*str, sa, i);
	}
	return OK;
}

//销毁
Status DestroyString(HString *s){
	if(s->ch){
		free(s->ch);
		s->ch=NULL;
	}
	s->length=0;
	s=NULL;
	return OK;
}


int main()
{
	HString sa,sb,sc,sd;
	int i,j;
	char *a="aaabbbccc";
	char *b="1234567891234";
	
	printf("StrAssign:\n");
	StrAssign(&sa,a);
	StrAssign(&sb,b);
	printf("sa->");
	StrPrintf(sa);
	printf("sb->");
	StrPrintf(sb);
	
	printf("\nStrCopy:\n");
	StrCopy(&sc,sa);
	printf("sc->");
	StrPrintf(sc);
	
	printf("\nStrCompare:\n");
	printf("sa:sb->%d — sb:sc->%d — sa:sc->%d \n",StrComare(sa,sb),StrComare(sb,sc),StrComare(sa,sc));
		
	printf("\nConcat:\n");
	Concat(&sc,sa,sb);
	printf("sc->");
	StrPrintf(sc);
	
	
	printf("\nSubString:\n");
	SubString(&sd,sc,2,5);
	printf("sd->sub from sc[1]->");
	StrPrintf(sd);
	
	printf("\nIndex:\n");
	printf("sc->");
	StrPrintf(sc);
	printf("sb->");
	StrPrintf(sb);
	printf("Index from sc of sb from 1-> %d \n",Index(sc,sb,1));
	
	
	printf("\nReplace:\n");
	printf("sc->");
	StrPrintf(sc);
	printf("sd->");
	StrPrintf(sd);
	printf("sa->");
	StrPrintf(sa);
	printf("Use sd to Replace all sa from sc -> \n");
	
	Replace(&sc, sa, sd);
	StrPrintf(sc);
	

	
	DestroyString(&sa);
	printf("\nDestroy sa:\n");
	StrPrintf(sa);
	
	DestroyString(&sb);
	DestroyString(&sc);
	return 0;
}