软考——数据结构总结

一、概念

       数据结构定义:计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

二、研究对象及内容


      1.数据的逻辑结构


       数据的逻辑结构即数据关系的逻辑描述,是指数据元素之间的关联方式或“邻接关系”.按逻辑关系可分有逻辑关      系跟无逻辑关系两大类。存在逻辑关系的可按有无线性关系分为线性关系、非线性关系。其中无逻辑关系的有集        合,存在逻辑关系并且是线性关系的有一维数组、堆、栈,非线性结构的有多维数组、图、树。


      2.数据的物理结构


      数据的逻辑结构在计算机中的实现称为数据的存储结构或物理结构。一个存储结构包含两个部分:存储的数据元素和数据元素之间的关联关系。     

      顺序存储方法:它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现,由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法,通常借助于程序设计语言中的数组来实现。

      链式存储方法:它不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构,链式存储结构通常借助于程序设计语言中的指针类型来实现
      索引存储方法:除建立存储结点信息外,还建立附加的索引表来标识结点的地址。

      散列存储方法:就是根据结点的关键字直接计算出该结点的存储地址。


     3.数据的结构的运算


       运算是指在某种逻辑结构上施加的操作,即对逻辑结构的加工。这种加工以数据的逻辑结构为对象,通常这些对象包括:建立、查找、读取、插入和删除等。


三、数据结构知识点总结


四、计算机解决问题的步骤


       计算机解决一个具体问题时,大致需要经过下列几个步骤:
       1.首先要从具体问题中抽象出一个适当的数学模型
       2.然后设计一个解此数学模型的算法(Algorithm)

       3.编出程序、进行测试、调整直至得到最终解答


五、研究意义


       数据是计算机化的信息,它是计算机可以直接处理的最基本和最重要的对象。无论是进行科学计算或数据处理、过程控制以及对文件的存储和检索及数据库技术应用等,都是对数据进行加工处理的过程。因此,要设计出一个结构好效率高的程序,必须研究数据的特性及数据间的相互关系及其对应的存储表示,并利用这些特性和关系设计出相应的算法和程序。
       数据必须在计算机内存储,数据的存储结构是数据结构的实现形式,是其在计算机内的表示;此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理的效率。所以数据结构与算法的研究是不可分离的。
       在许多类型的程序的设计中,数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明,系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候,确定了数据结构后,算法就容易得到了。有些时候事情也会反过来,我们根据特定算法来选择数据结构与之适应。不论哪种情况,选择合适的数据结构都是非常重要的。选择了数据结构,算法也随之确定,是数据而不是算法是系统构造的关键因素。

原文地址:https://www.cnblogs.com/riskyer/p/3331266.html