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

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

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

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

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

5、构，R中的关系没有任何约束，因此图结构反映的是多对多的关系图结构也被称为网状结构数据的存储结构首先必须了解的问题：计算机主存储器的特性计算机主存储器的特性：空间相邻：主存储器的存储空间提供了一种具有非负整数地址编码的、在存储空间上相邻的单元集合随机访问：计算机的指令具有按地址随机访问存储空间中任意单元的能力，访问不同单元所需要的时间基本相同数据的存储结构数据的存储结构的一个主要任务，是要充分利用主存储器的两个特点，利用顺序存储单元空间相邻关系来表达数据结构的结点，每个结点通常被存储在一片连续的存储区域内如何将逻辑关系映射到存储结构的地址关系上，利用存储地址表达逻辑关系，所采用的表达方法的好坏会

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

7、是经常使用的，特别是对于那些经常增删结点的复杂数据结构，顺序结构往往会遇到困难索引的方法索引法是顺序法的一种推广，它使用一个索引表存储存储一串指针，每个指针指向存储区域的一个数据结点。索引法的一个直接用途是可以把大小不等的数据结点顺序存储，并且仍然可以使用整数下标来间接访问数据结点位置散列的方法散列方法可以认为是索引方法的一种延伸和扩展，通过散列函数进行索引值的计算，然后通过索引表求出结点的指针地址抽象数据类型抽象数据类型是描述数据结构的一种理论工具，其特点是把数据结构作为独立于应用程序的一种抽象代数结构，使得人们可以独立于程序的实现细节来理解数据结构的主要性质和约束条件抽象数据类型的表示对应

8、于数据结构的二元组表示法，可采用三元组法表示抽象数据类型：，其中D是数据元素的有限集R是D上的关系集P是对D的基本操作集算法分析基础何谓“算法”？解决那些适合计算机实现的问题的方法对特定问题求解步骤的一种描述。在编写一个计算机程序时，我们通常会实现一个事先设计好的解决问题的方法。这个方法与具体使用的计算机无关，它可以适用于许多计算机和计算机语言。我们必须学习的是解决问题的方法，而不是计算机程序本身。“算法”这一术语就是这个方法在计算机科学中的对应物算法分析基础算法的五个特性：有穷性：对于任何合法的输入，一个算法必须在执行有穷步后结束，每个步骤必须在有穷时间内完成确定性：算法中的每个指令必须有确

9、切的含义可行性：算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现输入：一个算法有零个或多个输入输出：一个算法有一个或多个输出算法分析基础数据结构与算法的关系大多数算法关心计算机中数据的组织方式。而使用这种方式建立的对象称为“数据结构”从算法的角度看，数据结构是算法的副产物或最终产物算法分析基础算法设计的要求正确性：算法应当满足具体问题的需求可读性：算法主要是为了人的阅读和交流，其次才是机器执行健壮性：对于非法的输入数据，算法也能适当的作出反应或进行处理效率和低存储需求：时空资源的消耗以少为佳算法分析基础算法分析的两种策略：事后统计事前分析主要采取的事前分析的策略算法分析基础算法的

10、渐进分析简称算法分析算法的渐进分析算法在计算机上实现时，需要消耗时间（CPU执行指令的时间）和使用存储空间资源（占用的存储单元数）算法分析与算法所求解的问题的规模直接相关，因此通常将问题规模n作为一个参照量，求算法的时空消耗与n的关系算法分析主要考虑求解问题的规模n逐渐增大时，算法时空消耗的变化趋势算法分析基础算法分析方法的几点说明在具体估计时空消耗时，要对算法的整个执行过程进行全面检查，求出所执行的操作的总数量每一个操作的消耗估计与具体计算机的技术细节相关，这些细节不必牵涉到算法分析中，因此算法分析不应拘泥于操作的种类、不同操作种类间的消耗的差别，而主要关注消耗随n的变化趋势最好、最好和平均情况时空互换问题数据结构