算法与数据结构讲稿

算法和数据结构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线性表的定义线性表的定义–唯一的第一个元素–唯一的最后一个元素–前驱–后继第二章：线性表123n……算法和数据结构12相关概念和例子数据项纪录文件例子–字母表–数据库表第二章：线性表算法和数据结构13线性表操作（一）初始化：Initiate求长度：Length得到第I个元素：Get求前驱：Prior求后继：Next定位：Locate插入：Insert第二章：线性表算法和数据结构14线性表操作（二）删除操作：Delete判断表是否为空：Empty置空表操作：Clear第二章：线性表算法和数据结构15线性表的存储结构顺序存储链式存储第二章：线性表NULL……算法和数据结构16两种存储方式的比较顺序存储–优点：元素访问方便–缺点：内存使用；插入删除不方便链式存储–优点：内存利用好，插入删除方便–缺点：元素访问不方便第二章：线性表算法和数据结构17链式存储的代码（C）（一）structNode{Data_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;inIndex;i++){p=p-pNext;assert(p!=NULL);}returnp-Data;}第二章：线性表算法和数据结构19链式存储的代码（C）（三）//向第nIndex个位置上插入数据元素dataInsertvoidInsert(structNode*pHeader,intnIndex,Data_TypedataInsert){structNode*p=pHead;structNode*pInsert=newstructNode[1];pInsert-Data=dataInsert;(注意赋值)for(inti=0;inIndex-1;i++){p=p-pNext;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;inIndex-1;i++){p=p-pNext;assert(p!=NULL);}structNode*pTemp=p-pNext-Next;delete[]p-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)相关概念–队头–队尾A1A2A3A4A5……An入队出队队头（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算法思考的开始：–假定：主串为S1S2…Sn–模式串为P1P2…Pm–无回溯匹配问题变为：当主串中的第i个字符和模式串中的第j个字符出现不匹配，主串中的第i个字符应该和模式串中的哪个字符匹配（无回溯）？算法和数据结构38串的匹配——KMP算法进一步思考–假定主串中第i个字符与模式串第k个字符相比较，则应有•P1P2…Pk=Si-k+1Si-k+2…Si-1•问题可能有多个k，取哪一个？–而根据已有的匹配，有•Pj-k+1Pj-k+2…Pj-1=Si-k+1Si-k+2…Si-1–因此•Pj-k+1Pj-k+2…Pj-1=P1P2…Pk-1–因此k值只和P以及j有关，定义为Next[j]算法和数据结构39串的匹配——KMP算法Next[j]的定义Next[j]=0,j=1时Max{k|1kjandp1p2…pk-1=pj-k+1…pj-1}1,其它情况j12345678abaabcac01122312Next[j]