1
/
62
2018
数据结构总复?/p>
第一?/p>
概论
1.1
数据结构的定义和分类
1.
数据结构的定?/p>
数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的
学科?/p>
2.
数据结构包括的内?/p>
?/p>
1
?/p>
逻辑结构
:数据元素之间的逻辑关系?/p>
?/p>
2
?/p>
存储结构
:数据元素及其关系在计算机存储器内的表示?/p>
?/p>
3
?/p>
操作
:数据的运算(检索、排序、插入、删除、修改)
?/p>
1.2
为什么学习数据结?/p>
1.
学习数据结构的作?/p>
?/p>
1
)计算机内的数值运算依靠方程式,而非数值运算(如表、树、图等)则要依靠数据结构?/p>
?/p>
2
)同样的数据对象,用不同的数据结构来表示,运算效率可能有明显的差异?/p>
?/p>
3
)程序设计的实质是对实际问题选择一个好的数据结构,加之设计一个好的算法。而好的算法在
很大程度上取决于描述实际问题的数据结构?/p>
2.
电话号码查询问题
?/p>
1
)要写出好的查找算法,取决于这张表的结构及存储方式?/p>
?/p>
2
)电话号码表的结构和存储方式决定了查找(算法)的效率?/p>
1.3
算法的概念和特点
1.
算法的概念和特点
算法是由若干条指令组成的有穷序列,具有以下特点:
?/p>
1
?/p>
输入
:具?/p>
0
个或多个输入的外界量?/p>
?/p>
2
?/p>
输出
:至少产?/p>
1
个输出?/p>
?/p>
3
?/p>
有穷?/p>
:每一条指令的执行次数必须是有限的?/p>
?/p>
4
?/p>
确定?/p>
:每条指令的含义都必须明确,无二义性?/p>
?/p>
5
?/p>
可行?/p>
:每条指令的执行时间都是有限的?/p>
2.
算法与程序的区别
?/p>
1
)一个程?/p>
不一?/p>
满足有穷性,但算法一定?/p>
?/p>
2
)程序中的指?/p>
必须
是机器可执行的,而算法无此限制?/p>
?/p>
3
)一个算法若用机器可执行的语言来描述,则它就是一个程序?/p>