算法与数据结构讲稿.ppt

算术数据和数据结构，2001，程序=算术数据结构，软件：真实世界的描述，用于解决真实世界中的问题的语言：实现的工具和算法：解决方案的描述(每日：魔方)数据结构：真实世界的数据模型程序=算术数据结构，第1章：介绍，几个例子(问题)，表达式解释6 5*4=？匹配字符串“ABCAC”的字符串出现在另一个字符串“ABCABCACAC”的位置，对序列进行排序。如何尽快对其进行分类、压缩和编码？交通网络中最短路径图的地理研究，第一章：导论，课程内容，对上述问题的回答，包括一些常用的数据结构类型及其应用以及这些数据结构的相关算法空间数据结构，第一章：导论，数据结构(1)，数据结构作为一门学科，是研究计算机在非数值计算编程问题中的运算对象、它们的关系和运算等的一门学科。非数值计算操作对象(数组)，第1章：引言，数据结构数据项数据对象数据结构作为研究对象数据元素集关系数据结构=(D，S)D:有限集S:数据元素关系，第1章：引言，数据结构(2)，图书管理游戏集线性树网络中道路交叉口数据结构的几个实例分类(实例)，第1章：引言，数据结构(3)， 数据结构物理结构顺序存储链存储抽象数据类型数据类型(int，float)抽象数据类型原子类型固定聚合类型可变聚合类型面向对象技术和数据结构，第1章：简介，数据结构(4)，算法，定义完成特定任务指令的好算法的有限序列的特征、正确性、可读性、健壮性、效率和存储要求。 第一章：绪论，算法效率，大规模时间复杂度问题，O符号，空间复杂度。第一章：引言，线性表的定义，线性表的定义，唯一的第一个元素，唯一的最后一个元素的前身和继承者。第二章：线性表，1，2，3，N，相关概念和示例。数据项记录文件示例字母表数据库表，第2章：线性表，线性表操作(1)，初始化：初始化长度：获取第一个元素的长度：获取前一个元素：获取前一个元素：获取后一个元素：下一个元素：定位：插入，第2章：线性表，线性表操作(2)，删除操作：删除以确定表是否为空：空以设置空表操作：清除，第2章：线性表，线性表的存储结构，顺序存储链存储，第2章：线性表、空，两种存储方法的比较，顺序存储的优点：方便的元素访问，缺点：内存使用；插入和删除不便于链存储。优点：内存利用率高，插入和删除方便。缺点：不方便进入元件。第二章：线性表，链存储代码(C) (1)，结构节点数据_类型数据；结构节点* pNext；两个具体的实现是：1 .p头指针指向的地址存储数据，所以当链表为空时：pHeader=NULL(未分配空间)当链表不为空时(一个元素):2:P头指针指向的地址不存储数据。当链表为空时，分配一个节点的空间。第2章：线性表，P头，空，链存储代码(C) (II)，/获取nIndex元素/注释问题/基0或基1/下面的代码是基1，第二个实现是数据类型获取(结构节点* P头，IntIndex)结构节点* P=Phead对于(inti=0；ipNext。断言(p！=空)；返回-数据；，第2章：线性表，链存储代码(C)(三)，/插入数据元素数据插入无效插入(结构节点* P头，输入索引，数据_类型插入)结构节点* P=插入到索引位置；结构节点*输入=新结构节点1；引脚插入-数据=数据插入；(注释赋值)用于(inti=0；ipNext。断言(p！=空)； StructNode * PTeMP=p-PnExt；p-PnExt=PinSert；pInsert-pNext=pTemp。，第2章：线性表，链存储代码(c) (iv)，/删除数据元素void insert (structnode * p header，intnIndex) struct node * p=phead in position nindex；对于(inti=0；ipNext。断言(p！=空)； StructNode * PTeMP=p-PnExt-下一步；删除p-pNext；p-pNext=pTemp。，第2章：线性表，其他形式的链表，循环链表的结束元素的pNext指针不为空。判断方法是它是否等于pHeader的好处：可以从链表中的任何节点找到其他节点。具有两个指针字段的双链表的优点：它可以在两个方向上搜索，但是插入和删除很麻烦。第2章：线性表、堆栈、堆栈仅限于与仅在表的末尾插入和删除的线性表相关的后进先出概念。第3章：堆栈和队列，堆栈图，堆栈底部，堆栈顶部，推入堆栈，第3章：堆栈和队列，堆栈操作，初始化：插入判断堆栈是否为空：空堆栈：推入堆栈：弹出获取堆栈顶部元素：GetTop清空堆栈：清除获取堆栈大小：Current_Size，第3章：堆栈和队列，表达式求值，4 2*3-10/5表达式：操作数，运算符，边界运算符，堆栈运算符堆栈#运算符，它指示表达式的开始和结束。第3章：堆栈和队列，运算符优先级，第3章：堆栈和队列，表达式求值算法，1:操作数堆栈为空，运算符堆栈按运算符“#”2:表达式的每个字按顺序读取3:如果是操作数，则按操作数堆栈4:如果是运算符，则比较运算符堆栈顶部元素1和读取运算符2 4.1的优先级，如果堆栈顶部元素的优先级较低， 将2按入运算符堆栈4.2(如果相等)，Bomb运算符堆栈4.3如果堆栈的顶部元素具有低优先级，则弹出两个操作数和一个运算符来执行计算，将计算结果推入操作数堆栈，重复步骤4中的判断5:直到处理完整个表达式。 第3章：堆栈和队列，表达式求值示例，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)#弹出“-”.一、进入、退出、前、后、第3章：堆栈和队列、队列操作、初始化：初始化队列判断是否为空：空入队列：入队出队列：DlQueue取队列头：GetHead清空队列：Clear获取队列长度：Current_size、第3章：堆栈和队列、队列的应用和实现、任务调度和打印、任务消息队列队列模拟队列的两种实现、链存储、 应注意队列尾指针循环队列，第三章：堆栈和队列，字符串，定义：零个或多个字符的有限序列示例“中国”和“博扬德吉尔”应用语言处理，如编译器文本检索专家系统.第四章：字符串，字符串操作(1)，问题字符串和线性表操作：赋值和创建：赋值，创建判断是否相等：相等计算长度：长度连接：串联查找子字符串：子字符串，第四章：字符串，字符串操作(2)，位置：索引替换：替换插入：插入删除：删除，字符串存储实现，静态存储结构数组动态存储结构列表每个节点可以存储一个或多个数组。字符串匹配KMP算法，简单匹配算法KMP匹配算法起点：利用前面匹配的结果，举例说明非回溯匹配模式字符串：abcac主字符串：ababcabab，字符串匹配KMP算法，思路起点：假设：主字符串是S1S2Sn.sn模式字符串是P1P2Pm.pm无回溯匹配问题变成：当主字符串中的第I个字符与模式字符串中的第j个字符不匹配时，主字符串中的第I个字符应该与模式字符串中的哪个字符匹配，字符串匹配算法KMP，进一步思考假设主字符串中的第I个字符与模式字符串中的第K个字符比较，应该有P