课题1-数据结构概念资料.ppt

绪 论 能够分析研究计算机加工的对象的特性，获得其逻辑结构，根据需求，选择合适存储结构及其相应的算法； 学习一些常用的算法； 复杂程序设计的训练过程，要求编写的程序结构清楚和正确易读； 初步掌握算法的时间分析和空间分析技术； 1、从具体问题中抽象出一个适当的数学模型 ----》分析问题 2、设计一个解此模型的算法。 提取操作对象找出操作对象间含有的关系，用数学语言加以描述。 3、编出程序 4、测试、调整 5、得到最终解答 3、学习的目的 对每个数据结构加强对存在代价与效益的观念 掌握常用的数据结构——将常用的数据结构放入你的工具包 理解怎样去衡量一个数据结构或程序的代价 4、怎样学习数据结构 注重基础知识（牢固准确掌握） 联系实际问题（研究分析算法） 提出几点要求 认真独立完成作业 做好预习和及时复习 勤思考多练习（算法、程序） 数据对象： 数据的子集。具有相同性质的数据成员（数据元素）的集合 整数数据对象 N = { 0, ?1, ?2, … } 字母字符数据对象C={ ‘A’,’B’,……‘Z’} 例1-4 复数的二元组定义 复数由实部和虚部构成（构成元素），两者之间存在着一种次序关系（逻辑关系）。 可以表示为： Complex=(C,R) 其中,C={ c1,c2} R={c1,c2} 说明: 表示有序数对,用图示法表示时画箭头 ( )表示无序数对,用图示法表示时画线段 例2 设有数据逻辑结构为: B=(K,R) K={k1,k2,k3,k4,k5,k6,k7,k8,k9} R={k1,k3,k1,k8,k2,k3,k2,k4,k2,k5,k3,k9,k5,k6,k8,k9,k9,k7,k4,k7,k4,k6} 画出这个结构的图示. k1 k2 k3 k4 k5 k6 k7 k8 k9 网状结构(有向图) 数据的存储结构 —— 逻辑结构在存储器中的表示(映象) “数据元素”的映象 ？ “关系”的映象 ？ 数据元素的映象方法： 用二进制位(bit)的位串表示数据元素 (321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)2 关系的映象方法： （表示?x, y?的方法） 顺序映象 以相对的存储位置表示后继关系 例如:存储复数 z=3.0-2.3i 用顺序结构，内存存储情况为: 2001 2002 2003 2004 3.0 -2.3 链式映象 以附加信息(指针)表示后继关系 2001 2002 2003 2004 3.0 2036 2036 2037 -2.3 当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。 顺序结构:占用最少的存储空间，产生较多碎片。 非顺序（链式）：不会出现碎片，每个结点占用较多空间。 二、数据类型 在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。 定义：一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称. 不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。 例如，C 语言中提供的基本数据类型有: 整型 int 浮点型 float 字符型 char 空类型 void 双精度型 double 实型（ C++语言） 三、抽象数据类型 (Abstract Data Type 简称ADT) 由用户定义，用以表示应用问题的数据模型 由基本的数据类型组成, 并包括一组相关的服务（或称操作） 信息隐蔽和数据封装，使用与实现相分离 例如，抽象数据类型复数的定义： 数据对象： D＝{e1,e2｜e1,e2∈RealSet } 数据关系： R1＝{e1,e2 | e1是复数的实数部分 | e2 是复数的虚数部分 } ADT Complex { 基本操作： AssignComplex( Z, v1, v2 ) 操作结果：构造复数 Z,其实部和虚部 分别被赋以参数 v1 和 v2 的值。 DestroyComplex( Z) 操作结果：复数Z被销毁。 GetReal( Z, realPart ) 初始条件：复数已存在。 操作结果：用realPart返