算法与数据结构讲稿

算法数据和数据结构刘宇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*第十页，共四十页。线性表的定义线性表的定义唯一的第一个元素唯一的最后一个元素前驱后继第二章：线性表123n……11*第十一页，共四十页。相关概念和例子数据项纪录文件例子字母表数据库表第二章：线性表12*第十二页，共四十页。线性表操作（一）初始化：Initiate求长度：Length得到第I个元素：Get求前驱：Prior求后继：Next定位：Locate插入：Insert第二章：线性表13*第十三页，共四十页。线性表操作（二）删除操作：Delete判断表是否为空：Empty置空表操作：Clear第二章：线性表14*第十四页，共四十页。线性表的存储结构顺序存储链式存储第二章：线性表NULL……15*第十五页，共四十页。两种存储方式的比较顺序存储优点：元素访问方便缺点：内存使用；插入删除不方便链式存储优点：内存利用好，插入删除方便缺点：元素访问不方便第二章：线性表16*第十六页，共四十页。链式存储的代码（C）（一）structNode{ Data_TypeData; structNode*pNext;};具体的两种实现1：pHeader指针指向的地址存放数据 这样，链表为空时： pHeader=NULL;(未分配任何空间) 链表不为空时(一个元素)：

2：pHeader指针指向的地址不存放数据 链表为空时，分配了一个节点的空间。第二章：线性表pHeaderNULL17*第十七页，共四十页。链式存储的代码（C）（二）//得到第nIndex个元素//注意的问题//基0还是基1//两种实现方式的不同，以下的代码是基1，第二种实现方式Data_TypeGet(structNode*pHeader,intnIndex){ structNode*p=pHead; for(inti=0;i<nIndex;i++) { p=p->pNext; assert(p!=NULL); } returnp->Data;}第二章：线性表18*第十八页，共四十页。链式存储的代码（C）（三）//向第nIndex个位置上插入数据元素dataInsertvoidInsert(structNode*pHeader,intnIndex,Data_TypedataInsert){ structNode*p=pHead; structNode*pInsert=newstructNode[1]; pInsert->Data=dataInsert;(注意赋值) for(inti=0;i<nIndex-1;i++) { p=p->pNext; assert(p!=NULL); } structNode*pTemp=p->pNext; p->pNext=pInsert; pInsert->pNext=pTemp;}第二章：线性表19*第十九页，共四十页。链式存储的代码（C）（四）//删除第nIndex个位置上的数据元素voidInsert(structNode*pHeader,intnIndex){ structNode*p=pHead; for(inti=0;i<nIndex-1;i++) { p=p->pNext; assert(p!=NULL); } structNode*pTemp=p->pNext->Next; delete[]p->pNext; p->pNext=pTemp;}第二章：线性表20*第二十页，共四十页。其它形式的链表循环链表表尾元素的pNext指针不为NULL判断方式为是否等于pHeader好处：从链表中任何一个节点都可以找到其它的节点。双向链表两个指针域好处：可以进行两个方向的查找，但是插入和删除时比较麻烦。第二章：线性表21*第二十一页，共四十页。栈栈是限定于只在表尾进行插入和删除操作的线性表后进先出（Lastinfirstout,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#*(37-2)#压入“7”5#*(37-2)#压入“-”6#*(-372)#压入“2”7#*(-372)#弹出“-”压入7-28#*(35)#弹出“(”9#*35#计算3*510#15#操作符栈空，结束第三章：栈和队列28*第二十八页，共四十页。队列队列的特点先进先出，Firstinfirstout(FIFO)相关概念队头队尾A1A2A3A4A5……An入队出队队头（front）队尾（rear）第三章：栈和队列29*第二十九页，共四十页。队列的操作初始化：InitQueue判断是否为空：Empty入队列：EnQueue出队列：DlQueue取队列头：GetHead清空队列：Clear得到队列长度：Current_size第三章：栈和队列30*第三十页，共四十页。队列的应用和实现任务调度打印任务消息队列排队模拟队列的两种实现链式存储注意要有队尾指针循环队列第三章：栈和队列31*第三十一页，共四十页。串定义：零个或多个字符组成的有限序列例子“China”,“BoyandGirl”应用语言处理，如编译器文本检索专家系统…第四章：串32*第三十二页，共四十页。串的操作（一）一个问题串和线性表操作：赋值和创建：Assign,Create判断是否相等：Equal计算长度：Length联结：Concat求子串：SubStr第四章：串33*第三十三页，共四十页。串的操作（二）定位：Index置换：Replace插入：Insert删除：Delete34*第三十四页，共四十页。串的存储实现静态存储结构数组动态存储结构链表每个节点可以存储一个或多个数组35*第三十五页，共四十页。串的匹配——KMP算法一种朴素的匹配算法KMP匹配算法出发点：利用前面匹配的结果，进行无回溯匹配一个示例匹配的讲解模式串：abcac主串：ababcabcacbab36*第三十六页，共四十页。串的匹配——KMP算法思考的开始：假定：主串为S1S2…Sn

模式串为

P1P2…Pm无回溯匹配问题变为：当主串中的第i个字符和模式串中的第j个字符出现不匹配，主串中的第i个字符应该和模式串中的哪个字符匹配（无回溯）？37*第三十七页，共四十页。串的匹配——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]38*第三十八页，共四十页。串的匹配——KMP算法Next[j]的定义Next[j]=0,j=1时Max{k|1<k<jandp1p2…pk-1=pj-k+1…pj-1}1,其它情况j12345678abaabcac01122312Next[j]39*第三十九页，共四十页。内容总结算法数据和数据结构。算法和数据结构。软件：刻画现实世界