《数据结构___第四章》由会员分享，可在线阅读，更多相关《数据结构___第四章（18页珍藏版）》请在金锄头文库上搜索。
1、数据结构 第四章串 1 第四章串 4 1串的概念和基本操作4 2串的存储结构4 3串基本操作的实现4 4串应用示例 文本编辑 数据结构 第四章串 2 4 1串的概念和基本操作 4 1 1串的概念串是特殊的线性表 数据元素是单个字符 串 字符串 是由零个或多个字符组成的有限序列 记作 s a1a2 an n 0 串长串中字符的个数n 子串和主串串中任意个连续的字符组成的子序列称为该串的子串 包含子串的串称为主串 两个串相等的条件 两个串长度相等 且对应位置的字符都相等 空串和空白串空串不包含任何字符 表示为 空白串由一个或多个空格组成 如 数据结构 第四章串 3 4 1 2串的基本操作 1 用串
2、常量赋值StrAssign 2 串复制StrCopy 3 求串长StrLength 4 串连接Concat 5 求子串SubString 6 子串定位Index 7 串比较StrCompare 8 子串置换Replace 9 串插入StrInsert 10 子串删除StrDelete线性表的操作通常以 数据元素 为操作对象 串的操作主要以 串的整体 为操作对象 数据结构 第四章串 4 例 设s Iamastudent t OK p student q nurse r good 1 l concat s t l Iamastudent OK 2 replace s Iamanurse 3 ins
3、ert s 8 r s Iamagoodnurse 数据结构 第四章串 5 4 2串的存储结构 4 2 1顺序存储结构 顺序串 1 静态存储分配 定长结构 defineMaxStrSize1000 预定义最大串长空间typedefstruct charch MaxStrSize 1 C语言中设置串终止符 0 intlength 串长度 SeqString WelcometoBeijing 0 SeqStrings s ch 0 1000 s length 19 数据结构 第四章串 6 2 动态存储分配 堆 利用C语言的动态分配函数malloc和free实现 typedefstruct char
4、 ch 若串非空 则按实际串长分配 存储区 否则ch为NULLintlength 串长 HString HStrings1 if s1 ch char malloc 12 sizeof char error overflow else s1 ch ok s1 length 3 例 数据结构 第四章串 7 4 2 2块链存储结构 defineChunkSize80 由用户定义块大小typedefstructchunk charch ChunkSize structchunk next Chunk typedefstruct Chunk head 串的头指针intlength 串的长度 LinkS
5、tring ABO OK s head LinkStrings s length 6 块 chunksize值 大小的讨论 过大 存储密度增大 但一些操作 如插入 删除 替换等 有不便之处 可能会造成大量字符的移动 过小 最小为1 存储密度下降 便于插入和删除等操作 f r i d 数据结构 第四章串 8 4 3串基本操作的实现 高级语言程序设计中的串存储结构通常选择顺序串静态顺序存储约定 串值长度上溢时 用截尾法进行处理动态顺序存储 堆 操作中没有对串长的限制 更为实用 1 voidStrAssign HString s char str 用串常量str给串 s赋值 if s ch free
6、 s ch 释放s原有空间for len 0 str len 0 len 求str串长lenif len 0 s ch NULL s length 0 else if s ch char malloc len sizeof char error overflow s ch 0 len 1 str 0 len 1 s length len StrAssign 数据结构 第四章串 9 2 voidStrCopy HString s HStringt 将串t的值复制给串 s if s ch free s ch 释放s原有空间if t length 0 s ch NULL s length 0 els
7、e if s ch char malloc t length sizeof char error overflow s ch 0 t length 1 t ch 0 t length 1 s length t length StrCopy 数据结构 第四章串 10 3 intStrLength HStrings 求s的串长 return s length StrLength 4 intStrCompare HStrings1 HStrings2 s1 s2 返回值 0 s1 s2 返回0 s1 s2 返回值 0 for i 0 i s1 lengthreturn s1 length s2 le
8、ngth StrCompare 数据结构 第四章串 11 5 HStringConcat HStrings1 HStrings2 返回串s1和s2联接而成的新串 HStringt if t ch free t ch 释放t原有空间if t ch char malloc s1 length s2 length sizeof char error overflow t length s1 length s2 length t ch 0 s1 length 1 s1 ch 0 s1 length 1 t ch s1 length t length 1 s2 ch 0 s2 length 1 retu
9、rn t Concat 数据结构 第四章串 12 6 voidSubString HString sub HStrings intpos intlen 求串s从第pos个字符起长度为len的子串 sub if 1ch free sub ch if len 0 sub ch NULL sub length 0 else if sub ch char malloc len sizeof char error overflow sub ch 0 len 1 s ch pos 1 pos len 2 sub length len elseerror no SubString pos 1 len 0 s
10、 length 1 数据结构 第四章串 13 7 intIndex HStrings HStringt intpos 返回子串t在主串s中从第pos个字符开始的位置 若不存在 返回值为0 if poss length return 0 i pos j 1 设定主串 子串字符开始比较的位置while it length return i t length 匹配成功elsereturn 0 Index 数据结构 第四章串 14 i 模式匹配的概念 即子串的定位操作 例 s abcabcdefabcdmn t efapq 匹配失败t bcd 匹配成功 有效位移 5 主串s 子串t pos n s l
11、ength 1 m t length i s t pos n 1 n m 1 m j i j 1 数据结构 第四章串 15 4 4串应用示例 文本编辑 分析 操作对象 文本串 行是文本串的子串 基本操作查找插入删除 轻轻的我走了 正如我轻轻的来 我轻轻的招手 作别西天的云彩 那河畔的金柳 是夕阳中的新娘波光里的艳影 在我的心头荡漾 软泥上的青荇 油油的在水底招摇 在康河的柔波里 我甘心做一条水草那树荫下的一潭 不是清泉 是天上虹揉碎在浮藻间 沉淀着彩虹似的梦 寻梦 撑一支长篙 向青草更青处漫溯 满载一船星辉 在星辉斑斓里放歌但我不能放歌 悄悄是别离的笙箫 夏虫也为我沉默 沉默是今晚的康桥 悄悄的我走了 正如我悄悄的来 我挥一挥衣袖 不带走一片云彩 数据结构 第四章串 16 存储结构选择 方案一 简单顺序存储方案二 行表 堆 块链 012n 数据结构 第四章串 17 方案三 知识回顾KnowledgeReview
