4字符串

null4 字符串4 字符串主要内容主要内容字符串抽象数据类型 字符串的存储结构和类定义 字符串运算的算法实现 字符串的模式匹配主要掌握3.4.1 字符串抽象数据类型 字符串抽象数据类型 基本概念 字符串抽象数据类型 String抽象数据类型 重要性重要性串（字符串），是计算机非数值处理的主要对象之一。 如，在汇编和编译程序中，源程序和目标程序都是串； 如，在事务处理程序中，顾客的姓名和地址，以及货物的名称、产地和规格等，通常也都作为串处理。 由于我们现今使用的计算机的硬件结构主要是面向数值计算的需要，基本上没有提供对串进行操作的指令，因此需要用软件来实现串数据类型。 基本概念基本概念字符串，由0个或多个字符的顺序排列所组成的复合数据结构，简称“串”。 串的长度：一个字符串所包含的字符个数。 空串：长度为零的串，它不包含任何字符内容。 字符(char) ：组成字符串的基本单位 。null串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应的称为主串。例，串 "eij" 是串 "beijing" 的子串， "beijing" 称为主串。字符在序列中的序号称为该字符在串中的位置。子串在主串中的位置定义为子串的第一个字符在主串中的位置。例，字符 ‘n’ 在串 "beijing" 中的位置为 6 。例，子串 "eij" 在串 "beijing" 中的位置为 。2null串 由零个或多个字符组成的有限序列。 记作 S="a1a2…an" 串名：S； 串值：用双引号括起来的字符序列。 长度：串中字符的数目。 空串：含零个字符的串，表示。 空格串：由一个或多个空格组成的串。 子串：串中任意个连续的字符组成的子序列。 字符在串的位置：字符在序列中的序号。 子串在串的位置：子串的第一个字符在串中的位置。 相等：当且仅当两个串的值相等。串值必须用一对双引号括起来空串与空格串的区别？null两个串相等，当且仅当这两个串的值相等。例，串 "bei jing" 与串 "beijing" 不相等 。串值必须用一对双引号括起来，但双引号本身不属于串，只起界定作用。串与线性表区别串与线性表区别串的数据对象约束为字符集。 串的基本操作与线性表有很大差别 线性表的基本操作中，大多以“单个元素”作为操作对象，如查找某个元素、在某个位置上插入一个元素和删除一个元素。 串的基本操作中，通常以“串的整体”作为操作对象。如在串中查找某个子串、在串的某个位置上插入一个子串以及删除一个子串。例子例子 a="BEI" b="JING" c="BEIJING" d="BEI JING" 长度分别为3、4、7、8； a和b都是c和d的子串； a在c和d中的位置都是1； b在c和d中的位置是4和5； a、b、c、d彼此不相等。String抽象数据类型String抽象数据类型字符串类（class String）： 不采用char S[M]的形式 而采用一种动态变长的存储结构。null数据对象: D = { ai | ai ∈ CharacterSet，i = 1, 2, …, n }数据关系: R1 = { < ai-1, ai > }基本操作: nullStrEmpty ( S )StrCopy ( &T ，S )StrCompare ( S ，T )StrLength ( S )Concat ( &T，S1，S2 )SubString ( &Sub，S，pos，len )Index ( S，T )StrInsert ( &S，pos，T )StrDelete( &S，pos，len )String串的常用操作（一）Replace（&S，T，V）String串的常用操作（二）String串的常用操作（二）赋值算子＝ 拼接算子＋ 比较算子 < <= > >= != 和 == 重载下标算子[] char& operator[] (int n); 按字符定位下标 int Find(char c,int start); 反向寻找，定位尾部出现的字符 int FindLast(char c);串的表示和实现串的表示和实现定长顺序存储表示 ——用一组地址连续的存储单元存储串值的字符序列，属静态存储方式。 堆分配存储表示 ——用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。 串的块链存储表示 ——链式方式存储首先强调：串与线性表的运算有所不同，是以“串的整体”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。串有三种机内表示方法：顺序存储链式存储字符串的存储结构和类定义字符串的存储结构和类定义字符串的顺序存储 用一个特殊的末尾标记'\0'。 字符串类class String的存储结构 例如抽取子串 函 关于工期滞后的函关于工程严重滞后的函关于工程进度滞后的回复函关于征求同志党风廉政意见的函关于征求廉洁自律情况的复函 数： String s1 = "value-"; s2 = s1.Substr(2,3); 上述语句涉及的存储形式如下页所示。 字符串类class String的存储结构字符串类class String的存储结构堆分配存储表示堆分配存储表示系统开辟一个串值存储空间（串值可利用空间） ，同时建立一个符号表； 建立一个新串时，在可利用空间分配，并在符号表中记录下串变量名、串值在可利用空间的位置、串长度等信息。nullnullnullnull串的块链存储表示串的块链存储表示用链表方式存储串值，每个结点大小相同。 结点分为两个域 data域 next域结点大小为1的链表结点大小为4的链表#占满存储密度=串值所占的存储位/实际分配的存储位。链式存储特点 ：用链表存储串值，易插入和删除。链式存储特点 ：用链表存储串值，易插入和删除。讨论：法1存储密度为 ；法2存储密度为 ；显然，若数据元素很多，用法2存储更优—称为块链结构法1：链表结点的数据分量长度取1（个字符）法2：链表结点（数据域）大小取n(例如n=4)1/29/15=3/5块链类型的定义#define CHUNKSIZE 80 //每块大小，可由用户定义 typedef struct Chunk { //首先定义结点类型 char ch [ CHUNKSIZE ]; //每个结点中的数据域 struct Chunk * next ; //每个结点中的指针域 }Chunk; typedef struct { //其次定义用链式存储的串类型 Chunk *head; //头指针 Chunk *tail; //尾指针 int curLen; //结点个数 } Lstring; //串类型只用一次，前面可以不加Lstring块链类型的定义字符串的模式匹配字符串的模式匹配在串T中查找是否有与串P相等的子串，则称串T为目标(Target)，把P称为模式(Pattern)。 称查找模式在目标中的匹配位置的运算为模式匹配(Pattern matching)。模式匹配算法模式匹配算法简单模式匹配算法 BF算法 （又称古典的、经典的、朴素的、穷举的） 带回溯，速度慢 KMP(Knuth-Morris-Pratt)算法 避免回溯，匹配速度快 T=“longlonglongago”； P=“longlongago”；简单匹配算法思想简单匹配算法思想算法 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 思想： 将主串S的第pos个字符和模式T的第1个字符比较， 若相等，继续逐个比较后续字符； 若不等，从主串S的下一字符（pos+1）起，重新与T第一个字符比较。 直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。 否则，匹配失败，返回值 0 . 简单模式匹配算法过程简单模式匹配算法过程longlonglont0t1t2t3t4t5t6t7t8t9t10gagt11t12t13o\0t14t15第一趟比较：第二趟比较：第三趟比较：第四趟比较：第五趟比较：简单匹配算法代码简单匹配算法代码int Find(char* target, char* pat) { int i=0,j=0; int lengthP =strlen(pat), lengthT =strlen(target); while(i<=lengthT-lengthP) { j=0; while(target[i]==pat[j]&&j 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 简单模式匹配算法分析设目标T的长度为n,模式P 的长度为m,在最坏情况下，比较次数： 在多数情况下，m远小于n, 因此算法的最坏的时间复杂性为O(n*m)。 复杂度高，效率低*(n-m+1)*m改进的算法改进的算法KMP算法 不做课程要求 注重思想 感兴趣的同学可以学习&实践一下小 结小 结字符串的概念 字符串的存储结构 字符串运算的算法实现 字符串的模式匹配算法 作 业作 业 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 面作业（下周一交） 98页：6，7 复习前五次上机习题