数据结构与算法导论之基本概念和术语介绍

为了与大家取得“共同的语言”,下面对一些概念和术语赋予确定的含义。

1、数据(data):对客观事物的符号表示,在计算科学中指所有能输入到计算机中并被计算机程序处理的符号总称。

2、数据元素(data element):是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可以由若干个数据项(data item)组成,数据项是数据不可分割的最小单位。

3、数据对象(data object):性质相同的数据元素的组合,是数据的一个子集。

总结而言,数据、数据对象、数据元素和数据项之间的关系可以总结为:数据项是数据不可分割的最小单位,若干个数据项可以组成一个数据元素,性质相同的数据元素是数据对象,而数据对象是数据的一个子集。

4、数据结构(data structure):是相互之间存在一种或多种特定关系的数据元素的集合。这种数据元素相互之间的关系称为结构(structure)。根据数据元素之间的不同特性,通常有下列4类基本结构:

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

(2)、线性结构:结构中的数据元素之间存在一对一的关系;

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

(4)、图状结构或网状结构:结构中的数据元素之间存在多对多的关系;

讨论数据结构的目的是为了在计算机中实现对它的操作,因此还需研究如何在计算机中的表示。

5、数据结构在计算机中的表示或映像成为数据的物理结构,又称存储结构。它包括数据元素的表示和关系的表示。

在计算机中表示信息的最小单位是二进制的一位(bit)。我们可以用一个由若干位组合起来形成的一个位串表示一个数据元素,称为这个位串为元素(element)或结点(node)。当数据元素由若干数据项组成时,位串中对应于各个数据项的子位串称为数据域(data field)。因此,元素或结点可以看成是数据元素在计算机中的映射。

6、数据元素之间的关系在计算机中的有两种不同的表示方法:顺序映射非顺序映射,并由此得到两种不同的存储结构:顺序存储结构链式存储结构

顺序映射的特点:借助元素在存储器中的相应位置表示数据元素之间的逻辑关系。

非顺序映射的特点:借助指示元素存储地址的指针(pointer)表示数据元素之间的逻辑关系。

总而言之,数据的逻辑结构和物理结构是密切相关的两个方面:任何一个算法的设计取决于选定的数据(逻辑)结构,而算法的实现依赖于采用的存储结构。


7、数据类型(data type):是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型(abstract data type,ADT):指一个数学模型以及定义在该模型上的一组操作。

8、算法(algorithm):是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。

一个算法还具有下列5个重要特性:

(1)、有穷性:一个算法必须总是在执行有穷步骤之后结束,且每一步都可在有穷时间内完成;

(2)、确定性:算法中的每一条指令必须有确切的含义,并且在任何条件下,算法只有唯一的一条执行路径,即对于相同的输入只能得到相同的输出;

(3)、可行性:算法中描述的操作都是可以通过已经实现的基本运算执行有限次实现的;

(4)、输入:一个算法有0个或多个输入,这些输入取自于某个特定对象的集合;

(5)、输出:一个算法有一个或多个输出,这些输出是同输入某些特定关系的量。

算法设计的要求:正确性、可读性、健壮性、效率与低存储量需求;

算法效率的度量:时间复杂度和空间复杂度。

时间: 2024-10-29 04:17:03

数据结构与算法导论之基本概念和术语介绍的相关文章

《数据结构与算法:Python语言描述》一2.3类的定义和使用

2.3类的定义和使用 前面给出了两个有理数类的定义,帮助读者得到一些有关Python类机制的直观认识.本节将介绍Python类定义的进一步情况.本书中对类的使用比较规范,涉及的与Python类定义相关的机制不多,只需要有最基本的了解就可以学习后面内容.另一方面,本书的主题是数据结构和算法,并不计划全面完整地介绍Python语言的面向对象机制和各种使用技术.本节主要想给读者提供一些可参考的基本材料,因此,下面有关Python语言的相关介绍将限制在必要的范围内,供读者参考,不深入讨论.有关Pytho

《数据结构与算法:Python语言描述》一1.3算法和算法分析

1.3算法和算法分析 本节集中讨论算法的问题,特别是算法的性质及其分析技术. 1.3.1问题.问题实例和算法 在考虑计算问题时,需要清晰地区分问题.问题实例和算法三个概念,并理解它们之间的关系,这就是本小节讨论的内容.三个基本概念考虑一个计算问题时,需要注意到三个重要概念:问题:一个问题W是需要解决(需要用计算求解)的一个具体需求.例如判断任一个正整数N是否为素数,求任一个方形矩阵的行列式的值等.虽然可以严格定义"问题"的概念,但在这里还是想依靠读者的直观认识.总而言之,现实世界中存在

基本数据结构(算法导论)与python

Stack, Queue Stack是后进先出, LIFO, 队列为先进先出, FIFO 在python中两者, 都可以简单的用list实现, 进, 用append() 出, Stack用pop(), Queue用pop(0), pop的时候注意判断len(l)  对于优先队列, 要用到前面讲到的堆 链表和多重数组 这些数据结构在python中就没有存在的价值, 用list都能轻松实现 散列表 为了满足实时查询的需求而产生的数据结构, 查询复杂度的期望是O(1), 最差为O(n) 问题描述, 对

高效算法的常用技术(算法导论)

对于高效算法, 有些比较简单的技术, 如分治法, 随机化, 和递归求解技术. 这边介绍些更为复杂的技术, 动态规划, 贪心算法 当对于复杂问题设计算法时, 首先会想到使用分治法 来解决, 分而治之, 一个很有哲理性的思路, 再复杂的问题都可以不断分解到你可以轻松解决的粒度, 把所有简单问题都解决完后, 组合在一起就得到了复杂问题的解, 可以看出其中典型的递归求解的思路. 使用分治法的要求, 各个子问题是独立 的 (即不包含公共的子子问题,子问题不重叠 ). 如果子问题重叠, 用分治法就比较低效,

数据结构教程 第一课 数据结构的基本概念和术语

本课主题:数据结构的基本概念和术语 教学目的:了解数据结构的基本概念,理解常用术语 教学重点:基本概念:数据与数据元素 教学难点:数据元素间的四种结构关系. 授课内容: 一.数据.数据元素.数据对象.数据结构的定义 1.数据的定义 定义一:数据是客观事物的符号表示. 学号 姓名 语文 数学 C语言 6201001 张三 85 54 92 6201002 李四 92 84 64 6201003 王五 87 74 73 6201004         ...         例:张三的C语言考试成绩

【算法导论】排序 (二):堆排序

四.(1)堆排序 第一次听堆排序是在107lab听忠哥讲的,但是没讲怎么实现.那时刚看了数据结 构的二叉树,还以为要通过指针建立二叉树的方式来实现,觉得挺难的. 其实堆排序实现没有想象中 的那么难. "堆"这个词最初是在堆排序中提出来的,但后来就逐渐指"废料收集储存区",就像程 序设计语言Lisp和Java中所提供的设施那样.我们这里的堆数据结构不是废料收集存储区. 堆排序的 运行时间与归并排序一样为O(n lg n),  但是一种原地(in place)排序. (

JavaScript中数据结构与算法(三):链表

  这篇文章主要介绍了JavaScript中数据结构与算法(三):链表,本文分别讲解了单链表与双链表以及增加节和删除节的代码实例,需要的朋友可以参考下 我们可以看到在javascript概念中的队列与栈都是一种特殊的线性表的结构,也是一种比较简单的基于数组的顺序存储结构.由于javascript的解释器针对数组都做了直接的优化,不会存在在很多编程语言中数组固定长度的问题(当数组填满后再添加就比较困难了,包括添加删除,都是需要把数组中所有的元素全部都变换位置的,javascript的的数组确实直接

JavaScript中数据结构与算法(五):经典KMP算法

  这篇文章主要介绍了JavaScript中数据结构与算法(五):经典KMP算法,本文详解了KMP算法的方方面在,需要的朋友可以参考下 KMP算法和BM算法 KMP是前缀匹配和BM后缀匹配的经典算法,看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同 前缀匹配是指:模式串和母串的比较从左到右,模式串的移动也是从 左到右 后缀匹配是指:模式串和母串的的比较从右到左,模式串的移动从左到右. 通过上一章显而易见BF算法也是属于前缀的算法,不过就非常霸蛮的逐个匹配的效率自然不用提了O(mn),网上

JavaScript数据结构和算法之二叉树详解

 这篇文章主要介绍了JavaScript数据结构和算法之二叉树详解,本文讲解了二叉树的概念.二叉树的特点.二叉树节点的定义.查找最大和最小值等内容,需要的朋友可以参考下     二叉树的概念 二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两棵互不相交的.分别称为根结点的左子树和右子树的二叉树组成. 二叉树的特点 每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点.二叉树中每一个节点都是一个对象,每一个数据节点都有三个指针,