- #include <stdio.h>
- #include <stdlib.h>
- #include "SeqString.h"
- void TestSeqString();
- void TestBF();
- void TestVirusDemo();
- int virus_check(HString parent,HString child);
- int main()
- {
- //TestSeqString();
- //TestBF();
- return 0;
- }
- void TestSeqString()
- {
- HString * str1 = (HString*)malloc(sizeof(HString));
- HString * str2 = (HString*)malloc(sizeof(HString));
- HString * str4 = (HString*)malloc(sizeof(HString));
- StrAssign_H(str1,"abcdfrhjk");
- PrintH(str1);
- printf("\n");
- printf("复制后:\n");
- StrCopy_H(str2,str1);
- PrintH(str2);
- printf("\n 比较:\n");
- printf("%d",StrCompare(str1,str2));
- printf("\n 合并:\n");
- HString * str3 = (HString*)malloc(sizeof(HString));
- Concac_H(str3,str1,str2);
- PrintH(str3);
- printf("\n 截取后:\n");
- SubString_H(str3,str1,1,3);
- PrintH(str3);
- printf("\n 父子串匹配:\n");
- StrAssign_H(str4,"frh");
- printf("%d\n",Index_H(str1,str4,2));
- free(str1);
- free(str2);
- free(str3);
- free(str4);
- }
- void TestBF()
- {
- HString a;
- HString b;
- StrAssign_H(&a,"abcdfrHjk");
- StrAssign_H(&b,"frH");
- printf("BF 算法的匹配结果 %d\n",BF_Index(&a,&b,2));
- printf("KMP 算法的匹配结果 %d",KMP_Index(&a,&b,2));
- }
- main.c
- #ifndef SEQSTRING_H_INCLUDED
- #define SEQSTRING_H_INCLUDED
- /*****************************
- *project : 数据结构第四章案例
- *function : 串的顺序结构实现
- *Description:
- *Author : 中子
- *****************************
- *copyright:2019.3.5 by UZT
- ****************************/
- #include "StatusLib.h"
- /*
- // 不推荐定长方式, 浪费空间
- #define MAX_SIZE 1024
- typedef struct{
- char [MAX_SIZE + 1];//+1 是因为字符串有 \ 0
- int length;
- }SString;
- */
- /** 串的堆式顺序存储结构 */
- typedef struct{
- char * ch; // 空串使得 ch = NULL;
- int length;
- }HString;
- /** 初始化 */
- void InitString_HeapString(HString * str);
- /** 给串赋值 */
- Status StrAssign_H(HString * str,char * chars);
- /** 打印字符串 */
- void PrintH(HString * str);
- /** 将 SrcStr 复制到 destStr */
- Status StrCopy_H(HString * destStr,HString * srcStr);
- /** 是否为空 */
- Status IsEmpty_H(HString * str);
- /** 比较两个堆字符的大小, str1> str2 返回正数, str1 = str2 返回 0,str1 <str2 返回负数 */
- Status StrCompare(HString * deatStr,HString * srcStr);
- /** 连接 str1,str2 两个字符串 */
- Status Concac_H(HString* str3,HString * str1,HString * str2);
- /** 截取从 pos 位置处截取 len 长度字符串到串 destStr */
- Status SubString_H(HString * destStr,HString * str,int pos,int len);
- /** 返回子串 str2 在父串 str1 中的位置 */
- int Index_H(HString * str1,HString * str2,int pos);
- /** 从 pos 位置处删除长度 len */
- Status StrDelete_H(HString * str,int pos,int len);
- /** 向插入位置插入串 insertStr */
- Status StrInsert_H(HString * str,int pos,HString * insertStr);
- /** 替换 */
- Status Replace_H(HString * str,HString oldStr,HString newStr);
- /** 清空 */
- Status ClearString(HString * str);
- /** 使用 BF(暴风) 算法返回主串中的位置 */
- int BF_Index(HString * parent,HString * child,int pos);
- /** 返回 next 数组 (部分匹配表)*/
- void Get_Next(HString child,int*next);
- /** 使用 KMP 算法返回主串中的位置 */
- int KMP_Index(HString * parent,HString * child,int pos);
- #endif // SEQSTRING_H_INCLUDED
- SeqString.h
- #include "SeqString.h"
- /** 初始化 */
- void InitString_HeapString(HString * str)
- {
- str -> ch = NULL;
- str -> length = 0;
- }
- /** 给串赋值 */
- Status StrAssign_H(HString * str,char * chars)
- {
- int len = strlen(chars);
- if(!len)
- {
- return ERROR;
- }
- InitString_HeapString(str);
- str -> ch = (char*)malloc(len * sizeof(char));// 乘以
- if(!str->ch)
- {
- exit(OVERFLOW);
- }
- for(int i = 0;i <len;i++)
- {
- str -> ch[i] = chars[i];
- }
- str -> length = len;
- return OK;
- }
- /** 打印字符串 */
- void PrintH(HString * str)
- {
- if(str -> length == 0 || !str -> ch)
- {
- printf("字符串为空!");
- return;
- }
- for(int i = 0;i <str -> length;i++)
- {
- printf("%c",str -> ch[i]);
- }
- }
- /** 将 SrcStr 复制到 destStr */
- Status StrCopy_H(HString * destStr,HString * srcStr)
- {
- if(IsEmpty_H(srcStr))
- {
- printf("复制的字符不能为空!");
- return ERROR;
- }
- destStr -> ch = (char*)malloc(sizeof(char) * (srcStr -> length));
- if(!destStr -> ch) exit(OVERFLOW);
- for(int i = 0;i <srcStr -> length;i++)
- {
- destStr -> ch[i] = srcStr -> ch[i];
- }
- destStr -> length = srcStr -> length;
- return OK;
- }
- /** 是否为空 */
- Status IsEmpty_H(HString * str)
- {
- if(str -> length == 0 || !str)
- return TRUE;
- return FALSE;
- }
- /** 比较两个堆字符的大小, str1> str2 返回正数, str1 = str2 返回 0,str1 <str2 返回负数 */
- Status StrCompare(HString * deatStr,HString * srcStr)
- {
- for(int i = 0;i < deatStr -> length && i <srcStr -> length;i++)
- {
- // 字符串不同比较 ASCLL 码
- if(deatStr -> ch[i] != srcStr -> ch[i])
- return deatStr -> ch[i] - srcStr -> ch[i];
- }
- // 字符串相同, 比较长度
- return deatStr -> length - srcStr -> length;
- }
- /** 连接 str1,str2 两个字符串 */
- Status Concac_H(HString * str3,HString * str1,HString * str2)
- {
- InitString_HeapString(str3);
- str3 -> length = str1 -> length + str2 -> length;
- str3 -> ch = (char*)malloc(str3 -> length * sizeof(char));
- if(!str3) exit(OVERFLOW);
- for(int i = 0;i <str1 -> length;i++)
- {
- str3 -> ch[i] = str1 -> ch[i];
- }
- for(int i = 0;i <str2 -> length;i++)
- {
- str3 -> ch[i + str1 -> length] = str2 -> ch[i];
- }
- return OK;
- }
- /** 截取从 pos 位置处截取 len 长度字符串到串 destStr */
- Status SubString_H(HString * destStr,HString * str,int pos,int len)
- {
- InitString_HeapString(destStr);
- if(IsEmpty_H(str))
- return ERROR;
- if(pos <1 || pos> str -> length || len <0 || pos + len - 1> str -> length)
- return ERROR;
- destStr -> ch = (char*)malloc(len * sizeof(char));
- if(!destStr -> ch) exit(OVERFLOW);
- destStr -> length = len;
- for(int i = 0;i <len;i++)
- {
- destStr -> ch[i] = str -> ch[pos - 1 + i];
- }
- return OK;
- }
- /** 返回从 pos 位置开始子串 str2 在父串 str1 中的位置 */
- int Index_H(HString * str1,HString * str2,int pos)
- {
- if(pos == 0) return 0;
- HString * substr = (HString *)malloc(sizeof(HString));
- int i = pos;
- while(i + str2 -> length - 1 <= str1 -> length)
- {
- SubString_H(substr,str1,i,str2 -> length);
- if(StrCompare(substr,str2) != EQ)
- {
- i++;
- }
- else{
- return i;
- }
- }
- free(substr);
- return 0;
- }
- /** 从 pos 位置处删除长度 len */
- Status StrDelete_H(HString * str,int pos,int len)
- {
- if(IsEmpty_H(str)) return ERROR;
- if(pos <1 || pos + len - 1> str -> length || len <0)
- return ERROR;
- for(int i = pos - 1;i + len < str -> length;i++)
- {
- str -> ch[i] = str -> ch[i +len];
- }
- str -> length -= len;
- // 从新分配空间
- str -> ch = (char*)realloc(str -> ch,str -> length * sizeof(char));
- return OK;
- }
- /** 向插入位置插入串 insertStr */
- Status StrInsert_H(HString * str,int pos,HString * insertStr)
- {
- if(IsEmpty_H(str)) return ERROR;
- if(pos <1 || pos> str -> length + 1)
- {
- return ERROR;
- }
- str -> ch = (char*)realloc(str -> ch,(str -> length + insertStr -> length) * sizeof(char));
- if(!str -> ch) return OVERFLOW;
- // 为插入腾出位置
- for(int i = str -> length - 1;i> pos - 1;i--)
- {
- str -> ch[i+insertStr->length] = str -> ch[i];
- }
- for(int i = 0;i <insertStr -> length;i++)
- {
- str -> ch[pos - 1 + i] = insertStr -> ch[i];
- }
- str -> length += insertStr -> length;
- return OK;
- }
- /** 替换 */
- Status Replace_H(HString * str,HString oldStr,HString newStr)
- {
- if(IsEmpty_H(str)) return ERROR;
- int pos = Index_H(str,&oldStr,1);
- while(pos != 0)
- {
- StrDelete_H(str,pos,oldStr.length);
- StrInsert_H(str,pos,&newStr);
- pos += newStr.length;
- pos = Index_H(str,&oldStr,pos);
- }
- return OK;
- }
- /** 清空 */
- Status ClearString(HString * str)
- {
- if(str -> ch){
- free(str -> ch);
- str -> ch = NULL;
- }
- str -> length = 0;
- return OK;
- }
- /** 使用 BF(暴风) 算法返回主串中的位置 */
- int BF_Index(HString * parent,HString * child,int pos)
- {
- int i = pos;// 用于主串的起始位置
- int j = 1; // 用于子串的起始位置
- while(i <= parent -> length && j <= child -> length)
- {
- if(parent -> ch[i - 1] == child -> ch[j - 1])
- {
- i++;
- j++;
- }
- else
- {
- i = i - j + 2;// 回溯到上次匹配的首位的下一位
- j = 1; //j 回到子串的第一个位置
- }
- }
- if(j> child -> length)
- return i - child -> length;
- return 0;
- }
- /** 返回 next 数组 (部分匹配表)*/
- void Get_Next(HString child,int*next)
- {
- int i = 0;
- int j = -1;
- next[0] = -1;
- while(i <child.length)
- {
- if(j == -1 || child.ch[i] == child.ch[j])
- {
- i++;
- j++;
- next[i] = j;
- }
- else
- {
- j = next[j];
- }
- }
- }
- /** 使用 KMP 算法返回主串中的位置 */
- int KMP_Index(HString * parent,HString * child,int pos)
- {
- int next[255];
- Get_Next(*child,next);
- int i = pos - 1;
- int j = 0;
- while(i < parent -> length && j <child -> length)
- {
- if(j == -1 || parent->ch[i] == child->ch[j])
- {
- i++;
- j++;
- }
- else
- {
- j = next[j];
- }
- }
- if(j == child->length)
- {
- return(i+1-j);
- }
- return 0;
- }
- SeqString.c
- #ifndef STATUSLIB_H_INCLUDED
- #define STATUSLIB_H_INCLUDED
- /*****************************
- *project : 数据结构第四章案例
- *function : 相关状态码以及宏函数的定义
- *Description:
- *Author : 中子
- *****************************
- *copyright:2019.3.5 by UZT
- ****************************/
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- /** 状态码 */
- #define OK 1
- #define ERROR 0
- #define TRUE 1
- #define FALSE 0
- #define EQ 0 //=
- #define GT 1 //great than>
- #define LT -1 //Less than <
- #ifndef _STATUS_H_ // 如果系统中已经有了以下状态码的定义, 就不再定义了
- #define OVERFLOW -2 // 堆栈上溢 超过所能表示的最大正数
- #define UNDERFLOW -1// 堆栈下溢 超过所能表示的最小负数
- #endif // _STATUS_H_
- typedef int Status; // 自定义一个状态码类型
- #endif // STATUSLIB_H_INCLUDED
- StatusLib.h
来源: http://www.bubuko.com/infodetail-2987134.html