java 串的顺序存储_算法入门之串的顺序存储表示
串，即字符串。計算機上的非數值處理的對象基本上是字符串數據。但是，由于現在我們使用的計算機硬件結構主要是反映數值計算的需要的，在處理字符串數據時比處理整數和浮點數要復雜的多。而且，對于不同類型程序，所處理的字符串具有不同的特點，要有效地實現字符串的處理，就必須根據具體情況使用合適的存儲結構。串的存儲表示主要有：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 chars1[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.串的合并：S1，S2合并為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;
}
總結
以上是生活随笔為你收集整理的java 串的顺序存储_算法入门之串的顺序存储表示的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： linux挂载fc存储有超级坏块_Nan
- 下一篇： dbscan java_DBSCAN算法