数据结构（串）

串的定义串即字符串String是由零个或多个字符组成的有限序列。一般记为S′a1a2⋯⋯an′(n≥0)S a_1a_2\cdots\cdots a_n \quad (n \ge 0)S′a1​a2​⋯⋯an′​(n≥0)其中SSS是串名单引号括起来的字符序列是串的值aia_iai​可以是字母、数字或其他字符串中字符的个数nnn称为串的长度。n0n0n0时的串称为空串用∅\emptyset∅表示。子串串中任意个连续的字符组成的子序列。主串包含子串的串。字符在主串中的位置字符在串中的序号[第一次出现的位置。字符集字符的集合yf(x)y f(x)yf(x)字符集函数定义域编码函数映射规则 fy对应的二进制数基本操作串是一种特殊的线性表数据元素之间呈线性关系a1—a2—a3—a4—a5a_1—a_2—a_3—a_4—a_5a1​—a2​—a3​—a4​—a5​有啥不一样~~串的数据对象限定为字符集如中文字符、英文字符、数字字符、标点字符等串的基本操作如增删改查等通常以子串为操作对象#定义一个串顺序存储静态数组#defineMAXLEN255;typedefstruct{charch[MAXLEN];intlength;}SString;顺序存储动态数组-- 堆动态分配typedefstruct{char*ch;intlength;}HString;HString S;S.ch(char*)malloc(MAXLEN*sizeof(char));//用完要手动freeS.length0;方案二的ch只能存放0~255方案四的int就多的很喽链式存储每个节点存放单个字符** 存储密度低**typedefstructStringNode{charch;//每个节点存放1个字符structStringNode*next;}StringNode,*String;每个节点存多个字符存储密度高typedefstructStringNode{charch[4];//每个节点存多个字符structStringNode*next;}StringNode,*String;#StrAssign (T,chars)赋值操作。把串 T 赋值为 chars。#StrCopy (T,S)复制操作。由串 S 复制得到串 T。#StrEmpty (S)判空操作。若 S 为空串则返回 TRUE否则返回 FALSE。#StrLength (S)求串长。返回串 S 的元素个数。#ClearString (S)清空操作。将 S 清为空串。#DestroyString (S)销毁串。将串 S 销毁回收存储空间。#Concat (T,S1,S2)串联接。用 T 返回由 S1 和 S2 联接而成的新串#SubString(Sub,S,pos,len)求子串。用Sub返回串S的第pos个字符起长度为len的子串。boolSubString(SStringSub,SString S,intpos,intlen){if(poslen-1S.length)//字串范围越界returnfalse;for(intipos;iposlen;i)Sub.ch[i-pos1]S.ch[i];Sub.lengthlen;returntrue;}#Index(S,T)定位操作。若主串S中存在与串T值相同的子串则返回它在主串S中第一次出现的位置否则函数值为0。intIndex(SString S,SString T){inti1,nstrLength(S),mStrLength(T);SString sub;while(in-m1){SubString(sub,S,i,m);if(StrCompare(sub,T)!0)i;elsereturni;}return0;}#StrCompare(S,T)比较操作。若ST则返回值0若ST则返回值0若ST则返回值0。//比较操作若ST,则返回值0;相等返回0;若ST,则返回值0intStrCompare(SString S,SString T){for(inti1;iS.lengthiT.length;i){if(S.ch[i]!T.ch[i])returnS.ch[i]-T.ch[i];}//扫描过所有字符都相同则长度长的串更大returnS.length-T.length;}