文档介绍：计算机等级考试培训公共基础 算法与数据结构
计算机基础教研室
内容提要
算法的基本概念
数据结构的基本概念
线性表
栈和队列
线性链表
二叉树极其遍历
查找技术
排序技术
算法的基本概念
算法——对解决问题方案的准确而完整的描述(解决问题的操作步骤),流程图、N-S图、文字说明和伪代码。
对数据对象的运算和操作。包括算数运算、逻辑运算、关系运算和数据赋值传输。
运算和操作的控制结构。确定运算和操作的执行顺序,有三种基本结构:顺序结构、选择结构和循环结构,C和VF都支持这三种结构。
特征——可行性、确切性和有穷性(解密算法)
算法的基本概念
算法的复杂度——运行算法所消耗的计算机资源量的多少
时间复杂度:执行算法所需要的计算工作量,即算法执行的基本运算次数,特别提醒,它和算法执行的时间长短是无关的,复杂度=f(n),一般考虑平局复杂度和最坏情况复杂度。
(1)s=0 O(1)
(2) for(i=1;i<=n;i++) s=s+I O(n)
空间复杂度:执行一个算法所需要的内存空间,包括三个方面:数据占用空间、程序占用空间、额外空间占用。
数据结构的基本概念
数据结构——研究非数值计算的程序设计问题中的数据以及它们之间的关系和运算
逻辑关系(结构):数据元素本身和它们的前后件关系
物理关系(结构):逻辑结构在计算机存储空间的存储方式,顺序结构和链式结构
运算:实现的处理方法
线性表
线性表——n(n>=0)个数据元素构成的有限序列,表中除第一个元素,有且只有一个前件,除最后一个元素,有且只有一个后件。表示为(a1,a2,…ai-1,ai,…,an)。
基本特征有:
元素个数n—表长度,n=0空表
1<i<n时
ai的直接前驱是ai-1,a1无直接前驱
ai的直接后继是ai+1,an无直接后继
元素同构,且不能出现缺项
顺序存储结构:逻辑上相邻,物理存储上也相邻(数组)
链式存储结构:用节点来存储数据和逻辑相邻数据的地址,逻辑上相邻,物理上未必相邻(线性链表,双向链表,循环链表)
栈和队列
栈和队列是两种特殊的线性表,是操作受限的线性表
栈(stack)——限定在表的一端插入和删除元素的线性表,遵循“先进后出,后进先出”原则,可以逆序改变元素的顺序
出栈操作和进栈操作
an
a1
a2
……...
栈底
栈顶
...
出栈
进栈
栈s=(a1,a2,……,an)
栈和队列
队列——限定只能在表的一端进行插入,在表的另一端进行删除的线性表,遵循“先进先出,后进后出”原则,入队操作和进队操作。
a1 a2 a3…………………….an
入队
出队
head
tail
队列Q=(a1,a2,……,an)
树的基本概念
定义:树(tree)是n(n>0)个结点的有限集T,其中:
有且仅有一个特定的结点,称为树的根(root)
当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm,其中每一个集合本身又是一棵树,称为根的子树(subtree)
特点:
树中至少有一个结点——根
树中各子树是互不相交的集合
树的基本概念
结点(node)——表示树中的元素,包括数据项及若干指向其子树的分支
根(root)——无前件的节点
度——一个节点拥有的后件个数,树中节点的最大度数
叶子(leaf)——度为0的结点
深度——树的层次数
A
B
C
D
E
F
G
H
I
J
K
L
M