数据结构串(链式存储)的基本操作

- 日理万妓 2022-09-19 01:30 171阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    
    #define OK          1
    #define ERROR       0
    #define OVERFLOW    -2
    
    typedef struct
    {
    	char *ch;
    	int length;
    }String;
    
    void Init_String(String &T)
    {
    	T.ch = NULL;
    	T.length = 0;
    }
    
    int StrAssign(String &T, char *chars)
    {
    	int i;
    	int len;
    	char *p = chars;
    	if (T.ch)
    	{
    		free(T.ch);
    	}
    	for (len = 0;*p != '\0'; ++len,++p);
    	if (!len)
    	{
    		T.ch = NULL;
    		T.length = 0;
    	}
    	else
    	{
    		T.ch = (char *)malloc(len * sizeof(char));
    		if (!T.ch)
    		{
    			exit(OVERFLOW);
    		}
    		for (i=0; i<len; i++)
    		{
    			T.ch[i] = chars[i];
    		}
    		T.length = len;
    	}
    	return OK;
    }
    
    void Print_String(String T)
    {
    	if (T.length == 0)
    	{
    		return;
    	}
    	else
    	{
    		int i;
    		for (i=0; i<T.length; i++)
    		{
    			printf("%c",T.ch[i]);
    		}
    	}
    	printf("\n");
    }
    
    int StrLength(String T)
    {
    	return T.length;
    }
    
    
    int ClearString(String T)
    {
    	if (!T.ch)
    	{
    		free(T.ch);
    		T.ch = NULL;
    	}
    	T.length = 0;
    	return OK;
    }
    
    int StrCompare(String S, String T)
    {
    	int i;
    	for (i=0; i<S.length && i < T.length; i++)
    	{
    		if (S.ch[i] != T.ch[i])
    		{
    			return S.ch[i] - T.ch[i];
    		}
    	}
    	return S.length - T.length ;
    }
    
    
    int Concat(String &T, String S1, String S2)
    {
    	int i,j;
    	if (T.ch)
    	{
    		free(T.ch);
    	}
    	T.ch = (char *)malloc((S1.length + S2.length) * sizeof(char));
    	if (!T.ch)
    	{
    		exit(OVERFLOW);
    	}
    	T.length = S1.length + S2.length;
    	for (i=0; i<S1.length ; i++)
    	{
    		T.ch[i] = S1.ch[i];
    	}
    	for (j=0; j<S2.length; j++)
    	{
    		T.ch[i+j] = S2.ch[j];
    	}
    	return OK;
    }
    
    int SubString(String &Sub, String S,int pos, int len)
    {
    	int i;
    	if (pos < 1 || pos > S.length || len < 0 || len > S.length - pos + 1)
    	{
    		return ERROR;
    	}
    	if (Sub.ch)
    	{
    		free(Sub.ch);
    	}
    	if (!len)
    	{
    		Sub.ch = NULL;
    		Sub.length = 0;
    	}
    	else
    	{
    		Sub.ch = (char *)malloc(len * sizeof(char));
    		if (!Sub.ch)
    		{
    			exit(OVERFLOW);
    		}
    		for (i=0; i<len; i++)
    		{
    			Sub.ch[i] = S.ch[pos+i-1];
    		}
    		Sub.length = len;
    	}
    	return OK;
    }
    
    
    int StrInsert(String &S, int pos, String T)
    {
    	int i;
    	if (pos < 1 || pos > S.length +1)
    	{
    		return ERROR;
    	}
    	if (T.length)
    	{
    		S.ch = (char *)realloc(S.ch,(S.length + T.length ) * sizeof(char));
    		if (!S.ch)
    		{
    			exit(OVERFLOW);
    		}
    		for (i=S.length-1;i >= pos -1; --i)
    		{
    			S.ch[i+T.length] = S.ch[i];
    		}
    		for (i=0; i<T.length ; i++)
    		{
    			S.ch[pos-1 + i] = T.ch[i];
    		}
    		S.length += T.length;
    	}
    	return OK;
    }
    
    
    int Index(String S, String T, int pos)
    {
    	int i = pos-1;
    	int j = 0;
    	if (pos < 0 || pos >= S.length)
    	{
    		return ERROR;
    	}
    	while (i<S.length && j < T.length)
    	{
    		if (S.ch[i] == T.ch[j])
    		{
    			++i;
    			++j;
    		}
    		else
    		{
    			i = i-j+1;
    			j = 0;
    		}
    	}
    	if (j == T.length)
    	{
    		return i - T.length + 1;
    	}
    	return 0;
    }
    
    void get_next(String T, int next[])
    {
    	int i = 0;
    	int j = 0;
    	next[0] = -1;
    	while (i<T.length)
    	{
    		if (j == -1 || T.ch[i] == T.ch[j])
    		{
    			++i;
    			++j;
    			next[i] = j;
    		}
    		else
    		{
    			j = next[j];
    		}
    	}
    }
    
    void get_nextval(String T, int nextval[])
    {
    	int i = 0;
    	int j = 0;
    	nextval[0] = -1;
    	while (i<T.length )
    	{
    		if (j == -1 || T.ch[i] == T.ch[j])
    		{
    			++i;
    			++j;
    			if (T.ch[i] != T.ch[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 = 0;
    	int next[255];
    	get_next(T,next);
    	while (i<S.length  && j <T.length )
    	{
    		if (j == -1 || S.ch[i] == T.ch[j])
    		{
    			++i;
    			++j;
    		}
    		else
    		{
    			j = next[j];
    		}
    	}
    	if (j>T.length )
    	{
    		return i-T.length + 1 ;
    	}
    	else
    		return 0;
    }
    
    int Index_KMP2(String S, String T, int pos)
    {
    	int i = pos;
    	int j = 0;
    	int nextval[255];
    	get_nextval(T,nextval);
    	while (i<S.length  && j <T.length )
    	{
    		if (j == -1 || S.ch[i] == T.ch[j])
    		{
    			++i;
    			++j;
    		}
    		else
    		{
    			j = nextval[j];
    		}
    	}
    	if (j>T.length)
    	{
    		return i-T.length + 1;
    	}
    	else
    		return 0;
    }
    
    
    
    int main()
    {
    	char chars[1000];
    	char s[1000];
    	String S,T,H;
    	Init_String(T);
    	Init_String(S);
    	Init_String(H);
    	gets(chars);
    	StrAssign(T,chars);
    	Print_String(T);
    	gets(s);
    	StrAssign(S,s);
    	Concat(H,T,S);
    	Print_String(H);
    	SubString(T,H,5,8);
    	Print_String(T);
    	StrInsert(T,3,H);
    	Print_String(T);
    	printf("%d\n",Index(T,H,0));
    	printf("%d\n",Index_KMP(T,H,0));
    	printf("%d\n",Index_KMP2(T,H,0));
    	return 0;
    }