厳蔚敏版データ構造学習ノート(5):列

ストリング(string)は文字列と関係があるデータ構造であり、ゼロまたは複数の文字からなる有限シーケンスであり、s=a 1 a 2 a 3...an'(n>=0)と表記されています.ここでsはシリアル名で、シングルクォーテーションマークで囲まれた文字列はシリアルの値であり、aiはアルファベット、数字、または他の文字であってもよい.二つの列の値が等しいだけで、二つの列は等しいと言えます.シリアル値は二つのシングルクォーテーションマークでくくらなければなりませんが、シングルクォーテーションマークは列に含まれていません.シングルクォーテーションマークの役割は変数名または数の定数との混同を避けるだけです.複数の空欄からなる列を「」といい、空欄を「空欄」といいます.Φ空席を表す全体としてはシリアルの論理構造と線形表が非常に似ていますが、操作には大きな違いがあります.たとえば串の中で1つのサブストリングを探して、1つのサブストリングを取ることを求めて、列のある位置の上で1つのサブストリングを挿し込んで、および1つのサブストリングを削除します.

int Index(SString S, SString T, int pos) {  //   4.1
   // T    。   S  pos        T     ，
   //             S    ，    0
   int n,m,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 (StrCompare(sub,T) == 0) ++i;
         else return i;
      } // while
   } // if
   return 0;                    
}

列の表示方法は3つあります.固定長順序格納表現、スタック割り当て格納表現、ブロックチェーン格納表現.固定長順序は、線形テーブルの順序記憶構造のように、一連のアドレスのセットで連続する記憶部にシリアル値の文字列を格納する.

#define MAXSTRLEN 255
typedef unsigned char SString[MAXSTRLEN+1];//0         

列の実際の長さは予め定義された長さの中で任意に定義でき、超えた部分のシリアル値は切り捨てられます.二つの列を接続する場合、3つの場合があります.1、S［1］、S［2］の長さとともに、MAXSTRLENを超えない場合があります.2,S［1］およびS［2］の長さは、MASTRLENよりも大きく、S［1］の長さは、MASTRLENよりも小さい.3,S［1］の長さはMASTRLENよりも大きい.二つの串を結ぶ時はこの三つの違いを考えます.

Status Concat(SString &T, SString S1, SString S2) { // 
   //  T   S1 S2       。    ，   TRUE，  FALSE。
   int i;
   Status uncut;
   if (S1[0]+S2[0] <= MAXSTRLEN) {  //    
      for (i=1; i<=S1[0]; i++) T[i] = S1[i];
      for (i=1; i<=S2[0]; i++) T[i+S1[0]] = S2[i];
      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 (i=S1[0]+1; i<=MAXSTRLEN; i++) T[i] = S2[i-S1[0]];
      T[0] = MAXSTRLEN;
      uncut = FALSE;
   } else {                         //   (  S1)
      for (i=0; i<=MAXSTRLEN; i++) T[i] = S1[i];
      uncut = FALSE;
   }
   return uncut;
} // Concat

もう一つ重要な操作があります.サブストリングの操作です.

Status SubString(SString &Sub, SString S, int pos, int len) { 
   //  Sub   S  pos       len   。
   //   ，1≤pos≤StrLength(S) 0≤len≤StrLength(S)-pos+1。
   int i;
   if (pos < 1 || pos > S[0] || len < 0 || len > S[0]-pos+1)
      return ERROR;
   for(i=1; i<=len; i++)
      Sub[i] = S[pos+i-1];
   Sub[0] = len;
   return OK;
} // SubString

ヒープ割り当ては、このような記憶表現の特徴として、一連の連続した記憶ユニットを用いてシリアル値文字列を格納するが、記憶空間はプログラム実行中に動的に割り当てられている.

//         
typedef struct{
   char *ch;//     ，          ，  ch NULL
   int length;//   
}Hstring;

(続きは未定)