数据结构串 课件

1、1,第,3,章作业,3.5 3.6 3.10 3.21 3.29 3.32,全校各单位,根据国务院办公厅关于,2019,年国庆节放假的通知精神，今年国庆节学校放假,的时间定为,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

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

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

4、性表比较通用；堆栈用于函数调,用、递归和简化设计等；队列用于离散事件模拟,OS,作业调度和简化设计等,以后再举例,不同点,4,第,4,章,串,String,4.1,串类型的定义,4.2,串的表示和实现,4.3,串的模式匹配算法,5,主要内容,串,s = a,1,a,2,a,n,定长顺序,存储结构,块链,存储结构,堆,存储结构,逻辑结构,存储结构,操作,或运算,模式匹配算法,若干函数的实现,模式匹配,即,子串定位运算,即如何实现,Index(S,T,pos,函数,精华,KMP,算法,快速（用,nextj,或,nextvalj,6,记为,s,a,1,a,2,a,n,(n0,串名,串值（用,括起来,

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

6、有以下,4,个字符串,a =BEI,b =JING c = BEIJING d = BEI JING,问,他们各自的长度,a,是,c,和,d,的子串，在,c,和,d,中的位置都是,1,串,S,中,任意个连续的字符,序列叫,S,的子串,S,叫,主串,子串的第一个字符在主串中的序号,字符在串中的序号,串长度相等，且对应位置上字符相等,a,是哪个串的子串？在主串中的位置是多少,a =3,b =4,c = 7,d=8,空串是任意串的子串；任意串,S,都是,S,本身的子串，除,S,本身,外,S,的其他子串称为,S,的,真子串,数据结构与算法中山大学出版社,空串是哪个串的子串,a,是不是自己的子串,9,C

7、,语言中已有类似的串运算函数,ADT,String,Objects,D=a,i, a,i,CharacterSet, i=1, 2,n, n0,Relations,R1=a,i-1,a,i, a,i-1,a,i,D, i,2,n,functions,至少有,13,种基本操作,StrAssign,T, chars,串赋值，生成值为,chars,的串,T,StrCompare(S,T,串比较，若,ST,返回值大于,0,StrLength(S,求串长，即返回串,S,中的元素个数,Concat,T, S1, S2,串连接，用,T,返回,S1,S2,的新串,SubString,Sub, S, pos,

8、len,求,S,中,pos,起长度为,len,的子串,int,Index(S, T, pos,子串定位函数（模式匹配,返回位置,Replace( return OK,将串,S,中从第,pos,个字符开始、长度为,len,的字符序列复制到串,Sub,中,注：考虑到函数的通用性，应当让串,Sub,的预留长度与,S,一样,子串长度,s = a,1,a,2,a,n,pos,len,Sub,讨论：想存放超长字符串怎么办,改用动态分配的一维数组,堆,17,思路,利用,malloc,函数合理预设串长空间,特点,若在操作中串值改变，还可以利用,realloc,函数,按新串长度,增加空间,即动态数组概念,Typ

9、edef struct,char,ch,若非空串,按串长分配空间,否则,ch=NULL,int length,串长度,HString,堆分配存储特点,仍用一组连续的存储单元来存放串,但存储空间是在程序执行过程中,动态分配,而得,堆,T,的存储结构描述,各分量书写方式,T.ch,T.length,18,C,是指针变量，可以自增,意即每次后移一个数据单,元,直到终值为“假,停止，串尾特征是,c,0,NULL,0,Status,StrAssign,HString,T, char,chars,生成一个串,T, T,值串常量,chars,if (T.ch) free(T.ch,释放,T,原有空间,for

10、,i=0, c=chars,c,i, +c,求,chars,的串长度,i,例,1,编写建堆函数,参见教材,P76,此处,T.ch0,没有用,来装串长，因为另,有,T.length,分量,if ( !i ) T.ch = NULL; T.length = 0,else,if (,T.ch,(char*)malloc( i *sizeof(char,exit(OVERFLOW,T.ch0.i-1 = chars0.i-1,T.length =i,Return OK,StrAssign,19,Status,StrInsert,HString,S, int pos,HString,T,在串,S,的第,

11、pos,个字符,之前,包括尾部）插入串,T,if (pos1,posS.length+1) return ERROR,pos,不合法则告警,if(T.length,只要串,T,不空，就需要重新分配,S,空间，以便插入,T,if (,S.ch,(char*,realloc,S.ch,S.length+T.length)*sizeof(char,exit(OVERFLOW,若开不了新空间，则退出,for ( i=S.length-1; i,pos-1,i,S.ch,i+T.length,S.ch,i,为插入,T,而腾出,pos,之后的位置，即从,S,的,pos,位置起全部字符均后移,S.ch,po

12、s-1,pos+T.length,2 = T.ch,0,T.length,1,插入,T,略,0,S.length,T.length,刷新,S,串长度,return OK,StrInsert,例,2,用“堆”方式编写,串插入函数,参见教材,P75,20,讨论,法,1,存储密度为,法,2,存储密度为,显然，若数据元素很多，用法,2,存储更优,称为,块链结构,链式存储特点,用链表存储串值，易插入和删除,法,1,链表结点的数据分量长度取,1,个字符,法,2,链表结点（数据域）大小取,n,例如,n=4,1/2,9/15=3/5,A,B,C,I,NULL,head,head,A B C D,E F G H

13、,I # # # NULL,21,对块链表的整体描述,define,CHUNKSIZE,80,每块大小，可由用户定义,typedef struct Chunk,首先定义结点类型,char,ch,CHUNKSIZE,每个结点中的数据域,struct Chunk * next,每个结点中的指针域,Chunk,块链类型定义,块链函数的编写略,typedef struct,定义用链式存储的串类型,Chunk *head,头指针,Chunk *tail,尾指针,int curLen,结点个数,Lstring,串类型只用一次，前面可以不加结构名称,对每个结点的描述,22,算法目的,确定主串中所含子串第一次

14、出现的位置,定位,4.3,串的模式匹配算法,BF,算法,又称古典的、经典的、朴素的、穷举的,KMP,算法,算法种类,带回溯，速度慢,避免回溯，匹配速度快,是全课程的亮点之一,定位问题称为串的模式匹配,典型函数为,Index(S,T,pos,23,BF,算法的实现,即编写,Index(S, T, pos,函数,例,1,S,ababcabcacbab,T,abcac,pos,1,求：串,T,在串,S,中第,pos,个字符之后的位置,利用,演示系统,看,BF,算法执行过程,BF,算法设计思想,将主串,S,的第,pos,个字符和模式,T,的第,1,个字符比较,若,相等,继续逐个比较后续字符,若,不等,从主串,S,的下一字符,pos