概论西南林学院计科系课件.ppt

1、第一章 概论西南林学院计算机与信息科学系董跃宇本章的主要内容n为什么要学习数据结构？n什么是数据结构？n算法及其度量为什么要学习数据结构？n原因1：数据结构是计算机科学与技术学科的一门专业基础课，它可以为后续专业课程的学习提供必要的知识和技能准备。n例如：q程序设计语言及其编译技术要使用栈、散列表及语法树q操作系统会用到队列、存储管理表及目录树q数据库系统中会用到线性表、多链表及索引树q广义表、集合以及图的搜索在很多应用领域经常涉及为什么要学习数据结构？n原因2：现代电子计算机最初是设计用来处理数值型数据的，但随着计算机应用领域的不断拓展，所需要处理的不再只是数值型数据，这给程序设计等方面带来

2、了一些新的问题。分析待处理的对象以及待处理对象之间的关系成了一个必须的选择。这也正是数据结构这一课程出现的背景和原因。数据结构课程的主要内容n介绍一些最常用的数据结构，阐明数据结构内在的逻辑关系，讨论它们在计算机中的存储表示，并结合各种数据结构，讨论对它们实行各种运算的实现算法。n以上这些知识再配合以实际的上机编程练习，将增强求解复杂问题的能力，其中包括根据问题的性质恰当选择数据结构的能力，以及控制求解算法的复杂性的能力。爱莫能助什么是数据结构？n何谓数据？q数据是对客观事物的符号表示。q在计算机科学中是指所有能输入到计算机中并能被计算机处理的符号的总称n数据元素是数据的基本单位什么是数据结构

3、？n何谓结构？q在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在某种关系，这种数据元素相互之间的关系称为结构什么是数据结构？n数据结构涉及数据之间的逻辑关系、数据在计算机中的存储方式和在这种结构上的一组可行的操作（运算）三个方面。为了叙述方便，把上述三个方面分别称为：q数据的逻辑结构q数据的存储结构q数据的运算数据的逻辑结构n数据的逻辑结构反映了人们对数据的含义解释。n人们对现实世界的某个特定领域的认识，表现在对所涉及的事物之间的逻辑关系以及组成结构的认识数据的逻辑结构n数据的逻辑结构可以用集合论的观点来分析：q一个逻辑结构可以用一个二元组来表示：n，其中，D是数据元素的有限集，R是

4、D上关系的有限集q从这一角度来看，数据结构就是一组存在特定关系的数据元素的集合数据的逻辑结构n数据元素的有限集D中的数据元素是对现实世界特定领域所涉及的事物的反映nD中的元素可以是简单的基本类型，也可以是庞杂的复合类型数据的逻辑结构n可以利用集合R中的关系的性质来刻画数据结构的特点，对其进行分类n数据的逻辑结构可分为：q集合q线性结构q树形结构q图结构集合nD中的数据元素除了同属于一个集合外，无其他关系n集合反映了一种松散的逻辑结构线性结构n数据元素的直接前驱节点若存在，则唯一n数据元素的直接后继节点若存在，则唯一n线性结构反映的是一种一对一的关系树形结构n数据元素的直接前驱节点若存在，则唯一

5、n数据元素的直接后继节点若存在，可不唯一n树形结构反映的是一种一对多的关系图结构n对于图结构，R中的关系没有任何约束，因此图结构反映的是多对多的关系n图结构也被称为网状结构数据的存储结构n首先必须了解的问题：计算机主存储器的特性n计算机主存储器的特性：q空间相邻：主存储器的存储空间提供了一种具有非负整数地址编码的、在存储空间上相邻的单元集合q随机访问：计算机的指令具有按地址随机访问存储空间中任意单元的能力，访问不同单元所需要的时间基本相同数据的存储结构n数据的存储结构的一个主要任务，是要充分利用主存储器的两个特点，利用顺序存储单元空间相邻关系来表达数据结构的结点，每个结点通常被存储在一片连续的

6、存储区域内n如何将逻辑关系映射到存储结构的地址关系上，利用存储地址表达逻辑关系，所采用的表达方法的好坏会非常影响存储空间的开销，而且也会影响到算法的效率四种基本的存储映射方法n可以利用映射来表示存储结构，数据的存储结构是建立一种由逻辑结构到存储空间的映射n四种基本的存储映射方法是：q顺序的方法q链接的方法q索引的方法q散列的方法顺序的方法n用一块无空隙的存储区域存储数据元素称为顺序存储n顺序存储将一组数据元素存放在按地址相邻的存储单元里，数据元素间的逻辑关系采用存储单元的自然顺序关系来表达n顺序存储结构被称为紧凑存储结构，其紧凑性是指它的存储空间除了存储有用数据外，没有用于存储其他附加的信息链

7、接的方法n采用的数据元素的存储结构中附加指针字段的方法称为链接法。n两个数据元素的逻辑后继关系可以用指针的指向来表达n链接的方法是经常使用的，特别是对于那些经常增删结点的复杂数据结构，顺序结构往往会遇到困难索引的方法n索引法是顺序法的一种推广，它使用一个索引表存储存储一串指针，每个指针指向存储区域的一个数据结点。n索引法的一个直接用途是可以把大小不等的数据结点顺序存储，并且仍然可以使用整数下标来间接访问数据结点位置散列的方法n散列方法可以认为是索引方法的一种延伸和扩展，通过散列函数进行索引值的计算，然后通过索引表求出结点的指针地址抽象数据类型n抽象数据类型是描述数据结构的一种理论工具，其特点是

8、把数据结构作为独立于应用程序的一种抽象代数结构，使得人们可以独立于程序的实现细节来理解数据结构的主要性质和约束条件抽象数据类型的表示n对应于数据结构的二元组表示法，可采用三元组法表示抽象数据类型：，其中qD是数据元素的有限集qR是D上的关系集qP是对D的基本操作集算法分析基础n何谓“算法”？q解决那些适合计算机实现的问题的方法q对特定问题求解步骤的一种描述。n在编写一个计算机程序时，我们通常会实现一个事先设计好的解决问题的方法。这个方法与具体使用的计算机无关，它可以适用于许多计算机和计算机语言。我们必须学习的是解决问题的方法，而不是计算机程序本身。“算法”这一术语就是这个方法在计算机科学中的对

9、应物算法分析基础n算法的五个特性：q有穷性：对于任何合法的输入，一个算法必须在执行有穷步后结束，每个步骤必须在有穷时间内完成q确定性：算法中的每个指令必须有确切的含义q可行性：算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现q输入：一个算法有零个或多个输入q输出：一个算法有一个或多个输出算法分析基础n数据结构与算法的关系q大多数算法关心计算机中数据的组织方式。而使用这种方式建立的对象称为“数据结构”q从算法的角度看，数据结构是算法的副产物或最终产物算法分析基础n算法设计的要求q正确性：算法应当满足具体问题的需求q可读性：算法主要是为了人的阅读和交流，其次才是机器执行q健壮性：对于

10、非法的输入数据，算法也能适当的作出反应或进行处理q效率和低存储需求：时空资源的消耗以少为佳算法分析基础n算法分析的两种策略：q事后统计q事前分析n主要采取的事前分析的策略算法分析基础n算法的渐进分析简称算法分析n算法的渐进分析q算法在计算机上实现时，需要消耗时间（CPU执行指令的时间）和使用存储空间资源（占用的存储单元数）q算法分析与算法所求解的问题的规模直接相关，因此通常将问题规模n作为一个参照量，求算法的时空消耗与n的关系q算法分析主要考虑求解问题的规模n逐渐增大时，算法时空消耗的变化趋势算法分析基础n算法分析方法的几点说明q在具体估计时空消耗时，要对算法的整个执行过程进行全面检查，求出所执行的操作的总数量q每一个操作的消耗估计与具体计算机的技术细节相关，这些细节不必牵涉到算法分析中，因此算法分析不应拘泥于操作的种类、不同操作种类间的消耗的差别，而主要关注消耗随n的变化趋势q最好、最好和平均情况q时空互换问题数据结构的选择和评价n仔细分析所要解决的问题，特别是求解问题所涉及的数据类型和数据间的逻辑关系n数据结构的设计往往应先于算法的设计n注意数据结构的可扩展性n比较算法时空消耗的优劣参考书目n数据结构（C语言版）q严蔚敏 吴伟民 编著 q清华大学出版社n数据结构与算法q徐卓群 杨冬青 唐世渭 张铭q高等教育出版社n数据结构q徐孝凯 编著q电子工业出版社