数据结构 第四章ppt课件.ppt
《数据结构 第四章ppt课件.ppt》由会员分享,可在线阅读,更多相关《数据结构 第四章ppt课件.ppt(34页珍藏版)》请在三一办公上搜索。
1、数据结构课程的内容,第4章 串(String),4.2 串的表示和实现4.3 串的模式匹配算法,1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式,4.1 串类型的定义,串即字符串,是由零个或多个字符组成的有限序列,是数据元素为单个字符的特殊线性表。,4.1 串类型的定义,说明:串是一种在数据元素的组成上具有一定约束条件的线性表,即要求组成线性表的所有数据元素都是字符(字母、数字或其他字符),所以,人们经常这样定义串:串是一个有穷字符序列。,4,若干术语:串长:空白串:子串:子串位置:字符位置:串相等:,串中字符个数(n0).n=0 时称为空串。由一个或多个空格符组成的串。串s中任意个连
2、续的字符序列叫s的子串;S叫主串。子串的第一个字符的序号。字符在串中的序号。串长度相等,且对应位置上字符相等。,注:空串是任意串的子串。任意串是其自身的子串。,5,串常量和串变量通常在程序中使用的串可分为:串常量和串变量。串变量:串变量和其它类型的变量一样,其值是可以改变的。串常量:串常量和整常数、实常数一样,在程序中只能被引用但不能改变其值。即只能读不能写。串常量由直接量来表示的:【例】Error(“overflow”)中“overflow”是直接量。串常量命名 有的语言允许对串常量命名,以使程序易读、易写。【例】C+中,可定义串常量pathconst char path=dir/bin/a
3、ppl;,练1:串是由 字符组成的序列,一般记为。,练2:现有以下4个字符串:a=BEI b=JING c=BEIJING d=BEI JING,问:他们各自的长度?a是哪个串的子串?在主串中的位置是多少?,a=3,b=4,c=7,d=8,a是c和d的子串,在c和d中的位置都是1,练3:空串和空白串有无区别?答:有区别。空串(Null String)是指长度为零的串;而空白串(Blank String),是指包含一个或多个空白字符(空格键)的字符串.,0个或多个,S=a1a2an,ADT StingObjects:D=ai|aiCharacterSet,i=1,2,,n,n0Relations
4、:R1=|ai-1,ai D,i=2,,nfunctions:/有13种之多StrAssign(&T,chars)/串赋值,生成值为chars的串TStrCompare(S,T)/串比较,若ST,返回值大于0 StrLength(S)/求串长,即返回S的元素个数 Concat(&T,S1,S2)/串连接,用T返回S1S2的新串SubString(&Sub,S,pos,len)/求S中pos起长度为len的子串Index(S,T,pos)/返回子串T在pos之后的位置 Replace(&S,T,V)/用子串V替换子串TADT Sting,串的抽象数据类型定义(参见教材P71),最小操作子集,设
5、s=I AM A STUDENT,t=GOOD,q=WORKER。求:,练习:,StrLength(s)StrLength(t)SubString(s,8,7)=SubString(t,2,1)=Index(s,A)=Index(s,t)=Replace(s,STUDENT,q)=,144STUDENTO30(s中没有t!)I AM A WORKER,再问:Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)?,4.2串的表示和实现,定长顺序存储表示用一组地址连续的存储单元存储串值的字符序列堆分配存储表示用一组地址连续的存储单元存储串值的字符序列,
6、但存储空间是在程序执行过程中动态分配而得。串的块链存储表示链式方式存储,首先强调:串与线性表的运算有所不同,是以“串的整体”作为操作对象,例如查找某子串,在主串某位置上插入一个子串等。串有三种机内表示方法:,顺序存储,链式存储,定长顺序存储特点:用一组连续的存储单元来存放串,直接使用定长的字符数组来定义,数组的上界预先给出,故称为静态存储分配。,例如:#define Maxstrlen 255/用户可用的最大串长 typedef unsigned char SString Maxstrlen1;SString s;/s是一个可容纳255个字符的顺序串。,注:一般用SString0来存放串长信息
7、;C语言约定在串尾加结束符 0,以利操作加速,但不计入串长;若字符串超过Maxstrlen 则自动截断(因为静态数组存不 进去)。,讨论:想存放超长字符串怎么办?静态数组有缺陷!,实现方式:参见教材P73编程两例,两串连接和求子串,改用动态分配的一维数组,“堆”!,例:用顺序存储方式实现求子串函数SubString(&Sub,S,pos,len),Status SubString(SString,将串S中从第pos个字符开始长度为len的字符序列复制到串Sub中(注:串Sub的预留长度与S一样),s=a1,a2,.,an,n串长,pos,len,思路:利用malloc函数合理预设串长空间。特点
8、:若在操作中串值改变,还可以利用realloc函数按新串长度增加(堆砌)空间。,Typedef struct char*ch;/若非空串,按串长分配空间;否则 ch=NULLint length;/串长度HString,堆分配存储特点:仍用一组连续的存储单元来存放串,但存储空间是在程序执行过程中动态分配而得。,约定:所有按堆存储的串,其关键信息放置在:,Status StrInsert(HString/StrInsert,例:用“堆”实现串插入操作(教材P75),Status StrAssign(HString/StrAssign,指针变量C也可以自增!意即每次后移一个数据单元。,附:堆分配存
9、储表示,直到终值为“假”停止,串尾特征是0NULL=0,显然,若数据元素很多,用法2存储更优称为块链结构,链式存储特点:用链表存储串值,易插入和删除。,法1:链表结点(数据域)大小取1,法2:链表结点(数据域)大小取n(例如n=4),16,虽然提高结点的大小使得存储密度增大,但是做插入、删除运算时,可能会引起大量字符的移动,给运算带来不便。,#define CHUNKSIZE 80/可由用户定义的块大小typedef struct Chunk/首先定义结点类型 char ch CHUNKSIZE;/结点中的数据域 struct Chunk*next;/结点中的指针域Chunk;,块链类型定义:
10、,例略,typedef struct/其次定义用链式存储的串类型 Chunk*head;/头指针 Chunk*tail;/尾指针 int curLen;/结点个数 Lstring;,再次强调:串与线性表的运算有所不同,是以“串的整体”作为操作对象,例如查找某子串,在主串某位置上插入一个子串等。,这类操作中均涉及到定位问题,称为串的模式匹配。它是串处理系统中最重要的操作之一。,19,4.3 串的模式匹配算法,模式匹配(Pattern Matching)即子串定位运算(Index函数)。,算法目的:确定主串中所含子串第一次出现的位置(定位)即如何实现 Index(S,T,pos)函数(见教材P72
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 第四章ppt课件 第四 ppt 课件
链接地址:https://www.31ppt.com/p-2157289.html