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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
| #include <stdio.h>
#include <string.h>
#include <stdlib.h>
/*S是串的名字，串值，串中字符，串的长度，空串，注意空串和空白串的区别。
子串:连续的！位置由第一个字符第一次出现的位置确定
主串：任意的连续的包涵子串的串
串变量和串常量
1，字符串：
串的初始化：错误形式： char name【10】；name = “mwdiade”是非法的。因为这里的name是const型，无法修改
gets和puts函数(getchar和putchar)
strlen()函数：计算长度的，不包括最后的\0 string lenth
strcat(a,b)函数：拼接字符串a,b string catation
strcmp(a,b)函数：字符串比较函数 string compare 返回字符的ansic码的差值
*/
//--------------------------------------------------------------------------------------------------
//定长顺序存储表示(数组)
#define MAXSTRLEN 200 //自定义长度
typedef struct
{
char SString[MAXSTRLEN]; //存储字符数组
int length; //串中实际的字符个数
} SqString; //数据结构
//--------------------------------------------------------------------------------------------
//堆分配存储实现(malloc)
typedef struct
{
char *ch; //串的存储数组，只能是指针类型，不然没法修改
int maxSize; //串数组的最大长度，可以被修改，取决于用户的初始化
int length; //串的当前长度，同上
} HString;
//堆存储的初始化
void InitString(HString &S)
{
S.ch = (char *)malloc(MAXSTRLEN * sizeof(char)); //申请空间
if (S.ch == NULL) //判断申请是否成功
exit(1);
S.ch[0] = '\0'; //置空，注意，这里置空后后续是可以修改的，因为是指针类型；
S.maxSize = MAXSTRLEN; //修改参量
S.length = 0; //修改参量
}
//堆存储的提取子串
HString SubString(HString &S, int pos, int len)
{
HString tmp;
tmp.ch = (char *)malloc(MAXSTRLEN * sizeof(char));
tmp.maxSize = MAXSTRLEN;
if (pos < 0 || len < 0 || pos + len - 1 >= S.maxSize) //如果输入的数据不合法，返回空串，注意这里的判断用法
{
tmp.length = 0; //修改参数
tmp.ch[0] = '\0';
}
else
{
if (pos + len - 1 >= S.length) //长度大于主串，那么只能得到部分len
len = S.length - pos; //此时传进的len的值有误，修改，使得长度到末尾
//此时已经保证了所有的数据都是合法的了，于是可以循环遍历复制了
for (int i = 0, j = pos; i < len; i++, j++)
tmp.ch[i] = S.ch[j]; //复制
tmp.length = len; //修改参数
tmp.ch[len] = '\0'; //加上串最后一位的\0
}
return tmp; //返回子串
}
//堆串的链接算法
void concation(HString &S, HString &T)
{
//函数将串t复制到串S之后，通过S返回结果，串T不变
if (S.length + T.length <= S.maxSize) //如果不溢出，就直接复制，然后修改参数
{
for (int i = 0; i < T.length; i++) //循环遍历复制
S.ch[S.length + 1] = T.ch[i];
S.length = S.length + T.length; //修改参数
S.ch[S.length] = '\0'; //增加最后一个位置的\0
}
else //如果存在溢出
{ //就好像我们在学习链表的存储一样，此时我们创建新的堆串，使得新的堆串和原先的
//堆串指向同一片区域，最后释放这片区域。同时，开辟新的区域，存储链接后的结果，
//最后返回新的区域的地址，当然，也可以修改使得返回值
char *tmp = S.ch; //创建新的堆栈，最后便于释放原先的空间
S.maxSize = S.length + T.length; //修改参数，用于确定新开辟的空间的大小和链接串
S.ch = (char *)malloc((S.maxSize + 1) * sizeof(char)); //开辟新的空间
strcpy(S.ch, tmp); //复制原先的串的值到tmp
strcat(S.ch, T.ch); //链接串
S.length = S.length + T.length; //修改结果中的参数
free(tmp); //释放旧的串
}
}
//--------------------------------------------------------------------------------------------------------------------------
//串的块链存储表示
/*单链表形式存储字符串
每个结点的数据域可以存储n(自定义固定大小的值)个字符，叫做块的大小
存储密度： (串值所占的存储位/实际分配的存储位) <1
*/
#define BlockSize 4 //自定义结点的数据域大小
typedef struct block
{
char ch[BlockSize]; //数据域
struct block *next; //指向下一个结点的指针
} Chunk; //结点的数据结构
typedef struct
{
Chunk *first, *last; //头指针和尾指针
int length; //串的当前长度
} LString;
|