文档章节

绪论

OkSerIous
 OkSerIous
发布于 2017/02/27 20:22
字数 2351
阅读 9
收藏 0
点赞 0
评论 0

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

学习重点 
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】电话号码查询问题。
     编一个查询某个城市或单位的私人电话号码的程序。要求对任意给出的一个姓名,若该人有电话号码,则迅速找到其电话号码;否则指出该人没有电话号码。
    要解此问题首先构造一张电话号码登记表。表中每个结点存放两个数据项: 姓名和电话号码。
    要写出好的查找算法,取决于这张表的结构及存储方式。最简单的方式是将表中结点顺序地存储在计算机中。查找时从头开始依次查对姓名,直到找出正确的姓名或是找遍整个表均没有找到为止。这种查找算法对于一个不大的单位或许是可行的,但对一个有成千上万私人电话的城市就不实用了。若这张表是按姓氏排列的,则可另造一张姓氏索引表,采用如下图所示的存储结构。那么查找过程是先在索引表中查对姓氏,然后根据索引表中的地址到电话号码登记表中核查姓名,这样查找登记表时就无需查找其它姓氏的名字了。因此,在这种新的结构上产生的查找算法就更为有效。

© 著作权归作者所有

共有 人打赏支持
OkSerIous
粉丝 30
博文 34
码字总数 4888
作品 0
贵阳
后端工程师

暂无相关文章

JPA入门,配置文件的设置

<?xml version="1.0" encoding="UTF-8"?> <persistence xmlns="http://java.sun.com/xml/ns/persistence" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http......

码农屌丝 ⋅ 18分钟前 ⋅ 0

Java基础——面向对象和构造器

声明:本栏目所使用的素材都是凯哥学堂VIP学员所写,学员有权匿名,对文章有最终解释权;凯哥学堂旨在促进VIP学员互相学习的基础上公开笔记。 静态成员介绍 为什么要有静态成员?静态成员用来...

凯哥学堂 ⋅ 20分钟前 ⋅ 0

vmware中Centos 7 linux的LVM磁盘扩容

系统是RHEL7(centos7差不多一样) 关闭系统,在vmware、设置、硬盘、扩展、输入数字大于当前系统内存、点击扩展。 开机再查看磁盘信息 fdisk -l 注意:可以看出sda磁盘增加了,但是根目录还...

gugudu ⋅ 30分钟前 ⋅ 0

JAVA线程sleep和wait方法区别

昨天面试,突然被问到sleep 和 wait的区别,一下子有点蒙,在这里记一下,以示警戒。 首先说sleep,sleep就是正在执行的线程主动让出cpu,cpu去执行其他线程,在sleep指定的时间过去后,cpu...

徐玉强 ⋅ 32分钟前 ⋅ 0

vuex学习--模块

随着项目复杂性增加,共享状态也越来越多。需要对转态操作进行分组,分组后在进行分组编写。学习一下module:状态管理器的模块组操作。 首先是声明: const moduleA={ state,mutations,g...

大美琴 ⋅ 35分钟前 ⋅ 0

Selenium 简单入门

安装 pip install selenium 驱动下载 https://chromedriver.storage.googleapis.com/index.html 下载最新的驱动,放入path中,可以放入Python的scripts目录下,也可以放入Chrome安装目录,并...

阿豪boy ⋅ 36分钟前 ⋅ 0

292. Nim Game - LeetCode

Question 292. Nim Game Solution 思路:试着列举一下,就能发现一个n只要不是4的倍数,就能赢。 n 是否能赢1 true2 true3 true4 false 不论删除几,对方都能一把赢5 t...

yysue ⋅ 今天 ⋅ 0

6.5 zip压缩工具 6.6 tar打包 6.7 打包并压缩

zip压缩工具 zip命令可以压缩目录和文件,-r 压缩目录。 zip使用方法 zip 1.txt.zip 1.txt //压缩文件 zip -r 123.zip 123/ //压缩目录 unzip 1.txt.zip //解压 unzip 123.zip -d /root/456...

Linux_老吴 ⋅ 今天 ⋅ 0

react-loadable使用跳坑

官方给react-loadable的定义是: A higher order component for loading components with dynamic imports. 动态路由示例 withLoadable.js import React from 'react'import Loadable fro......

pengqinmm ⋅ 今天 ⋅ 0

记录工作中遇到的坑

1、ios safari浏览器向下滚动会触发window resize事件

端木遗风 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部