《C语言程序设计与数据结构》第12章 数据结构绪论

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,C语言程序设计与数据结构,第,12,章,数据结构绪论,教学目标：通过本章的学习，使读者能够掌握数据结 构的概念和有关的术语。,C语言程序设计与数据结构,12.1,什么是数据结构,计算机科学技术的广泛应用已从传统的数值计算领域发展到各种非数值计算领域。为了有效地处理数据，需要为数据建立一定的结构，描述所处理的对象的特性以及各对象之间的关系。,数据结构这门学科主要是研究各种结构、定义在各种结构上的操作和这些操作在计算机中的实现方法。,C语言程序设计与数据结构,用计算机解决一个具体问题时要考虑以下步骤,从具体问题中抽象出一个适当的数学模型。即从具体问题中找出操作对象之间含有的关系，然后用数学语言加以描述。,设计一个适合该数学模型的算法（,Algorithm,）。,编写程序。,(4),进行测试、调整、修改，直至解决问题。,所以，数据结构是研究程序设计中计算机操作的对象以及它们之间的关系和运算的一门学科。,C语言程序设计与数据结构,实际问题中，各个对象之间的关系有：,线性的：,列车中各车箱之间的关系，排队买车票的人之间的关系，一叠盘子中各盘子之间的关系都是线性的。,层次的：在军队的编制中，军下面是师，师下面是团，军、师、团之间是层次关系；在人的辈分关系中，祖辈下是父辈，父辈下是子辈，这些是层次关系；在学校的编制中，学校分成若干个学院、学院下又分成若干个系、系下又分成若干个教研室，这些也都是层次关系。,网状的：在城市铁路交通图中，各城市之间的关系是网状关系。在电话网中，各电话之间是网状关系。,对象之间的关系,C语言程序设计与数据结构,12.2,基本概念和术语,数据,数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。在计算机科学中，数据的含义非常广泛，我们把一切能够输入到计算机中并被计算机程序处理的信息，包括文字、表格、图象等，都称为数据。,C语言程序设计与数据结构,数据举例,一个个人书库管理程序所要处理的数据可能是一张如表所示的表格。,C语言程序设计与数据结构,结点,结点也叫数据元素，它是组成数据的基本单位。在程序中通常把结点作为一个整体进行考虑和处理。例如，在上表所示的个人书库中，为了便于处理，把其中的每一行（代表一本书）作为一个基本单位来考虑，故该数据由,10,个结点构成。,一般情况下，一个结点中含有若干个字段（也叫数据项）。例如，在上表所示的表格数据中，每个结点都有登录号、书号、书名、作者、出版社和价格等六个字段构成。,字段是构成数据的最小单位。,C语言程序设计与数据结构,逻辑结构,结点和结点之间的逻辑关系称为数据的逻辑结构。,在上表所示的表格数据中，各结点之间在逻辑上有一种线性关系，它指出了,10,个结点在表中的排列顺序。根据这种线性关系，可以看出表中第一本书是什么书，第二本书是什么书，等等。,C语言程序设计与数据结构,存储结构,数据在计算机中的存储表示称为数据的存储结构。,在上表所示的表格数据在计算机中可以有多种存储表示，例如，可以表示成数组，存放在内存中；也可以表示成文件，存放在磁盘上，等等。,C语言程序设计与数据结构,数据处理,数据处理：是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。,例：,从数据结构,S,中找出满足条件的结点在,S,中位置的运算是型运算。,从数据结构,S,中读出结构中指定位置上内容运算是型运算。,从数据结构,S,中修改结构中某指定结点内容的运算是型运算。,C语言程序设计与数据结构,数据结构（,Data Structure,）,数据结构：是研究数据元素（,Data Element,）,之间抽象化的相互关系和这种关系在计算机中的存储表示（即所谓数据的逻辑结构和物理结构），并对这种结构定义相适应的运算，设计出相应的算法，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。,为了叙述上的方便和避免产生混淆，通常我们 把数据的逻辑结构统称为数据结构；把数据的物理结构统称为存储结构（,Storage Structure,）。,C语言程序设计与数据结构,数据类型,数据类型是指程序设计语言中各变量可取的数据种类。数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密切相关。,一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。可以认为，数据类型是在程序设计中已经实现了的数据结构。,另一方面，在程序设计过程中，当需要引入某种新的数据结构时，总是借助编程语言所提供的数据类型来描述数据的存储结构。,C语言程序设计与数据结构,算法,简单地说就是解决特定问题的方法。特定的问题可以是数值的，也可以是非数值的。,解决数值问题的算法叫做数值算法，科学和工程计算方面的算法都属于数值算法，如求解数值积分，求解线性方程组、求解代数方程、求解微分方程等。,解决非数值问题的算法叫做非数值算法，数据处理方面的算法都属于非数值算法。例如各种排序算法、查找算法、插入算法、删除算法、遍历算法等。,数值算法和非数值算法并没有严格的区别。,C语言程序设计与数据结构,12.3,算法和算法的描述,算法是执行特定计算的有穷过程。这个过程有,5,个特点：,（,1,）,动态有穷：当执行一个算法时，不论是何种情况，在经过了有限步骤后，这个算法一定要终止。,（,2,）,确定性：算法中的每条指令都必须有确切的含义，不能有二义性。,（,3,）,输入：具有,0,个或,0,个以上由外界提供的输入量。,（,4,）,输出：产生,1,个或多个结果。,（,5,）,可行性：算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。,C语言程序设计与数据结构,算法的描述,一个算法可以用自然语言、数字语言或约定的符号来描述，也可以用计算机高级程序语言来描述，如,Pascal,语言、,C,语言或伪代码等。,本书选用,C,语言作为描述算法的工具。,C语言程序设计与数据结构,算法评价,设计一个好的算法应考虑以下几个方面：,正确性,运行时间,占用的存储空间,简单性,C语言程序设计与数据结构,正确性,“,正确,”,的含义在通常的用法中有很大的差别，大体可分为以下四个层次：,程序不含语法错误；,程序对于几组输入数据能够得出满足规格说明要求的结果；,程序对于精心选择的典型、苛刻而带有刁难性的几组数据能够得出满足规格说明要求的结果；,程序对一切合法的输入数据都能产生满足规格说明要求的结果。,C语言程序设计与数据结构,运行时间,运行时间是指一个算法在计算机上运算所花费的时间。它大致等于计算机执行一种简单操作（如赋值操作、转向操作、比较操作等等）所需要的时间与算法中进行简单操作次数的乘积。通常把算法中包含简单操作次数的多少叫做算法的时间复杂性，它是一个算法运行时间的相对量度。,在算法分析中绝对的量不能反映时间复杂度，使用一个函数,(,n),表示一个算法的复杂度。一个算法所解决问题的规模,n,增大时，时间的增长率越小，时间复杂度越好，反之时间复杂度越坏。也就是说，时间复杂度是,n,的一个函数。从好到坏表示时间复杂度的函数依次是：常量,阶,O(1),；,对数阶,O(log n),；,线性阶,O(n),；,平方阶,O(n,2,),；,多项式阶,O(n,k,),；,指数阶,O(2,n,),等。,C语言程序设计与数据结构,时间复杂度举例,下列三段程序的时间复杂度分别是：,x+;s=x+2;,时间复杂度为,(1),for(k=1;k=n;k+),s=k+2:,时间复杂度为,(,n),for(k=1;k=n;k+),for(j=1;j=n;j+),s=k+j:,时间复杂度为,(,n,2,),C语言程序设计与数据结构,占用的存储空间,一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入、输出数据所占用的存储空间和算法运行过程中临时占用的存储空间。,分析一个算法所占用的存储空间要从各方面综合考虑。,算法在运行过程中所占用的存储空间的大小被定义为算法的空间复杂性。它包括局部变量所占用的存储空间和系统为了实现递归所使用的堆栈这两个部分。,C语言程序设计与数据结构,算法的空间复杂性,算法的空间复杂性同算法的时间复杂性一样，一般以数量级的形式给出，使用一个函数,S(n),表示一个算法的空间复杂度。,对于空间复杂度，也用与时间复杂度同样的表示方法，用常量阶,O(1),；,对数阶,O(log n),；,线性阶,O(n),；,平方阶,O(n,2,),；,多项式阶,O(n,k,),；,指数阶,O(2,n,),等表示，,C语言程序设计与数据结构,简单性,最简单和最直接的算法往往不是最有效的，但算法的简单性使得证明其正确性比较容易，同时便于编写、修改、阅读和调试，所以还是应当强调和不容忽视的。不过对于那些需要经常使用的算法来说，高效率（即尽量减少运行时间和压缩存储空间）比简单性更为重要。,C语言程序设计与数据结构,谢 谢！,C语言程序设计与数据结构,