アルゴリズム入門の列の順序格納表現

列、すなわち文字列.コンピュータ上の非数値処理のオブジェクトは、基本的に文字列データです.しかし,現在我々が用いているコンピュータハードウェア構造は主に数値計算の必要性を反映しているため,文字列データの処理は整数や浮動小数点数の処理よりも複雑である.また,異なるタイプのプログラムでは,処理される文字列が異なるという特徴があり,文字列の処理を効率的に実現するには,状況に応じて適切な記憶構造を用いなければならない.列のストレージ表示は主に:1.定長順序記憶表示;2.スタック割当ストレージ表示;3.ブロックチェーン記憶表示.
以下では、比較的簡単な定長順序格納表現について説明します.
列定長順に表示を格納するのは,はっきり言って,固定長文字配列で格納することである.
1.「頭部」の定義

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

 2.初期化

Status InitStr(SString &T)
{
	T[0] = 0;//         。        0。
	return OK;
}

3.文字配列をSStringに割り当てます.

Status StrAssign(SString &T, char *chars)
{
	int len = strlen(chars);
	if (len > MAXSTRLEN)
		return ERROR;
	T[0] = len;
	for (int i = 0; i < len; i++)
	{
		T[i + 1] = chars[i];
	}
	return OK;
}

ここで見ると、SString自体が文字配列なのに、なぜ文字配列でSStringに割り当てられるのかと聞かれるかもしれません.
実はそうではありません.SStringは文字配列とは相対的に異なり、配列中の下付き0の位置に列の現在の実際の長さを格納します.PASCAL言語ではこのストリングタイプを使った表現です.
一方、char*chars="12345"については、char chars 1[n]のような別の文字配列に割り当てるように、ここでのn値は6以上でなければならない.C言語は文字列の末尾に終了フラグとして'0'を付けているからです.しかし、gccのようにこのエラーを検出しないコンパイラもあります.
4.シリアルの比較

Status StrCompare(SString S, SString T)
{
	for (int i = 1; i <= S[0] && i <= T[0]; i++)
	{

		if (S[i] != T[i])
		{
			return S[i] - T[i]; //             
		}
	}
	return T[0] - S[0];//                 ，            。
}

5.Sの下にposと表記されているものから長さlenのサブストリングSubをとる.

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

6.シリアルのマージ:S 1,S 2をSにマージ

Status Contact(SString &S, SString S1, SString S2)
{
	int i = 0;
	int j = 0;
	if (S1[0] + S2[0] <= MAXSTRLEN)   //     ，                    
	{
		S[0] = S1[0] + S2[0];
		for (i = 1; i <= S1[0]; ++i)
			S[i] = S1[i];
		for (j = 1; j <= S2[0]; ++i, ++j)
			S[i] = S2[j];
		return OK;
	} else if (S1[0] < MAXSTRLEN)     //     ，S1     S，S2             
	{

		S[0] = MAXSTRLEN;
		for (i = 1; i <= S1[0]; i++)
		{
			S[i] = S1[i];
		}
		for (j = 1; i <= MAXSTRLEN; ++i, ++j)
			S[i] = S2[j];
		return OK;
	} else)			      //     ， S1    
	{
		S[0] = MAXSTRLEN;
		for (i = 1; i <= MAXSTRLEN; i++)
		{
			S[i] = S1[i];
		}
		return OK;
	}
}

7.モードマッチングの改良アルゴリズム:KMPアルゴリズム

void get_next(SString T, int next[])
{
	int i = 1;
	next[1] = 0;
	int j = 0;
	while (i < T[0])
	{
		if (j == 0 || T[i] == T[j])
		{
			++i;		//   ++j，   next[i] = j。
			++j;		//       j+1       j     ，         j     。					next[i] = j;	//          T[i] == T[j]。
		} else			
			j = next[j];
	}
}

//S   ，T        
Status Index_KMP(SString S, SString T, int pos)
{
	int *next = new int();
	get_next(T, next);
	int i = pos, j = 1; //i T        ,
	while (i <= S[i] && j <= T[0])
	{
		if (j == 0 || S[i] == T[j])
		{
			++i;		
			++j;
		} else
			j = next[j];	//j != 0   S[i] != T[j]，S[i] T[next[j]]  
	}
	if (j > T[0])
		return i - T[0];		//    
	else
		return 0;
}