数据结构——串的相关算法实现

数据结构——串的相关算法实现

顺序串的插入函数实现

在进行顺序串的插入时，插入pos将串分为两个部分（假设为A、B,长度为LA、LB）及待插入部分（假设为C，长度为LC）,则串由插入前的AB变为ACB,由于是顺序串，插入会引起元素的移动。可能会出现以下的三种情况：

  • ①插入后串长度（LA+LC+LB）<=MAXLEN,则将B后移LC个元素位置，再将C插入；
  • ②插入后串长度 >=MAXLEN 且 pos+LC <=MAXLEN,则 B 后移时会有部分字符被舍弃;
  • ③插入后串长度>MAXLEN 且 pos+LC > MAXLEN，则 B 的全部字符被舍弃（不需要后移），并且C在插入时也有部分字符被舍弃。

代码实现

#include
 
#define MAX_SIZE 128
 
typedef struct
{
    char ch[MAX_SIZE];
    int last;
}string;
 
void init_str(string * s, int max)
{
    int i;
 
    for(i = 0; i < max; i++)
        s->ch[i] = 0;//而谁的 ASCII 码对应的是 整型的0呢？是字符'\0'
    s->last = 0;
}
 
void create_str(string * s, char * a, int n)
{
    int i=0; 
    for(;i < n; i++)
        s->ch[i] = a[i];
 
    s->ch[i+1] = '\0';
    s->last = n;
    printf("你输入的字符串为:\n");
    printf("%s\n",s->ch);
}
 
void insert_str(string * s,char * substr, int len, int pos)
{
    int i;
 
    if(pos < 0 || pos >= MAX_SIZE)
    {
        printf("输入的位置不合理!\n");
        return;
    }
 
    if (s->last + len >= MAX_SIZE) {
        printf("Can't insert, new string too long!\n");
        return;
    }
 
    if (pos >= s->last) {    /* 若插入的位置在last之后*/
        for (i = 0; i < len; i++)
            s->ch[s->last+i] = substr[i];//把新插入的串从s串的组后开始插入 
        s->ch[s->last+i] = 0;//插入新串之后，字符串的最末尾'\0' ,0 是'\0' 的 ASCII 
        puts(s->ch);
        s->last += len;
    } else {    /* 若插入的位置在ch内*/
        for (i = 0; i < len; i++)
            s->ch[pos+len+i] = s->ch[pos+i];//在没有插入新的串之前把s串分2部分，然后把后面部分整体向后移动len个长度
											//即，给即将要插入的串“腾空 ” 
 
        for (i = 0; i < len; i++)
            s->ch[pos+i] = substr[i]; //把新的串插入到刚刚腾出来的地方 
        s->ch[s->last+len] = 0; //插入后的“串”已经确定，改变了最后'/0'位置 
        s->last += len; //串的最大长度也重新确定 即，s->last = s->last+len 
    }
}
int main()
{
    string s;
    int pos, i;
    char a[80],b[80];
 
    init_str(&s, MAX_SIZE);
    printf("请输入字符串:\n");
    scanf("%s",a);
 
    /* 遍历整个字符串，并把a[]中的字符存在s中，长度为i ,然后输出*/
    for(i = 0; a[i]; i++)//for(i=0;a[i]！='＼0';i++) 后者这个准确些 
        ;
    create_str(&s, a, i);// 
    printf("请输入你要插入的字符串:\n");
    scanf("%s", b);
 
    for(i = 0; b[i]; i++)
        ;
    printf("请输入你要插入的位置:\n");
    scanf("%d",&pos);
    insert_str(&s, b, i, pos);//找到原来的串“s”,把b[]中的字符存进去，新插入的字符串的长度为i，插入的
	                           // 位置为pos
								 
    printf("新的字符串为：\n");
    printf("%s\n",s.ch);//输出插入后 所组成的 新串 
    return 0;
}

串的删除函数实现

指定要删除的位置，和从此位置要删除的字符的长度，实现删除字符串的删除操作。

代码实现

#include
 
#define MAX_SIZE 128
 
typedef struct
{
    char ch[MAX_SIZE];
    int last;
}string;
 
void init_str(string * s, int max)
{
    int i;
 
    for(i = 0; i < max; i++)
        s->ch[i] = 0;//而谁的 ASCII 码对应的是 整型的0呢？是字符'\0'
    s->last = 0;
}
 
void create_str(string * s, char * a, int n)
{
    int i=0; 
    for(;i < n; i++)
        s->ch[i] = a[i];
 
    s->ch[i+1] = '\0';
    s->last = n;
    printf("你输入的字符串为:\n");
    printf("%s\n",s->ch);
}
 

//顺序串的删除函数

void StrDelete(string * s,int pos,int len)
{
	int i;
	if(pos<0||pos>(s->last-len))
		{
			printf("删除参数不合法！");
			return; 
		}
	for(i=pos+len;ilast;i++)
	{
		s->ch[i-len] = s->ch[i];
	}
	s->ch[s->last-len] = 0;
	s->last = s->last - len;
}


 
int main()
{
    string s;
    int pos, i,n;
    char a[80];
 
    init_str(&s, MAX_SIZE);
    printf("请输入字符串:\n");
    scanf("%s",a);
 
   for(i = 0; a[i]; i++)//for(i=0;a[i]！='＼0';i++) 后者这个准确些 
        ;
    create_str(&s, a, i);// 
    
	                           
	printf("请输入要删除的位置 及字符串长度：");
	scanf("%d %d",&pos,&n);
	StrDelete(&s,pos,n);
								 
    printf("新的字符串为：\n");
    printf("%s\n",s.ch);//输出插入后 所组成的 新串 
    return 0;
}

串的比较函数实现

串的比较,即对两个字符串进行比较（ascii）在本例中，若串s和相等，则返回0，若s>t则返回正数，反之则返回负数。

代码实现

#include
 
#define MAX_SIZE 128
 
typedef struct
{
    char ch[MAX_SIZE];
    int last;
}string;
 
void init_str(string * s, int max)
{
    int i;
 
    for(i = 0; i < max; i++)
        s->ch[i] = 0;//而谁的 ASCII 码对应的是 整型的0呢？是字符'\0'
    s->last = 0;
}
 
void create_str(string * s, char * a, int n)
{
    int i=0; 
    for(;i < n; i++)
        s->ch[i] = a[i];
 
    s->ch[i+1] = '\0';
    s->last = n;
    printf("你输入的字符串为:\n");
    printf("%s\n",s->ch);
}
 


//串比较函数

int StrCompare(string s,string t)
{
	/*若串s和t相等则返回0，若s>t则返回正数；若s

串的简单模式匹配BF算法

简单的模式匹配算法是一种带回溯的匹配算法，算法的基本思想这里不再进行描述，可以在网上或书上找到很好的答案。这个算法时间复杂度较高。

代码实现

/*串的简单模式匹配函数*/

#include
 
#define MAX_SIZE 128
 
typedef struct
{
    char ch[MAX_SIZE];
    int last;//串的长度 
}string;
 
void init_str(string * s, int max)
{
    int i;
 
    for(i = 0; i < max; i++)
        s->ch[i] = 0;//而谁的 ASCII 码对应的是 整型的0呢？是字符'\0'
    s->last = 0;
}
 
void create_str(string * s, char * a, int n)
{
    int i=0; 
    for(;i < n; i++)
        s->ch[i] = a[i];
 
    s->ch[i+1] = '\0';
    s->last = n;
    printf("你输入的字符串为:\n");
    printf("%s\n",s->ch);
}
 


//顺序串的基本匹配算法

void StrIndex (string s,int pos,string t)
{
	/*求从主串的下标pos起....*/
	int i,j,start;
	if(t.last == 0)
		printf("匹配成功！");
	 start = pos;
	 i = start;//主串不一定从索引为0的字符开始，具体位置又客户指定 
	 j = 0;//模式串从索引0开始 
	 while(i=t.last)
	 	printf("匹配成功！匹配成功的位置索引为%d",start);
	  else
	 	printf("匹配失败！"); 
	
}


 
int main()
{
    string s,t;
    int pos,i;
    int m;
    char a[80];
    char b[80];
 
    init_str(&s, MAX_SIZE);
    printf("请输入字符串1:\n");
    scanf("%s",a);
    printf("请输入字符串2:\n");
    scanf("%s",b);
 
   for(i = 0; a[i]; i++)//for(i=0;a[i]！='＼0';i++) 后者这个准确些 
        ;
   create_str(&s, a, i);// 
   for(i = 0; b[i]; i++)//for(i=0;bi]！='＼0';i++) 后者这个准确些 
        ;
    
    create_str(&t, b, i);
                
	StrIndex (s,0,t);
								 
    
    return 0;
}

串的模式匹配改进的KMP算法

KMP算法的效率比Bf算法是要快的，具体的算法不再描述，这里只是简单给出相关代码实现。具体算法实现的内容可以参考课本和网上的解释。

代码实现

/*串的KMP匹配函数 */
/*http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html*/
/*上面的是对KMF算法的讲解，我个人觉得写的很清晰了emmmmm*/ 

#include
 
#define MAX_SIZE 128
 
typedef struct
{
    char ch[MAX_SIZE];
    int last;//串的长度 
}string;
 
void init_str(string * s, int max)
{
    int i;
 
    for(i = 0; i < max; i++)
        s->ch[i] = 0;//而谁的 ASCII 码对应的是 整型的0呢？是字符'\0'
    s->last = 0;
}
 
void create_str(string * s, char * a, int n)
{
    int i=0; 
    for(;i < n; i++)
        s->ch[i] = a[i];
 
    s->ch[i+1] = '\0';
    s->last = n;
    printf("你输入的字符串为:\n");
    printf("%s\n",s->ch);
}
 


//顺序串的基KMP算法

void Index_KMP(string s,int pos,string t)
{
	int i,j;
	int next[MAX_SIZE];
	i = pos;
	j = 1;//规定若指向了空格的话就是0，所以这里从1开始 
	while(i=t.last)
	 	printf("匹配成功！匹配成功的位置索引为%d",i-j);//i是模式串移动后“最后”的位置索引， 
	else                                              //如果想要开始索引，减去“移动的块的长度就可以了” 
	 	printf("匹配失败！"); 

}


 
int main()
{
    string s,t;
    int pos,i;
    int m;
    char a[80];
    char b[80];
 
    init_str(&s, MAX_SIZE);
    printf("请输入字符串1:\n");
    
    printf("请输入字符串2:\n");
    scanf("%s",b);
 
   for(i = 0; a[i]; i++)//for(i=0;a[i]！='＼0';i++) 后者这个准确些 
        ;
   create_str(&s, a, i);// 
   for(i = 0; b[i]; i++)//for(i=0;bi]！='＼0';i++) 后者这个准确些 
        ;
    
    create_str(&t, b, i);
                
	Index_KMP (s,0,t);
								 
    
    return 0;
}

参考文献

  • 数据结构-用C语言描述（第二版）[耿国华]
实验室

相关

Jupyter 实验室中的 GPU 仪表板

实验室管理系统

iOS逆向工程【From腾讯玄武实验室】

痛心：实验室服务器被挖矿怎么办？

实验室学习记录

有来实验室|第一篇：Seata1.5.2版本部署和开源全栈商城订单支付业务实战

标签