数据结构：串（MFC的CString模拟）的操作

数据结构：串（MFC的CString模拟）的操作2013-11-26 51cto博客 lilin9105一、串的定义

串:零个或多个字符组成的有限序列。

字串:串中任意个连续的字符组成的子序列称为该串的子串

主串：包含字串相应的串。（相对字串而言的）

空格串：由一个或多个空格组成的串，（只要有空格的串）

空串：串的长度为0时。（第一个字符为""或"/0"。）

串相等：串的长度相等，串的各个对应位置的字符都相等。

串的描述：s = "a1a2a3..........an" （n >= 0）；（n称为串的长度）

串的列子: s = "this is string example"；s = ""；

特点：组成的元素必须是字符。

二、串与线性表的区别：

一、串的逻辑结构和线性表极为相似,但不同的是串的数据对象约束为字符集。

二、串的基本操作和线性表有很大差别

三、在串的基本操作中，通常以“串的整体”作为操作对象。

三、代码演示：

本列模仿MFC的CString（CString对字符集个数没有限制）。

#include <stdio.h>#include<stdlib.h>#define OK 1#defineFALSE 0typedef int Status;int OVERFLOW=0;typedef struct{char* ch;int length;}HString;Status StrAssign（HString &T, char* chars）{//数组T初始化if（！T.length）free（T.ch）;//未赋值的T.ch指向地址，T.ch不为nullchar *c= chars;//c是为了算出chars的长度//printf（"%s", c）;for（int i = 0; *c; i++,c++）;//此处的c而不用chars是因为会用到下面的charsif（！i）{T.ch = NULL; T.length = 0;}else{if（！（T.ch = （char*）malloc（i*sizeof（char））））exit（OVERFLOW）;T.ch = chars;//printf（"
 chars is %s, T.ch is %s
", chars, T.ch）;T.length = i;}return OK;}//初始化int StrLength（HString S）{return S.length;}int StrCompare（HString S, HString T）{if（S.length == T.length）{for（int i = 0; i < S.length; i++）{if（*（S.ch + i） ！= *（T.ch + i）） return *（S.ch + i） - *（T.ch + i）;}}return S.length - T.length;}Status ClearString（HString &S）{//*S.ch = "";S.ch =NULL;//}S.length = 0;return OK;}Status Concat（HString &T, HString S1, HString S2）{if（T.ch）ClearString（T）;if（！（T.ch = （char*）malloc（（S1.length + S2.length + 1）*sizeof（char））））exit（OVERFLOW）;for（int j = 0; j < S1.length; j++）（*（T.ch + j）） = （*（S1.ch++））;T.length = S1.length + S2.length;for（int i = S1.length; i < T.length; i ++）{*（T.ch + i） = *（S2.ch++）;}*（T.ch + T.length） = "";return OK;}Status SubString（HString &Sub, HString S, int pos, intlen）{//当要取pos到未尾时，len取S.length - pos + 1if（pos < 1 || pos > S.length || len < 0 || len > S.length - pos + 1）return FALSE;if（Sub.ch）ClearString（Sub）;if（！len）{Sub.ch = NULL; Sub.length = 0;}else{Sub.ch = （char*）malloc（（len + 1） * sizeof（char））;for（int i = 0; i < len; i++）{//Sub.ch[i] = S.ch[pos + i-1];*（Sub.ch + i） = *（S.ch + pos + i-1）;}*（Sub.ch + len） = "";Sub.length = len;}return OK;}int index（HString s, HString t, int pos）{//查找位置int i = pos;int j = 1;HString S = s;S.ch = s.ch + i-1;HString T =t;while（i <= s.length && j <= t.length）{char strs = *（S.ch++）;char strt = *（T.ch++）;if（strs == strt）{++i; ++j;}else{i = i -j + 2;S.ch = s.ch + i-1;T.ch = t.ch;j = 1;}}if（j > T.length）return （i - T.length）;else return 0;}int main（）{HString S;char* s;//若定义的char *s = ""指向的是个常量s =new char;//此处相当于new char [1]printf（"请输入S.CH值
"）;scanf（"%s", s）;StrAssign（S, s）;HString T;char* t;t = new char;printf（"请输入T.CH值
"）;scanf（"%s", t）;StrAssign（T, t）;printf（"
"）;printf（"**************************
"）;HString W;Concat（W, S, T）;printf（"拼接结果是W.ch = %s
", W.ch）;printf（"**************************
"）;printf（"**************************
"）;HString Sub;int Pos, len;printf（"请输入截取字符的位置pos,长度len（pos,len格式）:
"）;scanf（"%d,%d", &Pos, &len）;SubString（Sub, S, Pos, len）;printf（"截取的字符时Sub.ch = %s
", Sub.ch）;printf（"**************************
"）;printf（"
"）;printf（"**************************
"）;printf（"StrCompare value is %d
", StrCompare（S,T））;printf（"**************************
"）;int pos = 1;int time = 1;while（pos ！= 0）{pos = index（S, T, pos）;if（pos ！= 0）{printf（"pos at %d index, show %d times
", pos , time）; pos+=1; time++;}if（time == 1）printf（"no elem find
"）;}ClearString（S）;return 0;}

四、知识点回顾

串，空串等等的定义，

串与线性表的区别

CString的模型实现

五、扩展学习

串的逻辑结构和基本操作

串的顺序存储

（静态、动态——堆分配存储）

串的链式存储

串的定位——模式匹配

（简单匹配）