内容纲要

一、数据结构的基本概念和术语

数据: 是描述客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称

数据元素:是数据的基本单位,是数据集合中的一个实体,是计算机程序中加工处理的基本单位,在计算机中通常作为整体处理,也称为节点、记录。

数据项: 一个数据元素可以由若干个数据项组成。数据项是数据不可分割的最小单位。

数据对象:是性质相同的数据元素的集合,是数据的一个子集。

数据结构:是相互之间存在一种或多种特定关系的数据元素的集合,数据结构的形式定义是一个二元组。 Data_Structure=(D,R) 其中 D 是数据元素的有限集;R 是 D 上关系的有限集。

逻辑结构:是指数据对象中数据元素之间的相互关系。

  1. 集合结构:集合结构中的数据元素除了同属于一个集合外,它们之间没有其他关系。
  2. 线性结构:线性结构中的数据元素之间是一对一的关系。
  3. 树形结构:树形结构中的数据元素之间是一对多的关系。
  4. 图状结构或网状结构:图状结构中的数据元素之间是多对多的关系。

存储结构: 是指数据的逻辑结构在计算机中的存储形式,数据结构在计算机中的表示称为(又称映像)称为数据的物理结构,又称存储结构。它包括数据元素的表示和关系表示。在计算机中表示信息的最小单位是二进制数的一位,叫做位(bit)。在计算机中,我们可以用一个由若干位组合起来形成的一个位串表示一个数据元素,通常称这个位串为元素或结点。当数 据元素由若干数据项组成时,位串中对应于各个数据项的字位串称为数据域。

  1. 顺序存储结构:又称顺序映像,是把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的。
  2. 链式存储结构: 又称非顺序映像,是把数据元素放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的。 由指针域的指向来表示各个节点的关系。
  3. 索引存储结构:除建立存储结点信息外,还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。
  4. 散列存储结构:又称hash存储,是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。

二、抽象数据类型的概念

数据类型:是指一组性质相同的值的集合以及在此集合上的一些操作的总称。

抽象数据类型:(abstract data type简称ADT)是指一个数学模型及定义在该模型上的一组操作。 仅取决于它的逻辑特性与在计算机中的如何实现和表示无关,抽象在于数据类型的数学抽象特性。ADT 的形式化定义是三元组:ADT=(D,S,P) ,D 是数据对象,S 是 D 上的关系集,P 是对 D 的基本操作集。

三、抽象数据类型的表示与实现

  1. 用自然语言表示算法
  2. 用流程图表示算法
  3. 用伪代码表示算法
  4. 用计算机语言表示算法
  5. 用类 C 或类 PASCAL 语言算法描述 (介于伪码和c之间)

选择算法描述语言的准则

  1. 该语言应该具有描述数据结构和算法的基本功能
  2. 该语言应该尽可能地简捷,以便于掌握、理解
  3. 使用该语言描述的算法应该能够比较容易地转换成任何一种程序设计语言

四、算法和算法分析

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

特性:

  1. 有穷性:一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束,每一步都在有穷的时间内完成。
  2. 确定性:算法中每一条指令必须有确切的含义,读者理解是不会产生二义性。
  3. 可行性:一个算法是能行的,即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
  4. 输入:一个算法有零个或多个输入。
  5. 输出:一个算法有零个或多个输出。(同输入有某些特定关系的量)

算法设计的要求

  1. 正确性:算法应当满足具体问题的需求
  2. 可读性:算法主要为了人的阅读与交流,其次才是机器执行。
  3. 健壮性:当时输入数据非法时,算法也能适当地做出反应或进行处理。而不会产生莫名其妙的输出结果。
  4. 效率与低存储量需求:算法执行的时间和算法执行过程中所需要的最大存储空间。

算法的时间复杂度:算法中基本操作重复执行的次数是问题规模 n 的某个函数,其时间量度记作 T(n) = O(f(n))

度量一个程序的执行时间通常有二种方法:事后统计的方法、事前分析估算的方法

  • 用常数1取代运行时间中的所有加法常数
  • 在修改后的运行次数函数中,只保留最高阶项。
  • 如果最高阶项存在且不为1,则去除与这个项相乘的常数。
执行次数函数非正式术语
12O(1)常数阶
2n+2O(n)线性阶
n^2+2n+1O(n^2)平方阶
n^3+ n^2+2n+1O(n^3)立方阶
3log2nO(logn)对数阶
nlog2nO(nlogn)nlogn阶
2^nO( 2^n )指数阶

时间复杂度从小到大排序: O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O( 2^n ) <O(n!)<O(n^n)

算法的空间复杂度:一个算法的空间效率是指在算法的执行过程中,所占据的辅助空间数量。 S(n)=O(f(n))

最后修改日期:2020年4月11日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。