串->串的表示和实现

 1 //
 2 // Created by Zhenjie Yu on 2019-04-14.
 3 //
 4 
 5 #include <stdio.h>
 6 #include <stdlib.h>
 7 #include <string.h>
 8 
 9 #define DEBUG
10 #ifdef DEBUG
11 #include <stdarg.h>
12 #define LOG(args...) _log_(__FILE__, __FUNCTION__, __LINE__, ##args);
13 static void _log_(const char *file, const char *function, int line, const char * format, ...)
14 {
15     char buf[1024] = {0};
16     va_list list;
17     va_start(list, format);
18     vsprintf(buf+strlen(buf), format, list);
19     sprintf(buf+strlen(buf), "\n");
20     va_end(list);
21     printf(buf);
22 }
23 #else
24 #define LOG
25 #endif // DEBUG
26 
27 #define MAX_STRING 255
28 typedef unsigned char SString[MAX_STRING+1]; //第一位表示串长
29 
30 static int Concat(SString T, SString S1, SString S2){
31     int uncut = -1;
32     if(S1[0]+S2[0] <= MAX_STRING){
33         snprintf(T+1, S1[0]+1, "%s", S1+1);
34         snprintf(T+1+S1[0], S2[0]+1, "%s", S2+1);
35         T[0] = S1[0] + S2[0];
36         uncut = 1;
37     }else if(S1[0] < MAX_STRING){
38         snprintf(T+1, S1[0]+1, "%s", S1+1);
39         snprintf(T+1+S1[0], MAX_STRING-S1[0]+1, "%s", S2+1);
40         T[0] = MAX_STRING;
41         uncut = 0;
42     }else{
43         snprintf(T+1, MAX_STRING+1, "%s", S1+1);
44         T[0] = MAX_STRING;
45         uncut = 0;
46     }
47     return uncut;
48 }
49 
50 static int StrAssign(SString T, const char chars[]){
51     memset(T, 0, MAX_STRING+1);
52     int len = strlen(chars);
53     if(len > MAX_STRING){
54         return -1;
55     }
56     T[0] = len;
57     snprintf(T+1, len+1, "%s", chars);
58     return 0;
59 }
60 
61 static int SubString(SString Sub, SString S, int pos, int len)
62 {
63     if(pos<1 || pos>S[0] || len<0 || len>(S[0]-pos+1)){
64         return -1;
65     }
66     snprintf(Sub+1, len+1, S+pos);
67     Sub[0] = len;
68     return 0;
69 }
70 
71 int main(int argc, char *arg)
72 {
73     SString S1, S2, T, Sub;
74     int ret = -1;
75 
76     StrAssign(S1, "test123");
77     LOG("设置串S1的值为%s, 长度为%d", S1+1, S1[0]);
78 
79     StrAssign(S2, "abcdef");
80     LOG("设置串S2的值为%s, 长度为%d", S2+1, S2[0]);
81 
82     ret = Concat(T, S1, S2);
83     LOG("连接串S1和S2,并保存到变量T中，连接后T为%s, T的长度为%d", T+1, T[0]);
84 
85     ret = SubString(Sub, T, 4, 6);
86     LOG("求主串T中，起始地址为4,长度为6的子串，子串结果保存咋变量Sub中; Sub的值为%s,长度为%d", Sub+1, Sub[0]);
87     return 0;
88 }

  1 //
  2 // Created by Zhenjie Yu on 2019-04-14.
  3 //
  4 
  5 #include <stdio.h>
  6 #include <stdlib.h>
  7 #include <string.h>
  8 
  9 #define DEBUG
 10 #ifdef DEBUG
 11 #include <stdarg.h>
 12 #define LOG(args...) _log_(__FILE__, __FUNCTION__, __LINE__, ##args);
 13 static void _log_(const char *file, const char *function, int line, const char * format, ...)
 14 {
 15     char buf[1024] = {0};
 16     va_list list;
 17     va_start(list, format);
 18     vsprintf(buf+strlen(buf), format, list);
 19     sprintf(buf+strlen(buf), "\n");
 20     va_end(list);
 21     printf(buf);
 22 }
 23 #else
 24 #define LOG
 25 #endif // DEBUG
 26 
 27 
 28 typedef struct HString{
 29     char *ch;  //如果是空串，就为NULL；否则按串长分配存储区
 30     int length; //串长度
 31 }HString;
 32 
 33 //生成一个其值等于串常量chars的串T
 34 static int StrAssign(HString *T, const char *chars);
 35 //返回S的元素个数，称为串的长度
 36 static int StrLength(HString S);
 37 //如果S大于T，则返回正值; 如果S等于T，则返回0; 否则返回负值
 38 static int StrCompare(HString S, HString T);
 39 //将S清为空串
 40 static int ClearString(HString *S);
 41 //用T返回由S1和S2连接而成的新串
 42 static int Concat(HString *T, HString S1, HString S2);
 43 //用Sub返回串S的第pos个字符起长度为Len的子串
 44 static int SubString(HString *Sub, HString S, int pos, int len);
 45 
 46 //返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0;
 47 static int Index(HString S, HString T, int pos){
 48     if(pos<0 || pos>=S.length){
 49         return -1;
 50     }
 51     int i = pos, j = 0;
 52     while(i<S.length && j<T.length){
 53         LOG("普通方法: 比较S.ch[%d]=%c 和 T.ch[%d]=%c", i, S.ch[i], j, T.ch[j]);
 54         if(S.ch[i] == T.ch[j]){
 55             i += 1;
 56             j += 1;
 57         }else{
 58             i = i-j+1;
 59             j = 0;
 60             LOG("普通方法: 两者不等，需把S的下标i回退到%d, 把T的下标j回退到%d", i, j);
 61         }
 62     }
 63     if(j>=T.length){
 64         return i-T.length;
 65     }else{
 66         return 0;
 67     }
 68 }
 69 
 70 
 71 
 72 /*********************使用KMP算法求子串位置的定位函数************************/
 73 void get_next(HString T, int next[]){
 74     int i = 1;
 75     int j = 0;
 76     memset(next, 0, T.length);
 77     next[1] = 0;
 78     int count = 1;
 79     while(i<T.length){
 80         count += 1;
 81         if(j == 0 || T.ch[i-1] == T.ch[j-1]){
 82             ++i;
 83             ++j;
 84             next[i] = j;
 85         }else{
 86             j = next[j];
 87         }
 88     }
 89 
 90     for(i=1; i<=T.length; i++){
 91         if(next[i]){
 92             next[i] = next[i]-1;
 93         }
 94         next[i-1] = next[i];
 95     }
 96 
 97     for(i=0; i<T.length; i++){
 98         LOG("KMP算法中字串(%s)的next函数值: next[%d]=%d", T.ch, i, next[i]);
 99     }
100 }
101 //https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html
102 static int Index_KMP(HString S, HString T, int pos){
103     if(pos<0 || pos>=S.length){
104         return -1;
105     }
106     int i = 0;
107     int j = 0;
108     int *next = (int*)malloc(sizeof(int)*T.length+1);
109 
110     get_next(T, next);
111 
112     i = pos;
113     j = 0;
114     while(i<S.length && j<T.length){
115         LOG("用KMP方法: 比较S.ch[%d]=%c 和 T.ch[%d]=%c", i, S.ch[i], j, T.ch[j]);
116         if(S.ch[i] == T.ch[j] || j == 0){
117             i += 1;
118             j += 1;
119         }else{
120             j = next[j];
121             LOG("用KMP方法: 两者不等，需把S的下标i保持不变, 把T的下标j回退到%d", j);
122         }
123     }
124 
125     free(next);
126     if(j>=T.length){
127         //匹配成都
128         return i-T.length;
129     }else{
130         return 0;
131     }
132 }
133 
134 
135 /*********************使用优化后的KMP算法求子串位置的定位函数************************/
136 void get_next_Val(HString T, int nextval[])
137 {
138     memset(nextval, 0, T.length+1);
139     int i = 1;
140     int j = 0;
141     nextval[1] = 0;
142     while (i<T.length){
143         if(j==0 || T.ch[i-1] == T.ch[j-1]){
144             i += 1;
145             j += 1;
146             if(j && (T.ch[i-1] != T.ch[j-1])){
147                 nextval[i] = j;
148             }else{
149                 nextval[i] = nextval[j];
150             }
151         }else{
152             j = nextval[j];
153         }
154     }
155 
156     for(i=1; i<=T.length; i++){
157         if(nextval[i]){
158             nextval[i] = nextval[i]-1;
159         }
160         nextval[i-1] = nextval[i];
161     }
162 
163     for(i=0; i<T.length; i++){
164         LOG("优化后的KMP算法中字串(%s)的nextval函数值: nextval[%d]=%d", T.ch, i, nextval[i]);
165     }
166     return ;
167 }
168 static int Index_KMP_Val(HString S, HString T, int pos)
169 {
170     if(pos<0 || pos>=S.length){
171         return -1;
172     }
173     int i = 0;
174     int j = 0;
175     int *next = (int*)malloc(sizeof(int)*T.length+1);
176 
177     get_next_Val(T, next);
178 
179     i = pos;
180     j = 0;
181     while(i<S.length && j<T.length){
182         LOG("用优化后的KMP方法: 比较S.ch[%d]=%c 和 T.ch[%d]=%c", i, S.ch[i], j, T.ch[j]);
183         if(S.ch[i] == T.ch[j] || j == 0){
184             i += 1;
185             j += 1;
186         }else{
187             j = next[j];
188             LOG("用优化后的KMP方法: 两者不等，需把S的下标i保持不变, 把T的下标j回退到%d", j);
189         }
190     }
191     free(next);
192     if(j>=T.length){
193         //匹配成都
194         return i-T.length;
195     }else{
196         return 0;
197     }
198 }
199 
200 
201 
202 int main(int argc, char *argv[])
203 {
204     int ret = -1;
205     int pos = 0;
206     HString S1, S2, T, Sub, S;
207     S1.ch = S2.ch = T.ch = Sub.ch = S.ch = NULL;
208     S1.length = S2.length = T.length = Sub.length = 0;
209 
210     ret = StrAssign(&S1, "hbcde");
211     LOG("设置变量S1为%s", S1.ch);
212 
213     ret = StrAssign(&S2, "ghijklm");
214     LOG("设置变量S2为%s", S2.ch);
215 
216     ret = StrCompare(S1, S2);
217     LOG("较字符串S1和S2的大小, 返回值为%d", ret);
218 
219     ret = Concat(&T, S1, S2);
220     LOG("将字符串S1和S2拼接，并将值保存到T; 结果使得变量T为%s", T.ch);
221 
222     ret = SubString(&Sub, T, 4, 3);
223     LOG("求字符串T中起始4开始、长度为3的子串，并将子串放到变量Sub; 结果使得变量Sub为%s, （下标从1开始）", Sub);
224 
225     LOG("清空S1、S2、T、Sub变量的内容");
226     ClearString(&S1);
227     ClearString(&S2);
228     ClearString(&T);
229     ClearString(&Sub);
230 
231     ret = StrAssign(&S, "acabaabaabcacaabc");
232     LOG("设置变量S为%s", S.ch);
233 
234     ret = StrAssign(&T, "abaabc");
235     LOG("设置变量T为%s", T.ch);
236 
237     LOG("求字串S中位置pos开始，是否存在子串T; 如果存在，则返回字串T在S中的位置下标");
238     LOG("方法一：普通方法");
239     ret = Index(S, T, pos);
240     LOG("普通方法: 求字串S(%s)中位置pos(%d)开始，是否存在子串T(%s); 返回的下标为%d (下标从0开始)\n", S.ch, pos, T.ch, ret);
241 
242     LOG("方法二：用KMP方法，例1");
243     ret = Index_KMP(S, T, pos);
244     LOG("用KMP方法，例1: 求字串S(%s)中位置pos(%d)开始，是否存在子串T(%s); 返回的下标为%d (下标从0开始)\n", S.ch, pos, T.ch, ret);
245 
246     ret = StrAssign(&S, "aaabaaaab");
247     LOG("设置变量S为%s", S.ch);
248 
249     ret = StrAssign(&T, "aaaab");
250     LOG("设置变量T为%s", T.ch);
251 
252     LOG("方法二：用KMP方法，例2");
253     ret = Index_KMP(S, T, pos);
254     LOG("用KMP方法，例2: 求字串S(%s)中位置pos(%d)开始，是否存在子串T(%s); 返回的下标为%d (下标从0开始)\n", S.ch, pos, T.ch, ret);
255 
256 
257     LOG("方法三：用改进后的KMP方法");
258     ret = Index_KMP_Val(S, T, pos);
259     LOG("用改进后的KMP方法: 求字串S(%s)中位置pos(%d)开始，是否存在子串T(%s); 返回的下标为%d (下标从0开始)", S.ch, pos, T.ch, ret);
260     return 0;
261 }
262 
263 
264 
265 //////////////////////////////////////////////////////////////////////////
266 static int StrAssign(HString *T, const char *chars)
267 {
268     if(T == NULL){
269         return -1;
270     }
271     if(T->ch){
272         free(T->ch);
273         T->ch = NULL;
274     }
275     int len = strlen(chars);
276     if((T->ch = malloc(len+1)) == NULL){
277         return -1;
278     }
279     memset(T->ch, 0, len+1);
280     T->length = len;
281     snprintf(T->ch, len+1, "%s", chars);
282     return 0;
283 }
284 
285 static int StrLength(HString S)
286 {
287     return S.length;
288 }
289 
290 static int StrCompare(HString S, HString T)
291 {
292     int i = 0;
293     for(i=0; i<S.length && i<T.length; ++i){
294         if(S.ch[i] != T.ch[i]){
295             return S.ch[i] - T.ch[i];
296         }
297     }
298     return S.length - T.length;
299 }
300 
301 static int ClearString(HString *S)
302 {
303     if(S->ch){
304         free(S->ch);
305         S->ch = NULL;
306     }
307     S->length = 0;
308     return 0;
309 }
310 static int Concat(HString *T, HString S1, HString S2)
311 {
312     if(T->ch){
313         free(T->ch);
314         T->ch = NULL;
315     }
316     if((T->ch = (char*)malloc((S1.length+S2.length)*sizeof(char))) == NULL){
317         return -1;
318     }
319     strncpy(T->ch, S1.ch, S1.length);
320     strncpy(T->ch+S1.length, S2.ch, S2.length);
321     T->length = S1.length + S2.length;
322     T->ch[T->length] = ‘\0‘;
323     return 0;
324 }
325 
326 static int  SubString(HString *Sub, HString S, int pos, int len)
327 {
328     if(pos<1 || pos>S.length || len<0 || len>S.length-pos+1){
329         return -1;
330     }
331     if(Sub->ch){
332         free(Sub->ch);
333         Sub->ch = NULL;
334     }
335     if(!len){
336         Sub->ch = NULL;
337         Sub->length = 0;
338     }else{
339         Sub->ch = (char *)malloc(len*sizeof(char)+1);
340         memset(Sub->ch, 0, len);
341         strncpy(Sub->ch, S.ch+pos-1, len);
342         Sub->length = len;
343         Sub->ch[len] = ‘\0‘;
344     }
345     return 0;
346 }