我们使用的计算机绝大多数都是冯·诺依曼体系,其理论基础就是”存储程序“概念。数据和操作数据的指令都需要先存储到地址线性表示的内存单元中。数据的一般操作有”增、查、删、改、遍历“等,数据存储需要”存得进、取得出”,需要考虑时间和空间效率,所以要“存数值、存联系”,数据的存储不仅需要保存数据本身,还需要考虑保存数据本身的逻辑关系。 程序要处理的数据有数值类或非数值类两种类型。数值类处理的是纯数值性的信息,如科学和工程计算。数值类数据的关系一般用数学公式或方程来描述。而非数值类问题的数据及数据间的相应关系一般无法用数学公式或方程来描述,如排序问题、检索问题,需要另外设计数据的描述方法和相应的算法来处理。 所以,用计算机解决实际问题,需要对解决的问题进行分析,提炼出问题的两个要素:信息和功能。(数据描述和数据处理的步骤描述,也就是数据结构和算法)。 分析问题中的已知信息,提炼数据和数据之间的联系(数据的逻辑结构),选用合适的存储方式(数据的存储结构)将逻辑结构(数据元素和逻辑关系)存到计算机中,然后在存储结构之上按照自顶向下逐步细化的方法给出算法。这就是程序设计思维的一般过程。 上图中,程序设计将算法”翻译“成相应命令语句及处理形成代码。
下表是一般编程的解题步骤与从软件工程角度看这些步骤的对应关系。
1 数据类型与抽象数据类型计算机对数据的处理,就如同工厂对“物料”的处理一样,物料如同数据,工艺如同算法。一般来说,按照“存储程序”概念,数据需要保存到“一格一格”的内存单元中,根据数据种类、数量的多少、数据元素的复杂程度,对应的数据结构和复杂度也会有所区别。如果数据量少,数据元素联系简单,则用简单的基本数据类型如变量、数组即可描述需要处理的数据,用简单的一些表达式即可描述算法。如果数据量大,数据元素联系复杂(普通数学方程无法描述),则需要定义或选择复杂的数据结构(抽象数据类型),如栈、树、图等,以及复杂的算法。 1.1 数据类型(data type)是一组性质相同的值的集合和定义在集合上的一级操作的总称。 1.2 抽象数据类型(Abstract Data Type,ADT)指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算,而不考虑计算机的具体存储结构和运算的具体实现算法。抽象数据类型中的数据对象和数据运算的声明与数据对象的表示和数据运算的实现相互分离。 一个具体问题的抽象数据类型的定义通常采用简洁、严谨的文字描述,一般包括数据对象(即数据元素的集合)、数据元素关系和基本运算三方面的内容。其基本格式可描述如下:
(Data和Relation一般可以用结构体或类数据成员定义,Operation一般可以用函数(数据结构算法)或类成员函数定义。) 如,线性表的抽象数据类型:
2 数据元素及联系(逻辑结构)现实世界是复杂的,抽象后的数据也有线性、非线性、集合的逻辑关系,而计算机内部的存储单元地址只是线性关系,所以数据元素逻辑关系与实际存储的映射会形成不同的数据结构和算法,会有不同的时间和空间效率。 数据结构的含义包括三个方面-数据的逻辑结构、数据的存储结构以及数据的运算(如增、查、删、改)。数据的逻辑结构体现在数据的联系,数据的存储是数据在计算机中的体现。 3 数据存储(存储结构)3.1 顺序存储结构 Sequential storage strcture 是采用一组连续的存储单元存放所有的数据元素,也就是说,所有数据元素在存储器中占有一整块存储空间,而且两个逻辑上相邻的元素在存储器中的存储位置也相邻。因此,数据元素之间的逻辑关系由存储单元地址间的关系隐含表示,即顺序存储结构将数据的逻辑结构直接映射到存储结构。 顺序存储结构的主要优点是存储效率高,因为分配给数据的存储单元全用于存放数据元素,元素之间的逻辑关系没有占用额外的存储空间;另外,在采用这种存储方法时可实现对元素的随机存储,即每个元素对应一个逻辑序号,由该序号可以直接计算出对应元素的存储地址,从而获取元素值。顺序存储结构的主要缺点是不便于数据修改,对元素的插入或删除操作可能需要移动一系列的元素。 3.2 链式存储结构 Linked storage structure 在链式存储结构中,每个逻辑元素用一个内存结点存储,每个结点是单独分配的,所有的结点地址不一定是连续的,所以无须占用一整块存储空间。为了表示元素之间的逻辑关系,给每个结点附加指针域,用于存放相邻结点的存储地址,也就是通过指针域将所有结点链接起来,这就是链式存储结构名称的由来。 3.3 顺序存储与链式存储二者优、缺点对比
3.4 索引存储结构 Indexed storage structure 索引存储结构是指在存储数据元素信息的同时还建立附加的索引表。存储所有数据元素信息的表称为主数据表,其中每个数据元素有一个关键字和对应的存储地址。索引表中的每一项称为索引项,索引项的一般形式为“关键字,地址”,其中“关键字”唯一标识一个元素,“地址”对应该关键字的元素在主数据表中的存储地址。通常,索引表中的所有索引项是按关键字有序排列的。 在按关键字查找时,首先在索引表中利用关键字的有序性快速查找到该关键字的地址,然后通过该地址在主数据表中找到对应的元素。 索引存储结构的优点是查找效率高。缺点是需要建立索引表,从而增加了空间开销。 3.5 哈希(或散列)存储结构 Hashed storage structure 哈希存储结构的基本思想是根据元素的关键字通过哈希(或散列)函数直接算出一个值,并将这个值作为该元素的存储地址。 哈希存储结构的优点是查找速度快,只要给出待查元素的关键字就可立即计算出该元素的存储地址。与前3种存储方法不同的是,哈希存储方法只存储元素的数据,不存储元素之间的逻辑关系。哈希存储结构一般只适合要求对数据能够进行快速查找和插入的场合。 4 数据运算(增、查、删、改)数据运算是指对数据实施的操作。每种数据结构都有一组相应的运算,最常用的运算有检索、插入、删除、更新和排序等。数据运算最终需要在对应的存储结构上用算法实现,所以数据运算分为运算定义和运算实现两个层面。 5 数据结构具体类型5.1 线性表包括顺序表和链表两种类型。 5.2 栈:操作都在表的一端(栈顶,top)进行,按先入(插入)后出(删除)的方式管理的线性表;栈相对于线性表来说,不需要考虑数组的下标增减等细节,而直接使用对栈的Push和Pop操作。如回退操作、递归调用、函数调用等可以方便地用到这种受限的线性表结构。 5.3 队列:一端插入(队尾)一端删除(队头)的线性表。
5.4 树结构:反映一种层次的纵向关系,如计算机文件系统的目录结构。其存储的数据逻辑关系是每一个结点都有1个或0个双亲(parent)结点,n个或0个子(child)结点。树结构的基本操作包括:构造、插入、删除、遍历、深度、查找等。堆通常是一个可以被看做一棵树(完全二叉树)的数组对象。 5.5 广义表:包含子结构的线性结构,是线性表的推广,但是一种非线性结构类型。 5.6 图结构:数据结构中的图不是几何平面中的图的概念,而是拓扑意义上的图。通常平面几何或立体几何研究的对象是点、线、面之间的位置关系以及它们的度量性质。拓扑学研究几何图形在连续变形下保持不变的性质。如地铁线路图就是应用了拓扑学的原理。通常在平面几何中,把平面上的一个图形搬到另一个图形上,如果完全重合,那么这两个图形叫做全等形。但在拓扑学中,无论图的大小或者形状怎么变化,只要其中点和线的数量不变,它们就是等价图。 图是一种比线性表和树形结构更为复杂的非线性数据结构,图对结点的前驱和后继个数不加限制,各数据元素之间的关系可以是任意的,描述的是“多对多”的关系。在数据结构中,考虑的是图在计算机中的存储和操作。 图是由顶点和边构成,除了要存储结点的信息,还要存储边的信息。另外,图有无向图、有序图、加权图等、
6 算法在分析处理的问题、确定的需要的数据结构、完成了数据的存储之后,接下来的事情就是对数据的加工处理了,对问题求解进行精确描述,也就是算法。 不同的问题有不同的解决方法,同一个问题也可能会有多种算法可供选择。 算法有5个特征。
算法的实现由函数完成。算法设计的一般步骤是:
常用算法:递推法、递归法、穷举法、贪心算法、分治法、动态规划法、迭代法、分支界限法。 算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法,厄米变形模型,随机森林算法。 7 数据处理(数据结构和算法)综述实际问题中数据的处理,一是根据问题中的信息,抽象出信息中的数据与联系,并根据问题的功能要求及数据量的大小,选用合适的存储结构;二是根据功能要求划分模块分别处理;三是测试和调试 如,求一个数的阶乘n! 5.1 问题分析:可以先选择一个数值不太大,又不是特殊点的值,如n=5来设计算法的实现。 5.2 测试样例设计:
5.3 函数接口及功能描述: 5.4 代码实现
5.5 测试结果
|
|