计算机概论

计算机概论的思维导图，从宏观上看，数据、数据元素和数据项实际上反映了数据组织的三个层次，数据由个数据元素组成，数据元素由若干个数据项组成。

第一章概论

1.基本概念和术语

数据、数据元素、数据项（数据结构）的概念

识记：概念

数据：所有被计算机存储、处理的对象

数据元素：也称结点、记录、元素，数据和运算的基本单位，在程序中作为一个整体而加以考虑和处理。

数据项：在数据库中数据项又称为字段或域，是数据的不可分割的最小标识单位。一般情况下，数据元素由数据项组成。

数据结构：计算机组织数据和存储数据的方式。更进一步说，是一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机内的存储方式，以及定义在该组数据上的一组操作。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。包括了数据的逻辑结构、存储结构和基本运算。

数据结构的作用

逻辑结构：数据元素之间的逻辑关系。只是一种数据模型，体现了数据的组织方式，要在计算机中实现逻辑结构，依赖计算机中的存储结构。

存储结构：数据的逻辑结构在计算机中的实现称为数据的存储结构（或物理结构）

存储数据元素

数据元素之间的关联方式

关联方式主要有顺序存储方式和链式存储方式

除以上两种，还有索引存储方式和散列存储方式

数据元素之间抽象化的相互关系，与数据存储无关

用机器级和语言级描述存储结构

机器级：讨论存储结构在计算机存储器里的表示形式，直接以内存地址来描述存储结构。

语言级：用程序设计语言中的类型说明、变量说明等手段来描述存储结构。一般语言中有几种常用的数据类型，如数组、结构体和指针等，用这些类型可以构造出更复杂的存储结构。

语言级存储描述可经编译器转换成机器级，因此可以看成一种机内表示。

基本运算

数据、数据元素和数据项三者关系

从宏观上看，数据、数据元素和数据项实际上反映了数据组织的三个层次，数据由个数据元素组成，数据元素由若干个数据项组成

数据的逻辑结构、存储结构

四类基本逻辑结构的特点

集合

线性结构

树形结构

图结构

顺序存储结构

顺序存储结构是指所有存储结点存放在一个连续的存储区里。利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。

链式存储结构

链式存储方式是指每个存储结点除了含有一个数据元素外，还包含指针，每个指针指向一个与本结点有逻辑关系的结点，用指针表示数据元素之间的逻辑关系。

逻辑结构和存储结构的关系

关系：一种逻辑结构可以常用一种或几种存储方式来表达数据元素之间的逻辑关系，相应的存储结构称为给定逻辑结构的存储实现或存储映象。逻辑结构依赖于存储结构。

运算

运算与数据结构的关系

关系：线性表、栈和队列中的元素具有相同的逻辑结构（即线性结构），但不同的运算集，他们是不同的数据结构。

基本运算

运算的概念：某种

运算的概念：某种逻辑结构上施加的操作，即对逻辑结构的加工。这种加工以数据的逻辑结构为对象。 一般来说，在每个逻辑结构上，都定义了一组基本运算，这些运算包括：建立、查找、读取、插入和删除等。

2.算法

算法及描述

算法的描述方法

算法可以用某种语言（类c语言）加以描述。

1.函数描述形式 函数类型 函数名（函数参数表） ／／算法说明 ｛ 语句序列 2.输入、输出语句 输入语句：scanf（格式串，变量1，……，变量n） 输出语句：printf（格式串，变量1，……，变量n） 3.赋值语句 变量名＝表达式 4.选择语句 ⑴条件语句 if（表达式）语句 或 if（表达式）语句 else语句 ⑵分支语句： switch ｛ case条件1：语句序列；break； case条件2：语句序列；break； …… case条件n：语句序列；break； default： 语句序列； ｝ 其中“default：语句序列；”可以省略。 5.循环语句 for（赋初值表达式序列；条件；修改表达式序列）语句； while（条件）语句； do｛ 语句； ｝while（条件）； 6.结束语句 ⑴函数结束语句：return表达式； ⑵case结束语句：break； ⑶异常结束语句：exit（异常代码）； 7.出错语句error（“错误描述”） 8.注释 单行注释：／／注释内容 多行注释：／* 注释内容

算法的评价因素

算法

运算的实现是指该运算的算法。 算法是计算机科学的一个基本概念，也是程序设计的一个核心概念。

算法分析

正确性 能正确的实现预定的功能，满足具体问题的需要。

易读性 易于阅读、理解和交流，便于调试、修改和扩充

健壮性 即使输入非法数据，算法也能适当的做出反应或进行处理，不会产生预料不到的运行结果

时空性（高效性） 一个算法的时空性是指该算法的时间性能或时间效率和空间性能或空间效率，前者是算法包含了计算量，后者是算法需要的存储量

算法分析

时间复杂度

时间复杂度分析方法

时间复杂度可能具有指数阶的算法是实际不可计算的，而阶数低于平方阶的算法是高效率的。

算法的渐进时间复杂度(简称时间复杂度)：T(n)＝O(f(n))

空间复杂度

空间复杂度分析方法

存储量和空间复杂度的概念与计算量和时间复杂度的概念类似。 一个算法的空间复杂度定义为该算法所耗费的存储空间，它也是问题规模n的函数。 通常可记为：S(n)＝O(g(n)) g(n)是问题规模n的某个函数。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。 一个在执行期间所需要的存储空间量包括以下三个部分： ⑴程序代码所占用的空间 ⑵输入数据所占用的空间 ⑶辅助变量所占用的空间

程序代码

程序代码所占用的空间对不同的算法来说也不会有数量级的差别。

输入数据

在算法执行过程中，输入数据所占用的空间是由问题所决定的。

辅助变量

辅助变量占用的空间则由算法决定

在估算算法空间复杂度时，一般只需要分析辅助变量所占用的空间。

3.简单应用

运用类c语言描述算法

简单算法时间复杂度分析

简单算法的空间复杂度分析