《数据结构串》PPT课件

《《数据结构串》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章作业（3.53.63.103.213.293.32）全校各单位：    根据国务院办公厅关于2010年国庆节放假的通知精神，今年国庆节学校放假的时间定为10月1日至7日，共7天。10月1日（星期五）、10月2日（星期六）、10月3日（星期日）为国庆节法定节假日，10月2日（星期六）、10月3日（星期日）公休日分别调至10月4日（星期一）、10月5日（星期二），9月26日(星期日)、10月9日（星期六）公休日分别调至10月6日（星期三）、10月7日（星期四）。9月26日（星期日）、10月9日（星期六）上班。10月1日(星期五)、10月2日（星期六）、10月3日（星期

2、日）全校停课，请任课教师和学生关注各教学职能部门国庆节期间的停调课安排。   节假日期间，各单位要妥善安排好值班和安全、保卫等工作，于9月28日前将值班安排分别送交学校办公室和保卫处。遇有重大突发事件发生，要及时报告并妥善处理，确保全校师生员工祥和平安度过节日假期。   后勤集团、产业集团等单位可根据自身情况作好安排。各附属单位自行安排。                                                   学校办公室                                               二0一0年九月十三日1内

3、容安排略外部排序114数组和广义表5略文件128树和二叉树664略6学时内部排序查找动态存储管理图内容104串494栈和队列386线性表272绪论1章学时内容章上机地点：南一楼东头二电信系机房第4、9、12周，周五晚上2第3章小结线性表、栈、队的异同点：相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。①运算规则不同：线性表为随机存取；而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。②用途不同。线

4、性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、OS作业调度和简化设计等。(以后再举例)不同点：3第4章串（String）4.1串类型的定义4.2串的表示和实现4.3串的模式匹配算法4主要内容串s=‘a1a2……..an’定长顺序存储结构块链存储结构堆存储结构逻辑结构存储结构操作(或运算)模式匹配算法若干函数的实现模式匹配即子串定位运算，即如何实现Index(S,T,pos)函数精华：KMP算法——快速（用next[j]或nextval[j])5记为：s=‘a1a2……..an’(n≥0)串名串值（用‘’括起来）串即字符串，是由零个或多个字符组成的

5、有限序列，是数据元素为单个字符的特殊线性表。4.1串类型的定义隐含结束符‘’，即ASCII码NUL为何要单独讨论“串”类型？1）字符串操作比其他数据类型更复杂（如拷贝、连接操作）2）程序设计中，处理对象很多都是串类型。6若干术语：串长：串中字符的个数（n≥0）。n=0时称为空串。空白串：由一个或多个空格符组成的串。问：空串和空白串有无区别？答：有区别。空串(NullString)是指长度为零的串；而空白串(BlankString),是指包含一个或多个空白字符‘’(空格键)的字符串.7子串：子串位置：字符位置：串相等：例1：现有以下4个字符串：a=‘BEI’b=‘JI

6、NG’c=‘BEIJING’d=‘BEIJING’问：①他们各自的长度？a是c和d的子串，在c和d中的位置都是1串S中任意个连续的字符序列叫S的子串;S叫主串。子串的第一个字符在主串中的序号。字符在串中的序号。串长度相等，且对应位置上字符相等。②a是哪个串的子串？在主串中的位置是多少？a=3，b=4，c=7，d=8“空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串称为S的真子串。”——《数据结构与算法》中山大学出版社③空串是哪个串的子串？a是不是自己的子串？8C语言中已有类似的串运算函数！ADTString{Objects:D={ai

7、ai∈Char

8、acterSet,i=1,2,…，n,n≥0}Relations:R1={

9、ai-1,ai∈D,i=2,…，n}functions://至少有13种基本操作StrAssign(&T,chars)//串赋值，生成值为chars的串TStrCompare(S,T)//串比较，若S>T，返回值大于0…StrLength(S)//求串长，即返回串S中的元素个数Concat(&T,S1,S2)//串连接，用T返回S1＋S2的新串SubString(&Sub,S,pos,len)//求S中pos起长度为len的子串……i