第四章串、数组和广义表PPT课件

第四章：字符串，数组和广义列表，2小时，2个教学目标，了解字符串的存储方法，了解字符串的两种模式匹配算法，重点是BF算法。明确数组和广义表两种数据结构的特点，掌握数组地址的计算方法，了解几种特殊矩阵的压缩和存储方法。掌握广义表的定义和性质以及GetHead和GetTail的操作。数据结构，字符串，第1节，4，补充：C语言中常用的字符串操作，调用标准库函数#包括字符串比较，strcmp(chars1，chars2)字符串复制，str copy(charto，charfrom)字符串连接，strcat(charto，charfrom)字符串长度，STRLEN (CHARS) ，字符串的基本概念，字符串：由零个或多个字符组成的有限序列。字符串名称，字符串值，字符串长度，n，空字符串，n=0，6，4.1.1字符串的基本概念，a= bei ，b= jing c= jing d= jing a和b是c和d的子字符串，a在c和d中的位置是1。b在c中的位置是4，d中的位置是5。是空格字符串、子字符串、字符位置、主字符串、子字符串位置、字符串相等、空格字符串的抽象数据类型。7，4.1.2，字符串数据对象：d=AI | AI 个字符et，I=1，2，n，n 0数据关系：r=| AI-1，AI d，I=2，3，n基本运算： strlenth (s):查找字符串s的长度，StrAssign(s1，s2):将s2的值赋给字符串s1。(3)STR CONCATA(s1，s2，S):连接，在字符串S1之后连接字符串S2以形成新字符串SubStr(s，I，len):找到子字符串并从字符串S的第个字符返回长度为len的子字符串。字符串的抽象数据类型， 8，4.1.2，5 strcmp (S1，S2):字符串比较，如果s1=s2，则返回0；如果是s1s2，返回1。6字符串索引：定位并返回子字符串T在主字符串S中第一次出现的位置。如果T不是S的子字符串，则返回0。(7) StrInsert(s,i,t i，t):插入，插入字符串t到字符串s的第I个位置(8)删除(s，I，LEN):删除，删除从字符串s的第I个字符开始的连续len个字符(9)替换，用字符串s中的字符串r替换所有等于字符串t的子字符串。9，4.1.2字符串，SubStr(s，I，len)操作示例，I=3，len=3，I=7，len=4，空字符串，10，4.1.3字符串非常类似于线性表，除了字符串的数据对象受字符集约束。线性表基本操作中的基本操作，大多以“单元素”为操作对象；在字符串的基本操作中，“整个字符串”通常作为操作对象。字符串的存储结构，字符串是一种特殊的线性表，它的存储表示与线性表相似，但不完全相同。存储字符串的方式取决于将对字符串执行的操作。计算机中有三种字符串表示法：固定长度顺序存储表示法：字符串被定义为字符数组，字符串值可以通过使用字符串名称直接访问。使用这种表示，字符串的存储空间是在编译时确定的，其大小不能更改。堆栈分配存储模式：一组具有连续地址的存储单元仍用于按顺序存储字符串中的字符序列，但在程序运行时，字符串的存储空间是根据字符串的实际长度动态分配的。区块链存储模式：它是一个链式存储结构的代表。嘿。12，4.1.4字符串存储结构，字符串的固定长度顺序存储意味着这种存储结构也称为字符串的顺序存储结构。它使用一组连续的存储单元来存储字符串中的字符序列。所谓的定长顺序存储结构是通过使用定长字符数组直接定义的，数组的上限是预先确定的。特征：字符串的实际长度可以在该预定长度范围内任意设置，超过预定长度的字符串值被截断，称为“截断”。这种字符串表示方法实现的字符串操作的基本操作是“字符序列的复制”。固定长度顺序存储结构被定义为：intlength字符串类型；字符串的存储结构，方案1:使用一个变量来表示字符串的实际长度。你如何表示字符串的长度？方案2:一个不适用的特殊角色字符串的存储结构14、4.1.4和字符串的连接算法需要在三种情况下处理：状态concat的存储结构(s string 1、s string 2、s string/concat、15，4.1.4字符串，以及字符串的堆分配存储表示的实现方法：系统提供了一个具有足够大的空间和连续地址(称为“堆”)的存储空间供字符串使用。它可以通过使用C语言中的动态存储分配函数malloc()和free()来管理。特征：字符串值仍然存储在一组具有连续地址的存储空间中，但是所需的存储空间是在程序执行期间动态分配的，因此它是动态的并且长度可变。字符串的堆存储结构的类型定义了typedefstruct char * ch/*如果不为空，则按长度分配，否则为空*/int length；/*字符串长度*/ HsString；字符串的存储结构，字符串的链式存储表示字符串的链式存储结构类似于线性表的字符串的链式存储结构，采用单链表来存储字符串。节点由一个数据字段组成：存储字符，数据字段可以存储的字符数称为节点大小。下一个字段：保存指向下一个节点的指针。如果每个节点中只存储一个字符，则该节点的指针字段非常大，导致系统空间浪费。为了节省存储空间，考虑到字符串结构的特殊性，每个节点存储几个字符。这个结构叫做区块链结构。17，4.1.4匹配模式，模式匹配：给定主字符串S= S1S2.“信噪比”和模式T=“T1 T2”.“模式匹配”就是在S中找到T的过程。如果匹配成功，返回T在S中的位置；如果匹配失败，则返回0。基本思想是比较主字符串S的第一个字符和模式T的第一个字符，如果它们相等，继续比较两者的后续字符；否则，从主字符串S的第二个字符开始，并与模式T的第一个字符进行比较，重复上述过程，直到比较了T中的所有字符，表明匹配成功。或者比较S中的所有字符，则匹配失败。模式匹配问题的特点是：(1)算法的执行时间不能一次忽略：问题的规模通常很大，往往需要在大量的信息中进行匹配；算法改进所获得的累积效益不可忽视：经常调用模式匹配操作，执行频率高。18，4.1.4匹配模式BP算法，si.主字符串s、模式t、TJ、19、4.1.4匹配模式BP算法、si.主字符串s、模式t、20，4.1.4匹配模式BP算法，例如：主字符串s= ababcabab ，模式T=abcac ，i=3，j=3失败；I“回溯”到2，j回溯到1，第一遍，abcac，21，4.1.4匹配模式BP算法，例如：主字符串s= ababcabab ，模式T=abcac ，第一遍，abcac，i=3，j=3失败；我“回溯”到2，j回溯到1，22，4.1.4匹配模式BP算法，例如：主字符串s= ababcabab ，模式T=abcac ，第二遍，abcac、I=2，j=1失败；我“回溯”到3，j回溯到1，23，4.1.4匹配模式BP算法，例如：主字符串s= ababcabcbab ，模式t= abcac ， j，第二遍，abcac，i=2，j=1失败；我“回溯”到3，j回溯到1，24，4.1.4匹配模式BP算法，例如：主字符串s= ababcabcbab ，模式T=abcac ，i=7，j=5失败；我“回溯”到4，j回溯到1，第三遍，ABCC，25，4.1.4匹配模式BP算法，例如：主字符串s= ababcabab ，模式t= ABCC ，第三遍，ABCC，I=7，j=5失败；我“回溯”到4，j回溯到1，26，4.1.4匹配模式BP算法，例如：主字符串s= ababcabab ，模式T=abcac ，第4遍，abcac、I=4，j=1失败；我“回溯”到5，j回溯到1，27，4.1.4匹配模式BP算法，例如：主字符串s= ababcabcbab ，模式t= abcac ， j，第4遍，abcac，i=4，j=1失败；我“回溯”到5，j回溯到1，28，4.1.4匹配模式BP算法，例如：主字符串s= ababcabab ，模式T=abcac ，第5遍，abcac、I=5，j=1失败；我“回溯”到6，j回溯到1，29，4.1.4匹配模式BP算法，例如：主字符串s= ababcabcbab ，模式t= abcac ， j，第5遍，abcac，i=5，j=1失败；我“回溯”到6，j回溯到1，30，4.1.4匹配模式BP算法，用于e，31，4.1.4匹配模式BP算法，它描述了设置为在字符串S和字符串T中进行比较的初始下标I和J；循环，直到比较了所有的字符；如果I=j，继续比较S和T的下一个字符；否则，我和J将回溯，为下一次比较做准备。如果比较了T中的所有字符，则匹配成功，并返回匹配的初始比较下标；否则，匹配失败并返回0；32，4.1.4匹配模式BP算法，intindex (sstrings，sstrings，int pos)/返回主字符串中pos字符后的子字符串t的位置，如果不存在，函数值为0。/其中t不为空，1 pos strlenth。i=pos。j=1；而(0)返回0；elsereturn0/索引、I、j、j-1、I-1、I-j2、I-j1、1、2、.33，4.1.4匹配模式BP算法，时间复杂度：将字符串s长度设置为n，字符串T长度设置为m，在匹配成功的情况下，考虑两种极端情况：最佳情况：字符串T的第一个字符匹配失败.例如，如果S= AAAAAAAAAABCDCCCC t= BCD 假设成功匹配发生在si，则i-1匹配在i-1的不成功匹配中被比较，并且I-1的成功匹配在总共M次中被比较，因此i-1 m匹配在总数中