链式存储结构.ppt

数据结构讲义 第四章串 2 4 1串类型的定义4 2串的表示和实现4 3串的模式匹配算法4 4串操作应用举例 第四章串 3 1 串类型的定义 串 或字符串 String 是由零个或多个字符组成的有限序列 一般记作s c0c1c2 cn 1 n 0 其中 s为串名 用双引号括起来的字符序列是串的值 ci 0 i n 1 可以是字母 数字或其它字符 双引号为串值的定界符 不是串的一部分 字符串字符的数目n称为串的长度 零个字符的串称为空串 仅由空格组成的的串称为空格串 4 零个字符的串称为空串 通常以两个相邻的双引号来表示空串 Nullstring 如 s 它的长度为零 仅由空格组成的的串称为空格串 如 s 若串中含有空格 在计算串长时 空格应计入串的长度中 如 s I mastudent 的长度为13 在C语言中 用单引号引起来的单个字符与单个字符的串是不同的 如s1 a 与s2 a 两者是不同的 s1表示字符 而s2表示字符串 空串与空格字符串 5 字符与字符串 称一个字符在串序列中的序号为该字符在串中的位置 当一个字符在串中多次出现时 以该字符第一次在字符串中出现的位置为该字符在串中的位置 子串与主串 子串 一个串的任意个连续的字符组成的子序列称为该串的子串 主串 包含子串的串称为主串 子串在主串中的位置是以子串的第一个字符在主串中的位置来表示的 两串串相等 称两个串是相等的 当且仅当这两个串的值相等 也即 两个串的长度相等 并且各个对应位置的字符都相等时才相等 字符相等意味着字符所对应的ascii值相等 主串和子串 6 串的基本操作定长顺序存储表示堆分配存储表示串的块链存储表示 2 串的表示和实现 7 串基本操作C语言函数库串处理函数串的基本操作描述串与线性表的比较串的存储结构 串的基本操作 8 串的基本操作分析 常规操作单串操作双串操作子串编辑操作索引操作 串的基本操作 9 常规操作 字符串初始化 InitString字符串销毁 DestoryString单串操作 求字符串长度 StrLength 判断是否为空串 将给定字符串清空 双串操作 两个字符串是否相等 两个字符串复制 两个字符串连接 串的基本操作分析 10 子串编辑操作 查找给定的子串是否存在 查找给定的子串存在数量 索引操作 在某个位置开始插入某个字符串 StrInsert 在某个位置替换给定长度的子串 StrReplaceIndex 在某个位置删除给定长度的子串 StrDeleteIndex 自某位置开始取给定长度的子串 StrSubString 串的基本操作分析 11 C语言函数库串处理函数 对于串的基本操作集可以有不同的定义方法 在使用高级程序设计语言中的串类型时 应以该语言的参考手册为准 例如 C语言函数库中提供下列串处理函数 gets str 输入一个串 puts str 输出一个串 strcat str1 str2 串联接函数 strcpy str1 str2 k 串复制函数 strcmp str1 str2 串比较函数 strlen str 求串长函数 c语言提供的关于字符串处理函数 其说明主要在 string h 中 12 C语言函数库串处理函数 strcpy 将字符串src复制到destStrcat 将字符串src添加到dest末尾Strchr 检索并返回字符c在字符串s中第一次出现的位置Strcmp 字符串s1与s2的大小 并返回s1 s2strcpy 将字符串src复制到destStrcspn 扫描s1 返回在s1中有 在s2中也有的字符个数Strdup 将字符串s复制到最近建立的单元Strerror 本函数返回最近一次的错误信息 Stricmp 比较字符串s1和s2 并返回s1 s2strlen 返回字符串s的长度 13 C语言函数库串处理函数 strlwr 字符串s中的大写字母全部转换成小写字母 并返回转换后的字符串strncat 将字符串src中最多maxlen个字符复制到字符串dest中strncmp 比较字符串s1与s2中的前maxlen个字符strncpy 复制src中的前maxlen个字符到dest中strnicmp 比较字符串s1与s2中的前maxlen个字符Strnset 将字符串s的前n个字符置于ch中strpbrk 扫描字符串s1 并返回在s1和s2中均有的字符个数Strrchr 扫描最后出现一个给定字符c的一个字符串sStrrev 将字符串s中的字符全部颠倒顺序重新排列 并返回排列后的字符串Strset 将一个字符串s中的所有字符置于一个给定的字符ch 14 C语言函数库串处理函数 strspn 扫描字符串s1 并返回在s1和s2中均有的字符个数strstr 扫描字符串s2 并返回第一次出现s1的位置strtod 将字符串str转换成双精度数 并返回这个数 strtok 检索字符串s1 该字符串s1是由字符串s2中定义的定界符所分隔strtol 将字符串str转换成长整型数 并返回这个数 strupr 将字符串s中的小写字母全部转换成大写字母 并返回转换后的字符串 串的基本操作 StrAssignStrCopyStrDestroyStrEmptyStrCompareStrLengthStrConcat StrSubStringStrIndexStrReplaceStrInsertStrDeleteStrClear 16 StrAssign StrAssign T chars 初始条件 chars是字符串常量 操作结果 把chars赋为T的值 17 StrCopy StrCopy T S 初始条件 串S存在 操作结果 由串S复制得串T 18 StrDestroy StrDestroy S 初始条件 串S存在 操作结果 串S被销毁 19 StrEmpty StrEmpty S 初始条件 串S存在 操作结果 若S为空串 则返回TRUE 否则返回FALSE 表示空串 空串的长度为零 20 StrEmpty StrEmpty S 初始条件 串S存在 操作结果 若S为空串 则返回TRUE 否则返回FALSE 表示空串 空串的长度为零 21 StrCompare StrCompare S T 初始条件 串S和T存在 操作结果 若S T 则返回值 0 若S T 则返回值 0 若S T 则返回值 0 例如 StrCompare data state 0 22 StrLength StrLength S 初始条件 串S存在 操作结果 返回S的元素个数 称为串的长度 23 StrConcat StrConcat T S1 S2 初始条件 串S1和S2存在 操作结果 用T返回由S1和S2联接而成的新串 例如 StrConcate T man kind 求得T mankind 24 StrSubString StrSubString Sub S pos len 初始条件 串S存在 1 pos StrLength S 且0 len StrLength S pos 1 操作结果 用Sub返回串S的第pos个字符起长度为len的子串 子串为 串 中的一个字符子序列 25 StrSubString示例 例如 StrSubString sub commander 4 3 求得sub man StrSubString sub commander 1 9 求得sub commander StrSubString sub commander 9 1 求得sub r StrSubString sub commander 4 7 sub StrSubString sub beijing 7 2 sub StrSubString sub student 5 0 sub 长度为0的子串为 合法 串 26 StrIndex StrIndex S T pos 初始条件 串S和T存在 T是非空串 1 pos StrLength S 操作结果 若主串S中存在和串T值相同的子串 则返回它在主串S中第pos个字符之后第一次出现的位置 否则函数值为0 子串在主串中的位置 子串在主串中的位置 意指子串中的第一个字符在主串中的位序 假设S abcaabcaaabc T bca StrIndex S T 1 2 StrIndex S T 3 6 StrIndex S T 8 0 27 StrReplace StrReplace S T V 初始条件 串S T和V均已存在 且T是非空串 操作结果 用V替换主串S中出现的所有与 模式串 T相等的不重叠的子串 StrReplace例 假设S abcaabcaaabca T bca 若V x 则经置换后得到S axaxaax 28 StrInsert StrInsert S pos T 初始条件 串S和T存在 1 pos StrLength S 1 操作结果 在串S的第pos个字符之前插入串T 例如 S chater T rac 则执行StrInsert S 4 T 之后得到S character 29 StrDelete StrDelete S pos len 初始条件 串S存在1 pos StrLength S len 1 操作结果 从串S中删除第pos个字符起长度为len的子串 30 StrClear StrClear S 初始条件 串S存在 操作结果 将S清为空串 31 串类型 在上述抽象数据类型定义的13种操作中 串赋值StrAssign 串复制Strcopy 串比较StrCompare 求串长StrLength 串联接Concat以及求子串SubString等六种操作构成串类型的最小操作子集 即 这些操作不可能利用其他串操作来实现 反之 其他串操作 除串清除ClearString和串销毁DestroyString外 可在这个最小操作子集上实现 32 串类型 定位函数Index S T pos 例如 可利用串比较 求串长和求子串等操作实现定位函数Index S T pos 算法的基本思想为 StrCompare SubString S i StrLength T T 0 33 StrIndex T为非空串 若主串S中第pos个字符之后存在与T相等的子串 则返回第一个这样的子串在S中的位置 否则返回0 intStrIndex StringS StringT intpos if pos 0 n StrLength S m StrLength T i pos while i n m 1 StrSubString sub S i m if StrCompare sub T 0 i elsereturni return0 S中不存在与T相等的子串 34 串与线性表的比较 串的逻辑结构和线性表极为相似 区别仅在于串的数据对象约束为字符集 串的基本操作和线性表有很大差别 在线性表的基本操作中 大多以 单个元 作为操作对象 在串的基本操作中 通常以 串的整体 作为操作对象 35 串的存储结构 对串的存储方式取决于我们对串所进行的运算 如果在程序设计语言中 串的运算只是作为输入或输出的常量出现 则此时只需存储该串的字符序列 这就是串值的存储 此外 一个字符序列还可赋给一个串变量 操作运算时通过串变量名访问串值 36 串的存储结构 实现串名到串值的访问 在C语言中可以有两种方式 串的静态存储结构 将串定义为字符型数组 数组名就是串名 串的存储空间分配在编译时完成 程序运行时不能更改 串的动态存储结构 定义字符指针变量 存储串值的首地址 通过字符指针变量名访问串值 串的存储空间分配是在程序运行时动态分配的 37 串存储结构区别 静态存储采用顺序存储结构 动态存储采用的是链式存储和堆存储结构串的逻辑结构和线性表极为相似 区别仅在于串的数据对象约束为字符集 串的基本操作和线性表有很大差别 在线性表的基本操作中 大多以 单个元 作为操作对象 在串的基本操作中 通常以 串的整体 作为操作对象 38 定长顺序存储表示 1 串的静态存储结构2 串的紧缩式存储3 串的顺序存储结构4 在静态存储方式中求子串 39 类似于线性表的顺序存储结构 用一组地址连续的存储单元存储串值的字符序列 由于一个字符只占1个字节 而现在大多数计算机的存储器地址是采用的字编址 一个字 即一个存储单元 占多个字节 因此顺序存储结构方式有两种 串的静态存储结构 40 1 紧缩格式 即一个字节存储一个字符 这种存储方式可以在一个存储单元中存放多个字符 充分地利用了存储空间 但在串的操作运算时 若要分离某一部分字符时 则变得非常麻烦 2 非紧缩格式 这种方式是以一个存储单元为单位 每个存储单元仅存放一个字符 这种存储方式的空间利用率较低 如一个存储单元有4个字节 则空间利用率仅为25 但这种存储方式中不需要分离字符 因而程序处理字符的速度高 串的静态存储结构 41 如图所示是以4个字节为一个存储单元的存储结构 每个存储单元可以存放4个字符 对于给定的串s data structure 在C语言中采用字符 0 作串值的结束符 串s的串值连同结束符的长度共15 只需4个存储单元 串的紧缩式存储 42 串的定长顺序存储结构 类似于顺序表 用一组地址连续的存储单元存储串值中的字符序列 所谓定长是指按预定义的大小 为每一个串变量分配一个固定长度的存储区 如 defineMAXSIZE256chars MAXSIZE 则串的最大长度不能超过256 如何标识实际长度 特殊字符作为串结束符 首字符存放串长度 指针标识 通常情况下有三种基本方法 43 特殊字符作为串的终结符在串尾存储一个不会在串中出现的特殊字符作为串的终结符 以此表示串的结尾 比如C语言中处理定长串的方法就是这样的 它是用 0 来表示串的结束 这种存储方法不能直接得到串长度 是用判断当前字符是否是 0 来确定串是否结束 的从而求得串的长度 chars MaxSize 定长顺序存储终结符 图4 1串的顺序存储方式1 44 类似顺序表 用一个指针来指向最后一个字符 这样表示的串描述如下 defineMaxSizetypedefstruct charstr MaxSize intcurlen 串长度 String 串类型定义 定长顺序存储指针标识 45 定义一个串变量 Strings s data 定长顺序存储指针标识图示 图4 1串的顺序存储方式2 这种存储方式可以直接得到串的长度 s curlen 1 46 设定长串存储空间 chars MAXSIZE 1 用s 0 存放串的实际长度 串值存放在s 1 s MaxSize 字符的序号和存储位置一致 应用更为方便 首字符存放串长度 在静态存储方式中求子串intSubStr Strings1 String s2 intstart intlen intj k j s1 length if startj len 0 参数错误 s2 str 0 0 s2 length 0 returnFALSE 静态存储示例 k strlen s1 str start 1 求子串的长度 if len k s2 length k else s2 length len 置子串的串长 for j 0 j s2 length j m s2 str j s1 str m 1 s2 str j 0 置结束标记 returnTRUE 静态存储示例 49 堆分配存储表示 串的动态存储结构堆存储结构链式存储结构在链式存储方式中求子串串名的存储映象 50 串的动态存储结构 我们知道 串的各种运算与串的存储结构有着很大的关系 在随机取子串时 顺序存储方式操作起来比较方便 而对串进行插入 删除等操作时 就会变得很复杂 因此 有必要采用串的动态存储方式 串的动态存储方式采用两种形式 链式存储结构堆存储结构 51 堆存储结构特点 堆存储结构的特点是 仍以一组空间足够大的 地址连续的存储单元存放串值字符序列 但它们的存储空间是在程序执行过程中动态分配的 每当产生一个新串时 系统就从剩余空间的起始处为串值分配一个长度和串值长度相等的存储空间 52 堆存储结构操作 在C语言中 存在一个称为 堆 的自由空间 由动态分配函数malloc 分配一块实际串长所需的存储空间 如果分配成功 则返回这段空间的起始地址 作为串的基址 由free 释放串不再需要的空间 用堆存放字符串时 其结构用C语言定义如下 typedefstruct char str intlength HeapString 53 链式存储结构 串的链式存储结构中每个结点包含字符域和结点链接指针域 字符域用于存放字符 指针域用于存放指向下一个结点的指针 因此 串可用单链表表示 用链表存放字符串时 其结构用C语言定义如下 typedefstructnode charstr structnode next LinkStringType 54 intsubstr HeapStrings1 HeapString s2 intm intn HeapString p q v intlength1 j p 在链式存储方式中求子串 55 p s1 next for j 0 jnext 找到子串和起始位置 s2 slstrtype malloc sizeof slstrtype 分配子串和第一个结点 v s2 q v for j 0 jnext NULL j 建立子串 q str p str p p next q slstrtype malloc sizeof slstrtype v next q v q q str 0 q next NULL 置子串和尾结点 returnTRUE 在链式存储方式中求子串 56 串名的存储映象 串名的存储映象就是建立了串名和串值之间的对应关系的一个符号表 在这个表中的项目可以依据实际需要来设置 以能方便地存取串值为原则 如 s1 data s2 structure 假若一个单元仅存放1个字符 则上面两个串的串值顺序存储如图4 5所示 若符号表中每行包含有串名 串值的始地址 尾地址 则如图4 6 a 所示 也可以不设尾地址 而设置串和长度值 则如图4 6 b 所示 对于链式存储串值的方式 如果要建立串变量的符号表 则只需要存入一个链表的表头指针即可 57 块链存储结构 用单链表存放串 每个结点仅存储一个字符 如图4 3所示 因此 每个结点的指针域所占空间比字符域所占空间要大得多 为了提高空间的利用率 我们可以使每个结点存放多个字符 称为块链结构 用块链存放字符串时 其结构用C语言定义如下 typedefstructnode charstr 4 structnode next LinkStringType 58 单字符链式存储结构 串的链式存储结构中每个结点包含字符域和结点链接指针域 字符域用于存放字符 指针域用于存放指向下一个结点的指针 因此 串可用单链表表示 用链表存放字符串时 其结构用C语言定义如下 typedefstructnode charstr structnode next LinkStringType 59 3 串的模式匹配算法 串的模式匹配算法朴素的模式匹配无回溯匹配问题 60 串的模式匹配算法 模式匹配定义 子串的定位操作通常称做串的模式匹配 设有两个串s和t s s0s1 sn 1 t t0t1 tm 1 其中1 m n 通常有m n 我们的任务是要在s中找出一个与t相同的子串 通常把s称为目标 把t称为模式 从目标s中查找与模式t完全相同的子串的过程叫作模式匹配 匹配结果有两种 如果s中存在等于t的子串 就指出该子串在s中的位置 称为匹配成功 否则称为匹配失败 函数值为零 模式匹配通常有 朴素的模式匹配 无回溯匹配 朴素的模式匹配思想 有两个串s和t 基本思想 先从主串s中的第一个字符起 截取模式串T的长度的子串 然后与模式串T中的字符逐个比较 其子串与模式串相同 即返回所截取子串的头一个字符位置作为查找的位置 否则 取S中的第二个字符为子串头 将其后的字符再依次与模式串T比较 判断是否相等 依次类推 直到找到位置或没有与模式串相同的子串为止 匹配成功 返回位置 否则 匹配失败 返回0 62 朴素的模式匹配图示 设目标串以t abbaba 和p aba 为例 t的长度为n n 6 p的长度为m m 3 63 朴素的模式匹配代码 intindex Strings Stringt intStart inti Start j 0 初始化 while istr i t str j i j 继续匹配下一个字符 else j j i 1 i 0 主串 子串的i j值回溯 重新开始下一次匹配 if i p length return j p length 1 匹配成功 返回第一个字符序号 elsereturn0 匹配失败 64 无回溯匹配问题 无回溯匹配问题的提出朴素的模式匹配有回溯 效率不高 因此我们希望找到无回溯的算法 为要找到一个无回溯的匹配算法 关键在于一旦pi和tj比较不等 即 要能立即确定右移的位数和继续 无回溯的 比较的字符 也就是说应该用p中哪个字符和tj进行比较 65 无回溯匹配算法的核心问题 一旦pi和tj比较不等 若p中字符pk应该和tj继续比较 显然k i 并且对不同的i k值也不相同 Knuth等人发现这个k值仅依赖于模式p本身 前i个字符 的组成 而与目标t无关 用next i 表示与i对应的k值 其意义在于 若next i 表示一旦匹配过程中pi与tj比较不等 可用p中以next i 为下标的字符与tj进行比较 若