绪论本文中主要总结相关概念、数据结构概述、算法分析

介绍

本文主要总结了计算机软件相关概念、数据结构概述、算法和算法分析。

一、计算机软件相关概念

在软件的早期，人们认为软件=程序，然后经历了软件危机。为了顺利度过危机，软件包括程序+文档+数据。

语言主要分为低级语言（机器语言、汇编语言）、高级语言、专用语言。

语言之间的关系

计算机软件的开发

第一阶段：编程时代（1940年代到20年代的1950年代） 这个阶段使用低级语言。

第二阶段：软件时代（1960年代到1970年代） 这个阶段采用高级语言计算机应用基础教案下载，存在软件危机。

第三阶段：软件工程时代（1980年代至今）主要采用面向对象的编程方法。

软件生命周期主要是指软件从开发需求到软件报废的全过程。主要分为三个阶段：规划期、开发期和运行期。

计算机软件主要分为系统软件（操作系统和驱动程序）和应用软件。其系统级图如下：

二、数据结构

将一批按照逻辑关系组织起来的数据按照一定的存储方式存储在计算机中，并在这些数据上定义一组相关的操作。

数据结构分类

数据逻辑结构：数据元素之间的逻辑关系可以看作是从特定问题中得出的数学模型。独立于数据的存储和独立于计算机。

线性结构：线性列表、堆栈、队列、字符串、数组。

非线性结构：树和二叉树、图

数据的存储结构：数据元素及其在计算机内存中的关系的表示，也称为物理结构。

主要包括：顺序存储结构、链式存储结构、索引存储结构、哈希存储结构。（不仅可以单独使用，也可以组合使用）

顺序存储结构：逻辑上相邻的节点存储在物理上相邻的存储单元中，节点之间的逻辑关系通过存储单元的邻接关系来体现。

链式存储结构：不要求逻辑上相邻的节点在物理位置上也相邻，节点之间的逻辑关系用一个额外的指针字段来表示；

数据操作

在逻辑结构上定义的一组操作及其在存储结构上的实现。（具体实现取决于存储结构）。

常用的操作有：检索、插入、删除、定位、修改、排序等计算机应用基础教案下载，这些只是强加在抽象数据上的一系列抽象操作。

数据类型：是数据的取值范围及其定义的操作的总称。例如：浮点数

抽象数据类型 (ADT) 一种数据结构和在此数据结构上定义的一组操作。三重符号

三、算法

算法是解决特定问题的过程（方法和步骤）的计算机描述。

程序是算法的一种实现，计算机按照程序一步一步地执行算法来解决问题。算法 + 数据结构 = 程序

好的算法：正确性、可读性、鲁棒性、效率。

时间和空间往往是取舍，时间换空间，空间换时间。

算法评价指标：时间效率、空间效率、（易懂、易读、易写、易调试）

四个因素影响算法的时间效率：硬件速度、编程语言、代码质量和问题大小。（屏蔽其他人，仅取决于问题大小）

算法的时间成本

当问题的大小在某个单元内从 1 增加到 n 时，相应算法所花费的时间也在某个单元 T（1） 到 T(n) 内增加。此时，我们称时间为算法 T ( n) 的成本。

算法的空间成本

当要解决的问题的大小在某个单元内从 1 增加到 n 时，算法解决问题所占用的空间也在某个单元 G (1） 到 G(n) 中增加，我们称该算法的空间成本为G(n)。

算法效率度量和标准 - 大 O 表示法（跟随学习）。加法和乘法标准。