(C语言)串定长顺序存储实现(数据结构十二)

青旅半醒 2022-09-17 11:19 144阅读 0赞

1.数据类型定义

在代码中为了清楚的表示一些错误和函数运行状态，我们预先定义一些变量来表示这些状态。在head.h头文件中有如下定义：

//定义数据结构中要用到的一些变量和类型
    #ifndef HEAD_H
    #define HEAD_H
    
    #include <stdio.h>
    #include <malloc.h>
    #include <stdlib.h>
    #include <math.h>
    
    #define TRUE  1
    #define FALSE 0
    #define OK    1
    #define ERROR  0
    #define INFEASIBLE -1
    #define OVERFLOW   -2    //分配内存出错
    
    typedef int  Status;     //函数返回值类型
    typedef int  ElemType;   //用户定义的数据类型
    
    #endif

2.定义串数据结构

#define INIT_STRING_SIZE   100
    typedef unsigned char     String[INIT_STRING_SIZE+1] ;

3.串实现

String.h代码如下：

#ifndef STRING_H
    #define STRING_H
    
    #include "head.h"
    #include <string.h>
    
    #define INIT_STRING_SIZE   100
    
    typedef unsigned char     String[INIT_STRING_SIZE+1] ;
    
    Status StrAssign(String &S,char* ch){
    	S[0]=strlen(ch);                   //S[0]串的长度
    	if(S[0]>INIT_STRING_SIZE) return ERROR;
    	for(int i=1;i<=S[0];i++)
    		S[i]=ch[i-1];
    	return true;
    }
    
    Status StrCopy(String &S,String T){
    	for(int i=0;i<=T[0];i++)
    		S[i]=T[i];
    	return true;
    }
    
    Status StrEmpty(String S){
    	return S[0]==0;
    }
    
    
    Status StrCompare(String S,String T){
    	int n=S[0]<=T[0]?S[0]:T[0];
    	for (int i=1;i<=n;i++)
    	{
    		if(S[i]!=T[i]){
    			return S[i]-T[i];
    			break;
    		}
    		if(i==n){
    			return S[0]==T[0]?0:S[0]-T[0];
    		}
    	}
    }
    Status StrLength(String S){
    	return (int)S[0];
    }
    Status ClearString(String S){
    	S[0]=0;
    	return true;
    }
    Status StrConcat(String &S,String S1,String S2){
    	S[0]=S1[0]+S2[0];
    	if(S[0]>INIT_STRING_SIZE) return ERROR;
    	for(int i=1;i<=S1[0];i++)
    		S[i]=S1[i];
    	for(int j=1;j<=S2[0];j++)
    		S[S1[0]+j]=S2[j];
    	return true;
    }
    Status StrPrint(String S){
    	for(int i=1;i<=S[0];i++)
    		printf("%c",S[i]);
    	return true;
    }
    Status SubString(String &Sub,String S,int pos,int len){
    	if(pos<1 || pos+len-1>S[0]) return ERROR;
    	Sub[0]=len;
    	for (int i=1;i<=len;i++)
    		Sub[i]=S[pos+i-1];
    	return true;
    }
    Status Index(String S,String T,int pos){
    	if(pos>0 &&pos<S[0]){
    		int n=StrLength(S);
    		int m=StrLength(T);
    		for (int i=pos;i<=n-m+1;i++)
    		{
    			String sub;
    			SubString(sub,S,i,m);
    			if(StrCompare(sub,T)==0){
    				return i;
    				break;
    			}
    				
    		}
    	}
    	return 0;
    }
    
    
    Status StrInsert(String &S,int pos,String T){
    	if(pos<1 ||pos>StrLength(S)+1) return ERROR;
    	int m=T[0];
    	int n=S[0];
    
    	for (int i=n;i>=pos;i--)
    		S[i+m]=S[i];
    	for(int i=1;i<=m;i++)
    		S[i+pos-1]=T[i];
    	S[0]+=m;
    	return ERROR;
    
    }
    
    Status StrDelete(String &S,int pos,int len){
    	if(pos<1 ||pos+len>StrLength(S)+1) return ERROR;
    	for (int i=pos+len;i<=StrLength(S);i++)
    		S[i-len]=S[i];
    	S[0]-=len;
    	return OK;
    }
    Status DestroyString(String &S){
    	S[0]=0;
    	return OK;
    }
    
    Status Replace(String &S,String T,String V){
    
    	int n=StrLength(T);
    	int m=StrLength(V);
    	int index=Index(S,T,1);
    	while (index!=0)
    	{	
    		int k=StrLength(S);
    		StrDelete(S,index,n);
    		StrInsert(S,index,V);
    		index=Index(S,T,1);
    	}
    	return true;
    }
    
    #endif

4.串测试

#include "String.h"
    
    
    void main(){
    	String S;
    	String T;
    
    	StrAssign(S,"ab");
    	StrAssign(T,"ab");
    
    
    
    	printf("比较结果：%d ",StrCompare(S,T));
    	printf("\n长度：%d ",StrLength(S));
    
    	String S1;
    	StrConcat(S1,S,T);
    	printf("\nStrConcat测试：");
    	StrPrint(S1);
    
    	String Sub;
    	SubString(Sub,S1,2,2);
    	printf("\nSubString测试：");
    	StrPrint(Sub);
    
    	printf("\n位置：%d",Index(S,T,1));
    
    
    	String S2;
    	StrAssign(S2,"abcccabccaba");
    	String V;
    	printf("\n替换前：");
    	StrPrint(S2);
    	StrAssign(V,"XX");
    	Replace(S2,T,V);
    	printf("\n替换结果：");
    	StrPrint(S2);
    
    	StrInsert(S2,5,V);
    	printf("\n插入后：");
    	StrPrint(S2);
    
    	StrDelete(S2,1,2);
    	printf("\n删除后：");
    	StrPrint(S2);
    
    	DestroyString(S2);
    }

5. *测试结果*

比较结果：0
    长度：2
    StrConcat测试：abab
    SubString测试：ba
    位置：1
    替换前：abcccabccaba
    替换结果：XXcccXXccXXa
    插入后：XXccXXcXXccXXa
    删除后：ccXXcXXccXXa