数据结构–串的存储结构

串的顺序存储

静态数组实现(定长顺序存储)

#define MAXLEN 255
typedef struct
{char ch[MAXLEN];int length;
}SString;

动态数组实现(堆分配存储)

typedef struct
{char* ch;int length;
}HString;int main()
{HString S;S.ch = (char*)malloc(sizeof(char) * MAXLEN);return 0;
}

方案一：

方案二：

$\color{purple}优点:字符的位序和数组下标相同$

方案三：

$\ 0 ′ 表示结尾 ( 对应 A S C I I 码的 \ 0 ) \color{purple}没有Length变量,以字符'\backslash0'表示结尾(对应ASCII码的\backslash0)$

方案四：

串的链式存储

typedef struct StringNode
{char ch;struct StringNode* next;
}StringNode, *String;

typedef struct StringNode
{char ch[4]; //每个结点存多个字符struct StringNode* next;
}StringNode, *String;

基本操作的实现

#define MAXLEN 255
typedef struct 
{char ch[MAXLEN];int length;
}SString;

StrAssign(&T,chars):赋值操作。把串T赋值为chars。StrCopy(&T,S):复制操作。由串s复制得到串干。
StrEmpty(S):判空操作。若s为空串，则返回TRUE，否则返回FALSE。StrLength(S):求串长。返回串s的元素个数。
ClearString(&S):清空操作。将s清为空串。
DestroyString(&S):销毁串。将串s销毁（回收存储空间）。Concat(&T,S1,S2):串联接。用T返回由S1和S2联接而成的新串

$\color{red}SubString(\&Sub,S,pos,len)$ :求子串。用Sub返回串S的第pos个字符起长度为len的子串。

bool SubString(SString &Sub, SString S, int pos, int len)
{if (pos + len - 1 > S.length)   return false;for (int i = pos; i < pos + len; i++)Sub.ch[i - pos + 1] = S.ch[i];Sub.length = len;return true;
}

$\color{red}StrCompare(S,T)$ :比较操作。若S>T，则返回值>0;若S=T，则返回值=0;若S<T，则返回值<0。

int StrCompare(SString S, SString T)
{for (int i = 1; i <= S.length && i <= T.length; i++)if (S.ch[i] != T.ch[i])return S.ch[i] - T.ch[i];return S.length - T.length;
}

$\color{red}Index(S,T)$ :定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置;否则函数值为0。

int Index(SString S, SString T)
{int i = 1, n = S.length, m = T.length;SString sub;while (i <= n - m + 1){SubString(sub, S, i, m);if (StrCompare(sub, T) != 0)    i++;else    return i;}return 0;
}