cms建站系统开源,都匀住房和城乡建设部网站,seo诊断方案,装修网站排名前十数据结构学习 --1 绪论 数据结构学习 --2 线性表 数据结构学习 --3 栈#xff0c;队列和数组 数据结构学习 --4 串 数据结构学习 --5 树和二叉树 数据结构学习 --6 图 数据结构学习 --7 查找 数据结构学习 --8 排序 本人学习记录使用 希望对大家帮助 不当之处希望大家帮忙纠正…数据结构学习 --1 绪论 数据结构学习 --2 线性表 数据结构学习 --3 栈队列和数组 数据结构学习 --4 串 数据结构学习 --5 树和二叉树 数据结构学习 --6 图 数据结构学习 --7 查找 数据结构学习 --8 排序 本人学习记录使用 希望对大家帮助 不当之处希望大家帮忙纠正 数据结构学习 --4 串 文章目录 4.1 串的定义和实现4.1.1 串的定义4.1.2 串的存储结构4.1.3 串的基本操作 4.2 串的模式匹配4.2.1 简单的模式匹配算法4.2.2 串的模式匹配算法KMP 算法 4.1 串的定义和实现 字符串简称串计算机上非数值处理的对象基本都是字符串数据。我们常见的信息检索系统(如搜索引擎) 文本编辑程序 (如 Word)问答系统、自然语言翻译系统等 都是符数据作为处理对象的。 4.1.1 串的定义
串string 是有零个或多个字符组成的有限序列 一般记为
SA1,A2,A3,AN(N0);其中S 是串名单引号括起来的字符序列是串的值a1可以是字母 数字 或者其他字符串中字符的个数n 称为串的长度。n0时的串称为空串
串的逻辑结构和线性表极为相似区别仅在于串的数据对象限定为字符集。在基本操作上串和线性表有很大差别。线性表的基本操作主要以单个元素作为操作对象如查找、插入或删除某个元素等:而串的基本操作通常以子串作为操作对象如查找、插入或删除一个子串等
4.1.2 串的存储结构
定长顺序存储表示 类似于线性表的顺序存储结构用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中为每个串变量分配一个固定长度的存储区即定长数组。
#define MAXLEN 255 //预定义最大串长为255
typedef struct{ //每个分量存储一个字符char ch[MAXLEN]; int length;//串的实际长度
}SString;串的实际长度只能小于或等于 MAXLEN超过预定义长度的串值会被舍去称为截断。串长有两种表示方法:一是如上述定义描述的那样用一个额外的变量 len来存放串的长度;二是在串值后面加一个不计入串长的结束标记字符“\0”此时的串长为隐含值。 在一些串的操作(如插入、联接等)中若串值序列的长度超过上界MAXLEN约定用“截断”法处理要克服这种弊端只能不限定串长的最大长度即采用动态分配的方式。 堆分配存储表示 堆分配存储表示仍然以一组地址连续的存储单元存放串值的字符序列但它们的存储空间是在程序执行过程中动态分配得到的。
typedef struct{char *ch; //按串长分配存储区ch 指向串的基地址int length; //串的长度
}HString;在C语言中存在一个称之为“堆”的自由存储区并用malloc()和free()函数来完成动态存储管理。利用malloc()为每个新产生的串分配一块实际串长所需的存储空间若分配成功则返回一个指向起始地址的指针作为串的基地址这个串由 ch 指针来指示;若分配失败则返回NULL。已分配的空间可用free()释放掉。 上述两种存储表示通常为高级程序设计语言所采用。块链存储表示仅做简单介绍。 块链存储表示 类似于线性表的链式存储结构也可采用链表方式存储串值。由于串的特殊性(每个元素只有一个字符)在具体实现时每个结点既可以存放一个字符也可以存放多个字符。每个结点称为块整个链表称为块链结构
4.1.3 串的基本操作
StrAssign(T,chars) :赋值操作。把串赋值为chars
StrCopy(T,S) :赋值操作由串S复制得到串T。
StrEmpty(S) :判空操作。若S为空串返回 true 否则false
StrCompare(S,T) :比较操作。若ST ,则返回值0,若ST则返回值0若ST则返回值0;
Strlength(S) 求串长。返回串S的元素个数
Substring(Sub,S,pos,len):求子串。用Sub 返串s的第pos 个字符起长度为len的子串。
Concat(T,S1,S2):串联接。用T返回由S1和S2联接而成的新串。Index(S,T):定位操作。若主串 s 中存在与串T值相同的子串则返回它在主串 S中第一次出现的位置;否则函数值为 0。
clearString(S):清空操作。将s清为空串
DestroyString(S):销毁串。将串S销毁不同的高级语言对串的基本操作集可以有不同的定义方法。在上述定义的操作中串赋值strAssign串比较StrCompare、求串长StrLength 串联接Concat 及求子串 Substring五种操作构成串类型的最小操作子集即这些操作不可能利用其他串操作来实现:反之其他串操作(除串清除ClearString和串销毁 Destroystring外)均可在该最小操作子集上实现。
4.2 串的模式匹配
4.2.1 简单的模式匹配算法 子串的定位操作通常称为串的模式匹配它求的是子串常称模式串在主串中的位置。这里采用定长顺序存储结构给出一种不依赖于其他串操作的爆破匹配算法。 int Index(SString S,SString T){int i1,j1;while(iS.length j T.length){if(S.ch[i] T.ch[j]){i;j; //继续比较后继字符}else{i i-j2; j1 //指针后退重新开始匹配}if(jT.length) return i-T.length;else return 0;}
}4.2.2 串的模式匹配算法KMP 算法
字符串的前缀 后缀 和部分匹配值 要了解子串的结构首先要弄清楚几个概念:前缀、后缀和部分匹配值。前缀指除最后一个字符以外字符串的所有头部子串;后缀指除第一个字符外字符串的所有尾部子串;部分匹配值则为字符串的前缀和后缀的最长相等前后缀长度。 void get_nextval(SString T,int nextval[]){int i1,j0;nextval[1]0;while(iT.length)(if(j0 || T.ch[i]T.ch[j]){i,j;if(T.ch[i]!T.ch[j]) nextval[i]j;else nextval[i]nextval[j];}else jnextval[j];}
}
