【数据结构】-串的顺序存储(静态分配）

蔚落 2023-03-01 11:48 30阅读 0赞

### 串的定长顺序存储-静态分配 ###

*  串的定长顺序存储示意图
 *  1.头文件及类型定义
 *  2.串类型定义
 *  3.函数声明
 *  4.基本操作
 *   *  4.1 初始化串
     *  4.2 求串长
     *  4.3 清空
     *  4.4 判空
     *  4.5 赋值操作★
     *  4.6 复制操作★
     *  4.7 联接操作★
     *  4.8 求子串操作★★
     *  4.9 比较操作★★
     *  4.10 定位操作★★★
     *  4.11 遍历
     *  4.9 main函数
 *  5.小结

# 串的定长顺序存储示意图 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pYX1pYXw_size_16_color_FFFFFF_t_70_pic_center]

# 1.头文件及类型定义 #

#include<stdio.h>
    #include<stdlib.h>
    #define MAXLEN 255   //预定义最大串长为255

# 2.串类型定义 #

typedef struct {
        		//串的定长顺序存储表示定义
    	char ch[MAXLEN];	//每个分量存储一个字符
    	int length;		//串的实际长度
    }SString;

# 3.函数声明 #

/*函数声明*/
    void InitString(SString& S);									//1.初始化
    int StrLength(SString S);										//2.串长
    void ClearString(SString& S);									//3.清空
    bool StrEmpty(SString S);										//4.判空
    void StrAssign(SString& T, char s[]);							//5.赋值
    void StrCopy(SString& T, SString S);							//6.复制
    void Concat(SString& T, SString S1, SString S2);				//7.连接
    bool SubString(SString& Sub, SString S, int pos, int len);		//8.求子串
    int StrCompare(SString S, SString T);							//9.比较
    int Index(SString S, SString T);								//10.定位
    void PrintString(SString S);									//11.遍历

# 4.基本操作 #

## 4.1 初始化串 ##

//1.初始化
    void InitString(SString& S) {
        
    	S.length = 0;		
    }

## 4.2 求串长 ##

//2.求串长:返回串S的元素个数
    int StrLength(SString S) {
        
    	return S.length;
    }

## 4.3 清空 ##

//3.清空操作：将S清为空串(逻辑上清空)
    void ClearString(SString& S) {
        
    	S.length = 0;
    }

## 4.4 判空 ##

//4.判空操作：若S为空串，返回true，否则返回false
    bool StrEmpty(SString S) {
        
    	return S.length == 0;
    }

## 4.5 赋值操作★ ##

//5.赋值操作：把串T赋值为s
    void StrAssign(SString& T, char s[]) {
        
    	int i = 0;
    	while (s[i])	
    	{
        	
    		T.ch[++T.length] = s[i];
    		i++;
    	}
    }

## 4.6 复制操作★ ##

//6.复制操作：由串S复制得到T
    void StrCopy(SString& T, SString S) {
        
    	for (int i = 1; i <= S.length; i++)
    		T.ch[i] = S.ch[i];
    	T.length = S.length;
    }

## 4.7 联接操作★ ##

//7.联接操作：用T返回由S1和S2连接而成的新串
    void Concat(SString& T, SString S1, SString S2) {
        
    	/*先将S1赋值给T,等价于 StrCopy(T, S1);*/
    	for (int i = 1; i <= S1.length; i++)	
    		T.ch[i] = S1.ch[i];
    	for (int i = 1; i <= S2.length; i++)
    		T.ch[i + S1.length] = S2.ch[i];
    	T.length = S1.length + S2.length;
    }

## 4.8 求子串操作★★ ##

//8.求子串操作：用Sub返回串S的第pos个字符起长度为len的子串
    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 true;
    }

## 4.9 比较操作★★ ##

//9.比较操作：若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0
    int StrCompare(SString S, SString T) {
        
    	for (int i = 1; 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;
    }

## 4.10 定位操作★★★ ##

//10.定位操作:若主串中存在与串T值相同的子串，则返回它在主串中第一次出现的位置，否则函数值为0，即不存在
    int Index(SString S, SString T) {
        
    	int i = 1, n = StrLength(S), m = StrLength(T);
    	SString sub;		//用于暂存字串
    	while (i <= n - m + 1) {
        		//n-m+1是i能取到的最大值
    		SubString(sub, S, i, m);	//从i开始取长度为m的子串
    		if (StrCompare(sub, T) != 0)	//若字串和T不相等
    			++i;					//取下一个字串
    		else
    			return i;	//若相等则返回字串在主串中的位置
    	}
    	return 0;		//S中不存在与T相等的子串
    }

## 4.11 遍历 ##

//11.遍历：仅为测试，可以不写
    void PrintString(SString S) {
        
    	for (int i = 1; i < S.length + 1; i++)
    		printf("%c\t", S.ch[i]);
    	printf("\n");
    }

## 4.9 main函数 ##

int main() {
        
    	/*1、赋值操作*/
    	printf("<——赋值操作S1——>\n");
    	SString S1;
    	InitString(S1);
    	char ch[] = "321";
    	StrAssign(S1, ch);
    	PrintString(S1);
    
    	/*2、复制操作*/
    	printf("<——复制操作S2——>\n");
    	SString S2;
    	StrCopy(S2, S1);
    	PrintString(S2);
    
    	/*3、联接操作*/
    	printf("<——联接操作S3——>\n");
    	SString S3;
    	Concat(S3, S1, S2);
    	PrintString(S3);
    
    	/*4、求子串操作*/
    	printf("<——求子串操作S4——>\n");
    	SString S4;
    	int pos, len;
    	printf("请输入起点和长度：");
    	scanf("%d%d", &pos, &len);
    	if (SubString(S4, S3, pos, len)) {
        
    		printf("所求子串为：");
    		PrintString(S4);
    	}else
    		printf("子串范围越界！\n");
    	
    	/*5、比较操作*/
    	printf("<——比较操作——>\n");
    	if (StrCompare(S1, S2) == 0)
    		printf("S1=S2！\n");
    	else if (StrCompare(S1, S2) > 0)
    		printf("S1>S2! \n");
    	else if(StrCompare(S1, S2) < 0)
    		printf("S1<S2! \n");
    
    	/*6、定位操作*/
    	printf("<——定位操作——>\n");
    	if (Index(S3, S4) == 0)
    		printf("S4不是S3的子串！");
    	else
    		printf("子串S4在S3中的位置为：%d", Index(S3, S4));
    
    	return 0;
    }

# 5.小结 #

1.  **关于串和线性表的异同**  
    (1)同  
    在**逻辑结构**方面串和线性表几乎一样，区别仅在于*串的数据对象限定为字符集*。  
    (2)异  
    在**基本操作**上，串和线性表有很大的区别。线性表的基本操作主要以 *单个元素* 为操作对象，而串的基本操作通常以*子串* 为操作对象。这也是上述代码中标★的原因，关于子串的操作要重点掌握，尤其是定位操作，本文中是用**求子串操作**和**比较操作**这两个基本操作来实现子串的定位操作，后续会通过直接对静态数组操作来实现子串的定位(**这是串的重点内容**)。
2.  **关于串的顺序存储(静态分配)**  
    顺序存储的串的静态分配，也叫 *定长顺序存储表示*，同顺序表的静态分配一样，也是用静态数组实现的，因此，它的优缺点也和顺序表的静态分配一样，便于随机存取，无法扩展，不便删除和插入。所以，也就有了串的动态分配的顺序存储和链式存储。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pYX1pYXw_size_16_color_FFFFFF_t_70_pic_center]: /images/20230208/b3c8050347aa4c2eaa0db80b3a010c53.png