算法数据和数据结构.ppt

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