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