欣诚教育第2章数据结构主要内容算法及其描述数据、数据元素和数据结构线性表rr
栈和队列数组树rr
图rr
查找rr
排序算法及其描述算法是对特定问题求解步骤的一种描述它是指令的有限序列其中每条指令表示一个或多个操作。算法特性rr
有穷性确定性可行性输入零个或多个输入。rr
输出一个或多个输出。rr
程序并不需要满足有穷性算法及其描述算法的描述方式流程图rr
自然语言伪代码程序设计语言rr
C描述算法的唯一要求rr
精确地描述计算过程。算法及其描述算法设计要求评价指标正确性rr
健壮性如对非法数据的处理和反应可读性简单性采用的数据结构和方法的简单程度rr
时间效率高存储空间少算法分析算法复杂度语句频度算法中该语句执行的次数。rr
一个算法中所有语句的频度之和构成该算法的运行时间。一个算法的语句频度是其求解问题规模
的函数记rr
为T
。rr
如果有某个函数F
使得当问题规模
趋于无穷大rr
时有rr
则将OF
称作算法的时间复杂度。lim
∞T
rr
F
rr
常数≠0只需分析rr
主要部分算法分析算法复杂度例下面算法为求
个自然数的和S123…
。请rr
给出该算法的语句频度。rr
sumi
t
rr
i
tis0rr
fori1i
i
1次rr
ssi
次rr
pri
tf“d
”s1次rr
sumT
1
12
2rr
lim
∞T
rr
rr
2≠0rr
算法复杂度为OF
O
基本概念数据Data能被计算机识别、存储和处理的的符rr
号的集合是计算机操作对象的总称。rr
数值、字符图形、图像声音、视频rr
数据元素DataEleme
t数据的基本单位亦rr
称为结点、元素、顶点和记录等。在计算机程序中通rr
常作为一个整体考虑和处理。例如一个学生记录数据项DataItem数据结构中讨论的最小单位数据元素是数据项的集合。亦称为域、字段等。例rr
如学生记录中的学号。数据结构数据结构带结构的数据元素的集合。是相互间存在关系的数据元素集合。数据结构包括3部分内容rr
逻辑结构指数据之间的相互关系。存储结构指数据及其关系在计算机中的存储方式或数据的物理结构。rr
运算指对数据进行检索、插入、删除、合并、排序、统计、简单计算、转换、输入和输出等操作过程。数据结构逻辑结构例如2行3列的二维数组rr
Da1a2a3a4a5a6rr
Rrowcolrr
rowa1a2a2a3a4a5a5a6rr
cola1a4a2a5a3a6不同的关系构成不同的结构集合、线性结构、树形结构、图网状结构a1a2a3a4a5ar