算法与数据结构讲稿

单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,算法与数据结构,算法数据和数据结构,2001年,1,程序=算法+数据结构,软件：刻画现实世界，解决现实世界中的问题,语言：实现的工具,算法：解的描述（日常的：如魔方）,数据结构：现实世界的数据模型,程序=算法+数据结构,第一章：概论,2,几个例子（问题）,表达式解释,6+5*4=？,字符串匹配,串“ABCAC”出现在另一个串“ABCABCACAC”的第几个位置上,排序,一个序列，如何最快地对其进行排序,压缩编码,AAAABBBCDDE,?,图的最短路径,地理研究中的交通网络,第一章：概论,3,课程讲述的内容,上述问题的答案，包括,一些常用的数据结构类型以及其应用,与这些数据结构的有关算法,空间数据结构,第一章：概论,4,数据结构（一）,作为学科的数据结构,数据结构是研究非数值计算的程序设计问题中计算机的操作对象以及它们之间关系和操作等等的学科。,非数值计算,操作对象（数组）,第一章：概论,5,作为研究对象的数据结构,数据,数据项目,数据对象,数据结构,存在一种或多种特定关系的数据元素的集合,集合,关系,Data_Structure = (D,S),D:数据元素的有限集合,S:关系,第一章：概论,数据结构（二）,6,几个例子,图书管理,对弈,道路交叉口,数据结构的分类（例子）,集合,线性,树型,网状,第一章：概论,数据结构（三）,7,数据结构,物理结构,顺序存储,链式存储,抽象数据类型,数据类型（int,float）,抽象数据类型,原子类型,固定聚合类型,可变聚合类型,面向对象技术与数据结构,第一章：概论,数据结构（四）,8,算法,定义,为了完成特定任务指令的有穷序列,好的算法的特性,正确性,可读性,健壮性,效率和存储要求,第一章：概论,9,算法的效率,时间复杂性,问题规模,大O记法,空间复杂性,第一章：概论,10,线性表的定义,线性表的定义,唯一的第一个元素,唯一的最后一个元素,前驱,后继,第二章：线性表,1,2,3,n, ,11,相关概念和例子,数据项,纪录,文件,例子,字母表,数据库表,第二章：线性表,12,线性表操作（一）,初始化：Initiate,求长度：Length,得到第I个元素：Get,求前驱：Prior,求后继：Next,定位：Locate,插入：Insert,第二章：线性表,13,线性表操作（二）,删除操作：Delete,判断表是否为空：Empty,置空表操作：Clear,第二章：线性表,14,线性表的存储结构,顺序存储,链式存储,第二章：线性表,NULL,15,两种存储方式的比较,顺序存储,优点：元素访问方便,缺点：内存使用；插入删除不方便,链式存储,优点：内存利用好，插入删除方便,缺点：元素访问不方便,第二章：线性表,16,链式存储的代码（C）（一）,struct Node,Data_Type Data;,struct Node *pNext;,;,具体的两种实现,1：pHeader指针指向的地址存放数据,这样，链表为空时：,pHeader = NULL;(未分配任何空间),链表不为空时(一个元素)：,2：pHeader指针指向的地址不存放数据,链表为空时，分配了一个节点的空间。,第二章：线性表,pHeader,NULL,17,链式存储的代码（C）（二）,/得到第nIndex个元素,/注意的问题,/基0还是基1,/两种实现方式的不同，以下的代码是基1，第二种实现方式,Data_Type Get(struct Node *pHeader,int nIndex),struct Node *p = pHead;,for(int i=0;ipNext;,assert(p!=NULL);,return p-Data;,第二章：线性表,18,链式存储的代码（C）（三）,/向第nIndex个位置上插入数据元素dataInsert,void Insert(struct Node *pHeader,int nIndex,Data_Type dataInsert),struct Node *p = pHead;,struct Node *pInsert = new struct Node1;,pInsert-Data = dataInsert;(注意赋值),for(int i=0;ipNext;,assert(p!=NULL);,struct Node *pTemp = p-pNext;,p-pNext = pInsert;,pInsert-pNext = pTemp;,第二章：线性表,19,链式存储的代码（C）（四）,/删除第nIndex个位置上的数据元素,void Insert(struct Node *pHeader,int nIndex),struct Node *p = pHead;,for(int i=0;ipNext;,assert(p!=NULL);,struct Node *pTemp = p-pNext-Next;,delete p-pNext;,p-pNext = pTemp;,第二章：线性表,20,其它形式的链表,循环链表,表尾元素的pNext指针不为NULL,判断方式为是否等于pHeader,好处：从链表中任何一个节点都可以找到其它的节点。,双向链表,两个指针域,好处：可以进行两个方向的查找，但是插入和删除时比较麻烦。,第二章：线性表,21,栈,栈是限定于只在表尾进行插入和删除操作的线性表,后进先出（Last in first out,LIFO）,相关概念,栈顶（表尾）,栈底（表头）,第三章：栈和队列,22,栈的图示,栈底,栈顶,出栈,压栈,第三章：栈和队列,23,栈的操作,初始化：Inistack,判断栈是否为空：Empty,压栈：Push,弹栈：Pop,得到栈顶元素：GetTop,清空栈：Clear,得到栈的大小：Current_Size,第三章：栈和队列,24,表达式求值,4+2*3-10/5,表达式：操作数，运算符，界限符,操作数栈,算符栈,#算符，表示表达式的开始和结束,第三章：栈和队列,25,算符优先级,第三章：栈和队列,26,表达式求值算法,1：操作数栈置空，操作符栈压入算符“#”,2：依次读入表达式的每个单词,3：如果是操作数，压入操作数栈,4：如果是操作符，将操作符栈顶元素,1,与读入的操作符,2,进行优先级比较,4.1,如果栈顶元素优先级低，将,2,压入操作符栈,4.2如果相等，弹操作符栈,4.3如果栈顶元素优先级低，弹出两个操作数，一个运算符，进行计算，并将计算结果压入操作数栈，重复第4步的判断,5:直至整个表达式处理完毕,第三章：栈和队列,27,表达式求值的例子,3*(7-2)#,步骤 操作符栈 操作数栈 输入字符 操作,1 #,3,*(7-2)# 压入“3”,2 # 3,*,(7-2)# 压入“*”,3 #* 3,(,7-2)# 压入“(”,4 #*( 3,7,-2)# 压入“7”,5 #*( 37,-,2)# 压入“-”,6 #*(- 37,2,)# 压入“2”,7 #*(- 372,),# 弹出“-”压入7-2,8 #*( 35 )# 弹出“(”,9 #* 35 # 计算3*5,10 # 15 # 操作符栈空，结束,第三章：栈和队列,28,队列,队列的特点,先进先出，First in first out(FIFO),相关概念,队头,队尾,A1 A2 A3 A4 A5 An,入队,出队,队头（front）,队尾（rear）,第三章：栈和队列,29,队列的操作,初始化：InitQueue,判断是否为空：Empty,入队列：EnQueue,出队列：DlQueue,取队列头：GetHead,清空队列：Clear,得到队列长度：Current_size,第三章：栈和队列,30,队列的应用和实现,任务调度,打印任务,消息队列,排队模拟,队列的两种实现,链式存储,注意要有队尾指针,循环队列,第三章：栈和队列,31,串,定义：,零个或多个字符组成的有限序列,例子,“China”, “Boy and Girl”,应用,语言处理，如编译器,文本检索,专家系统,第四章：串,32,串的操作（一）,一个问题,串和线性表,操作：,赋值和创建：Assign,Create,判断是否相等：Equal,计算长度：Length,联结：Concat,求子串：SubStr,第四章：串,33,串的操作（二）,定位：Index,置换：Replace,插入：Insert,删除：Delete,34,串的存储实现,静态存储结构,数组,动态存储结构,链表,每个节点可以存储一个或多个数组,35,串的匹配KMP算法,一种朴素的匹配算法,KMP匹配算法,出发点：利用前面匹配的结果，进行无回溯匹配,一个示例匹配的讲解,模式串：abcac,主串：ababcabcacbab,36,串的匹配KMP算法,思考的开始：,假定：主串为 S,1,S,2,S,n,模式串为,P,1,P,2,P,m,无回溯匹配问题变为：当主串中的第i个字符和模式串中的第j个字符出现不匹配，主串中的第i个字符应该和模式串中的哪个字符匹配（无回溯）？,37,串的匹配KMP算法,进一步思考,假定主串中第i个字符与模式串第k个字符相比较，则应有,P,1,P,2,P,k,=S,i-k+1,S,i-k+2,S,i-1,问题可能有多个k，取哪一个？,而根据已有的匹配，有,P,j-k+1,P,j-k+2,P,j-1,=S,i-k+1,S,i-k+2,S,i-1,因此,P,j-k+1,P,j-k+2,P,j-1,=P,1,P,2,P,k-1,因此k值只和P以及j有关，定义为Nextj,38,串的匹配KMP算法,Nextj的定义,Nextj =,0,j=1时,Maxk|1kj and p,1,p,2,p,k-1,= p,j-k+1,p,j-1,1,其它情况,j,1 2 3 4 5 6 7 8,a b a a b c a c,0 1 1 2 2 3 1 2,Nextj,39,