数据结构导论之第一章(概论)

 一、引言

数据结构(Data structure):是计算机组织数据和存储数据的方式，是指一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机内的存储方式，以及定义在该组数据上的一组操作。

数据结构：数据的逻辑结构+数据的存储结构+数据的基本运算

计算机解决问题的步骤：

• 1、建立数学模型
• 2、设计求解算法
• 3、编程实现算法(运用各种计算机语言实现算法)

1976年瑞士计算机科学家尼克劳斯·维尔特[Niklaus Wirth]提出：算法+数据结构=程序

二、基本概念和术语

数据(Data)：所有能被计算机处理的符号的集合。实际问题中的数据称为原始数据
数据元素(Data Element):是数据这个集合中的一个个体即数据的基本单位。
数据项(Data Item)：数据元素常常还可分为若干个数据项，数据项是数据具有意义的最小单位；数据库中，数据项又称为字段/域,它是数据的不可分割的最小标识单位。

1、数据的逻辑结构：数据的逻辑结构是指数据及数据的组织方式，是一种数学模型；指数据元素之间的结构关系

数据的逻辑结构(D, {R}) 可分为下列几种: D = {d1,d2, …, dn}

• ◆ 集合: 数据元素同“属于一个集合”。R = { }。任意两个结点之间都没有邻接关系，组织形式松散
• ◆ 线性结构: R= {(d1, d2), (d2, d3), …, (dn-1, dn)}，即除起始节点和终端结点d1、dn外，每个节点有一个前驱和一个后继；结点按逻辑关系依次排列形成一条“链”，结点之间一个一个依次相邻接。
• ◆ 树形结构: (D, {R}) 构成树，即每个元素最多有一个前驱，可以有多个后继；具有分支、层次特性，上层的结点可以和下层多个结点相邻接，但下层结点只能和上层的一个结点相邻接
• ◆ 图结构: (D, {R})构成一个图；最复杂，任何两个结点都可以相邻接。

2、数据的存储结构(物理结构)：数据的存储结构是指数据的逻辑结构在计算机中的表示，数据的存储结构分为顺序存储结构和链接存储结构两种。

存储结构的主要部分：

• 存储结点：每个存储结点存放一个数据元素
• 元素逻辑关系：数据元素之间关联方式的表示

数据结构的存储=数据元素的存储+元素逻辑关系的存储

元素关联关系的存储方式主要有：

• 顺序存储方式：指所有存储节点存放在一个连续的存储区里，利用节点在存储器中的相对位置来表示元素之间的逻辑关系
• 链式存储方式：指每个存储点除了包含一个数据元素外，还包含指针，每个指针指向一个与本节点有逻辑关系的节点，用指针表示数据元素之间的逻辑关系
• 索引存储方式
• 散列存储方式

=============顺序存储方式=================

顺序存储方式：借助数据元素的相对存储位置来表示数据的逻辑结构；
线性表的顺序存储方法：将表中的结点一次存放在计算机内存中一组连续的存储单元中。
顺序的方法: 将元素存储到一片连续的存储区
特点：

• 1、 预先分配好长度，需要预估存储数据需要的存储量；
• 2、插入和删除需要移动其他元素；
• 3、存取快捷，是随机存取结构。

=============链式存储方式=================

链式存储方式：借助数据元素地址的指针表示数据的逻辑结构；这种结构是给结点附加一个指针字段，指出其后继节点的位置，即存放结点的存储单元分为两部分:数据项和指针项

特点：

•  动态分配，不需要预先确定内存分配；
•  插入和删除不需要移动其他元素；
•  非随机存取结构

===========索引存储方式===============

索引存储方式：借助索引表中的索引指示各存储节点的存储位置。

===========散列存储方式===============
散列存储方式：用散列函数指示各节点的存储位置。

3、运算

运算：指在某种逻辑结构上施加的操作，即对逻辑结构的加工。
加工型运算：其操作改变原逻辑结构的值；如：结点个数，结点内容等。
引用型运算：其操作不改变原逻辑结构的值。

基本运算：建立(创建)、查找 、读取 、插入 、删除

三、算法及描述

算法：算法规定了求解给定类型问题所需的所有“处理步骤”及执行顺序，使给定类型问题能在有限时间内被机械的求解。

算法必须使用某种语言描述：

• 程序
• 介于自然语言和程序设计语言的伪代码
• 非形式算法（自然语言）
• 框图(N-S图)

一个算法是对特定问题求解步骤的一种描述，它是指令的有穷序列。
算法具有以下特性：

• ① 有穷性: 一个算法总是在执行有穷步后结束。
• ② 确定性: 算法的每一步都必须是明确地定义的。
• ③ 可行性: 算法中的每一步都是可以通过已经实现的操作来完成的。
• ④ 输入: 一个算法有零个或者多个输入，这些输入取自于特定的对象集合。
• ⑤ 输出：一个算法有一个或者多个输出，它们是与输入有特定关系的量。

四、算法分析

算法的设计应满足：

• ① 正确性：对于合法的输入产生符合要求的输出。
• ② 易读性：算法应该易读、便于交流， 这也是保证算法正确性的前提；添加注释也是一种增加可读性的办法。
• ③ 健壮性：当输入非法数据时， 算法还能做出适当的反应而不会崩溃，如输出错误信息；算法中应该考虑适当的错误处理。
• ④ 时空性：指算法的时间复杂度和空间复杂度，算法分析主要分析算法的时间复杂度和空间复杂度，目的是提高算法的效率。

最优算法的2个度量：

• 时间复杂度：算法运行时需要的总步数，通常是问题规模的函数。
• 空间复杂度：算法执行时所占用的存储空间，通常是问题规模的函数

确定算法的计算量:

• 合理地选择一种或几种操作作为“标准操作”，无特殊说明，默认以赋值语句作为标准操作；确定每个算法共执行多少次标准操作，并将此次数规定为该算法的计算量。
• 算法的最坏情况时间复杂度：以算法在所有输入下的计算量的最大值作为算法的计算量。
• 算法的平均情况时间复杂度：以算法在所有输入下的计算量的加权平均值作为算法的计算量。
• 最坏情况时间复杂度和平均情况时间复杂度统称为时间复杂度

================时间复杂度================

 运行该代码需要1秒 ，时间复杂度记作O(1)

 运行该代码需要n*1秒 时间复杂度记作O(n)

 运行该代码需要n*n*1秒 时间复杂度记作O(n*n);

 ================空间复杂度===============

空间复杂度:是对一个算法在运行过程中临时占用存储空间大小的量度;估算算法空间复杂度时，一般只分析辅助变量所占用的空间。
一个算法在执行期间所需要的存储空间量包括以下部分：

•  程序代码所占用的空间；
•  输入数据所占用的空间；
•  辅助变量所占用的空间；