数据结构·串·笔记

• • 1.逻辑结构
  • 2.存储结构
  • 3.常见定义结构体形式
  • 4.清空串
  • 5.赋值操作
  • 6.取串长度
  • 7.串比较
  • 8.串连接
  • 9.求字串

逻辑结构类似线性表，也是一对一的形式。

以顺序结构居多，链式结构较少，本文仅讨论顺序结构‘

定长度的存储定义方式

typedef struct{
				char str[maxSize+1];
				//maxSize为已经定义的常量，表示串的最大长度
				//str数组长度定义为maxSize+1是因为多一个''作结束标志
				int length;
				}Str;

变长度的存储定义方式(后文均采用此结构定义方式）

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

一般使用情况：

Str S;
S.length=L;
S.ch=(char*)malloc((L+1)*sizeof(char));//L+1为''
S.ch[x]='?';//x需要合法不越界
?=S.ch[x];

int clearString(Str &str)
{
	if(str.ch)
	{
	free(str.ch);
	str.ch=NULL;
	}
	str.length=0;
	return 1:
}

int strAssign(Str &str,char *ch)
{
	if(str.ch)
		free(str.ch);
	int len = 0;
	char *c = ch;
	while(*c)
	{
		++len;
		++c;
	}
	if(len==0)
	{
		str.ch=NULL;
		str.length=0;
		return 1;
	}
	else
	{
		str.ch=(char*)malloc(sizeof(char)*(len+1));
		if(str.ch==NULL)
			return 0;
		else
		{
			c=ch;
			for(int i=0;i<=len;i++,c++)
				str.ch[i]=*c;
			str.length=len;
			return 1;
		}
	}
}

int strlength(Str str)
{
	return str.length;
}

比较C1和C2两个字符串：
对应位进行ASCII码比较，第一位与第一位，第二位与第二位以此类推
假设比较字符为a1和a2
a1>a2返回正数
a1 a1=a2比较下一组，若一直到最后都是’=',先结束的是较小串，同时结束则返回0

int strCompare(Str s1,Str s2)
{
	for(int i=0;i 
8.串连接 
int connect(Str &str,Str str1,Str str2)
{
	if(str.ch)
	{
	free(str.ch);
	str.ch=NULL;
	}
	str.ch=(char*)malloc((str1.length+str2.length+1)*sizeof(char));
	if(!str.ch)
		return 0;
	int i=0;
	while(i
		str.ch[i]=str1.ch[i];
		++i;
	}
	int j=0;
	while(j
		str.ch[j]=str2.ch[j];
		++j;
	}
	str.length=str1.length+str2.length;
	return 1;
}
 
9.求字串 
int subString(Str &substr,Str str,int pos,int len)//pos是起点，len是长度
{
	if（pos<0||pos>=str.length||len<0||len>str.length-pos)//字串最大长度
		return 0;
	if(str.ch)
	{
	free(str.ch);
	str.ch=NULL;
	}
	if(len==0)
	{
		substr.ch=NULL;
		substr.length=0;
		return 1;
	}else{
		substr.ch=(char*)malloc((len+1)*sizeof(char));
		int i=pos;
		int j=0;
			while(i
			substr.ch[j]=str.ch[i];
			++i;++j;
			}
		substr.ch[j]='';
		substr.length=len;
		return 1;
		}
}