文档介绍：计算机基础
课程目录
计算机基础知识
数据结构与算法
计算机网络
多媒体
操作系统
Office 2010
数据结构与算法
算法的基本概念
数据结构基本概念
常用的数据结构
常用算法
算法的基本概念
指令:告诉计算机执行某一特殊操作的代码;如鼠标的单击、双击等
算法:是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令集合
针对同一个问题,可能会有不同的算法方案,不同的算法可能用不同的时间、空间或效率来完成任务
算法的特征
有穷性:是指算法必须能在执行有限个步骤之后终止
确切性:算法的每一步骤必须有确切的含义
输入项:一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定出了初始条件
输出项:一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的
可行性:算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步,即每个计算步都可以在有限时间内完成(也称之为有效性)
算法好坏的评判标准
算法的好坏从以下五个方面进行评定
时间复杂度:是指执行算法所需要的计算工作量
计算公式为:T(n) = O(f(n)),n代表问题的复杂度
因此问题的复杂度越高算法的执行的时间的增长率越高
空间复杂度:是指算法需要消耗的内存空间,其计算方式与时间复杂度相似
正确性:评价一个算法优劣的最重要的标准
可读性:是指一个算法可供人们阅读的容易程度
健壮性:是指一个算法对不合理数据输入的反应能力和处理能力,也称为容错性
数据结构
基本概念
数据项:是数据结构中讨论的最小单位,是数据记录中最基本的、不可分的有名数据单位,是具有独立含义的最小标识单位
数据元素:它是数据的基本单位
数据结构:是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合
数据处理包括插入、删除、查找、排序等
数据结构
数据结构
数据元素
数据项
包含
包含
常用的数据结构
线性结构
线性表:是最简单、最基本、也是最常用的一种线性结构
顺序存储:逻辑上相邻的结点在物理存储地址上也是相邻的
链式存储:逻辑上相邻的结点在物理存储地址上可以相邻的,也可以不相邻,通常不相邻
栈:又名堆栈,它是一种运算受限的线性表,按“后进先出”的规则进行操作
队列:和栈一样是一种运算受限的线性表,按“先进先出”的规则进行操作
按拼音查看,文字的顺序和拼音的顺序一致
按部首查看,文字的顺序和拼音的顺序基本不一致
88
65
77
88
79
80
常用的数据结构
非线性结构
树:有限结点组成一个具有层次关系的集合
节点的度:一个节点含有的子树的个数称为该节点的度
叶节点或终端节点:度为0的节点称为叶节点;
非终端节点或分支节点:度不为0的节点;
双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;
孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;
兄弟节点:具有相同父节点的节点互称为兄弟节点;
树的度:一棵树中,最大的节点的度称为树的度;
节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
树的高度或深度:树中节点的最大层次;
堂兄弟节点:双亲在同一层的节点互为堂兄弟;
节点的祖先:从根到该节点所经分支上的所有节点;
子孙:以某节点为根的子树中任一节点都称为该节点的子孙。
森林:由m(m>=0)棵互不相交的树的集合称为森林;
A
B
C
D
E
F
G
H
I
J
K
L
M
N
常用的数据结构
二叉树:每个节点最多含有两个子树的树称为二叉树
二叉树的遍历
先序:根→左→右
A B D H J I E C F G
中序:左→根→右
J H D I B E A F C G
后序:左→右→根
J H I D E B F G C A
A
B
C
D
E
F
G
H
I
J