数据结构CC++第一章绪论.ppt

《数据结构CC++第一章绪论.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构第一章绪论第一章绪论知识点数据结构中常用的基本概念和术语算法描述和分析方法难点算法复杂性的分析方法要求了解数据的逻辑结构和物理结构，算法的基本概念，它们对于程序设计的重要性以及相互关系掌握算法复杂性的概念及分析方法第一章目录1.1基本概念1.2算法的描述1.3算法的评价1.4应用举例及分析小结习题与练习分析程序处理的数据的特性及数据之间的关系，这就是“数据结构”这门学科形成和发展的背景。数据结构主要研究非数值应用问题中数据之间的逻辑关系和对数据的操作，同时还研究如何将具有逻辑关系的数据按一定的存储方式存放在计算机内

2、。例:某单位职工档案的管理。图1.1中的职工档案表就是一个数据结构。如果把表中的一行看成一个记录并称为一个结点，则在此表中，结点和结点之间的关系是一种最简单的线性关系。某学校教师的名册。虽然可以用例1.1中的二维表格将全校教师的名单列出，但采用图1.2所示的结构更好。它像一棵根在上而倒挂的树，清晰地描述了教师所在的系和教研组，这样一来可以从树根沿着某系某教研组很快找到某个教师，查找的过程就是从树根沿分支到某个叶子的过程。例在n个城市之间建立通信网络，要求在其中任意两个城市之间都有直接的或间接的通信线路，在已知某些城市之间直

3、接通信线路预算造价的情况下，使网络的造价最低。通过上面三个例子可以看出：数据结构中元素和元素之间存在着逻辑关系，而线性表，树，图是三种基本的逻辑结构，其他各类的数据结构都是由这三种基本结构派生的。数据结构就是解决如何分析数据元素之间的关系、如何确立合适的逻辑结构、如何存储这些数据，并对为完成数据操作所设计的算法做出时间和空间的分析。“数据结构”在计算机科学中是一门综合性的专业基础课，它不仅是一般程序设计(特别是非数值计算的程序设计)的基础，而且也是设计和实现编译程序、操作系统、数据库系统及大型应用程序的重要基础。1.1基本

4、概念(1)数据(Data)：一切能够由计算机接受和处理的对象。数据元素(Dataelement)：是数据的基本单位，在程序中作为一个整体加以考虑和处理。数据项(Dataitem)：是数据的不可分割的最小单位，在有些场合下，数据项又称为字段或域。1.1基本概念(2)数据结构(Datastructure)：数据之间的相互关系，即数据的组织形式。研究数据结构，是指研究数据的逻辑结构和物理结构数据的逻辑结构：数据元素之间的逻辑关系数据的物理结构：数据元素在计算机存储器中是如何存储的四类基本逻辑结构的示意图定义一组有关数据元素的运算

5、。在讨论各种数据结构时，针对其逻辑结构和具体的存储结构给出对应的数据类型，进一步在确定的数据类型上实现各种操作。数据的存储结构是逻辑结构在计算机存储器中的实现。数据元素在计算机中主要有两种不同的存储方法：顺序存储结构和链式存储结构。顺序存储的特点是在内存中开辟一组连续的空间(高级语言中的数组)来存放数据。链式存储的特点是通过指针反映数据元素之间的逻辑关系，又称动态存储。1.1基本概念(3)算法(Algorithm)：对特定问题求解步骤的一种描述。程序=数据结构+算法”。算法是一个有穷的规则序列，这些规则决定了解决某一特定问

6、题的一系列运算。由此问题相关的一定输入，计算机依照这些规则进行计算和处理，经过有限的计算步骤后能得到一定的输出。返回1.2算法的描述1、框图算法描述：这种描述方法在算法研究的早期曾流行过。它的优点是直观、易懂，但用来描述比较复杂的算法就显得不够方便，也不够清晰简洁。例：求两个整数m,n(m≥n)的最大公因子算法的描述方法有很多，根据描述算法语言的不同，可将算法分为以下四种：2、非形式算法描述：用中文语言，同时还使用一些程序设计语言中的语句来描述算法，这称为非形式算法描述。a.［求余数］以n除m，并令r为余数(0≤r

7、b.［余数是零否］若r=0则结束算法，n就是最大公因子；c.［替换并返回a］若r≠0则m←n,n←r返回a。例：求两个整数m,n(m≥n)的最大公因子3、C语言描述：这是可在计算机上运行并获得结果的算法，使给定问题能在有限时间内被求解，通常这种算法也称程序。本书将采用C语言描述算法，所有算法都以如下所示的函数形式表示：函数类型函数名（参数表）{语句序列}例：求两个整数m,n(m≥n)的最大公因子intmax_common_factor(intm,intn){intr;r=m%n;while(r!=0){m=n;n=r;r=

8、m%n;}returnn;}1.3.1评价算法的一般原则正确性：算法应能正确地实现处理要求。易读性：有助于对算法的理解，便于纠正和扩充。简单性：使证明其正确性比较容易，对算法进行修改也比较方便。高效率：达到所需的时、空性能。1.3.2算法复杂性的分析算法的复杂性包括时间复杂性（所需运算时间）和空间复杂性