算法与数据结构讲稿.pptx

《算法与数据结构讲稿.pptx》由会员分享，可在线阅读，更多相关《算法与数据结构讲稿.pptx（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法数据和数据结构刘宇2001年1算法和数据结构程序=算法+数据结构w软件：刻画现实世界，解决现实世界中的问题w语言：实现的工具w算法：解的描述（日常的：如魔方）w数据结构：现实世界的数据模型w程序=算法+数据结构第一章：概论2算法和数据结构几个例子（问题）w表达式解释6+5*4=？w字符串匹配串“ABCAC”出现在另一个串“ABCABCACAC”的第几个位置上w排序一个序列，如何最快地对其进行排序w压缩编码AAAABBBCDDE?w图的最短路径地理研究中的交通网络第一章：概论3算法和数据结构课程讲述的内容w上述问题的答案，包括w一些常用的数据结构类型以及其应用w与这些数据结构的有关算法w空间

2、数据结构第一章：概论4算法和数据结构数据结构（一）w作为学科的数据结构数据结构是研究非数值计算的程序设计问题中计算机的操作对象以及它们之间关系和操作等等的学科。非数值计算操作对象（数组）第一章：概论5算法和数据结构作为研究对象的数据结构数据数据项目数据对象数据结构存在一种或多种特定关系的数据元素的集合集合关系Data_Structure=(D,S)D:数据元素的有限集合S:关系第一章：概论数据结构（二）6算法和数据结构几个例子图书管理对弈道路交叉口数据结构的分类（例子）集合线性树型网状第一章：概论数据结构（三）7算法和数据结构数据结构物理结构顺序存储链式存储抽象数据类型数据类型（int,flo

3、at）抽象数据类型原子类型固定聚合类型可变聚合类型面向对象技术与数据结构第一章：概论数据结构（四）8算法和数据结构算法w定义为了完成特定任务指令的有穷序列w好的算法的特性正确性可读性健壮性效率和存储要求第一章：概论9算法和数据结构算法的效率w时间复杂性问题规模大O记法w空间复杂性第一章：概论10算法和数据结构线性表的定义w线性表的定义唯一的第一个元素唯一的最后一个元素前驱后继第二章：线性表123n 11算法和数据结构相关概念和例子w数据项w纪录w文件w例子字母表数据库表第二章：线性表12算法和数据结构线性表操作（一）w初始化：Initiatew求长度：Lengthw得到第I个元素：Getw求前

4、驱：Priorw求后继：Nextw定位：Locatew插入：Insert第二章：线性表13算法和数据结构线性表操作（二）w删除操作：Deletew判断表是否为空：Emptyw置空表操作：Clear第二章：线性表14算法和数据结构线性表的存储结构w顺序存储w链式存储第二章：线性表NULL15算法和数据结构两种存储方式的比较w顺序存储优点：元素访问方便缺点：内存使用；插入删除不方便w链式存储优点：内存利用好，插入删除方便缺点：元素访问不方便第二章：线性表16算法和数据结构链式存储的代码（C）（一）struct Node Data_Type Data;struct Node*pNext;具体的两种实

5、现1：pHeader指针指向的地址存放数据这样，链表为空时：pHeader=NULL;(未分配任何空间)链表不为空时(一个元素)：2：pHeader指针指向的地址不存放数据链表为空时，分配了一个节点的空间。第二章：线性表pHeaderNULL17算法和数据结构链式存储的代码（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);retu

6、rn p-Data;第二章：线性表18算法和数据结构链式存储的代码（C）（三）/向第nIndex个位置上插入数据元素dataInsertvoid 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;pIns

7、ert-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算法和数据结构其它形式的链表w循环链表表尾元素的pNext指针不为NULL判断方式为是否等于pHeader好处：从链表中任何一个节点都可以

8、找到其它的节点。w双向链表两个指针域好处：可以进行两个方向的查找，但是插入和删除时比较麻烦。第二章：线性表21算法和数据结构栈w栈是限定于只在表尾进行插入和删除操作的线性表w后进先出（Last in first out,LIFO）w相关概念栈顶（表尾）栈底（表头）第三章：栈和队列22算法和数据结构栈的图示栈底栈顶出栈压栈第三章：栈和队列23算法和数据结构栈的操作w初始化：Inistackw判断栈是否为空：Emptyw压栈：Pushw弹栈：Popw得到栈顶元素：GetTopw清空栈：Clearw得到栈的大小：Current_Size第三章：栈和队列24算法和数据结构表达式求值w4+2*3-10/

9、5w表达式：操作数，运算符，界限符w操作数栈w算符栈w#算符，表示表达式的开始和结束第三章：栈和队列25算法和数据结构算符优先级+-*/()#+-*/(#=第三章：栈和队列26算法和数据结构表达式求值算法w1：操作数栈置空，操作符栈压入算符“#”w2：依次读入表达式的每个单词w3：如果是操作数，压入操作数栈w4：如果是操作符，将操作符栈顶元素1与读入的操作符2进行优先级比较4.1如果栈顶元素优先级低，将2压入操作符栈4.2如果相等，弹操作符栈4.3如果栈顶元素优先级低，弹出两个操作数，一个运算符，进行计算，并将计算结果压入操作数栈，重复第4步的判断w5:直至整个表达式处理完毕第三章：栈和队列2

10、7算法和数据结构表达式求值的例子w3*(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-28#*(35 )#弹出“(”9#*35#计算3*510#15#操作符栈空，结束第三章：栈和队列28算法和数据结构队列w队列的特点先进先出，First in first out(FIFO)w相关概念队头队尾A1 A2 A3 A4 A5 An入队出队队头（front）队尾（rear

11、）第三章：栈和队列29算法和数据结构队列的操作w初始化：InitQueuew判断是否为空：Emptyw入队列：EnQueuew出队列：DlQueuew取队列头：GetHeadw清空队列：Clearw得到队列长度：Current_size第三章：栈和队列30算法和数据结构队列的应用和实现w任务调度打印任务消息队列排队模拟w队列的两种实现链式存储注意要有队尾指针循环队列第三章：栈和队列31算法和数据结构串w定义：零个或多个字符组成的有限序列w例子“China”,“Boy and Girl”w应用语言处理，如编译器文本检索专家系统第四章：串32算法和数据结构串的操作（一）w一个问题串和线性表w操作：

12、赋值和创建：Assign,Create判断是否相等：Equal计算长度：Length联结：Concat求子串：SubStr第四章：串33算法和数据结构串的操作（二）定位：Index置换：Replace插入：Insert删除：Delete34算法和数据结构串的存储实现w静态存储结构数组w动态存储结构链表每个节点可以存储一个或多个数组35算法和数据结构串的匹配KMP算法w一种朴素的匹配算法wKMP匹配算法出发点：利用前面匹配的结果，进行无回溯匹配一个示例匹配的讲解模式串：abcac主串：ababcabcacbab36算法和数据结构串的匹配KMP算法w思考的开始：假定：主串为 S1S2Sn 模式串为

13、 P1P2Pm无回溯匹配问题变为：当主串中的第i个字符和模式串中的第j个字符出现不匹配，主串中的第i个字符应该和模式串中的哪个字符匹配（无回溯）？37算法和数据结构串的匹配KMP算法w进一步思考假定主串中第i个字符与模式串第k个字符相比较，则应有P1P2Pk=Si-k+1Si-k+2Si-1问题可能有多个k，取哪一个？而根据已有的匹配，有Pj-k+1Pj-k+2Pj-1=Si-k+1Si-k+2Si-1因此Pj-k+1Pj-k+2Pj-1=P1P2Pk-1因此k值只和P以及j有关，定义为Nextj38算法和数据结构串的匹配KMP算法wNextj的定义wNextj=0,j=1时Maxk|1kj and p1p2pk-1=pj-k+1pj-11,其它情况j1 2 3 4 5 6 7 8 a b a a b c a c 0 1 1 2 2 3 1 2Nextj39算法和数据结构