搜索
第六章数据结构与程序设计6.16.26.3数据与数据类型数据结构程序设计2Contents目录数据结构是对各种数据关系的总结、归纳和抽象。本章首先介绍了数据和数据类型的基本概念以及数据结构的产生，并详细讲解了数据结构研究的内容，包括数据、数据的逻辑结构以及在相应存储结构下对数据的操作运算。针对常见的数据结构——线性与非线性结构进行了讲解。最后通过对程序概念的提出，阐述了程序设计的步骤、常用工具，并对软件工程和软件开发的常用模型进行了概述。本章要点36.1数据与数据类型数据:是对客观事物的符号表示，是一组表示数量、行动和目标的非随机数字或字母的可鉴别的符号。在计算机中，数据通常是指一切可以输入到计算机中并能被计算机程序处理的所有符号的总称，包括文本、声音、图形、图像、动画和视频等。数据结构：在计算机科学中，数据之间的关系称为数据结构。数据结构是对各种各样的数据关系的总结、归纳和抽象，对数据结构的研究分为数据的逻辑结构和物理结构两个方面。5数据数据类型是对具有同类性质的数据的抽象，是计算机程序设计语言特有的概念。在计算机程序中变量存储数据，而变量都应属于某种特定的数据类型。①决定数据在计算机中所占的存储空间大小。②决定数据的存储方式。③决定数据的操作运算。不同问题其数据的含义各不相同，数据间的联系称为结构，数据及其关系的研究在计算机中要考虑数据表示和存储两方面。6数据类型6.2数据结构计算机不局限于单纯的数值计算，更多地应用于控制、管理及信息处理等非数值计算的数据处理工作。对于不同的处理对象，如何组织数据和处理数据，如何根据问题的要求及数据元素之间的特性，确定相应的存储结构和算法，这都数据结构研究的内容。数据结构就是研究非数值处理问题的学科。8数据结构的产生数据结构通常通过抽象数据类型来描述，包括：1.逻辑结构：指数据元素之间的逻辑关系，与数据在计算机内部是如何存储无关，数据的逻辑结构独立于计算机。数据的逻辑结构一般有集合、线性结构、树形结构、图形结构等四种类型。2.存储结构：指数据元素在计算机存储设备中的存储方式。一般分成顺序存储和链式存储两种。3.数据的运算：插入、删除、检索和排序等与问题相关的处理。9数据结构研究的内容线性结构最常用且最简单的数据结构，是一个有序数据元素集合，如线性表、栈、队列、双队列、数组和串等。这些数据元素之间除了在表中的排列次序即先后次序不同外，没有其他的联系，这一类的表属于线性表。从数据结构的角度出发，线性表是n个数据元素组成的有限序列，其中n≥0，记为（a1,a2,…..,an-1,an）当n为0时，线性表为空表。10常用的数据结构1在线性表中，除了第一个和最后一个数据元素外，每个数据元素都有一个直接前趋和一个直接后继。线性表可以用不同的方式存储在计算机中，其中最简单也是最常见的是用一组连续的内存空间，依次存放线性表中的每一个数据元素，称为线性表的顺序存储结构，用这种方法存储的线性表称为顺序表。在高级语言中，可以用一维数组来实现。11常用的数据结构2线性表还可以采用链式方式进行存储。每个数据结点独立保存在内存的一片连续区域之中，结点和结点之间不要求连续，为了能反映数据逻辑上的先后次序，在链式存储方式中，每个结点就必须有一个能反映逻辑上后继结点在内存位置的信息，存放该信息的部分称为链域，结点之间通过链域连接。这样只要给出逻辑上第一个结点的位置，就可以通过链域找到所有数据。第一个结点的位置称为链表首指针。12常用的数据结构3非线性结构逻辑特征是一个结点元素可能有多个直接前趋或多个直接后继。常用的有树和图两类。树形结构一种简单的非线性结构，所有数据之间有明显的层次特性。树结构（除了根结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。13常用的数据结构4树是n个结点的有限集合，在任一棵非空树中：①有且仅有一个称为根的结点。②其余结点可分为互不相交的集合，而且这些集合中的每一集合本身又是一棵树，称为根的子树。从逻辑结构看：①树中只有根结点没有前趋；②除根外，其余结点都有且仅一个前趋；③树的结点，可以有零个或多个后继；④除根外的其他结点，都存在唯一条从根到该结点的路径；⑤树是一种分支结构。14常用的数据结构5图形结构一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继。针对图中边的不同定义，图又分为无向图（在图中，若所有边是无向边，则称为无向图）；有向图（在图中，若所有边是有向边，则称为有向图）；混和图（在图中，即有无向边也有有向边，则称为混合图）。用计算机处理交通线路规划，电路图、各种流程图等都要使用图形结构，因此图形结构也是一种重要的数据结构。15常用的数据结构66.3程序设计指完成某些事务的一种既定方式和过程。从计算机应用的观点看，程序就是人与计算机交流信息的基本方式。算法+数据结构=程序1.程序是计算机指令的某种组合，控制计算机的工作流程，完成一定的逻辑功能，以实现任务。2.算法是程序的逻辑抽象，是解决某类客观问题的数学过程。数据结构具有逻辑结构和物理结构两层含义。前者是客观事物自身所具有的结构特点；而后者是在计算机中的具体实现则称之为物理结构。数据结构与算法呈相互依托，恰当的确立了问题的结构，问题的解决才能根据确立的数据结构选择合适的算法。17程序的概念18程序设计的步骤1.程序流程图又称程序框图，是一种算法表达工具。它独立于任何一种程序设计语言，直观、清晰，易于学习掌握。因此，至今仍是软件开发者最普遍采用的一种工具。但流程图所使用的符号不够规范，常常使用一些习惯性用法来替代标准。19程序设计的常用工具12.N-S图一种符合结构化程序设计原则的图形描述工具，叫做盒图或N-S图。N-S图的5种基本控制结构：20程序设计的常用工具2N-S图特点：⑴图中每个矩形框都是明确定义了的功能域，以图形表示，清晰可见。⑵它的控制转移不能任意规定，必须遵守结构化程序设计的要求。⑶易确定局部数据和(或)全局数据的作用域。⑷易表现嵌套关系和模块的层次结构。注：当问题复杂时，可给图中的某些部分取个名字，并在图中相应位置用椭圆形框住名字；然后在另外的纸上再把这些命名的部分进一步展开。21程序设计的常用工具3PAD图PAD是用结构化程序设计思想表现程序逻辑结构的图形工具，它由程序流程图演化而来。也设置了5种基本控制结构的图式，并允许递归使用。由于PAD的树形特点，使它比流程图更容易在计算机上处理。22程序设计的常用工具4程序设计语言PDL一种用于描述功能模块的算法设计和加工细节的语言，称为设计程序用语言。PDL是一种伪码，它具有严格的关键字外语法，用于定义控制结构和数据结构，同时它表示实际操作和条件的内语法又是灵括自由的，可使用自然语言的词汇。具有正文格式，方便完成PDL的书写和编辑工作。从其来源看，PDL可能是某种高级语言23程序设计的常用工具5PDL特点：⑴有固定的关键字外语法，提供全部结构化控制结构、数据说明和模块特征。⑵内语法使用自然语言来描述处理特性，为开发者提供方便，提高可读性。⑶有数据说明机制，包括简单与复杂的数据结构。⑷有子程序定义与调用机制，用以表达各种方式的接口说明。使用PDL语言，可以做到逐步求精：从比较概括和抽象的PDL程序起，逐步写出更详细、更精确的描述。24程序设计的常用工具6即内部文档编制，包括选择标识符（变量和标号）的名字、安排注释及程序的视觉组织等。1．符号名的命名：符号名即标识符，应能反映所代表的实际对象，有一定实际意义，有助于对程序功能的理解。一般命名采用匈牙利表示法。2．程序的注释：给阅读程序带来方便。注释分为序言性注释和功能性注释。3．视觉组织：用空格区分程序词汇；自然的程序段之间可用空行隔开；利用移行突出程序的层次感。25源程序文档化软件工程，研究大规模程序设计的方法、工具和管理的一门工程科学。要求采用工程的概念、原理、技术和方法来开发和维护软件，把经过时间考验而证明正确的管理技术和当前能够得到的最好的技术方法结合起来。软件生存周期分为：1.软件定义：问题定义和可行性研究；2.软件开发：需求分析、总体设计、详细设计、编码、测试；3.运行维护26软件开发的常用模型1软件过程模型也称为软件生存周期模型。每个过程模型从某个特定视点描述了一个生存期过程，从而提供了有关该过程的特定信息。1.瀑布模型规定了各项软件工程活动极其自上而下，相互衔接的固定次序，如同瀑布流水，所以被称为瀑布模型27软件开发的常用模型22.快速原型模型快速原型模型也称为演进模型，先做试验开发，探索可行性，弄清软件需求；然后在此基础上获得较为满意的软件产品。通常把第一次得到的试验性产品称为“原型”。快速原型开发过程有演进开发和废弃原型两种。28软件开发的常用模型3软件开发的演进方法通常比瀑布方法更有效，可以增量式地开发出需求规格说明，具有较大的灵活性，适合于软件需求不明确，设计方案有一定风险的软件项目。一般对于一个具体的软件开发过程可能会存在着若干方法的组合与交叉。随着软件开发技术的进步，一些新的开发模型与方式也在出现，现有的开发模型也在不断的完善与演变。29软件开发的常用模型4