数据结构串(顺序存储)的基本操作

柔光的暖阳◎ 2022-09-19 01:30 200阅读 0赞

#include <stdio.h>
    
    #define OK        1
    #define ERROR     0
    #define TRUE      1
    #define FALSE     0
    #define MAXSTRLEN 255
    
    typedef unsigned char String[MAXSTRLEN+1];
    
    
    int StrAssign(String &S, char *str)
    {
    	int i,len;
    	char *p;
    	for (len = 0, p = str; *p != '\0'; len++,p++);
    	if (len == 0)
    	{
    		S[0] = 0;
    	}
    	else
    	{
    		for (i=0; i<len;i++)
    		{
    			S[i+1] = str[i];
    		}
    		S[0] = len;
    	}
    	return OK;
    }
    
    void StrCopy(String &S,String T)
    {
    	if (T[0] == 0)
    	{
    		S[0] = 0;
    	}
    	else
    	{
    		int i;
    		for (i=1;i<=T[0]; i++)
    		{
    			S[i] = T[i];
    		}
    		S[0] = T[0];
    	}
    }
    
    int StrEmpty(String T)
    {
    	if (T[0] == 0)
    	{
    		return OK;
    	}
    	return ERROR;
    }
    
    int StrLength(String T)
    {
    	return T[0];
    }
    
    void ClearString(String &T)
    {
    	T[0] = 0;
    }
    
    int StrCompare(String S,String T)
    {
    	int i;
    	for (i=1; i<=S[0] && i<=T[0]; ++i)
    	{
    		if (S[i] != T[i])
    		{
    			return S[i] - T[i];
    		}
    	}
    	return S[0] - T[0];
    }
    
    int Concat(String &T,String S1,String S2)
    {
    	int uncut;
    	int i,j;
    	if (S1[0] + S2[0] <= MAXSTRLEN)
    	{
    		for (i=1; i<=S1[0]; i++)
    		{
    			T[i] = S1[i];
    		}
    		for (j=1;j<=S2[0];j++)
    		{
    			T[i+j-1] = S2[j];
    		}
    		T[0] = S1[0] + S2[0];
    		uncut = TRUE;
    	}
    	else if (S1[0] < MAXSTRLEN)
    	{
    		for (i=1; i<=S1[0]; i++)
    		{
    			T[i] = S1[i];
    		}
    		for (j=1; j<=MAXSTRLEN - S1[0]; j++)
    		{
    			T[i+j-1] = S2[j];
    		}
    		T[0] = MAXSTRLEN;
    		uncut = FALSE;
    	}
    	else
    	{
    		for (i=0; i<=MAXSTRLEN; i++)
    		{
    			T[i] = S1[i];
    		}
    		uncut = FALSE;
    	}
    	return uncut;
    }
     
    
    
    
    
    
    void Print_String(String S)
    {
    	if (S[0] == 0)
    	{
    		return;
    	}
    	else
    	{
    		int i;
    		for (i=1; i<=S[0]; i++)
    		{
    			printf("%c",S[i]);
    		}
    		printf("\n");
    	}
    }
    
    int SubString(String &Sub, String S, int pos, int len)
    {
    	int i;
    	if (pos < 1 || pos > S[0] || len < 0 || len > S[0] - pos + 1)
    	{
    		return ERROR;
    	}
    	if (!len)
    	{
    		Sub[0] = 0;
    	}
    	else
    	{
    		for (i=1; i<=len;i++)
    		{
    			Sub[i] = S[pos+i-1];
    		}
    		Sub[0] = len;
    	}
    	return OK;
    }
    
    
    int Index(String S,String T, int pos)
    {
    
    	if (pos > 0 && pos <= S[0] - T[0] + 1)
    	{
    		int n = S[0];
    		int m = T[0];
    		int i = pos;
    		String sub;
    		while (i<= n-m+1)
    		{
    			SubString(sub,S, i,m);
    			if (StrCompare(sub, T) != 0)
    			{
    				++i;
    			}
    			else
    			{
    				return i;
    			}
    		}
    	}
    	return 0;
    }
    
    void get_next(String T, int next[])
    {
    	int i = 1;
    	int j = 0;
    	next[1] = 0;
    	while (i<T[0])
    	{
    		if (j == 0 || T[i] == T[j])
    		{
    			++i;
    			++j;
    			next[i] = j;
    		}
    		else
    		{
    			j = next[j];
    		}
    	}
    }
    
    void get_nextval(String T, int nextval[])
    {
    	int i = 1;
    	int j = 0;
    	nextval[1] = 0;
    	while (i<T[0])
    	{
    		if (j == 0 || T[i] == T[j])
    		{
    			++i;
    			++j;
    			if (T[i] != T[j])
    			{
    				nextval[i] = j;
    			}
    			else
    			{
    				nextval[i] = nextval[j];
    			}
    
    		}
    		else
    		{
    			j = nextval[j];
    		}
    	}
    }
    
    int Index_KMP(String S, String T, int pos)
    {
    	int i = pos;
    	int j = 1;
    	int next[255];
    	get_next(T,next);
    	while (i<=S[0] && j <= T[0])
    	{
    		if (j == 0 || S[i] == T[j])
    		{
    			++i;
    			++j;
    		}
    		else
    		{
    			j = next[j];
    		}
    	}
    	if (j>T[0])
    	{
    		return i-T[0];
    	}
    	else
    		return 0;
    }
    
    int Index_KMP2(String S, String T, int pos)
    {
    	int i = pos;
    	int j = 1;
    	int nextval[255];
    	get_nextval(T,nextval);
    	while (i<=S[0] && j <= T[0])
    	{
    		if (j == 0 || S[i] == T[j])
    		{
    			++i;
    			++j;
    		}
    		else
    		{
    			j = nextval[j];
    		}
    	}
    	if (j>T[0])
    	{
    		return i-T[0];
    	}
    	else
    		return 0;
    }
    
    int main()
    {
    	String T,S,H;
    	char str[1000];
    	gets(str);
    	StrAssign(T,str);
    	Print_String(T);
    	gets(str);
    	StrAssign(S,str);
    	Print_String(S);
    	StrCopy(T,S);
    	Print_String(T);
    	Concat(H,S,T);
    	Print_String(H);
    	SubString(S,T,5,3);
    	Print_String(S);
    	printf("%d\n",Index(T,S,1));
    	printf("%d\n",Index_KMP(T,S,1));
    	printf("%d\n",Index_KMP2(T,S,1));
    
    
    	return 0;
    }