數據結構——定長串操作

首先我們必須了解的定長串的相關名詞： 串   長：是指字符串的長度，如：“abcde”長度為5，“PI”長度為2   串相等：兩個字符串的長度和內容均相等，如：“abcde”和“abcde”   空格串：字符串由一個或多個空格組成，空格串不是空串，空格串有長度，如：“   ”   空   串：字符串長度為零，如：“”   子   串：一個串的某一部分，如：“abcde”的“a”，“bc”，“bcd”等都是子串   [cpp]   //-----頭文件------   #include <stdio.h>   #include <stdlib.h>   #include <stdbool.h>      //------宏定義------   #define      MAXSTRLEN         255   #define      OVERFLOW          -2   #define      TURE              1   #define      ERROR             0      //-------類型名替換--------   typedef unsigned char SString[MAXSTRLEN+1];   typedef int Bool;      //-----函數列表-----   Bool StrAssign(SString *T,char *s);   Bool StrCopy(SString *T,SString S);   Bool StrEmpty(SString S);   Bool ClearString(SString *S);   int  StrCompare(SString S,SString T);   int  StrLength(SString S);   Bool Concat(SString *T,SString S1,SString S2);   Bool SubString(SString *Sub,SString S,int pos,int len);   Bool StrInsert(SString *S,int pos,SString T);   Bool StrDelete(SString *S,int pos,int len);   Bool Replace(SString *S,SString T,SString V);   Bool DestroyString(SString *S);   int  Index(SString S,SString T,int pos);   void StrOutput(SString S);      //-----主函數做替換測試------   int main()   {       SString t,*T=&t,s,*S=&s,s0,*S0=&s0;       int n;              //串初始化       StrAssign(T,"abcdedehdeklmdepqded");       StrAssign(S0,"de");       StrAssign(S,"$$$");              //串拷貝       StrCopy(T, s0);       if(StrEmpty(t))       {           printf("yes is empty!\n");       }       else       {           printf("non empty!\n");       }              //清空串       //ClearString(T);       if(StrEmpty(t))       {           printf("yes is empty!\n");       }       else       {           printf("non empty!\n");       }              //判斷兩個串是否相等       n = StrCompare(t, s0);       printf("The reasult is: %d\n", n);              //獲取串長       printf("The length is:%d\n", StrLength(t));              //串連接       Concat(S, t, s0);       StrOutput(s);              //獲取指定字串       SubString(S, t, 5, 5);       StrOutput(s);              //插入字串       StrInsert(T, 1, s0);       StrOutput(t);              //刪除字串       StrDelete(T, 5, 5);       StrOutput(*T);              //串替換       Replace(T,s0,s);       StrOutput(*T);              return 0;   }      //------生成一個其值等於字符串常量的串T------   Bool StrAssign(SString *T, char *s)   {       int i;       for(i=0; '\0'!=*s; s++,i++)       {           (*T)[i+1] = *s;       }       (*T)[0] = i;   //串第一個地址存放串長       return TURE;   }      //------復制串S到串T中,生成一個其值等於串S的串T------   Bool StrCopy(SString *T, SString S)   {       int i;       for(i=1; i<=S[0]; i++)       {           (*T)[i] = S[i];       }       (*T)[0] = S[0];       return TURE;   }      //-----判斷是否為空串,為空返回TURE,非空返回ERROR------   Bool StrEmpty(SString S)   {       return S[0]==0?TURE:ERROR;   }      //-----比較兩個串的大小------   //串S大於串T返回1,小於返回-1,等於返回0,錯誤返回-2   int StrCompare(SString S,SString T)   {       int i;       if(0==S[0] || 0==T[0])       {           return -2;       //不能返回ERROR,因為ERROR=0       }       for(i=1; i<=S[0]&&i<=T[0]; i++)       {           if(S[i]>T[i])           {               return 1;           }           else if(S[i]<T[i])           {               return -1;           }           else           {               continue;           }       }       if(S[0]==T[0])       {           return 0;       }       else if(S[0]>T[0])       {           return 1;       }       else       {           return -1;       }   }      //-----返回串長-----   int StrLength(SString S)   {       return S[0];   }      //-----清空串-----   Bool ClearString(SString *S)   {       if(0 != (*S)[0])       {           (*S)[1] = '\0';  //首地址寫入'\0'           (*S)[0] = 0;     //串長寫入0       }       return TURE;   }      //-----串連接,把串S2連接到S1後面並存放到串T當中-----   Bool Concat(SString *T,SString S1,SString S2)   {       int i,j;              //全部能復制完       if(S1[0]+S2[0] <= MAXSTRLEN)       {           for(i=1; i<=S1[0]; i++)           {               (*T)[i]=S1[i];    //復制串S1到串T中           }           for(j=1; i<=S1[0]+S2[0]; i++)           {               (*T)[i]=S2[j++];  //復制串S2到串T中           }           (*T)[0]=S1[0]+S2[0];           return TURE;       }       //此情況S1能全部復制完,而S2只能復制一部分,因為此函數優先復制S1       else if(S1[0]<MAXSTRLEN && (S1[0]+S2[0])>MAXSTRLEN)       {           for(i=1; i<=S1[0]; i++)           {               (*T)[i]=S1[i];           }           for(j=1;i<=MAXSTRLEN;i++)           {               (*T)[i]=S2[j++];           }           (*T)[0]=MAXSTRLEN;           return ERROR;       }              //只能復制S1一部分       else       {           for(i=1; i<=MAXSTRLEN; i++)           {               (*T)[i]=S1[i];           }           (*T)[0]=MAXSTRLEN;           return ERROR;       }   }      //-----打印指定串S-----   void StrOutput(SString S)   {       int i;       printf("Output string:");       for(i=1; i<=S[0]; i++)       {           printf("%c",S[i]);       }       printf("\n");   }      //-----截取指定字符串,用Sub返回串S中在pos位置開始長度為len的字串-----   Bool SubString(SString *Sub, SString S, int pos, int len)   {         int i,j;       if((pos>=1 && pos<=S[0]) && (len>0 && len<=S[0]-pos+1))       {           for(i=1,j=pos; i<=len; i++)           {               (*Sub)[i]=S[j++];           }           (*Sub)[0]=len;           return TURE;       }       return ERROR;   }      //-----在串S中從pos位置查找第一次出現串T的位置,返回相對S新的偏移位置-----   int Index(SString S, SString T, int pos)   {       int m,n,i;       SString sub;       if(pos > 0)       {           n=StrLength(S);           m=StrLength(T);           i=pos;           while(i<=n-m+1)  //遍歷次數           {               SubString(&sub,S,i,m);               if(0!=StrCompare(sub,T))               {                   ++i;               }               else               {                   return i;               }           }       }       return 0;   }      //-----把串S中所有字符串T用V替換掉-----   Bool Replace(SString *S, SString T, SString V)   {       int i=1,j=1,m=StrLength(T),n=StrLength(V);       while(i <= (*S)[0])          //遍歷所有的字符       {           j=Index(*S,T,i);         //查找匹配字串的位置           if(j > 0)                //查找到字串           {               StrDelete(S,j,m);    //刪除字串               StrInsert(S,j,V);    //插入替換字串           }           i+=n+1;           //i++;           printf("======%d======\n", i);       }       return TURE;   }         //-----在串S的第pos位置前插入串T, 插入時注意S空間要足夠大-----   Bool StrInsert(SString *S, int pos, SString T)   {       int m,n=StrLength(T),i=1,j=pos;       if(pos>=1 && pos<=StrLength(*S)+1 && (T[0]+(*S)[0] <= MAXSTRLEN))       {           while(i<=n)           {               for(m=StrLength(*S)+1; j<m; m--)               {                   (*S)[m]=(*S)[m-1];    //字串後移一位,挪出一位空間               }               (*S)[j]=T[i++];           //拷貝串T字符到串S中               (*S)[0]+=1;               //S串長加1               j+=1;                     //插入位置後移一位           }           return TURE;       }       return ERROR;   }      //------刪除串S中從pos位置起長度為len的子串------   Bool StrDelete(SString *S, int pos, int len)   {       int i=1,j,m,n;       if(pos>=1 && pos<=StrLength(*S)-len+1)       {           while(i<=len)           {               for(m=StrLength(*S),j=pos; j<=m; j++)               {                   (*S)[j]=(*S)[j+1];     //字符串前移一位               }               (*S)[0]-=1;               i++;           }           return TURE;       }       return ERROR;   }      //-----銷毀串-----   Bool DestroyString(SString *S)   {       free(S);       return TURE;   }