数据结构（C语言描述）全套PPT课件.pptx

第1章 绪论 ;1.1 什么是数据结构 ;;（3） 图形结构示例;2．数据元素（data element） 数据的基本单位是数据元素。 一个数据元素是可由若干个数据项（域或称字段）组成，数据项是数据的最小单位。 数据元素也称为结点、元素、记录等。;3． 数据类型（data type） 是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。;在本书中，描述一种抽象数据类型将采用如下书写格式： ADT 抽象数据类型名 { Data 数据描述 Operations 操作声明 } ADT 抽象数据类型名 ;5． 数据结构（data structure） 是一门研究数据是如何组织、存储、数据之间的相互关系及运算操作的学科。 具体地讲，它主要包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算（或操作）： （1）元素之间的相互关系又称为数据的逻辑结构。数据的逻辑结构独立于计算机，是数据本身所固有的。 （2）数据元素在计算机内存中的表示，称为数据的物理结构（存储结构）。必须依赖于计算机。 （3）对数据需要施加的操作，主要包括：查找、插入、删除、修改和排序等。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。 ;6. 数据结构的分类 从逻辑结构划分数据结构 数据结构从逻辑结构划分为： （1）线性结构 特点： a. 有且仅有一个开始结点(表头结点)a1; b.有且仅有一个终端结点(表尾结点)an ; c. 除了表头结点外，其余的结点有且仅有一个直接 前驱结点; d. 除了表尾结点外，其余的结点有且仅有一个直接 后继结点。 总之， 元素之间为一对一的线性关系。;（2）非线性结构 元素之间为一对多或多对多的非线性关系，每个元素有多个直接前驱或多个直接后继。 从存贮结构划分数据结构 数据结构从存贮结构划分为： (1)顺序存贮（向量存贮） 所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。 (2) 链式存贮 所有元素存放在可以不连续的存贮单元中，但元素之间的关系可以通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。 ;(3)索引存??? 使用该方法存放元素的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），其中的关键字是能唯一标识一个结点的那些数据项。 (4)散列存贮 通过构造散列函数，用函数的值来确定元素存放的地址。 一般来说，这四种基本存储方法既可单独使用，也可组合起来，同一种逻辑结构可采用不的存储方法，得到不同的存储结构，选择何种结构视具体问题的要求而定。;1.3 数据结构的重要地位 “数据结构”作为一门独立的课程在国外是从1968年才开始设立的。 是一门综合性的专业基础课。 瑞士N.Wirth提出的公式：程序= 算法+数据结构;第2章 程序的灵魂——算法;例1. 求1+2+3+4+…+100 方法1：直接相加，得出结果。 方法2：=100+(1+99)+(2+98)+…+(49+51)+50 =5050 例2：求1*2*3*4*5 最原始的方法：S1：先求1*2,得2。 S2：将2*3,得6。 … S4：将24*5=120,这是最后的结果。 若求1*2*3*…*1000,此方法不可行。因为需要999个步骤。; 故要找一种通用的方法。可设两个变量，一个变量代表 被乘数，一个变量代表乘数，p为被乘数，i为乘数。 S1:使p=1 S2:使i=2 S3:使p*i,将p*i=p S4:i+1=i S5:若i不大于5,返回重新执行S3及S4，S5；否则，算法结 束。 2.2 算法的特征 （1）有穷性. 一个算法应包含有限的操作步骤，而不能是 无限的。 （2）确定性. 每一步应是确定的，而不应是含糊的、模棱 两可的。;（3）有输入. 有零个或多个输入 如例2没有输入，但求两个 整数中 最大者，须输入。 （4）有输出. 有一个或多个输出. 算法的目的是为了“解”，求结果。所以没有输出的算法是没有意义的。 （5）有效性. (可行性）算法中的每一步都应能有效地执行，并得到确定的结果，如 若b=0,则执行a/b是不能有效执行的。 2.3 算法的描述 （1）用自然语言（是人们日常使用的语言，可用汉语、英 文或其他语言） （2）用流程图表示算法。这是一种用图形表示算法的方法。 直观形象