数据结构C语言-串-BF-KMP算法

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include "SeqString.h"
 4 
 5 void TestSeqString();
 6 void TestBF();
 7 void TestVirusDemo();
 8 int virus_check(HString parent,HString child);
 9 
10 int main()
11 {
12     //TestSeqString();
13     //TestBF();
14     return 0;
15 }
16 
17 void TestSeqString()
18 {
19     HString * str1 = (HString*)malloc(sizeof(HString));
20     HString * str2 = (HString*)malloc(sizeof(HString));
21     HString * str4 = (HString*)malloc(sizeof(HString));
22 
23     StrAssign_H(str1,"abcdfrhjk");
24     PrintH(str1);
25     printf("\n");
26 
27     printf("复制后：\n");
28     StrCopy_H(str2,str1);
29     PrintH(str2);
30 
31     printf("\n比较:\n");
32     printf("%d",StrCompare(str1,str2));
33 
34     printf("\n合并:\n");
35     HString * str3 = (HString*)malloc(sizeof(HString));
36     Concac_H(str3,str1,str2);
37     PrintH(str3);
38 
39     printf("\n截取后：\n");
40     SubString_H(str3,str1,1,3);
41     PrintH(str3);
42 
43     printf("\n父子串匹配：\n");
44     StrAssign_H(str4,"frh");
45     printf("%d\n",Index_H(str1,str4,2));
46 
47     free(str1);
48     free(str2);
49     free(str3);
50     free(str4);
51 }
52 
53 void TestBF()
54 {
55     HString a;
56     HString b;
57     StrAssign_H(&a,"abcdfrHjk");
58     StrAssign_H(&b,"frH");
59     printf("BF算法的匹配结果%d\n",BF_Index(&a,&b,2));
60     printf("KMP算法的匹配结果%d",KMP_Index(&a,&b,2));
61 }

 1 #ifndef SEQSTRING_H_INCLUDED
 2 #define SEQSTRING_H_INCLUDED
 3 
 4 /*****************************
 5 *project    :数据结构第四章案例
 6 *function   :串的顺序结构实现
 7 *Description:
 8 *Author        :中子
 9 *****************************
10 *copyright:2019.3.5 by UZT
11 ****************************/
12 #include "StatusLib.h"
13 
14 /*
15 //不推荐定长方式，浪费空间
16 #define MAX_SIZE 1024
17 typedef struct{
18     char [MAX_SIZE + 1];//+1 是因为字符串有\0
19     int length;
20 }SString;
21 */
22 
23 /** 串的堆式顺序存储结构 */
24 typedef struct{
25     char * ch;  //空串使得ch = NULL;
26     int length;
27 }HString;
28 
29 /** 初始化 */
30 void InitString_HeapString(HString * str);
31 
32 /** 给串赋值 */
33 Status StrAssign_H(HString * str,char * chars);
34 
35 /** 打印字符串 */
36 void PrintH(HString * str);
37 
38 /** 将SrcStr复制到destStr */
39 Status StrCopy_H(HString * destStr,HString * srcStr);
40 
41 /** 是否为空 */
42 Status IsEmpty_H(HString * str);
43 
44 /** 比较两个堆字符的大小，str1 > str2返回正数，str1 = str2返回0，str1 < str2返回负数 */
45 Status StrCompare(HString * deatStr,HString * srcStr);
46 
47 /** 连接str1,str2两个字符串 */
48 Status Concac_H(HString* str3,HString * str1,HString * str2);
49 
50 /** 截取从pos位置处截取len长度字符串到串destStr */
51 Status SubString_H(HString * destStr,HString * str,int pos,int len);
52 
53 /** 返回子串str2在父串str1中的位置 */
54 int Index_H(HString * str1,HString * str2,int pos);
55 
56 /** 从pos位置处删除长度len */
57 Status StrDelete_H(HString * str,int pos,int len);
58 
59 /** 向插入位置插入串insertStr */
60 Status StrInsert_H(HString * str,int pos,HString * insertStr);
61 
62 /** 替换 */
63 Status Replace_H(HString * str,HString oldStr,HString newStr);
64 
65 /** 清空 */
66 Status ClearString(HString * str);
67 
68 /** 使用BF（暴风）算法返回主串中的位置*/
69 int BF_Index(HString * parent,HString * child,int pos);
70 
71 /** 返回next数组(部分匹配表)*/
72 void Get_Next(HString child,int*next);
73 
74 /** 使用KMP算法返回主串中的位置*/
75 int KMP_Index(HString * parent,HString * child,int pos);
76 
77 #endif // SEQSTRING_H_INCLUDED

  1 #include "SeqString.h"
  2 
  3 /** 初始化 */
  4 void InitString_HeapString(HString * str)
  5 {
  6     str -> ch = NULL;
  7     str -> length = 0;
  8 }
  9 
 10 /** 给串赋值 */
 11 Status StrAssign_H(HString * str,char * chars)
 12 {
 13     int len = strlen(chars);
 14     if(!len)
 15     {
 16         return ERROR;
 17     }
 18     InitString_HeapString(str);
 19     str -> ch = (char*)malloc(len * sizeof(char));//乘以
 20     if(!str->ch)
 21     {
 22         exit(OVERFLOW);
 23     }
 24     for(int i = 0;i < len;i++)
 25     {
 26         str -> ch[i] = chars[i];
 27     }
 28     str -> length = len;
 29     return OK;
 30 }
 31 
 32 /** 打印字符串 */
 33 void PrintH(HString * str)
 34 {
 35     if(str -> length == 0 || !str -> ch)
 36     {
 37         printf("字符串为空!");
 38         return;
 39     }
 40     for(int i = 0;i < str -> length;i++)
 41     {
 42         printf("%c",str -> ch[i]);
 43     }
 44 
 45 }
 46 
 47 /** 将SrcStr复制到destStr */
 48 Status StrCopy_H(HString * destStr,HString * srcStr)
 49 {
 50     if(IsEmpty_H(srcStr))
 51     {
 52         printf("复制的字符不能为空！");
 53         return ERROR;
 54     }
 55     destStr -> ch = (char*)malloc(sizeof(char) * (srcStr -> length));
 56     if(!destStr -> ch) exit(OVERFLOW);
 57     for(int i = 0;i < srcStr -> length;i++)
 58     {
 59         destStr -> ch[i] = srcStr -> ch[i];
 60     }
 61     destStr -> length = srcStr -> length;
 62     return OK;
 63 }
 64 
 65 /** 是否为空 */
 66 Status IsEmpty_H(HString * str)
 67 {
 68     if(str -> length == 0 || !str)
 69         return TRUE;
 70     return FALSE;
 71 }
 72 
 73 /** 比较两个堆字符的大小，str1 > str2返回正数，str1 = str2返回0，str1 < str2返回负数 */
 74 Status StrCompare(HString * deatStr,HString * srcStr)
 75 {
 76     for(int i = 0;i < deatStr -> length && i < srcStr -> length;i++)
 77     {
 78         //字符串不同比较ASCLL码
 79         if(deatStr -> ch[i] != srcStr -> ch[i])
 80             return deatStr -> ch[i] - srcStr -> ch[i];
 81     }
 82     //字符串相同，比较长度
 83     return deatStr -> length - srcStr -> length;
 84 }
 85 /** 连接str1,str2两个字符串 */
 86 Status Concac_H(HString * str3,HString * str1,HString * str2)
 87 {
 88     InitString_HeapString(str3);
 89     str3 -> length = str1 -> length + str2 -> length;
 90     str3 -> ch = (char*)malloc(str3 -> length * sizeof(char));
 91     if(!str3) exit(OVERFLOW);
 92     for(int i = 0;i < str1 -> length;i++)
 93     {
 94         str3 -> ch[i] = str1 -> ch[i];
 95     }
 96     for(int i = 0;i < str2 -> length;i++)
 97     {
 98         str3 -> ch[i + str1 -> length] = str2 -> ch[i];
 99     }
100     return OK;
101 }
102 
103 /** 截取从pos位置处截取len长度字符串到串destStr */
104 Status SubString_H(HString * destStr,HString * str,int pos,int len)
105 {
106     InitString_HeapString(destStr);
107     if(IsEmpty_H(str))
108         return ERROR;
109     if(pos < 1 || pos > str -> length || len < 0 || pos + len - 1 > str -> length)
110         return ERROR;
111     destStr -> ch = (char*)malloc(len * sizeof(char));
112     if(!destStr -> ch) exit(OVERFLOW);
113     destStr -> length = len;
114     for(int i = 0;i < len;i++)
115     {
116         destStr -> ch[i] = str -> ch[pos - 1 + i];
117     }
118     return OK;
119 }
120 
121 /** 返回从pos位置开始子串str2在父串str1中的位置 */
122 int Index_H(HString * str1,HString * str2,int pos)
123 {
124     if(pos == 0) return 0;
125     HString * substr = (HString *)malloc(sizeof(HString));
126     int i = pos;
127     while(i + str2 -> length - 1 <= str1 -> length)
128     {
129         SubString_H(substr,str1,i,str2 -> length);
130         if(StrCompare(substr,str2) != EQ)
131         {
132             i++;
133         }
134         else{
135             return i;
136         }
137     }
138     free(substr);
139     return 0;
140 }
141 /** 从pos位置处删除长度len */
142 Status StrDelete_H(HString * str,int pos,int len)
143 {
144     if(IsEmpty_H(str)) return ERROR;
145     if(pos < 1 || pos + len - 1 > str -> length || len < 0)
146         return ERROR;
147     for(int i = pos - 1;i + len < str -> length;i++)
148     {
149         str -> ch[i] = str -> ch[i +len];
150     }
151     str -> length -= len;
152     //从新分配空间
153     str -> ch = (char*)realloc(str -> ch,str -> length * sizeof(char));
154     return OK;
155 }
156 
157 /** 向插入位置插入串insertStr */
158 Status StrInsert_H(HString * str,int pos,HString * insertStr)
159 {
160     if(IsEmpty_H(str)) return ERROR;
161     if(pos < 1 || pos > str -> length + 1)
162     {
163         return ERROR;
164     }
165     str -> ch = (char*)realloc(str -> ch,(str -> length + insertStr -> length) * sizeof(char));
166     if(!str -> ch) return OVERFLOW;
167     //为插入腾出位置
168     for(int i = str -> length - 1;i > pos - 1;i--)
169     {
170         str -> ch[i+insertStr->length] = str -> ch[i];
171     }
172     for(int i = 0;i < insertStr -> length;i++)
173     {
174         str -> ch[pos - 1 + i] = insertStr -> ch[i];
175     }
176     str -> length += insertStr -> length;
177     return OK;
178 }
179 
180 /** 替换 */
181 Status Replace_H(HString * str,HString oldStr,HString newStr)
182 {
183     if(IsEmpty_H(str)) return ERROR;
184     int pos = Index_H(str,&oldStr,1);
185     while(pos != 0)
186     {
187         StrDelete_H(str,pos,oldStr.length);
188         StrInsert_H(str,pos,&newStr);
189         pos += newStr.length;
190         pos = Index_H(str,&oldStr,pos);
191     }
192     return OK;
193 }
194 
195 /** 清空 */
196 Status ClearString(HString * str)
197 {
198     if(str -> ch){
199         free(str -> ch);
200         str -> ch = NULL;
201     }
202     str -> length = 0;
203     return OK;
204 }
205 
206 /** 使用BF（暴风）算法返回主串中的位置*/
207 int BF_Index(HString * parent,HString * child,int pos)
208 {
209     int i = pos;//用于主串的起始位置
210     int j = 1;  //用于子串的起始位置
211     while(i <= parent -> length && j <= child -> length)
212     {
213         if(parent -> ch[i - 1] == child -> ch[j - 1])
214         {
215             i++;
216             j++;
217         }
218         else
219         {
220             i = i - j + 2;//回溯到上次匹配的首位的下一位
221             j = 1;        //j回到子串的第一个位置
222         }
223     }
224     if(j > child -> length)
225         return i - child -> length;
226     return 0;
227 }
228 
229 /** 返回next数组(部分匹配表)*/
230 void Get_Next(HString child,int*next)
231 {
232     int i = 0;
233     int j = -1;
234     next[0] = -1;
235     while(i < child.length)
236     {
237         if(j == -1 || child.ch[i] == child.ch[j])
238         {
239             i++;
240             j++;
241             next[i] = j;
242         }
243         else
244         {
245             j = next[j];
246         }
247     }
248 }
249 
250 /** 使用KMP算法返回主串中的位置*/
251 int KMP_Index(HString * parent,HString * child,int pos)
252 {
253     int next[255];
254     Get_Next(*child,next);
255     int i = pos - 1;
256     int j = 0;
257     while(i < parent -> length && j < child -> length)
258     {
259         if(j == -1 || parent->ch[i] == child->ch[j])
260         {
261             i++;
262             j++;
263         }
264         else
265         {
266             j = next[j];
267         }
268     }
269     if(j == child->length)
270     {
271         return(i+1-j);
272     }
273     return 0;
274 }

 1 #ifndef STATUSLIB_H_INCLUDED
 2 #define STATUSLIB_H_INCLUDED
 3 
 4 /*****************************
 5 *project    :数据结构第四章案例
 6 *function   :相关状态码以及宏函数的定义
 7 *Description:
 8 *Author        :中子
 9 *****************************
10 *copyright:2019.3.5 by UZT
11 ****************************/
12 
13 #include <stdio.h>
14 #include <stdlib.h>
15 #include <string.h>
16 
17 /** 状态码 */
18 #define OK 1
19 #define ERROR 0
20 #define TRUE 1
21 #define FALSE 0
22 #define EQ 0        //=
23 #define GT 1        //great than >
24 #define LT -1       //less than  <
25 #ifndef _STATUS_H_      //如果系统中已经有了以下状态码的定义，就不再定义了
26     #define OVERFLOW -2 //堆栈上溢 超过所能表示的最大正数
27     #define UNDERFLOW -1//堆栈下溢 超过所能表示的最小负数
28 #endif // _STATUS_H_
29 
30 typedef int Status;     //自定义一个状态码类型
31 
32 
33 
34 #endif // STATUSLIB_H_INCLUDED