数据结构算法C语言实现（十四）--- 4.1&4.2串的类型定义、表示及实现
一.简述
【暂无】
二.头文件
1 //4_2_part1.h
2 /**
3 author:zhaoyu
4 */
5 //2016-6-10
6 //----串的定长顺序存储表示----
7 #include "head.h"
8 #define MAXSTRLEN 255//用户可以在255以内定义最大串长
9 //这语法还不是很熟悉
10 typedef unsigned char SString[MAXSTRLEN+1];//0 号单元存放串的长度
11 int StrLength(SString T)
12 {
13 for (int i = 1; i <= MAXSTRLEN; ++i)
14 {
15 if ('\0' == T[i])
16 {
17 return i-1;
18 }
19 }
20 return MAXSTRLEN;
21 }
22
23 /**
24 algorithm 4.2
25 */
26 Status Concat(SString &T, SString S1, SString S2)
27 {
28 //用 T 返回由 S1 和 S2 连接而成的新串。
29 //若未截断，则返回 TRUE，否则返回 FALSE
30 Status uncut;
31 if (S1[0] + S2[0] < MAXSTRLEN)
32 {//未截断
33 int i = 1;
34 for (i = 1; i <= S1[0]; ++i)
35 {
36 T[i] = S1[i];
37 }
38 for (i = 1; i <= S2[0]; ++i)
39 {
40 T[S1[0]+i] = S2[i];
41 }
42 T[0] = S1[0] + S2[0];
43 uncut = TRUE;
44 }
45 else if (S1[0] < MAXSTRLEN)
46 {
47 int i = 1;
48 for (i = 1; i <= S1[0]; i++)
49 {
50 T[i] = S1[i];
51 }
52 for (i = S1[0]+1; i <= MAXSTRLEN; i++)
53 {
54 T[i] = S2[i-S1[0]];
55 }
56 T[0] = MAXSTRLEN;
57 uncut = FALSE;
58 }
59 else
60 {
61 for (int i = 1; i <= MAXSTRLEN; i++)
62 {
63 T[i] = S1[i];
64 }
65 T[0] = S1[0] = MAXSTRLEN;
66 uncut = FALSE;
67 }
68 return uncut;
69 }
70 /**
71 algorithm 4.3
72 */
73 Status SubString(SString &Sub, SString S, int pos, int len)
74 {
75 //用 Sub 返回串 S 的第 pos 个字符起长度为 len 的字串
76 //其中， 1<= pos <<= SreLength(S) 且 0 <= len <= StrLength(S)-pos+1
77 if (pos < 1 || pos > S[0] || len < 0 || len > S[0]-pos+1)
78 {
79 return ERROR;
80 }
81 for (int i = 1; i <= len; i++)
82 {
83 Sub[i] = S[i+pos-1];
84 }
85 Sub[0] = len;
86 return OK;
87 }
88 void PrintSString(SString T)
89 {
90 //if(T[])
91 for (int i = 1; i <= T[0]; ++i)
92 {
93 printf("%c", *(T+i));
94 }
95 printf("\n");
96 }
97
98 4_2_part1.h
4_2_part1.h
1 //4_2_part2.h
2 /**
3 author:zhaoyu
4 */
5 //2016-6-12
6 #include "head.h"
7 #include <cstdlib>
8 #include <cstring>
9 //----串的对分配存储表示----
10 typedef struct {
11 char *ch;//
12 int length;
13 }HString;
14
15 Status StrInsert(HString &S, int pos, HString T)
16 {//1<= pos <= StrLength(S)+1
17 //在串的第 pos 个字符之前插入串 T
18 if (1 < pos || pos > S.length + 1)
19 {
20 printf("Illegal pos\n");
21 return ERROR;
22 }
23 if (T.length){//T 非空，则重新分配空间，插入 T
24 if (!(S.ch = (char *)realloc(S.ch, (S.length +
25 T.length)*sizeof(char))));
26 {
27 exit(OVERFLOW);
28 }
29 for (int i = S.length-1; i >= pos-1; i--)
30 {//为插入 T 为腾出位置
31 S.ch[i+T.length] = S.ch[i];
32 }
33 for (int i = pos-1; i <= pos+T.length-2; i++)
34 {//插入 T
35 S.ch[i] = T.ch[i];
36 }
37 S.length += T.length;
38 }
39 return OK;
40 }
41 //page 76-77
42 //----基本操作的算法描述----
43 Status StrAssign(HString &T, char *chars)
44 {//生成一个其值等于串常量 chars的串 T
45 if (T.ch)
46 {
47 T.ch = NULL;
48 }
49 int L;
50 char *c;;
51 for (L = 0, c = chars; *c!='\0'; ++L, ++c);//求 chars 的长度 L
52 if(!L)
53 {
54 T.ch = NULL;
55 T.length = 0;
56 }
57 else
58 {
59 if (!(T.ch = (char *)malloc(L*sizeof(char))))
60 {
61 exit(OVERFLOW);
62 }
63 for (int i = 0; i < L; ++i)
64 {
65 T.ch[i] = chars[i];
66 }
67 T.length = L;
68 }
69 return OK;
70 }
71 int StrLength(HString S)
72 {//返回 S 的元素个数， 称为串的长度
73 return S.length;
74 }
75 int StrCompare(HString S, HString T)
76 {//若 S >|=|< T，则返回 >|=|< 0
77 for (int i = 0; i < S.length && i < T.length; i++)
78 {
79 if (T.ch[i] != S.ch[i])
80 {
81 return S.ch[i] - T.ch[i];
82 }
83 }
84 return S.length - T.length;
85 }
86 Status ClearString(HString &S)
87 {
88 //将 S 清空为空串
89 if (S.ch)
90 {
91 free(S.ch);
92 S.ch = NULL;
93 }
94 S.length = 0;
95 return OK;
96 }
97 Status Concat(HString &T, HString S1, HString S2)
98 {
99 if (T.ch)
100 {//释放旧空间
101 free(T.ch);
102 }
103 if (!(T.ch = (char *)malloc((S1.length+S2.length)*sizeof(char))))
104 {
105 exit(OVERFLOW);
106 }
107 for (int i = 0; i < S1.length; ++i)
108 {
109 T.ch[i] = S1.ch[i];
110 }
111 for (int i = 0; i < S2.length; ++i)
112 {
113 T.ch[i+S1.length] = S2.ch[i];
114 }
115 T.length = S1.length + S2.length;
116 return OK;
117 }
118 Status SubString(HString &Sub, HString S, int pos, int len)
119 {
120 //用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串
121 //其中，其中， 1<= pos <<= SreLength(S) 且 0 <= len <= StrLength(S)-pos+1
122 if (pos < 1 || pos > S.length || len < 0 || len > S.length-pos+1)
123 {
124 return ERROR;
125 }
126 if (Sub.ch)
127 {
128 free(Sub.ch);
129 }
130 if (!len)
131 {//空子串
132 Sub.ch = NULL;
133 Sub.length = 0;
134 }
135 else
136 {
137 Sub.ch = (char *)malloc(len*sizeof(char));
138 for (int i = 0; i < len; ++i)
139 {
140 Sub.ch[i] = S.ch[pos+i-1];
141 }
142 Sub.length = len;
143 }
144 return OK;
145 }
146 void PrintHString(HString S)
147 {
148 for (int i = 0; i < S.length; ++i)
149 {
150 printf("%c", S.ch[i]);
151 }
152 printf("\n");
153 }
4_2_part2.h
三.CPP文件
1 #include "4_2_part1.h"
2 int main(int argc, char const *argv[])
3 {
4 SString S1;
5 SString S2;
6 SString T;
7 scanf("%s", S1+1);
8 *S1 = StrLength(S1);
9 scanf("%s", S2+1);
10 *S2 = StrLength(S2);
11 Concat(T, S1, S2);
12 PrintSString(T);
13 int pos = 2, len = 5;
14 SubString(T, S1, pos, len);
15 PrintSString(T);
16 return 0;
17 }
4_2_part1.cpp
1 #include "4_2_part2.h"
2 int main(int argc, char const *argv[])
3 {
4 char S[100];
5 HString T = {NULL, 0};
6 HString S1 = {NULL, 0};
7 HString S2 = {NULL, 0};
8 scanf("%s", S);
9 StrAssign(S1, S);
10 printf("S1:\t");
11 PrintHString(S1);
12 printf("StrLength\t%d\n", StrLength(S1));
13 scanf("%s", S);
14 StrAssign(S2, S);
15 printf("S2\t");
16 PrintHString(S2);
17 printf("StrLength\t%d\n", StrLength(S1));
18 printf("Compare S1 vs S2\t%d\n", StrCompare(S1, S2));
19 Concat(T, S1, S2);
20 printf("T = S1 + S2\t");
21 PrintHString(T);
22 SubString(S1, T, 2, 3);
23 printf("Sub :T[2]-T[4]\t");
24 PrintHString(S1);
25 return 0;
26 }
4_2_part2.cpp
四.测试
连接
求子串
比较串
