串的堆分配存储表示与操作实现

发表于 | 更新于: | 分类于 | | 浏览 次

我们知道物理结构分为顺序存储结构和链式存储结构，串的顺序存储包括定长顺序存储和堆分配存储两种，由于后者是动态分配内存的，使用起来更灵活，因此我将把串的堆分配存储结构与其操作实现分享各位小伙伴~(串的链式存储不灵活且操作复杂，因此很少用，在此就不分享了)

串的ADT(Abstract Data Type-抽象数据类型)的实现

#1 堆分配存储表示

String.h (数据对象和关系表示)
1
2
3
4
5
6
7
8
9
10
//===============ADT String的表示======================
#ifndef HSTRING
	#define HSTRING
	typedef int Status;
	//==========串的堆分配存储表示===========l
	typedef struct{
		char* ch;
		int length;
	}HString;
#endif
String_Fun.h (基本操作声明)
1
2
3
4
5
6
7
8
9
10
11
12
#include "String.h"
#ifndef FUN
#define FUN
void StrInit(HString&S);//用于给指针置空，防止野指针出现
Status StrAssign(HString& T,char* chars);//生成一个其值等于串常量的串
int StrLength(HString S);//返回字符串长
int StrCompare(HString S,HString T);//按字典序比较两个字符串大小
Status ClearString(HString& S);//清空字符串
Status ConCat(HString &T,HString S1,HString S2);//合并串S1和串S2，生成串T
Status SubString(HString& Sub,HString S,int pos,int len);
//返回从pos开始，长度为len的S的子串
#endif
String_Fun.cpp (基本操作实现)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#ifndef PRE_LIST
#define PRE_LIST
	#include"String.h"
	#include "String_Fun.h"
	#include<malloc.h>
	#include<stdio.h>
	#include<windows.h>
	#define ERROR 0
	#define OVERFLOW -2
	#define OK 1
	#define INFEASIBLE -1
#endif
/*
	typedef struct{
		char* ch;
		int length;
	}HString;
*/
//------------------基本操作的实现-----------------
void StrInit(HString& S){ 
	S.ch=NULL;
	S.length=0;
}
Status StrAssign(HString &T,char* chars){
	if(T.ch) free(T.ch); 
	if(!chars){
		T.ch=NULL;
		T.length=0;
		return OK;
	}
	int i;
	char* c=NULL;
	for(c=chars,i=0;*c;i++,c++);
	if(!i){T.ch=NULL;T.length=0; return OK;}
	//if(!(T.ch=(char*)malloc(sizeof(char)*(i+1)))) exit(OVERFLOW); 
      //多个'\0'字符，但后来发现不要多申请空间，否则进行合并等操作时还要考
      //虑跳过'\0'字符，这显然使得操作变复杂了
	if(!(T.ch=(char*)malloc(sizeof(char)*i))) exit(OVERFLOW);
	c=chars;//reset
	T.length=i;
	i=0;
	while(*c){
		T.ch[i++]=*c++;
	}
	//T.ch[i]='\0';
	return OK;
}

int StrLength(HString S){
	return S.length;
}

int StrCompare(HString S1,HString S2){
	for(int i=0;i<S1.length&&i<S2.length;i++){
		if(S1.ch[i]!=S2.ch[i]) return S1.ch[i]-S2.ch[i];
	}
	return S1.length-S2.length;
}

Status ClearString(HString& S){
	if(!S.ch) return OK;
	return (free(S.ch),S.ch=NULL,S.length=0,OK);//S.ch=NULL防野指针
}

//由此可知实现该操作不能使字符串末尾为'\0'
Status ConCat(HString &T,HString S1,HString S2){
	if(T.ch) free(T.ch);
	//if(!(T.ch=(char*)malloc(sizeof(char)*(T.length+1)))) exit(OVERFLOW);
      //多的1个空间用于存储'\0'
     if(!(T.ch=(char*)malloc(sizeof(char)*(S1.length+S2.length))))exit(OVERFLOW);
	T.length=S1.length+S2.length;
	char* c=NULL;
	int i;
	/*正确写法*/
	for(i=0;i<S1.length;i++)
		T.ch[i]=S1.ch[i];
	for(;i<T.length;i++)
		T.ch[i]=S2.ch[i-S1.length];
	/* 错误写法*/
	//for(i=0,c=S1.ch;*c;T.ch[i++]=*c++); //会越界，因为串没有用'\0'封闭
	//for(c=S2.ch;*c;T.ch[i++]=*c++);//会越界，因为串没有用'\0'封闭
	//T.ch[i]='\0';
	return OK;
}

Status SubString(HString &Sub,HString S,int pos,int len){
	if(pos<1||pos>StrLength(S)||len<0||len>StrLength(S)-pos+1) return ERROR;
	if(Sub.ch) free(Sub.ch);
	if(!(Sub.ch=(char*)malloc(sizeof(char)*len))) exit(OVERFLOW);
	char* c=NULL;
	int i;
	//for(i=0,*c=S.ch[pos-1];c-(S.ch+pos-1)<len;Sub.ch[i++]=*c++);
      //*c=S.ch[pos-1]有问题，因为c本身没申请堆内存，不能存储值，此处用作一个指针
	for(i=0,c=S.ch+pos-1;c-(S.ch+pos-1)<len;Sub.ch[i++]=*c++);
      //这句没问题，毕竟有长度限制，不会越界
	Sub.length=len;
	return OK;
}
test1.cpp (基本操作的测试)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include"String.h"
#include "String_Fun.h"
#include<stdio.h>
#include<string.h>
void PrintStr(HString S){
	for(int i=0;i<StrLength(S);i++)
		printf("%c",S.ch[i]);
	//printf("%s",S1.ch);//慎用!! %s将对一个没有'\0'休止的char*变量输出，
      //这很可能使得正常输出后面跟乱码
}
/*基本操作测试*/
int main(){
	HString S1,S2,S3;
	//一开始一定要把HString::ch置为NULL，否则它会成为野指针，
      //使得if(T.ch)条件满足而执行free()出现错误
	/* StrInit(HString&) Essential*/
	StrInit(S1);
	StrInit(S2);
	StrInit(S3);
	/**********/
	//StrInit(S3);
	StrAssign(S1,"HelloWorld");
	StrAssign(S2,"I'm Sheng!");
	printf("S1:"); PrintStr(S1); printf("\n");
	printf("S2:"); PrintStr(S2); printf("\n");
	printf("Use StrLength(HString):\n");
	printf("The length of S1 is %d.\n
      The length of S2 is %d.\n",StrLength(S1),StrLength(S2));
	printf("Use ClearString(S1):\n");
	ClearString(S1);
	if(!S1.ch) printf("After the clear,S1 refers to NULL.\n");
	printf("Use StrAssign(HString&,char*) for S1,S2:\n");
	StrAssign(S1,"String is so good");
	StrAssign(S2,"that we should learn it well.");
	printf("S1:"); PrintStr(S1); printf("\n");
	printf("S2:"); PrintStr(S2); printf("\n");
	printf("Use Concat(S3,S1,S2):\n");
	ConCat(S3,S1,S2);
	printf("S3:"); PrintStr(S3); printf("\n");
	printf("Use StrCompare(S1,S2):\n");
	int a;
	(a=StrCompare(S1,S2))>=0?a==0?printf("S1 and S2 are the same.\n"):
	printf("S1 is bigger than S2.\n"):printf("S1 is smaller than S2.\n");
	printf("Use SubString(S2,S1,11,7):\n");
	SubString(S2,S1,11,7);
	printf("S2:");
	PrintStr(S2);
	printf("\n");

	return 0;
}
测试结果

由于作者很懒，代码中的一些细节仅仅用几行注释标注，不再详述。但这些注释其实映射了我写程序的心路历程(其实是我犯的一些错误))，这过程中我遇到很多疑惑，好在我通过频繁的Debug以及查阅资料，最终解决了大部分疑惑，于是也就有了上面一行行绿(灰)色的标注。希望这些注释能引起你我的共鸣。
有什么问题欢迎在评论区讨♂论。