绪论
绪论
OkSerIous 发表于9个月前
绪论
  • 发表于 9个月前
  • 阅读 9
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 新注册用户 域名抢购1元起>>>   

简介 
为了编写出一个“好”的程序,必须分析待处理的对象的特性以及各处理对象之间存在的关系,而这就是数据结构这门学科所研究的内容。本部分将介绍数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确切含义和算法设计的基本要求以及从时间和空间角度分析算法。

学习重点 
1、熟悉数据、数据对象、数据元素、数据类型、数据结构等基本概念,特别是数据的逻辑结构与物理结构概念及逻辑结构与物理结构间的关系。
2、了解算法的定义、算法的特性、算法的时间代价、算法的空间代价。
3、掌握计算语句频度和估算算法时间复杂度的方法。

基本概念和术语

在进一步学习《数据结构》之前,必须先理解下面一些概念和术语:

数据(Data)

    数据(Data)是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被程序处理的符号的总称。数据是计算机程序加工的“原料”。例如,一个利用数值分析方法解代数方程的程序,其处理的数据是整数和实数;一个编译程序或文字处理器(比如Word)处理的数据是字符串。因此,对计算机科学而言,数据的含义极为广泛,如图象、声音等都可以通过编码而归之于数据的范畴。


数据元素(Data Element)

    数据元素(Data Element) 是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。比如,包括书名、作者名、分类号、出版单位及出版时间在内的一条书目信息在计算机图书管理程序中被作为一个数据元素来看待。而书名、分类号等被称作数据项(Data Item)。 

数据对象(Data Object)

数据对象(Data Object)是性质相同的数据元素的集合。是数据的一个子集。
例如,整数数据对象的集合可表示为N={0,±1,±2…….},字母字符数据对象的集合可表示为C={‘A’,’B’,…’Z’}。

数据结构(Data Structure)

    数据结构(Data Structure): 是指数据元素之间存在着的一种或多种特定的关系。我们根据数据元素之间关系的不同特性,将数据结构划分为四种类型(见图1.1):

(1)集合 结构中的数据元素之间除了“同属于一个集合”的关系外,别无其它关系;

(2)线性结构 结构中的数据元素之间存在一对一的关系,即相邻数据元素之间具有“前驱”和“后继”的关系;

(3)树形结构 结构中数据元素之间存在一对多的关系;

(4)图状结构或网状结构 结构中数据元素间存在多对多的关系。由于“集合”是数据元素之间关系极为松散的一种结构,因此也可以用其它结构来表示它。 

数据结构的形式定义

数据结构可以被定义成一个二元组: Data_Structure=(D,S),其中,D是数据元素的有限集,S是D上关系的有限集。比如,在计算机科学中,复数作为一种数据结构是这样定义的:Complex=(C,R)其中,C是含两个实数的集合C={c1,c2},R是定义在C上的一种关系集合R={},其中有序偶表示c1是复数的实部,c2是复数的虚部。

上述数据结构的形式定义仅仅是对操作对象的一种数学描述,也就是从操作对象抽象出来的一种数学模型。结构定义中的“关系”描述的是数据元素之间逻辑关系,因此这种形式定义又被称为数据的逻辑结构

但数据的逻辑结构不能描述计算机是如何操作数据的。研究数据结构的目的是为了在计算机中实现对它的操作,因此我们必须研究如何在计算机中表示数据结构,即数据的物理结构

存储结构(Storge Structure):数据结构在计算机中的表示(或称映象)称为数据的存储结构,又称为物理结构
数据结构在计算机中有两种不同的表示方法:顺序表示非顺序表示,由此得出两种不同的存储结构:顺序存储结构链式存储结构

顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
链式存储结构:在每一个数据元素中增加一个存放地址的指针,用此指针来表示数据元素之间的逻辑关系。
在C语言中,顺序存储结构用一维数组来描述,而链式存储结构利用指针来描述。而在实际程序设计过程中,针对一种数据的逻辑结构,到底选择哪种存储结构会影响到具体算法的设计。也就是说,在设计具体算法之前,必须先确定存储结构。在C语言中,一般使用typedef语句来为存储结构定义新的数据类型。

数据类型:在一种程序设计语言中,变量所具有的数据种类。是一个值的集合和定义在这个值集上的一组操作的总称。

学习数据结构的意义

数据结构是计算机软件和计算机应用专业的核心课程之一,在众多的计算机系统软件和应用软件中都要用到各种数据结构。因此,仅掌握几种计算机语言是难以应付众多复杂的课题的。要想有效地使用计算机,还必须学习数据结构的有关知识。

选择合适数据结构解决应用问题
1. 计算机处理问题的分类
(1)数值计算问题
    在计算机发展初期,人们使用计算机主要是处理数值计算问题。
【例2.1】线性方程的求解
     该类问题涉及的运算对象是简单的整型、实型或布尔型数据。程序设计者的主要精力集中于程序设计的技巧,无须重视数据结构。

(2)非数值性问题
     随着计算机应用领域的扩大和软、硬件的发展,"非数值性问题"越来越显得重要。据统计,当今处理非数值性问题占用了90%以上的机器时间,这类问题涉及到的数据结构更为复杂,数据元素之间的相互关系一般无法用数学方程式加以描述。因此,解决此类问题的关键已不再是分析数学和计算方法,而是要设计出合适的数据结构,才能有效地解决问题。

2.非数值问题求解
     著名的瑞士计算机科学家沃思(N.Wirth)教授曾提出:
      算法+数据结构=程序
      数据结构:是指数据的逻辑结构和存储结构
      算法:是对数据运算的描述
     程序设计的实质是对实际问题选择一种好的数据结构,加之设计一个好的算法,而好的算法在很大程度上取决于描述实际问题的数据结构。
【例2.2】电话号码查询问题。
     编一个查询某个城市或单位的私人电话号码的程序。要求对任意给出的一个姓名,若该人有电话号码,则迅速找到其电话号码;否则指出该人没有电话号码。
    要解此问题首先构造一张电话号码登记表。表中每个结点存放两个数据项: 姓名和电话号码。
    要写出好的查找算法,取决于这张表的结构及存储方式。最简单的方式是将表中结点顺序地存储在计算机中。查找时从头开始依次查对姓名,直到找出正确的姓名或是找遍整个表均没有找到为止。这种查找算法对于一个不大的单位或许是可行的,但对一个有成千上万私人电话的城市就不实用了。若这张表是按姓氏排列的,则可另造一张姓氏索引表,采用如下图所示的存储结构。那么查找过程是先在索引表中查对姓氏,然后根据索引表中的地址到电话号码登记表中核查姓名,这样查找登记表时就无需查找其它姓氏的名字了。因此,在这种新的结构上产生的查找算法就更为有效。

共有 人打赏支持
粉丝 31
博文 33
码字总数 4469
×
OkSerIous
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: