本篇文章参考王道网课的内容

目录

一、串的顺序存储

1、静态数组实现（定长顺序存储）

2、动态数组实现（堆分配存储）

 3、存储方案​编辑

 4、串的链式存储

5、基本操作的实现

六、求子串的实现方式

七、比较俩个串的大小

八、定位操作

一、串的顺序存储

1、静态数组实现（定长顺序存储）

#define MAXLEN 255    //预定义最大长串为255 
typedef struct{
	char ch[MAXLEN];   //每个分量存储一个字符 
	int length;       //串的实际长度 
}SString;

2、动态数组实现（堆分配存储）

typedef struct{
	char *ch;   //按串长分配存储区，ch指向串的基地址
	int length; //串的长度 
}HString;
//用完需要手动free 
HString S;
S.ch = (char *) malloc(MAXLEN * sizeof(char));
S.length = 0; 

 3、存储方案

 4、串的链式存储

（一）

typedef struct StringNode{
	char ch;
	struct StringLNode *next;	
}StringNode,*String;

缺点：存储密度低，每个字符1B，每个指针4B 

 （二）

typedef struct StringNode{
	char ch[4];     //每个结点存多个字符 
	struct StringNode * next;
}StringNode, *String;

存储密度提高 

5、基本操作的实现

StrAssign(&T, chars): 赋值操作，把串T赋值为chars；

StrCopy(&T, S): 复制操作，把串S复制得到串T

StrEmpty(S): 判空操作，若S为空串，则返回TRUE，否则返回False；

StrLength(S): 求串长，返回串S的元素个数；

ClearString(&S): 清空操作，将S清为空串；

DestroyString(&S): 销毁串，将串S销毁——回收存储空间；

Concat(&T, S1, S2): 串联联接，用T返回由S1和S2联接而成的新串———可能会导致存储空间的扩展；

六、求子串的实现方式

//求子串
bool SubString(SString &Sub,SString S,int pos,int len)
{
    //判断子串范围是否越界
	if(pos+len-1>S.length)
	   return false;
	for(int i = pos;i < pos+len;i ++)
	   Sub.ch[i-pos+1] = S.ch[i];
	Sub.length = len;
	return false;
 } 

七、比较俩个串的大小

StrCompare（S,T）：比较操作。若S>T，则返回值>0;若S=T，则返回值 = 0；若S< T则返回值<0. 

 
 int StrCompare(SString S,SString T)
 {
 	for(int i = 0;i <= S.length && i <= T.length;i ++){
 		if(S.ch[i] != T.ch[i])
 		   return S.ch[i] - T.ch[i];
	 }
	 //扫描过的所有字符都相同，则长度长的串更大
	 return S.length - T.length; 
 }

八、定位操作

Index(S,T) ：定位操作。若主串S中存在与串T值相同的子串，则返回它与主串S中第一次出现的位置；否则函数值为0

// 3. 定位操作
int Index(SString S, SString T){
    int i=1;
    n = StrLength(S);
    m = StrLength(T);
    SString sub;        //用于暂存子串

    while(i<=n-m+1){
        SubString(Sub,S,i,m);
        if(StrCompare(Sub,T)!=0)
            ++i;
        else 
            return i;    // 返回子串在主串中的位置
    }
    return 0;            //S中不存在与T相等的子串
}