算法数据和数据结构.ppt

算法和数据结构 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 线性表的定义 线性表的定义唯一的第一个元素唯一的最后一个元素前驱后继 第二章 线性表 1 2 3 n 算法和数据结构 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 ipNext 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 ipNext 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 ipNext 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