算法和数据结构

《算法和数据结构》由会员分享，可在线阅读，更多相关《算法和数据结构（199页珍藏版）》请在金锄头文库上搜索。

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

2、些常用的数据结构类型以及其应用 w 与这些数据结构的有关算法 w 空间数据结构第一章：概论4 算法和数据结构数据结构（一）w 作为学科的数据结构数据结构是研究非数值计算的程序设计问 题中计算机的操作对象以及它们之间关系 和操作等等的学科。 非数值计算 操作对象（数组）第一章：概论5 算法和数据结构作为研究对象的数据结构 数据（和信息的关系） 数据项目 数据对象第一章：概论数据结构（二）6 算法和数据结构数据n n数据是信息的载体，是描述客观事数据是信息的载体，是描述客观事 物的数、字符、以及所有能输入到物的数、字符、以及所有能输入到 计算机中，被计算机程序识别和处计算机中，被计算机程序识别和处

3、 理的符号的集合。理的符号的集合。uu 数值性数据数值性数据uu 非数值性数据非数值性数据7 算法和数据结构数据元素n n数据的数据的基本单位基本单位。在计算机程序中。在计算机程序中 常作为一个整体进行考虑和处理。常作为一个整体进行考虑和处理。n n有时一个数据元素可以由若干有时一个数据元素可以由若干数据数据 项项(Data Item)(Data Item)组成。组成。数据项数据项是是具有具有 独立含义的最小标识单位独立含义的最小标识单位。n n数据元素又称为元素、结点、记录数据元素又称为元素、结点、记录 。8 算法和数据结构数据对象n n数据的子集。具有相同性质的数据数据的子集。具有相同性质

4、的数据 成员（数据元素）的集合。成员（数据元素）的集合。uu整数数据对象整数数据对象 N N = 0, = 0, 1, 1, 2, 2, uu学生数据对象学生数据对象9 算法和数据结构数据结构（三）树形关系树形关系网状关系网状关系152436152436数据结构：存在一种或多种特定关系的数据 元素的集合 集合关系 Data_Structure = (D,S) D:数据元素的有限集合 S:关系10 算法和数据结构几个例子 图书管理 对弈 道路交叉口 数据结构的分类（例子） 集合 线性 树型 网状第一章：概论数据结构（三）11 算法和数据结构数据结构物理结构 顺序存储 链式存储 抽象数据类型 数据

5、类型（int,float） 抽象数据类型 原子类型 固定聚合类型 可变聚合类型 面向对象技术与数据结构第一章：概论数据结构（四）12 算法和数据结构抽象数据类型(ADT)uu由用户定义，用以表示应用问题由用户定义，用以表示应用问题 的的数据模型数据模型uu由由基本的数据类型基本的数据类型组成组成, , 并包括并包括 一组相关的服务一组相关的服务（或称操作）（或称操作）uu信息隐蔽信息隐蔽和和数据封装数据封装，使用与实，使用与实 现相分离现相分离13 算法和数据结构算法w 定义为了完成特定任务指令的有穷序列 w 好的算法的特性正确性 可读性 健壮性 效率和存储要求第一章：概论14 算法和数据结构

6、算法的特性uu 输入输入 有有0 0个或多个输入个或多个输入uu 输出输出 有一个或多个输出有一个或多个输出( (处理结果处理结果) )uu 确定性确定性 每步定义都是确切、无歧义每步定义都是确切、无歧义 的的uu 有穷性有穷性 算法应在执行有穷步后结束算法应在执行有穷步后结束uu 有效性有效性 每一条运算应足够基本每一条运算应足够基本15 算法和数据结构算法的效率w 时间复杂性问题规模 大O记法 w 空间复杂性第一章：概论16 算法和数据结构线性表的定义w 线性表的定义唯一的第一个元素 唯一的最后一个元素 前驱 后继第二章：线性表123n 17 算法和数据结构相关概念和例子w 数据项 w 纪

7、录 w 文件 w 例子字母表 数据库表第二章：线性表18 算法和数据结构线性表操作（一）w 初始化：Initiate w 求长度：Length w 得到第I个元素：Get w 设置第I个元素：Set w 求前驱：Prior w 求后继：Next w 定位：Locate w 插入：Insert第二章：线性表19 算法和数据结构线性表操作（二）w 删除操作：Delete w 判断表是否为空：Empty w 置空表操作：Clear第二章：线性表20 算法和数据结构线性表模板类的定义(按值访问)template class LinearList public: void Initiate(); int

8、 Length(); T GetAt(int nIndex); void SetAt(int nIndex, T newValue); T Prior(T Value); T Next(T Value); int Locate(T Value); bool Insert(int nIndex, T Value); void Delete(int nIndex); bool IsEmpty(); void Clear(); ;21 算法和数据结构线性表模板类的定义(按地址访问 )typedef voide * POSITION; template class LinearList public:

9、 void Initiate(); int Length(); POSITION GetAt(int nIndex); T T POSITION Prior(POSITION p); POSITION Next(POSITION p); int Locate(POSITION p); bool Insert(int nIndex, T Value); void Delete(int nIndex); bool IsEmpty(); void Clear(); ;22 算法和数据结构线性表的存储结构w 顺序存储w 链式存储第二章：线性表NULL23 算法和数据结构两种存储方式的比较w 顺序存储优

10、点：元素访问方便 缺点：内存使用；插入删除不方便 w 链式存储优点：内存利用好，插入删除方便 缺点：元素访问不方便第二章：线性表24 算法和数据结构两种存储方式的模板类声明(1)顺序存储 template class LinearList private: T *m_pData; int m_nAllocatedSize;/线性表分配内存长度 int m_nSize;/线性表实际长度 public: . ;25 算法和数据结构两种存储方式的模板类声明(2)链式存储 template class LinearList private: struct Node T Data; struct Nod

11、e *pNext; ; struct Node *m_pHeader; public: . ;26 算法和数据结构链式存储的代码（C）（一）struct Node Data_Type Data; struct Node *pNext; ; 具体的两种实现 1：pHeader指针指向的地址存放数据 这样，链表为空时： pHeader = NULL;(未分配任何空间) 链表不为空时(一个元素)：2：pHeader指针指向的地址不存放数据 链表为空时，分配了一个节点的空间。第二章：线性表pHeaderNULL27 算法和数据结构链式存储的代码（C）（二）/得到第nIndex个元素 /注意的问题 /基

12、0还是基1 /两种实现方式的不同，以下的代码是基0，第二种实现方式 Template T LinearList:Get(int nIndex) struct Node *p = pHeader; for(int i=0;ipNext; assert(p!=NULL); return p-Data; 第二章：线性表28 算法和数据结构链式存储的代码（C）（三）/向第nIndex个位置上插入数据元素dataInsert Template void LinearList:Insert(int nIndex, T dataInsert) struct Node *p = m_pHeader; stru

13、ct Node *pInsert = new struct Node1; pInsert-Data = dataInsert;(注意赋值) for(int i=0;ipNext; assert(p!=NULL); pInsert-pNext = p-pNext; p-pNext = pInsert; 第二章：线性表29 算法和数据结构链式存储的代码（C）（四）/删除第nIndex个位置上的数据元素 Template void LinearList:Delete(int nIndex) struct Node *p = m_pHeader; for(int i=0;ipNext; assert(

14、p!=NULL); assert(p-pNext!=NULL); struct Node *pTemp = p-pNext-pNext; delete p-pNext; p-pNext = pTemp; 第二章：线性表30 算法和数据结构其它形式的链表w 循环链表 表尾元素的pNext指针不为NULL判断方式为是否等于pHeader好处：从链表中任何一个节点都可以找到其它的 节点。 w 双向链表两个指针域好处：可以进行两个方向的查找，但是插入和删 除时比较麻烦。第二章：线性表31 算法和数据结构线性表的应用多项式表达w wn n 阶多项式阶多项式 Pn(x) 有有 n n+1 +1 项项。 系

15、数系数 c c0, 0, c c1, 1, c c2, , 2, , cncn 指数指数 0, 1, 2, , 0, 1, 2, , n n。按升幂排列。按升幂排列32 算法和数据结构多项式的顺序表表示w 定义数据元素的类型 struct Term double coef; int exp; ; w 定义一个多项式对象 LinearList polynomial;33 算法和数据结构多项式的加法算法w 扫描两个多项式，若都未检测完：若当前被检测项指数相等，系数相加。若 未变成 0，则将结果加到结果多项式。两个 多项式各后移一项； 若当前被检测项指数不等，将指数小者加 到结果多项式，并后移一项。 w 若一个多项式已检测完，将另一个多项 式剩余部分复制到结果多项式。34 算法和数据结构栈w 栈是限定于只在表尾进行插入和删除操 作的线性表 w 后进先出（Last in first out,LIFO）w 相关概念栈顶（表尾） 栈底（表头）第三章：栈和队列35 算法和数据结构栈的图示栈底栈顶出栈压栈第三章：栈和队列36 算法和数据结构栈的操作w 初始化：Inistack w 判断栈是否为空：Empty w 压栈：Push w 弹栈：Pop w 得到栈顶元素：GetTop w 清空栈：Clear w 得到栈的大小：Current_Siz