数据结构域算法设计-第一二章 绪论、线性表l 课件

《数据结构域算法设计-第一二章 绪论、线性表l 课件》由会员分享，可在线阅读，更多相关《数据结构域算法设计-第一二章 绪论、线性表l 课件（106页珍藏版）》请在金锄头文库上搜索。

1、数据结构电子讲义主讲教师：王 力 辅导：艾妮、栾岚 2003年2月24日-7月 Email: wangl_ 电话：4730230Ver 1.0版注意事项l1、为何要学习数据结构l2、如何学习数据结构l3、作业与实验报告l4、重要参考书目为何学习数据结构课程l l它研究了计算机需要处理的数据对象和它研究了计算机需要处理的数据对象和 对象之间的关系。对象之间的关系。l l它刻画了应用中涉及到的数据的逻辑组它刻画了应用中涉及到的数据的逻辑组 织。织。l l它描述了数据在计算机中如何存储、传它描述了数据在计算机中如何存储、传 送、转换。送、转换。l l它是计算机专业的核心课程。是学习操它是计算机专业的

2、核心课程。是学习操 作系统、编译原理、数据库系统原理的作系统、编译原理、数据库系统原理的 先行课程先行课程如何学习数据结构课程l1、反复阅读教材经验：5遍以上才可能掌握某些概念与 技巧。l2、认真按时完成作业l3、认真完成实验并写出实验报告l4、与同学讨论l5、多阅读相关书籍，看别人怎么说作业、实验报告和纪律l1、作业要求：按时完成，按时交。2次或2次以上不 交或不按时交者，不能参加考试。l2、实验报告要求：按时完成，按时交。1次或1次以上不 交或不按时交者，不能参加考试。l3、课堂纪律：1次实验不参加，或3次理论课不参加 者不能参加考试。重要参考书目1. 严蔚敏等著 数据结构 清华大学出版社

3、 1998 2. 谢楚屏等编著 数据结构 人民邮电出版社3. 徐绪松等著 数据结构与算法导论电子工业出版社4. D.E.Knuth著 计算机程序设计技巧第一、三 卷 管纪文译 国防出版社5.（ 美）Sartaj Sahni著数据结构算法与应用汪诗林等译 机械工业出版社6. 徐孝凯 编著数据结构实用教程（C/C+描述清华大学出版社第一章 绪 论1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分1.4.1 算法1.4.2 算法设计的要求1.4.3 算法效率的度量1.4.4 算法的存储空间的需求数据结构研究的问题l数据表示数据以何种方式表示，数据以

4、何种方 式存储等l数据处理对数据的操作，如插入、删除、修改 、显示、排序、查找等。1.1什么是数据结构一、几个实例 例1、图书馆的书目检索系统自动化问题（P1）可以建立一张按登号顺序排列的书目文件和三张分别 按书名、作者和分类号顺序排列的索引表。（线性结 构） 例2、计算机人机对奕问题（P1-2）格局：对奕过程中某一时刻可能出现的棋盘状态。着法：对奕双方可以走的位置（方法）。对奕过程：格局从开始进一步扩展到某个格局（终局 ）的过程由于A方完成某一“着法”后，棋盘格局发生了变化，B 方又有很多“着法”应对。（树形结构） 例3、多叉路口交通灯的管理问题（P3）以图的一个顶点表示一条通路，而通路之间

5、互相矛盾的 关系以两个顶点之间的连线表示。数学模型为：对图 的着色问题。（图或网络结构）登录号： 书名： 作者名： 分类号： 出版单位： 出版时间： 价格：书目卡片书目文件按书名按作者名按分类号索引表线性表例1、图书馆的书目检索系统自动化问题（P1）例2 人机对奕问题树.格 局着法例3 多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图AB，AC，AD， BA，DC，EDBC，BD，EA二、什么是数据结构通过以上几例可以直接地认为：数据结构就是研究数据的逻辑结构 和物理结构以及它们之间相互关系，并 对这种结构定义相应的运算，而且确保 经过这些运算后所得到的新

6、结构仍然是 原来的结构类型。三、数据结构学科的发展l1968年，国外开始该门课程的教学l70年代初，结构化程序设计成为程序设 计的方法学。程序=数据结构+算法l发展方向。（1）面向专门领域，如多维图形数结 构（2）用抽象数据类型来表示数据结构 。1.2 基本概念和术语一、基本概念 1、数据(Data):是对信息的一种符号表示。在计算机科学中 是指所有能输入到计算机中并被计算机程序处理的符号的 总称。又称信息的载体。 2、数据元素(Data Element):是数据的基本单位，在计算机 程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据 的不可分割的最小单位（原

7、子项）。 3、数据对象(Data Object)：是性质相同的数据元素的集合 。是数据的一个子集。又称数据元素的实例，可分为变量 、常量。如整数1,2,3,4;字符串“letter“,“string“等 4、数据结构(Data Structure)：数据元素及定义在数据元 素上的关系的集合。6、结构：指数据元素之间的相互关系。可 分为：逻辑结构：只抽象反映数据元素逻辑关 系。 存储（物理）结构：数据的逻辑结 构在计算机存储器中的实现。（1）集合 结构中的数据元素除了同属于一种类 型外，别无其它关系。（2）线性结构 结构中的数据元素之间存在一 对一的关系。（3）树型结构 结构中的数据元素之间存在

8、 一对多的关系。（4）图状结构或网状结构 结构中的数据元素 之间存在多对多的关系。集合结构：线性关系树形结构树形结构bindevetclibuser1014131211123456789树树3158710119613二叉树二叉树 987456231二叉搜索树二叉搜索树堆结构“最大最大”堆堆 “最小最小”堆堆123548711102916410121151236987图结构图结构 网络结构网络结构12564312543611 331814665161921二、数据结构的形式化定义1、定义 ：数据结构是一个二元组：Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有

9、限集 。例 复数的数据结构定义如下：Complex=(C，R)其中：C是含两个实数的集合C1，C2，分别表 示复数的实部和虚部。R=P，P是定义在集合上的 一种关系C1，C2。2、数据的物理存储存储结构分为： 顺序存储结构借助元素在存储器中的相对位置来表示数据元素间的逻辑关系 链式存储结构借助指示元素存储地址的指针表示数据元素间的逻辑关系算法设计逻辑结构算法实现存储结构元素n.元素i.元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储设一个元素占m 个字节，则n 个 元素顺序存储在 内存中的映象如 左图。如果知道了第1

10、 个元素的首地址 ，则可直接计算 出第i个元素的地 址。1536元素21400元素11346元素3元素41345存储地址 存储内容 指针1345 元素1 14001346 元素4 . . .1400 元素2 1536. . .1536 元素3 1346链式存储 h1、数据类型：高级语言中指数据的取值范围及 其上可进行的操作的总称例 C语言中，提供int, char, float, double等基本数据类型，数组、结构体、共用体、枚举等构造数据类型，还有指针、空(void)类型等。用户也可用typedef 自己定义数据类型typedef struct int num;char name20;f

11、loat score; STUDENT; STUDENT stu1,stu2, *p;三、数据类型与抽象数据类型2、抽象数据类型 (ADTs: Abstract Data Types)- -由用户定义，用以表示应用问题的由用户定义，用以表示应用问题的数据模型数据模型- -由由基本的数据类型基本的数据类型组成组成, , 并包括并包括一组相关的一组相关的 服务服务（或称操作）（或称操作） - -信息隐蔽信息隐蔽和和数据封装数据封装，使用与实现相分离，使用与实现相分离简而言之：抽象数据类型是指一个数学模型简而言之：抽象数据类型是指一个数学模型 以及定义在该模型上的一组操作。以及定义在该模型上的一组操

12、作。抽 象 数 据 类 型查找 登录 删除 修改 符 号 表抽象数据类型的定义ADT 抽象数据类型名 数据对象: (数据对象的定义）数据关系: (数据关系的定义）基本操作: (基本操作的定义） ADT抽象数据类型名 最后的“ADT.”串可省略 其中数据对象与数据关系用伪码表示 基本操作的定义为：基本操作名（参数表）初始条件：操作结果：抽象数据类型实例1（P9）ADT Triplet 数据对象：D= 数据关系：R1=. 基本操作：InitTriplet()操作结果：DestroyTriplet(.)操作结果： ADT Triplet数据的逻辑结构 数据的存储结构 数据的运算：检索、排序、插入、删

13、除、修改等 线性结构 非线性结构顺序存储链式存储 线性表 栈 队树形结构图形结构数据结构的三个方面：1.3 抽象数据型的表示与实现lP9-P13 自学1.4 算法和算法表示1.4.1 算法及特点 （algorithm）解决某一特定问题的具体的有顺序 的步骤的描述，是指令的有限序列。 特点：（1）有穷性：算法的步骤是有限的。（2）确定性：算法的每个步骤须无二义性。（3）可行性：算法是可以实现的。（4）输入：算法可以有0到多个输入。（5）输出：至少应该有一个输出。1.4.2 算法的设计要求1、正确性：算法应该满足具体问题的需求。无语法错误，无语义错误，对于预期的输入总 能得到预期的结果。 2、可读

14、性：算法的书写应该易于阅读。可移植性，可维护性 3、健壮性：算法应该对系统可能出现的各种异 常进行提示及处理。 4、效率：花费时间及存储空间。时间与空间是此消彼涨的关系。可用空间换时 间，也可用时间来换空间。1.4.3算法效率的度量一、算法效率用依据该算法编制的程序在计算机上执行所消耗的 时间来度量1.事后统计利用计算机内记时功能，不同算法的程序可以 用一组或多组相同的统计数据区分缺点：必须先运行依据算法编制的程序所得时间统计量依赖于硬件、软件等环境因素，掩盖 算 法本身的优劣2.事前分析估计一个高级语言程序在计算机上运行所消耗 的时间取决于：依据的算法选用何种策略 问题的规模程序语言 编译程

15、序产生机器代码质量机器执行指令速度二、算法时间复杂度同一个算法用不同的语言、不同的 编译程序、在不同的计算机上运行，效 率均不同，所以使用这些因素来 衡量算法效率不合适1、时间复杂度的组成l lT T（P)=P)=编译时间编译时间+ +运行时间运行时间 但是由于程序一但编译完后，就不需再编译。只需关但是由于程序一但编译完后，就不需再编译。只需关 注运行时间即可，运行时间常用注运行时间即可，运行时间常用“ “t tp p( (问题特征问题特征)“)“来来 表示表示( (c ci i表示一个运算表示一个运算i i执行的时间，执行的时间，e ei i(n)(n)表示运算表示运算i i出现的次数，出现的次数，n n表示问题表示问题p p的规模的规模) ) 由于不同的数据类型做相同的操作其运算时间也不同由于不同的数据类型做相同的操作其运算时间也不同 ，因此，增加了时间复杂度的计算。，因此，增加了时间复杂度的计算。 可操作的方法：可操作的方法：（1 1）找出一个或多个关键操作，确定这些关键）找出一个或多个关键操作，确定这些关键 操作所需的执行时间。操作所需的执行时间