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

ゝ一世哀愁。 2023-03-01 11:49 27阅读 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.12 销毁操作
     *  4.13 遍历
     *  4.14 main函数
 *  5.小结

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

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

# 2.串类型定义 #

typedef struct {
        	//串的堆分配存储表示定义
    	char* ch;		//按串长分配存储区，ch指向串的基址
    	int length;			//串的长度
    }HString;

# 3.函数声明 #

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

# 4.基本操作 #

## 4.1 初始化串 ##

//1.初始化串
    void InitString(HString& S) {
        
    	S.ch = (char*)malloc(sizeof(char) * MAXLEN);
    	S.length = 0;
    }

## 4.2 增加串的长度 ##

//2.增加动态数组的长度
    void IncreaseSize(HString& S, int len) {
        
    	char* p = S.ch;
    	S.ch = (char*)malloc(sizeof(char) * (MAXLEN + len));
    	for (int i = 1; i <= S.length; i++)		//将数据复制到新区域(时间开销大)
    		S.ch[i] = p[i];
    	S.length += len;			//串的长度增加len
    	free(p);		//释放原来的内存空间
    }

## 4.3 求串长 ##

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

## 4.4 清空 ##

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

## 4.5 判空 ##

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

## 4.6 赋值操作★ ##

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

## 4.7 复制操作★ ##

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

## 4.8 联接操作★ ##

//8.串联接操作：用T返回由S1和S2连接而成的新串
    void Concat(HString& T, HString S1, HString S2) {
        
    	/*先将S1赋值给S2,等价于 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.9 求子串操作★★ ##

//9.求子串操作：用Sub返回串S的第pos个字符起长度为len的子串
    bool SubString(HString& Sub, HString 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.10 比较操作★★ ##

//10.比较操作：若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0
    int StrCompare(HString S, HString 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.11 定位操作★★★ ##

//11.定位操作:若主串中存在与串T值相同的子串，则返回它在主串中第一次出现的位置，否则函数值为0，即不存在
    int Index(HString S, HString T) {
        
    	int i = 1, n = StrLength(S), m = StrLength(T);
    	HString sub;		//用于暂存字串
    	InitString(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.12 销毁操作 ##

//12.销毁操作：销毁串S
    void DestroyString(HString& S) {
        
    	free(S.ch);
    	S.ch = NULL;
    }

## 4.13 遍历 ##

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

## 4.14 main函数 ##

int main() {
        
    	/*1、赋值操作*/
    	printf("<——赋值操作S1——>\n");
    	HString S1;
    	InitString(S1);
    	char ch[] = "321";
    	StrAssign(S1, ch);
    	PrintString(S1);
    
    	/*2、复制操作*/
    	printf("<——复制操作S2——>\n");
    	HString S2;
    	InitString(S2);
    	StrCopy(S2, S1);
    	PrintString(S2);
    
    	/*3、联接操作*/
    	printf("<——联接操作S3——>\n");
    	HString S3;
    	InitString(S3);
    	Concat(S3, S1, S2);
    	PrintString(S3);
    
    	/*4、求子串操作*/
    	printf("<——求子串操作S4——>\n");
    	HString S4;
    	InitString(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的子串！\n");
    	else
    		printf("子串S4在S3中的位置为：%d\n", Index(S3, S4));
    
    	/*7、销毁操作*/
    	DestroyString(S1);
    	DestroyString(S2);
    	DestroyString(S3);
    	DestroyString(S4);
    
    	return 0;
    }

# 5.小结 #

1.  **关于串的顺序存储(动态分配)**  
    因为顺序存储的串的动态分配实现同顺序表的动态分配一样，也是用动态数组实现的，通过malloc函数申请的一片连续的存储空间属于**堆区**，因此，也叫 *堆分配存储表示*。
2.  **关于动态分配和静态分配的区别**  
    （1）因为存储空间是自己申请的，所以需要使用free函数手动释放，因此，有了串的销毁操作。  
    （2）动态分配和静态分配最大的不同就是可以扩容，因此，相比静态分配增加了串的扩容操作(增加串的长度)。  
    本质上还是顺序存储，所以可随机存取，虽实现了扩容操作，但移动元素的时间复杂度较大，且不易插入和删除，因此，有了串的链式存储。
3.  **关于串的链式存储说明**  
    和线性表的链式存储几乎一致，只不过和线性表还有一些不同。在链结点中有数据域和指向下个结点的指针域，对于串的链式存储来说，如果每个结点只存一个字符，在32位的计算机中，一个字符占1个字节，指针占4个字节，这样会导致存储密度很低，比较好的解决方案是在一个结点中存多个字符，以提高存储密度，最后一个结点如果存不满，则用一些特殊字符填充用来标识。关于串的链式存储结构后续文章不再展开，重点掌握定长顺序存储，后续关于串的定位操作也以定长顺序存储表示展开。