数据结构第一章概论.pptVIP

定义为一个二元组：Data_structures=(D,S)如：线性结构：其中n为线性表的表长，n=0时线性表为空表。其中：D是数据元素的有限集，S是D上关系的有限集。数据对象：A={ai︱1=i=n,n=0,ai∈elemtype}数据关系：R={r}R={ai,ai+1︱1=i=n-1}123456数据逻辑结构的定义数据的在计算机上的存储表示称作数据的物理结构或存储结构。数据元素的映像方法：用二进制位（bit）的位串表示数据元素。10=（101000001）2A=(001000001)2010302040506数据的物理结构（存储结构）数据的物理结构（存储结构）关系集合的映像方法： 所有关系都可用一个有序对的集合来表示。{a1,a2,a1,a3,a2,a4,a2,a5,a2,a6} 有序对看成是关系的一个基本单位，讨论关系的映像，只要讨论这个有序对的映像方法即可。a1a2a3a4a5a6映像方法：顺序映像：以存储位置的相邻表示后继关系。链式印象：存储位置无固定关系，用附加信息（指针）来表示后继关系。a1a2a3a4a1a2a3215数据类型是一个值的集合和定义在这个集合上的一组操作的总称。如pascal中的integer类型，数据范围数据类型分为：简单型和结构类型（构造类型）4操作：+-*divmod3[-32768,32767]数据类型据结构上的一组操作的总称。比如：数组，数组的值可以分割，它是某个结构类型也可以看成是一个数据结构和定义在这个数的值，因此这个值集是一个数据结构。所以数据从这个概念出发——抽象数据类型（ADTAbstractDataType）是指一个数学模型以及定义在这个数学模型上的一组操作。结构类型例如：抽象数据类型复数的定义ADTcomplex{数据对象：D={e1,e2∣e1,e2∈real}数据关系：R={e1,e2∣e1是复数的实部，e2是复数的虚部}基本操作：Initcomplex(z,v1,v2)操作结果：构造复数z，其实部和虚部分别赋以参数v1,v2的值。Destroycomplex(z)操作结果：复数z被销毁Getreal(z,x)初始条件：复数已存在操作结果：用x返回复数z的实部值Getimag(z,y)初始条件：复数已存在操作结果：用y返回z的虚部值Add(z1,z2,sum)初始条件：z1,z2是复数操作结果：用sum返回两个复数的和值。抽象数据类型的描述方法(D,S,P)三元组表示：D是数据对象S是D上的关系集P是对D的基本操作数据结构ADT抽象数据类型的表示和实现：通过固有数据类型，即高级编程语言中已经实现的数据类型，来实现。数据结构的三个方面：数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构算法：是为了解决某类问题而规定的一个有限长的操作序列。算法的五个重要特性：有穷性2、确定性3、可行性有输入5、有输出问题三：算法及算法的衡量其含义有二：其一：描述算法的指令条数有限。其二：每一步的执行时间是有限的，非数学意义上的有限，而应理解为合理。有穷性：对任意一组合法输入值，在执行有穷步骤之后，一定能结束，即能在有限时间内完成。算法的特性算法的特性②确定性：每种情况下执行的操作，在算法中都有确切的规定，使算法的执行者或者阅读者能够明确其含义及如何执行，并且在任何条件下，算法都只有与之对应的一条路径。③可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次来实现之。如：将a,b的最大公约数赋值给c（×）增加x的值（×）交换a,b两个变量的值（√）有输入：输入的形式多样，有的输入嵌在算法中，有的可通过终端输入。必须保证算法有可以加工的对象。如：求100以内的素数Fori:=2to100do……有输出：信息加工的结果。算法的特性程序不含语法错误01对于精心选择的、典型的、苛刻且带有刁难性的几组输入数据都能得出满足要求的结果。03程序对于几组输入数据能够得到满足要求的结果。02程序对于一切合法的输入数据都能得出满足要求的结果。（相当难）04正确性：算法设计（评价）的原则可读性算法主要是为了人的阅读与交流